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 extraídas do enunciado:
Informações relevantes extraídas do enunciado:
-
é enumerável (isto significa que é finito ou numerável infinito). - Deve-se provar que o conjunto de todas as somas de dois elementos de
também é enumerável.
Passo 2
Vou lembrar exatamente o que significa “enumerável” (para a gente não tropeçar nas palavras). Dizemos que um conjunto
é enumerável quando ele é finito ou existe uma enumeração infinita sem repetições, isto é, existe uma bijeção entre
e
(quando é infinito) ou então
tem fimito número de elementos. Em termos práticos: enumerável = dá para listar seus elementos em uma sequência
possivelmente terminando se for finito.
Estratégia geral (sem resolver ainda): tratar separadamente o caso finito e o caso infinito numerável; no caso infinito, usar que produto de conjuntos enumeráveis é enumerável (em particular é enumerável) e que a imagem de um conjunto enumerável por uma função é enumerável.
Estratégia geral (sem resolver ainda): tratar separadamente o caso finito e o caso infinito numerável; no caso infinito, usar que produto de conjuntos enumeráveis é enumerável (em particular
Passo 3
Caso simples:
é finito.
Se tem
elementos então
tem
elementos e, portanto, o conjunto de somas
é subconjunto de um conjunto finito, logo é finito e, portanto, enumerável. Concluímos o caso finito. Agora vamos ao caso mais interessante:
é infinito enumerável.
Se
Passo 4
Se
é infinito enumerável, existe uma enumeração
ou seja, uma bijeção
dada por
. Vou usar essa enumeração para construir enumerações para conjuntos relacionados. Primeiro mostro que
é enumerável.
Explicação/lembrança didática: já se conhece que é enumerável — uma forma intuitiva é a enumeração diagonal:
Explicação/lembrança didática: já se conhece que
em que se percorrem as diagonais
. Isso dá uma sequência que lista todos os pares
sem repetição. Outra forma é usar a função de Cantor, mas a ideia geométrica da diagonal é suficiente e mais intuitiva.
Como existe bijeção , a aplicação
dada por
é bijetora. Assim, como
é enumerável, segue que
também é enumerável. Ou seja, existe uma enumeração
Como existe bijeção
Passo 5
Agora passo à função soma. Defina
por
O conjunto
é exatamente a imagem de
, isto é,
. Como
é enumerável e
é uma aplicação (qualquer aplicação), a imagem
é enumerável. Vou explicar por que a imagem de um conjunto enumerável é enumerável (essa é uma propriedade importante e que costuma cair em prova).
Passo 6
Prova de que imagem de conjunto enumerável é enumerável (procedimento construtivo): seja
enumerável e
qualquer função. Se
é finito,
é finito e pronto. Se
é numerável infinito, temos enumeração
. Então os elementos de
aparecem entre os termos da sequência
. Para listar
sem repetições, fazemos o seguinte procedimento: percorre a sequência
e ao encontrar um valor novo (ainda não listado) adiciona-o na lista de imagem; ao encontrar um valor que já apareceu, ignora. Como todo elemento de
é da forma
para algum
, cada elemento de
eventualmente aparecerá e será listado. Assim obtemos uma sequência sem repetições que enumera
. Logo
é finito ou numerável infinito; em qualquer caso é enumerável. Aplicando isso a
e
obtemos que
é enumerável.
Passo 7
Resumo construtivo final (versão prática para prova): se
então enumere os pares
pela diagonal e escreva a sequência correspondente de somas
pulando repetições quando necessário. Essa sequência lista todos os elementos de
. Assim
é enumerável. (Se
for finito, o argumento é ainda mais simples:
é subconjunto de um conjunto finito e, portanto, finito.)