Questão 19 Usando apenas a definição de enumerabilidade, mostre que a reunião de três conjuntos infinitos enumeráveis é enumerável.

Passo 1

O que o enunciado dá e o que pede.
  • São dados três conjuntos infinitos enumeráveis: A, B e C. Ou seja, cada um deles tem uma enumeração (uma correspondência bijetiva) com os naturais.
  • O problema pede: mostrar que a reunião A\cup B\cup C também é enumerável (ou seja, existe uma bijeção entre \mathbb{N} e A\cup B\cup C) usando apenas a definição de enumerabilidade.

Passo 2

Lembrando a definição e conceitos básicos (passo-a-passo, sem pressa).
  • Definição que vamos usar: um conjunto X é enumerável (countably infinite) se existe uma bijeção f:\mathbb{N}\to X.
    • Aqui \mathbb{N}=\{0,1,2,\dots\}.
    • Bijeção significa que f é injetora (elementos distintos de \mathbb{N} vão para elementos distintos de X) e sobrejetora (todo elemento de X é imagem de algum natural).
  • Outra linguagem frequente: é suficiente construir uma aplicação \varphi:\mathbb{N}\to X que seja sobrejetora e então eliminar repetições para transformar em bijeção. Vou usar essa ideia construtiva.

Passo 3

Fixando enumerações dos três conjuntos (isso vem da hipótese).
Pela hipótese de que A,B,C são enumeráveis infinitos, existem bijeções
f:\mathbb{N}\to A,\qquad g:\mathbb{N}\to B,\qquad h:\mathbb{N}\to C.
Isto significa que f(0),f(1),\dots enumera todos os elementos de A sem faltar nenhum (cada um aparece exatamente uma vez), e analogousamente para g e h.

Passo 4

Construindo uma sequência que cobre toda a reunião (possivelmente com repetições).
Defina uma função s:\mathbb{N}\to A\cup B\cup C por intercalamento:
s(3n)=f(n),\qquad s(3n+1)=g(n),\qquad s(3n+2)=h(n)\quad\text{para todo }n\in\mathbb{N}.
Explicando: a sequência s(0),s(1),s(2),s(3),\dots vale
f(0),\; g(0),\; h(0),\; f(1),\; g(1),\; h(1),\; f(2),\; g(2),\; h(2),\dots
  • Por que s é sobrejetora em A\cup B\cup C? Porque qualquer elemento x\in A\cup B\cup C pertence a pelo menos um dos conjuntos A,B ou C. Se x\in A então existe n com f(n)=x, logo s(3n)=x. Caso x\in B ou x\in C há argumento parecido. Logo todo elemento da reunião aparece em algum lugar da sequência s.
  • Observação: s pode repetir elementos (se, por exemplo, A\cap B\neq\varnothing um mesmo elemento aparece na posição correspondente a f e também a g). Isso não é problema: agora vamos tirar repetições mantendo a ordem de primeira aparição.

Passo 5

Construindo a enumeração sem repetições (passo construtivo e detalhado).
Vamos definir uma nova sequência t:\mathbb{N}\to A\cup B\cup C que lista, na ordem de primeira aparição em s, os elementos distintos de A\cup B\cup C.
Definição por recorrência:
  • Primeiro, t(0)=s(0).
  • Supondo t(0),\dots,t(m-1) já definidos e distintos, definimos t(m) como o primeiro termo s(k) (isto é, o de menor índice k) tal que s(k)\notin\{t(0),\dots,t(m-1)\}.
Precisamos mostrar que essa definição faz sentido (ou seja, tal k existe para todo m).

Passo 6

Porque sempre existe um próximo elemento novo (justificando bem para prova).
Argumento: a imagem de s é A\cup B\cup C, que é infinita (união de três conjuntos infinitos contém infinitos elementos). Portanto a sequência (s(n))_{n\in\mathbb{N}} tem infinitamente muitas aparições de elementos distintos. Assim, para qualquer conjunto finito F\subset A\cup B\cup C existe algum índice k com s(k)\notin F. Aplicando isso com F=\{t(0),\dots,t(m-1)\} (que é finito), existe k tal que s(k)\notin F. Tomando o menor desses k define-se t(m). Logo t fica bem definida para todo m.

Passo 7

Provar que t é bijetora \mathbb{N}\to A\cup B\cup C.
  • Injetividade: por construção os termos t(0),t(1),\dots são todos distintos (cada novo termo é escolhido fora do conjunto dos anteriores). Logo t é injetora.
  • Sobrejetividade: seja x\in A\cup B\cup C. Como s é sobrejetora existe um índice k_0 mínimo tal que s(k_0)=x (mínimo no conjunto dos índices que produzem x). Quando definimos t escolhemos para cada m o primeiro s(k) que ainda não apareceu antes; portanto, ao chegar ao momento em que todos os elementos distintos entre s(0),\dots,s(k_0-1) já foram listados, o próximo t(\cdot) será precisamente s(k_0)=x. Em outras palavras, o elemento x aparece em t exactamente na posição correspondente à sua primeira aparição em s. Assim x está na imagem de t. Portanto t é sobrejetora.
Como t é injetora e sobrejetora, é bijeção entre \mathbb{N} e A\cup B\cup C.

Passo 8

Fechamento e observações práticas para a prova.
  • Consequência direta: existe bijeção t:\mathbb{N}\to A\cup B\cup C, logo A\cup B\cup C é enumerável.
  • Método prático que vale na prova: dado enumerações de cada conjunto, intercale-as (por exemplo em blocos de três) para obter uma sequência sobrejetora; depois remova repetições mantendo a ordem de primeira ocorrência — isso fornece uma enumeração (bijeção) da união. É um argumento padrão e elementar que só usa a definição de enumerabilidade.

Resposta

A\cup B\cup C é enumerável.

Exercícios relacionados