Countable vs Uncountable

The rationals fit into a single list; the reals do not — verified by Cantor's diagonal argument.

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 exactly once: $m = 0$ as $a_0$ , $m \geq 1$ as $a_{2m-1}$ , and $m < 0$ as $a_{-2m}$ .
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.

x_n = \begin{cases} 5 & r_n\text{'s }n\text{th digit} \ne 5 \\ 6 & \text{otherwise} \end{cases}

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 $x$ digit by digit: its $n$ -th digit is $5$ when $r_n$ 's $n$ -th digit is not $5$ , and $6$ otherwise. Then $x \in (0,1)$ , but $x \ne r_n$ for every $n$ since they differ at digit $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 proof

[Sketch] Arrange $A_1, A_2, \dots$ as the rows of an infinite grid. Sweeping it 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.