Countable sets, uncountable sets

The cardinalities (numbers of elements) of the sets $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$ are all infinite. Which one is "larger" or "smaller"? It turns out that the sets $\mathbb{N}$, $\mathbb{Z}$, and $\mathbb{Q}$ all have the "same" number of elements and are called countable, whereas $\mathbb{R}$ contains a far greater number of elements and is called uncountable. But how can we "count" infinities?

The sets $\{a,b,c,d\}$ and $\{1,2,3,4\}$ have no elements in common, but they have the same number of elements (i.e., 4). Note that there are bijections between them. For example, (but not limited to)

$$\begin{array}{rl}1& \mapsto \text{a},\\ 2& \mapsto \text{b},\\ 3& \mapsto \text{c},\\ 4& \mapsto \text{d}.\end{array}$$ 

Quiz. How many bijections are possible from $\{1,2,3,4\}$ to $\{a,b,c,d\}$?

Any finite set $X$ with $N$ elements (i.e., $|X|=N$) may be written as

$$X=\{x_1,x_2,\cdots ,x_N\}.$$

Note that this means there is a bijection from $\{1,2,\cdots ,N\}$ to $X$, that is,  $k\mapsto x_k$ for each $k=1,2,\cdots ,N$. If a set $X$ is not finite, then there may or may not be a bijection from $\mathbb{N}$ to $X$, and there is a crucial difference between the two cases.

Definition (Countable sets, uncountable sets)

A non-empty set $X$ is said to be countable if the elements of $X$ may be enumerated as a finite or infinite sequence of the form $x_1,x_2,\cdots$. If $X$ is finite and has $N$ elements, then $X=\{x_n\mid n=1,2,\cdots ,N\}=\{x_1,x_2,\cdots ,x_N\}$; if $X$ is infinite then $X=\{x_n\mid n\in \mathbb{N}\}=\{x_1,x_2,\cdots \}$. Sets that are not countable are said to be uncountable.

Remark. Some authors define a countable set as a set to which there exists a bijection from $\mathbb{N}$. In that case, a countable set is necessarily infinite, and a set that is either finite or countable is said to be at most countable or discrete. □

Example. The set $-\mathbb{N}$ of strictly negative integers given by $-\mathbb{N}=\{-n\mid n\in \mathbb{N}\}$ is countable. The bijection from $\mathbb{N}$ to $-\mathbb{N}$ is given by $f(n)=-n$ for $n\in \mathbb{N}$. □

Example. The set $\mathbb{Z}$ is countable. To see this we define a function $f:\mathbb{N}\to \mathbb{Z}$ by

