집합의 서수

By | Januar 8, 2018

집합의 기수(cardinal number)는 집합의 크기를 나타내는 값이고, 집합의 서수(ordinal number)는 집합이 가진 순서의 구조를 나타내는 값이다. (서수를 순서수라고 부르기도 한다.) 서수를 정의하는 방법은 '서수 공리'를 도입하는 공리적 방법과 집합으로 서수를 정의하는 구성적 방법이 있다. 여기서는 구성적 방법을 살펴보자.

1. 서수의 정의

서수가 모든 순서집합의 구조를 나타내지는 않는다. 서수는 순서집합 중에서도 정렬집합의 구조만 나타낸다. 따라서 서수를 정의하기 전에 정렬집합을 정의한다.

\(X\)가 집합이고 \(<\)가 \(X\) 위에서 정의된 전순서라고 하자. 만약 \(X\)의 부분집합 중에서 공집합이 아닌 것들이 항상 최소원소를 가지면 \( < \)를 \(X\)의 정렬(well-order)이라고 부르며, \((X,\, < )\)를 정렬집합(well-ordered set)이라고 부른다.

정리 1.  정렬집합에 대한 수학적 귀납법의 원리.

\((X ,\, < )\)가 정렬집합이고 \(Y \subseteq X\)라고 하자. 만약 \(x\in X,\) \(y\in Y,\) \(y < x\)일 때마다 \(x\in Y\)가 성립하면 \(Y=X\)이다.

증명. 결론에 반하여 \(Y \ne X\)라고 하자. 그러면 \(X \setminus Y \ne \varnothing\)이다. \(X\)가 정렬집합이므로 \(X \setminus Y\)는 최소원소를 가진다. 그 최소원소를 \(x\)라고 하자. \(x\)의 정의에 의하여 \(y < x\)인 \(y\)는 \(X \setminus Y\)에 속하지 않으므로 \(Y\)에 속한다. 그러면 정리의 가정에 의하여 \(x \in Y\)이므로 모순이다. 즉 \(Y \ne X\)일 수 없다.

위 정리는 다음과 같이 표현할 수도 있다.

정리 2.  정렬집합에 대한 수학적 귀납법의 원리.

\((X,\, < )\)가 정렬집합이며 \(p\)가 \(X\)를 정의역으로 하는 진술이라고 하자. 만약 \(x\in X,\) \(y < x,\) \(p(y) = \mathrm{T}\)일 때마다 \(p(x) = \mathrm{T}\)이면 \(X\)의 모든 원소에 대하여 \(p\)가 참이다.

증명. \(X\)의 원소 중에서 \(p\)가 참이 되도록 하는 것들의 모임을 \(Y\)라고 하자. 그러면 \(Y\)는 정리 1의 모든 조건을 만족시키므로 \(Y = X\)이다.

\((X,\, < )\)가 전순서집합이며 \(a\in X\)라고 하자. 이때 절단(section)을 \[X_a := \left\{ x \in X \,\vert\, x < a \right\}\] 로 정의한다. 절단의 개념은 서수를 정의할 때, 그리고 서수의 성질을 밝힐 때 계속 사용된다.

\(0\) 이상인 임의의 정수 \[n=\left\{ 0,\,1,\, \cdots ,\, n-1 \right\}\] 에 대하여 \[0 < 1 < 2 < \cdots < n-1\] 로 정의된 순서 \( < \)는 \(n\) 위에서의 정렬이다. 또한 임의의 유한집합 \(S\)에 대하여 \(S\)와 순서동형인 정렬집합 \(n\)이 존재한다. 이때 \(n\)은 \(S\)의 순서구조를 나타내는 값으로 여길 수 있다. 이러한 관점에서 임의의 정렬집합의 서수를 다음과 같이 정의하자.

정의 3.  서수.

\((X,\, < )\)가 정렬집합이고 임의의 \(a\in X\)에 대하여 \(X_a = a\)가 성립할 때, \((X,\, < )\)를 서수(ordinal number)라고 부른다.

