Hanul Jeon
POSTS, SET-THEORY

서수란 무엇인가

Summary in English: This series of posts, which will comprise two posts, aims to explain the notion of ordinal and cardinal, which is the basic concept of set theory. This post, the first post of the series, will explain about the basic concept of ordinals. I will try to give an intuitive explanation as possible.

Acknowledgment: Some of my explanations originated from my previous introductory paper about the Goodstein theorem. Hansol Jeon pointed out some errors in this paper for which I am thankful. I am also thankful for my colleague allowing me to mention the conversation between her and me.

며칠 전에 지인을 만나서 이야기를 하다 집합론에 대해 이야기가 나왔습니다. 그 지인은 제게 기수와 서수라는 개념이 이해하기 어렵다고 이야기했고, 기수와 서수를 빼고 집합론을 공부할 수 없느냐는 질문을 했습니다. 저는 기수와 서수는 집합론, 그리고 논리학 전반에서 약방의 감초같은 존재라고 했고1, 또한 저는 대부분 수학자들은 이 지점에서 집합론 공부를 그만두지 않겠느냐 이야기했습니다. 그리고 이 말을 하면서 왜 집합론이 보통 수학자들 눈에 잘 안 들어가는 지 감잡을 수 있었습니다. (때로는 별 생각없이 말하면서 깨닫기도 하는 것 같습니다.) 따라서 집합론에 대해 본격적인 소개 이전에 기수와 서수가 무엇인지 설명할 필요성이 있음을 알 수 있었습니다.

기수와 서수는 집합론이 생겨나게 된 두 개의 큰 축 중 하나라고 할 수 있습니다.2 칸토어의 집합론 연구는 서수와 초한재귀법의 발견에서 시작되었고, 집합론을 이 위치까지 발전시킨 연속체 가설 또한 기수에 대한 문제입니다. 따라서 서수와 기수가 뭔지 모르면 현업 집합론이 어떤 일을 하는지 이해하는 것 자체가 불가능합니다. 당장, Jech의 집합론 책의 2, 3단원이 각각 서수와 기수를 다룬다는 것만 봐도 기수와 서수가 얼마나 기초적인 개념인지 알 수 있습니다. 아쉽게도, 적어도 국내에서 이 둘을 제대로 배울 방법은 거의 없는 것처럼 보입니다. 이 글에서는 기수와 서수에 대해 최대한 직관적인 접근을 하려고 합니다. 원래는 한 글에 모든 내용을 설명하려고 했지만, 글이 생각보다 길어질 것 같고, 긴 글을 어떠한 자극도 없이 쓰는 것은 지루하고 지치는 일이기 때문에 두 부분으로 나눌 생각입니다.

모든 것을 처음부터 설명하는 것은 비효율적이기 때문에, 독자가 어느 정도 기초적인 집합론 공부를 해서 칸토어의 대각선 논법과 이를 통한 $\mathbb{R}$이 비가산이라는 증명, 그리고 가산 집합과 비가산 집합에 대한 공부를 어느 정도 했음을 가정할 것입니다. 또한 독자가 집합론 시간에 자연수 체계와 그 위에서의 귀납법, 재귀(recursion), 그리고 선택공리에 대해 안다는 것 또한 가정할 것입니다. 이 내용들은 여느 수학과에 열리는 집합론 수업을 들었다면 알고 있으리라 생각합니다.

우선, 서수에 대해 설명하려고 합니다. 국립국어원 표준대사전에 따르면 서수는 “사물의 순서를 나타내는 수”입니다. 이러한 기본적인 개념은 집합론에서도 마찬가지입니다. 하지만 실제 집합론 교재에서 정렬순서니 뭐니 등을 이용해서 서수를 설명하죠. 서수의 정의를 모를 분을 위해, 서수의 정의를 잠깐 짚고 넘어가도록 합시다:

정의. 구조 $(X,\le)$가 반순서집합 (partially ordered set)이라는 것은 다음 세 조건을 만족하는 것이다:

  1. (반사성) 모든 $x\in X$에 대해 $x\le x$,

  2. (반대칭성) 모든 $x,y\in X$에 대해 $x\le y$이고 $y\le x$이면 $x=y$,

  3. (추이성) 모든 $x,y,z\in X$에 대해 $x\le y$, $y\le z$이면 $x\le z$.

그리고 $(X,\le)$가 다음 조건을 추가적으로 만족한다면 선형순서집합 (linearly ordered set)이라 한다:

  1. (비교가능성) 모든 $x,y\in X$에 대해 $x\le y$이거나 $y\le x$이다.

그리고 선형순서집합 $(X,\le)$가 다음 조건을 만족하면 정렬집합 (well-ordered set)이라 부른다:

  1. (정렬가능성) 임의의 공집합이 아닌 부분집합 $A\subseteq X$에 대해 $A$의 최소원 $\min A$가 존재한다.

우리는 $a<b$를 $(a\le b)\land (a\neq b)$로 정의한다. 그리고 이를 강한 순서 (strict order)라 부를 것이다. 때때로 우리들은 보통 순서 대신 강순서를 이용해서 순서집합을 정의할 것이다. 특히, 강순서는 다음 조건들을 만족한다:

  1. 모든 $x\in X$에 대해 $x\nless x$.

  2. (추이성) 모든 $x,y,z\in X$에 대해 $x<y$이고 $y<z$이면 $x<z$.

정의. 어떤 집합 $X$가 추이적(transitive)이란 것은 임의의 $x,y$에 대해 $x\in y \in X$이면 $x\in X$인 것이다.

