정렬의 삼분성과 서수의 완전성

1. 기본 개념

정의. 다음을 만족하는 $(W, <)$를 정렬 집합(well-ordered set)이라고 한다.

1. $(W, <)$은 전순서이다.
2. $W$의 임의의 부분집합은 최소 원소를 가진다.

정의. $(W, <)$가 정렬 집합일 때, $a \in S$에 대해 $x < a \rightarrow x \in S$인 $W$의 부분집합 $S$를 초기단(initial segment)이라고 한다.

정리. $S$가 정렬 집합 $(W, <)$의 초기단일 때, 어떤 $a \in W$에 대해 다음이 성립한다.

$S = W[a] \coloneqq \{ x \in W : x < a \}$

증명. $a$를 $W \setminus S$의 최솟값으로 잡는다.

2. 정렬의 삼분성

정리.

(1) 정렬 집합은 자신의 초기단과 동형일 수 없다.
(2) 정렬 집합의 자기동형사상은 항등사상이다.
(3) 두 정렬 집합 간 동형사상은 유일하다.

증명.

보조정리.

$f: (W, <) → (W, <)$가 순서 보존이라면 $x \in W$에 대해 $x \leq f(x)$이다.

보조정리의 증명.

귀류법에 따라 $S = \{ x \in W : x > f(x) \}$가 공집합이 아니라고 하자. $W$는 정렬 집합이므로 $c = \min S$가 존재한다. $c \in S$이므로 $c > f(c)$이며, $f$가 순서 보존이므로 $f(c) > f(f(c))$이다. 한편 $c = \min S$이므로 $f(c) \notin S$이며, $f(f(c)) \geq f(c)$이므로 모순이다. □

(1)의 증명.

$f: (W, <) → (W[a], <)$가 동형사상이라고 하자. 포함사상 $j: W[a] → W$에 대해 $jf: (W, <) → (W, <)$는 순서 보존이다. 따라서 $jf(a) \geq a$이다. 하지만 $a \notin \mathrm{im}f$이므로 모순이다. □

(2)의 증명.

$f: (W, <) → (W, <)$가 동형사상이라고 하자. $f^{-1}$ 또한 동형사상이므로 $x \in W$에 대해 $x \leq f(x)$, $f(x) \leq f^{-1}(f(x)) = x$이다. 따라서 $x = f(x)$이다. □

(3)의 증명.

$f, g: (W_1, <_1) → (W_2, <_2)$가 동형사상이라고 하자. $g^{-1}f: (W_1, <_1) → (W_1, <_1)$은 자기동형사상이므로 (2)에 의해 항등사상이다. 따라서 $f = g$이다. ■

정렬의 삼분성. $(W_1, <_1), (W_2, <_2)$가 정렬 집합일 때 다음 중 정확히 하나가 성립한다.

1. $(W_1, <_1) \sim (W_2, <_2)$
2. 어떤 $a$에 대해 $(W_1[a], <_1) \sim (W_2, <_2)$
3. 어떤 $b$에 대해 $(W_1, <_1) \sim (W_2[b], <_2)$

각 경우 동형사상은 유일하며, 또한 2, 3의 경우 $a, b$는 유일하다.

증명.

앞선 정리는 1, 2, 3이 mutually exclusive함과, 유일성에 대한 주장을 보증한다. 따라서 임의의 $(W_1, <_1), (W_2, <_2)$가 위 세 경우에 속함을 보이면 충분하다.

다음과 같이 부분함수 $f: W_1 → W_2$를 정의한다.

$f$가 단사이고 순서 보존임을 쉽게 확인할 수 있다. 이제 두 가지 경우를 고려한다.

Case 1. $\mathrm{dom} f = W_1$

정리의 3번 경우에 해당하여 증명이 끝난다.

Case 2. $\mathrm{dom} f \subsetneq W_1$

먼저 어떤 $a \in W$에 대해 $\mathrm{dom}f = W_1[a]$임을 보인다. $x \in \mathrm{dom}f$라면 $W_1[x] \sim W_2[f(x)]$이다. 해당 동형의 동형사상을 $\phi$라고 하면 $x' < x$에 대해 $W_1[x'] = W_2[\phi(x')]$이므로 $x' \in \mathrm{dom}f$이다. 따라서 $\mathrm{dom} f$는 초기단이다.

두 번째로 $\mathrm{im} f = W_2$임을 보인다. $\mathrm{dom}f = W_1[a]$라고 하자. 앞선 문단과 비슷한 논증으로 $\mathrm{im}f$ 또한 $W_2$의 초기단임을 알 수 있다. $\mathrm{im}f = W_2[b]$라면, $(a, b) \in f$이므로 $a \in \mathrm{dom}f$이며 모순이다. ■

3. 서수의 완전성

서수의 완전성. 모든 정렬 집합은 어떤 서수와 순서 동형이다.

증명. $(W, <)$가 정렬 집합이라고 하자. 다음과 같이 $A, S$를 정의한다.

$S$가 서수이고 $A$가 초기단임을 쉽게 보일 수 있다. $S = \beta$, $A = W[c]$라고 하자. $f: A → S; a \mapsto \alpha_a$는 $(A, <)$와 $(S, \in)$의 순서동형사상이다. 즉, $W[c] \simeq \beta$이므로 $c \in A$이며, 이는 모순이다. 따라서 $A = W \sim \beta$이다. ■

4. 치환 공리

위 증명에서 $S$의 존재성은 치환 공리꼴 없이 보장되지 않는다. 왜냐하면 부랄리포르티 역설에 의해 $\mathrm{Ord}$는 집합이 아니며, 이에 따라 분류 공리꼴로 $S$의 존재성을 보장할 수 없기 때문이다.

치환 공리의 필요성을 보여주는 다른 예시로, 치환 공리꼴 없이는 $\omega + \omega$의 존재성을 보장할 수 없다. 각 $n \in \mathbb{N}$에 대해 $\omega + n$이 존재함은 짝 공리와 합집합 공리로 보일 수 있지만, $\omega + \omega \coloneqq \cup_{n \in \mathbb{N}} (\omega + n)$가 존재함은 보일 수 없다. 그렇다고 임의의 집합들의 합집합을 허용하는 공리를 추가할 수는 없는데, 이는 $V$를 집합으로 만들기 때문이다.

위 두 경우에서 우리에게 필요한 것은, “잘 정의된 일대일 대응 관계 $R(x,y)$와 집합 $X$가 주어졌을 때 $\{ y : R(x, y), x \in X \}$는 집합이다”라는 내용의 공리이다. 이 공리가 치환 공리이다. 치환 공리를 사용하면 $\omega = \{0, 1, 2, ... \}$와 관계 $R(x, y): y = \omega + x$에 대해 $\mathrm{im}R|_\omega = \{ \omega, \omega + 1, \omega + 2, ... \}$가 존재하며, $\omega \cup \mathrm{im}R|_\omega = \omega + \omega$가 존재함을 보일 수 있다.