자연순서가 주어졌을 때 음이 아닌 정수는 모두 정렬집합이며 서수의 정의를 만족시킨다. 즉 서수를 가장 작은 것부터 나열하면 \[\begin{eqnarray} 0 &=& \varnothing , \\[6pt] 1 &=& \left\{ 0 \right\} , \\[6pt] 2 &=& \left\{ 0,\,1 \right\} , \\[6pt] 3 &=& \left\{ 0,\,1,\,2 \right\} , \\[6pt] & \vdots & \\[6pt] n &=& \left\{ 0,\,1,\,2,\, \cdots ,\, n-1 \right\}\\[6pt] & \vdots & \end{eqnarray}\] 이 된다. 하지만 정수가 아닌 서수도 존재한다. 음이 아닌 모든 정수의 모임을 \(\omega\)로 나타내자. 즉 \[\omega := \left\{ 0,\,1,\,2,\,3,\, \cdots \right\}\] 이라고 하자. 이 집합에 자연순서가 주어지면, \(\omega\)는 정수가 아닌 서수 중에서 가장 작은 것이 된다. 만약 \(\omega \cup \left\{ \omega \right\}\)에 순서 \[0 < 1 < 2 < 3 < \cdots < \omega\] 가 주어지면 \(\omega \cup \left\{ \omega \right\}\)는 \(\omega\) 바로 다음 서수가 된다. 이와 같은 방법으로 다음 서수를 새롭게 계속 구성할 수 있으므로 정수가 아닌 서수는 무한히 많다.

2. 서수의 존재성과 유일성

이제 우리는 임의의 정렬집합에 대하여 그 정렬집합과 순서동형인 서수가 유일하게 존재함을 보일 것이다. 이것을 보여야만 서수가 정렬집합의 순서구조를 나타내는 값으로서의 역할을 할 수 있게 된다. 이것을 위하여 먼저 여러 개의 보조정리를 증명해야 한다.

보조정리 4. \(x\)가 서수이면 \(x\cup\left\{ x \right\}\)도 서수이다. (단, 임의의 \(y\in x\)에 대하여 \(y < x \)인 순서가 주어진 것으로 본다.)

증명. \(a = x \cup \left\{ x \right\}\)라고 하자. 그러면 \(a\)의 모든 절단은 \(x\)의 절단이거나 \(a_x\)이다. 그런데 \(x\)의 모든 원소는 \(x\)보다 작으므로 \(a_x = x\)이다. 더욱이 \(x\)가 서수이므로 \(y\in x\)인 \(y\)에 대하여 \(a_y = x_y = y\)이다.

보조정리 5. \((x,\, < )\)가 정렬집합이고 \(Y \subseteq X\)이며 \(f : X \rightarrow Y\)가 순서동형사상이라고 하자. 그러면 임의의 \(x\in X\)에 대하여 \(f(x) \ge x\)이다.

증명. 수학적 귀납법의 원리를 사용하자. \(E = \left\{ x\in X \,\vert\, f(x) < x \right\}\)라고 하자. 만약 \(E \ne \varnothing\)이면 \(E\)는 최소원소를 가진다. 그 최소원소를 \(x_0\)이라고 하자. 그러면 \(f(x_0 ) < x_0\)이다. \(f\)가 순서동형사상이므로 \(f(f(x_0 )) < f(x_0 )\)이다. 그러나 이것은 \(f(x_0 ) \in E\)를 뜻하며, \(f(x_0 )\)은 최소원소 \(x_0 \in E\)보다 작은 원소가 된다. 이것은 모순이므로 \(E = \varnothing\)이다.

보조정리 6. \(X\)와 \(Y\)가 정렬집합이라고 하자. 그러면 \(X\)로부터 \(Y\)로의 순서동형사상은 많아야 하나 존재한다.

증명. \(f\)와 \(g\)가 모두 \(X\)로부터 \(Y\)로의 순서동형사상이라고 하자. 그러면 \(g^{-1} \circ f\)는 \(X\)로부터 \(X\)로의 순서동형사상이며, 보조정리 5에 의하여 임의의 \(x\in X\)에 대하여 \(x \leq g^{-1} (f(x))\)이다. 여기서 \(g\)가 순서동형사상이므로 \(g(x) \le f(x)\)이다. 같은 방법으로 두 함수의 역할을 바꾸면 임의의 \(x\in X\)에 대하여 \(f(x) \le g(x)\)임을 보일 수 있다. 그러므로 순서관계의 반대칭성에 의하여 \(f(x) = g(x)\)를 얻는다.

보조정리 7. 정렬집합 \(X\)로부터 그 절단 \(X_a\)로의 순서동형은 존재하지 않는다.

증명. 만약 \(f : X \rightarrow X_a\)가 순서동형사상이라면 \(f(a) \in X_a\)이므로 \(f(a) < a\)이다. 이것은 보조정리 5에 모순이다.

보조정리 8. \((X,\, < )\)가 정렬집합이고 \(A = \left\{ X_a \,\vert\, a \in X \right\}\)라고 하자. 그러면 \((A ,\, \subset ) \cong (X ,\, < )\)이다.