정의. 어떤 집합 $\alpha$가 서수 (ordinal)이란 것은 $\alpha$가 추이적이고 $(\alpha,\in)$이 정렬집합인 것이다. 즉, $\in$이 집합 $\alpha$ 위에서 강순서인 것이다. 특히, $\alpha$가 서수이면 다음 조건들이 성립해야 한다:

  1. (추이성) $\xi\in\eta$이고 $\eta\in\alpha$이면 $\xi\in\alpha$이다.

  2. (비교가능성) 모든 $\xi,\eta\in \alpha$에 대해 $\xi\in\eta$, $\xi=\eta$ 혹은 $\eta\in\xi$가 성립한다.

  3. (정렬가능성) 만약 $A\subseteq\alpha$가 공집합이 아닌 $\alpha$의 부분집합이면, 어떤 $\beta\in A$가 있어 $\beta$는 $A$의 최소원이다. 즉, 임의의 $\xi\in A$에 대해 $\beta=\xi$ 혹은 $\beta\in \xi$가 성립한다.

위의 정의가 이해되지 않는다고 해서 지금 무리하게 이해하려고 할 필요는 없습니다. 이 정의의 의미를 소개하는 게 이 글의 뒷부분에서 할 일입니다. 제가 아는 한, 정렬순서집합의 정의는 칸토어 때까지 거슬러 올라가고, 위의 형태의 서수의 정의는 폰 노이만에 의해 주어졌습니다. 수학에서 비형식적 개념과 형식적 정의 간에 거리가 있는 일은 흔히 있지만, 이 차이를 이해하는 것은 종종 쉬운 일이 아닙니다. 폰 노이만이 준 정의니 인간이 이해할 수 없는 것이라 포기하는 대신, 왜 위의 정의여야 하는지 보고자 합니다.

다시 말하자면, 서수는 사물의 순서를 나타낼 때 쓰는 수입니다. 즉, 사람들을 일렬로 나열했을 때 왼쪽에서 오른쪽 순서로 번호를 붙이면 붙는 수가 서수라는 것입니다. 0부터 시작해서 $n$명이 나열된 열을 묘사한다면 아마 이렇게 쓸 수 있을 것입니다:

\[ 0 < 1 < 2 < \cdots < (n-1) \]

여기서 관찰을 하나 합시다: 가령, $1$이라는 숫자 전에는

\[ 0 \]

이라는 열이 옵니다. 그리고, $3$이라는 숫자 전에는

\[ 0 < 1 < 2 \]

라는 열이 옵니다. 마지막으로, $n$이라는 숫자 전에는

\[ 0 < 1 < 2 < \cdots < (n-1) \]

열이 와야 할 것입니다. 그리고 위에서 제시한 열의 형태는 ‘그 열을 자른 위치’에 대해 유일합니다. 즉, $0<1<2$라는 형태의 열은 $3$ 이전의 열을 따졌을 때만 나타날 거라는 것입니다. 가령, $4$ 이전에서 자르면 $0<1<2<3$과 같이 좀 더 긴 열이 나오고, $2$ 이전에서 자르면 $0<1$같이 더 짧은 열이 나오지, 정확히 $0<1<2$라는 열은 안 나옵니다. 따라서 $3$이 $0<1<2$라는 열을 “대표”한다고 생각할 수 있습니다. 마찬가지로, $n$이라는 수가

\[ 0 < 1 < 2 < \cdots < (n-1) \]

라는 열을 “대표”한다고 생각할 수 있습니다. 그러면 $0$은 어떤 열을 대표할까요? 0 이전으로는 어떠한 수도 따라오지 않으니, 열은 비어있는 열, 그러니까 아무 것도 세워지지 않은 줄을 대표한다고 생각할 수 있습니다.

이러한 철학에 따라서, $0=\varnothing$이라 둡시다. $n$이 $ 0 < 1 < 2 < \cdots < (n-1)$을 ‘대표’한다는 철학에 따라서, $n=\{0,1,\cdots,(n-1)\}$으로 둡시다. 그러면 재밌는 사실을 하나 관찰할 수 있습니다: 가령, $0<1$이면 $0\in 1=\{0\}$입니다. $2<5$이니 $2\in 5=\{0,1,2,3,4\}$이기도 합니다. 이는 $n$을 $\{0,1,\cdots,(n-1)\}$으로 둔 데에서 나오는 일반적인 사실입니다: 즉, $m<n$이면 $m\in n$입니다.

그런데 여기서 $<$는 뭘까요? 집합론의 제일 큰 모토 중 하나는 “모든 것이 집합일 수 있다”는 것입니다. 다르게 말하면, 지금 다루는 자연수 역시 집합일 수 있다는 것입니다. 그리고 우리들은 아직 자연수의 실체를 모릅니다. 이럴 때 쓸 수 있는 방법은 위의 유비를 그냥 정의로 바꾸는 것입니다. 즉, $n$은 $\{0,1,\cdots (n-1)\}$으로 주어지는 집합이며, 강순서 $<$는 그냥 $\in$으로 주어진다고 생각할 수 있습니다.

여기서 좀 더 생각을 하면, 다음 사실도 알 수 있습니다. 그에 대한 판단은 독자에게 맡겨 둡니다:

사실. $n\le m$일 필요충분조건은 $n\subseteq m$인 것이다.

하지만 수학에서 나오는 대상이 모두 유한하지만은 않습니다. 이에 따라 무한히 큰 대상도 고려해야 합니다. 이제 다음과 같이 생긴 무한히 긴 줄을 상상해봅시다:

\[0 < 1 < 2 < 3 < \cdots < n < n + 1 < \cdots \]

이는 자연수 집합 $\mathbb{N}$과 똑같이 생긴 순서집합입니다. 우리들은 위의 순서형을 $\omega$라 나타낼 것입니다. 집합론적으로 쓰자면, $\omega=\{0,1,2,3,\cdots\}$겠고, 모든 자연수들의 집합과 같습니다.3 이제, 위의 순서형에 자연수를 하나 더 붙여보려고 합니다. 그러면 다음과 같은 순서형이 나타날 것입니다:

