선택 공리((the) Axiom of Choice, AC)는 임의의 집합족의 각 집합에서 원소를 하나씩 선택하여 모아 만든 새로운 집합을 구성할 수 있음을 주장하는 공리이다. 수학의 전 분야, 특히 집합론과 해석학에서 그 형식화에 많은 도움을 주는 공리이다. 임의의 집합의 기수의 존재성[1], 임의의 벡터공간의 기저의 존재성[2] 등 여러 분야에서 쓰이는 개념을 잘 정의할 수 있게 해준다. 물론 이보다 약한 가산 선택 공리나 의존 선택 공리와 같은 것만을 이용하여 증명할 수 있는 것들도 일부 있지만, 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]이다.
- 선택함수(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]이다.