증명. \(X\)로부터 \(A\)로의 함수 \(f\)가 \(f(a) = X_a\)로 주어졌다고 하자. 이 함수가 순서동형사상임을 보일 것이다. 먼저 \(f\)가 일대일 대응임을 보이자. 만약 \(a < b\)이면 \(a\in X_b\)이지만 \(a \notin X_a\)이므로 \(X_a \ne X_b\)이다. 그러므로 \(f\)는 일대일 함수이다. 더욱이 \(f\)는 명백히 위에로의 함수이므로, \(f\)는 일대일 대응이다. 다음으로 \(f\)가 순서를 보존함을 보이자. \(a < b\)라고 하자. 그러면 임의의 \(x\in X_a\)에 대하여 \(x < a\)이므로 \(x < b\)이며 \(x \in X_b)\)이다. 이것은 \(X_a \subseteq X_b\)를 뜻한다. 그런데 \(f\)가 일대일 함수이므로 여기서 등호가 성립하지 않고 \(X_a \subset X_b\)이다. 그러므로 \(f\)는 순서를 보존한다.

보조정리 9. 서수의 절단은 서수이다.

증명. \(X\)가 서수이고 \(X_a\)가 \(X\)의 절단이라고 하자. 그리고 \(b\in X_a\)에 대하여 \((X_a )_b \)를 생각하자. 이 집합은 \(x\in X_a\) 중에서 \(b\)보다 작은 것들로 이루어져 있다. 그런데 \(b\)보다 작은 임의의 원소 \(x\)는 \(a\)보다 작다. 따라서 \((X_a )_b = X_b = b\)이다. 여기서 두 번째 등식은 \(X\)가 서수라는 사실로부터 얻어진 것이다. 그러므로 \(X_a\)는 서수이다.

보조정리 10. \(X\)와 \(Y\)가 서수이고 \(Y \subseteq X\)이면 \(Y\)는 \(X\)의 절단이다.

증명. \(a\)가 \(X \setminus Y\)의 최소원소라고 하자. 그러면 \(X_a \subseteq Y\)이다. \(y\in Y\)라고 하자. 만약 \(a < y\)이면 \(X_y = y = Y_y\)이며, 이 집합은 \(a\)를 원소로 갖는다. 즉 \(a\in Y\)인데, 이것은 가정에 모순이다. 또한 \(y\in Y\)이고 \(a \notin Y\)이므로 \(y = a\)는 성립하지 않는다. 따라서 \(y < a\)이고 \(y \in X_a\)이다. 그러므로 \(Y \subseteq X_a\)이다. 이로써 \(Y = X_a\)이므로 \(Y\)는 \(X\)의 절단이다.

보조정리 11. \(X\)와 \(Y\)가 서로 다른 서수이면 둘 중 하나는 다른 하나의 절단이다.

증명. 먼저 \(X \cap Y\)는 서수이다. 왜냐하면, 만약 \(a \in X \cap Y\)이면 \(X_a = a = Y_a\)이므로 \(a\)의 모든 원소는 \(X\)와 \(Y\) 모두에 속하며 \(a = (X \cap Y)_a\)이다. 따라서 보조정리 10에 의하여 \(X \cap Y\)는 \(X\)와 \(Y\) 모두의 절단이다.

이제 결론에 반하여 \(X\)와 \(Y\) 중 어느 것도 다른 것의 부분집합이 아니라고 가정하자. 적당한 \(a\in X\)에 대하여 \(X \cap Y = X_a\)이고, 적당한 \(b \in Y\)에 대하여 \(X \cap Y = X_b\)이므로 \[a = X_a = X \cap Y = X_b = b \in X \cap Y \] 이다. 이것은 모순이므로 \(X\)와 \(Y\) 중 하나는 다른 것의 부분집합이다. 그러므로 보조정리 10에 의하여 둘 중 하나는 다른 하나의 절단이다.

보조정리 12. 두 개 이상의 서수의 합집합은 서수이다.

증명. 먼저, 공집합이 아닌 서수의 원소는 서수임을 확인하자. \(x\)가 서수이고 \(y \in x\)라고 하자. \(z \in y\)이면 \(y = x_y\)이므로 \[y_z = (x_y )_z = x_z = z\]이다. 그러므로 \(y\)는 서수이다.

