Theorem 7.3.5
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

(1)
\begin{align} N'= \{n_x: x\in X \}. \end{align}

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

(2)
\begin{equation} g(n_x)=x \end{equation}

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$


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