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

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

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

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

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

 

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

 

Lemma 1.

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

 

Proof.

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

Base Case:

$\alpha \le 0\Rightarrow \alpha =0\Rightarrow \alpha +0=0$

Successor Case:

$\alpha \le {\beta }^{+}\Rightarrow \alpha \le \beta \vee \alpha ={\beta }^{+}$이다.

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

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

Limit Case:

$\alpha \le \beta \Rightarrow \alpha <\beta \vee \alpha =\beta$이다.

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

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

$◼$

 

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

 

Theorem 1.

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

 

Proof.

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

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

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

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

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

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

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

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

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

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

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

따라서 다음이 성립한다.

$\beta \times \gamma ={\displaystyle \bigcup _{u\in \gamma }\beta \times u\le \bigcup _{u\in \gamma }x=x}$

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

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

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

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

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

$\beta \times \gamma \le \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 \le 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$ 역시 유일함을 알 수 있다.

$◼$