이제 \(X\)가 집합이고 그 원소가 모두 서수라고 하자. 그러면 \(A = \cup X\)는 서수의 집합이다. \(A\)의 원소 \(x,\) \(y\)에 대하여 \(x < y\)일 필요충분조건을 \(x\)가 \(y\)의 절단인 것으로 정의하면 \( < \)는 \(A\) 위에서 비반사적이고 반대칭적인 관계가 된다. 또한 \(x < y < z\)이면 \(y=z_y\)이고 \[x = y_x = (z_y )_x = z_x\]이며 \(x < z\)이므로 \( < \)는 \(A\)의 순서관계이다. 그리고 보조정리 11에 의하여 \( < \)는 전순서가 된다. 더욱이 \( < \)는 정렬이다. 즉 \(A\)의 공집합 아닌 부분집합 \(B\)에 대하여 \(b \in B\)를 택하자. 만약 \(b\)가 \(B\)의 최소원소가 아니면 \(b\)보다 작은 원소는 모두 \(b\)의 절단이 되는데, \(b\)가 정렬집합이므로 그러한 원소들 중에 최소원소가 존재한다. [이것으로부터 임의의 서수가 정렬집합임이라는 정리를 얻는다.] 따라서 \( < \)는 \(A\)의 정렬이다. 끝으로 \(a \in A\)를 택하고 \(a \in x \in X\)라고 가정하자. 그러면 \(a = x_a\)이므로 \(a\)의 모든 원소는 \(x\)에 속하며 \(A\)에도 속한다. 그러므로 \(a = A_a\)이다. 즉 \(A\)는 서수이다.

보조정리 13. \(X\)와 \(Y\)가 순서동형인 서수이면 \(X=Y\)이다.

증명. \(f : X \rightarrow Y\)가 순서동형사상이라고 하고 \[E = \left\{ x \in X \,\vert\, f(x) \ne x \right\}\] 라고 하자. \(E = \varnothing\)인 경우에는 자명하게 \(X = Y\)이다. 그러므로 \(E \ne \varnothing\)이라고 가정하자. \(a\)가 \(E\)의 최소원소이면 \(x < a\)인 임의의 \(x\)에 대하여 \(f(x) = x\)이므로 \[a = X_a = Y_{f(a)} = f(a)\] 이다. 이것은 모순이므로 \(E = \varnothing\)일 수밖에 없다.

보조정리 14. \((X,\, < )\)가 정렬집합이며, 임의의 \(a \in X\)에 대하여 절단 \(X_a\)와 순서동형인 서수가 존재하면 \(X\)와 순서동형인 서수도 존재한다.

증명. 각 \(a \in X\)가 서수 \(Z(a)\)와 순서동형이고, \(g_a : X_a \rightarrow Z(a)\)가 순서동형사상이라고 하자. 보조정리 13과 보조정리 6에 의하여 각 \(a\)에 대하여 \(Z(a)\)와 \(g_a\)는 유일하게 결정된다. 그러므로 \(Z\)는 \(X\)를 정의역으로 하는 함수로 여겨질 수 있다. \(Z\)의 치역을 \(W\)라고 하자. 즉 \[W := \left\{ Z(a) \,\vert\, a \in X \right\}\] 이다. 만약 \(x \in X,\) \(y \in X,\) \(x < y\)이면 \(Z(x) \subset Z(y)\)이다. \(Z(x)\)와 \(Z(y)\)가 서로 다른 서수이므로 보조정리 11에 의하여 \(Z(x)\)와 \(Z(y)\) 중 하나는 다른 것의 절단이다. 그런데 \(Z(y)\)가 \(Z(x)\)의 절단이 될 수는 없다. 왜냐하면 만약 \(Z(y)\)가 \(Z(x)\)의 절단이라면 \(g_y\)와 포함관계와 \(g_x\)를 합성하여 \(X_y\)로부터 \(X_x\)로의 일대일인 순서동형사상을 만들 수 있기 때문이다. 따라서 \(Z\)는 일대일 대응이다. 즉 \(W\)에 포함관계가 순서관계로 주어졌다고 보면 \(Z\)는 \(X\)로부터 \(W\)로의 순서동형사상이다. 이로써 \(W\)는 정렬집합과 순서동형이므로 \(W\) 자신도 정렬집합이다. 끝으로 \(W\)의 임의의 부분집합이 서수이므로 임의의 절단 \(W_a\)는 \(a\)와 같다. 그러므로 \(W\)는 서수이다.

정리 15. 임의의 정렬집합에 대하여 그 정렬집합과 순서동형인 서수가 유일하게 존재한다.

증명. \(X\)가 정렬집합이라고 하자. 그리고 \(X\)의 원소 \(a\) 중에서 \(X_a\)와 순서동형인 서수가 존재하지 않도록 하는 원소 \(a\)가 존재한다고 가정하자. \(X\)가 정렬집합이므로 그러한 \(a\) 중 가장 작은 것이 존재한다. \(a\)가 최소원소라는 성질에 의하여 \(X_a\)의 임의의 절단에 대하여 그것과 순서동형인 서수가 존재한다. 따라서 보조정리 14에 의하여 \(X_a\)와 순서동형인 서수도 존재한다. 이것은 모순이므로 임의의 \(a \in X\)에 대하여 \(X_a\)와 순서동형인 서수가 존재한다. 그러므로 다시 보조정리 14에 의하여 \(X\)와 순서동형인 서수도 존재한다. 더욱이 보조정리 13에 의하여 \(X\)와 순서동형인 서수는 유일하다.

