K

Grad. student in mathematics

Introduction

서수가 무엇인지를 알기 위해서는 자연수를 정의하는 다음의 페아노 공리계를 살펴보는 것이 도움이 된다.

Peano Axioms. 자연수 집합 $\mathbb{N}$과, 이 집합 위에 정의된 successor function $S$는 다음의 공리들을 만족하는 대상들이다.

  1. $0$은 자연수이다.
  2. 임의의 자연수 $n$에 대하여, $S(n)$ 또한 자연수이다.
  3. $S$는 단사함수다.
  4. $S(n)=0$을 만족하는 자연수 $n$은 존재하지 않는다.
  5. 만일, $0$을 포함하는 또 다른 집합 $K$가 $S$에 대하여 닫혀있다면, $K$는 $\mathbb{N}$을 포함한다.

우리가 흔히 사용하는 수학적 귀납법은 사실 위의 공리로부터 얻어지는 명제가 된다. 일반적인 집합론 교재, 예를 들어 우리가 ZFC 공리계 및 순서쌍을 정의할 때 사용했었던 [HJJ] 같은 경우에는 이 시점에서, 다음의 recursion theorem을 이용해서 자연수의 연산을 정의한다.

정리 1 (The recursion theorem) 집합 $A$가 주어졌다 하자. 이 집합의 원소 $a\in A$와 임의의 함수 $g:A\times \mathbb{N}\rightarrow A$에 대하여, 다음의 조건

  1. $f_0=a$,
  2. 모든 $n\in\mathbb{N}$에 대하여 $f_{n+1}=g(f_n,n)$

을 만족하는 유일한 무한수열 $f:\mathbb{N}\rightarrow A$이 존재한다.

증명

증명의 아이디어만 간략하게 소개한다. $m$-step computation을 다음의 조건

\[t_0=a,\quad t_{k+1}=g(t_k,k)\text{ for all }k< m\]

을 만족하는 유한수열 $t:\left\{1,2,\cdots,m\right\}\rightarrow A$로 정의하자. 그럼 $t$는 $\mathbb{N}\times A$의 부분집합임이 자명하다. 이제 다음의 집합

\[\mathfrak{F}=\left\{t\in\mathcal{P}(A)\mid t\text{ is an }m\text{-step computation for some natural number }m\right\}\]

에 대하여 $F=\bigcup\mathfrak{F}$라 하자. 그럼

  1. 임의의 $m,n$에 대하여 $m$-step computation과 $n$-step computation이 compatible하다는 것을 보일 수 있고, 이를 통해 $f$가 함수라는 것을 보인다.
  2. 이후 $\pr_1F=\mathbb{N}$, $\pr_2F\subseteq A$임을 보인다. 이 과정에서 귀납법을 사용해야 한다.
  3. 2번에 의하여 $f=(F,\mathbb{N},A)$가 함수임을 알고 있으므로, 이 함수가 주어진 두 조건을 만족함을 보이면 된다.
  4. 마지막으로 유일성의 경우, 어떤 $h:\mathbb{N}\rightarrow A$가 정리의 조건을 만족한다 가정한 후 $f_n=h_n$이 모든 $n$에 대해 성립함을 귀납법을 사용하여 보이면 된다.

우리가 다루던 공리계 안에서는 자연수 집합, 더 일반적으로는 무한집합의 존재성을 보일 방법이 없기 때문에, 다음의 공리를 도입해야 한다.

The Axiom of infinity $0$을 포함하며, successor function에 대해 닫혀있는 집합 $I$가 존재한다.

자연수와 서수

노이만은 위의 페아노 공리계를 만족하는 자연수 $\mathbb{N}$의 특정한 모델을 제시했는데, 이것이 서수를 정의할 때 좋은 motivation이 되므로 우선 소개한다. 노이만의 아이디어는 자연수 $n$을 원소 $n$개짜리 집합으로 정의하는 것이다. 그럼 0은 유일하게 정의될 수밖에 없다.

\[0=\emptyset.\]

그 후에, $1$을 정의하기 위해서 우리는 원소 하나짜리 집합을 만들어야 한다. 그런데, 우리가 갖고 있는 집합은 현재로선 $\emptyset$밖에 없으니, $1$을 정의할 합리적인 방법 또한 하나 뿐이다.

\[1=\{\emptyset\}.\]

그 후 우리는 $2$를 다음의 식

\[2=\{0,1\}=\big\{\emptyset,\{\emptyset\}\big\}\]

으로 정의하고, 같은 방법으로 $3=\{0,1,2\}$ 등과 같이 정의한다. 이러한 모델에서, $S$는 다음의 함수

\[S(x)=x\cup\{x\}\]

으로 정의된다는 것을 쉽게 확인할 수 있다. 정의에 의해 $m<n$인 것은 $m\in n$인 것과 동치이다. 우선은 이 과정을 반복하여 자연수 집합을 얻는다. 자연수 집합을 이와 같이 서수로 취급할 때에는 $\omega$로 적는다.

그러나 위의 과정은 $\omega$를 얻었다고 하여 끝나는 것이 아니다. 가령

\[S(\omega)=\{0,1,2,\ldots,\omega\}\]

는 기존의 어떤 집합들과도 다르다.1 이를 $\omega+1$이라 하자. 이런 방식으로 $S$를 거듭하여 적용하면

\[S(\omega)=\omega+1,\qquad S(\omega+1)=\omega+2, \ldots\]

를 얻고, 이를 계속 반복하다보면 다시

\[\omega+1,\omega+2, \ldots, \omega+\omega:=\omega\cdot 2\]

