선택 공리

“	The Axiom of Choice is necessary to select a set from an infinite number of socks, but not an infinite number of shoes.	“
— Bertrand Russell

“	The axiom gets its name not because mathematicians prefer it to other axioms.	“
— A. K. Dewdney

선택 공리((the) Axiom of Choice, AC)는 임의의 집합족의 각 집합에서 원소를 하나씩 선택하여 모아 만든 새로운 집합을 구성할 수 있음을 주장하는 공리이다. 수학의 전 분야, 특히 집합론과 해석학에서 그 형식화에 많은 도움을 주는 공리이다. 임의의 집합의 기수의 존재성, 임의의 벡터공간의 기저의 존재성 등 여러 분야에서 쓰이는 개념을 잘 정의할 수 있게 해준다. 물론 이보다 약한 가산 선택 공리나 의존 선택 공리와 같은 것만을 이용하여 증명할 수 있는 것들도 일부 있지만, AC가 꼭 필요한 명제들도 있기에 집합론과 해석학에서는 보통 선택 공리를 인정하는 편이다. 하지만 이를 가정하는 데에 조심스러운 수학자가 많다.

직관

큰 상자 안에 작은 상자가 여러 개 있고, 그 각각의 작은 상자에 동전이 한 개 이상씩 들어 있는 상황을 생각해 보자. 각각의 상자에서 동전을 하나씩 골라 주머니 안에 넣을 수 있을까?

... 당연하다. 그냥 뽑으면 되지 않는가! 뭐라고 설명해야 할지는 모르겠지만, 뽑아보면 안다. 하지만, 이것은 작은 상자가 유한할 때에만 적용될 수 있는 논리이다. 만약 그 작은 상자가 무한 개(?) 있다면, 우리는 그 동전들을 골라 주머니에 넣을 수 있는가? (사실 현실의 상황으로 생각하는 것은 nonsense이다. 상자가 무한 개 있을 리가 없다!)

진술

다음 동치인 명제 중 하나를 선택 공리(AC 또는 AoC)라고 한다:

• [math]\displaystyle{ \mathcal A }[/math]를 mutually disjoint한 공이 아닌 집합들의 족이라 하자. 그렇다면 [math]\displaystyle{ \mathcal A }[/math]의 각각의 집합으로부터 하나의 원소-씩으로 구성된 집합이 존재한다.
• [math]\displaystyle{ \mathcal A = \{A_i\}_{i\in I} }[/math]를 index를 가진 집합족이라 하자. [math]\displaystyle{ I\ne \emptyset }[/math]이면, [math]\displaystyle{ \prod_{i \in I} A_i \ne \emptyset }[/math]이다.
• [math]\displaystyle{ \mathcal A = \{A_i\}_{i\in I} }[/math]를 index를 가진 집합족이라 하자. [math]\displaystyle{ I\ne \emptyset }[/math]이면, 어떤 집합 [math]\displaystyle{ C }[/math]가 존재하여 [math]\displaystyle{ \forall i \in I [C \cap A_i \text{ is a singleton}] }[/math]이다. 이때 [math]\displaystyle{ C }[/math]를 선택자(selector)라고 하기도 한다.
• 선택함수(choice function)가 존재한다. 더욱 명시적으로, 주어진 집합 [math]\displaystyle{ A }[/math]에 대하여, 함수 [math]\displaystyle{ F:\mathcal P(A) \to A }[/math]가 존재하여 [math]\displaystyle{ \forall X \subseteq A[X\ne \emptyset \Rightarrow F(X) \in X] }[/math]이다.
• 선택함수가 존재한다. 임의의 집합족 [math]\displaystyle{ \mathcal A }[/math]에 대하여, [math]\displaystyle{ \emptyset \notin \mathcal A\implies \exists f\colon \mathcal A\rightarrow \bigcup \mathcal A\left[\forall X\in \mathcal A\,(f(X)\in X)\right] }[/math]이다.

선택 공리의 변형

AC로 올라 갈수록 강한 명제이다.

이 목록은 Herrlich, Horst (2006). 《Axiom of Choice》. Lecture Notes in Mathematics (영어) 1876. Springer. ISBN 3-540-30989-6 에 실려 있다.

