기수가 집합의 '크기'를 나타낸다면, 서수(ordinal number)는 집합의 원소들의 '순서'까지 고려한 개념이다. 이 장에서는 정렬집합과 서수의 개념을 도입하고, 서수의 연산과 초한귀납법을 살펴본다.
1. 정렬순서와 정렬집합
집합 \(A\) 위의 순서관계 \(\leq\)가 다음 조건을 만족할 때 이 순서관계를 정렬순서(well-ordering)라고 부른다.
- \(\le\)는 전순서이다. 즉, 임의의 \(a,\, b \in A\)에 대하여 \(a \leq b\)이거나 \(b \leq a\)이다.
- \(A\)의 공집합이 아닌 모든 부분집합이 최소원소를 가진다.
정렬순서를 갖는 집합을 정렬집합(well-ordered set)이라고 부른다. 정렬집합의 대표적인 예는 다음과 같은 것들이 있다.
- 자연수 집합 \(\mathbb{N}\)은 통상적인 순서가 주어졌을 때 정렬집합이다.
- 실수 집합 \(\mathbb{R}\)은 통상적인 순서가 주어졌을 때 정렬집합이 아니다. (예를 들어, 열린구간 \((0,\, 1)\)은 최소원소가 없다.)
- 전순서가 주어진 유한집합은 항상 정렬집합이다.
무한집합에는 여러 가지 정렬순서를 부여할 수 있다. 예를 들어, \(\mathbb{Z}\)에 다음과 같은 순서를 정의하면 정렬집합이 된다. \[0 < 1 < -1 < 2 < -2 < 3 < -3 < \cdots\]
순서관계 \(\le\)가 주어진 집합 \(A\)를 순서집합이라고 부르고 \(\left( A ,\, \le \right)\)와 같이 나타낸다. 두 순서집합 \((A,\, \leq_A)\)와 \((B,\, \leq_B)\)가 순서동형(order isomorphic)이라는 것은 순서를 보존하는 일대일대응 \(f: A \to B\)가 존재한다는 의미이다. 즉 임의의 \(a_1 ,\, a_2 \in A\)에 대하여 \[a_1 \leq_A a_2 \quad \Longleftrightarrow \quad f(a_1) \leq_B f(a_2)\] 를 만족시키는 일대일대응 \(f:A \to B\)가 존재함을 의미한다. 순서동형인 정렬집합들은 본질적으로 같은 순서구조를 가진다. 예를 들어, 순서관계 \[a_1 < a_2 < \cdots < a_n \] 이 주어진 순서집합 \(\{a_1,\, a_2,\, a_3,\, \ldots,\, a_n\}\)은 통상적인 순서가 주어진 집합 \(\{1,\, 2,\, 3,\, \ldots,\, n\}\)과 순서동형이다.
정렬집합 \((A,\, \leq)\)와 원소 \(a \in A\)에 대하여, 절편(initial segment) \(A_a\)를 다음과 같이 정의한다. \[A_a = \{x \in A \mid x < a\}\]
두 정렬집합 \(A\)와 \(B\)에 대하여, 다음 중 정확히 하나가 성립한다.
- \(A\)와 \(B\)가 순서동형이다.
- \(A\)가 \(B\)의 어떤 절편과 순서동형이다.
- \(B\)가 \(A\)의 어떤 절편과 순서동형이다.
즉 정렬집합 사이에 자연스러운 비교 관계가 존재한다.
문제 8.1. 순서집합에서 '상계', '상한', '하계', '하한'의 개념을 조사해 보자.
문제 8.2. 수학에서 '동형'의 개념을 조사하고, 일반적인 '동형'의 개념과 '순서동형'의 개념의 관계를 서술하시오.
2. 서수의 정의
서수(ordinal number)는 순서동형인 정렬집합들이 공통으로 갖는 '순서 유형'을 나타내는 개념이다. 서수를 엄밀하게 다루기 위하여 다음과 같은 서수 공리를 도입한다.
모든 원소가 정렬집합으로 이루어진 서수의 모임 \(ORD\)가 존재하여, 다음 두 조건을 모두 만족시킨다.
- (O1) 임의의 정렬집합 \(A\)에 대하여 \(A\)와 순서동형인 \(\alpha\in ORD\)가 존재한다. 이때 \(\alpha\)를 \(A\)의 서수라고 부르고, \(\operatorname{ord}(A)\)로 나타낸다.
- (O2) 두 정렬집합 \(A\)와 \(B\)가 순서동형일 필요충분조건은 \(\operatorname{ord}(A) = \operatorname{ord}(B)\)이다.
유한 정렬집합의 서수는 자연수이다.
- \(\text{ord}(\varnothing) = 0\)
- \(\text{ord}(\{a\}) = 1\)
- \(\text{ord}(\{a < b\}) = 2\)
- 일반적으로 \(n\)개 원소를 가진 정렬집합의 서수는 \(n\)이다.
무한 정렬집합의 서수를 초한서수(transfinite ordinal)라고 부른다. 가장 작은 초한서수는 \(\omega\)로, 통상적인 순서가 주어진 자연수 집합의 서수이다. \[\omega = \text{ord}(\mathbb{N}) = \text{ord}(\{0 < 1 < 2 < 3 < \cdots\})\]
3. 서수의 순서
서수들 사이에는 자연스러운 순서가 있다. 서수 \(\alpha\)와 \(\beta\)에 대하여, \(\alpha < \beta\)라는 것은 서수 \(\alpha\)를 갖는 정렬집합이 서수 \(\beta\)를 갖는 정렬집합의 절편과 순서동형이라는 의미이다.
서수의 순서는 다음과 같다. \[0 < 1 < 2 < 3 < \cdots < \omega < \omega + 1 < \omega + 2 < \cdots < \omega \cdot 2 < \cdots\] 여기서 주목할 점은 \(\omega\) 다음에도 서수가 계속 존재한다는 것이다. 또한 서수로 이루어지고 공집합이 아닌 집합을 생각하면, 그 집합에는 반드시 가장 작은 서수가 존재한다. 즉 서수의 크기를 비교하는 순서 관계는 정렬순서이다.
4. 초한귀납법
6장에서 다룬 수학적 귀납법을 서수로 확장한 것이 초한귀납법(transfinite induction)이다. 초한귀납법을 진술하기 위해서는 직전원소(immediate predecessor)와 극원소(limit element)의 개념이 필요하다.
\(A\)가 정렬집합이고 \(x \in A\)라고 하자. \(A\)의 원소 중 \(x\)보다 큰 것들의 집합이 최소원소를 가질 때 그 최소원소를 \(x\)의 직후원소(immediate successor) 또는 따름수라고 부른다. 만약 \(y\)가 \(x\)의 직후원소이면, \(x\)를 \(y\)의 직전원소라고 부른다.
정렬집합의 원소 중에서는 직전원소를 갖지 않는 것이 존재한다. 예를 들어, 자연수를 홀수부터 다 나열한 뒤 짝수를 배열하는 다음과 같은 순서를 생각하자. \[1 < 3 < 5 < 7 < \cdots < 0 < 2 < 4 < 6 \cdots \] 여기서 모든 원소는 직후원소를 가진다. 하지만 \(0\)은 직전원소를 갖지 않는다. 이와 같이 정렬집합에서 최소원소가 아니면서 직전원소를 갖지 않는 원소를 극원소라고 부른다.
서수를 크기 순으로 나열했을 때 직전원소를 갖지 않는 서수를 극서수(limit ordinal)라고 부른다. 예를 들어, \(\omega\)는 가장 작은 무한 극서수이다.
초한귀납법은 다음과 같다.
정렬집합 \(A\)의 원소에 대한 명제 \(p(x)\)가 다음 조건을 만족시키면, 모든 \(x \in A\)에 대해 \(p(x)\)가 성립한다.
"임의의 \(x \in A\)에 대하여, \(x\)보다 작은 모든 원소에 대하여 \(p\)가 성립하면 \(p(x)\)도 성립한다."
초한귀납법은 증명할 때뿐만 아니라 정의할 때도 사용된다. 초한귀납법을 사용하여 정의역이 정렬집합인 함수를 정의하는 것을 초한재귀(transfinite recursion)라고 부른다.
문제 8.3. 다음을 증명하시오.
- 정렬집합에서 최소원소가 아닌 모든 원소 \(x\)는 직전원소를 갖거나 극한원소이다.
- 서로 다른 서수 \(\alpha\), \(\beta\)에 대하여 \(\alpha < \beta\)이거나 \(\beta < \alpha\)이다.
5. 서수의 덧셈
두 서수 \(\alpha\)와 \(\beta\)의 합 \(\alpha + \beta\)는 다음과 같이 정의된다. 서수 \(\alpha\)를 갖는 정렬집합 \(A\)와 서수 \(\beta\)를 갖는 정렬집합 \(B\)를 택하되 두 집합이 서로소가 되도록 택하고, \(A \cup B\)에 다음 순서를 준다.
- \(A\)의 원소들은 원래 순서를 유지한다.
- \(B\)의 원소들은 원래 순서를 유지한다.
- \(A\)의 임의의 원소는 \(B\)의 임의의의 원소보다 작다.
이때 \(\alpha + \beta = \text{ord}(A \cup B)\)로 정의한다.
예를 들면 다음과 같다.
- \(2 + 3 = 5\)
- \(\omega + 1\) (자연수들 다음에 하나의 원소가 더 있는 순서)
- \(1 + \omega = \omega\)
서수 덧셈의 성질은 다음과 같다.
- 결합법칙: \((\alpha + \beta) + \gamma = \alpha + (\beta + \gamma)\)
- 왼쪽 항등원: \(0 + \alpha = \alpha\)
- 오른쪽 소거법칙: \(\alpha + \gamma = \beta + \gamma\)이면 \(\alpha = \beta\)
- 교환법칙은 일반적으로 성립하지 않는다. 얘를 들어 \(1 + \omega \neq \omega + 1\)이다.
6. 서수의 곱셈
두 서수 \(\alpha\)와 \(\beta\)의 곱 \(\alpha \cdot \beta\)는 데카르트 곱 \(B \times A\)에 사전식 순서를 준 정렬집합의 서수이다. 여기서 \((b_1,\, a_1) < (b_2,\, a_2)\)일 필요충분조건은 다음과 같다. \[b_1 < b_2 \quad \text{또는} \quad (b_1 = b_2 \,\text{ 그리고 }\, a_1 < a_2)\]
예를 들어 다음과 같은 서수의 곱을 생각할 수 있다.
- \(2 \cdot 3 = 6\)
- \(\omega \cdot 2\) (자연수가 두 벌 있는 순서: \(0 < 1 < 2 < \cdots < 0' < 1' < 2' < \cdots\))
- \(2 \cdot \omega = \omega\)
서수 곱셈의 성질은 다음과 같다.
- 결합법칙: \((\alpha \cdot \beta) \cdot \gamma = \alpha \cdot (\beta \cdot \gamma)\)
- 왼쪽 분배법칙: \(\alpha \cdot (\beta + \gamma) = \alpha \cdot \beta + \alpha \cdot \gamma\)
- 오른쪽 분배법칙은 일반적으로 성립하지 않는다.
- 교환법칙은 일반적으로 성립하지 않는다, 예를 들어 \(2 \cdot \omega \neq \omega \cdot 2\)이다.
7. 서수의 거듭제곱
서수의 거듭제곱 \(\alpha^\beta\)는 초한재귀로 정의된다.
- \(\alpha^0 = 1\)
- \(\alpha^{\beta+1} = \alpha^\beta \cdot \alpha\)
- \(\beta\)가 극한서수일 때, \(\alpha^\beta = \operatorname{sup}\{\alpha^\gamma \mid \gamma < \beta\}\). [\(\sup\)은 '상한'(supremum)을 의미한다. 상한을 '최소상계'(least upper bound)라고 부르기도 한다.]
예를 들면 다음과 같다.
- \(2^\omega\): 이진수열을 사전식 순서로 나열한 것.
- \(\omega^\omega\): 자연수 수열을 사전식 순서로 나열한 것.
문제 8.4. 다음 물음에 답하시오.
- 서수 \(\omega + \omega\)와 \(\omega \cdot 2\)를 비교하시오.
- 서수 \((\omega + 1) \cdot 2\)와 \(\omega \cdot 2 + 2\)를 계산하시오.
- \(2^3\)과 \(3^2\)을 서수로서 계산하시오.
- 서수 \(\omega^2\)의 의미를 설명하시오.
8. 서수와 기수의 관계
모든 기수는 특별한 서수로 볼 수 있다. 구체적으로, 기수는 그 크기를 갖는 가장 작은 서수이다. 이러한 서수를 기수서수(cardinal ordinal) 또는 초기서수(initial ordinal)라고 한다.
예를 들어 다음과 같은 경우를 생각할 수 있다.
- 유한기수 \(n\)은 서수 \(n\)과 같다.
- \(\aleph_0\)은 서수 \(\omega\)와 같다.
- \(\omega + 1\), \(\omega \cdot 2\), \(\omega^2\) 등은 모두 가산무한이지만 서로 다른 서수이다.
즉, 같은 기수를 갖는 여러 서수가 존재할 수 있다. 서수는 집합의 크기뿐만 아니라 순서 구조까지 구별하기 때문이다.
9. 서수와 관련된 역설
모든 서수의 모임을 생각하면, 이것도 정렬순서를 가지므로 서수를 가져야 한다. 그런데 이 서수는 모든 서수보다 커야 하므로 모순이다. 이와 같은 역설을 부랄리-포르티의 역설(Burali-Forti paradox)이라고 부른다.
이 역설은 "모든 서수의 모임"이 집합이 아니라 고유클래스임을 보여준다. ZFC 공리계는 이러한 역설을 피하도록 설계되어 있다.
10. 서수의 집합론적 구성
지금까지 서수를 공리적으로 도입했지만, 사실 서수는 집합을 사용하여 직접 구성할 수 있다. 이러한 구성은 폰 노이만(von Neumann)이 제안한 방법으로, 6장에서 자연수를 집합으로 정의한 방법을 확장한 것이다.
폰 노이만의 방법에서 서수는 다음과 같이 정의된다.
- 서수 \(0 = \varnothing\)
- 서수 \(1 = \{0\} = \{\varnothing\}\)
- 서수 \(2 = \{0,\, 1\} = \{\varnothing,\, \{\varnothing\}\}\)
- 서수 \(3 = \{0,\, 1,\, 2\}\)
- 일반적으로, 서수 \(\alpha\)의 따름수는 \(\alpha \cup \{\alpha\}\)로 정의한다.
- 극한서수는 그보다 작은 모든 서수의 합집합으로 정의한다.
이 정의에서 각 서수는 자기보다 작은 모든 서수들의 집합이 된다. 즉 다음과 같다. \[\alpha = \{\beta \mid \beta < \alpha\}\] 특히 가장 작은 무한서수 \(\omega\)는 모든 유한서수(자연수)의 집합이다. \[\omega = \{0,\, 1,\, 2,\, 3,\, \ldots\} = \mathbb{N}\]
이러한 구성의 특징은 다음과 같다.
- 각 서수가 그 자신이 정렬집합이 된다. (원소 관계 \(\in\)이 순서관계가 된다.)
- 서수 \(\alpha\)는 자기 자신의 서수를 갖는 정렬집합의 표준적인 대표원소가 된다.
- 두 서수 \(\alpha\), \(\beta\)에 대하여, \(\alpha < \beta\)일 필요충분조건은 \(\alpha \in \beta\)인 것이다.
이와 같은 구성을 통해 서수 공리 (O1)과 (O2)가 만족됨을 알 수 있다. 즉, 서수를 별도의 공리로 도입할 필요 없이 ZFC 공리계 내에서 직접 구성할 수 있다. 다만 이와 같은 구성 방법은 집합론의 공리들, 특히 무한공리와 치환공리를 필요로 한다.
이렇게 구성된 서수 전체의 모임 \(ORD\)는 집합이 아니라 고유클래스가 된다. 만약 이것이 집합이라면 부랄리-포르티의 역설이 발생하기 때문이다.