Prove que o conjunto Q dos números racionais é enumerável.

Passo 1

O enunciado pede para provar que o conjunto Q dos números racionais é enumerável, ou seja, que existe uma bijeção entre N e Q. Vamos usar teoria de conjuntos contáveis, mostrando que conjuntos como Z e NtimesN são countáveis e, em seguida, relacionar Q com um desses produtos.

Passo 2

Definição: um conjunto A é chamado enumerável (ou contável infinito) se existe bijeção
fcolon Nto A
Mostraremos várias bijeções intermediárias para chegar em Q.

Passo 3

Vamos construir uma bijeção
gcolon Nto Z
Definimos
g(0)=0, g(2n-1)=+n, g(2n)=-n (n>=1)
É fácil ver que cada inteiro aparece exatamente uma vez em g(0),g(1),g(2),dots, logo g é bijetora e Z é enumerável.

Passo 4

Agora estabelecemos uma bijeção
hcolon Nto NtimesN
Usamos a enumeração por diagonais: para cada kinN liste todos os pares (i,j) tais que i+j=k, variando i de 0 a k. Indexe esses pares em ordem crescente de k. Assim cada (i,j) surge numa posição finita de N, dando uma bijeção h.

Passo 5

Como Z e N são ambos enumeráveis, o produto ZtimesN também é enumerável: basta compor
Nxrightarrowh NtimesN xrightarrow(gtimesid) ZtimesN,
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.

Resposta

O conjunto Q dos números racionais é enumerável.

Exercícios relacionados