이로써 임의의 정렬집합에 대하여 그 정렬집합의 순서구조를 나타내는 서수가 존재하게 되었다. 이것은 마치 세상의 모든 것에 수의 개념을 도입하여 물건의 개수를 세도록 하는 것과 마찬가지의 상황이다. 여기서 Russell의 역리와 비슷한 다음 역리를 만난다.

정리 16.  Burali-Forti의 역리.

모든 서수의 집합은 존재하지 않는다. 즉 모든 서수의 모임은 고유클래스(proper class)이다.

증명. 모든 서수들의 모임을 \(OR\)라고 하자. 그러면 \(OR\)는 그 자체로서 서수이다. 만약 \(OR\)가 고유클래스가 아니라면 \(OR\)는 자기 자신의 원소가 되어야 한다. 그런데 \(OR\)는 \(OR\)에 속한 어떤 원소보다도 크므로 자기 자신에 속할 수가 없다. 이것은 모순이다.

3. 서수의 대소비교와 극서수

서수들의 모임 \(OR\)가 집합은 아니지만 클래스이므로 \(OR\)의 적당한 부분집합을 잡아서 그 집합 위에서 순서관계를 생각할 수 있다.

정리 17.  서수의 대소비교.

\(x\)와 \(y\)가 서수일 때, 다음 세 조건은 모두 서로 필요충분조건이다.
(a) \(x < y\)
(b) \(x \in y\)
(c) \(x \subset y\)

더욱이 \(x < y,\) \(x=y,\) \(x > y\) 중 하나가 유일하게 성립한다.

위 정리에서 \(x < y\)라는 표현을 쓸 때에는 \(x\)와 \(y\) 모두가 속하는 서수를 순서집합으로 생각해야 한다. 왜냐하면 모든 서수의 모임 \(OR\)는 집합이 아니므로 \(OR\)에 순서관계를 부여할 수 없기 때문이다.

정리 17의 증명. \(x < y\)일 필요충분조건은 \(x \in z_y = y\)이므로 (a)와 (b)는 서로 필요충분조건이다. 다음으로 \(x < y\)일 때 \(x = z_x \subset z_y = y\)이고, \(x \nless y\)일 때 \(x=y\) 또는 \(y < x\)이므로 \(y \subset x\) 즉 \(x \not\subset y\)이다. 따라서 (a)와 (c)는 서로 필요충분조건이다. 끝으로 보조정리 11에 의하여 \(x \subset y ,\) \(x=y,\) \(x \supset y\) 중 하나가 유일하게 성립하므로 \(x < y,\) \(x=y,\) \(x > y\) 중 하나가 유일하게 성립한다.

정렬집합에 대한 수학적 귀납법의 원리와 비슷하게 \(OR\)에 대해서도 수학적 귀납법의 원리를 사용할 수 있다.

정리 18. 서수에 대한 수학적 귀납법의 원리.

\(P\)가 서수에 대한 진술(명제함수)이라고 하자. \(x\)가 서수이고 \(y < x\)인 임의의 서수 \(y\)에 대하여 \(P(y)\)가 참일 때마다 \(P(x)\)도 참이라고 가정하자. 그러면 임의의 서수 \(x\)에 대하여 \(P(x)\)가 참이다.

증명. 서수 \(x\)가 임의로 주어졌다고 하자. 서수 \(x \cup \left\{ x \right\}\)는 정렬집합이므로, 이 집합 위에서 수학적 귀납법을 사용하면 \(P(x)\)가 참임을 보일 수 있다.

서수를 작은 것부터 나열했을 때 어떠한 위치에 놓여 있느냐에 따라 서수를 크게 세 가지 종류로 나눌 수 있다.

첫 번째는 가장 작은 서수인 \(0\)이다.

두 번째는 직후자서수(successor ordinal)이다. 즉 주어진 서수를 \(\alpha \cup \left\{ \alpha \right\}\)의 꼴로 나타낼 수 있을 때, 주어진 서수는 \(\alpha\)의 직후자서수가 된다. 자연수의 경우 \(n\)의 직후자서수는 \(n+1\)이다. 일반적으로 \(\alpha\)이 직후자서수를 \(s(\alpha )\)로 나타낸다.

세 번째는 어떠한 서수의 직후자서수도 되지 않는 서수, 즉 극서수(limit ordinal)이다. 극서수는 자기 자신보다 작은 모든 서수들의 합집합과 같다. 즉 \(\lambda\)가 극서수라는 것은 \[\lambda = \bigcup_{\alpha < \lambda} \alpha\] 임을 뜻한다. 극서수를 극한서수라고 부르기도 한다. 직후자서수는 극서수가 아니다. 왜냐하면, 만약 \(\lambda = \alpha \cup \left\{ \alpha \right\}\)이면 \(\lambda\)보다 작은 모든 서수는 \(\alpha\)에 포함되므로 그들의 합집합도 \(\alpha\)에 포함되기 때문이다.

