Mostre que o conjunto
, onde Q é o conjunto dos racionais, é um conjunto enumerável.
Passo 1
O enunciado define o conjunto
e pede para mostrar que
é enumerável. Informações dadas e pedidos, listados claramente:
- Dados:
é o conjunto dos números racionais; e variam em . - Pedido: provar que o conjunto
é enumerável (isto é, que seus elementos podem ser listados em uma sequência, possivelmente infinita, sem deixar nenhum de fora).
Passo 2
O que significa “enumerável” exatamente? Vou explicar de um jeito prático e sem formalismo exagerado.
- Dizemos que um conjunto
é enumerável (ou contável) se existe uma sequência que lista todos os seus elementos, isto é, se existe uma função sobrejetora da enumeração natural para . Em linguagem alternativa e equivalente: é enumerável se é finito ou tem a mesma quantidade de elementos que (os naturais). - Ideia que vou usar (sem resolver ainda): se eu conseguir estabelecer uma correspondência simples entre
e um conjunto que já sabemos enumerável, então também será enumerável. Não vou decidir o método final aqui; só deixei claro o objetivo.
Passo 3
Primeiro fato útil (e que vamos precisar):
é enumerável. Vou provar isso de forma didática e curta.
- Plano: representar cada racional como uma fração inteira
com e . Logo, está contido em . - Passo intermediário: mostrar que
e são enumeráveis. -
é enumerável porque se pode listar os inteiros como . Assim há uma sequência que percorre todos os inteiros. -
é enumerável pelo método da diagonalização: organize pares numa grade e percorra as diagonais (por exemplo, ). Isso lista todos os pares sem repetir nenhum.
-
- Conclusão dessa etapa: como
é enumerável, também é enumerável (produto de dois conjuntos enumeráveis é enumerável — pode-se compor as enumerações). E é imagem (subconjunto) de pelo mapeamento (tomando ). Logo é enumerável (pode-se enumerar todas as frações e, se necessário, pular repetições).
Passo 4
Agora um fato útil que também vou usar: se
e
são conjuntos enumeráveis então
é enumerável. Vou justificar de maneira explícita e prática.
- Seja
e enumerações (ou seja, funções sobrejetoras). Então podemos enumerar pela sequência que percorre os pares na ordem das diagonais. Como essa sequência atinge todos os pares, é enumerável. - Aplicação: como
é enumerável (Passo 3), o produto também é enumerável.
Passo 5
Agora vou relacionar
com
. Defina a função
Vou mostrar que
é bijetora (uma bijeção), o que dará imediatamente que
tem a mesma cardinalidade de
e, portanto, é enumerável.
Passo 6
Verificação de sobrejetividade (cada elemento de
vem de algum par
).
- Por definição de
, todo elemento é da forma com . Logo existe tal que . Portanto é sobrejetora.
Passo 7
Verificação de injetividade (se
então
).
- Suponha que
. Então Subtraindo os termos racionais de ambos os lados obtemos O lado esquerdo é racional, pois é diferença de racionais. Assim temos uma igualdade entre um racional e outro racional multiplicado por . - Aqui precisamos usar que
é irracional. Vou provar isso brevemente (prova clássica por contradição): - Suponha, para contradizer, que
fosse racional. Então para alguns inteiros sem fator comum, . - Elevando ao quadrado:
, logo . Isso mostra que é par, logo é par; escreva . - Substituindo:
dá e dividindo por 2: . Assim é par, então é par. - Conclusão:
e são ambos pares, o que contraria a hipótese de serem primos entre si. Contradição. Logo é irracional.
- Suponha, para contradizer, que
- Voltando à igualdade
: a única maneira de um número racional ser igual ao produto de outro racional com um número irracional é que ambos os racionais sejam zero. Mais formalmente, se e satisfazem , então se teríamos racional, impossibilidade. Logo e então . - Aplicando isso aqui:
e . Logo e . Assim é injetora.
Passo 8
Da Passo 6 e Passo 7 temos que
é bijetora entre
e
. Portanto
tem exatamente a mesma cardinalidade que
.
- Como mostrados antes,
é enumerável e o produto de dois conjuntos enumeráveis é enumerável. Logo é enumerável. - Conclusão final:
é enumerável.