결정 집합

집합론과 일반위상수학에서 결정 집합(決定集合, 영어: determined set)은 두 사람이 번갈아서 자연수를 고르는 게임에서, 항상 두 사람 가운데 하나가 필승 전략을 갖게 되는 집합이다. 결정 공리(決定公理, 영어: axiom of determinacy, 약자 ${\displaystyle {\mathsf {AD}}}$)는 자연수열 공간의 모든 부분 집합이 결정 집합이라는 명제이다.^[1] 결정 공리는 선택 공리와 모순되지만, 제한된 형태는 선택 공리와 일관적일 수 있다.

다음과 같은 데이터가 주어졌다고 하자.

• 집합 ${\displaystyle A}$
• ${\displaystyle A}$의 원소의 열들의 집합 ${\displaystyle X\subseteq A^{\omega }}$. 이를 승패 집합(勝敗集合, 영어: payoff set)이라고 한다.
• ${\displaystyle A}$에 이산 위상을 부여하고, ${\displaystyle A^{\omega }}$에 곱위상을 부여하였을 때, 공집합이 아닌 닫힌집합 ${\displaystyle \varnothing \neq [T]\subseteq A^{\omega }}$. 이는 마찬가지로 나무 ${\displaystyle T=\textstyle \bigcup _{n<\omega }\{t\upharpoonright n\colon t\in T\}\subseteq A^{<\omega }}$로 나타낼 수 있다. 나무 ${\displaystyle T}$를 허용된 수의 나무(許容된 手의 나무, 영어: tree of allowed positions)라고 한다.

이제 다음과 같은 2인(人) 게임을 생각하자.^{[2]:237, §5[3]:137, §20.A}

1. 두 선수 갑(甲)과 을(乙)이 있다.
2. 갑과 을은 수(手)를 두는 것을 반복하며, 갑이 먼저 수를 둔다. 여기서, 수를 둔다는 것은 ${\displaystyle a\in A}$를 고르는 것이다. 수들을 ${\displaystyle k=(k_{0},k_{1},k_{2},\dots )}$라고 하자. (즉, 갑은 ${\displaystyle k_{0},k_{2},k_{4},\dots }$를 두고, 을은 ${\displaystyle k_{1},k_{3},k_{5},\dots }$를 둔다.) 각 선수는 이전에 놓인 모든 수(手)들을 알고 있다. 또한, 각 ${\displaystyle i<\omega }$에 대하여 ${\displaystyle (k_{0},k_{1},\dots ,k_{i-1})\in T}$이어야만 한다.
3. 만약 ${\displaystyle (k)_{i<\omega }\in X}$라면 갑이 이기며, 아니라면 을이 이긴다.

전략(戰略, 영어: strategy)은 함수 ${\displaystyle A^{<\omega }\to A}$이다. 여기서

${\displaystyle A^{<\omega }=\bigsqcup _{n<\omega }A^{n}}$

는 ${\displaystyle A}$ 속의 유한열들의 집합이다. 갑의 필승 전략(甲의必勝戰略, 영어: winning strategy for the first player)은 다음 조건을 만족시키는 전략 ${\displaystyle \sigma \colon A^{<\omega }\to A}$이다.

임의의 열 ${\displaystyle (t_{i})_{i\in \mathbb {N} }\in A^{n}}$에 대하여, 다음이 성립한다.

${\displaystyle \left(\sigma (),t_{0},\sigma (t_{0}),t_{1},\sigma (t_{0},t_{1}),t_{2},\sigma (t_{0},t_{1},t_{2}),\ldots \right)\in X}$

을의 필승 전략(乙의必勝戰略, 영어: winning strategy for the second player)은 다음 조건을 만족시키는 전략 ${\displaystyle \sigma \colon A^{<\omega }\to A}$이다.

임의의 열 ${\displaystyle (s_{i})_{i<\omega }\in A^{n}}$에 대하여, 다음이 성립한다.

${\displaystyle \left(s_{0},\sigma (s_{0}),s_{1},\sigma (s_{0},s_{1}),s_{2},\sigma (s_{0},s_{1},s_{2}),\ldots \right)\not \in X}$