정리 19.  서수의 분류

\(0\)이 아닌 임의의 서수는 직후자서수이거나 극서수이다.

증명. \(\lambda\)가 \(0\)이 아니고 직후자서수도 아닌 서수라고 하자. 그리고 \[\mu = \bigcup_{\alpha < \lambda} \alpha\] 라고 하자. 서수들의 합집합은 서수이므로 \(\mu\)도 서수이다. 또한 \(\mu \subseteq \lambda\) 즉 \(\mu \le \lambda\)이다. \(\mu < \lambda\)라고 가정하자. 그러면 \(\mu\)는 \(\mu\)를 구성할 때 합집합한 집합들 중 하나이므로 \(\lambda\)보다 작은 서수들 중에서 가장 큰 서수이다. \(\lambda > \mu\)이므로 \(\lambda \ge s(\mu )\)이다. 이 부등식에서 등호를 뺄 수 없다. 왜냐하면 만약 등호를 빼면 \(s(\mu )\)는 \(\mu\)를 구성할 때 합집합한 집합들 중 하나가 되는데 그러면 \(s(\mu ) \le \mu\)이므로 성립하지 않는다. 그러므로 \(\lambda = s(\mu )\)는 직후자서수가 되어 가정에 모순이다. 즉 \(\lambda = \mu\)이며 \(\lambda\)는 극서수이다.

서수에 대한 수학적 귀납법의 원리는 다음과 같이 표현할 수 있다.

정리 20.  서수에 대한 수학적 귀납법의 원리(초한 귀납법).

\(P\)가 서수에 대한 진술이고 다음 세 조건을 모두 만족시킨다고 하자.

  • \(P(0)\)은 참이다.
  • 임의의 서수 \(\alpha\)에 대하여 \(P(\alpha )\)가 참일 때마다 \(P(s(\alpha ))\)도 참이다.
  • \(\lambda\)가 극서수이고 \(\beta < \lambda\)일 때마다 \(P(\beta )\)가 참이면 \(P(\lambda )\)도 참이다.

그러면 임의의 서수 \(\alpha\)에 대하여 \(P(\alpha )\)는 참이다.

증명. \(Q\)가 서수에 대한 진술이며, \(Q(\alpha)\)가 참일 필요충분조건은 \(\beta \le \alpha\)인 임의의 \(\beta\)에 대하여 \(P(\beta )\)가 참인 것이라고 정의하자. \(Q\)가 정리 18의 가정을 만족시킴을 보이자. \(\beta < \alpha\)인 임의의 \(\beta\)에 대하여 \(Q(\beta )\)가 참이라고 가정하자. 그러면 \(\beta < \alpha\)인 임의의 \(\beta\)에 대하여 \(P(\beta )\)가 참이다. \(\alpha = 0\)이거나 \(\alpha\)가 극서수이면 정리의 가정으로부터 \(P(\alpha )\)는 참이다. \(\alpha = s(\beta )\)라고 가정하자. 그러면 \(P(\beta )\)가 참이므로 가정에 의하여 \(P(\alpha )\)도 참이다.

따라서 모든 경우에서 \(P(\alpha )\)는 참이다. \(\beta < \alpha\)인 임의의 \(\beta\)에 대하여 \(P(\beta )\)가 참이므로 \(Q(\alpha )\)도 참이다.

그러므로 정리 18에 의하여 임의의 서수 \(\alpha\)에 대하여 \(Q(\alpha)\)가 참이며, \(P(\alpha )\)도 참이다.

4. 서수의 연산

서수는 모든 자연수를 포함한다. 서수는 유한집합뿐만 아니라 임의의 정렬집합의 순서구조를 나타낸다. 기수를 '집합의 원소의 개수를 세는 수'라고 한다면 서수는 '정렬집합의 순서구조를 세는 수'라고 할 수 있다. 이러한 관점에서 서수의 연산 즉 서수합, 서수곱, 서수거듭제곱을 생각할 수 있다.

서수의 연산을 정의하는 방법은 두 가지가 있다. 하나는 순서합과 순서곱을 먼저 정의한 뒤 이를 이용하여 서수의 합과 곱을 정의하는 방법이고, 다른 하나는 초한귀납법을 이용하는 방법이다. 먼저 순서합과 순서곱을 이용하는 방법은 다음과 같다.

정의 21.  순서합과 순서곱.

