결정 집합

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

## 결정 집합
다음과 같은 데이터가 주어졌다고 하자. * 집합 A * A의 원소의 열들의 집합 X\subseteq A^\omega. 이를 **승패 집합**(勝敗集合, payoff set)이라고 한다. * A에 이산 위상을 부여하고, A^\omega에 곱위상을 부여하였을 때, 공집합이 아닌 닫힌집합 \varnothing\ne[T]\subseteq A^\omega. 이는 마찬가지로 나무 T=\textstyle\bigcup_{n<\omega}\\{t\restriction n\colon t\in T\\}\subseteq A^{<\omega}로 나타낼 수 있다. 나무 T를 **허용된 수의 나무**(許容된 手의 나무, tree of allowed positions)라고 한다. 이제 다음과 같은 2인(人) 게임을 생각하자.언어=en237, §5언어=en137, §20.A # 두 선수 갑(甲)과 을(乙)이 있다. # 갑과 을은 수(手)를 두는 것을 반복하며, 갑이 먼저 수를 둔다. 여기서, 수를 둔다는 것은 a\in A를 고르는 것이다. 수들을 k=(k_0,k_1,k_2,\dots)라고 하자. (즉, 갑은 k_0,k_2,k_4,\dots를 두고, 을은 k_1,k_3,k_5,\dots를 둔다.) 각 선수는 이전에 놓인 모든 수(手)들을 알고 있다. 또한, 각 i<\omega에 대하여 (k_0,k_1,\dots,k_{i-1})\in T이어야만 한다. # 만약 (k)_{i<\omega}\in X라면 갑이 이기며, 아니라면 을이 이긴다. **전략**(戰略, strategy)은 함수 A^{<\omega}\to A이다. 여기서 :A^{<\omega}=\bigsqcup_{n<\omega}A^n 는 A 속의 유한열들의 집합이다. **갑의 필승 전략**(甲의必勝戰略, winning strategy for the first player)은 다음 조건을 만족시키는 전략 \sigma\colon A^{<\omega}\to A이다. :임의의 열 (t_i)_{i\in\mathbb N}\in A^n에 대하여, 다음이 성립한다. ::\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)은 다음 조건을 만족시키는 전략 \sigma\colon A^{<\omega}\to A이다. :임의의 열 (s_i)_{i<\omega}\in A^n에 대하여, 다음이 성립한다. ::\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 X\subseteq A^\omega에 대하여, 만약 위 게임에서 갑과 을 가운데 하나가 필승 전략을 갖는다면, X가 T로 정의되는 게임에 대한 **결정 집합**(決定集合, determined set)이라고 한다.137, §20.A 만약 T가 명시되지 않았다면, T=A^{<\omega}이다.
## 결정 공리
이제, 다음과 같은 명제들을 정의할 수 있다. * **결정 공리**(決定公理, axiom of determinacy) \mathsf{AD}에 따르면, 모든 집합 X\subseteq\mathbb N^\omega은 결정 집합이다. * **실수 정의 가능 결정 공리**(實數定義可能決定公理, axiom of real-definable determinacy) \mathsf{AD}^{L(\mathbb R)}에 따르면, 모든 집합 X\subseteq \mathbb N^\omega\cap L(\mathbb R)은 결정 집합이다. 여기서 L(\mathbb R)은 실수 구성 가능 집합들의 누적 위계이다. * **사영 결정 공리**(射影決定公理, axiom of projective determinacy) \mathsf{PD}에 따르면, 모든 사영 집합 X\subseteq \mathbb N^\omega에 대하여 선수 1이 필승 전략을 갖거나, 아니면 선수 2가 필승 전략을 갖는다.
# 성질

