Questão 22 Se
é um conjunto infinito enumerável e
, usando apenas as definições de conjuntos finitos e enumeráveis, mostre que
é também enumerável.
Passo 1
O enunciado dá as seguintes informações e pede o que segue:
-
Informações dadas:
-
é um conjunto infinito enumerável. -
é um conjunto finito com exatamente elementos.
-
-
O que é pedido:
- Mostrar que
é enumerável (isto é, que existe uma enumeração de por números naturais).
- Mostrar que
Vou seguir apenas as definições de conjunto finito e enumerável, sem usar teoremas prontos além dessas definições.
Passo 2
Recordando as definições que vamos usar (explicadas devagarinho):
-
Dizemos que um conjunto
é enumerável (ou denumerável) se existe uma bijeção . Aqui é o conjunto dos números naturais . A bijeção significa que é injetora (valores diferentes de dão elementos diferentes de ) e sobrejetora (todo elemento de aparece como para algum ). -
Dizemos que um conjunto
é finito se existe tal que existe uma bijeção entre e . No problema foi dado que tem exatamente elementos e já foi escrita como .
Essas duas definições são tudo o que usaremos explicitamente.
Passo 3
Como
é enumerável e infinito, existe uma bijeção
Isto nos fornece uma “lista” de todos os elementos de
:
essa sequência contém cada elemento de
exatamente uma vez.
Nota intuitiva: alguns desses
podem coincidir com os elementos
de
; outros não. Vamos eliminar da lista todos os elementos que pertencem a
e mostrar que o que sobra ainda é uma enumeração (ou seja, pode ser colocada em bijeção com
).
Passo 4
Identificamos os índices onde aparecem os elementos de
na enumeração
. Como
e
é sobrejetora, para cada
existe pelo menos um índice
tal que
Como os
são elementos distintos (são os
elementos dados de
), os índices
são
números naturais distintos. Assim definimos o conjunto finito de índices
Observação importante: cada elemento de
aparece em algum lugar da lista
, então todos os
existem; e há apenas finitamente muitos desses índices porque
é finito.
Passo 5
Agora consideremos os números naturais que não pertencem a
. O conjunto
é infinito (porque
é infinito e remover um conjunto finito de índices deixa um conjunto infinito). Ordenando esses naturais em ordem crescente, obtemos uma sequência estritamente crescente de índices:
onde cada
e a sequência percorre todos os elementos de
(isto é,
é o menor natural fora de
,
é o segundo menor fora de
, e assim por diante). A existência dessa sequência é trivial: basta escolher o menor natural não em
para
, depois o menor maior que
não em
para
, etc.; como
é infinito esse procedimento continua indefinidamente.
Passo 6
Definimos a função
por
Explicando: escolhemos apenas os termos da lista
cujos índices não estão em
, ou seja, pulamos os termos que correspondem a elementos de
. Como
, tem-se
, logo
. Assim
está bem definida com imagem contida em
.
Passo 7
Mostro que
é sobrejetora em
(ou seja, que para todo
existe
com
):
Se
, então
mas
. Como
é sobrejetora em
, existe
tal que
. Como
, o índice
não pertence a
. Logo
. Pela definição dos
(que enumeram todos os elementos de
em ordem), existe
tal que
. Então
. Assim todo
é atingido por
. Conclusão:
é sobrejetora.
Passo 8
Mostro que
é injetora (ou seja, valores
distintos para
distintos):
Suponha
. Isso significa
. Como
é injetora (é bijeção), temos
. Mas a sequência
tem termos estritamente crescentes, então
implica
. Portanto
é injetora.
Passo 9
Como
é injetora e sobrejetora,
é bijeção entre
e
. Pela definição de enumerável (existe bijeção
conjunto), concluímos que
é enumerável.
Interpretando em palavras: a enumeração original de
tinha os elementos de
espalhados em posições finitas; ao simplesmente ignorar essas posições obtemos uma enumeração completa e sem repetições de
.
Passo 10
Comentário final de incentivo: deu trabalho listar as etapas, mas a ideia é simples e muito útil em provas — remover um número finito de elementos de um conjunto enumerável deixa o conjunto ainda enumerável. Agora você consegue reaplicar esse argumento sempre que precisar!