\((X,\, < _X )\)와 \((Y ,\, < _Y )\)가 순서집합이라고 하자. 이때 순서합집합 \((Z ,\, < _Z ) \)를 다음과 같이 정의한다.

  • \(Z = (X \times \left\{ 0 \right\} ) \cup ( Y \times \left\{ 1 \right\}) \)
  • \((x_1 ,\, 0) < _Z ( x_2 ,\, 0)\)일 필요충분조건은 \(x_1 < _X x_2 \)이다.
  • \((y_1 ,\, 1) < _Z ( y_2 ,\, 1)\)일 필요충분조건은 \(y_1 < _Y y_2 \)이다.
  • \(x \in X,\) \(y \in Y\)에 대하여 \((x,\,0) < _Z (y ,\,1)\)이다.

다음으로 순서곱집합 \((W ,\, < _W ) \)를 다음과 같이 정의한다.

  • \(W = X \times Y\)
  • \(y_1 < _Y y_2\)일 때 \((x_1 ,\, y_1 ) < _W (x_2 ,\, y_2 )\)이다.
  • \(x_1 < _X x_2\)일 때 \((x_1 ,\, y ) < _W ( x_2 ,\, y )\)이다.

두 전순서집합의 순서합집합과 순서곱집합은 모두 전순서집합이다. 더욱이 두 정렬집합의 순서합집합과 순거곱집합은 모두 정렬집합이다.

정의 22.  서수합과 서수곱.

\(\alpha\)와 \(\beta\)가 서수라고 하자. \(\alpha\)와 \(\beta\)의 순서합집합의 서수를 서수합이라고 부르며 \(\alpha + \beta\)로 나타낸다. \(\alpha\)와 \(\beta\)의 순서곱집합의 서수를 서수곱이라고 부르며 \(\alpha\beta\)로 나타낸다.

다음으로 초한귀납법을 이용하여 서수합과 서수곱을 정의하는 방법을 살펴보자.

정의 23.  초한귀납법을 이용한 서수합과 서수곱의 정의.

