자연수의 서수와 기수
얼마 전 계승혁 교수님의 집합론 영상을 끝까지 봤다. 마지막 챕터가 선택공리, 서수, 기수에 대한 내용이었는데, 서수와 기수를 먼저 이용해놓고는 막상 정의는 마지막에 가서 하는 것이 좀 의아했다. 예를 들어 전단사함수가 존재하는 두 집합 $X$와 $Y$는 대등하다(equipotent)고 말하며, 아래와 같이 쓰면서,
$$X \approx Y \Leftrightarrow \mathrm{card}(X) = \mathrm{card}(Y)$$
"$\mathrm{card}(X)$"를 $X$의 기수라 부른다"고 적혀있다. 만족스럽지 않은 설명이라고 생각했는데, 정의를 보니까 왜 정의를 나중에 설명하는지 납득이 됐다.
솔직히 이 글을 쓰는 지금도 이해했다고는 말 못하겠는데, 감은 온 것 같아서 기록을 남겨둔다.
두 집합 $A$, $B$ 간에 순서를 보존하는 전단사함수가 있으면 두 집합을 순서동형(order isomorphic)이라고 말하며, $A \cong B$라고 쓴다. 자연수 집합은 $\mathbb{N}$이라고 쓰지만 정렬집합(well ordered set)으로 볼 때에는 $\omega$라고 쓴다. 순서관계를 생각해보면 $1+\omega \cong \omega$이지만 $\omega$와 $\omega+1$은 순서동형이 아니다. $\omega$는 최대원소가 없지만 $\omega+1$은 최대원소가 있기 때문이다. 같은 방식으로 임의의 자연수 $n$에 대해
$$\omega < \omega + 1 <\omega + 2 < \dots < \omega + n$$
임을 알 수 있다.
하지만 순서보존을 신경쓰지 않는다면 이 집합들은 모두 $\mathbb{N}$과 전단사함수가 있다. 즉, 집합의 크기는 같다. 순서만 다르다. 기수는 크기가 같은지, 즉 전단사함수가 존재하는지를 보는 것이고, 서수는 여기에 순서를 추가한 개념이다.
정확한 정의는 다음과 같다.
[Definition] 서수(ordinal number): $\alpha$가 정렬집합이고 임의의 $\xi\in\alpha$에 대해 $S_{\xi} = \xi$이면 $\alpha$를 서수라고 부른다.
여기서 $S_{\xi}$는 $\xi$에 의한 절단으로, $S_{\xi} := \{x\in \alpha | x < \xi\}$로 정의된다. 임의의 자연수와 $\omega$는 서수이다. $\alpha$가 서수이면 $\alpha$ 맨 뒤에 $\{\alpha\}$를 삽입하면 서수의 성질을 만족하므로 서수가 된다. 따라서 임의의 자연수 $n$에 대해 $\omega + n$도 서수이다.
두 서수는 대소비교가 가능하다. 두 서수 $\alpha$와 $\beta$에 대해 $\alpha$가 $\beta$의 절편이면 $\alpha < \beta$라고 정의한다.
서수를 받아들이면 기수는 어렵지 않다. 어떤 집합 $X$의 기수(cartinal number)의 정의는 $X$와 전단사함수가 존재하는 서수 중 가장 작은 것이다. 앞서 말했듯 $\mathbb{N}$은 임의의 자연수 $n$에 대해 $\omega + n$과 전단사함수가 존재한다. 그 중에서 가장 작은 것인 $\omega$가 $\mathbb{N}$의 기수이다. 따라서 $\omega+1$은 기수가 될 수 없다. $\omega + 1$과 $\omega$ 사이에 전단사함수가 존재하기 때문이다. 즉, 서로 다른 두 서수는 같은 기수를 가질 수 있다. 다만 유한서수의 경우는 서수와 기수가 같다.
이 표기를 활용한 유명한 정리가 있다.
Schröder–Bernstein theorem: 두 집합 $A$와 $B$에 대해 $A\to B$와 $B\to A$ 모두 1-1 함수가 존재하면 $A$와 $B$ 사이에는 1-1 대응이 존재하며, $|A| = |B|$라고 쓴다.
여기서 $|A|$과 $|B|$가 각각 $A$와 $B$의 기수이다.
참고.
• 집합 $X$의 기수는 $\mathrm{card}(X)$라고 쓰며, 서수는 $\mathrm{ord}(X)$라고 쓴다.
• 두 정렬집합 $A$, $B$에 대해 다음 중 정확히 하나가 성립한다.
- $A$와 $B$가 순서동형이다.
- $A$가 $B$의 절편과 순서동형이다.
- $B$가 $A$의 절편과 순서동형이다.
• $\mathrm{card}(\mathbb{N}) = \mathrm{card}(\mathbb{Z}) = \mathrm{card}(\mathbb{Q}) = \aleph_0$
여기까지...
이 글 작성에 도움 주신 이보 님께 감사말씀 드립니다.
참고도서: 집합과 수의 체계