• CC = AC_ω: 가산 선택 공리(Axiom of Countable Choice). 가산 개의 집합의 족에 대한 선택함수가 존재한다.
• AC(fin): 유한집합들의 임의 족에 대한 선택함수가 존재한다.
• AC(n): 원소 [math]\displaystyle{ n }[/math] 개인 집합들의 임의 족에 대한 선택함수가 존재한다.
• AMC: 다중 선택 공리(Axiom of Multiple Choice). 각 집합에서 한 개만 뽑는 거라면 몰라도, 유한 개 정도는 뽑을 수 있다. [math]\displaystyle{ \{A_i\}_{i\in I} }[/math]가 집합족일 때, 유한집합들의 족 [math]\displaystyle{ \{\mathcal F_i\}_{i\in I} }[/math]이 존재하여 [math]\displaystyle{ \forall i \in I \; \mathcal F_i \subseteq A_i }[/math]
• KW: 킨나-바그너 선택 원리(Kinna–Wagner Selection Principle). [math]\displaystyle{ \{X_i\}_{i\in I} }[/math]가 원소를 적어도 두 개 이상 포함한 집합들의 족일 때 집합족 [math]\displaystyle{ \{Y_i\}_{i\in I} }[/math]가 있어 [math]\displaystyle{ Y_i }[/math]는 [math]\displaystyle{ X_i }[/math]의 진부분집합이다.
• CC(R): 실수들로 이뤄진 가산집합들의 족에 대한 선택공리
• CC(Z): [math]\displaystyle{ (X_n, \le_n)_{n\lt \omega} }[/math]가 정수 집합 [math]\displaystyle{ \mathbb Z }[/math]과 순서동형인 순서집합들의 족일 때 그 곱 [math]\displaystyle{ \prod_n X_n }[/math]은 nonempty하다.
• CC(fin): 유한집합들의 가산 족에 대한 선택함수가 존재한다.
• CC(n): 원소 n개인 집합들의 가산 족에 대한 선택함수가 존재한다.
• CMC: 다중 가산 선택 공리(Axiom of Countable Multiple Choice). [math]\displaystyle{ \{A_n\}_{n\lt \omega} }[/math]가 가산 집합족일 때, 유한집합들의 족 [math]\displaystyle{ \{\mathcal F_n\}_{n\lt \omega} }[/math]가 있어 [math]\displaystyle{ \mathcal F_n\subseteq A_n }[/math] for all [math]\displaystyle{ n\lt \omega }[/math]이다.
• DC: 의존 선택 공리(Axiom of Dependent Choice). X가 집합이고 [math]\displaystyle{ \mathcal R }[/math]이 X 위의 관계이며 [math]\displaystyle{ \forall x\exists y (x \mathcal R y) }[/math]이면 [math]\displaystyle{ x_n \mathcal R x_{n+1} }[/math]인 X 위의 수열 [math]\displaystyle{ (x_n)_{n\lt \omega} }[/math]가 존재한다. 대충 말하면, 위로 막혀 있지 않은 집합에서는 증가하는 수열을 고를 수 있다는 것이다.
• PCC: 부분 가산 선택 공리(Axiom of Partial Countable Choice). CC와 동치인 공리로, [math]\displaystyle{ (X_n)_{n\lt \omega} }[/math]가 공집합이 아닌 집합들의 족일 때 무한집합 [math]\displaystyle{ M\subseteq\omega }[/math]가 있어 [math]\displaystyle{ \prod_{m \in M}X_m \ne \emptyset }[/math]이다. (CC와 동치이다.)
• Fin: 임의의 무한집합은 데데킨트 무한이다.
• Fin(R): 실수 집합의 임의의 무한 부분집합은 데데킨트 무한이다.
• Fin(lin): 임의의 무한 선형 순서 집합(linearly ordered set)은 데데킨트 무한이다.
• PIT: 불 소 아이디얼 정리(Boolean prime ideal theorem). 불 대수에 대한 강한 소 아이디얼 정리이다. 불 대수 [math]\displaystyle{ B }[/math]와 그 아이디얼 [math]\displaystyle{ \mathfrak i }[/math], [math]\displaystyle{ B }[/math]의 필터 [math]\displaystyle{ \mathcal F }[/math]에 대하여 [math]\displaystyle{ \mathfrak i }[/math]와 [math]\displaystyle{ \mathcal F }[/math]가 서로 소라고 하자. 그렇다면 [math]\displaystyle{ \mathfrak i \subseteq \mathfrak p }[/math]이고 [math]\displaystyle{ \mathcal F }[/math]와 서로 소인 [math]\displaystyle{ B }[/math]의 소 아이디얼 [math]\displaystyle{ \mathfrak p }[/math]가 존재한다.
• UFT: 초필터 정리(Ultrafilter theorem). 임의의 무한집합 위의 임의의 필터는 초필터로 확장될 수 있다. PIT와 동치이다.
• UFT(N): 자연수 집합 위의 임의의 필터는 초필터로 확장될 수 있다.
• WUF: 약한 초필터 원리(Weak ultrafilter principle). 임의의 무한집합은 free ultrafilter를 갖는다.
• WUF(N): 자연수 집합은 free ultrafilter를 갖는다.
• WUF(?): free ultrafilter를 갖는 집합이 존재한다.
• OP: 순서 원리(Ordering principle). 임의의 집합은 전순서 관계를 가질 수 있다.
• OEP: 순서 확장 원리(Ordering extension principle). 임의의 반순서 관계는 선형 순서 관계로 확장될 수 있다.
• AH(α): Aleph Hypothesis. [math]\displaystyle{ \aleph_{\alpha + 1 } = 2^{\aleph_\alpha} }[/math]. α = 0일 때 연속체 가설(CH)이고, for every ordinal [math]\displaystyle{ \alpha }[/math]일 때 일반화된 연속체 가설(GCH)이다.
• CUT: 가산 합집합 정리(Countable Union Theorem). 가산-이하(at most countable)의 집합을 가산-이하 개 합해도 가산-이하인 집합이다.

