Prove que o conjunto dos reais é não enumerável.

Passo 1

O enunciado pede para mostrar que não existe uma bijeção entre os naturais \mathbb{N} e os reais \mathbb{R}. Isto é, queremos provar que \mathbb{R} é não enumerável (não contável). Vamos usar o clássico argumento diagonal de Cantor, aplicando-o ao intervalo (0,1)\subset\mathbb{R}: se (0,1) já é não enumerável, então todo \mathbb{R} também o é, pois (0,1)\subset\mathbb{R}.

Passo 2

Suponha, por absurdo, que exista enumeração de todos os números em (0,1). Ou seja, existe sequência
r_1, r_2, r_3, \dots
tal que cada real em (0,1) aparece em algum lugar da lista. Escrevamos a expansão decimal de cada r_n como
r_n = 0.a_{n1}a_{n2}a_{n3}\dots,
onde cada a_{nk}\in\{0,1,2,\dots,9\}. Para evitar ambiguidades de finais infinitos em 9, podemos exigir que nenhuma expansão termine numa sequência infinita de 9.

Passo 3

Agora, construiremos um número x\in(0,1)\) cujo \(n\)-ésimo dígito decimal \(d_n\) difere de \(a_{nn}\). Definimos \[d_n = \begin{cases} 1, &\text{se }a_{nn}\neq1,\\\\ 2, &\text{se }a_{nn}=1. \end{cases}
Então tomamos
x = 0.d_1 d_2 d_3 \dots.
Por construção, d_n\neq a_{nn}\] para todo \(n, e d_n\in\{1,2\}, logo não corremos o risco de ter infinitos 9 finais.

Passo 4

Mostramos que x não está na lista. De fato, para cada n temos que o n-ésimo dígito de x d_n difere do n-ésimo dígito de r_n a_{nn}. Logo x\neq r_n para todo n. Isso contradiz a hipótese de que a lista era completa.

Resposta

Não existe enumeração de (0,1) nem de \mathbb{R}. Logo, o conjunto dos reais é não enumerável.

Exercícios relacionados