[ZFC Set Theory] XII. 칸토어-슈뢰더-베른슈타인 정리 Cantor-Schröder-Bernstein Theorem

[lang-en]To see the previous post[/lang-en][lang-ko]이전 글 보러가기[/lang-ko]

 

[lang-en]As noted in the previous post, we will address the question, "Is the $\leq$ between the cardinality of sets antisymmetric?" The answer is, YES! The answer is, yes! But what does this mean exactly? Formally, this can be stated as: "If $\lvert X \rvert \leq \lvert Y \rvert$ and $\lvert Y \rvert \leq \lvert X \rvert$ for two sets $X$ and $Y$, then $\lvert X \rvert = \lvert Y \rvert$." Intuitively, it makes sense. Intuitively, if a set $X$ is no larger than $Y$, and simultaneously $Y$ is no larger than $X$, then it is reasonable to conclude they are of the same size. However, it is not immediately clear that our definition implies this result. So, we need a proof to confirm this. Let's delve into it below:[/lang-en]

[lang-ko]저번 글에서 언급했듯이, 이번 글에서는 "집합의 농도 간의 $\leq$가 반대칭적인가?"라는 질문에 대해 답을 하려 합니다. 이에 대한 대답은 "그렇다"입니다. 하지만, 이것이 정확히 무슨 의미일까요? 형식적으로, 이는 다음과 같이 쓸 수 있습니다.[/lang-ko]

만일 두 집합 $X$, $Y$에 대해 $\lvert X \rvert \leq \lvert Y \rvert$이고 $\lvert Y \rvert \leq \lvert X \rvert$이면 $\lvert X \rvert = \lvert Y \rvert$이다.

[lang-ko]직관적으로는 당연해보입니다. 만약 집합 $X$가 집합 $Y$보다 크지 않고, 그와 동시에 $Y$가 $X$보다 크지 않다면, 이 둘이 같은 크기를 가지고 있다고 말하는 것이 합리적으로 보입니다. 하지만, 우리의 두 집합의 크기 관계에 대한 정의가 이러한 결론을 이끌어낸다는 사실은 그다지 자명하지 않습니다. 그렇기 때문에 우리는 이 결론을 마음껏 사용하기 위해선 이를 증명할 필요가 있습니다. 아래를 보시죠![/lang-ko]

 

[thm]{1. ([lang-en]Cantor-Schröder-Bernstein Theorem[/lang-en][lang-ko]칸토어-슈뢰더-베른슈타인 정리[/lang-ko])}[lang-en]Let $X$ and $Y$ be sets. If there exist two injective functions $f : X \to Y$ and $g : Y \to X$, then there exists a bijective function $h : X \to Y$.[/lang-en][lang-ko]두 집합 $X$, $Y$를 생각하자. 만일 두 단사 함수 $f : X \to Y$와 $g : Y \to X$가 존재한다면, 전단사 함수 $h : X \to Y$ 역시 존재한다.[/lang-ko][/thm]

 

Proof.

[lang-en]Let $f : X \to Y$ and $g : Y \to X$ be injective functions. And define the sets: $Z_0 = X \setminus g(Y)$ and $Z_{n+1} = g(f(Z_n))$ for $n = 0,1,2,\cdots$, and $\displaystyle Z = \bigcup_{n=0}^{\infty} Z_n$.[/lang-en]

[lang-en]Now, let $h(x) := \begin{cases} f(x) &\mbox{for } x \in Z \\ g^{-1}(x) &\mbox{for } x \in X \setminus Z \end{cases}$. Then $h : X \to Y$ is indeed a function. Now we claim that $h$ is actually bijective.[/lang-en]

[lang-en]To show $h$ is injective, assume $h(x_1) = h(x_2)$.[/lang-en]

[lang-en]If $x_1,x_2 \in Z$, then $f(x_1) = h(x_1) = h(x_2) = f(x_2)$ and hence $x_1 = x_2$ as $f$ is injective.[/lang-en]

[lang-en]If $x_1,x_2 \in X \setminus Z$, then $g^{-1}(x_1) = h(x_1) = h(x_2) = g^{-1}(x_2)$ and hence $x_1 = g(g^{-1}(x_1)) = g(g^{-1}(x_2)) = x_2$.[/lang-en]

[lang-en]If $x_1 \in Z$ and $x_2 \in X \setminus Z$, then $f(x_1) = h(x_1) = h(x_2) = g^{-1}(x_2)$ and thus: $$ x_2 = g(g^{-1}(x_2)) = g(f(x_1)) \in g(f(Z)) = g \left( f \left(\bigcup_{n=0}^{\infty} Z_n \right) \right) = \bigcup_{n=0}^\infty g(f(Z_n)) = \bigcup_{n=1}^\infty Z_n \subset Z. $$ This contradicts $x_2 \in X \setminus Z$.[/lang-en]

[lang-en]Hence, to sum up, we can conclude that $h$ is injective.[/lang-en]

[lang-en]To show $h$ is surjective, let $y \in Y$.[/lang-en]

[lang-en]If $y \in f(Z)$, then there is a $x \in Z$ such that $h(x) = f(x) = y$.[/lang-en]

[lang-en]If $y \in Y \setminus f(Z)$, then $g(y) \notin g(f(Z))$ since $g$ is injective. Now $g(y) \notin g(f(Z)) = \displaystyle \bigcup_{n=1}^\infty Z_n$ but $g(y) \in g(Y)$ and hence $g(y) \notin Z_0 = X \setminus g(Y)$. So together $g(y) \notin Z$ and therefore $h(g(y)) = g^{-1}(g(y)) = y$. So $x=g(y)$ has the property $h(x) = y$.[/lang-en]

