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

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

 

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

 

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

 

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

 

Part 1. Base Case

 

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

 

Part 2. Successor Case

 

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

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

 

Part 3. Limit Case

 

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

$\begin{array}{lll}\left(\alpha+\beta\right)+\gamma&=&\displaystyle\bigcup_{\delta\in\gamma}\left(\left(\alpha+\beta\right)+\delta\right)\\&=&\displaystyle\bigcup_{\delta\in\gamma}\left(\alpha+\left(\beta+\delta\right)\right)\\&=&\displaystyle\bigcup_{\varepsilon\in\left(\beta+\gamma\right)}\left(\alpha+\varepsilon\right)\\&=&\alpha+\left(\beta+\gamma\right)\end{array}$

 

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

 

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

 

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

 

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

 

1. $\forall\alpha,\beta,\gamma\in\text{Ord},\;\alpha(\beta+\gamma)=\alpha\beta+\alpha\gamma$ 2. $\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+\alpha0$

 

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_{\varepsilon\in(\beta+\gamma)}\varepsilon\\&=&\displaystyle\bigcup_{\varepsilon\in(\beta+\gamma)}\alpha\varepsilon\\&=&\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=\alpha0=\alpha(\beta0)$

 

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_{\varepsilon\in\beta\gamma}\alpha\varepsilon\\&=&\alpha(\beta\gamma)\end{array}$

 

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

($\because2\cdot\omega=(1+1)\cdot\omega\neq\omega+\omega$)

 

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

 

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

 

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

 

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

 

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

 

Part 1.

 

Base Case

 

$\alpha^\beta\alpha^0=\alpha^\beta1=\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_{\varepsilon\in\beta+\gamma}\alpha^\varepsilon\\&=&\alpha^{\beta+\gamma}\end{array}$

 

따라서 초한 귀납법에 의해 $\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^{\beta0}$

 

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\left(\gamma+1\right)}\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}$

 

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