“ No one will drive us from the paradise which Cantor created for us. “ — David Hilbert (1926)
선택 공리((the) Axiom of Choice, AC)는 임의의 집합족의 각 집합에서 원소를 하나씩 선택하여 모아 만든 새로운 집합을 구성할 수 있음을 주장하는 공리이다. 수학의 전 분야, 특히 집합론과 해석학에서 그 형식화에 많은 도움을 주는 공리이다. 임의의 집합의 기수의 존재성[1], 임의의 벡터공간의 기저의 존재성[2] 등 여러 분야에서 쓰이는 개념을 잘 정의할 수 있게 해준다. 물론 이보다 약한 가산 선택 공리나 의존 선택 공리와 같은 것만을 이용하여 증명할 수 있는 것들도 일부 있지만, AC가 꼭 필요한 명제들도 있기에 집합론과 해석학에서는 보통 선택 공리를 인정하는 편이다.Cantor의 천국에 들어가지 못하는 직관주의자가 아닌 이상...
직관
큰 상자 안에 작은 상자가 여러 개 있고, 그 각각의 작은 상자에 동전이 한 개 이상씩 들어 있는 상황을 생각해 보자. 각각의 상자에서 동전을 하나씩 골라 주머니 안에 넣을 수 있을까?
... 당연하다. 그냥 뽑으면 되지 않는가! 뭐라고 설명해야 할지는 모르겠지만, 뽑아보면 안다. 하지만, 이것은 작은 상자가 유한할 때에만 적용될 수 있는 논리이다. 만약 그 작은 상자가 무한 개(?) 있다면, 우리는 그 동전들을 골라 주머니에 넣을 수 있는가? (사실 현실의 상황으로 생각하는 것은 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]이다.
- 선택함수(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]이다.
선택 공리의 직관적/반직관적인 결과
“ No one will drive us from the paradise which Cantor created for us. “ — [3].
선택 공리와 동치인 유명한 명제들
누가 뭐래도, 제일 중요한 것은 Zorn's Lemma와 정렬 정리이다. 이와 함께, 다음과 같은 동치인 명제들이 알려져 있다.
- 집합론
- 정렬 원리: 모든 집합은 정렬될(well-ordered) 수 있다.
- 타르스키의 선택 정리: 임의의 무한집합 [math]\displaystyle{ A }[/math]에 대해서, [math]\displaystyle{ A }[/math]와 [math]\displaystyle{ A\times A }[/math] 사이에 전단사 함수가 존재한다. 즉 둘은 대등(equipotent)하고, 둘의 기수(cardinality)는 같다. 이 명제는 AC와 동치이므로, 다음 명제와도 동치이다: [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]이다.
- 모든 전사 함수는 우역원을 가진다.
- 순서론
- 초른의 보조정리: Every non-empty partially ordered set in which every chain (i.e. totally ordered subset) has an upper bound contains at least one maximal element.
- 하우스도르프 극대 원리: In any partially ordered set, every totally ordered subset is contained in a maximal totally ordered subset. The restricted principle "Every partially ordered set has a maximal totally ordered subset" is also equivalent to AC over ZF.
- 투키-타이히뮐러 보조정리(Tukey-Teichmüller lemma, 또는 Tukey's lemma): Every non-empty collection of finite character has a maximal element with respect to inclusion.
- 반사슬 원리 모든 poset(반순서집합)은 극대 반사슬을 갖는다.
- 대수학
- 모든 벡터공간은 기저를 갖는다. (초른의 보조정리의 직접적인 응용)
Every unital ring other than the trivial ring contains a maximal ideal. For every non-empty set S there is a binary operation defined on S that gives it a group structure.[16] (A cancellative binary operation is enough, see group structure and the axiom of choice.) Functional analysis The closed unit ball of the dual of a normed vector space over the reals has an extreme point. Point-set topology Tychonoff's theorem: Every product of compact topological spaces is compact. In the product topology, the closure of a product of subsets is equal to the product of the closures. Mathematical logic If S is a set of sentences of first-order logic and B is a consistent subset of S, then B is included in a set that is maximal among consistent subsets of S. The special case where S is the set of all first-order sentences in a given signature is weaker, equivalent to the Boolean prime ideal theorem; see the section "Weaker forms" below. Graph theory Every connected graph has a spanning tree.[17]
선택 공리를 함의하는 명제들
열린 문제들
ZF와의 독립성
- ↑ 선택 공리와 동치
- ↑ 선택 공리와의 함의 관계가 일반적으로 밝혀지지 않았다. 하단 참조.
- ↑ Schechter, Eric (1997). 《Handbook of analysis and its foundations》. Academic Press, 145쪽. doi 10.1016/B978-0-12-622760-4.50033-9doi 10.1016/B978-0-12-622760-4.50033-9