집합론, 그 서른한 번째 이야기 | 칸토어 표준형 정리 ( Cantor's Normal Form Theorem )

이번 글에서는 정수론에서의 진법 표현을 서수로 확장한 칸토어 표준형 정리를 소개할 것이다. 칸토어 표준형 정리란, 다음 정리를 말한다.

 

Theorem 1.

$0$이 아닌 임의의 서수 $\alpha$는 다음과 같이 나타낼 수 있으며, 그 방법은 유일하다. $$ \alpha = \omega^\beta_1 \cdot k_1 + \cdots + \omega^\beta_n \cdot k_n $$ 단, $\alpha \geq \beta_1 > \beta_2 > \cdots > \beta_n$이며, $k_1, k_2, \cdots, k_n$은 $0$이 아닌 자연수이다. 또한, 위와 같은 형태의 표현을 $\alpha$의 칸토어 표준형 (Cantor's Normal Form)이라고 한다.

 

Proof.

칸토어 표준형의 존재성은 $\alpha$에 대한 귀납법으로 증명할 수 있다.

$\alpha = 1$인 경우에는 $1 = \omega^0 \cdot 1$이므로 자명하다.

이제 $\alpha$보다 작은 모든 서수에 대해 정리가 성립한다고 가정하자.

그리고 서수 $\beta$를 $\omega^\beta \leq \alpha$인 $\beta$ 중 가장 큰 서수로 설정하자.

그러면 서수의 나눗셈 정리에 의해 $\alpha = \omega^\beta \cdot k + \delta$인 $k$와 $\delta < \omega^\beta$가 유일하게 존재한다.

이때, $\omega \leq k$이면, $\omega^{\beta+1} = \omega^k \cdot \omega \leq \alpha$이므로 $\beta$의 정의에 모순이다.

따라서 $k$는 유한 서수가 되며, $k = 0$인 경우에는 $\alpha = \delta < \omega^\beta$가 되어 $\beta$의 정의에 모순이다. 즉, $k$는 $0$이 아닌 자연수이다.

따라서 귀납가정에 의해 $\alpha$의 칸토어 표준형이 존재한다.

칸토어 표준형의 유일성은 귀납법으로 간단하게 증명된다.^[각주:1]

$\blacksquare$

 

위의 정리는 더욱 일반적인 형태로 확장이 가능하다. 다음 명제를 보자.

 

Corollary 1.

$0$이 아닌 임의의 서수 $\alpha$와 서수 $\delta > 1$가 주어질 때, $\alpha$를 다음과 같이 나타낼 수 있으며, 그 형태는 유일하다. $$ \alpha = \delta^\beta_1 \cdot k_1 + \cdots + \delta^\beta_n \cdot k_n $$ 단, $\alpha \geq \beta_1 > \beta_2 > \cdots > \beta_n$이며, $k_1, k_2, \cdots, k_n$은 $0$보다 크고 $\delta$보다 작다. 위와 같은 형태의 표현을 $\alpha$의 $\delta$진 표현 ($\delta$-Base Expansion)이라고 한다.

 

증명은 칸토어 표준형 정리의 증명과 유사하므로 생략하도록 하겠다.

또한, 칸토어 표준형 정리를 반복적으로 적용하면 비교적 작은 서수들^[각주:2]은 다음과 같이 나타낼 수 있다는 사실을 알 수 있다.

$$ \omega^{\left( \omega^{\left( \omega^7 \cdot 6 + \omega + 42 \right)} \cdot 1729 + \omega^9 + 88 \right)} \cdot 3 + \omega^{\left( \omega^\omega \right)} \cdot 5 + 65537 $$

이렇게 $\omega$의 지수를 다시 칸토어 표준형으로 나타내는 작업을 재귀적으로 적용한 형태를 완전 칸토어 표준형 (Complete Cantor's Normal Form)이라고 한다.

 

 

1. 정수론에서의 n진법 표현의 유일성에 대한 증명을 참고하라. [본문으로]
2. ε0 미만의 서수를 말한다. [본문으로]