집합론, 그 열아홉 번째 이야기 | 정렬 정리 ( Well-Ordering Theorem )

정렬 정리는 이 글에서 소개한 선택공리와 동치인 명제 중 하나이다. 이 글에서는 정렬 정리를 소개하고, 초른 보조정리가 정렬 정리를 함의하는 것을 증명하는 과정을 서술할 것이며, 정렬 정리가 선택공리를 함의하는 것을 증명하는 과정 또한 서술할 것이다.

정렬 정리(Well-Ordering Theorem) 공집합이 아닌 집합은 항상 정렬순서를 갖는다.

 

다음은 정렬 정리의 증명과정이다.

 

정렬 정리(Well-Ordering Theorem)의 증명

 

집합 $A$를 생각하자.

그리고 $W$를 $S\subseteq A$이고 동시에 $R_S$가 $S$의 정렬순서가 되는 모든 순서쌍 $(S,R_S)$의 집합이라고 하자.

그 후 $W$ 위의 순서관계 $\leq$를 $(S,R_S)\leq(S',R_{S'})$와 다음 세 조건을 만족하는 것이 동치가 되도록 정의하자.

1) $S\subseteq S'$

2) $\forall s\in S,\;s'\in S'\setminus S,\;s R_{S'} s'$

3) $R_S = S^2 \cap R_{S'}$

그러면 $\leq$가 $W$ 위의 부분순서관계이며 $W$의 모든 사슬은 상계를 가진다는 사실을 즉시 알 수 있다.

그러면 우리는 초른 보조정리에 의해 $W$의 극대원소 $(M,R_M)$을 잡을 수 있다.

만약 $a\notin M$을 만족하는 $a\in A$가 존재한다면, 우리는 집합 $M^+=M\cup\{a\}$를 잡을 수 있으며 동시에 $M^+$ 위에서의 순서관계 $R_{M^+} = R_M \cup \{(m,a)\;|\;m\in M^+\}$를 정의할 수 있다.

그러면 $R_M$이 집합 $M$ 위의 정렬순서라는 사실로부터 $R_{M^+}$는 집합 $M^+$ 위의 정렬순서가 된다는 것을 알 수 있다.

하지만, $M$이 $M^+$의 부분이 되므로 $(M,R_M)\lneq(M^+,R_{M^+})$이 되어 $(M,R_M)$이 $W$의 극대원소임에 모순이다.

귀류법에 의해 $a\notin M$인 $a\in A$는 존재할 수 없으며, $A=M$이 된다.

따라서 $R_M$은 집합 $A$ 위의 정렬순서이다.

$\blacksquare$

 

이제 초른 보조정리가 정렬 정리를 함의한다는 것을 보였으므로 정렬 정리가 선택공리를 함의한다는 것만 보이면 선택공리(Axiom of Choice; AC)와 하우스도르프 극대원리(Hausdorff Maximal Principle; HMP), 초른 보조정리(Zorn's Lemma; ZL), 그리고 정렬 정리(Well-Ordering Theorem)가 ZF 공리계 하에서 동치라는 사실을 얻을 수 있다. 아래는 정렬 정리가 선택공리를 함의한다는 것을 증명하는 과정이다.

 

정렬 정리(Well-Ordering Theorem)가 선택공리(Axiom of Choice; AC)를 함의한다는 것의 증명

 

공집합을 원소로 가지지 않는 임의의 집합족 $\cal{F}$를 생각하자.

집합 $U=\displaystyle\bigcup\cal{F}$를 정의하면 정렬 정리에 의해 $U$ 위의 정렬순서 $\leq$가 존재한다.

이때, 함수 $f:\mathcal{P}(U)\setminus\{\varnothing\}\rightarrow U$를 $f(A)=\text{min}A$로 정의하자.

이러면 함수 $f$가 $\cal{F}$의 선택함수가 됨은 자명하다.

$\blacksquare$