##### Claim

Let $f:\mathbb{N}\to X$ be an onto function. Then $X$ is countable.

##### Proof

Let $f:\mathbb{N}\to X$ be an onto function. For each $x \in X$, choose exactly one $n_x \in \mathbb{N}$ such that $f(n_x)=x$.

Because $f$ is a function, we know that $f(n_x)\neq f(n_y)$ whenever $x \neq y$. Now, we define the set $N' \subseteq \mathbb{N}$ via

Because $N' \subseteq \mathbb{N}$, $N'$ is countable (by Theorem 7.3.4). Now we define the function $g: N' \to X$ via

(2)By construction, it is clear that $g$ is onto. Let $n_x, n_y \in N'$ and assume $g(n_x)=g(n_y)$. Since we chose a unique point in $f^{-1}(\{x\})$, it must be the case that $n_x=n_y$. Thus, $g$ is 1-1. This means that $g: N' \to X$ is a 1-1 correspondence, and by Theorem 7.3.3, $X$ is countable.

$\blacksquare$

For each $x\in X$, choose exactly one $n_x\in\mathbb{N}$ such that $f(n_x)=x$. We know that we can do this since $f$ is onto. Also, since $f$ is a function, we know that $f(n_x)\neq f(n_y)$ whenever $x\neq y$. Now, define the set $N'\subseteq \mathbb{N}$ via

(1)What does Theorem 7.3.4 tell us about $N'$? Next, define the function $g: N'\to X$ via $g(n_x)=x$. Is $g$ onto? How about 1-1? What does Theorem 7.3.3 tell us?

ReplyOptions