집합의 서수

기수가 집합의 ‘크기’를 나타낸다면, 서수(ordinal number)는 정렬된 집합의 ‘순서 유형’을 나타낸다. 6장에서 자연수를 폰 노이만 방식을 사용하여 구성하고, 7장에서 집합의 크기를 기수로 나타내었다. 이 장에서는 정렬집합과 서수의 개념을 도입하고, 서수의 순서와 연산, 초한귀납법을 살펴본다.

1. 정렬순서와 정렬집합

정렬집합의 대표적인 예는 다음과 같다.

• 자연수 집합 \(\mathbb N\)은 6장에서 정의한 순서가 주어졌을 때 정렬집합이다.
• 실수 집합 \(\mathbb R\)은 통상적인 순서가 주어졌을 때 정렬집합이 아니다. 예를 들어 \((0,1)\)은 최소원소를 갖지 않는다.
• 전순서가 주어진 유한집합은 항상 정렬집합이다.

무한집합에도 여러 가지 순서를 부여할 수 있다. 예를 들어, \(\mathbb Z\)에 \[0<1<-1<2<-2<3<-3<\cdots\] 라는 순서를 주면 정렬집합이 된다.

순서동형인 정렬집합들은 같은 순서구조를 가진다. 예를 들어, \[a_1

정렬집합 \((A,\leq)\)와 \(a\in A\)에 대하여 \[A_a=\{x\in A\mid x절편(initial segment)이라고 부른다. 이 책에서 절편이라 하면 이와 같은 진절편을 뜻한다.

상한과 하한은 주어진 순서집합 안에 존재하지 않을 수도 있다. 예를 들어 \((0,1)\cap\mathbb Q\)를 \(\mathbb Q\)의 부분집합으로 볼 때 상한은 \(1\)이므로 존재하지만, \(\{q\in\mathbb Q\mid q^2<2\}\)는 \(\mathbb Q\) 안에서 상한을 갖지 않는다.

2. 서수의 정의

집합 \(T\)가 \(x\in y\in T\)일 때마다 \(x\in T\)를 만족시키면 \(T\)를 추이적 집합(transitive set)이라고 부른다. 6장에서 자연수는 이러한 성질을 갖는다는 것을 보았다.

자연수의 폰 노이만 구성과 6장의 자연수 순서 정리에 의해 모든 자연수는 서수이다. 특히 \[ 0=\varnothing,\quad1=\{0\},\quad2=\{0,1\},\quad3=\{0,1,2\},\quad\ldots \] 이고, 가장 작은 무한서수는 \[\omega=\mathbb N=\{0,1,2,3,\ldots\}\] 이다.

이 정리는 서수가 정렬집합의 순서 유형을 나타낸다는 것을 엄밀하게 표현한다. 증명의 핵심은 초한재귀이며, 이 장의 마지막 절에서 설명한다.

3. 서수의 순서

서수 \(\alpha\), \(\beta\)에 대하여 \[\alpha<\beta\quad\Longleftrightarrow\quad\alpha\in\beta\] 로 정의한다. 또한 \(\alpha\leq\beta\)는 \(\alpha<\beta\)이거나 \(\alpha=\beta\)라는 뜻이다.

따라서 서수의 순서는 \[0<1<2<3<\cdots<\omega<\omega+1<\omega+2<\cdots<\omega\cdot2<\cdots\] 처럼 계속 이어진다. 여기서 \(+\)와 \(\cdot\)은 뒤에서 정의할 서수의 연산이다.

서수들의 집합에서는 상한이 항상 존재한다.

4. 초한귀납법과 초한재귀

서수 \(\alpha\)의 따름서수(successor ordinal)를 \[S(\alpha)=\alpha\cup\{\alpha\}\] 로 정의한다. \(0\)이 아니면서 어떤 서수의 따름서수도 아닌 서수를 극한서수(limit ordinal)라고 부른다. 극한서수는 최대원소를 갖지 않는다. 가장 작은 무한 극한서수는 \(\omega\)이다.

초한귀납법은 흔히 다음 세 단계로 나누어 사용한다. \(P(0)\)을 보이고, \(P(\alpha)\)에서 \(P(S(\alpha))\)를 보이며, 극한서수 \(\lambda\)에 대해서는 모든 \(\beta<\lambda\)에서 \(P(\beta)\)가 성립한다고 가정하여 \(P(\lambda)\)를 보인다.

초한귀납법에 대응하는 정의 원리를 초한재귀(transfinite recursion)라고 부른다.

이 정리의 완전한 집합론적 진술과 증명에는 치환 공리 등의 집합 존재 원리가 필요하므로 여기서는 증명 없이 사용한다. 아래의 서수 덧셈, 곱셈, 거듭제곱은 순서 유형 또는 초한재귀를 이용하여 정의한다.

5. 서수의 덧셈

서수의 덧셈은 두 정렬집합을 차례로 이어 붙이는 연산이다.

대표 정렬집합을 순서동형인 다른 정렬집합으로 바꾸어도 두 복사본에 성분별 순서동형을 적용하면 같은 순서 유형을 얻으므로 이 정의는 대표원의 선택과 무관하다.

예를 들면 \[2+3=5,\quad1+\omega=\omega\] 이고, \(\omega+1\)은 자연수들을 모두 놓은 뒤 마지막에 새 원소 하나를 붙인 순서 유형이다. 따라서 \[1+\omega=\omega<\omega+1\] 이므로 서수의 덧셈은 일반적으로 교환법칙을 만족시키지 않는다.

공통된 왼쪽 항은 소거할 수 있지만 공통된 오른쪽 항은 일반적으로 소거할 수 없다. 실제로 \[1+\omega=2+\omega=\omega\] 이다.

6. 서수의 곱셈

서수의 곱셈은 같은 순서 유형의 블록을 차례로 놓는 연산이다.

따라서 \(\alpha\cdot\beta\)는 \(\alpha\)형의 블록을 \(\beta\)의 순서대로 늘어놓은 순서 유형이다. 예를 들어 \[2\cdot3=6,\quad2\cdot\omega=\omega\] 이고, \(\omega\cdot2\)는 자연수형의 블록 두 개를 차례로 놓은 순서 유형이므로 \[2\cdot\omega=\omega<\omega\cdot2\] 이다.

오른쪽 분배법칙과 교환법칙은 일반적으로 성립하지 않는다. 예를 들어 \[(1+1)\cdot\omega=2\cdot\omega=\omega\] 이지만 \[1\cdot\omega+1\cdot\omega=\omega+\omega=\omega\cdot2\] 이므로 오른쪽 분배법칙이 실패한다.

7. 서수의 거듭제곱

서수의 거듭제곱은 초한재귀로 정의한다.

따라서 \(0^0=1\)이고 \(\beta>0\)이면 \(0^\beta=0\)이다. 또한 정리 8.10에 의해 극한 단계의 상한은 항상 존재한다.

예를 들어 \[2^\omega=\sup_{n<\omega}2^n=\omega\] 이고, \[\omega^\omega=\sup_{n<\omega}\omega^n\] 이다. 따라서 \(\omega^\omega\)는 모든 \(\omega^n\)보다 큰 가산서수이다.

여기서 서수의 거듭제곱과 7장의 기수 거듭제곱을 구별해야 한다. 같은 기호를 사용하지만 서로 다른 연산이다. 예를 들어 \[2^\omega=\omega\quad\text{(서수 연산)}\] 인 반면 \[2^{\aleph_0}=\mathfrak c\quad\text{(기수 연산)}\] 이다. 마찬가지로 서수 \(\omega^\omega\)는 가산이지만 기수 \(\aleph_0^{\aleph_0}\)은 \(\mathfrak c\)이다.

8. 서수와 기수의 관계

서수 \(\kappa\)가 자기보다 작은 어떤 서수와도 대등하지 않으면 \(\kappa\)를 초기서수(initial ordinal)라고 부른다. 기수서수(cardinal ordinal)라고도 한다. 초기서수는 같은 크기를 갖는 서수들 가운데 가장 작은 서수이다.

이 정리의 존재 부분은 9장의 초기서수 존재 정리에서 증명한다. 선택공리를 가정하지 않는 ZF에서는 정렬 가능하지 않은 집합이 있을 수 있으므로, 모든 기수를 서수로 대표할 수 있다고 말해서는 안 된다.

유한 초기서수는 \(0,1,2,\ldots\)이고, 가장 작은 무한 초기서수는 \(\omega\)이다. 무한 초기서수를 차례로 \[\omega_0,\omega_1,\omega_2,\ldots\] 및 초한 첨자로 계속 나타내고, 그 기수를 \[\aleph_\alpha=|\omega_\alpha|\] 로 나타낸다. 특히 \[\omega_0=\omega,\quad\aleph_0=|\omega|\] 이고, \(\omega_1\)은 가장 작은 비가산서수이며 \[\aleph_1=|\omega_1|\] 이다. 이 알레프 계층의 일반적인 존재와 구성은 공리적 집합론의 도구를 필요로 한다.

한편 \(\omega+1\), \(\omega\cdot2\), \(\omega^2\), \(\omega^\omega\)는 서로 다른 서수이지만 모두 가산이므로 기수는 \(\aleph_0\)이다. 즉 기수는 크기만 구별하지만 서수는 순서 유형까지 구별한다. 선택공리 아래에서 7장의 연속체 가설은 \[2^{\aleph_0}=\aleph_1\] 로 나타낼 수 있다.

9. 서수와 관련된 역설

모든 서수의 모임을 \(\mathrm{Ord}\)라고 하자. \(\mathrm{Ord}\)가 집합이라고 가정하면, 모든 서수의 원소는 다시 서수이고 서수들은 \(\in\)에 의하여 정렬되므로 \(\mathrm{Ord}\) 자체도 서수가 된다. 그러면 서수 전체의 모임이라는 정의에 의해 \[\mathrm{Ord}\in\mathrm{Ord}\] 이어야 하는데, 이는 정리 8.5(2)에 모순이다. 이를 부랄리-포르티의 역설(Burali–Forti paradox)이라고 부른다.

따라서 모든 서수의 모임은 집합이 아니라 고유클래스(proper class)이다. 9장에서 다룰 공리적 집합론에서는 “모든 서수의 집합”을 만들 수 없으며, 이러한 구분이 역설을 막는다.

10. 서수의 집합론적 구성

앞에서는 폰 노이만 서수를 정의하고 정리 8.6을 사용하였다. 이제 이 정리의 핵심 구성을 살펴보자. 정렬집합 \((A,<)\)에 대하여 초한재귀로 \[F(a)=\{F(x)\mid x

초한귀납법을 사용하면 각 \(F(a)\)가 서수이고 \[x

유일성을 보이기 위하여 두 서수 \(\alpha\), \(\beta\) 사이에 순서동형 \(f\)가 있다고 하자. 초한귀납법을 사용하여 \[f(\gamma)=\gamma\quad(\gamma\in\alpha)\] 임을 보일 수 있다. 실제로 모든 \(\delta<\gamma\)에서 \(f(\delta)=\delta\)라고 가정하면 순서동형은 절편을 절편으로 보내므로 \[f(\gamma)=\{f(\delta)\mid\delta<\gamma\}=\{\delta\mid\delta<\gamma\}=\gamma\] 이다. 따라서 \(f\)는 항등함수이고 \(\alpha=\beta\)이다.

이 구성의 엄밀한 집합론적 정당화에는 9장에서 다룰 치환 공리꼴 등이 사용된다. 또한 \(\omega\)와 같은 무한서수의 존재에는 무한 공리가 필요하다.