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 A_1,A_2,\dots,A_n são conjuntos infinitos e enumeráveis, mostrar que \displaystyle A_1\cup A_2\cup\cdots\cup A_n é enumerável.\n
  • Informações dadas (usadas como hipótese): cada A_i é infinito e enumerável, isto é, para cada i existe uma enumeração A_i=\{a_{i1},a_{i2},a_{i3},\dots\} que lista todos os elementos de A_i (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 \mathbb{N}. Equivalentemente, há uma lista (sequência) que enumera todos os elementos do conjunto sem deixar nenhum de fora: S=\{s_1,s_2,s_3,\dots\} e cada elemento de S aparece em alguma posição dessa lista.\n
  • Estratégia geral: construir explicitamente uma lista que contenha todos os elementos de \bigcup_{i=1}^n A_i. 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 \mathbb{N} e portanto mostrarei que a união é enumerável.

Passo 3

Caso base (união de duas coleções enumeráveis): provar que A\cup B é enumerável quando A e B são infinitos e enumeráveis.\n
  • Como A e B são enumeráveis, escrevo enumerações
A=\{a_1,a_2,a_3,\dots\}, \qquad B=\{b_1,b_2,b_3,\dots\}.
  • Construo uma lista que intercale os termos:
f(1)=a_1,\\ f(2)=b_1,\\ f(3)=a_2,\\ f(4)=b_2,\\ f(5)=a_3,\\ f(6)=b_3,\dots
em forma geral posso escrever f(2n-1)=a_n e f(2n)=b_n. Assim f:\mathbb{N}\to A\cup B é uma função cuja imagem contém todos os elementos de A e de B (logo é sobrejetora para A\cup B).\n
  • Esta lista f(1),f(2),\dots 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 f numa enumeração sem repetições, aplico o procedimento padrão: percorro a sequência f(1),f(2),\dots e construo uma nova sequência c_1,c_2,c_3,\dots onde c_1=f(1) e, para k\ge1, c_{k+1} é o primeiro termo f(m) com índice m maior do que o usado até então que seja diferente de todos c_1,\dots,c_k.\n
  • Propriedades dessa construção:\n
    1. Todos os c_j são distintos por construção, então a sequência não tem repetições.\n
    2. A sequência é infinita porque pelo menos um dos conjuntos A ou B é infinito (na hipótese ambos são infinitos), então haverá sempre novos elementos a serem listados; mesmo no caso extremo em que B\subseteq A a união é A, que é infinita, logo a lista com elementos distintos é infinita.\n
    3. A sequência é sobrejetora em A\cup B: dado x\in A\cup B, então x aparece em alguma posição da sequência f (porque f lista todos os elementos de A e de B); o primeiro aparecimento de x em f será incluído na sequência c_1,c_2,\dots. Assim todo x\in A\cup B aparece em algum c_j.\n
  • Conclusão do caso duas coleções: a sequência c_1,c_2,\dots estabelece uma bijeção entre \mathbb{N} e A\cup B. Logo A\cup B é enumerável.

Passo 4

Passo indutivo para a reunião finita (de n conjuntos):\n
  • Vou provar por indução sobre n que a união de n conjuntos infinitos enumeráveis é enumerável.\n
  • Base n=1: trivial, pois A_1 é enumerável por hipótese.\n
  • Passo indutivo: suponha que para algum k\ge1 vale que A_1\cup\cdots\cup A_k é enumerável. Considere agora
\left(A_1\cup\cdots\cup A_k\right)\cup A_{k+1}.
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 A_1\cup\cdots\cup A_k (enumerável pela hipótese indutiva) e A_{k+1} (enumerável por hipótese do enunciado), obtemos que a união com A_{k+1} também é enumerável. Assim a propriedade passa de k para k+1.\n
  • Pelo princípio da indução matemática, a união de qualquer número finito n 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á n conjuntos: escreva enumerações A_i=\{a_{i1},a_{i2},a_{i3},\dots\} e construa a sequência que percorre linhas e colunas da matriz (a_{ij}) por colunas ou por diagonal (por exemplo, a_{11},a_{21},\dots,a_{n1},a_{12},a_{22},\dots,a_{n2},\dots). 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 A_1,\dots,A_n são conjuntos infinitos enumeráveis então \displaystyle A_1\cup\cdots\cup A_n é enumerável.

Exercícios relacionados