집합론, 그 스물한 번째 이야기 | 모든 정렬집합은 유일한 서수와 Order Isomorphic하다

이번 글에서는 모든 정렬집합은 그와 Order Isomorphic한 서수가 존재하며, 그러한 서수는 유일하다는 사실에 대해 서술하려 한다. 이 정리는 결국 선택공리가 추가된 ZF 공리계 하에서 모든 집합 $X$는 전단사함수 $f:X\rightarrow\alpha$가 존재하는 서수 $\alpha$가 항상 존재한다는 따름정리를 이끌어낸다. 이를 통해 이 다음 글에 서술될 기수에 대한 이야기를 할 수 있게 되며 우리는 그를 이용하여 전단사함수의 존재성을 직접적으로 증명하지 않고도 두 집합의 크기가 같음을 이야기할 수 있게 된다. 또한, 집합의 크기를 비교하는 것 또한 가능하게 된다. 이 모든 것이 겨우 10개의 공리로부터 유도된다는 것이 정말 놀랍지 않은가? 잡설은 이쯤 하고 이제 이 글의 주제로 다시 돌아가도록 하겠다. 일단, 이 정리를 증명하기 위해서는 몇 개의 Lemma가 필요하다. 따라서 그 Lemma들을 먼저 소개하도록 하겠다.

 

Lemma 1. Order Isomorphic한 두 서수는 같다.

 

두 서수 $\alpha$와 $\beta$가 Order Isomorphic하다고 하자.

이제 귀류법을 통한 증명을 위해 $\alpha\neq\beta$를 가정하자.

그러면 서로 다른 두 서수는 항상 비교 가능하므로 $\alpha\subseteq\beta$ 또는 $\beta\subseteq\alpha$이며, 둘 모두 서수이므로 $\alpha$가 $\beta$의 Initial Segment이거나 $\beta$가 $\alpha$의 Initial Segment이다.

하지만, 모든 정렬집합은 자기자신의 Initial Segment와의 Order Isomorphism이 존재하지 않으므로 이는 $\alpha$와 $\beta$가 Order Isomorphic하다는 것에 모순이다.

따라서 두 서수 $\alpha$와 $\beta$는 같다.

$\blacksquare$

 

Lemma 2. 서수만을 원소로 가지는 추이적 집합은 서수이다.

 

모든 서수의 모임인 $\text{Ord}$가 정렬성을 만족하므로, 서수만을 원소로 가지는 모든 집합은 정렬집합이다. 따라서 서수만을 원소로 가지는 추이적 집합은 정렬집합이면서 동시에 추이적 집합이므로 서수이다.

$\blacksquare$

 

Lemma 3. 어떤 정렬집합의 모든 Initial Segment가 Order Isomorphic한 서수를 가지면 그 정렬집합과 Order Isomorphic한 서수가 존재한다.

 

$(W,\leq)$가 정렬집합이고 $W$의 모든 Initial Segment가 Order Isomorphic한 서수를 가진다고 가정하자.

$W$의 $a$에 의한 Initial Segment를 $W[a]$라고 하자.

그리고 함수 $f:W\to\text{Ord}$를 $f(a)$와 $W[a]$가 동형이 되도록 정의하자.

그러면 $f$는 Lemma 1에 의해 잘 정의되며, 동시에 단사함수가 된다.

이때, $a,b\in W$에 대해 $a\leq b$이면 $W[a]\subseteq W[b]$이므로 $f(a)\leq f(b)$가 된다. 또한 그 역도 성립한다.

따라서 함수 $f$는 $W$와 $\text{im}f$의 Order Isomorphism임을 즉시 알 수 있다.

이떄, Lemma 2에 의해 $\text{im}f$는 서수이므로 $W$와 Order Isomorphic한 서수가 존재한다.

$\blacksquare$

 

Theorem. 모든 정렬집합은 유일한 서수와 Order Isomorphic하다.

 

$(S,\leq)$를 정렬집합이라고 하자. 그리고 $S$의 $a$에 의한 Initial Segment를 $S[a]$로 표현하자.

그리고 집합 $E$를 다음과 같이 정의하자.

$E:=\{a\in S\;|\;\nexists\;\alpha\in\text{Ord}\;s.t.\;S[a]\text{ is Order Isomorphic to }\alpha\}$

만약 $E=\emptyset$이라면, Lemma 3에 의해 $S$와 Order Isomorphic한 서수가 존재한다.

따라서 귀류법을 이용한 증명을 위해 $E\neq\emptyset$이라고 가정하자.

그러면 $E$가 $S$의 공집합이 아닌 부분집합이므로 $E$의 최소원소 $m$이 존재한다.

그러면 $n\leq m$인 $n\in S$에 대해 언제나 $S[n]$과 Order Isomorphic한 서수가 존재한다.

따라서 $S[m]$의 모든 Initial Segment는 Order Isomorphic한 서수를 가지며, Lemma 3에 의해 $S[m]$과 Order Isomorphic한 서수가 존재한다.

이는 $m$이 $E$의 최소원소임에 모순된다. 따라서 귀류법에 의해 $E=\emptyset$이다.

따라서 $S$와 Order Isomorphic한 서수가 존재하며, Lemma 1에 의해 그러한 서수는 유일하다.

$\blacksquare$