${\displaystyle X\subseteq A^{\omega }}$에 대하여, 만약 위 게임에서 갑과 을 가운데 하나가 필승 전략을 갖는다면, ${\displaystyle X}$가 ${\displaystyle T}$로 정의되는 게임에 대한 결정 집합(決定集合, 영어: determined set)이라고 한다.^{[3]:137, §20.A} 만약 ${\displaystyle T}$가 명시되지 않았다면, ${\displaystyle T=A^{<\omega }}$이다.

이제, 다음과 같은 명제들을 정의할 수 있다.

• 결정 공리(決定公理, 영어: axiom of determinacy) ${\displaystyle {\mathsf {AD}}}$에 따르면, 모든 집합 ${\displaystyle X\subseteq \mathbb {N} ^{\omega }}$은 결정 집합이다.
• 실수 정의 가능 결정 공리(實數定義可能決定公理, 영어: axiom of real-definable determinacy) ${\displaystyle {\mathsf {AD}}^{L(\mathbb {R} )}}$에 따르면, 모든 집합 ${\displaystyle X\subseteq \mathbb {N} ^{\omega }\cap L(\mathbb {R} )}$은 결정 집합이다. 여기서 ${\displaystyle L(\mathbb {R} )}$은 실수 구성 가능 집합들의 누적 위계이다.
• 사영 결정 공리(射影決定公理, 영어: axiom of projective determinacy) ${\displaystyle {\mathsf {PD}}}$에 따르면, 모든 사영 집합 ${\displaystyle X\subseteq \mathbb {N} ^{\omega }}$에 대하여 선수 1이 필승 전략을 갖거나, 아니면 선수 2가 필승 전략을 갖는다.

ZFC에서는 다음 성질들을 증명할 수 있다.

• 모든 보렐 집합은 결정 집합이다.^{[3]:140, Theorem 20.5[4][5]}
• 모든 결정 집합은
  • 보편 가측 집합이며,
  • 준열린집합이며,
  • 완전 집합 성질을 만족시킨다.

선택 공리에 의하면 르베그 가측 집합이 아닌 집합이 존재하므로, 결정 집합이 아닌 집합이 존재한다.

체르멜로-프렝켈 집합론 + 결정 공리는 선택 공리의 부정을 함의하며, 또한 체르멜로-프렝켈 집합론의 일관성을 증명할 수 있다.

${\displaystyle {\mathsf {ZF}}+{\mathsf {AD}}\vdash \lnot {\mathsf {AC}}}$

${\displaystyle {\mathsf {ZF}}+{\mathsf {AD}}\vdash \operatorname {Con} ({\mathsf {ZF}})}$

체르멜로-프렝켈 집합론 + 결정 공리를 가정하면, ZFC에서 성립하지 않는 다음 명제들이 성립한다.

• 실수 집합의 모든 부분 집합은 르베그 가측 집합이다.
• 실수 집합의 모든 부분 집합은 준열린집합이다.
• 실수 집합의 모든 부분 집합은 완전 집합 성질을 만족시킨다.
• 실수 집합의 모든 부분 집합은 가산 집합이거나, 아니면 크기가 실수 집합 전체와 같다.

반면, 결정 공리보다 더 약한 공리 ${\displaystyle {\mathsf {AD}}^{L(\mathbb {R} )}}$는 선택 공리와 모순되지 않는다고 여겨진다.

충분히 강한 큰 기수의 존재를 가정하면, ${\displaystyle {\mathsf {AD}}^{L(\mathbb {R} )}}$를 증명할 수 있다.^[6][7] 구체적으로, 결정 공리들의 충분 조건은 다음과 같다.

• 가산 무한 개의 우딘 기수가 존재한다면, ${\displaystyle {\mathsf {PD}}}$가 성립한다.
• 가산 무한 개의 우딘 기수가 존재하며, 이들보다 더 큰 (하나 이상의) 가측 기수가 존재한다면, ${\displaystyle {\mathsf {AD}}^{L(\mathbb {R} )}}$가 성립한다.

구체적으로, 다음 두 명제가 서로 동치이다.^[8]:1147