## ZFC로 증명 가능한 성질
ZFC에서는 다음 성질들을 증명할 수 있다. * 모든 보렐 집합은 결정 집합이다.140, Theorem 20.5언어=en * 모든 결정 집합은 ** 보편 가측 집합이며, ** 준열린집합이며, ** 완전 집합 성질을 만족시킨다. 선택 공리에 의하면 르베그 가측 집합이 아닌 집합이 존재하므로, 결정 집합이 아닌 집합이 존재한다.
## 결정 공리
체르멜로-프렝켈 집합론 + 결정 공리는 선택 공리의 부정을 함의하며, 또한 체르멜로-프렝켈 집합론의 일관성을 증명할 수 있다. :\mathsf{ZF}+\mathsf{AD}\vdash\lnot\mathsf{AC} :\mathsf{ZF}+\mathsf{AD}\vdash\operatorname{Con}(\mathsf{ZF}) 체르멜로-프렝켈 집합론 + 결정 공리를 가정하면, ZFC에서 성립하지 않는 다음 명제들이 성립한다. * 실수 집합의 모든 부분 집합은 르베그 가측 집합이다. * 실수 집합의 모든 부분 집합은 준열린집합이다. * 실수 집합의 모든 부분 집합은 완전 집합 성질을 만족시킨다. * 실수 집합의 모든 부분 집합은 가산 집합이거나, 아니면 크기가 실수 집합 전체와 같다. 반면, 결정 공리보다 더 약한 공리 \mathsf{AD}^{L(\mathbb R)}는 선택 공리와 모순되지 않는다고 여겨진다.
## 큰 기수와의 관계
충분히 강한 큰 기수의 존재를 가정하면, \mathsf{AD}^{L(\mathbb R)}를 증명할 수 있다.언어=en언어=en 구체적으로, 결정 공리들의 충분 조건은 다음과 같다. * 가산 무한 개의 우딘 기수가 존재한다면, \mathsf{PD}가 성립한다. * 가산 무한 개의 우딘 기수가 존재하며, 이들보다 더 큰 (하나 이상의) 가측 기수가 존재한다면, \mathsf{AD}^{L(\mathbb R)}가 성립한다. 구체적으로, 다음 두 명제가 서로 동치이다.언어=en1147 * \mathsf{PD} * 임의의 자연수 n에 대하여, (ZFC + n개의 우딘 기수가 존재한다)로부터 유추할 수 있는, 산술의 2차 논리 언어로 나타낼 수 있는 모든 명제가 참이다. 즉, 이에 대하여 존 로버트 스틸(John Robert Steel)은 다음과 같이 적었다. 1147 여기서 도구주의는 어떤 이론을 단순히 어떤 실용적인 목표를 이루기 위한 도구로 여기는 철학이다. 즉, 만약 우딘 기수의 존재를 단순히 산술의 2차 논리 언어에서의 정리들을 증명하기 위한 도구로 생각한다면, 이러한 도구로서 (가산 무한 개의) 우딘 기수들의 존재는 \mathsf{PD}와 동치이다.
# 역사
슈코츠카 책의 현존하는 한 쪽 위와 같은 꼴의 게임은 스타니스와프 울람이 1935년에 도입하였다. 당시 리비우에 살던 수학자들은 슈코츠카 카페(카비아르니아 슈코츠카, 슈코츠카는 슈코치아(스코틀랜드)의 형용사형)에 모여서 수학 문제들을 토론하였으며, 토론에 의하여 얻은 결과들을 "슈코츠카 책"(크시엥가 슈코츠카)이라는 노트에 기록하였다. 여기서 울람은 바나흐-마주르 게임(슈코츠카 책의 43번 문제)을 약간 변형한 다음과 같은 게임을 제시하였다.언어=en116, Problem 43 Dany jest zbiór liczb rzeczywistych 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 E. Dla jakich zbiorów istnieje metoda wygrania dla gracza A (gracza B)? — S. Ulam 결정 공리는 얀 미치엘스키와 후고 스테인하우스가 1962년에 도입하였다.언어=en언어=en언어=en737 ZFC만을 사용한, 실수의 부분 집합의 결정 집합 여부에 대한 정리들의 역사는 다음과 같다. * 1953년에 데이비드 게일(David Gale)과 프랭크 스튜어트(Frank M. Stewart)가 모든 열린집합이 결정 집합임을 증명하였다.언어=en * 1955년에 필립 울프(Philip Wolfe)는 \boldsymbol\Sigma_2^0 집합이 결정 집합임을 증명하였다.언어=en * 1964년에 모턴 데이비스(Morton Davis)는 \boldsymbol\Sigma_3^0 집합이 결정 집합임을 증명하였다.언어=en * 1972년에 제프리 브루스 패리스(Jeffrey Bruce Paris)는 \boldsymbol\Sigma_4^0 집합이 결정 집합임을 증명하였다.언어=en * 1975년에 도널드 앤서니 마틴(Donald Anthony Martin)이 모든 보렐 집합이 결정 집합임을 증명하였다.언어=en
## 실수 정의 가능 결정 공리의 허용
L(\mathbb R)에 제한한 결정 공리의 각종 흥미로운 성질들 및 큰 기수와의 관계가 밝혀지면서, 이후 일부 수학자들은 L(\mathbb R)에 제한한 결정 공리를 자유로이 가정하거나, 심지어 집합론의 공리로 제시하기도 하였다. 예를 들어, 이 내용을 다루는 집합론 교재들은 실수 정의 가능 결정 공리에 대하여 다음과 같이 적는다. 205–206, §26.B 472, §8I L(\mathbb R)에 제한한 결정 공리에 대하여, 결정 공리를 고안한 얀 미치엘스키는 훗날 다음과 같이 적었다. 210 결정 공리와 선택 공리 사이의 모순에 대하여 대니얼 몰딘(R. Daniel Mauldin)은 다음과 같이 적었다. 118, Problem 43