O que é Equipotência, enumerabilidade?

Exemplo 1.7 (Uma função de emparelhamento, na prática)

A bijeção $(p, q) \mapsto 2^p(2q + 1) - 1$ da demonstração merece ser vista em ação. Seus primeiros valores:

A linha $p$ reúne os inteiros $n$ para os quais $n + 1$ é divisível por $2^p$ exatamente: todo número natural aparece exatamente uma vez. Decodificar é tão explícito quanto codificar: para $n = 43$, fatore $n + 1 = 44 = 2^2\cdot 11 = 2^2(2\cdot5 + 1)$, donde $(p, q) = (2, 5)$. A lição final: as demonstrações de enumerabilidade são muitas vezes algoritmos disfarçados — aqui, “ponha os fatores dois em evidência”.

Exemplo 1.8 (Os números algébricos são enumeráveis)

Um número complexo é algébrico quando anula algum polinômio não nulo com coeficientes racionais. O conjunto $\overline\Q$ dos números algébricos é enumerável: os polinômios de grau $\leq d$ sobre $\Q$ injetam-se em $\Q^{d+1}$, produto finito de conjuntos enumeráveis (Proposição 1.6 (2)); a união sobre $d$ enumera os polinômios racionais não nulos como $P_0, P_1, P_2, \dots$; cada $P_k$ tem um número finito de raízes; e

é uma união enumerável de conjuntos finitos (Proposição 1.6 (3)), infinita pois contém $\Q$. Combinado com a não enumerabilidade de $\R$ (Teorema 1.9 adiante), isso prova — sem exibir um único deles — que os números transcendentes existem e formam uma maioria não enumerável: o argumento de contagem de Cantor de 1874, a existência apenas pela cardinalidade.

Exemplo 1.11

$\intoo{0}{1}$ e $\intcc{0}{1}$ são equipotentes: a identidade injeta num sentido, $x \mapsto \frac{x + 1}{3}$ no outro; o teorema fabrica a bijeção (necessariamente descontínua). Do mesmo modo $\R$, $\intoo{0}{1}$ (por bijeções do tipo $\tanh$) e $\mathcal{P}(\N)$ (expansões binárias, Exercício 1.3) são todos equipotentes: “a cardinalidade do contínuo”.