• ${\displaystyle {\mathsf {PD}}}$
• 임의의 자연수 ${\displaystyle n}$에 대하여, (ZFC + ${\displaystyle n}$개의 우딘 기수가 존재한다)로부터 유추할 수 있는, 산술의 2차 논리 언어로 나타낼 수 있는 모든 명제가 참이다.

즉, 이에 대하여 존 로버트 스틸(영어: John Robert Steel)은 다음과 같이 적었다.

“	${\displaystyle {\mathsf {PD}}}$는 정확히 우딘 기수의, 산술 2차 논리 언어에서의 ‘도구주의적 자취’이다. ${\displaystyle {\mathsf {PD}}}$ is precisely the “instrumentalist’s trace” of Woodin cardinals in the language of second-order arithmetic.	”
	— [8]:1147

여기서 도구주의는 어떤 이론을 단순히 어떤 실용적인 목표를 이루기 위한 도구로 여기는 철학이다. 즉, 만약 우딘 기수의 존재를 단순히 산술의 2차 논리 언어에서의 정리들을 증명하기 위한 도구로 생각한다면, 이러한 도구로서 (가산 무한 개의) 우딘 기수들의 존재는 ${\displaystyle {\mathsf {PD}}}$와 동치이다.

위와 같은 꼴의 게임은 스타니스와프 울람이 1935년에 도입하였다. 당시 리비우에 살던 수학자들은 슈코츠카 카페(폴란드어: Kawiarnia Szkocka 카비아르니아 슈코츠카^[*], 폴란드어: szkocka 슈코츠카^[*]는 폴란드어: Szkocja 슈코치아^[*](스코틀랜드)의 형용사형)에 모여서 수학 문제들을 토론하였으며, 토론에 의하여 얻은 결과들을 "슈코츠카 책"(폴란드어: Księga Szkocka 크시엥가 슈코츠카^[*])이라는 노트에 기록하였다. 여기서 울람은 바나흐-마주르 게임(슈코츠카 책의 43번 문제)을 약간 변형한 다음과 같은 게임을 제시하였다.^{[9]:116, Problem 43}

“

실수 집합 ${\displaystyle E}$가 주어졌다고 하자. 선수 A와 B가 번갈아서 0 또는 1을 제시한다. 선수 A가 승리할 조건은, 숫자들이 (이진수로 해석하였을 때) 집합 ${\displaystyle E}$에 속하는 것이다. 어떤 집합의 경우 선수 A(또는 선수 B)가 필승 전략을 갖는가? — S. 울람 Dany jest zbiór liczb rzeczywistych ${\displaystyle E}$. Gracze A i B podają na przemian cyfrę 0 lub 1. Gracz A wygrywa, jeśli liczba utworzona z tych cyfr w podanym porządku (w systemie dwójkowym) należy do zbioru ${\displaystyle E}$. Dla jakich zbiorów istnieje metoda wygrania dla gracza A (gracza B)? — S. Ulam

”

결정 공리는 얀 미치엘스키와 후고 스테인하우스가 1962년에 도입하였다.^{[10][11][12]:737}

ZFC만을 사용한, 실수의 부분 집합의 결정 집합 여부에 대한 정리들의 역사는 다음과 같다.

• 1953년에 데이비드 게일(영어: David Gale)과 프랭크 스튜어트(영어: Frank M. Stewart)가 모든 열린집합이 결정 집합임을 증명하였다.^[13]
• 1955년에 필립 울프(영어: Philip Wolfe)는 ${\displaystyle {\boldsymbol {\Sigma }}_{2}^{0}}$ 집합이 결정 집합임을 증명하였다.^[14]
• 1964년에 모턴 데이비스(영어: Morton Davis)는 ${\displaystyle {\boldsymbol {\Sigma }}_{3}^{0}}$ 집합이 결정 집합임을 증명하였다.^[15]
• 1972년에 제프리 브루스 패리스(영어: Jeffrey Bruce Paris)는 ${\displaystyle {\boldsymbol {\Sigma }}_{4}^{0}}$ 집합이 결정 집합임을 증명하였다.^[16]
• 1975년에 도널드 앤서니 마틴(영어: Donald Anthony Martin)이 모든 보렐 집합이 결정 집합임을 증명하였다.^[4]

${\displaystyle L(\mathbb {R} )}$에 제한한 결정 공리의 각종 흥미로운 성질들 및 큰 기수와의 관계가 밝혀지면서, 이후 일부 수학자들은 ${\displaystyle L(\mathbb {R} )}$에 제한한 결정 공리를 자유로이 가정하거나, 심지어 집합론의 공리로 제시하기도 하였다. 예를 들어, 이 내용을 다루는 집합론 교재들은 실수 정의 가능 결정 공리에 대하여 다음과 같이 적는다.

“	지난 25년 동안 이루어진 집합론의 기초론에 대한 철저한 연구로 인하여, 오늘날에는 ‘정의 가능 결정성 원리’에 대한 압도적인 양의 증거가 존재한다 […]. 이 증거는 한편으로는 이 원리에 기초한 폴란드 공간의 ‘정의 가능’ 집합 이론의 구조적 일관성에서 유래하며, 다른 한편으로는 이 이론과 ‘큰 기수’ 이론 사이의 깊은 관계로부터 유래한다 […]. 앞으로 우리는 ‘정의 가능 결정성 원리’를 필요한 대로 자유로이 사용할 것이다. Following extensive studies in the foundations of set theory in the last 25 years, there is now overwhelming evidence of the validity of the "Principle of Definable Determinacy" […]. This evidence comes on the one hand from the structural coherence of the theory of “definable” sets in Polish spaces developed on the basis of this principle and on the other hand on the deep connections of this theory with that of the so-called “large cardinals” in set theory […]. We will be freely using various instances of “Definable Determinacy” as needed in the sequel.	”
	— [3]:205–206, §26.B

“	결정성 가설에 대한 직접적 직관을 갖는다고는 아무도 주장하지 않는다—이러한 가설들을 그럴듯하다고 선호하는 이들은 이 가설이 함의하는 결과들로부터 이 가설을 옹호한다. […] 이러한 결과들의 풍요로움과 내부 조화 말고도, 이론의 두 측면을 특히 언급할 수 있다. 첫째, 결정성을 사용하는 증명들은 자연스럽다 […]. [결정성을 사용하여 얻는] 새 결과들은 이미 알려진 명제들의 자연스러운 일반화이며, 그 증명들은 고전적 묘사 집합론을 새롭게 이해할 수 있게 한다. (반면, 구성 가능성 공리를 가정한 증명들의 경우는 그렇지 않다 […]). 둘째, 결정성과 큰 기수 가설들 사이에는 놀라운 관계들이 존재하며, 이는 결정성과 큰 기수 둘 다에 신빙성을 부여한다. […] 오늘날에는 오직 몇몇 집합론자들만이 ${\displaystyle \operatorname {Det} (L(\mathbb {R} ))}$를 매우 신빙성이 있다고 여기며, 아직 아무도 이를 확실히 믿을 수 있다고 여기지 않는다 […]. No one claims direct intuitions of this type either for or against determinacy hypothesis—those who have come to favor these hypotheses as plausible, argue from their consequences […]. In addition to the richness and internal harmony of these consequences, two aspects of the theory [..] deserve explicit mention. One is the naturalness of the proofs from determinacy […]. [T]he new results appear to be natural generalizations of known results and their proofs shed new light on classical descriptive set theory. (This is not the case with the proofs from ${\displaystyle V=L}$ […]). The second point is the surprising connection between determinacy and large cardinal hypotheses […] which lends credence to both. […] At the present state of knowledge only few set theorists accept ${\displaystyle \operatorname {Det} (L(\mathbb {R} ))}$ as highly plausible and no one is quite ready to believe it beyond a reasonable doubt […]	”
	— [17]:472, §8I

${\displaystyle L(\mathbb {R} )}$에 제한한 결정 공리에 대하여, 결정 공리를 고안한 얀 미치엘스키는 훗날 다음과 같이 적었다.