[lang-ko]단사 함수 $f : X \to Y$와 $g : Y \to X$를 생각합시다. 그리고 $Z_0 = X \setminus g(Y)$이라 하고, 각 자연수 $n = 0,1,2,\cdots$에 대해 $Z_{n+1} = g(f(Z_n))$이라 합시다. 또한, $\displaystyle Z = \bigcup_{n=0}^{\infty} Z_n$라고 합시다.[/lang-ko]

[lang-ko]이제, $h(x) := \begin{cases} f(x) &\mbox{for } x \in Z \\ g^{-1}(x) &\mbox{for } x \in X \setminus Z \end{cases}$를 정의합시다. 그렇게 되면 $h : X \to Y$는 함수가 됩니다. 이제 $h$가 전단사임을 증명합시다.[/lang-ko]

[lang-ko]$h$가 단사라는 것을 보이기 위해서, $h(x_1) = h(x_2)$라고 가정합시다.[/lang-ko]

[lang-ko]만약 $x_1,x_2 \in Z$라면, $f(x_1) = h(x_1) = h(x_2) = f(x_2)$이므로 $f$가 단사이기 때문에 $x_1 = x_2$가 됩니다.[/lang-ko]

[lang-ko]만약 $x_1,x_2 \in X \setminus Z$라면, $g^{-1}(x_1) = h(x_1) = h(x_2) = g^{-1}(x_2)$이므로 $x_1 = g(g^{-1}(x_1)) = g(g^{-1}(x_2)) = x_2$가 됩니다.[/lang-ko]

[lang-ko]만약 $x_1 \in Z$, $x_2 \in X \setminus Z$라면, $f(x_1) = h(x_1) = h(x_2) = g^{-1}(x_2)$ 이므로 다음과 같습니다. $$x_2 = g(g^{-1}(x_2)) = g(f(x_1)) \in g(f(Z)) = g \left( f \left(\bigcup_{n=0}^{\infty} Z_n \right) \right) = \bigcup_{n=0}^\infty g(f(Z_n)) = \bigcup_{n=1}^\infty Z_n \subset Z.$$ 이는 $x_2 \in X \setminus Z$에 모순입니다.[/lang-ko]

[lang-ko]따라서, $h$가 단사임을 결론지을 수 있습니다.[/lang-ko]

[lang-ko]이제 $h$가 전사라는 것을 보이기 위해, $y \in Y$라고 합시다.[/lang-ko]

[lang-ko]만약 $y \in f(Z)$라면, $x \in Z$가 존재하여 $h(x) = f(x) = y$가 됩니다.[/lang-ko]

[lang-ko]만약 $y \in Y \setminus f(Z)$라면, $g(y) \notin g(f(Z))$인데 이는 $g$가 단사 함수이기 때문입니다. 이제 $g(y) \notin g(f(Z)) = \displaystyle \bigcup_{n=1}^\infty Z_n$이지만 $g(y) \in g(Y)$이므로 $g(y) \notin Z_0 = X \setminus g(Y)$입니다. 따라서 $g(y) \notin Z$이며, $h(g(y)) = g^{-1}(g(y)) = y$가 됩니다. 그러므로, $x=g(y)$는 $h(x) = y$라는 속성을 가지게 됩니다.[/lang-ko]

$\blacksquare$

 

[lang-en]By the theorem above, we can say that $\leq$ between the cardinality of sets is indeed antisymmetric, and thus it is an ordering among the cardinality of sets.[/lang-en]

[lang-ko]위 정리에 의해 집합의 농도 간의 $\leq$가 실제로 반대칭적임을 알 수 있으며, 따라서 집합의 농도 간의 $\leq$가 순서 관계가 됨을 알 수 있습니다.[/lang-ko]

[lang-en]In the next post, we will talk about Cantor's theorem, which implies there are infinitely many infinites. To summarize Cantor's theorem in one sentence, it states "The power set $\mathscr{P}(S)$ of a set $S$ is greater than the set $S$." This means that $\mathscr{P}(\mathbb{N})$ is greater than $\NN$, $\mathscr{P}(\mathscr{P}(\NN))$ is greater than $\mathscr{P}(\NN)$, and so on. Hence, we can conclude there are infinitely many infinites. In the later posts, we will define the cardinal numbers, and address the aleph number, which is a transfinite sequence of the cardinal numbers. And always, thanks for reading.[/lang-en]

[lang-ko]다음 글에서는 칸토어 정리에 대해 다룰 예정입니다. 칸토어 정리의 내용을 한 문장으로 말하자면, "멱집합은 항상 원래 집합보다 크다"로 정리할 수 있습니다. 이는 $\mathscr{P}(\NN)$이 $\NN$보다 크고, $\mathscr{P}(\mathscr{P}(\NN))$이 $\mathscr{P}(\NN)$보다 크고, ...를 의미하며, 따라서 무한히 많은 무한이 존재한다는 결론을 내릴 수 있게 됩니다. 그 이후의 글들에서는 기수를 정의하고, 기수를 나타내는 수열인 알레프 수에 대해 다룰 것으로 보입니다. 그럼, 언제나 그렇듯이, 읽어주셔서 감사합니다.[/lang-ko]

 

[lang-en]To see the next post[/lang-en][lang-ko]다음 글 보러가기[/lang-ko]