\(\alpha\)와 \(\beta\)가 서수라고 하자. 이때 서수합 \(\alpha + \beta\)를 다음과 같이 정의한다.

  • \(\alpha + 0 := \alpha .\)
  • \(\alpha + s(\beta ) := s(\alpha + \beta .\)
  • \(\lambda\)가 극서수일 때 \(\alpha + \lambda := \bigcup_{\beta < \lambda} ( \alpha + \beta ) . \)

다음으로 서수곱 \(\alpha \beta\)를 다음과 같이 정의한다.

  • \(\alpha \cdot 0 := 0 .\)
  • \(\alpha \cdot s(\beta ) := \alpha \cdot \beta + \alpha .\)
  • \(\lambda\)가 극서수일 때 \(\alpha \cdot \lambda := \bigcup_{\beta < \lambda} ( \alpha \cdot \beta ) . \)

초한귀납법을 이용하면 정의 23이 정의 22와 일치함을 보일 수 있다. 초한귀납법을 이용하여 서수합과 서수곱을 정의했을 때의 장점은 응용이 쉽다는 것이다. 예컨대 초한귀납법을 이용하여 서수거듭제곱을 다음과 같이 정의할 수 있다.

정의 24.  서수거듭제곱.

\(\alpha\)와 \(\beta\)가 서수라고 하자. 이때 서수거듭제곱 \(\alpha ^{\beta}\)을 다음과 같이 정의한다.

  • \(\alpha ^0 := 1 .\)
  • \(\alpha ^{s(\beta )} := \alpha^{\beta} \cdot \alpha .\)
  • \(\lambda\)가 극서수일 때 \(\alpha^{\lambda} := \bigcup_{\beta < \lambda} \alpha^{\beta} .\)

\(\omega\)보다 작은 서수는 \(0\) 또는 자연수이다. 더욱이 자연수의 합, 곱, 거듭제곱은 서수의 연산의 정의와 일치한다. 유한집합이 아닌 집합에 대한 서수를 초한서수 또는 무한서수라고 부른다. 초한서수 중 가장 작은 것이 \(\omega\)이다.

서수의 연산과 관련된 법칙은 대부분 초한귀납법을 이용하여 증명된다.

정리 25.  서수 연산의 법칙.

\(\alpha ,\) \(\beta ,\) \(\gamma\)가 서수일 때 다음이 성립한다.

(a) \((\alpha + \beta ) + \gamma = \alpha + (\beta + \gamma ) .\)
(b) \(\gamma \cdot (\alpha + \beta ) = \gamma \cdot \alpha + \gamma \cdot \beta .\)
(c) \( \alpha^{\beta + \gamma} = \alpha^{\beta} \cdot \alpha^{\gamma} . \)

증명. 세 등식 모두 초한귀납법을 이용하여 증명된다. 여기서는 (a)만 증명한다. 먼저 \(\gamma = 0\)인 경우는 다음과 같다. \[(\alpha + \beta ) + 0 = \alpha + \beta = \alpha + (\beta + 0).\] 다음으로 \(\gamma = s(\delta )\)이고 \[(\alpha + \beta )+ \delta = \alpha +(\beta + \delta )\] 라고 하자. 그러면 다음이 성립한다. \[\begin{eqnarray} (\alpha + \beta ) + s(\delta ) &=& s((\alpha + \beta ) + \delta ) \\[7pt] &=& s(\alpha + (\beta + \delta )) \\[7pt] &=& \alpha + s(\beta + \delta ) \\[7pt] &=& \alpha + (\beta + s(\delta )). \end{eqnarray}\] 끝으로 \(\gamma\)가 극서수이고 \(\delta < \gamma\)인 \(\delta\)에 대하여 \[(\alpha + \beta )+\delta = \alpha + ( \beta + \delta )\] 라고 하자. 그러면 다음이 성립한다. \[\begin{eqnarray} (\alpha + \beta ) + \gamma &=& \bigcup_{\delta < \gamma} ((\alpha + \beta )+\delta) \\[3pt] &=& \bigcup_{\delta < \gamma} (\alpha + (\beta + \delta )) \\[3pt] &=& \alpha + \bigcup_{\delta < \gamma} (\beta + \delta ) \\[3pt] &=& \alpha + (\beta + \gamma). \end{eqnarray}\] 그러므로 초한귀납법에 의하여 임의의 \(\alpha ,\) \(\beta ,\) \(\gamma\)에 대하여 (a)가 성립한다.

기수나 자연수의 연산 법칙이 서수에 대해서는 성립하지 않는 경우가 있다. 예컨대 무한수열의 가장 앞에 하나의 항을 추가하여도 처음 수열과 동형인 무한수열이지만, 무한수열의 가장 끝에 하나의 항을 추가하면 처음 수열과 동형이 아니므로 \[1+\omega = \omega \neq \omega +1\] 이다. 즉 서수합의 교환법칙이나 소거법칙은 성립하지 않는다. [참고 : 서수의 연산과 관련된 다양한 성질.]

서수를 구성하다 보면 복잡한 순서 구조를 만나게 된다. \(\omega ^2\)은 무한수열의 무한수열이며 \(\omega ^3 ,\) \(\omega ^4 ,\) \(\cdots\)은 무한수열들의 무한수열이다. 더욱이 \[\omega^{\omega} = \bigcup_{n\in\mathbb{N}} \omega^n\] 이며, 과정을 계속하여 다음과 같은 서수를 만난다. \[\omega^{\omega^{\text{⋰} ^{\omega}}}\] 여기서 밑과 지수 모두에 \(\omega\)는 \(n+1\)개이다. 이와 같은 서수를 \(\omega_n\)으로 나타내자. 일반적으로 \(\omega_{\alpha}\)는 다음과 같의 정의된 서수이다.

  • \(\omega _0 := \omega .\)
  • \(\omega_{s(\alpha )} := \omega ^{\omega_{\alpha}} .\)
  • \(\lambda\)가 극서수일 때, \(\omega_{\lambda} := \bigcup_{\alpha < \lambda} \omega_{\alpha} .\)

그러면 \(\omega_{\omega}\)는 지수가 무한히 반복되는 \(\omega^{\omega^{\text{⋰}}}\)와 같은 꼴이다. 이러한 과정이 다시 무한히 반복되는 서수 \(\epsilon = \omega_{\omega_{\ddots}}\)를 생각할 수 있다.

이러한 방법으로 얻어지는 서수들은 모두 가산이다. 왜냐하면 가산 개의 가산서수의 합집합은 가산서수이기 때문이다. 그런데 정렬 원리에 의하여 임의의 집합은 정렬 가능하므로 비가산집합 중에서 가장 작은 집합 \(\aleph_1\)도 정렬 가능하다. \(\aleph_1\)의 정렬은 여러 가지가 있으므로 \(\aleph_1\)에 대응시킬 수 있는 서수는 여러 개가 존재하는데, 그러한 서수 중 가장 작은 것을 최소비가산서수(first uncountable ordinal)라고 부른다.

기수가 동일한 정렬집합 중 정렬 순서로 비교하였을 때 가장 작은 정렬집합의 서수를 시서수(initial ordinal number)라고 부른다. 모든 시서수들의 모임을 \(CD\)라고 하면 \(CD\)는 기수 공리의 조건을 모두 만족시킨다. 따라서 기수를 공리로 정의하지 않고 시서수로서 정의할 수 있다.

서수의 숲은 참 놀랍다. What a wonderland!

Schreibe einen Kommentar