Chapter 4 : Countable and uncountable

The set of integers $\mathbb{Z}$ is countable. Define $f:\mathbb{N}\rightarrow \mathbb{Z}$ by $$ f(n)=\begin{cases}\frac{1}{2} n & \mbox{ if }n\mbox{ is even}. \\ -\frac{1}{2} (n-1) & \mbox{ if }n\mbox{ is odd}. \end{cases} $$ It is clear that $f$ maps $\mathbb{N}$ into $\mathbb{Z}$. Check that it is one-one and onto. Thus, we have found a bijection from $\mathbb{N}$ onto $\mathbb{Z}$ which shows that $\mathbb{Z}$ is countable. This function is a formal way of saying the we can list the elements of $\mathbb{Z}$ as $$ 0, +1, -1,+2,-2,+3,-3,\ldots. $$ It is obvious, but good to realize there are wrong ways to try writing such a list. For example, if you list all the negative integers first, as $-1,-2,-3,\ldots$, then you will never arrive at $0$ or $1$, and hence the list is incomplete!

The set $\mathbb{N}\times \mathbb{N}$ is countable. Rather than give a formula, we list the elements of $\mathbb{Z}\times \mathbb{Z}$ as follows. $$ (1,1), (1,2), (2,1), (1,3), (2,2), (3,1), (1,4),(2,3),(3,2),(4,1), \ldots $$ The pattern should be clear. Use this list to define a bijection from $\mathbb{N}$ onto $\mathbb{N}\times \mathbb{N}$ and hence show that $\mathbb{N}\times \mathbb{N}$ is countable.

The set $\mathbb{Z}\times \mathbb{Z}$ is countable. This follows from the first two examples. Indeed, we have a bijection $f:\mathbb{N}\rightarrow \mathbb{Z}$ and a bijection $g:\mathbb{N}\times \mathbb{N} \rightarrow \mathbb{N}$. Define a bijection $F:\mathbb{N}\times \mathbb{N}\rightarrow \mathbb{Z}\times \mathbb{Z}$ by composing them, i.e., $F(n,m)=f(g(n))$. Then, $F$ is one-one and onto. This shows that $\mathbb{Z}\times \mathbb{Z}$ is indeed countable.

The set of rational numbers $\mathbb{Q}$ is countable. Recall that rational numbers other than $0$ can be written uniquely in the form $p/q$ where $p$ is a non-zero integer and $q$ is a strictly positive integer, and there are no common factors of $p$ and $q$ (this is called the lowest form of the rational number $r$). Consider the map $f:\mathbb{Q}\rightarrow \mathbb{Z}\times \mathbb{Z}$ defined by $$ f(r) = \begin{cases} (0,1) & \mbox{ if }r=0 \ (p,q) & \mbox{ if }r=\frac{p}{q} \mbox{ in the lowest form}. \end{cases} $$ Clearly, $f$ is injective and hence, it appears that $\mathbb{Z}\times \mathbb{Z}$ is a ''bigger set'' than $\mathbb{Q}$. Next define the function $g:\mathbb{Z}\rightarrow \mathbb{Q}$ by setting $g(n)=n$. This is also injective and hence we may say that ''$\mathbb{Q}$ is a bigger set than $\mathbb{N}$.

But we have already seen that $\mathbb{N}$ and $\mathbb{Z}\times \mathbb{Z}$ are in bijection with each other, in that sense, they are of equal size. Since $\mathbb{Q}$ is sandwiched between the two it ought to be true that $\mathbb{Q}$ has the same size as $\mathbb{N}$, and thus countable.

This reasoning is not incorrect, but an argument is needed to make it an honest proof. This is indicated in the Schröder-Bernstein theorem stated later. Use that to fill the gap in the above argument, or alternately, try to directly find a bijection between $\mathbb{Q}$ and $\mathbb{N}$.

The set of real numbers $\mathbb{R}$ is not countable. The extraordinarily proof of this fact is due to Cantor, and the core idea, called the diagonalization trick is one that can be used in many other contexts.

Consider any function $f:\mathbb{N} \rightarrow [0,1]$. We show that it is not onto, and hence not a bijection. Indeed, use the decimal expansion to write a number $x\in [0,1]$ as $0.x_{1}x_{2}x_{3}\ldots$ where $x_{i}\in \{0,1,\ldots ,9\}$. Write the decimal expansion for each of the numbers $f(1),f(2),f(3),.\ldots$ as follows. $$\begin{align*} f(1)&=0.X_{1,1}X_{1,2}X_{1,3}\ldots \\ f(2)&=0.X_{2,1}X_{2,2}X_{2,3}\ldots \\ f(3)&=0.X_{3,1}X_{3,2}X_{3,3}\ldots \\ \cdots & \cdots \cdots \cdots \end{align*}$$ Let $Y_{1},Y_{2},Y_{3},\ldots$ be any numbers in $\{0,1,\ldots ,9\}$ with the only condition that $Y_{i}\not= X_{i,i}$. Clearly it is possible to choose $Y_{i}$ like this. Now consider the number $y=0.Y_{1}Y_{2}Y_{3}\ldots$ which is a number in $[0,1]$. However, it does not occur in the above list. Indeed, $y$ disagrees with $f(1)$ in the first decimal place, disagrees with $f(2)$ in the second decimal place etc. Thus, $y\not= f(i)$ for any $i\in \mathbb{N}$ which means that $f$ is not onto $[0,1]$.

Thus, no function $f:\mathbb{N}\rightarrow [0,1]$ is onto, and hence there is no bijection from $\mathbb{N}$ onto $[0,1]$ and hence $[0,1]$ is not countable. Obviously, if there is no onto function onto $[0,1]$, there cannot be an onto function onto $\mathbb{R}$. Thus, $\mathbb{R}$ is also uncountable.

Let $A_{1},A_{2},\ldots $ be subsets of a set $\Omega$. Suppose each $A_{i}$ is countable (finite is allowed). Then $\cup_{i}A_{i}$ is also countable. We leave it as an exercise. [ Hint: If each $A_{i}$ is countably infinite and pairwise disjoint, then $\cup A_{i}$ can be thought of as $\mathbb{N}\times \mathbb{N}$].