\[0 < 1 < 2 < 3 < \cdots < \omega \]

이러한 순서형을 어떻게 나타낼까요? 유한한 순서열을 관찰함으로써 어떻게 나타내야 할 지 알 수 있습니다: $0$에서 $1$로 넘어가는 것은, $0$에 $1$을 더하는 것으로 이해할 수도 있습니다. $4$에서 바로 다음 수인 $5$로 넘어가는 것도 $4$에 $1$을 더하는 것으로 이해할 수 있습니다. 그러면 위에서 나타낸 무한한 길이의 나열도, 그 이전 서수인 $\omega$에 $1$을 더한 것으로 이해할 수 있지 않을까요? 이러한 철학에 따라, 순서형

\[0 < 1 < 2 < 3 < \cdots < \omega \]

을 $\omega+1$로 나타낼 것입니다. 마찬가지로,

\[0 < 1 < 2 < 3 < \cdots < n < n + 1 < \cdots < \omega < \omega+1\]

이라는 순서형은 $\omega+2$라고 나타낼 수 있겠죠. 이를 무한히 이어 나가면

\[0 < 1 < 2 < 3 < \cdots< \omega < \omega+1 < \omega+2 < \cdots \]

라는 순서형이 얻어질 것이고, 이는 $\omega+\omega$로 나타낼 수 있을 것입니다. 여기서, $\omega+\omega$라고 쓰는 대신 곱셈을 이용해서 $\omega\cdot 2$라고 써 봅시다. (왜 $2\cdot\omega$가 아닌 지는 뒤에서 설명할 것입니다.) 마찬가지로,

\[0 < 1 < 2 < 3 < \cdots< \omega < \omega+1 < \omega+2 < \cdots < \omega+\omega \] 와 같이 나타내어지는 순서형은 $\omega\cdot 2+1$이라 쓸 수 있을 것이고, 여기서 한 단계 점프해서

\[0 < 1 < 2 < 3 < \cdots< \omega < \omega+1 < \omega+2 < \cdots < \omega\cdot 2 < \omega\cdot 2+1 < \cdots \]

와 같이 이어지는 순서형은 $\omega\cdot 3$과 같이 쓸 수 있을 것입니다. 내친 김에 더 나아가 봅시다.

\[\begin{multline}0 < 1 < 2 < 3 < \cdots< \omega < \omega+1 < \omega+2 < \cdots < \omega\cdot 2 < \omega\cdot 2+1 < \cdots \\ < \omega\cdot 3 < \omega\cdot 3+ 1 < \cdots < \omega\cdot 4 < \cdots < \omega\cdot 5 < \cdots \end{multline}\]

과 같이 이어지는 열은 어떻게 표현해야 할까요? 어떻게 보면, 이러한 열은 $\omega$, $\omega\cdot 2$, $\omega\cdot 3$, $\cdots$ 등을 ‘합집합하면’ 얻어지는 열과 같음을 알 수 있습니다. 이 수열의 이름을 어떻게 붙일 지 고민하기 전에, 이전에 봤던 열들에 대한 관찰을 좀 더 해 봅시다. 가령,

\[0 < 1 < 2 < 3 < \cdots< \omega < \omega+1 < \omega+2 < \cdots \]

라는 수열은 $0 < 1 < 2 < 3 < \cdots$이라는 열에 $0 < 1 < 2 < 3 < \cdots$이란 열을 “이어붙인” 것으로 생각할 수 있습니다. 달리 쓰면, $\omega\cdot 2$는 $\omega$에 $\omega$를 이어붙인 것, 즉 $\omega\cdot 2 = \omega+\omega$로 이해할 수 있습니다. 마찬가지로, $\omega\cdot 3$은 $\omega\cdot 2$에 $\omega$를 이어붙인 것, 즉 $\omega\cdot 3=\omega\cdot2+\omega$라고 생각할 수 있습니다. 일반적으로 모든 $\omega\cdot n$에 대해서도 마찬가지 관찰을 할 수 있을 것입니다. 즉, $\omega\cdot n$은 $\omega$를 $n$번 붙인 것으로 생각할 수 있습니다.

그러면 \[\begin{multline}0 < 1 < 2 < 3 < \cdots< \omega < \omega+1 < \omega+2 < \cdots < \omega\cdot 2 < \omega\cdot 2+1 < \cdots \\ < \omega\cdot 3 < \omega\cdot 3+ 1 < \cdots < \omega\cdot 4 < \cdots < \omega\cdot 5 < \cdots \end{multline}\] 는 $\omega$를 $\omega$번 붙인 거라 생각할 수 있지 않을까요? 따라서 이를 $\omega\cdot \omega=\omega^2$으로 나타냅시다. 이보다 더 큰 서수에 대한 표현으로 나아갈 수 있겠지만, 여기서부터는 서수에 대한 연산을 정의하고 나서 체계적으로 설명하는 게 나으니 뒤로 미루겠습니다.

이렇게 무한서수가 어떤 대상인지, 그리고 왜 서수의 순서를 $\in$으로 잡았는지 감을 잡았을 것이라 생각합니다. 그런데 한 가지 의문이 남습니다. 서수 $(\alpha,\in)$가 정렬집합이란 것과 위에서 설명한 서수의 개념과 무슨 연관이 있을까요? 무한강하법이란 단어를 들어본 적이 있는 분이라면 이를 힌트삼을 수 있습니다. 하지만 안 들어본 분도 있을 것 같으니 설명해보겠습니다.

다시, 자연수들의 열로 돌아가봅시다:

\[ 0 < 1 < 2 < 3 < 4 < 5 < 6 < 7 < \cdots \]

가령 7부터 시작해서 역으로 세 봅시다: $7$, $6$, $5$, $4$, $\cdots$. 이렇게 세면 유한한 시간 안에 0에 도달할 겁니다. (이 경우에는 8번 세면 0으로 도달하겠죠.) 이는 어떤 자연수에서 시작해도, 중간에 얼마나 많은 자연수를 건너뛰느냐에 상관 없이 성립합니다: 즉, 어떻게 자연수를 세더라도, 감소하는 순으로 세면 유한한 시점 안에 0으로 도달합니다. 이를 형식적으로 쓰면 이렇습니다:

사실. $\langle n_k \mid k\in\mathbb{N}\rangle$이고 $n_0>n_1>n_2>\cdots$인 자연수열은 존재할 수 없다.

왜 ‘존재할 수 없다’는 형태로 기술했을까요? $n_0>n_1>n_2>\cdots$을 만족하는 자연수열이 있다는 것은, $n_0$으로 시작해서 감소하는 순으로 셌을 때 무한히 끝나지 않는 경우가 있다는 뜻이기도 해서 그렇습니다. (이해가 안 간다면, 유리수 구조 위에서 $1$, $1/2$, $1/3$, $\cdots$를 감소순으로 세어보는 것도 도움이 될 수 있습니다.) 그러면 이제, 좀 더 긴 서수열을 가져와서 비슷한 생각을 해 봅시다:

\[ 0 < 1 < 2 < 3 < 4 < \cdots \omega < \omega+1 < \omega+2 < \omega+3 < \omega+4 < \cdots \]

가령, $\omega+4$에서 시작해서 감소순으로 수를 세 봅시다. 그러면 다섯 단계 안에 $\omega$에 도달할 것입니다. 이제 여기서 $0$까지 내려가는 순으로 세 볼 것입니다. 아까 말했듯, 중간에 숫자를 건너뛰는 것을 허용합시다. 그렇지 않으면 $\omega$ “바로 전” 숫자가 없으니 감소순으로는 더 셀 수 없을 것입니다. 그런데 $\omega$보다 작은 수는 그게 뭐든간 자연수겠죠. 가령, $39$에서 다시 시작했다고 합시다. $39$부터 역순으로 세면, 아무리 길어도 $40$단계 안에 $0$에 도달할 겁니다. 위의 내용을 요약하면,

\[\omega+4>\omega+3>\cdots> \omega>39>38,\cdots> 1>0\]

같이 이어지는 열을 고려했고, 이는 유한한 길이 안에 끝난다는 것입니다. 이는 중간에 “건너뛰는” 수를 $39$ 대신 다른 자연수로 잡아도 마찬가지일 것입니다.

내친 김에 좀 더 큰 서수에 대해서도 생각해봅시다. 한 번 $\omega\cdot\omega+1$을 고려해봅시다:

\[0 < 1 < 2 < \cdots< \omega < \omega+1 < \cdots < \omega\cdot 2 < \cdots < \omega\cdot 3 < \cdots < \omega\cdot\omega \]

이제 $\omega\cdot\omega$에서 시작해서 역순으로 세 볼 것입니다. 그런데 $\omega\cdot\omega$ “바로 전” 수는 없습니다. 따라서 그보다 작은 서수에서 시작해야겠죠. $\omega\cdot\omega$보다 작은 서수는 $\omega\cdot n + m$꼴입니다. 여기서는 가령, $\omega\cdot 7 + 65$에서 시작해봅시다. 여기서 차근차근 감소순으로 내려가다 보면, 아무리 길어도 $66$단계 안에 $\omega\cdot 7$에 도달할 겁니다. 그런데 $\omega\cdot 7$ 역시 “바로 전” 수가 없으니 그보다 작은 서수를 하나 골라와야 합니다. 한 번 $\omega\cdot 3 + 46$을 골라봅시다. 이 경우에도 역시, 아무리 길어도 $47$단계 안에 $\omega+3$에 도달할 것입니다. 이제 $\omega+3$보다 작은 서수를 하나 골라야 합니다. 한 번 $876$을 골라봅시다. 이는 자연수이므로, $876$부터 감소순으로 세면 아무리 길어도 $877$번 안에 $0$에 도달할 것입니다.

위에서 생각한 감소열을 적자면 다음과 같습니다:

\[\omega\cdot\omega>\omega\cdot 7 + 65 > \cdots > \omega\cdot 7 > \omega\cdot 3 + 46 > \cdots > \omega\cdot 3 > 876 > 875 > \cdots > 0\]

이 역시 길이는 유한합니다. 이를 좀 일반화해서, 우리들이 구성한 서수열 위에서 감소열은 항상 유한한 길이 안에 끝난다는 생각을 할 수 있습니다. 즉, 무한히 감소하는 서수열은 없다는 것입니다:

사실. $\alpha_0>\alpha_1>\cdots$를 만족하는 서수열 $\langle \alpha_n\mid n\in\mathbb{N}\rangle$은 없다.

그런데 위의 서술이 어떻게 정렬가능성과 연관지어질 수 있을까요? 집합론에서 많이 등장하는 사고법 중 하나로 함수를 집합으로 바꾸는 것이 있습니다. 이는 연구 분야로서의 집합론에 들어갈 때도 사람의 이해를 종종 괴롭히는 부분인데, 한편 이러한 작업을 통해 다루는 대상을 함수에서 집합으로 단순화시킬 수 있다는 이점도 지닙니다. 집합론 수업을 들어서 집합론에서 함수를 순서쌍들의 집합으로 정의한다는 것을 안다면, 순서쌍들의 집합보다 그 치역이 좀 더 간단한 집합일 것이라는 사실에는 동의할 수 있을 것이라 생각합니다.

상술했듯, 무한히 감소하는 서수열은 없습니다. 이 말인즉슨, 약하게 감소하는 서수열 $\alpha_0\ge \alpha_1\ge\alpha_2\ge\cdots$가 있으면 이 서수열은 언젠가 상수로 멈출 것이란 뜻이기도 합니다: 그렇지 않고 계속 감소하면 ‘상수로 정체된 구간’은 건너뛰는 방식으로 무한히 감소하는 서수열을 얻을 수 있기 때문입니다. 이를 수열이 아니라 집합 $\{\alpha_0,\alpha_1\cdots\}$의 관점에서 본다면, 해당 집합이 유한집합이고 제일 작은 원소를 갖는다는 말이 됩니다.

위 사실을 달리 말하면, 어떤 서수의 유한 부분집합은 항상 최소원을 갖는다는 말이기도 합니다. 그런데 서수 위에서 감소수열이 없다는 주장을 했을 때, 모든 수열에 대해서 이야기했지 특정한 조건의 서수열이 그렇다는 이야기는 한 적이 없습니다. 헌데 위에서 언급한 부분집합에 대한 이야기는, 유한 부분집합에 대해 한정되어 있습니다. 그러면 주어진 서수의 무한 부분집합의 경우는 어떨까요?

한 번 대우를 대신 생각해봅시다: 만약 어떤 서수의 부분집합 $X\subseteq \alpha$가 최소원을 갖지 않는다고 합시다. 유한 부분집합의 경우는 최소원을 가지니, $X$는 무한집합이여야 할 것입니다. 이제 $\alpha_0\in X$를 잡읍시다. 만약 $\alpha_0$보다 더 작은 $X$의 원소가 없다면 $\alpha_0$은 $X$의 최소원이겠죠. 하지만 $X$의 최소원이 없다고 생각했으니, $\alpha_1<\alpha_0$인 $\alpha_0\in X$를 고를 수 있을 것입니다. 마찬가지로, $\alpha_2<\alpha_1$인 $\alpha_2\in X$도 고를 수 있고 이런 과정을 반복할 수 있을 것입니다. 이렇게 무한히 감소하는 $X$ 위의 열 $\langle \alpha_n\mid n\in\mathbb{N}\rangle$을 얻었습니다. 그런데 각 $\alpha_n$은 서수이고, 따라서 무한히 감소하는 서수열을 얻었습니다.

하지만 이는 불가능합니다! 따라서 $X$는 최소원을 가져야 합니다. 즉, 모든 서수의 부분집합은 공집합이 아닌 한 최소원을 갖습니다. 참고로, 역도 성립합니다: 서수가 정렬집합이라는 사실로부터, 무한히 감소하는 서수열이 없음을 보일 수도 있습니다. (이는 감소하는 무한 서수열을 하나 잡고, 그 열들의 항으로 이뤄진 집합의 최소원을 잡음으로써 확인할 수 있습니다.) 그리고 사실, 이보다 좀 더 일반적인 사실이 성립합니다:

정리. $(X,<)$이 선형순서집합이라 하자. 그러면 다음 둘은 동치이다:4

  1. $(X,<)$은 정렬집합이다.

  2. $(X,<)$ 위에서 무한 감소열은 존재하지 않는다. 즉, $x_0>x_1>x_2>\cdots$를 만족하는 $x_0,x_1,\cdots X$는 존재하지 않는다.

이제 초한귀납법과 초한재귀에 대해 설명하려고 합니다. 그 전에 좀 더 친숙한 자연수의 귀납법과 재귀적 정의에 대해 봅시다. 이 둘은 자연수 구조의 제일 특징적인 면이기도 합니다.

정리. (귀납법) 만약

  1. $P(0)$이 성립하고

  2. 모든 자연수 $n$에 대해 $P(n)\to P(n+1)$이 성립하면

모든 자연수 $n$에 대해 $P(n)$이 성립한다.

정리. (원시적 재귀, Primitive recursion) $a\in\mathbb{N}$, $g:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$이라 하자. 그러면 어떤 $h:\mathbb{N}\to\mathbb{N}$이 있어

  1. $h(0) = a$,

  2. $h(n+1) = g(h(n),n)$

을 만족한다.

여기서 재귀적 정의를 좀 더 강화하면, 다음과 같은 형태의 정리도 얻을 수 있습니다. (이 부분이 이해가 안 된다면 건너뛰고 바로 서수에 대한 귀납법으로 넘어가도 상관 없습니다.)

정리. (자연수에 대한 재귀) $V$를 모든 집합들의 모임이라 하자. 그리고 $F:V\to V$를 함수라 하자.5 이 때 어떤 함수 $G:\mathbb{N}\to V$가 있어 $G(n) = F(G\upharpoonright n)$을 만족한다.

여기서 $G\upharpoonright n$은 함수 $G$의 정의역을 $n$으로 제한한 것입니다. Jech 같은 교재에서 위의 형태의 재귀 정리를 다룹니다.6 정의의 형태가 왜 이렇게 이상한 지는 초한재귀법을 설명하면서 같이 설명하려고 합니다.

위에서 상술한 귀납법과 재귀적 정의는, 자연수 집합이 정렬되었다는 데에서 따라나옵니다. 재귀적 정의가 가능하단 정리는 증명하려면 조금 고통스럽기 때문에 그렇다고 하고, 귀납법에 대해서만 증명해봅시다:

