Questão 23 Mostre que
é enumerável.
Passo 1
O que o enunciado pede e o que ele dá.
- Pede: mostrar que o conjunto
é enumerável (contável). - Informação dada: a descrição explícita do conjunto como pares de racionais
combinados na forma .
Vou provar que existe uma enumeração (uma lista) dos elementos de
, isto é, que se pode colocar os elementos em sequência
, de forma que toda elemento do conjunto apareça em alguma posição da sequência.
Passo 2
Definição e ideia geral (aula rápida).
- Definição de enumerável / contável: um conjunto
é enumerável (ou contável) se existe uma função injetora de em (ou equivalentemente uma bijeção entre e um subconjunto de ), ou mais intuitivamente se os elementos de podem ser listados como uma sequência onde cada elemento de aparece pelo menos uma vez. Para conjuntos infinitos dizemos “contável infinito”. - Estratégia para o problema: mostrar uma bijeção entre
e (o produto cartesiano dos racionais com os racionais), e então mostrar que é enumerável. Como produto de dois conjuntos enumeráveis é enumerável, isso conclui.
Passo 3
Mostrar que
é enumerável (a parte sobre contar os racionais).
- Primeiro, lembrar que
é enumerável por definição. Mostrar que é enumerável: uma enumeração explícita é
ou formalmente uma bijeção
dada por
Isso prova que
é enumerável.
-
Agora
é enumerável: pense numa grade infinite de pares e percorra-a por diagonais (método de Cantor). Um modo prático é listar pares por ordem crescente de , e para cada soma fixa listar todos os pares com essa soma numa ordem finita. Esse procedimento lista todos os pares sem repetir, provando que é enumerável. -
Há uma aplicação natural sobrejetora de
em : definir
Como domínio é enumerável e existe uma aplicação sobrejetora para
, segue que
é enumerável (um sobrejeto de um conjunto enumerável é no máximo enumerável; aqui cada racional aparece possivelmente várias vezes, mas isso não impede enumerabilidade).
- Finalmente, produto de dois conjuntos enumeráveis é enumerável. Uma enumeração explícita de
pode ser feita assim: enumerar e então listar pares na ordem
novamente por diagonais na matriz
. Assim
é enumerável.
(Resumo:
enumerável
enumerável
enumerável
enumerável
enumerável.)
Passo 4
Construir a aplicação natural entre
e
.
Definir a função
Por definição todo elemento de
tem a forma
com
, portanto
é sobrejetora (cada elemento da direita tem pelo menos um pré‑imagem).
Para concluir que
é enumerável é suficiente mostrar que
é injetora ou pelo menos que existe uma bijeção entre
e
. Vou provar que
é injetora, logo é bijetora (pois já é sobrejetora).
Passo 5
Provar que
é injetora (a parte essencial: independência linear de
e
sobre
).
Suponha que
ou seja
Rearranjando,
Chamando
e
, temos
Se
então
, logo
e
. Se
, então
o que é impossível porque
é irracional (prova clássica: suponha
em forma irredutível e obtenha contradição com paridade). Portanto não pode ocorrer
. Assim
e
, isto é
e
. Logo
é injetora.
Como
é injetora e sobrejetora, é bijetora, e por consequência existe bijeção entre
(enumerável) e
.
Passo 6
Conclusão final e motivação prática para prova de exame.
- Mostramos que
é enumerável (porque é enumerável e produto de dois enumeráveis é enumerável). - Construímos a aplicação natural
e provamos que ela é bijetora usando que é irracional (ou, dito de outra forma, que e são linearmente independentes sobre ). - Assim
está em bijeção com um conjunto enumerável, logo é enumerável.
Dica de prova curta para a prova: escreva a bijeção
, diga rapidamente que é sobrejetora por definição e injetora porque
(usar irracionalidade de
). Termine lembrando que
é enumerável.