선택 공리

“	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)라고 한다:

• [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, 145쪽. 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{ \{F_i\}_{i\in I} }[/math]이 존재하여 [math]\displaystyle{ \forall i \in I \; F_i \subseteq A_i }[/math]

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

“	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):
  • 반사슬 원리: 모든 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가 논리적으로 독립임을 알 수 있다.