Supondo que A e B são dois conjuntos enumeráveis, mostre que o conjunto A cup B é 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
f:Nto A
e
g:Nto B
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
S=(f(1),;g(1),;f(2),;g(2),;f(3),;g(3),;dots)
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.

Exercícios relacionados