집합론, 그 스물두 번째 이야기 | 기수 ( Cardinal Numbers )

기수는 집합의 크기를 쉽게 비교하기 위하여 고안된 체계이며, 유한 집합은 단순히 원소의 개수를 세는 것만으로도 크기를 비교할 수 있지만, 무한 집합의 경우에는 원소의 개수를 세는 일이 불가능해지기 때문에 이와 같은 방법으로 크기를 비교하는 것이 곤란하다. 그래서 우리는 기수라는 것을 새롭게 정의하게 된다. 기수의 정의는 다음과 같다.

 

집합 $X$의 크기를 나타내는 기수 $|X|$는 다음과 같이 정의된다. $$|X|=\text{min}\{\alpha\in\text{Ord}\;|\;\exists f:X\to\alpha\;\text{s.t.}\;f\text{ is bijective}\}$$

 

위와 같이 정의된 모든 기수의 모임을 $\text{Card}$로 나타낸다. 서수의 고유 모임은 정렬 순서를 갖추었으므로 서수를 원소로 가지는 집합에는 언제나 최소값이 유일하게 존재한다. 따라서 위의 정의는 잘 정의(well-defined)된다. 또한, 기수의 정의에 의해 임의의 기수의 크기를 나타내는 기수는 자기자신이다. 그렇다면 이렇게 정의된 기수를 어떻게 활용할 수 있을까? 이에 대해 알아보기 위해 다음 두 정리에 대해 알아보자.

 

Theorem 1. 어떤 두 집합의 크기를 나타내는 기수가 같다면 두 집합의 크기는 같고 그 역도 성립한다.

 

Part 1.

두 집합 $X$와 $Y$의 크기를 나타내는 기수가 $\alpha$라고 하자. 그러면 기수의 정의에 의해 전단사함수 $f:X\to\alpha$와 $g:Y\to\alpha$가 존재한다. 이때, 함수 $g$가 전단사함수이므로 역함수 $g^{-1}$가 존재한다. 그러면 $g^{-1}\circ f$는 $X$에서 $Y$로 가는 전단사함수이다. 따라서 집합 $X$와 집합 $Y$의 크기는 같다.
$\blacksquare$

 

Part 2.

두 집합 $X$와 $Y$의 크기가 같고 집합 $X$의 크기를 나타내는 기수가 $\alpha$, 집합 $Y$의 크기를 나타내는 기수가 $\beta$라고 하자. 그러면 기수의 정의에 의해 전단사함수 $f:X\to\alpha$와 $g:Y\to\beta$가 존재하며, 두 집합 $X$와 $Y$의 크기가 같으므로 둘 사이의 전단사함수 $h:X\to Y$ 역시 존재한다. 그러면 $g\circ h$가 $X$에서 $\beta$로 가는 전단사함수임은 자명하다. 따라서 $X$와 $\beta$ 사이의 전단사함수가 존재하며, 기수의 정의로부터 $\alpha\leq\beta$임을 얻을 수 있다. 또한, 같은 방법으로 $\beta\leq\alpha$임을 보일 수 있다. 따라서 $\alpha=\beta$임이 보여졌다.
$\blacksquare$

 

Theorem 2. 어떤 두 집합의 크기를 나타내는 기수의 순서관계는 두 집합의 크기의 순서관계와 같다.

 

Part 1.

두 집합 $X$와 $Y$의 크기를 나타내는 기수가 각각 $\alpha$, $\beta$라고 하고 함수 $f:X\to\alpha$와 $g:Y\to\beta$를 전단사함수라고 하자. 또한, 단사함수 $h:X\to Y$가 존재한다고 하자. 이때, 만약 두 집합 $X$와 $Y$ 사이에 전단사함수가 존재한다면 $\alpha\leq\beta$가 됨은 Theorem 1에 의해 자명하다. 그러니 둘 사이에는 전단사함수가 존재하지 않는다고 가정하자. 함수 $g\circ h\circ f^{-1}$는 $\alpha$에서 $\beta$로 가는 단사함수이다. 만약 $\beta$에서 $\alpha$로 가는 단사함수가 존재한다면 칸토어-베른슈타인 정리에 의해 $\alpha$에서 $\beta$로 가는 전단사함수가 존재한다. 그러면 Theorem 1에 의해 두 집합 $X$와 $Y$ 사이의 전단사함수가 존재하며, 이는 두 집합 사이의 전단사함수가 존재하지 않는다는 가정에 모순이다. 따라서 $\beta$에서 $\alpha$로 가는 단사함수는 존재하지 않는다. 이때, 만약 $\beta<\alpha$라면 함수 $I:x\mapsto x$가 $\beta$에서 $\alpha$로 가는 단사함수가 되어 위의 사실과 모순이다. 따라서 $\beta<\alpha$일 수 없으며, 서수는 정렬 순서를 가지므로 $\alpha\leq\beta$가 성립한다.
$\blacksquare$

 

