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

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

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

 

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

 

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

 

집합 $A$를 생각하자.

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

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

1) $S\subseteq S^{\prime }$

2) $\mathrm{\forall }s\in S,s^{\prime }\in S^{\prime }\setminus S,s{R}_{S^{\prime }}{s}^{\prime }$

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

그러면 $\le$가 $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)⪇(M^{+},R_{M^{+}})$이 되어 $(M,R_M)$이 $W$의 극대원소임에 모순이다.

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

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

$◼$

 

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

 

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

 

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

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

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

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

$◼$