선택 공리의 직관적/반직관적인 결과

“	The Axiom of Choice is obviously true; the Well Ordering principle is obviously false; and who can tell about Zorn’s lemma?	“
— Jerry Lloyd Bona.

선택 공리와 동치인 유명한 명제들

누가 뭐래도, 제일 중요한 것은 Zorn's Lemma와 정렬 원리이다. 이와 함께, 다음과 같은 동치인 명제들이 알려져 있다.

이하, ZF를 가정한다.

• 집합론
  • 정렬 원리: 모든 집합은 정렬될(well-ordered) 수 있다.
  • 타르스키의 선택 정리: 임의의 무한집합 [math]\displaystyle{ A }[/math]에 대해서, [math]\displaystyle{ A }[/math]와 [math]\displaystyle{ A\times A }[/math] 사이에 전단사 함수가 존재한다. 즉 둘은 대등(equipotent)하고, 둘의 기수(cardinality)는 같다. 따라서 다음 명제와 AC가 동치이다: finite [math]\displaystyle{ \lambda \lt \kappa := |A| }[/math]에 대하여, [math]\displaystyle{ |A| = \kappa = \kappa^\lambda = |A|^\lambda }[/math]이다.
  • 기수의 삼분성질: 기수 사이의 순서 관계는 linear ordering이다. 즉, 임의의 두 집합 [math]\displaystyle{ A }[/math]와 [math]\displaystyle{ B }[/math]가 있으면, [math]\displaystyle{ |A| \lt |B| }[/math], [math]\displaystyle{ |A| = |B| }[/math], [math]\displaystyle{ |A| \gt |B| }[/math] 중 하나이다.
  • 쾨니그 정리: 작은 것들의 합은 큰 것들의 곱보다 작다. 즉, [math]\displaystyle{ \kappa_i \lt \lambda_i }[/math]이면 [math]\displaystyle{ \sum_i \kappa_i \lt \prod_i \lambda_i }[/math]이다.
  • 모든 전사 함수는 우역원을 가진다.
• 순서론
  • 초른의 보조정리: 모든 사슬(전순서인 부분집합)이 상한을 가지는 poset(반순서집합)은 극대원을 갖는다.
  • 하우스도르프 극대 원리: 모든 poset에 대하여, 극대의 전순서 부분집합이 존재하여 모든 전순서 부분집합이 극대 전순서 부분집합에 포함된다. 극대 전순서 부분집합의 존재성만을 진술한 것은 ZF 위에서 AC와 동치이다.
  • 투키-타이히뮐러 보조정리(Tukey-Teichmüller lemma, 또는 Tukey's lemma): 임의의 유한 특성을 갖는 집합족은 [math]\displaystyle{ \subseteq }[/math]-극대 원소를 갖는다. 여기서 집합족 [math]\displaystyle{ \mathscr F }[/math]가 유한 특성을 갖는다는 것은, [math]\displaystyle{ A \in \mathscr F \Longleftrightarrow }[/math]모든 [math]\displaystyle{ A }[/math]의 유한집합이 [math]\displaystyle{ \in \mathscr F }[/math]임을 말한다.
  • 반사슬 원리: 모든 poset은 극대 반사슬을 갖는다.
• 대수학
  • 모든 벡터공간은 기저를 갖는다. (초른의 보조정리의 직접적인 응용)
  • 모든 nontrivial r[math]\displaystyle{ i }[/math]ng은 극대 이데알을 가진다.
  • 공이 아닌 집합 [math]\displaystyle{ S }[/math]에 대하여 [math]\displaystyle{ S }[/math]를 군이 되게 하는 이항연산이 존재한다.
• 함수해석
  • 티호노프 정리

ZF와의 독립성

쿠르트 괴델은 ZF가 일관적(consistent)임을 가정하고, AC의 부정이 ZF의 정리가 아님을 ZFC를 만족하는 내부 모형을 구성함으로써 보여 결과적으로 ZFC가 일관적임을 보였다. 또 폴 코언은 강제법을 이용하여 ZF¬C인 모형을 구성하고, 즉 ZF의 일관성을 가정할 때 ZF¬C가 일관적임을 보였다. 이 두 결과로부터 우리는 ZF와 AC가 논리적으로 독립임을 알 수 있다.