##### 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$

There are quite a few ways to approach this problem. Here's one way. Consider two cases:

In case 1, there exists a 1-1 correspondence $g: \{1,2,\dots,k\}\to C$ for some $k$ (by definition of $C$ being finite). Consider the composition $f\circ g: \{1,2,\dots, k\}\to B$ and take a look at Theorem 5.2.3. Conclude that $B$ is finite and hence countable.

In case 2, there exists a 1-1 correspondence $g: \mathbb{N}\to C$ (since $\mathbb{N}$ and $C$ have same cardinality). Again consider the composition $f\circ g$ and argue similar to case 1, except you will conclude that $B$ is countably infinite.

ReplyOptions