Equipotence and countable sets

Counting without counting

How do you decide that two sets have "as many" elements when they are infinite? In 1874 Cantor proposed an answer that involves no counting at all: two sets $E$ and $F$ are equipotent (have the same cardinality) if there exists a bijection from $E$ onto $F$.

$$E \sim F \iff \exists\, f : E \to F \ \text{bijective}$$

For finite sets, this gives back equality of cardinalities. For infinite sets, it holds some surprises.

Countable sets

A set is countable if it is equipotent to $\mathbb{N}$: its elements can then be numbered $x_0, x_1, x_2, \ldots$ without missing or repeating any. It is the smallest infinity.

The first shock is that you can remove elements from an infinite set without changing its size. The map $n \mapsto n + 1$ is a bijection from $\mathbb{N}$ onto $\mathbb{N}^*$: the set of nonzero integers is as large as the set of all integers. This is Hilbert's hotel, full yet still able to take in one more guest by moving everyone up one room.

The catalog of countable sets

Set	Bijection with $\mathbb{N}$	Countable?
$\mathbb{N}^*$	$n \mapsto n + 1$	yes
even integers	$n \mapsto 2n$	yes
$\mathbb{Z}$	alternating $0, 1, -1, 2, -2, \ldots$	yes
$\mathbb{N}^2$	traversal along diagonals	yes
$\mathbb{Q}$	see the next lesson	yes
algebraic numbers	countable union of finite subsets	yes

Let's look at $\mathbb{Z}$ in detail. The bijection is written explicitly as

$$f(n) = \begin{cases} \dfrac{n}{2} & \text{if } n \text{ is even} \\[2mm] -\dfrac{n+1}{2} & \text{if } n \text{ is odd} \end{cases}$$

which lists $0, -1, 1, -2, 2, \ldots$ and reaches every integer exactly once.

Two stability rules

They are used constantly, and both follow from the diagonal traversal of $\mathbb{N}^2$:

A countable union of countable sets is countable. A finite product of countable sets is countable.

On the other hand, an infinite product of two-element sets is not: the set $\{0, 1\}^{\mathbb{N}}$ of binary sequences is the first uncountable set one encounters, and it is the one that Cantor's diagonal will catch out.

Classic pitfall

Believing that a "richer" set is necessarily larger. Intuition says that $\mathbb{Q}$ contains many more elements than $\mathbb{N}$, since there are infinitely many of them between two consecutive integers. This is false in the sense of equipotence: density and cardinality are two independent notions. The set $\mathbb{Q}$ is dense in $\mathbb{R}$ and yet countable.