“	선택 공리를 사용하여, 결정 공리가 거짓임을 쉽게 증명할 수 있다. 그러나 공리 ${\displaystyle \operatorname {AD} ^{L(\mathbb {R} )}}$는 […] 여러 흥미로운 결과들을 함의한다. ${\displaystyle \operatorname {AD} ^{L(\mathbb {R} )}}$를 가정할 경우, 모임 ${\displaystyle L(\mathbb {R} )}$는 폴란드 공간 위에서의 해석학의 자연스러운 무대가 된다. […] 또한, 사영 집합의 이론은 매우 정칙적인 형태를 취하게 된다. […]. 따라서 공리 ${\displaystyle \operatorname {AD} ^{L(\mathbb {R} )}}$를 수용하는 것이 합리적이다. It is easy to prove using the Axiom of Choice that ${\displaystyle \operatorname {AD} }$ is false. But the Axiom ${\displaystyle \operatorname {AD} ^{L(\mathbb {R} )}}$ […] has many interesting consequences. Assuming ${\displaystyle \operatorname {AD} ^{L(\mathbb {R} )}}$ the class ${\displaystyle L(\mathbb {R} )}$ becomes the natural universe of sets for mathematical analysis in Polish spaces. […] Also the theory of projective sets gets a very regular form […]. Therefore it is rational to accept the axiom ${\displaystyle \operatorname {AD} ^{L(\mathbb {R} )}}$.	”
	— [18]:210

결정 공리와 선택 공리 사이의 모순에 대하여 대니얼 몰딘(영어: R. Daniel Mauldin)은 다음과 같이 적었다.

“	왜 선택 공리를 버리고 대신 결정 공리를 사용하지 않는가 — 이 경우 구의 역설적 분해와 같은 인위적인 현상이 사라지고, 여러 ‘긍정적’ 결과를 얻을 수 있는데도 말인가? 그 이유는 이러한 결과들(과 [결정] 공리)를 적절한 모임[…](예를 들어, 사영 집합들의 모임)에 제한하는 것이 더 자연스럽다고 느껴지기 때문이다. 이 경우, (선택 공리를 비롯한) 모든 집합들의 모임에 대한 기초적 직관을 위배하지 않고, 기본적 이론의 유일성을 위배하지 않아도 된다. Why don’t we abandon the axiom of choice and accept in its place the axiom of determinacy, in spite of the fact that this removes such artificial phenomena as paradoxical decompositions of the sphere and yields so many “positive” consequences? The answer is that it seems more natural to restrict those consequences (and the axiom) to a suitable class […], e.g., the class of projective sets, without violating our basic intuitions about the class of all sets (of which the axiom of choice is a part) and without wrecking the unicity of our fundamental theory.	”
	— [9]:118, Problem 43

• Koellner, Peter (2013년 5월 22일). “Large cardinals and determinacy”. 《Stanford Encyclopedia of Philosophy》 (영어). 스탠퍼드 대학교. 
• “Axiom of determinacy”. 《nLab》 (영어). 
• Bryant, Ross (2001년 12월). 《Borel determinacy and its metamathematics》 (PDF) (영어). 석사 학위 논문 (지도 교수 Steve Jackson). University of North Texas. 
• Stanton, Samantha (2010). 《The axiom of determinacy》 (영어). 석사 학위 논문 (지도 교수 Andrew Lewis). Virginia Commonwealth University. 
• Gowers, Timothy (2013년 8월 23일). “Determinacy of Borel games I”. 《Gowers’s Weblog》 (영어). 
• Gowers, Timothy (2013년 8월 31일). “Determinacy of Borel games II”. 《Gowers’s Weblog》 (영어). 
• Gowers, Timothy (2013년 9월 5일). “Determinacy of Borel games III”. 《Gowers’s Weblog》 (영어). 
• Gowers, Timothy (2013년 9월 10일). “Determinacy of Borel games IV”. 《Gowers’s Weblog》 (영어). 
• Gowers, Timothy (2013년 9월 16일). “Determinacy of Borel games V”. 《Gowers’s Weblog》 (영어). 
• “Counterintuitive consequences of the axiom of determinacy” (영어). Math Overflow.