Wat is Gelijkmachtigheid, aftelbaarheid?

Voorbeeld 1.7 (Een koppelfunctie, doorgerekend)

De bijectie $(p, q) \mapsto 2^p(2q + 1) - 1$ uit het bewijs verdient het om aan het werk gezien te worden. Haar eerste waarden:

Rij $p$ verzamelt de getallen $n$ waarvoor $n + 1$ precies door $2^p$ deelbaar is: elk natuurlijk getal komt precies één keer voor. Decoderen is even expliciet als coderen: voor $n = 43$ ontbinden we $n + 1 = 44 = 2^2\cdot 11 = 2^2(2\cdot5 + 1)$, dus $(p, q) = (2, 5)$. Het inzicht om te onthouden: bewijzen over aftelbaarheid zijn vaak vermomde algoritmen — hier “haal de factoren $2$ eruit”.

Voorbeeld 1.8 (De algebraïsche getallen zijn aftelbaar)

Een complex getal heet algebraïsch wanneer het een nulpunt is van een veelterm ongelijk aan nul met rationale coëfficiënten. De verzameling $\overline\Q$ van de algebraïsche getallen is aftelbaar: de veeltermen van graad $\leq d$ over $\Q$ injecteren in $\Q^{d+1}$, een eindig product van aftelbare verzamelingen (Propositie 1.6 (2)); de vereniging over $d$ somt de veeltermen ongelijk aan nul op als $P_0, P_1, P_2, \dots$; elke $P_k$ heeft eindig veel nulpunten; en

is een aftelbare vereniging van eindige verzamelingen (Propositie 1.6 (3)), oneindig omdat zij $\Q$ bevat. Samen met de overaftelbaarheid van $\R$ (Stelling 1.9 hieronder) bewijst dit — zonder er ook maar één aan te wijzen — dat er transcendente getallen bestaan en dat zij een overaftelbare meerderheid vormen: het telargument van Cantor uit 1874, bestaan louter op grond van kardinaliteit.

Voorbeeld 1.11

$\intoo{0}{1}$ en $\intcc{0}{1}$ zijn gelijkmachtig: de identiteit injecteert de ene kant op, $x \mapsto \frac{x + 1}{3}$ de andere; de stelling fabriceert vervolgens de (noodzakelijk discontinue) bijectie. Evenzo zijn $\R$, $\intoo{0}{1}$ (via bijecties van het type $\tanh$) en $\mathcal{P}(\N)$ (binaire ontwikkelingen, Oefening 1.3) alle gelijkmachtig: “de machtigheid van het continuüm”.