Prove que o conjunto dos números racionais é enumerável.
Passo 1
O enunciado pede para provar que o conjunto dos números racionais é enumerável, ou seja, que existe uma bijeção entre e . Vamos usar teoria de conjuntos contáveis, mostrando que conjuntos como e são countáveis e, em seguida, relacionar com um desses produtos.
Passo 2
Definição: um conjunto é chamado enumerável (ou contável infinito) se existe bijeção
Mostraremos várias bijeções intermediárias para chegar em .
Passo 3
Vamos construir uma bijeção
Definimos
É fácil ver que cada inteiro aparece exatamente uma vez em , logo é bijetora e é enumerável.
Passo 4
Agora estabelecemos uma bijeção
Usamos a enumeração por diagonais: para cada liste todos os pares tais que , variando de a . Indexe esses pares em ordem crescente de . Assim cada surge numa posição finita de , dando uma bijeção .
Passo 5
Como e são ambos enumeráveis, o produto também é enumerável: basta compor
onde gtimesid age em cada componente, e isso preserva bijeção. Logo ZtimesN é enumerável.
Passo 6
Cada racional rinQ pode ser escrito de forma única em “fração irredutível”
r = pq, pinZ,;qinN,;q>0,;gcd(p,q)=1
Defina
psicolon Qto ZtimesN, psil(tfracpqr)=(p,q)
Esse psi é injetora (cada racional em sua forma irredutível mapeia num par diferente) e tem imagem contida em ZtimesN. Como ZtimesN é enumerável, todo subconjunto infinito injetado também é enumerável. Logo Q é enumerável.