alternative definitions of countable
The following are alternative ways of characterizing a countable set.
Proposition 1.
Let $A$ be a set and $\mathrm{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)\iff (2)\iff (3)$ vacuously. Now, suppose that $A\ne \mathrm{\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 $\{n\in \mathbb{N}\mid f(n)=a\}$. Since ${f}^{1}(a)$ is a subset of $\mathbb{N}$, which is wellordered, ${f}^{1}(a)$ itself is wellordered, and thus has a least element (keep in mind $A\ne \mathrm{\varnothing}$, the existence of $a\in A$ is guaranteed, so that ${f}^{1}(a)\ne \mathrm{\varnothing}$ as well). Let $g(a)$ be this least element. Then $a\mapsto g(a)$ is a welldefined mapping from $A$ to $\mathbb{N}$. It is onetoone, for if $g(a)=g(b)=n$, then $a=f(n)=b$.
$(2)\Rightarrow (1)$. Suppose $g:A\to \mathbb{N}$ is onetoone. 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 nonempty). Define a function $f:\mathbb{N}\to A$ by $f(n):={g}^{1}(n)$. By the discussion above, ${g}^{1}(n)$ is a welldefined element of $A$, and therefore $f$ is welldefined. $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 wellordered. The (induced) wellordering on $g(A)$ implies that $g(A)=\{{n}_{1},{n}_{2},\mathrm{\dots}\}$, where $$.
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 welldefined. 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)$. ∎
Therefore, countability can be defined in terms of either of the above three statements.
Note that the axiom of choice^{} is not needed in the proof of $(1)\Rightarrow (2)$, since the selection of an element in ${f}^{1}(a)$ is definite, not arbitrary.
For example, we show that ${\mathbb{N}}^{2}$ is countable^{}. By the proposition^{} above, we either need to find a surjection $f:\mathbb{N}\to {\mathbb{N}}^{2}$, or an injection $g:{\mathbb{N}}^{2}\to \mathbb{N}$. Actually, in this case, we can find both:

1.
the function $f:\mathbb{N}\to {\mathbb{N}}^{2}$ given by $f(a)=(m,n)$ where $a={2}^{m}(2n+1)$ is surjective. First, the function is welldefined, for every positive integer has a unique representation as the product^{} of a power of $2$ and an odd number^{}. It is surjective because for every $(m,n)$, we see that $f({2}^{m}(2n+1))=(m,n)$.

2.
the function $g:{\mathbb{N}}^{2}\to \mathbb{N}$ given by $f(m,n)={2}^{m}{3}^{n}$ is clearly injective.
Note that the injectivity of $g$, as well as $f$ being welldefined, rely on the unique factorization of integers by prime numbers^{}. In this entry (http://planetmath.org/ProductOfCountableSets), we actually find a bijection between $\mathbb{N}$ and ${\mathbb{N}}^{2}$.
As a corollary, we record the following:
Corollary 1.
Let $A\mathrm{,}B$ be sets, $f\mathrm{:}A\mathrm{\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$.
The proof is left to the reader.
Title  alternative definitions of countable 

Canonical name  AlternativeDefinitionsOfCountable 
Date of creation  20130322 19:02:49 
Last modified on  20130322 19:02:49 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  7 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 03E10 