Mostre que a união de conjuntos enumeráveis é também enumerável.

Passo 1

O enunciado pede para mostrar que, se temos dois conjuntos enumeráveis (ou seja, existem enumerações de cada um deles), então a união desses conjuntos também admite uma enumeração. O conteúdo envolve a definição de conjunto enumerável (existência de surjeção ou bijeção com N) e a construção de uma enumeração para a união.

Passo 2

Um conjunto X é chamado de enumerável se existe uma surjeção f:Nto X (ou bijeção com N no caso infinito). Sejam A e B dois conjuntos enumeráveis. Então, existem surjeções
f:Nto A,
g:Nto B

Passo 3

Para construir uma enumeração da união Acup B, vamos intercalar as imagens de f e g. Definimos a função h:Nto Acup B da seguinte forma:
h(n)=f(k),&se n=2k,g(k),&se n=2k+1

Passo 4

Agora, mostramos que h é sobrejetora em Acup B. Se xin Acup B, então ou xin A ou xin B. Se xin A, existe k tal que f(k)=x e então h(2k)=x. Se xin B, existe k tal que g(k)=x e então h(2k+1)=x. Logo, todo xin Acup B tem um pré-imagem por h.

Passo 5

Como encontramos uma surjeção h:Nto Acup B, concluímos que Acup B é enumerável.

Resposta

A união de dois conjuntos enumeráveis é enumerável, pois podemos construir explicitamente uma enumeração intercalando as enumerações de cada conjunto.

Exercícios relacionados