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

이 글에서는 서수에 대해 설명한 글에서 잠깐 언급했었던 서수의 연산에 대해 설명할 것이다. 또한, 이 글에서는 서술의 편의를 위해 모든 극한 서수의 모임을 $\text{LO}$이라고 쓰겠다.

 

서수의 덧셈은 초한 귀납법을 이용하여 다음과 같은 조건들을 만족하는 연산으로 정의한다.

 

1. $\mathrm{\forall }\alpha \in \text{Ord},\alpha +0=\alpha$ 2. $\mathrm{\forall }\alpha ,\beta \in \text{Ord},(\alpha +\beta )+1=\alpha +(\beta +1)$ 3. $\mathrm{\forall }\beta \in \text{LO},\alpha +\beta ={\displaystyle \bigcup _{\gamma \in \beta }(\alpha +\gamma )}$

 

서수의 덧셈도 자연수의 덧셈처럼 결합법칙이 성립한다. 이는 초한 귀납법을 이용하여 증명할 수 있으며, 그 과정은 아래와 같다.

 

Part 1. Base Case

 

$(\alpha +\beta )+0=\alpha +\beta =\alpha +(\beta +0)$

 

Part 2. Successor Case

 

$\gamma$에 대해 $(\alpha +\beta )+\gamma =\alpha +(\beta +\gamma )$가 성립한다고 가정하자.

$\begin{array}{lll}(\alpha +\beta )+(\gamma +1)& =& ((\alpha +\beta )+\gamma )+1\\ & =& (\alpha +(\beta +\gamma ))+1\\ & =& \alpha +((\beta +\gamma )+1)\\ & =& \alpha +(\beta +(\gamma +1))\end{array}$

 

Part 3. Limit Case

 

$\gamma \in \text{LO}$라 하고 $\mathrm{\forall }\delta \in \text{Ord},\delta <\gamma \Rightarrow (\alpha +\beta )+\delta =\alpha +(\beta +\delta )$임을 가정하자.

$\begin{array}{lll}(\alpha +\beta )+\gamma & =& {\displaystyle \bigcup _{\delta \in \gamma }((\alpha +\beta )+\delta )}\\ & =& {\displaystyle \bigcup _{\delta \in \gamma }(\alpha +(\beta +\delta ))}\\ & =& {\displaystyle \bigcup _{\epsilon \in (\beta +\gamma )}(\alpha +\epsilon )}\\ & =& \alpha +(\beta +\gamma )\end{array}$

 

따라서 초한 귀납법에 의해 서수의 덧셈의 결합법칙은 성립한다. 그렇다면 서수의 덧셈의 교환법칙도 과연 성립할까? 이에 대한 대답은 '그렇지 않다'이다. 한 가지 예를 들어보자. $1+\omega$는 $\omega +1$과 같을까? $\omega +1=S\left(\omega \right)$임은 자명하므로 $1+\omega$의 값만 계산해보면 비교할 수 있을 것이다. 극한서수의 덧셈의 정의에 의해 $1+\omega ={\displaystyle \bigcup _{n\in \omega }(1+n)}$이며, $0\cup 1=1$이므로 ${\displaystyle \bigcup _{n\in \omega }(1+n)={\displaystyle \bigcup _{n\in \omega }n=\omega }}$이다. 따라서 $1+\omega =\omega$이다. 이때, $\omega \ne S\left(\omega \right)$임은 자명하므로 $1+\omega \ne \omega +1$이다. 따라서 서수의 덧셈은 교환법칙이 성립하지 않는다.

 

서수의 덧셈에 대해 이야기했으니 이제 서수의 곱셈에 대해 말할 차례다. 서수의 곱셈은 초한 귀납법을 이용하여 아래의 조건들을 만족하는 연산으로 정의한다.

 

1. $\mathrm{\forall }\alpha \in \text{Ord},\alpha 0=0$ 2. $\mathrm{\forall }\alpha ,\beta \in \text{Ord},\alpha (\beta +1)=\alpha \beta +\alpha$ 3. $\mathrm{\forall }\beta \in \text{LO},\alpha \beta ={\displaystyle \bigcup _{\gamma \in \beta }\left(\alpha \gamma \right)}$

 

