Questão 20 Usando apenas a definição de enumerabilidade, mostre que a reunião de
conjuntos infinitos enumeráveis é enumerável.
Passo 1
O enunciado dá
conjuntos
. Cada um desses conjuntos é infinito e enumerável. A tarefa é mostrar que a reunião
é enumerável, usando apenas a definição de enumerabilidade.
Informações relevantes dadas:
- Há exatamente
conjuntos: . - Cada
é infinito e enumerável (isto é, tem bijeção com ). - Pedido: provar que
é enumerável (isto é, construir ou provar existência de uma bijeção ).
Passo 2
Recordando a definição de enumerável que vamos usar (exatamente a exigida): um conjunto
é enumerável quando existe uma bijeção
Isso significa que é possível listar todos os elementos de
numa sequência
sem omitir nenhum e sem repetir (cada elemento de
aparece exatamente uma vez na lista).
Vou trabalhar diretamente com essa definição: a cada
corresponde uma bijeção para
.
Passo 3
Como cada
é enumerável, para cada
existe uma bijeção
Explicando as variáveis: para cada
,
é o
-ésimo elemento da enumeração de
. Como cada
é infinito,
é definida para todo
.
Passo 4
Construo uma sequência que percorre as enumerações dos
alternando-as (intercalando). Defino
por
onde
Interpretação concreta: escrevo os valores de
em blocos de tamanho
assim:
e assim por diante. Cada par
aparece em algum lugar da sequência: o elemento
aparece em
.
Passo 5
Mostro que
é sobrejetora em
. Seja
. Então existe algum
e algum
tais que
(pois
pertence a algum
e
enumera
). O índice
satisfaz
. Assim todo
aparece em algum lugar da sequência
. Conclui-se que
é sobrejeção
.
Observação:
pode listar elementos repetidos (se as
não forem disjuntas, um mesmo elemento pode aparecer várias vezes em posições diferentes).
Passo 6
Agora converto a sobrejeção
numa bijeção
eliminando repetições, por uma construção passo a passo que usa somente
e a sequência
.
Definição recursiva: seja
e
.
Supondo definidos e
distintos, defino
Supondo definidos
e então
Preciso justificar que esse mínimo existe para todo
, ou seja, o processo nunca trava.
Passo 7
Justificativa de existência dos
infinitamente: suponha, por contradição, que para algum
não exista
com
. Isso significaria que todos os termos
com
pertencem ao conjunto finito
, então a imagem de
seria finita. Mas já vimos que a imagem de
contém
(pelo menos) e
é infinita; portanto a imagem de
é infinita. Logo existe sempre algum
com
novo, e o mínimo existe. Assim a definição recursiva produz uma sequência infinita
.
Passo 8
Propriedades de
:
- Injetividade: por construção cada
é diferente dos anteriores, logo é injetora. - Sobrejetividade: seja
. Como em Passo 5, existe com . No processo de construção de , os termos da sequência são examinados da esquerda para a direita e cada novo valor distinto é eventualmente escolhido como algum . Assim — que aparece em — será escolhido em algum passo e pertence à imagem de . Logo é sobrejetora.
De injetividade + sobrejetividade segue que
é bijeção
Passo 9
Concluímos que existe bijeção de
sobre
. Pela definição de enumerabilidade usada, isto mostra que
é enumerável.
Um comentário final amigo: a ideia prática é simples e útil na prova e na prova oral da prova — intercalar as listas e depois eliminar repetições, garantindo que nenhum elemento ficou de fora.
Resposta
A reunião
é enumerável.