Equipotencia, numerabilidad কী?

Ejemplo 1.7 (Una función de emparejamiento, calculada)

La biyección $(p, q) \mapsto 2^p(2q + 1) - 1$ de la demostración merece verse en funcionamiento. Sus primeros valores:

La fila $p$ reúne los enteros $n$ para los que $n + 1$ es divisible exactamente por $2^p$: cada número natural aparece una sola vez. Descodificar es tan explícito como codificar: para $n = 43$ se factoriza $n + 1 = 44 = 2^2\cdot 11 = 2^2(2\cdot5 + 1)$, luego $(p, q) = (2, 5)$. La moraleja: las demostraciones de numerabilidad son a menudo algoritmos disfrazados; aquí, “sacar factor común los doses”.

Ejemplo 1.8 (Los números algebraicos son numerables)

Un número complejo es algebraico cuando anula algún polinomio no nulo con coeficientes racionales. El conjunto $\overline\Q$ de los números algebraicos es numerable: los polinomios de grado $\leq d$ sobre $\Q$ se inyectan en $\Q^{d+1}$, producto finito de conjuntos numerables (Proposición 1.6 (2)); la unión sobre $d$ enumera los polinomios racionales no nulos como $P_0, P_1, P_2, \dots$; cada $P_k$ tiene un número finito de raíces; y

es una unión numerable de conjuntos finitos (Proposición 1.6 (3)), infinita porque contiene a $\Q$. Junto con la no numerabilidad de $\R$ (Teorema 1.9 más abajo), esto demuestra —sin exhibir ni uno solo— que los números trascendentes existen y forman una mayoría no numerable: el argumento de conteo de Cantor de 1874, existencia por pura cardinalidad.

Ejemplo 1.11

$\intoo{0}{1}$ y $\intcc{0}{1}$ son equipotentes: la identidad inyecta en un sentido y $x \mapsto \frac{x + 1}{3}$ en el otro; el teorema fabrica la biyección (forzosamente discontinua). Del mismo modo, $\R$, $\intoo{0}{1}$ (mediante biyecciones de tipo $\tanh$) y $\mathcal{P}(\N)$ (desarrollos binarios, Ejercicio 1.3) son todos equipotentes: “el cardinal del continuo”.