집합론, 그 서른 번째 이야기 | 서수의 나눗셈 정리 ( Division Theorem for Ordinals )

이번 글에선 정수론의 나눗셈 정리를 서수로 확장한 정리에 대해 다룰 것이다.

만약 서수와 그의 연산에 대해 잘 모른다면 다음 두 글을 읽은 후에 이번 글을 읽는 것을 추천한다.

집합론, 그 열세 번째 이야기 | 서수 ( Ordinal Numbers )

집합론, 그 열다섯 번째 이야기 | 서수의 연산 ( Arithmetic Operations of Ordinal Numbers )

 

서수의 나눗셈 정리를 증명하기에 앞서, 다음 보조정리를 하나 보자.

 

Lemma 1.

두 서수 $\alpha$, $\beta$에 대하여 $\alpha \leq \beta$라고 하면, $\alpha + \gamma = \beta$인 서수 $\gamma$가 유일하게 존재한다.

 

Proof.

$\beta$에 대한 초한 귀납법을 이용하여 증명할 것이다.

Base Case:

$\alpha \leq 0 \Rightarrow \alpha = 0 \Rightarrow \alpha + 0 = 0$

Successor Case:

$\alpha \leq \beta^+ \Rightarrow \alpha \leq \beta \lor \alpha = \beta^+$이다.

이때, 귀납가정에 의해 $\alpha \leq \beta$인 경우에는 조건을 만족하는 서수 $\gamma$가 유일하게 존재한다.

$\alpha = \beta^+$인 경우, $\alpha + 0 = \beta^+$이고, $\gamma \neq 0$이면 $\alpha + \gamma > \beta^+$이므로 조건을 만족하는 서수 $\gamma$가 유일하게 존재한다.

Limit Case:

$\alpha \leq \beta \Rightarrow \alpha < \beta \lor \alpha = \beta$이다.

이때, $\alpha < \beta$인 경우에는 귀납가정에 의해 조건을 만족하는 서수 $\gamma$가 유일하게 존재한다.

$\alpha = \beta$인 경우에는 $\alpha + 0 = \beta$이고, $\gamma \neq 0$이면 $\alpha + \gamma > \beta$이므로 조건을 만족하는 서수 $\gamma$가 유일하게 존재한다.

$\blacksquare$

 

그럼 이제 서수의 나눗셈 정리를 소개하고 증명하도록 하겠다. 서수의 나눗셈 정리란, 다음 정리를 말한다.

 

Theorem 1.

$\alpha$와 $\beta$가 서수라고 하자. $\beta$가 $0$이 아니라면 다음을 만족하는 두 서수 $\gamma$와 $\delta$가 유일하게 존재한다. $$\alpha = \beta \times \gamma + \delta \land \delta < \beta$$

 

Proof.

먼저, 조건을 만족하는 두 서수 $\gamma$와 $\delta$가 존재함을 보이자.

서수는 정렬서수를 가지므로 $\alpha < \beta$이거나 $\alpha \geq \beta$이다.

$\alpha < \beta$인 경우, $\gamma$를 $0$이라고 하고 $\delta$를 $\alpha$라고 하면 조건을 만족한다.

$\alpha \geq \beta$인 경우는 $\gamma = \displaystyle \bigcup \{ v \;|\; \beta \times v \leq \alpha \}$를 생각하자.

이때, 이 글의 Theorem 1에 의하면 $\gamma$는 집합 $\{ v \;|\; \beta \times v \leq \alpha \}$의 상한이다.

따라서 $\gamma$는 극한 서수이거나 어떤 서수 $u$에 대해 $\gamma = u^+$이다. 이때, $u^+$는 $u$의 다음 서수를 나타낸다.

먼저, $\gamma = u^+$인 경우를 살펴보자.

$\gamma = u^+$로부터 $u < \gamma$임이 자명하고, 따라서 $\gamma$의 정의에 의해 $\beta \times u \leq \alpha$이다.

또한, $\gamma$가 집합 $\{ v \;|\; \beta \times v \leq \alpha \}$의 상한이므로 $u \in v$를 만족하는 $v \in \{ v \;|\; \beta \times v \leq \alpha \}$가 존재한다.

이때, 서수와 그 서수의 다음 서수 사이에는 서수가 존재하지 않으므로 $v$가 $\gamma$보다 작지 않고, 이는 $\gamma \leq v$를 의미하며, 이로 인해 $\beta \times \gamma \leq \alpha$를 얻는다.

이번엔 $\gamma$가 극한 서수인 경우를 생각하자. 그러면 $\gamma$의 임의의 원소 $u$에 대하여 $\beta \times u \leq \alpha$이다.

따라서 다음이 성립한다.

$\beta \times \gamma = \displaystyle \bigcup_{u \in \gamma} \beta \times u \leq \bigcup_{u \in \gamma} x = x$

따라서 $\gamma$가 극한 서수이든 따름 서수이든간에 관계 없이 $\beta \times \gamma \leq \alpha$이다.

이제 귀류법을 이용하여 $\beta \times \gamma^+ > \alpha$임을 보일 것이다.

먼저, $\beta \times \gamma^+ \leq \alpha$라고 가정하자.

그러면 $\gamma < \gamma^+$로부터 $\gamma$는 $\{ v \;|\; \beta \times v \leq \alpha \}$의 상한이라는 사실에 모순이 발생한다.

따라서 $\beta \times \gamma^+ > \alpha$이다.

$\beta \times \gamma \leq \alpha$이고 $\beta \times \gamma^+ > \alpha$이므로 Lemma 1에 의해 $\alpha = \beta \times \gamma + \delta$인 $\delta < \beta$가 유일하게 존재한다.

이제 조건을 만족하는 두 서수 $\gamma$와 $\delta$가 존재함을 보였으므로 이 쌍이 유일하다는 것을 보이자.

먼저 $\alpha = \beta \times \gamma_1 + \delta_1 = \beta \times \gamma_2 + \delta_2$, $\delta_1, \delta_2 \in \beta$임을 가정하자.

그러면 $\gamma = \gamma_1$과 $\gamma = \gamma_2$에 대하여 다음이 공통적으로 성립한다.

$\beta \times \gamma \leq x < \beta \times \gamma + \beta = \beta \times \gamma^+$

따라서 $\beta \times \gamma_1 < \beta \times \gamma_2^+$와 $\beta \times \gamma_2 < \beta \times \gamma_1^+$를 얻을 수 있다.

따라서 서수의 연산의 성질에 의해 $\gamma_1 < \gamma_2^+$, $\gamma_2 < \gamma_1^+$를 얻게 되며, 간단한 귀류법에 의해 $\gamma_1 = \gamma_2$임을 알 수 있다.

따라서 $\gamma$가 유일하며, $\gamma$가 유일하므로 Lemma 1에 의해 $\delta$ 역시 유일함을 알 수 있다.

$\blacksquare$