Questão 20 Usando apenas a definição de enumerabilidade, mostre que a reunião de n conjuntos infinitos enumeráveis é enumerável.

Passo 1

O enunciado dá n conjuntos A_{1},A_{2},\dots,A_{n}. Cada um desses conjuntos é infinito e enumerável. A tarefa é mostrar que a reunião
A:=A_{1}\cup A_{2}\cup\cdots\cup A_{n}
é enumerável, usando apenas a definição de enumerabilidade.
Informações relevantes dadas:
  • Há exatamente n conjuntos: A_{1},\dots,A_{n}.
  • Cada A_{i} é infinito e enumerável (isto é, tem bijeção com \mathbb{N}).
  • Pedido: provar que A é enumerável (isto é, construir ou provar existência de uma bijeção \mathbb{N}\to A).

Passo 2

Recordando a definição de enumerável que vamos usar (exatamente a exigida): um conjunto S é enumerável quando existe uma bijeção
f:\mathbb{N}\to S.
Isso significa que é possível listar todos os elementos de S numa sequência f(1),f(2),f(3),\dots sem omitir nenhum e sem repetir (cada elemento de S aparece exatamente uma vez na lista).
Vou trabalhar diretamente com essa definição: a cada A_i corresponde uma bijeção para \mathbb{N}.

Passo 3

Como cada A_{i} é enumerável, para cada i\in\{1,\dots,n\} existe uma bijeção
f_{i}:\mathbb{N}\to A_{i}.
Explicando as variáveis: para cada i, f_{i}(m) é o m-ésimo elemento da enumeração de A_{i}. Como cada A_{i} é infinito, f_{i} é definida para todo m\in\mathbb{N}.

Passo 4

Construo uma sequência que percorre as enumerações dos A_{i} alternando-as (intercalando). Defino s:\mathbb{N}\to A por
s(t)=f_{r}\bigl(q\bigr),
onde
q=\left\lfloor\frac{t-1}{n}\right\rfloor+1, \qquad r=((t-1)\bmod n)+1.
Interpretação concreta: escrevo os valores de s em blocos de tamanho n assim:
s(1)=f_{1}(1),\\ s(2)=f_{2}(1),\\ \dots,\\ s(n)=f_{n}(1),
s(n+1)=f_{1}(2),\\ s(n+2)=f_{2}(2),\\ \dots,\\ s(2n)=f_{n}(2),
e assim por diante. Cada par (i,m) aparece em algum lugar da sequência: o elemento f_{i}(m) aparece em s\bigl((m-1)n+i\bigr).

Passo 5

Mostro que s é sobrejetora em A. Seja x\in A. Então existe algum i e algum m tais que x=f_{i}(m) (pois x pertence a algum A_{i} e f_{i} enumera A_{i}). O índice t=(m-1)n+i satisfaz s(t)=f_{i}(m)=x. Assim todo x\in A aparece em algum lugar da sequência s. Conclui-se que s é sobrejeção \mathbb{N}\twoheadrightarrow A.
Observação: s pode listar elementos repetidos (se as A_i não forem disjuntas, um mesmo elemento pode aparecer várias vezes em posições diferentes).

Passo 6

Agora converto a sobrejeção s numa bijeção h:\mathbb{N}\to A eliminando repetições, por uma construção passo a passo que usa somente \mathbb{N} e a sequência s.
Definição recursiva: seja t_{1}=1 e h(1)=s(t_{1}).
Supondo definidos t_{1}<t_{2}<\cdots<t_{k} e h(1),\dots,h(k) distintos, defino
t_{k+1}=\min\{t>t_{k}\mid s(t)\notin\{h(1),\dots,h(k)\}\}
e então
h(k+1)=s(t_{k+1}).
Preciso justificar que esse mínimo existe para todo k, ou seja, o processo nunca trava.

Passo 7

Justificativa de existência dos t_{k} infinitamente: suponha, por contradição, que para algum k não exista t>t_{k} com s(t)\notin\{h(1),\dots,h(k)\}. Isso significaria que todos os termos s(t) com t>t_{k} pertencem ao conjunto finito \{h(1),\dots,h(k)\}, então a imagem de s seria finita. Mas já vimos que a imagem de s contém A_{1} (pelo menos) e A_{1} é infinita; portanto a imagem de s é infinita. Logo existe sempre algum t>t_{k} com s(t) novo, e o mínimo existe. Assim a definição recursiva produz uma sequência infinita h(1),h(2),\dots.

Passo 8

Propriedades de h:
  • Injetividade: por construção cada h(k) é diferente dos anteriores, logo h é injetora.
  • Sobrejetividade: seja x\in A. Como em Passo 5, existe t com s(t)=x. No processo de construção de h, os termos da sequência s são examinados da esquerda para a direita e cada novo valor distinto é eventualmente escolhido como algum h(k). Assim x — que aparece em s — será escolhido em algum passo e pertence à imagem de h. Logo h é sobrejetora.
De injetividade + sobrejetividade segue que h é bijeção
h:\mathbb{N}\to A.

Passo 9

Concluímos que existe bijeção de \mathbb{N} sobre A. Pela definição de enumerabilidade usada, isto mostra que A é 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 A_{1}\cup A_{2}\cup\cdots\cup A_{n} é enumerável.

Exercícios relacionados