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

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

 

Theorem 1.

$0$이 아닌 임의의 서수 $\alpha$는 다음과 같이 나타낼 수 있으며, 그 방법은 유일하다. $$\alpha ={\omega }_1^{\beta }\cdot k_1+\cdots +{\omega }_n^{\beta }\cdot k_n$$ 단, $\alpha \ge {\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 }\le \alpha$인 $\beta$ 중 가장 큰 서수로 설정하자.

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

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

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

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

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

$◼$

 

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

 

Corollary 1.

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

 

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

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

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

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

 

 

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