You are here
Homealternative definitions of countable
Primary tabs
alternative definitions of countable
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\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 wellordered, $f^{{1}}(a)$ itself is wellordered, 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 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},\ldots\}$, 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 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, 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.
Mathematics Subject Classification
03E10 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections