[ZFC Set Theory] XI. 집합의 농도 Cardinality of Sets

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

 

[lang-en]In this post, we will talk about the cardinality of sets. The cardinality of a set is a kind of the "size" of a set, intuitively. We can compare the sizes of two sets using the concept of cardinality. The formal definition of cardinality is as follows:[/lang-en]

[lang-ko]이번 글에서는 집합의 농도에 대한 이야기를 해보려 합니다. 집합의 농도는 직관적으로 생각할 때에는 집합의 크기 같은 개념이라고 생각할 수 있으며, 이 농도의 개념을 이용하여 두 집합 사이의 크기를 비교할 수 있습니다. 아래는 집합의 농도의 형식적인 정의입니다.[/lang-ko]

 

[def]{1. ([lang-en]Cardinality of Sets[/lang-en][lang-ko]집합의 농도[/lang-ko])}[lang-en]Let $X$ and $Y$ be sets. If there exists a bijection $f : X \to Y$, then we say $X$ and $Y$ have the same $cardinality$, and we denote it by $\lvert X \rvert = \lvert Y \rvert$.
If there exists an injection $f : X \to Y$, then we say that the cardinality of $X$ is less than or equal to the one of $Y$, or the cardinality of $Y$ is greater than or equal to the one of $X$, and we denote it by $\lvert X \rvert \leq \lvert Y \rvert$ or $\lvert Y \rvert \geq \lvert X \rvert$.
Also, if $\lvert X \lvert \leq \lvert Y \rvert$ and $\lvert X \rvert \neq \lvert Y \rvert$, then we say the cardinality of $X$ is less than the one of $Y$, or the cardinality of $Y$ is greater than the one of $X$, and we denote it by $\lvert X \rvert < \lvert Y \rvert$ or $\lvert Y \rvert > \lvert X \rvert$.[/lang-en][lang-ko]두 집합 $X$, $Y$를 생각하자. 만일 전단사 함수 $f : X \to Y$가 존재한다면 $X$와 $Y$의 농도가 같다고 말하며, 이를 $\lvert X \rvert = \lvert Y \rvert$와 같이 쓴다.
만약 단사 함수 $f : X \to Y$가 존재한다면 $X$의 농도가 $Y$의 농도보다 작거나 같다, 또는 $Y$의 농도가 $X$의 농도보다 크거나 같다고 말하며, 이를 $\lvert X \rvert \leq \lvert Y \rvert$ 또는 $\lvert Y \rvert \geq \lvert X \rvert$와 같이 쓴다.
또한, 만일 $\lvert X \rvert \leq \lvert Y \rvert$이고 $\lvert X \rvert \neq \lvert Y \rvert$이면, $X$의 농도가 $Y$의 농도보다 작다, 또는 $Y$의 농도가 $X$의 농도보다 크다고 말하며, 이를 $\lvert X \rvert < \lvert Y \rvert$ 또는 $\lvert Y \rvert > \lvert X \rvert$와 같이 쓴다.[/lang-ko][/def]

 

[lang-en]The below are the properties of the cardinality of sets:[/lang-en]

[lang-ko]아래는 집합의 농도의 성질입니다.[/lang-ko]

 

[thm]{2.}[lang-en]The following hold:[/lang-en][lang-ko]다음이 성립한다.[/lang-ko]
1. [lang-en]The equality between the cardinality is an equivalence relation.[/lang-en][lang-ko]농도 간의 등호는 동치 관계이다.[/lang-ko]
2. [lang-en]The $\leq$ between the cardinality is reflexive and transitive.[/lang-en][lang-ko]농도 간의 등호를 포함한 부등호는 반사적이고 추이적이다.[/lang-ko]
3. [lang-en]Let $X$ and $Y$ be nonempty sets. Then $\lvert X \rvert \leq \lvert Y \rvert$ if and only if there exists a surjection $f : Y \to X$.[/lang-en][lang-ko]두 비어있지 않은 집합 $X$, $Y$를 생각하자. 그러면 $\lvert X \rvert \leq \lvert Y \rvert$와 전사 함수 $f : Y \to X$가 존재하는 것은 필요충분조건이다.[/lang-ko][/thm]

 

Proof.

Part 1. [lang-en]Let $X$, $Y$, and $Z$ be sets.[/lang-en][lang-ko]세 집합 $X$, $Y$, $Z$를 생각합시다.[/lang-ko]

[lang-en]First, since the identity function on a set $X$ is a bijection, $\lvert X \rvert = \lvert X \rvert$.[/lang-en]

[lang-ko]먼저, 집합 $X$ 위의 항등 함수는 전단사 함수이므로 $\lvert X \rvert = \lvert X \rvert$가 성립합니다.[/lang-ko]

[lang-en]Secondly, let $\lvert X \rvert = \lvert Y \rvert$. Then, there exists a bijection $f : X \to Y$. Since the inverse $f^{-1}$ of $f$ is a bijection, $\lvert Y \rvert = \lvert X \rvert$.[/lang-en]

[lang-ko]이번에는 $\lvert X \rvert = \lvert Y \rvert$라고 가정합시다. 그러면 전단사 함수 $f : X \to Y$가 존재하며, $f$의 역함수 $f^{-1}$가 전단사 함수이므로 $\lvert Y \rvert = \lvert X \rvert$가 성립합니다.[/lang-ko]

[lang-en]Finally, let $\lvert X \rvert = \lvert Y \rvert$ and $\lvert Y \rvert = \lvert Z \rvert$. Then, there exist bijections $f : X \to Y$ and $g : Y \to Z$. Then, their composition $g \circ f$ is also a bijection, and thus $\lvert X \rvert = \lvert Z \rvert$.[/lang-en]