서수의 곱셈도 자연수의 곱셈처럼 결합법칙이 성립하며, 덧셈에 대한 좌분배법칙이 성립한다. 즉, 아래의 세 가지 명제가 성립한다.

 

1. $\mathrm{\forall }\alpha ,\beta ,\gamma \in \text{Ord},\alpha (\beta +\gamma )=\alpha \beta +\alpha \gamma$ 2. $\mathrm{\forall }\alpha ,\beta ,\gamma \in \text{Ord},\left(\alpha \beta \right)\gamma =\alpha \left(\beta \gamma \right)$

 

아래는 위의 세 가지 명제의 증명과정이다.

 

Part 1. 덧셈에 대한 좌분배법칙

 

Base Case

 

$\alpha (\beta +0)=\alpha \beta =\alpha \beta +0=\alpha \beta +\alpha 0$

 

Successor Case

 

$\begin{array}{lll}\alpha (\beta +(\gamma +1))& =& \alpha (\beta +\gamma +1)\\ & =& \alpha (\beta +\gamma )+\alpha \\ & =& \alpha \beta +\alpha \gamma +\alpha \\ & =& \alpha \beta +\alpha (\gamma +1)\end{array}$

 

Limit Case

 

$\begin{array}{lll}\alpha (\beta +\gamma )& =& \alpha {\displaystyle \bigcup _{\delta \in \gamma }(\beta +\delta )}\\ & =& \alpha {\displaystyle \bigcup _{\epsilon \in (\beta +\gamma )}\epsilon }\\ & =& {\displaystyle \bigcup _{\epsilon \in (\beta +\gamma )}\alpha \epsilon }\\ & =& {\displaystyle \bigcup _{\delta \in \gamma }\alpha (\beta +\delta )}\\ & =& {\displaystyle \bigcup _{\delta \in \gamma }(\alpha \beta +\alpha \delta )}\\ & =& \alpha \beta +{\displaystyle \bigcup _{\delta \in \gamma }\alpha \delta }\\ & =& \alpha \beta +\alpha \gamma \end{array}$

 

따라서 초한 귀납법에 의해 서수의 곱셈의 덧셈에 대한 좌분배법칙이 성립한다.

 

Part 2. 곱셈의 결합법칙

 

Base Case

 

$(\alpha \beta )0=0=\alpha 0=\alpha (\beta 0)$

 

Successor Case

 

$\begin{array}{lll}(\alpha \beta )(\gamma +1)& =& (\alpha \beta )\gamma +(\alpha \beta )\\ & =& \alpha (\beta \gamma )+\alpha \beta \\ & =& \alpha (\beta \gamma +\beta )\\ & =& \alpha (\beta (\gamma +1))\end{array}$

 

Limit Case

 

$\begin{array}{lll}(\alpha \beta )\gamma & =& {\displaystyle \bigcup _{\delta \in \gamma }(\alpha \beta )\delta }\\ & =& {\displaystyle \bigcup _{\delta \in \gamma }\alpha (\beta \delta )}\\ & =& {\displaystyle \bigcup _{\epsilon \in \beta \gamma }\alpha \epsilon }\\ & =& \alpha (\beta \gamma )\end{array}$

 

따라서 초한 귀납법에 의해 서수의 곱셈의 결합법칙이 성립한다. 그렇다면 서수의 곱셈도 자연수의 곱셈처럼 교환법칙이 성립할까? 이에 대한 대답은 '그렇지 않다'이다. 한 가지 예를 들어보자. $2\cdot \omega$는 $\omega \cdot 2$와 같을까? $2\cdot \omega ={\displaystyle \bigcup _{n\in \omega }2n=\omega }$이지만, $\omega \cdot 2=\omega \cdot (1+1)=\omega +\omega$이므로 $2\cdot \omega \ne \omega \cdot 2$이다. 따라서 서수의 곱셈의 교환법칙이 성립하지 않는다. 또한, 이로부터 덧셈에 대한 우분배법칙이 성립하지 않는다는 것을 쉽게 알 수 있다.

($\because 2\cdot \omega =(1+1)\cdot \omega \ne \omega +\omega$)

 

