Supondo que
e
são dois conjuntos enumeráveis, mostre que o conjunto
é enumerável.
Passo 1
O enunciado diz que os conjuntos A e B são enumeráveis, ou seja, cada um deles pode ser listado em sequência infinita. O conteúdo principal é a definição de conjunto enumerável (ou numerável): um conjunto C é enumerável se existe uma função sobrejetora de ℕ em C. Vamos usar as enumerações de A e B para construir uma enumeração de A ∪ B.
Passo 2
Como A e B são enumeráveis, existem funções sobrejetoras
e
que listam todos os elementos de A e B, possivelmente com repetições.
Passo 3
Vamos criar uma sequência intercalada S que pega alternadamente termos de A e de B. Por exemplo, indexando ℕ a partir de 1, definimos
Essa sequência percorre todos os elementos de A e B, mas pode repetir alguns.
Passo 4
Para obter de S um enumerador de A ∪ B sem repetições, definimos h:ℕ→A∪B removendo duplicatas de S. De modo ilustrativo, fazemos:
- h(1)=S(1).
- Para n>1, h(n) é o primeiro termo de S que ainda não apareceu entre h(1),…,h(n−1).
Assim, h lista exatamente cada elemento de A ∪ B uma única vez.
Passo 5
Precisamos verificar que h é sobrejetora em A ∪ B. Dado x em A ∪ B, x aparece em S (já que S percorre f e g). Logo, na varredura de S para definir h, em algum passo x será escolhido como h(k). Isso mostra que h(ℕ)=A ∪ B, ou seja, h é enumeração de A ∪ B. Portanto A ∪ B é enumerável.
Resposta
O conjunto A ∪ B é enumerável.