증명. $P$가 $P(0)$과, 모든 $n$에 대해 $P(n)\to P(n+1)$를 만족한다고 하자. 이제 집합 \[X = \{n\in\mathbb{N} \mid P(n)\} \] 을 생각하자. 우리들은 $X=\mathbb{N}$임을 보일 것이다. 만약 그렇지 않다면, $\mathbb{N}\setminus X$는 공집합이 아니고, 따라서 최소원 $n$을 갖는다. 특히, $n$은 $\lnot P(n)$을 만족한다. 따라서 $n$은 $0$일 수 없다. ($0$은 $P(0)$을 만족하므로.) 만약 $n=m+1$이면, $n$이 $\lnot P(n)$을 민족하는 제일 작은 자연수라는 데서 $P(m)$이 성립해야 한다. (그렇지 않으면 $m$이 $\lnot P(m)$을 만족하는, $n$보다 작은 자연수가 되므로.) 그런데 $P(m)$은 $P(m+1)$을 이끌어내고, 이는 $P(n)$이다. 따라서 $n$은 $0$일 수도 없고 $m+1$꼴일 수도 없다. 이는 모순이다. 따라서 $X=\mathbb{N}$이다.

한편, 자연수에 대한 귀납법은 다음과 같은 형태로도 쓰일 수 있습니다:

정리. (귀납법, 다른 형태) 다음이 성립한다고 가정하자: 모든 자연수 $n$에 대해, $\forall k<n P(k)$가 $P(n)$을 이끌어낸다고 하자. 그러면 모든 자연수 $n$에 대해 $P(n)$이 성립한다.

그리고 서수 역시 정렬순서입니다. 따라서 서수에 대해서도 귀납법과 재귀적 정의가 가능할 것이라 생각해볼 수 있습니다.

정리. (서수 위에서의 귀납법) $\alpha$를 서수라 하자. 그리고 다음이 성립한다고 가정하자: 모든 서수 $\xi<\alpha$에 대해, $\forall \eta<\xi P(\eta)$가 $P(\xi)$을 이끌어낸다고 하자. 그러면 모든 서수 $\xi<\alpha$에 대해 $P(\xi)$가 성립한다.

그리고 위의 귀납법은 모든 서수에 대해서도 일반화될 수 있습니다:

정리. (초한귀납법) 다음이 성립한다고 가정하자: 모든 서수 $\xi$에 대해, $\forall \eta<\xi P(\eta)$가 $P(\xi)$을 이끌어낸다고 하자. 그러면 모든 서수 $\xi$에 대해 $P(\xi)$가 성립한다.

마찬가지로, 재귀적 정의 역시 모든 서수에 대해 일반화할 수 있습니다:

정리. (초한재귀) $V$를 모든 집합들의 모임이라 하자. 그리고 $F:V\to V$를 함수라 하자.5 이 때 어떤 함수 $G:\mathrm{Ord}\to V$가 있어 $G(\alpha) = F(G\upharpoonright \alpha)$을 만족한다.

여기서 $\mathrm{Ord}$는 모든 서수들의 모임(class)입니다. 그런데, 위 정리에서 $G(\alpha) = F(G\upharpoonright \alpha)$가 뜻하는 게 안 보일 수도 있습니다. 이걸 설명하기 전에, 자연수에 대한 재귀적 정의를 다시 한 번 봅시다.

재귀적 정의는, 이전에 등장한 값을 이용해서 새로운 값을 정의하는 과정입니다. 가령, 다음과 같은 정의는 어떤 수열을 재귀적으로 정의하겠죠: \[ a_0 = 1, a_n = a_0+a_1+\cdots + a_{n-1}.\] 조금 일반적인 경우를 적어 보자면, 다음과 같은 형태의 정의는 어떤 수열을 재귀적으로 정의할 것입니다: \[ a_0 = a, a_n = f(a_0,a_1,\cdots, a_{n-1}).\] 그런데, 위의 형태에는 한 가지 문제가 있습니다: $n$에 따라 $f$가 받는 인자의 갯수가 늘어난다는 것입니다. 하지만 분명 $f$는 고정된 정의역을 가진 함수입니다. 이 문제를 해소하기 위해서, $f$가 여러 개의 수를 받는 대신 유한한 길이의 열 $\langle a_0,\cdots, a_{n-1}\rangle$을 인자로 받는다고 생각해봅시다. \[ a_0 = a, a_n = f(\langle a_0,a_1,\cdots, a_{n-1}\rangle).\] 그런데, 유한열 $\langle a_0,a_1,\cdots, a_{n-1}\rangle$을 함수로 생각할 수 있습니다: 보다 정확히는, 정의역이 $n=\{0,1,\cdots,n-1\}$이고 $g(k)=a_k$로 주어지는 함수 $g$로 생각할 수 있습니다. 그런데 여기서, $g$의 정의역을 $n$으로 한정할 이유가 없어 보이지는 않나요? 만약 $g(n)=a_n$으로 정의한다면, $\langle a_0,a_1,\cdots, a_{n-1}\rangle$은 함수 $g$의 정의역을 $n=\{0,1,\cdots,n-1\}$으로 제한한 함수가 될 것입니다. 그리고 위의 정의는 \[ g(0) = a , g(n) = f(g\upharpoonright n).\] 의 형태가 될 것입니다. 여기서 $f(\varnothing)=a$라면7, $g$가 $g(n)=f(g\upharpoonright n)$와 같이 정의된다는 주장을 할 수 있을 것입니다. 위에서 제시한 초한재귀 역시 비슷한 구조로, ‘주어진 서수 인자보다 더 작은 서수에 대한 값을 참조해서’ 함수를 정의한다는 의미로 비슷한 형태의 정의를 따라간다고 이해할 수 있습니다.

하지만, 자연수에 대한 귀납법이나 재귀적 정의는 두 가지 형태가 있습니다. 그리고 우리는 그 중 한 형태 – $\forall k<n P(k)$로부터 $P(n)$을 이끌어내는 형태 – 만 서수에 대한 명제 형태로 바꿨습니다. 나머지 형태 – $P(n)$으로부터 $P(n+1)$을 이끌어내는 것 – 에 대응하는 초한귀납법이나 초한재귀가 있을까요? 무한서수는 자연수와 다르게, 항상 ‘바로 전 서수’라는 게 존재한다는 보장이 없습니다. $\alpha+1$꼴의 서수라면 (따름서수라 부릅니다) $\alpha$가 바로 전 서수가 되겠지만, $\omega$나 $\omega\cdot 2$같은 극한서수는 대응하는 바로 전 서수가 없습니다. 그러면 그 경우에 한해서만, 기존에 취한 귀납법 형태를 따라가봅시다. 그러면 다음과 같은 서수에 대한 초한귀납법을 얻을 수 있습니다:

정리. (초한귀납법, 다른 형태) 다음이 성립한다고 가정하자.

그러면 모든 서수 $\alpha$에 대해 $P(\alpha)$가 성립한다.

초한 재귀 역시 위와 같이 따름서수, 극한서수로 나눠서 다룰 수 있습니다.

정리. (초한 재귀, 다른 형태) 집합 $a$와 함수 $F:V\times V\to V$와 $G:V\to V$가 주어져 있을 때 다음을 만족하는 $H:\mathrm{Ord}\to V$가 존재한다:

이 글을 마무리하기 전에, 서수의 연산에 대해 설명하려고 합니다. 자연수와 마찬가지로, 서수 역시 덧셈, 곱셈, 지수 연산을 지닙니다. 하지만 자연수의 경우와 달리 만족하는 연산 법칙은 판이하게 다릅니다.

위에서 서수에 대한 설명을 할 때 덧셈을 “이어붙이는” 것으로 이해했습니다. 일반적인 서수의 덧셈도 그렇게 정의됩니다. 좀 형식적으로 적으면 다음과 같습니다:

정의. (서수의 덧셈) $\alpha$와 $\beta$가 서수라 하자. 이 때 $\alpha+\beta$는 다음 순서집합 $(X,<)$과 순서동형인 서수로 주어진다:

텍스트로만 적으면 바로 감이 안 올 수도 있지만, 위와 같이 주어진 순서는 $\alpha$ 바로 뒤에 $\beta$를 붙여서 얻어진 순서와 같습니다. 위의 순서집합이 정렬순서임을 보이는 것은 어렵지 않고, 모든 정렬순서는 어떤 서수와 동형이라는 사실이 알려져 있기 때문에8 위의 순서와 동형인 서수가 존재한다고 보장할 수 있습니다.

위의 정의에 따라 서수 덧셈을 하나 계산해봅시다. 처음 서수를 설명할 때, 위의 정의대로 $\omega+\omega$가 무엇인지 설명한 바 있습니다. 가령, 한 번 위 정의에 따라서 $1+\omega$를 계산해봅시다. 우선 $1+\omega$는 다음과 같은 순서집합과 동형인 서수일 것입니다: \[(0,0) < (1,0) < (1,1) < (1,2) < (1,3) < \cdots \] 이를 다시 순서매겨보면, $0<1<2<3<\cdots$가 나옵니다. 이는 $\omega$와 같고, 따라서 $1+\omega=\omega$입니다. 그런데 $\omega+1$은 $\omega$가 아니므로 $1+\omega \neq \omega+1$임을 알 수 있습니다. 즉, 서수에 대한 덧셈의 교환법칙은 성립하지 않습니다.

한편으로, 서수의 덧셈은 초한재귀를 사용해서 정의할 수도 있습니다:

정의. (초한 재귀를 사용한 서수의 덧셈) 서수의 덧셈은 다음과 같이 재귀적으로 주어진다:

초한귀납법을 사용하면 이전에 소개한 정의와 초한재귀를 사용한 정의가 같은 함수라는 사실을 보일 수 있습니다.

이제 덧셈을 정의했으니 곱셈을 정의해봅시다. 곱셈은 사전식 순서를 이용해서 정의합니다.9

정의. (서수의 곱셈) $\alpha$와 $\beta$가 서수라 하자. 이 때 $\alpha\cdot\beta$는 다음 순서집합 $(X,<)$과 순서동형인 서수로 주어진다:

역시, 위 정의를 이용해서 곱셈을 계산해보는 것이 이해에 도움이 될 수 있습니다. 가령, $2\cdot \omega$를 계산해봅시다. $2\cdot\omega$는 다음과 같은 순서집합의 순서형입니다:

\[(0,0) < (0,1) < (1,0) < (1,1) < (2,0) < (2,1) < \cdots \]

이 역시 $\omega$의 순서형이고, 따라서 $2\cdot\omega=\omega$입니다. 하지만 $\omega\cdot 2\neq \omega$이고, 따라서 $\omega\cdot 2\neq2\cdot\omega$입니다. 즉, 서수의 곱셈 또한 교환법칙을 만족시키지 않습니다.

서수의 곱셈 역시 초한재귀를 이용해서 정의할 수 있습니다:

정의. (초한 재귀를 사용한 서수의 곱셈) 서수의 곱셈은 다음과 같이 재귀적으로 주어진다:

지수 연산의 경우에도 덧셈과 곱셈처럼 순서형을 조작하는 식으로 줄 수 있습니다. 하지만 덧셈이나 곱셈과 달리, 뭔가 특별한 통찰을 주는 형태의 정의가 아닙니다.10 지수 연산의 경우에는 다음과 같이 재귀적으로 정의하는 편이 더 낫습니다:

정의. (서수의 지수 연산) 서수의 지수 연산은 다음과 같이 재귀적으로 주어진다:

이제 서수 연산들의 성질을 알아봅시다. 우선, 다음이 성립한단 것이 알려져 있습니다:

정리. 다음이 성립한다:

  1. (덧셈의 결합법칙) $(\alpha+\beta)+\gamma = \alpha+(\beta+\gamma)$

  2. (덧셈의 좌소거법칙) $\alpha+\beta=\alpha+\gamma$이면 $\beta=\gamma$이다.

  3. (곱셈의 결합법칙) $(\alpha\cdot\beta)\cdot\gamma = \alpha\cdot(\beta\cdot\gamma)$

  4. (곱셈의 좌소거법칙) $\alpha\ge 1$이고 $\alpha\cdot\beta=\alpha\cdot\gamma$이면 $\beta=\gamma$이다.

  5. (좌분배법칙) $\alpha\cdot(\beta+\gamma) = (\alpha\cdot\beta) + (\alpha\cdot\gamma)$

  6. (지수 연산의 밑 소거법칙) $\alpha\ge 2$이고 $\alpha^\beta=\alpha^\gamma$이면 $\beta=\gamma$이다.

  7. $\alpha^{\beta+\gamma} = \alpha^\beta\cdot\alpha^\gamma$

  8. $\alpha^{\beta\cdot\gamma} = (\alpha^\beta)^\gamma$

  9. $\gamma\le\alpha$일 때 어떤 $\rho<\beta$와 $\delta$가 있어 $\alpha=\gamma\cdot\gamma+\rho$이다.

정리. 다음이 성립한다: $\alpha<\beta$일 때

  1. $\alpha+\gamma < \beta+\gamma$,

  2. $\alpha\cdot\gamma < \beta\cdot\gamma$,

  3. $\gamma^\alpha < \gamma^\beta$.

또한, 다음이 성립한다: $\alpha\le\beta$일 때

  1. $\gamma+\alpha \le \gamma+\beta$,

  2. $\gamma\cdot\alpha \le \gamma\cdot\beta$,

  3. $\alpha^\gamma \le \beta^\gamma$.

하지만, 위에 적힌 것들 외에는 꼭 성립한단 보장이 없습니다. 위에서 봤듯이 교환법칙은 성립하지 않고, 덧셈의 우소거법칙도 성립하지 않습니다: 가령, $0+\omega=1+\omega=\omega$이지만 $0=1$은 아닙니다.

서수 자체에 대해서 할 이야기는 아직도 많이 남아 있지만, 이 정도면 서수에 대한 기초적인 설명은 다 했다고 생각합니다. 다음 글에서는 기수와 알레프 수에 대해서 이야기해보려고 합니다.

  1. 실제로 저 단어를 꺼내지는 않았지만, 가끔은 현실과 다른 기술을 하는 게 의도를 더 분명히 전달할 때가 있습니다. ↩

  2. 나머지 하나는 기술집합론(descriptive set theory)에 영향을 크게 줬을 일반위상과 측도론일 것 같습니다. 하지만 기술집합론에서도 서수가 안 나온다는 것은 아닙니다. 논리학 전반에서, 무한서수와 무한기수, 혹은 그와 유사한 개념의 등장은 불가피한 것 같습니다. ↩

  3. $0$은 자연수입니다. 반복하자면, $0$은 자연수입니다. $0$이 다른 자연수보다 늦게 발견(혹은 발명)되었으므로 $0$이 자연수가 아니라는 주장은, 구골플렉스나 $\operatorname{TREE}(3)$ 같은 자연수는 역사상 더 늦게 등장했단 것으로 반박할 수 있습니다. ↩

  4. 참고로, 이 둘이 동치라는 증명은 선택공리를 사용합니다. ↩

  5. 여기서 $F$는 집합일 수 없습니다. 따라서 “함수”라는 단어를, 특정한 조건을 만족하는 집합으로 보아서는 안 됩니다. 차라리, 함수의 정의 – 순서쌍의 모임 중 $(x,y),(x,z)\in f$일 때 $y=z$인 $f$ – 를 만족하는 진모임(proper class), 혹은 $P(x,y)$이고 $P(x,z)$일 때 $y=z$를 만족하는 논리식 $P$로 이해해야 할 것입니다. ↩ ↩2

  6. Jech/Hrbacek의 경우에는 $F$의 정의역이 $V$ 대신 어떤 집합 위의 유한한 열들의 집합이라는 차이는 있습니다. 하지만 큰 차이는 아닙니다. ↩

  7. 여기서 공집합은 $g$를 $0=\varnothing$ 위로 제한해서 나타난 것입니다. ↩

  8. 사실 서수라는 개념을 처음 도입하게 된 제일 큰 동기이기도 합니다. 서수는 정렬순서의 순서를 대표하는 집합이며, 칸토어는 서수를 정렬집합들의 모임을 동형관계에 대해 나눈 동치류로 보았습니다. ↩

  9. 사전에서 단어를 찾을 때, 첫 문자의 알파벳 순서에 따라 먼저 찾은 후 그 다음 문자의 알파벳 순서에 따라 단어를 찾습니다. ↩

  10. 그럼에도 궁금해 할 분이 있을까봐, 지수 연산의 다른 정의를 소개합니다: $\alpha$와 $\beta$가 서수일 때 $\alpha^\beta$는 다음과 같이 주어지는 순서집합 $(X,<)$와 순서동형입니다: $X=\{f:\beta\to\alpha \mid f(\xi)=0 \text{ for all but finitely many }\xi\in\beta\}$이고, $f<g$일 필요충분조건은 $f$가 $g$가 사전식 순서 하에 작은 것이다. 즉, $\xi=\min\{\eta\in\beta\mid f(\eta)\neq g(\eta)\}$에 대해 $f(\eta)<g(\eta)$인 것이다. ↩