서수의 덧셈과 곱셈에 대해 설명했으니 이제 거듭제곱에 대해 설명할 차례이다. 서수의 거듭제곱은 초한 귀납법을 이용하여 아래의 조건을 만족하는 연산으로 정의한다.

 

1. $\mathrm{\forall }\alpha \in \text{Ord},{\alpha }^0=1$ 2. $\mathrm{\forall }\alpha ,\beta \in \text{Ord},{\alpha }^{\beta +1}={\alpha }^{\beta }\alpha$ 3. $\mathrm{\forall }\beta \in \text{LO},{\alpha }^{\beta }={\displaystyle \bigcup _{\gamma \in \beta }{\alpha }^{\gamma }}$

 

서수의 거듭제곱도 자연수의 거듭제곱과 같이 지수법칙이 성립한다. 즉, 다음 두 가지 명제가 성립한다.

 

1. $\mathrm{\forall }\alpha ,\beta ,\gamma \in \text{Ord},{\alpha }^{\beta }{\alpha }^{\gamma }={\alpha }^{\beta +\gamma }$ 2. $\mathrm{\forall }\alpha ,\beta ,\gamma \in \text{Ord},{\left({\alpha }^{\beta }\right)}^{\gamma }={\alpha }^{\beta \gamma }$

 

아래는 위의 두 가지 명제의 증명이다.

 

Part 1.

 

Base Case

 

${\alpha }^{\beta }{\alpha }^0={\alpha }^{\beta }1={\alpha }^{\beta }={\alpha }^{\beta +0}$

 

Successor Case

 

$\begin{array}{lll}{\alpha }^{\beta }{\alpha }^{\gamma +1}& =& {\alpha }^{\beta }{\alpha }^{\gamma }\alpha \\ & =& {\alpha }^{\beta +\gamma }\alpha \\ & =& {\alpha }^{\beta +\gamma +1}\end{array}$

 

Limit Case

 

$\begin{array}{lll}{\alpha }^{\beta }{\alpha }^{\gamma }& =& {\alpha }^{\beta }{\displaystyle \bigcup _{\delta \in \gamma }{\alpha }^{\delta }}\\ & =& {\displaystyle \bigcup _{\delta \in \gamma }{\alpha }^{\beta }{\alpha }^{\delta }}\\ & =& {\displaystyle \bigcup _{\delta \in \gamma }{\alpha }^{\beta +\gamma }}\\ & =& {\displaystyle \bigcup _{\epsilon \in \beta +\gamma }{\alpha }^{\epsilon }}\\ & =& {\alpha }^{\beta +\gamma }\end{array}$

 

따라서 초한 귀납법에 의해 $\mathrm{\forall }\alpha ,\beta ,\gamma \in \text{Ord},{\alpha }^{\beta }{\alpha }^{\gamma }={\alpha }^{\beta +\gamma }$가 성립한다.

 

Part 2.

 

Base Case

 

${\left({\alpha }^{\beta }\right)}^0=1={\alpha }^0={\alpha }^{\beta 0}$

 

Successor Case

 

$\begin{array}{lll}{\left({\alpha }^{\beta }\right)}^{\gamma +1}& =& {\left({\alpha }^{\beta }\right)}^{\gamma }{\alpha }^{\beta }\\ & =& {\alpha }^{\beta \gamma }{\alpha }^{\beta }\\ & =& {\alpha }^{\beta \gamma +\beta }\\ & =& {\alpha }^{\beta (\gamma +1)}\end{array}$

 

Limit Case

 

$\begin{array}{lll}{\left({\alpha }^{\beta }\right)}^{\gamma }& =& {\displaystyle \bigcup _{\delta \in \gamma }{\left({\alpha }^{\beta }\right)}^{\delta }}\\ & =& {\displaystyle \bigcup _{\delta \in \gamma }{\alpha }^{\beta \delta }}\\ & =& {\displaystyle {\alpha }^{\bigcup _{\delta \in \gamma }\beta \delta }}\\ & =& {\alpha }^{\beta \gamma }\end{array}$

 

따라서 초한 귀납법에 의해 $\mathrm{\forall }\alpha ,\beta ,\gamma \in \text{Ord},{\left({\alpha }^{\beta }\right)}^{\gamma }={\alpha }^{\beta \gamma }$가 성립한다.