Questão 24 Se
é um conjunto enumerável, mostre que
Passo 1
O enunciado dá que
é um conjunto enumerável e pede para mostrar que
é enumerável.
Informações relevantes que o enunciado fornece:
-
é enumerável (isto é, é finito ou tem o mesmo tamanho que ). - A definição do conjunto pedido é
.
O que se quer provar (pergunta do enunciado):
- Mostrar que o conjunto
é enumerável.
Passo 2
Primeiro caso simples: se
for finito então
também é finito (pois é imagem de
por uma operação), e todo conjunto finito é enumerável. Logo neste caso está provado. A parte interessante é quando
é infinito enumerável (contável infinito). A partir daqui assumo que
é enumerável infinito: existe uma enumeração
Vou trabalhar a partir dessa enumeração.
Passo 3
Idéia principal (sem pular passos): representar
como imagem do produto
através da aplicação que manda o par
para
. Mais precisamente, definir a função
Observação:
é exatamente a imagem
, porque todo elemento
com
aparece como
para algum
.
Portanto, basta mostrar que
é enumerável e que a imagem de um conjunto enumerável por uma função é enumerável. Vou provar essas duas coisas passo a passo.
Passo 4
Provar que
é enumerável (diagonalização explícita).
Construção explícita de uma enumeração (diagonal):
uma maneira clássica é listar os pares na ordem
uma maneira clássica é listar os pares
ou seja, primeiro os pares cuja soma
é
, depois soma
, depois
, e assim por diante, e dentro de cada soma ordenar por
crescente (ou outra ordem fixa). Essa lista contém todo par
exatamente uma vez, portanto define uma bijeção entre
e
(ou, mais fraco, uma enumeração surjetiva
). Conclusão:
é enumerável.
Comentário didático curto sobre por que isso funciona: todo par
tem soma
finita; na enumeração cada soma aparece em algum estágio, então o par aparece. Não há repetição porque cada par tem posição marcada pela sua soma e por sua ordem interna.
Passo 5
Provar que imagem de conjunto enumerável por função é enumerável.
Seja
enumerável e
qualquer função. Há dois subcasos:
- Se
é finito então é finito, logo enumerável. - Se
é enumerável infinito, então existe uma enumeração . Considere a sequência definida por . A sequência contém todos os elementos de , possivelmente com repetições. Para obter uma enumeração sem repetições de basta percorrer e tomar, na ordem, apenas as primeiras ocorrências de cada novo valor (algoritmo de “remover duplicatas mantendo a ordem”). Formalmente, define-se a subsequência dos índices tais que ainda não apareceu antes; essa subsequência é infinita se for infinito, ou termina se for finito. Assim obtém-se uma enumeração de . Conclusão: é enumerável.
Explicação intuitiva: a imagem não pode ser “maior” que o domínio em cardinalidade; enumerar o domínio e aplicar
dá uma lista da imagem com possíveis repetições, e eliminar repetições deixa uma enumeração válida.
Passo 6
Aplicar os fatos ao problema: já temos
-
é enumerável (Passo 4). - A função
mapeia sobre (Passo 3), isto é . - Pela propriedade do Passo 5, a imagem de um conjunto enumerável por uma função é enumerável.
Portanto
é enumerável.
Passo 7
Pequeno exemplo para fixar a ideia: se
então
, e sabemos que
é enumerável — isso é compatível com a prova geral (a função
envia
sobre
).