Theorem 7.3.3
Claim

Let $C$ be a countable set and let $B$ be any set. If $f:C \to B$ is a 1-1 correspondence, then $B$ is countable.

Proof

Assume that $C$ is a countable set, $B$ is a set, and $f:C \to B$ is a 1-1 correspondence.

Case 1:

Assume $C$ is finite. Then there exist a 1-1 correspondence $g:\{1,2,\dots, k\}\to C$, for some $k$ (by definition of $C$ being finite). So, the composition $(f\circ g)(x):\{1,2,\dots,k\}\to B$ is a 1-1 correspondence (by Theorem 5.2.3). Then $B$ is finite, and therefore, $B$ is countable.

Case 2:

Assume that $C$ is countably infinite. We know that $B$ is also infinite. Since $f:C \to B$ is a 1-1 correspondence, we know that $\text {card } C = \text {card } B$. By the definition of countable we know that $\text {card } C = \text {card } \mathbb {N}$. Since $\text {card } C = \text {card } B$ and $\text {card } C = \text {card } \mathbb {N}$, we can see that $\text {card } B = \text {card } \mathbb {N}$ (by Theorem 7.1.3 part 3). By Definition 7.3.1, $B$ is also countable.

$\blacksquare$


Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License