선택공리(Axiom of Choice)

선택공리는 다음과 같다.

집합 $A$에 대하여 다음을 만족하는 함수 $f: \mathcal{P}(A)-\{\emptyset\} \to A$가 존재한다.

$$\forall X f(X)\in X$$

또는 다음과 같이 말해도 된다.

공집합이 아닌 집합들의 집합족 $\{A_i\}_{i\in I}$에 대하여, 함수 $f: \{A_i\} \to \bigcup _{i \in I} A_i$가 존재하여 다음을 만족한다.

$$ \forall i \in I \quad f(A_i) \in A_i $$

둘은 서로 동치이다. 그리고 이때의 함수 $f$를 선택함수(choice function)이라 한다. 지금부터 선택공리에 말하고 싶은 것은 선택공리의 아이러니한 파생 정리가 아니고, 선택공리에 대해서 오해하는 것들이다.

가장 큰 오해는 "공집합이 아닌 집합 $A$에서 원소 하나를 뽑아 $a$라 하자" 라는 문장을 사용할 때 선택공리가 필요하냐는 것이다. 이것은 물론 선택공리를 필요로 하지 않는다. 1차 논리를 배웠다면 알겠지만 이것은 증명 과정에서 사용할 수 있는 문장이다.(existence elimination) 마찬가지로, 유한한 집합족 $A_1, A_2, \cdots, A_n$에 대하여(각각의 집합은 무한해도 상관없다) 원소를 뽑아 $a_1, \cdots a_n$이라 두는 것은 선택공리를 요구하지 않는다. (그냥 기계적으로 각 원소가 존재한다고 증명에 서술하면 된다)

선택공리가 필요한 상황은 집합족이 무한할 때이다. 무한한 집합족에 대해서는 각 원소를 뽑는 과정을 유한하게 서술할 수가 없다. 그래서 증명의 요건인 '유한한 명제들의 모임'을 만족하지 못한다. 따라서 무한한 집합족에 대해서도 선택함수가 존재한다는 것은 공리가 필요한 것이다. 물론 이게 선택공리와 ZF 공리계의 독립성의 증명은 아니고, 정황상 선택공리의 도입이 필요하다는 것이다.

한편 위 논의에서 집합족이 가산이라도 공리가 필요하다는 것을 알 수 있다. 이를 Axiom of Countable Choice 또는 가산선택공리라 한다. 가산선택공리는 당연히 선택공리의 약한 버전이지만 그래도 많은 것들을 유도할 수 있다.

그 외에 전역선택공리(axiom of global choice)는 임의의 집합 $A$에 대하여 함수 $\tau$가 존재하여 $\tau(A)\in A$를 만족한다는 공리이다. 보다시피 이 공리는 ZFC에서는 논의할 수가 없고($\tau$의 정의역이 모든 집합의 모임(class)이므로) NBG에서는 논의할 수 있다. 이 함수의 존재성은 굉장히 강력해서 모든 집합의 모임을 정렬가능하게 할 수 있다는 명제를 유도할 수 있다.