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\)가 존재한다. ↩

댓글남기기