Proposition 1   Let $A$ be a set and $\mathbb{N}$ the set of natural numbers. The following are equivalent:

1. there is a surjection from $\mathbb{N}$ to $A$ .
2. there is an injection from $A$ to $\mathbb{N}$ .
3. either $A$ is finite or there is a bijection between $A$ and $\mathbb{N}$ .

Proof. First notice that if $A$ were the empty set, then any map to or from $A$ is empty, so $(1)\Leftrightarrow (2) \Leftrightarrow (3)$ vacuously. Now, suppose that $A \ne \varnothing$ .

$(1)\Rightarrow (2)$ . Suppose $f: \mathbb{N}\to A$ is a surjection. For each $a\in A$ , let $f^{-1}(a)$ be the set $\lbrace n \in \mathbb{N} \mid f(n)=a\rbrace$ . Since $f^{-1}(a)$ is a subset of $\mathbb{N}$ , which is well-ordered, $f^{-1}(a)$ itself is well-ordered, and thus has a least element (keep in mind $A\ne \varnothing$ , the existence of $a\in A$ is guaranteed, so that $f^{-1}(a)\ne \varnothing$ as well). Let $g(a)$ be this least element. Then $a \mapsto g(a)$ is a well-defined mapping from $A$ to $\mathbb{N}$ . It is one-to-one, for if $g(a)=g(b)=n$ , then $a=f(n)=b$ .

$(2)\Rightarrow (1)$ . Suppose $g:A\to \mathbb{N}$ is one-to-one. So $g^{-1}(n)$ is at most a singleton for every $n\in \mathbb{N}$ . If it is a singleton, identify $g^{-1}(n)$ with that element. Otherwise, identify $g^{-1}(n)$ with a designated element $a_0\in A$ (remember $A$ is non-empty). Define a function $f:\mathbb{N} \to A$ by $f(n):=g^{-1}(n)$ . By the discussion above, $g^{-1}(n)$ is a well-defined element of $A$ , and therefore $f$ is well-defined. $f$ is onto because for every $a\in A$ , $f(g(a))=a$ .

$(3)\Rightarrow (2)$ is clear.

$(2)\Rightarrow (3)$ . Let $g: A\to \mathbb{N}$ be an injection. Then $g(A)$ is either finite or infinite. If $g(A)$ is finite, so is $A$ , since they are equinumerous. Suppose $g(A)$ is infinite. Since $g(A) \subseteq \mathbb{N}$ , it is well-ordered. The (induced) well-ordering on $g(A)$ implies that $g(A)=\lbrace n_1, n_2, \ldots \rbrace$ , where $n_1 < n_2 < \cdots$ .

Now, define $h: \mathbb{N}\to A$ as follows, for each $i\in \mathbb{N}$ , $h(i)$ is the element in $A$ such that $g(h(i))=n_i$ . So $h$ is well-defined. Next, $h$ is injective. For if $h(i)=h(j)$ , then $n_i = g(h(i))=g(h(j)) = n_j$ , implying $i=j$ . Finally, $h$ is a surjection, for if we pick any $a\in A$ , then $g(a)\in g(A)$ , meaning that $g(a)=n_i$ for some $i$ , so $h(i)=g(a)$ .

Corollary 1   Let $A,B$ be sets, $f:A\to B$ a function.

• If $f$ is an injection, and $B$ is countable, so is $A$ .
• If $f$ is a surjection, and $A$ countable, so is $B$ .