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 well-ordered, $f^{-1}(a)$ itself is well-ordered, 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 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,\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 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. 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. 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\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	2013-03-22 19:02:49
Last modified on	2013-03-22 19:02:49
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	7
Author	CWoo (3771)
Entry type	Definition
Classification	msc 03E10