Part 2.

두 집합 $X$와 $Y$의 크기를 나타내는 기수가 각각 $\alpha$, $\beta$라고 하고 함수 $f:X\to\alpha$와 $g:Y\to\beta$를 전단사함수라고 하자. 만약 $\alpha\leq\beta$가 성립한다면 함수 $I:x\mapsto x$는 $\alpha$에서 $\beta$로 가는 단사함수가 된다. 이때, $g^{-1}\circ I\circ f$가 $X$에서 $Y$로 가는 단사함수가 되므로 $X$에서 $Y$로 가는 단사함수가 존재한다.
$\blacksquare$

 

위의 두 정리로부터 우리는 두 집합 사이의 함수를 잡지 않고 단순히 두 집합의 크기를 나타내는 기수를 비교하는 것만으로도 두 집합의 크기를 비교할 수 있게 되었다. 또한, 기수 역시 서수와 같이 연산을 정의할 수 있는데, 기수의 연산은 아래와 같이 정의된다.

 

따름 기수

따름 기수란, 바로 그 다음 기수를 의미한다. 기수 $\kappa$의 따름 기수는 $\kappa^+$로 나타내며, 유한기수의 경우엔 해당 기수의 따름 서수를 따름 기수로 정의하면 되지만, 무한 기수의 경우, 따름 서수가 기수가 아니게 되므로 해당 정의를 사용할 수 없다. 따라서 다음과 같은 정의를 사용한다.

 

$$\kappa^+=|\text{inf}\{\lambda\in\text{Ord}\;|\;\kappa<|\lambda|\}|$$

 

하르톡스 정리(Hartog's Theorem)에 의해 어떤 기수보다 더 큰 기수의 존재성이 보장되며, 서수는 정렬 순서를 가지므로 서수의 모임의 하한 역시 잘 정의된다. 따라서 위와 같은 정의는 잘 정의된다.

 

따름 기수의 성질

임의의 기수 $\kappa$에 대해 항상 다음 명제가 성립한다.

 

$$\nexists\lambda\in\text{Card} \; \text{s.t.}\; \kappa<\lambda<\kappa^+$$

 

이 명제는 귀류법을 이용하여 간단하게 증명할 수 있다.

 

Proof.

만약 $\kappa<\lambda<\kappa^+$를 만족하는 기수 $\lambda$가 존재한다면, $\lambda$는 집합 $\{\mu\in\text{Ord}\;|\;\kappa<|\mu|\}$의 원소가 된다. 따라서 $\text{inf}\{\mu\in\text{Ord}\;|\;\kappa<|\mu|\}\leq\lambda$가 성립한다. 이제 우리는 $\kappa^+$의 정의로부터 $\kappa^+\leq\lambda$가 성립함을 알 수 있다. 그런데 이는 처음의 $\lambda<\kappa^+$라는 가정에 모순되므로 이러한 $\lambda$는 존재할 수 없다.

$\blacksquare$

 

기수의 연산

임의의 두 기수 $\kappa$와 $\lambda$에 대해 두 기수의 연산은 다음과 같이 정의된다. 단, 집합 $A$, $B$에 대해 $|A|=\kappa$, $|B|=\lambda$가 성립한다.

 

1. 덧셈: $$\kappa+\lambda=|A\sqcup B|$$ 2. 곱셈: $$\kappa\lambda=|A\times B|$$ 3. 거듭제곱: $$\kappa^{\lambda}=|\{f:B\to A\;|\;f\text{ is a function}\}|$$

 

위 연산의 성질은 다음 글에서 소개하도록 하겠다.

기수의 산술 연산의 성질

 

추가로, 기수는 한 가지 성질을 더 가지는데, 서수의 정렬성에 의해 임의의 두 기수 $\kappa$, $\lambda$에 대해 항상 다음 3가지 중 하나가 성립한다.

 

1. $\kappa=\lambda$ 2. $\kappa<\lambda$ 3. $\kappa>\lambda$

 

이를 기수의 삼분성이라 하며, 이로부터 임의의 두 집합 $A$, $B$에 대해서도 삼분성이 성립함을 알 수 있다.