Countable vs Uncountable

See the rationals numbered in a single list. Then see the same attempt fail for the reals.

Countable means pairing off with the natural numbers. Fractions tile a grid, and a zigzag count numbers them all. Reals refuse. Every proposed list misses some real. Changing digits along the diagonal proves it.

For example, hand number tickets to every 🧑 classmate. However long the line, one ticket each means countable. If every roster still misses someone, the crowd cannot be counted.

Examples & Exercises

Prove $\mathbb{Z}$ is countable via the explicit enumeration $0, 1, -1, 2, -2, \dots$ .

a_0 = 0,\quad a_{2k-1} = k,\quad a_{2k} = -k\ \ (k \geq 1)

The same diagonal idea as the rationals — starting with the integers.

Show proof

With $a_0 = 0$ , $a_{2k-1} = k$ and $a_{2k} = -k$ for $k \geq 1$ , every integer appears (surjectivity): $m = 0$ as $a_0$ , $m \geq 1$ as $a_{2m-1}$ , and $m < 0$ as $a_{-2m}$ .
Injectivity (exactly once) also needs an argument: the index classes $\{0\}$ , $\{2k-1 : k \geq 1\}$ (odd indices), and $\{2k : k \geq 1\}$ (even positive indices) are pairwise disjoint and cover all indices.
Their value ranges $\{0\}$ , the positive integers, and the negative integers are likewise disjoint, and within each class $k$ is uniquely recovered from the value ( $k = m$ or $k = -m$ ).
Hence distinct indices give distinct values.
Hence $n \mapsto a_n$ is a bijection $\mathbb{N} \to \mathbb{Z}$ , so $\mathbb{Z}$ is countable.

Prove $(0,1)$ is uncountable by Cantor's diagonal argument.

d_n = \begin{cases} 5 & r_n\text{'s }n\text{th digit} \ne 5 \\ 6 & \text{otherwise} \end{cases} \qquad (d_n \text{ is the } n\text{th digit of } x)

The flipped diagonal cannot be anywhere in the list.

Show proof

Suppose the elements of $(0,1)$ could be fully enumerated as $r_1, r_2, \dots$ . Each $r_n$ has a unique decimal expansion not ending in infinite $9$ s, so its $n$ -th digit is well defined.
Define the $n$ -th digit $d_n$ of $x$ to be $5$ when $r_n$ 's $n$ -th digit is not $5$ , and $6$ otherwise.
Then $x \in (0,1)$ .
To pass from a digit difference to $x \ne r_n$ the dual-expansion issue must be addressed: the expansion of $x$ uses only the digits $5$ and $6$ , so it has no tail of $0$ s and no tail of $9$ s.
But two decimal expansions of the same number are possible only when one ends in a tail of $0$ s and the other in a tail of $9$ s, so an expansion using only $5, 6$ is the unique — canonical — expansion of $x$ .
It differs from the canonical expansion of $r_n$ at digit $n$ , hence $x \ne r_n$ for every $n$ — a contradiction.
Hence no enumeration of $(0,1)$ exists: $(0,1)$ is uncountable.

Explain at idea level why a countable union of countable sets is countable, via diagonal enumeration.

(Idea level; full proof omitted.)

n=64

: the same diagonal sweep of the grid.

Show hint

[Sketch] Arrange $A_1, A_2, \dots$ as the rows of a grid.
Choose an enumeration of each $A_i$ in advance (countable choice): skip rows with $A_i$ empty.
Pad each finite $A_i$ to an infinite row by repeating one fixed element (padding — duplicates are removed afterwards, or the construction is read as a surjection from $\mathbb{N} \times \mathbb{N}$ rather than an injection).
With every row now infinite, sweeping the grid in diagonal order — exactly as for the rationals — every element shows up at some finite diagonal position.
[Sketch] This is an idea-level explanation; the full proof needs care with duplicate elements.

Countable vs Uncountable

Part of these learning paths

Examples & Exercises