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:
, e . Ou seja, cada um deles tem uma enumeração (uma correspondência bijetiva) com os naturais. - O problema pede: mostrar que a reunião
também é enumerável (ou seja, existe uma bijeção entre e ) 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
é enumerável (countably infinite) se existe uma bijeção . - Aqui
. - Bijeção significa que
é injetora (elementos distintos de vão para elementos distintos de ) e sobrejetora (todo elemento de é imagem de algum natural).
- Aqui
- Outra linguagem frequente: é suficiente construir uma aplicação
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
são enumeráveis infinitos, existem bijeções
Isto significa que
enumera todos os elementos de
sem faltar nenhum (cada um aparece exatamente uma vez), e analogousamente para
e
.
Passo 4
Construindo uma sequência que cobre toda a reunião (possivelmente com repetições).
Defina uma função
por intercalamento:
Explicando: a sequência
vale
- Por que
é sobrejetora em ? Porque qualquer elemento pertence a pelo menos um dos conjuntos ou . Se então existe com , logo . Caso ou há argumento parecido. Logo todo elemento da reunião aparece em algum lugar da sequência . - Observação:
pode repetir elementos (se, por exemplo, um mesmo elemento aparece na posição correspondente a e também a ). 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
que lista, na ordem de primeira aparição em
, os elementos distintos de
.
Definição por recorrência:
- Primeiro,
. - Supondo
já definidos e distintos, definimos como o primeiro termo (isto é, o de menor índice ) tal que .
Precisamos mostrar que essa definição faz sentido (ou seja, tal
existe para todo
).
Passo 6
Porque sempre existe um próximo elemento novo (justificando bem para prova).
Argumento: a imagem de
é
, que é infinita (união de três conjuntos infinitos contém infinitos elementos). Portanto a sequência
tem infinitamente muitas aparições de elementos distintos. Assim, para qualquer conjunto finito
existe algum índice
com
. Aplicando isso com
(que é finito), existe
tal que
. Tomando o menor desses
define-se
. Logo
fica bem definida para todo
.
Passo 7
Provar que
é bijetora
.
- Injetividade: por construção os termos
são todos distintos (cada novo termo é escolhido fora do conjunto dos anteriores). Logo é injetora. - Sobrejetividade: seja
. Como é sobrejetora existe um índice mínimo tal que (mínimo no conjunto dos índices que produzem ). Quando definimos escolhemos para cada o primeiro que ainda não apareceu antes; portanto, ao chegar ao momento em que todos os elementos distintos entre já foram listados, o próximo será precisamente . Em outras palavras, o elemento aparece em exactamente na posição correspondente à sua primeira aparição em . Assim está na imagem de . Portanto é sobrejetora.
Como
é injetora e sobrejetora, é bijeção entre
e
.
Passo 8
Fechamento e observações práticas para a prova.
- Consequência direta: existe bijeção
, logo é 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.