Questão 29 Mostre que a reunião finita de conjuntos infinitos enumeráveis é um conjunto enumerável.
Passo 1
O que o enunciado pede e o que nos dá:\n
- Pede para provar que a reunião (união) finita de conjuntos infinitos enumeráveis é um conjunto enumerável. Em outras palavras, se
são conjuntos infinitos e enumeráveis, mostrar que é enumerável.\n - Informações dadas (usadas como hipótese): cada
é infinito e enumerável, isto é, para cada existe uma enumeração que lista todos os elementos de (possivelmente com repetições se a mesma notação aparecer em outra lista).
Passo 2
Definições e ideias principais (explicadas como se eu estivesse ao lado explicando):\n
- “Enumerável” (ou “contável numerável”) aqui significa que o conjunto tem uma bijeção com
. Equivalentemente, há uma lista (sequência) que enumera todos os elementos do conjunto sem deixar nenhum de fora: e cada elemento de aparece em alguma posição dessa lista.\n - Estratégia geral: construir explicitamente uma lista que contenha todos os elementos de
. Se eu conseguir transformar essa lista (possivelmente com repetições) numa lista sem repetições que ainda contenha todo o conjunto, terei uma bijeção com e portanto mostrarei que a união é enumerável.
Passo 3
Caso base (união de duas coleções enumeráveis): provar que
é enumerável quando
e
são infinitos e enumeráveis.\n
- Como
e são enumeráveis, escrevo enumerações
- Construo uma lista que intercale os termos:
em forma geral posso escrever
e
. Assim
é uma função cuja imagem contém todos os elementos de
e de
(logo é sobrejetora para
).\n
- Esta lista
pode ter repetições quando um elemento pertence a ambos os conjuntos, ou quando a enumeração interna já repetia elementos (mas enumerações geralmente listam elementos possivelmente repetidos se não for cuidada). Para transformar numa enumeração sem repetições, aplico o procedimento padrão: percorro a sequência e construo uma nova sequência onde e, para , é o primeiro termo com índice maior do que o usado até então que seja diferente de todos .\n - Propriedades dessa construção:\n
- Todos os
são distintos por construção, então a sequência não tem repetições.\n - A sequência é infinita porque pelo menos um dos conjuntos
ou é infinito (na hipótese ambos são infinitos), então haverá sempre novos elementos a serem listados; mesmo no caso extremo em que a união é , que é infinita, logo a lista com elementos distintos é infinita.\n - A sequência é sobrejetora em
: dado , então aparece em alguma posição da sequência (porque lista todos os elementos de e de ); o primeiro aparecimento de em será incluído na sequência . Assim todo aparece em algum .\n
- Todos os
- Conclusão do caso duas coleções: a sequência
estabelece uma bijeção entre e . Logo é enumerável.
Passo 4
Passo indutivo para a reunião finita (de
conjuntos):\n
- Vou provar por indução sobre
que a união de conjuntos infinitos enumeráveis é enumerável.\n - Base
: trivial, pois é enumerável por hipótese.\n - Passo indutivo: suponha que para algum
vale que é enumerável. Considere agora
Pelo passo anterior (união de duas coleções enumeráveis) a união de um conjunto enumerável com outro enumerável é enumerável. Aplicando isso a
(enumerável pela hipótese indutiva) e
(enumerável por hipótese do enunciado), obtemos que a união com
também é enumerável. Assim a propriedade passa de
para
.\n
- Pelo princípio da indução matemática, a união de qualquer número finito
de conjuntos infinitos enumeráveis é enumerável.
Passo 5
Observações finais e algoritmo prático (para a prova):\n
- Método prático para construir a enumeração quando há
conjuntos: escreva enumerações e construa a sequência que percorre linhas e colunas da matriz por colunas ou por diagonal (por exemplo, ). Depois remova repetições pegando apenas a primeira ocorrência de cada elemento. Esse processo sempre dá uma enumeração completa sem repetições.\n - Moral: intercalar as listas e eliminar repetições garante que nenhum elemento da união fique de fora, e a união permanece infinita porque cada conjunto em si é infinito.
Resposta
Se
são conjuntos infinitos enumeráveis então
é enumerável.