What is Equipotence, countability?

Example 1.7 (A pairing function, computed)

The bijection $(p, q) \mapsto 2^p(2q + 1) - 1$ of the proof deserves to be seen at work. Its first values:

Row $p$ collects the integers $n$ for which $n + 1$ is exactly divisible by $2^p$: every natural number appears exactly once. Decoding is as explicit as encoding: for $n = 43$, factor $n + 1 = 44 = 2^2\cdot 11 = 2^2(2\cdot5 + 1)$, so $(p, q) = (2, 5)$. The closing insight: countability proofs are often algorithms in disguise — here, “factor out the twos”.

Example 1.8 (The algebraic numbers are countable)

A complex number is algebraic when it annihilates some nonzero polynomial with rational coefficients. The set $\overline\Q$ of algebraic numbers is countable: polynomials of degree $\leq d$ over $\Q$ inject into $\Q^{d+1}$, a finite product of countable sets (Proposition 1.6 (2)); the union over $d$ enumerates the nonzero rational polynomials as $P_0, P_1, P_2, \dots$; each $P_k$ has finitely many roots; and

is a countable union of finite sets (Proposition 1.6 (3)), infinite since it contains $\Q$. Combined with the uncountability of $\R$ (Theorem 1.9 below), this proves — without exhibiting a single one — that transcendental numbers exist and form an uncountable majority: Cantor’s counting argument of 1874, existence by cardinality alone.

Example 1.11

$\intoo{0}{1}$ and $\intcc{0}{1}$ are equipotent: the identity injects one way, $x \mapsto \frac{x + 1}{3}$ the other; the theorem manufactures the (necessarily discontinuous) bijection. Likewise $\R$, $\intoo{0}{1}$ (via $\tanh$-type bijections) and $\mathcal{P}(\N)$ (binary expansions, Exercise 1.3) are all equipotent: “the cardinality of the continuum”.