[lang-ko]마지막으로, $\lvert X \rvert = \lvert Y \rvert$이고 $\lvert Y \rvert = \lvert Z \rvert$라고 가정합시다. 그러면 전단사 함수 $f : X \to Y$와 $g : Y \to Z$가 존재하며, 이들의 합성 $g \circ f$ 역시 전단사 함수이므로 $\lvert X \rvert = \lvert Z \rvert$가 성립합니다.[/lang-ko]

[lang-en]Therefore, the equality between the cardinality is an equivalence relation.[/lang-en]

[lang-ko]따라서, 농도 간의 등호는 동치 관계입니다.[/lang-ko]

Part 2. [lang-en]Let $X$, $Y$, $Z$ be sets.[/lang-en][lang-ko]세 집합 $X$, $Y$, $Z$를 생각합시다.[/lang-ko]

[lang-en]First, since the identity function on a set $X$ is bijection, it is injective, indeed, and thus $\lvert X \rvert \leq \lvert X \rvert$.[/lang-en]

[lang-ko]먼저, 집합 $X$ 위의 항등 함수는 전단사 함수이므로, 단사 함수 $X \to X$가 존재하며, 따라서 $\lvert X \rvert \leq \lvert X \rvert$가 성립합니다.[/lang-ko]

[lang-en]Secondly, let $\lvert X \rvert \leq \lvert Y \rvert$ and $\lvert Y \rvert \leq \lvert Z \rvert$. Then, there exist injections $f : X \to Y$ and $g : Y \to Z$. Compositing them, we obtain a injective map $g \circ f : X \to Z$ and thus $\lvert X \rvert \leq \lvert Z \rvert$.[/lang-en]

[lang-ko]이제 $\lvert X \rvert \leq \lvert Y \rvert$이고 $\lvert Y \rvert \leq \lvert Z \rvert$라고 가정합시다. 그러면 단사 함수 $f : X \to Y$와 $g : Y \to Z$가 존재합니다. 두 단사 함수의 합성은 단사 함수이므로 $g \circ f : X \to Z$는 단사 함수이며, 따라서 $\lvert X \rvert \leq \lvert Z \rvert$가 성립합니다.[/lang-ko]

Part 3. [lang-en]Let $X$ and $Y$ be sets.[/lang-en][lang-ko]두 집합 $X$, $Y$를 생각합시다.[/lang-ko]

[lang-en]First, let $\lvert X \rvert \leq \lvert Y \rvert$. Then there exists an injection $f : X \to Y$. Hence, for any $y \in f(X)$, there exists a unique element $x \in X$ such that $f(x) = y$. Now, since $X$ is nonempty, we can take an element $x_0 \in X$. Consider a function $g : Y \to X$ defined as: $$ g(y) = \begin{cases} x & \mbox{if } f(x) = y \\ x_0 & \mbox{if } x \notin f(X). \end{cases} $$ Then $g$ is surjective, obviously.[/lang-en]

[lang-ko]먼저 $\lvert X \rvert \leq \lvert Y \rvert$라고 합시다. 그러면 단사 함수 $f : X \to Y$가 존재합니다. 그러므로 각 $y \in f(X)$에 대해 $f(x) = y$인 $x \in X$가 유일하게 존재합니다. $X$가 비어있지 않으므로 $x_0 \in X$를 하나 잡을 수 있으며, 따라서 다음과 같이 정의되는 함수 $g : Y \to X$를 생각할 수 있습니다. $$ g(y) = \begin{cases} x & \mbox{if } f(x) = y \\ x_0 & \mbox{if } x \notin f(X) \end{cases} $$ 위와 같이 정의한 $g$가 전사 함수임은 쉽게 알 수 있습니다.[/lang-ko]

[lang-en]Conversely, suppose that there exists a surjection $f : Y \to X$. Then, for any $x \in X$, there exists a $y \in Y$ such that $f(y) = x$. Hence, by the axiom ob choice, we can take a function $g : X \to Y$ such that $f(g(x)) = x$ for each $x \in X$ since each $f^{-1}(x)$ is nonempty. Indeed, the $g$ is injective.[/lang-en]

[lang-ko]이번에는 반대로 전사 함수 $f : Y \to X$가 존재한다고 합시다. 그러면 각 $x \in X$에 대하여 $f(y) = x$이도록 하는 $y \in Y$가 하나 이상은 존재합니다. 따라서 선택 공리에 의해, 임의의 $x \in X$에 대해 $f(g(x)) = x$이도록 하는 함수 $g : X \to Y$가 존재하며, 이 $g$가 단사 함수임은 어렵지 않게 보일 수 있습니다.[/lang-ko]

$\blacksquare$

 

[lang-en]Now, by [href]Theorem 2[/href], we can think the $\leq$ between the cardinality of sets as an ordering if it is antisymmetric. So, it is natural to ask if the $\leq$ between the cardinality of sets is antisymmetric. We will cover this in the next post. And always, thanks for reading.[/lang-en]

[lang-ko][href]Theorem 2[/href]에 의해, 만일 농도 간의 등호를 포함한 부등호가 반대칭적이라면, 이는 일종의 순서관계라는 말을 할 수 있게 됩니다. 그렇기에 농도 간의 등호를 포함한 부등호가 반대칭적인지를 묻는 것은 굉장히 자연스러운 질문이라고 할 수 있습니다. 이 질문에 대한 답은 다음 글에서 다룰 예정입니다. 항상 그렇듯이, 읽어주셔서 감사합니다.[/lang-ko]

 

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