집합의 기수와 칸토어-슈뢰더-베른슈타인 정리(Cardinal number of set and Cantor-Schröder-Bernstein Theorem)
by Gosamy2023. 11. 26.
반응형
이제 기수를 도입하여 무한집합 사이의 가산집합, 비가산집합에 대해 나눌 것이고, 가산집합의 가부번집합 중에서, 또 비가산집합들 중에서도 무한집합의 크기나 힘의 차이가 있는지를 알아볼 것입니다. 예를 들어 자연수 집합보다 작은 가부번집합이 있을까요? 실수 집합보다 큰 비가산집합이 있을까요? 유리수보다는 클 것 같고 실수보다는 작을 것 같은 무한집합이 있을까요? 이러한 답을 찾아보기 위해 기수라는 개념이 필요합니다.
1. 기수의 정의와 공리
정의($S.T$) 4-4) 기수의 공리 집합 $A$ 에 대한 '기수(cardinal number or cardinality)'는 다음의 공리를 만족시키는 수로 정의한다. A1) 모든 집합 $A$ 는 그 집합 자신에 부여되는 기수를 부여받고, $\mathrm{Card}A$ 또는 $\left| A \right|$[각주:1] 로 표기한다. 반대로 모든 기수 $a$ 는 $a$ 를 기수로 갖는 집합 $A$가 하나 존재하며, $\left| A \right|=a$ 로 표기한다. A2) $A=\phi \;\Leftrightarrow \; \left| A \right|=0$ A3) $\phi\neq A$ 가 유한집합일 때, $A\sim \left\{ 1,2,\cdots , k \right\}\;\Leftrightarrow\;$ 이면 $\left| A \right|=k$ 이다. A4) 임의의 두 집합 $A,B$ 에 대하여 $A\sim B\;\Leftrightarrow \;\left| A \right|=\left| B \right|$
정의($S.T$) 4-5) 기수의 종류 유한집합의 기수는 '유한기수(finite cardinal number)'라 하고 무한집합의 기수는 '초한기수(超限, transfinite cardinal number)'라고 한다.
'기수(基數)'는 순서를 나타내는 '서수(序數)'와 달리 일반적으로 양을 셀 때 사용하는 숫자를 말합니다. 한 개, 두 개, 세 개, 할 때 하나, 둘, 셋이라 할 수 있습니다. 'Cardinal'은 원래 영어에서도 기수를 의미하는 바로 쓰이고 명사형으로 보면 'cardinality'가 됩니다.
무한집합에 대한 논의를 하다 보면 '셀 수 있다(countable)'을 정의할 때 가부번성을 언급했습니다. 즉 무한집합이 가부번이면 셀 수 있다고 정의한다는 것입니다. 물론 여기서 센다는 개념은 일대일대응을 말하는 것이고 실제 노가다로 일일히 다 세어 본다는 것은 아닙니다. 그래서, 말은 '셀 수 있다'고 하지만 실제로 무한집합의 원소 갯수를 전부 세는 것은 아닌데, 기수에 대한 논의를 계속 하다 보면 뒤에서 기수가 서로 다른 무한집합에 대한 논의를 하게 됩니다. 이미 이전 글에서 알아보았지만 자연수 집합은 실수 집합과 일대일대응을 할 수 없어서 대등하지 않고, 따라서 기수가 다릅니다. 하지만 둘 다 무한집합이지요. 이러한 점에서, 같은 무한집합이긴 하지만 가부번적 특징이 다르다, 곧 기수의 관점에서는 특징이 다르기 때문에 (무한)집합에도 우열이 있다는 관점에서 집합의 '농도'가 다르다는 표현을 하기도 합니다. 그래서 cardinality 를 '농도'로 번역하는 경우도 있습니다.
기수에 대해 우리가 주로 다루는 것은 유한집합이나 공집합이 아니고, 무한집합에 대한 것입니다. 따라서 이 중 A1)~A3) 은 비교적 당연하게 받아들일 수 있는 내용이라 A4) 에 집중해 주시기 바랍니다.
정의($S.T$) 4-6) 기수의 대소관계 두 집합 $A,B$ 가 있고 두 집합의 임의의 부분집합을 각각 $C\subseteq A$, $D\subseteq B$ 라 하자. ① $A\sim D$ 이지만 $B\nsim C$ 인 경우 $B$ 의 기수는 $A$ 의 기수보다 크다고 표현하거나 $A$ 의 기수는 $B$ 의 기수보다 작다고 말한다. 즉 $A$ 가 $B$ 의 어느 하나의 부분집합과 대등하지만 $B$ 는 $A$ 의 어떤 부분집합과도 대등하지 않은 경우를 말한다. 이를 $\left| A \right|<\left| B \right|$ 라 표기한다. ② $A$ 의 기수가 $B$ 의 기수보다 작거나 같을 조건, 즉 $\left| A \right| \leq \left| B \right|$ 일 조건은 $A$ 가 $D\subseteq B$ 와 대등한 것, 곧 $A\sim D$ 인 것이다.
정리하면 다음과 같습니다.
1) $A\sim B\;\;\Rightarrow \;\;\left| A \right|=\left| B \right|$ 2) $A\sim D\subseteq B \;\; \Rightarrow \;\; \left| A \right| \leq \left| B \right|$ 3) $A\sim D\subseteq B$ 그리고 $B\nsim C\subseteq A \;\; \Rightarrow \;\; \left| A \right| < \left| B \right|$
$\mathbb{N}\subseteq \mathbb{R}$ 임을 고려하면, $\mathbb{N}$ 은 $\mathbb{R}$ 의 부분집합인 $\mathbb{N}$ 과 대등하다. 그런데 $\mathbb{R}$ 은 비가부번집합이기 때문에 $\mathbb{N}\nsim \mathbb{R}$ 이고, 따라서 임의의 $C\subseteq \mathbb{N}$ 과도 대등하지 않다. 그러므로 위 정의에 의하여 $\left| \mathbb{N} \right| < \left| \mathbb{R} \right|$ 이다. $_\blacksquare$
2. 칸토어-슈뢰더-베른슈타인 정리
그 다음으로는 기수에 대해 일반적인 숫자와 같은 관계가 성립하는지를 볼 것입니다. 일반적으로 두 실수 사이에서는 $x,y,\in\mathbb{R}$ 에 대해 $x\leq y \;\; \wedge \;\; y\leq x$ 이면 $x=y$ 가 당연히 성립합니다. 하지만 기수의 관계에서
$$\left| A \right| \leq \left| B \right|\;\wedge \; \left| B \right| \leq \left| A \right|\;\;\Rightarrow \;\; \left| A \right| =\left| B \right|$$
가 항상 성립할까요? 당연히 그럴 것이라고 생각하는 것은 문제가 있는데, 기수라는 것이 무한대의 개념을 가질 수가 있기 때문입니다. 무한대의 관계 상에서 이것이 성립하는지는 증명을 반드시 해야 한다는 것입니다. 실제로 이 명제는 참이며, 이를 증명할 것이고 그 전에 보조정리를 보일 필요가 있습니다.
보조정리($S.T$) 4.1) 집합 $X,Y$ 에 대해 $Y\subseteq X$ 라 하자. 만일 단사함수인 $f:X\rightarrow Y$ 가 존재하면, 전단사함수 $h:X\sim Y$ 또한 존재한다.[각주:2]
여기서 주의할 점이 있다. 만일 $Y\subseteq X$ 이고 $X,Y$ 가 무한집합이면, 단사함수 $f:Y\rightarrow X$ 는 반드시 존재한다.[각주:3] 하지만 이 보조정리에서 말하는 $f:X\rightarrow Y$ 는 존재할 수도, 존재하지 않을 수도 있으므로 존재한다면 전단사함수 $h:X\rightarrow Y$ 가 존재한다는 논리이다.
증명) 1) $X=Y$ : 항등함수를 택하면 항등함수는 단사이고 전단사이니 주어진 명제가 성립한다.
2) $X\subset Y$ : $Y$ 가 $X$ 의 진부분집합인 경우를 고려해보자. 즉 $X-Y\neq \phi$ 이다.
그리고 $C:=\displaystyle \bigcup_{n\geq 0}^{}f^n(X-Y)\;,\;n\in\mathbb{N}$ 이라는 함수를 정의하고 싶은데, 여기서 $n=0$ 일 때는 $f^0 : X\rightarrow X$ 를 항등함수로 생각하고, $n\geq 1$ 일 때는 $f^k:f\circ f^{k-1}$ 로 생각한다. 그러면 $X-Y=I(X-Y)=f^0(X-Y)\subseteq \displaystyle \bigcup_{n\geq 0}^{}f^n(X-Y)=C$ 이 되고,
$$\begin{align*} f(C)&=f\left( \displaystyle \bigcup_{n\geq 0}^{}f^n(X-Y) \right) \\\\&=\displaystyle \bigcup_{n\geq 0}^{}f\left( f^n(X-Y) \right) \\\\&=\displaystyle \bigcup_{n\geq 0}^{} f^{n+1}(X-Y) \\\\&=\displaystyle \bigcup_{n\geq 1}^{} f^{n}(X-Y)\subseteq \displaystyle \bigcup_{n\geq 0}^{} f^{n}(X-Y) =C \end{align*}$$ 이므로 $f(C)\subseteq C$ 또한 성립한다. 그러면 이제 $m,n\in\mathbb{N}\cup \left\{ 0 \right\}$ 이고 $n<m$ 에 대해
$$f^m(A-B)\cap f^n(A-B)=\phi$$ 가 성립함을 보이고 싶다. (이것을 구체적으로 증명하기 전에, 아래 그림을 참고하자. 직관적으로 생각하면 $f$ 는 단사함수이기 때문에, 처음 노란색$=X-Y$ 를 $f$ 로 보낸 것이 주황색$=f(X-Y)$ 이고, 다시 주황색을 정의역으로서 $f$ 로 보내면 파란색$=f^2(X-Y)$ 가 되며, 다시 파란색을 정의역으로서 $f$ 를 통해 보내면 초록색$=f^3(X-Y)$ 가 된다. 그래서 $n < m$ 에 대해 합성의 횟수가 다르면 그들의 치역의 교집합이 0이다.)
[그림 1] 이 그림을 통해 우선 쉽게 이해하는 것을 추천합니다. 구체적으로 증명하려면 $f^m(A-B)\cap f^n(A-B)\neq\phi$ 이라고 가정하자. $x,x'\in \left( f^m(A-B)\cap f^n(A-B) \right)$ 가 존재하고 $f^m(x)=f^n(x')$ 이라 가정하자. 그러면 $f$ 가 단사이므로,
그런데 마지막 줄에서 $x\in X-Y$ 이고, $f^{m-n}(x') \in Y$ 인데, $f^{m-n}(x')\in \left[ (X-Y)\cap Y \right]$ 일 수는 없다.[각주:4] 그러므로 모순이다.
[그림 2] 치역들의 집합과 $X,Y,C$ 의 관계. 그림을 통해 생각하면 어렵지 않습니다. 이제 우리가 전단사함수임을 보이기 위한 함수 $h$ 를
$$h(z) = \left\{ \begin{array}{cl} f(z) &\;\;( z\in C) \\ z & \;\;(z\in X-C) \end{array} \right.$$ 와 같이 정의하자. 그러면 $z\in C$ 일 때 $f$ 는 단사함수이므로 $h$ 도 단사가 되고, $z\in A-C$ 면 그냥 항등함수이니 자명하게 단사이다. 즉 $h$ 는 단사다. 반면 $h$ 가 전사임을 보이기 위해서 다음을 확인한다.
$$\begin{align*} h(X)&=(X-C)\cup f(C) \\\\&=\left( X-\displaystyle \bigcup_{n\geq 0}^{}f^n(X-Y) \right)\cup f\left( \displaystyle \bigcup_{n\geq 0}^{}f^n(X-Y) \right) \\\\&=\left( X-\displaystyle \bigcup_{n\geq 0}^{}f^n(X-Y) \right)\cup \left( \displaystyle \bigcup_{n\geq 1}^{}f^n(X-Y) \right) \\\\& =X-(X-Y)=Y \end{align*}$$ 따라서 $h(X)=Y$ 가 되므로 $h$는 전사이다. 고로 전단사함수인 $h$ 가 존재한다. $_\blacksquare$
정리($S.T$) 4.17) 칸토어-슈뢰더-베른슈타인 정리(Cantor-Schröder-Bernstein Theorem) 집합 $A,B$ 에 대하여 $A$ 가 $B$ 의 부분집합과 대등하고 $B$ 도 $A$ 의 부분집합과 대등한 경우, $A\sim B$ 이다.
따름정리($S.T$) 4.17.1) $\left| A \right| \leq \left| B \right|\;\wedge \; \left| B \right| \leq \left| A \right|\;\;\Rightarrow \;\; \left| A \right| =\left| B \right|$
따름정리($S.T$) 4.17.2) 함수 $f:A\rightarrow B$ 가 단사인 것은 $\left| A \right|\leq \left| B \right|$ 인 것과 필요충분조건이다.
증명) $A$ 와 $B$ 각각의 한 부분집합을 $A_0, B_0$ 라 하고 $A\sim B_0$ 이고 $B\sim A_0$ 라 하자. 그러면 두 전단사함수 $f_0:A\sim B_0\;,\; g_0:B\sim A_0$ 가 존재한다. 함수 $f:A\rightarrow A_0$ 를 $f(x)=g_0(f_0(x))$ 와 같이 정의하면, $f_0,g_0$ 는 모두 전단사이므로 $g_0\circ f_0$ 는 단사이다.[각주:5] 그런데, 보조정리($S.T$) 4.1) 에 의하면 이 경우 단사함수가 존재하면 전단사함수 $h:A\sim A_0$ 가 존재한다고 말할 수 있다. 따라서 $g_0^{-1}\circ h = A\sim A_0\sim B$ 은 전단사이고, $A\sim B$ 이므로 주어진 명제가 성립한다. $_\blacksquare$
첫 번째 따름정리의 증명은 기수의 크고 작음에 관한 정의와 이 정리로부터 바로 도출된다. $_\blacksquare$
두 번째 따름정리의 증명)
1) $\Rightarrow $ : $f:A\rightarrow B$ 가 단사라 가정하자. 그러면 $A\sim f(A)\subseteq B$, 즉 $A$ 와 $B$ 의 한 부분집합과 일대일대응인 함수 $f$ 를 만들 수 있으므로 정의($S.T$) 4-6)-② 에 의하여 $\left| A \right|\leq \left| B \right|$ 가 성립한다.
2) $\Leftarrow $ : $\left| A \right|\leq \left| B \right|$ 라 가정하자. 그러면 $D\subseteq B$ 인 $D$ 와 $A$ 가 대등하다는 것이다. 즉 어떤 전단사 함수 $g:A\sim D\subseteq B$ 가 존재한다. 전단사함수의 공역을 확장하여[각주:6] $B$ 로 바꾸면, 함수 $g' : A\rightarrow B$ 는 단사가 된다. 따라서 $A$ 에서 $B$ 로 가는 단사함수가 존재한다. $_\blacksquare$
두 번째 따름정리는 굉장히 중요하고, 기수의 대소관계를 파악하기에 신선한 관점을 선사합니다. 특히 이후에 정리($S.T$) 4.25) 를 증명할 때 부등호의 양 방향을 두 번 증명함으로서 등식을 보이게 되는 경우 매우 강력한 도구가 됩니다.
[참고문헌]
You-Feng Lin, Shwu-Yeng T,Lin - Set thoery
이 블로그에서는 기수를 나타낼 때 $\mathrm{Card}$ 보다는 절댓값 기호를 사용할 것입니다. 물론 후자는 집합에다가 씌우면 기수를 나타내는 기호지 절댓값을 의미하는 기호는 아닙니다. 집합론이나 해석개론에서는 보통 전자의 기호를 좀 더 많이 사용하는 듯 하나, 대수학에서는 라그랑주 정리나 잉여류(cosets), 클래스 방정식(Class equation - 여기서의 'class'는 동치류(equivalence class)의 그 class 와 유사합니다) 등을 따질 때 등 군 이론(Group theory) 에서 전자의 기호를 쓰면 매우 불편해져서 후자의 기호를 쓸 일이 매우 많습니다. [본문으로]
댓글