Ordinal들 사이의 순서관계
임의의 ordinal은 정의에 의해 well-ordered set이다. 뿐만 아니라, 그 역 또한 성립한다고 할 수 있다.
명제 1 \(A,B\)가 두 well-ordered set들이라 하자. 그럼 적어도 다음 중 하나가 성립한다.
- \(A\)에서 \(B\)의 segment로의 order isomorphism이 존재하거나,
- \(B\)에서 \(A\)의 segment로의 order isomorphism이 존재한다.
증명
\(\mathcal{F}\)를 \(A\)의 segment에서 \(B\)의 segment로의 isomorphism들의 집합이라 하자. 우선 우리는 \(\mathcal{F}\)가 inductive임을 보인다.
\(\mathcal{F}\)의 totally ordered subset \(\mathcal{G}\)가 주어졌다고 하자. 그럼 \(u\in\mathcal{G}\)들의 정의역을 모두 합집합하여 집합 \(S\)를 만들 수 있다. 이 집합 \(S\)는 \(A\)의 segment들의 합집합이므로 다시 \(A\)의 segment이다. 한편, \(\fun(A,B)\)를 \(A\)의 부분집합에서 \(B\)로의 함수들의 모임이라 하자. 그럼 이 집합이 함수의 확장에 대해 inductive하다는 것은 자명하다. 이제 \(\bigcup\mathcal{G}\)는 \(A\)의 부분집합에서 \(B\)의 부분집합의 함수들이므로, \(\mathcal{G}\)의 \(\fun(A,B)\)에서의 least upper bound를 \(v\)라 하자. 그럼 \(v(S)\)는 \(u\in\mathcal{G}\)들의 치역의 합집합이므로 \(F\)의 segment가 되며, 임의의 \(x, y\)에 대하여 \(x\)와 \(y\)를 둘 다 포함하는 \(u\in \mathcal{G}\)를 골라오면
\[v(x)=u(x) < u(y)=v(y)\]에서 \(v\)는 \(S\)에서 \(v(S)\)로의 isomorphism이다. 따라서 \(\mathcal{F}\)는 inductive이다.
이제 Zorn’s lemma에 의해 \(\mathcal{F}\)는 maximal element를 갖는다. 이를 \(u_0\)이라 하고, 이의 정의역을 \(S_0\)이라 하자. 우리는 \(S_0=A\)이거나 \(u_0(S_0)=B\)임을 보여야 한다.
만일 그렇지 않다면, 어떤 \(a\in A\)와 \(b\in B\)가 존재하여 \(S_0=(-\infty, a)\)이고 \(u_0(S_0)=(-\infty, b)\)일 것이다. 이제 \(u_0\)에 \((a,b)\)를 추가하면 \(u_0\)을 strict하게 확장하는 새로운 함수가 생기고, 이는 \(u_0\)의 maximality에 모순이므로 \(S_0=A\)이거나 \(u_0(S_0)=B\)이다.
앞서 말한 것과 같이 임의의 ordinal은 well-ordered set이므로, 위 명제에 의하면 임의의 well-ordered set을 어떤 ordinal의 initial segment와 order isomorphic한 segment로 볼 수 있는 길이 열렸다. 그러나, 이를 위해서는 다음의 새로운 공리를 도입해야 한다.
The Axiom schema of Replacement. \(P(x,y)\)가
임의의 \(x\)에 대하여, \(P(x,y)\)를 성립하도록 하는 \(y\)가 항상 존재한다
를 만족하는 성질이라 하자. 그럼 임의의 집합 \(A\)에 대하여, 또 다른 집합 \(B\)가 존재하여,
\(x\in A\)마다, 적절한 \(y\in B\)가 존재하여 \(P(x,y)\)가 성립
하도록 할 수 있다.
위의 조건을 만족하는 \(P\)가 주어지면, 이를 \(x\)를 넣었을 때 \(y\)가 나오는 함수 \(F\)로 생각할 수도 있다. 다만 함수는 기본적으로 target이 정의된 상태에서 정의되었는데, 이 조건 \(P\)로 만들어지는 대응은 target에 대한 정보가 아무것도 없기 때문에 단일 공리 대신 axiom schema가 필요한 것이다. 어쨌든 replacement schema가 주어진다면 target \(B\)를 잘 정의해줄 수 있고, 이 때 \(B\)에 comprehension schema를 이용해
\((x,y)\in F\) for some \(x\)
조건을 걸어주면 \(A\)의 \(F\)를 통한 image를 동일하게 정의할 수 있게 된다.
정리 2 임의의 well-ordered set은 어떤 유일한 ordinal과 order isomorphic하다.
증명
\(A\)가 well-ordered set이라 하고, 집합 \(X\)를
\(S_x\)가 어떠한 ordinal과 order isomorphic하다
를 만족하는 \(x\in A\)들의 집합이라 하자. 임의의 ordinal은 자신을 제외한 ordinal과는 order isomorphic하지 않으므로, \(X\)에 속해있는 \(x\in A\)마다 유일한 ordinal \(\alpha_x\)를 지정해 줄 수 있다. 우리의 목표는 이러한 ordinal들을 모은 집합 \(B\)가 \(A\)와 order isomorphic한 ordinal이 된다는 것을 보이는 것인데, 그를 위해서는 이 집합이 존재한다는 것부터 우선 보여야 한다.
이를 위해, 성질 \(P(x,y)\)를 다음과 같이 정의하자.
(i) \(x\in X\)이고 \(y\)가 \(S_x\)와 order isomorphic한 ordinal이거나, (ii) \(x\not\in X\)이고 \(y=\emptyset\)이다.
이 성질은, 앞서 말한 것과 같이 유일한 ordinal \(y\)를 지정하거나, 혹은 (마찬가지로 유일한) 공집합 \(\emptyset\)을 지정하므로, axiom schema of replacement를 사용할 수 있다. 이를 적용하면, \(P\)에 의해 정의되는 함수 \(F\)에 대하여 집합 \(F(A)\)가 존재한다는 것을 알 수 있다. 이 집합을 \(B\)라 하자.
- \(B\)는 ordinal들의 집합이므로, \(\in\)에 의해 well-ordering이 주어져있다.
- 임의의 \(\alpha_x\in B\)에 대하여, 만일 \(\gamma\in\alpha_x\)라면 \(\alpha_x\)와 \(S_x\) 사이의 order isomorphism \(\varphi\)에 의한 inverse image \(\varphi^{-1}(\gamma)\in S_x\)를 생각할 수 있다. 이를 \(c\)라 하면, \(\varphi\)를 \(S_c\)로 제한한 함수가 \(S_c\)와 \(\gamma\) 사이의 order isomorphism을 정의하므로 \(B\)의 정의에 의해 \(\gamma\in B\)이다.
이상에서 \(B\)는 ordinal number임을 알 수 있다. 또, 2번 증명을 똑같이 적용한다면 임의의 \(x\in X\)에 대하여, 만일 \(y<x\)라면 \(y\in X\)임도 보일 수 있다. 즉, \(X\)는 \(A\)의 segment이고, 따라서 \(X=S_x\)이거나 \(X=A\)이다.
이제 \(X=A\)임을 보이기 위해, 결론을 부정하여 모순을 찾자. 우선 우리는 \(f:X\rightarrow B\)를 \(f(x)=\alpha_x\)로 정의할 수 있으며, 이 경우 \(f\)는 \(B\)와 \(X\) 사이의 order isomorphism이 된다는 것을 확인할 수 있다. 그런데 만일 \(X=S_x\)였다면, \(B\)는 ordinal이므로, \(S_x\)가 ordinal \(B\)와 isomorphic하다는 이야기가 되므로, 정의에 의해 \(x\in X\)여야 한다. 이는 모순이므로, \(X=A\)이다.
Cardinal number의 정의
이제 우리는 cardinality의 엄밀한 정의를 소개한다. 다만, 우리가 본격적으로 cardinal에 대해 다루는 것은 (엄밀하지 않은 정의를 사용하는) 다음 글이 될 것이며, 지금 할 내용은 어디까지나
우리가 다음 글에서 생각할 cardinality의 정의는 집합들 사이의 전단사함수를 이용해 집합의 크기를 정의한다. 예를 들어, 원소 두 개짜리 집합들 간에는 전단사함수가 존재하므로 이들의 크기가 같다고 생각할 것이다. 이러한 정의는 어떻게 보면 ordinal과는 잘 맞지 않는데, 예를 들어 \(\omega\)와 \(\omega+1\)은 분명 ordinal 측면에서는 다른 집합이지만 이들 간의 (순서를 무시하는) 전단사함수는 존재하기 때문이다. 이들을 합치려면 다음과 같이 정의하면 된다.
정의 3 임의의 집합 \(A\)에 대하여, \(A\)의 어떠한 부분집합과도 전단사함수가 존재하지 않는 가장 작은 ordinal number를 \(A\)의 Hartogs number라고 부르고, \(h(A)\)로 표기한다.
Successor ordinal들은 이들의
정의 4 Ordinal \(\alpha\)가 initial ordinal이라는 것은, \(\beta<\alpha\)를 만족하는 모든 \(\beta\)에 대해, \(\beta\)와 \(\alpha\) 사이의 전단사함수가 존재하지 않는 것이다.
그렇다면 임의의 집합의 크기는 initial ordinal의 크기로 표현할 수 있다. 어떤 집합 \(X\)가 주어졌을 때, 여기에 well-order를 주어 ordinal \(\alpha\)를 택한 다음, 이와 같은 크기를 갖는 ordinal들 중 가장 작은 것을 (well-ordering에 의해) 뽑아오면 된다.
우리는 ordinal number를 이용해서 cardinal number를 정의할 수 있다. 무한한 initial ordinal들을 모아둔 다음, 여기에 순서대로 \(0, 1, \ldots\)번째 순서를 붙인다고 생각하자. 즉, \(\omega_0\)은 0번째 initial ordinal, 즉 \(\omega\)와 같고, 그 후로 집합의 크기가 strict하게 커지는 \(\omega_1,\omega_2,\ldots\)와 같이 정의하는 것이다. Cardinal을 정의할 때에는, 이들을 (ordinal을 정의하는 문자인 \(\omega\) 대신) \(\aleph_\alpha\)와 같이 적는 것이 보통이다.
참고문헌
[HJJ] K. Hrbacek, T.J. Jeck, and T. Jech. Introduction to Set Theory. Lecture Notes in Pure and Applied Mathematics. M. Dekker, 1978.
댓글남기기