# alternative definitions of countable

The following are alternative ways of characterizing a countable set.

###### Proposition 1.

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

1. 1.

there is a surjection from $\mathbb{N}$ to $A$.

2. 2.

there is an injection from $A$ to $\mathbb{N}$.

3. 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\neq\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 well-ordered, $f^{-1}(a)$ itself is well-ordered, and thus has a least element (keep in mind $A\neq\varnothing$, the existence of $a\in A$ is guaranteed, so that $f^{-1}(a)\neq\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)=\{n_{1},n_{2},\ldots\}$, where $n_{1}.

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)$. ∎

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. 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 well-defined, 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. 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 well-defined, 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,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$.

The proof is left to the reader.

Title alternative definitions of countable AlternativeDefinitionsOfCountable 2013-03-22 19:02:49 2013-03-22 19:02:49 CWoo (3771) CWoo (3771) 7 CWoo (3771) Definition msc 03E10