$$f(n)=\{\begin{array}{cc}\frac{n-1}{2},& \text{if }n\text{ is odd},\\ -\frac{n}{2},& \text{if }n\text{ is even}.\end{array}$$

This function can be shown to be a bijection (exercise!). □

The following theorem is trivial.

Theorem

Any subset of a countable set is countable.

Proof. Trivial. ■

Example. The set of even integers, $2\mathbb{Z}=\{2i\mid i\in \mathbb{Z}\}$, is countable. □

Example. Let $X$ be a set of elements $x_{ij}$ having double suffices such that

$$X=\{x_{pq}\mid p,q\in \mathbb{N}\}.$$

We may write down the elements in a 2-dimensional array (like a matrix):

$$\begin{array}{ccccc}{x}_{11}& x_{12}& x_{13}& x_{14}& \cdots \\ x_{21}& x_{22}& x_{23}& x_{24}& \cdots \\ x_{31}& x_{32}& x_{33}& x_{34}& \cdots \\ x_{41}& x_{42}& x_{43}& x_{44}& \cdots \\ ⋮& ⋮& ⋮& ⋮& \ddots \end{array}$$

This 2-dimensional array can be "serialized" in a unique manner:

$$\begin{array}{}\text{(Eq:Serialized)}& x_{11};x_{12},x_{21};x_{13},x_{22},x_{31};x_{14},x_{23},x_{32},x_{41};\cdots \end{array}$$

Each element of the array appears precisely once in this sequence, and all the elements are enumerated. Thus, this set $X$ is countable. □

Exercise. Construct a bijection between $\mathbb{N}$ and $X=\{x_{pq}\}$ in the above example. □

Theorem (Union of countable sets)

The union of a countable number of (countably many) countable sets is countable. That is, let $X_1,X_2,\cdots$ be countable sets. Then $\bigcup _{i=1}^{\mathrm{\infty }}{X}_i$ is countable.

Proof. Let $X_1,X_2,\cdots$ be countable sets. Let us enumerate their elements as follow:

$$\begin{array}{rcl}{X}_1& =& \{x_{11},x_{12},\cdots \},\\ X_2& =& \{x_{21},x_{22},\cdots \},\\ X_3& =& \{x_{31},x_{32},\cdots \},\\ & ⋮& \end{array}$$

Then, the elements of $\bigcup _{i=1}^{\mathrm{\infty }}{X}_i$ may be written as a 2-dimensional array $\{x_{pq}\}$ which is countable by the above Example. ■

Example. Here's is another way to prove that $\mathbb{Z}$ is countable. $\mathbb{N}$, $-\mathbb{N}$ and $\{0\}$ are countable. Thus, so is

$$\mathbb{Z}=\mathbb{N}\cup -\mathbb{N}\cup \{0\}.$$

□

Theorem (Cartesian product of finitely many countable sets)

The Cartesian product of a finite number of countable sets is countable.

Proof. Let $A=\{a_n\mid n\in \mathbb{N}\}$ and $B=\{b_n\mid n\in \mathbb{N}\}$. If we represent the elements of $A\times B$ as $x_{pq}=(a_p,b_q)\in A\times B$, then it is evident that the Cartesian product $A\times B$ is countable.

More generally, let $X_1,X_2,\cdots ,X_N$ be countable sets. Note that their Cartesian product may be represented as

$$X_1\times X_2\times \cdots \times X_N=(X_1\times X_2\times \cdots \times X_{N-1})\times X_N.$$

The right-hand side is the Cartesian product of two countable sets (assuming $X_1\times \cdots \times X_{N-1}$ is countable). Thus, by mathematical induction, this set is countable. ■

Corollary 

$\mathbb{Q}$, the set of rational numbers, is countable.

Proof. Consider the set ${\mathbb{Q}}^{+}$ of strictly positive rational numbers. Its elements can be expressed as $m/n$ where $m,n\in \mathbb{N}$. By the correspondence $m/n\leftrightarrow (m,n)$, it is easy to see that ${\mathbb{Q}}^{+}$ is countable. The rest is exercise. ■

Note that the theorem applies to the Cartesian product of finitely many countable sets. Guess what happens if we relax this condition to the Cartesian product of countably many countable sets: $X_1\times X_2\times \cdots$. Is this still countable? As we will see below, the answer is negative.

Lemma

Let ${\mathbf{2}}^{\mathbb{N}}$ be the set of all maps from $\mathbb{N}$ to $\mathbf{2}=\{0,1\}$,

$${\mathbf{2}}^{\mathbb{N}}=\{f\mid f:\mathbb{N}\to \mathbf{2}\}.$$

Then, ${\mathbf{2}}^{\mathbb{N}}$ is uncountable.

Proof. We prove this by contradiction.

Suppose ${\mathbf{2}}^{\mathbb{N}}$ is countable. Then, we can enumerate all the maps from $\mathbb{N}$ to $\{0,1\}$. So, we can write ${\mathbf{2}}^{\mathbb{N}}=\{f_1,f_2,\cdots \}$. Then, for every map from $\mathbb{N}$ to $\{0,1\}$, there is some $r\in \mathbb{N}$ such that $f_r$ is that map. Let us define $g:\mathbb{N}\to \{0,1\}$ as follows:

$$g(n)=\{\begin{array}{ll}0& \text{if }{f}_n(n)=1,\\ 1& \text{if }{f}_n(n)=0\end{array}$$

for each $n\in \mathbb{N}$. Certainly, $g\in {\mathbf{2}}^{\mathbb{N}}$, and hence, there must be some element $f_r\in {\mathbf{2}}^{\mathbb{N}}$ such that $g=f_r$. However, for all $n\in \mathbb{N}$, we have $g(n)\ne f_n(n)$ by the above construction, so $g$ cannot be in ${\mathbf{2}}^{\mathbb{N}}$. This is a contradiction. ■

Remark. Let's examine this proof more closely. Note that each map in ${\mathbf{2}}^{\mathbb{N}}$ in the above Lemma can be regarded as an element of $\mathbf{2}\times \mathbf{2}\times \cdots$, the Cartesian product of infinitely many $\mathbf{2}$. That is, each element of this Cartesian product can be written as

$$(f(1),f(2),f(3),\cdots )$$

for some $f\in {\mathbf{2}}^{\mathbb{N}}$. If ${\mathbf{2}}^{\mathbb{N}}$ were countable (which is not true!), its elements would be enumerated in the matrix form as

$$\begin{array}{ccccc}{f}_1(1)& f_1(2)& f_1(3)& f_1(4)& \cdots \\ f_2(1)& f_2(2)& f_2(3)& f_2(4)& \cdots \\ f_3(1)& f_3(2)& f_3(3)& f_3(4)& \cdots \\ f_4(1)& f_4(2)& f_4(3)& f_4(4)& \cdots \\ ⋮& ⋮& ⋮& ⋮& \ddots \end{array}$$

The map $g$ in the proof is constructed by taking the diagonal elements, $f_1(1),f_2(2),f_3(3),\cdots$, of this matrix and swapping 0 and 1. This $g$ must be one of the rows of this matrix. But $g(n)$ cannot match any of the rows! This type of proving strategy is called Cantor's diagonal argument. It is useful in many situations. □

Theorem

$\mathbb{R}$, the set of real numbers, is uncountable.

Proof. It suffices to prove that the set of real numbers in the interval $[0,1]$ is uncountable. Each real number in the binary format is represented as $0.a_1{a}_2{a}_3\cdots$ where each $a_i$ is either 0 or 1. This correspondence makes the bijection $[0,1]\to {\mathbf{2}}^{\mathbb{N}}$. Since ${\mathbf{2}}^{\mathbb{N}}$ is uncountable, so is $[0,1]$. ■

Thus, the sets $\mathbb{N}$, $\mathbb{Z}$, and $\mathbb{Q}$ all have the "same" number of elements. The cardinality of these sets is represented by ${\mathrm{\aleph }}_0$ (read "aleph-naught" or "aleph-zero"; $\mathrm{\aleph }$ is the first letter of the Hebrew alphabet, corresponding to ا (alif) in Arabic (Hebrew and Arabic both belong to the Semitic language family) or $\alpha$ in Greek). 

$\mathbb{R}$ has a far "greater" number of elements. Its cardinality is represented by ${\mathrm{\aleph }}_1$. In the proof of the above theorem, we see that $\mathbb{R}$ and ${\mathbf{2}}^{\mathbb{N}}$ are isomorphic (i.e., there exists a bijection between them). Thus, its cardinality is $|{\mathbf{2}}^{\mathbb{N}}|=2^{{\mathrm{\aleph }}_0}$ (if this makes any sense). Therefore, we seem to have

$${\mathrm{\aleph }}_1=2^{{\mathrm{\aleph }}_0}.$$

In summary, ${\mathrm{\aleph }}_0$ and ${\mathrm{\aleph }}_1$ are both infinite, but there is a huge difference. (Actually, the situation is a lot more complicated than this. See Aleph number on Wikipedia for further information.)

Perhaps, the most important lesson here is that if things involve infinity, something strange can happen so that we can't rely on our intuition.