를 얻는다. 이를 다시 반복하면, $\omega\cdot 2, \omega\cdot 2+1, \ldots, \omega\cdot 3, \ldots, $ 그리고 다시 이를 반복하면 마침내 $\omega\cdot\omega=\omega^2$마저도 얻을 것이며, 이를 또 다시 반복하여 $\omega^3, \ldots, \omega^\omega$, 그 다음엔 $\omega^{\omega^{\omega}}, \ldots$, 물론 이 과정이 끝났을 때 이 집합에 새롭게 기호를 준다면 또 같은 일을 반복할 수도 있다.

정렬집합

위의 논의는 직관적이지만 정의로 받아들이기엔 충분히 엄밀하지 않다.

정의 2 집합 $A$ 위에서 정의된 totally ordered set $R$이 well-ordering정렬순서이라는 것은 공집합이 아닌 $A$의 임의의 부분집합 $X$가 least element를 갖는 것이다.

예시 3 $\mathbb{N}$은 well-ordered set이지만, $\mathbb{R}$은 그렇지 않다.

집합 전체가 least element를 갖는 것은 집합이 well-ordered이기 위한 충분조건이 아니다. 예컨대 $\mathbb{R}^{\geq 0}$은 least element $0$을 갖지만, 그의 부분집합 $\mathbb{R}^{>0}$은 least element를 갖지 않는다. 또, $\mathbb{Z}$는 well-ordered가 아니므로, 집합의 크기 또한 여기에 영향을 미치지 않는다.

정의 4 $(A,\leq)$가 ordered set이라 하자. $A$의 부분집합 $S$가 다음의 조건

만약 $x\in S$, $y\in A$이고 $y\leq x$라면, $y\in S$이다.

을 만족한다면 이를 $A$의 initial segment라 부른다.

대부분의 경우, initial segment를 간단히 segment로 줄여 쓰기도 한다.

명제 5 $(A,\leq)$가 well-ordered set이라 하자. $A$ 자기 자신을 제외한 $A$의 모든 segment는 어떠한 $a\in A$에 대하여 $(-\infty, a)$의 꼴이다.

증명

$S\neq A$가 임의의 segment라 하자. 집합 $A$가 well-ordered이므로, $A\setminus S$ 또한 least element를 갖는다. 이를 $a$라 하자. 정의에 의해 $A\setminus S$의 모든 원소는 $a$보다 크거나 같으므로, $A\setminus S$는 $[a,\infty)$의 부분집합이다.

이제, $A\setminus S$가 정확히 $[a,\infty)$라는 것만 보이면, $S=(-\infty, a)$가 될 것이므로 증명이 끝난다. 결론에 반하여, 어떤 $x\in [a,\infty)$가 $A\setminus S$의 원소가 아니라 가정하자. 즉, $x$는 $a\leq x$, 그리고 $x\in S$를 동시에 만족하는 원소이다. 그런데, $S$는 segment이므로 $a\leq x$라는 것은 $a\in S$를 함의하고, 이는 $a$가 $A\setminus S$의 least element라는 가정에 모순이므로 $x\not\in S$여야 한다. 따라서, $A\setminus S$는 정확히 $[a,\infty)$이고 증명이 끝난다.

참고 위의 명제는 집합 $(-\infty, a]$가 $A$의 segment가 될 수 없다고 말하는 것이 아니다. 이 정리는 만약 $(-\infty, a]$가 $A$의 segment라 한다면, 이 집합은 어떤 $a’\in A$에 대하여 $(-\infty, a’)$의 꼴로도 쓰여질 수 있음을 의미한다.

예를 들어, $\mathbb{N}$에서 $(-\infty, 3]$이라는 집합은 정의상 $\{0,1,2,3\}$이다. 앞선 명제는 이 집합이 segment가 아니라는 뜻이 아니라, 이 집합을 $(-\infty, 4)$로도 쓸 수 있다는 뜻이다.

당연히 이는 이는 일반적인 ordered set에서는 참일 필요가 없다. 예컨대 $\mathbb{R}$은 well-ordered가 아니며, 이의 segment $(-\infty, a]$는 $(-\infty, a’)$와 같은 꼴로 쓰여질 수 없다.

어쨌건, 집합 $(-\infty, a)$는 항상 ordered set의 segment가 된다. 이 집합을 $a$를 끝점으로 하는 segment라 부르고 $S_a$로 적는다. 임의의 ordered set $A$에 대하여, 다음이 성립한다.

\[\bigcup_{a\in A}S_a=\begin{cases}A&\text{if there is no greatest element of $A$}\\ A\setminus\{b\}&\text{if }b\text{ is the greatest element of $A$}\end{cases}.\]

그러나 어떠한 경우에도 $(-\infty, a)$ 꼴의 segment는 $a$를 포함하지 않으므로, 이런 꼴을 갖는 $A$의 segment가 $A$ 자기자신이 될 수는 없다.

참고문헌

[HJJ] K. Hrbacek, T.J. Jeck, and T. Jech. Introduction to Set Theory. Lecture Notes in Pure and Applied Mathematics. M. Dekker, 1978.
[Bou] N. Bourbaki, Theory of Sets. Elements of mathematics. Springer Berlin-Heidelberg, 2013.

  1. 물론 이 집합은 $\mathbb{N}$에 단 하나의 원소만을 추가한 집합이므로 $\mathbb{N}$과 같은 크기를 갖는다. 하지만 순서집합으로서, 자연수집합은 maximal element가 존재하지 않지만 이 집합은 maximal element $\omega$가 존재한다. ↩

댓글남기기