Questão 2. Sejam X_{1}, X_{2}, \ldots, X_{n}, \ldots conjuntos enumeráveis. Mostre que X=\bigcup_{n \in \mathbb{N}} X_{n} é também enumerável.
Dica: Use as bijeções f_{j}: \mathbb{N} \rightarrow X_{j} e defina f: \mathbb{N} \times \mathbb{N} \rightarrow X dada por f(n, j)=f_{j}(n).

Passo 1

O enunciado pede para mostrar que X=\bigcup_{j\in\mathbb{N}} X_{j} é enumerável, sabendo que cada conjunto X_{j} é enumerável. O que foi dado explicitamente:
  • Para cada j\in\mathbb{N} existe uma bijeção f_{j}: \mathbb{N}\to X_{j}.
    A tarefa é produzir uma enumeração de X (ou seja, mostrar que existe uma bijeção \mathbb{N}\to X, ou pelo menos uma surjeção \mathbb{N}\to X seguida de uma padronização que torne bijetiva).

Passo 2

Defina a função
f:\mathbb{N}\times\mathbb{N}\to X,\qquad f(n,j)=f_{j}(n).
Primeiro ver que f está bem definida: para qualquer par (n,j) tem-se f_{j}(n)\in X_{j}\subseteq X, logo f(n,j) é realmente um elemento de X. Portanto f é uma aplicação com domínio \mathbb{N}\times\mathbb{N} e contradomínio X.

Passo 3

Mostre que f é sobrejetora (surjetiva). Tome x\in X. Pelo modo como X foi definido, existe algum índice j_{0} tal que x\in X_{j_{0}}. Como f_{j_{0}} é bijeção \mathbb{N}\to X_{j_{0}}, existe n_{0}\in\mathbb{N} com f_{j_{0}}(n_{0})=x. Então
f(n_{0},j_{0})=f_{j_{0}}(n_{0})=x.
Isso prova que para todo x\in X existe (n,j)\in\mathbb{N}\times\mathbb{N} com f(n,j)=x; logo f é sobrejetora.

Passo 4

Agora precisamos usar que \mathbb{N}\times\mathbb{N} é enumerável. Vou construir explicitamente uma bijeção g:\mathbb{N}\to\mathbb{N}\times\mathbb{N}. Uma maneira clássica (método das diagonais / função de Cantor) é a seguinte. Para (a,b)\in\mathbb{N}\times\mathbb{N} defina
\pi(a,b)=\frac{(a+b)(a+b+1)}{2}+b.
A função \pi:\mathbb{N}\times\mathbb{N}\to\mathbb{N} é bijetora (é a função de pareamento de Cantor). Uma explicação sucinta do porquê ela é bijetora:
  • Os números da forma \dfrac{t(t+1)}{2} são os números triangulares T_{t}. Para cada z\in\mathbb{N} existe um único t tal que T_{t}\le z < T_{t+1}.
  • Dado z, defina t como o inteiro que satisfaz T_{t}\le z<T_{t+1}, e então b=z-T_{t} e a=t-b. Esses a,b são não-negativos e verificam \pi(a,b)=z. Isso dá a inversa explícita de \pi, provando que \pi é bijetora.
    Como \pi é bijeção \mathbb{N}\times\mathbb{N}\to\mathbb{N}, sua inversa g=\pi^{-1} é uma bijeção g:\mathbb{N}\to\mathbb{N}\times\mathbb{N}. (Intuitivamente: enumeramos os pares por diagonais (0,0),(1,0),(0,1),(2,0),(1,1),(0,2),\dots.)

Passo 5

Agora compose as funções: defina h=f\circ g:\mathbb{N}\to X. Para cada k\in\mathbb{N},
h(k)=f\big(g(k)\big)\in X.
Como f é sobrejetora e g é bijetora (em particular sobrejetora), a composição h é sobrejetora. Assim existe uma enumeração (possivelmente com repetições) de todos os elementos de X dada pela sequência \big(h(0),h(1),h(2),\dots\big).

Passo 6

Transformar a enumeração sobrejetora h em uma bijeção explicitando os elementos sem repetição (procedimento padrão). Construa a sequência (x_{0},x_{1},x_{2},\dots) por recorrência:
  • x_{0}=h(0).
  • Suponha x_{0},\dots,x_{m} já escolhidos; então escolha x_{m+1}=h(t) com t mínimo tal que h(t)\notin\{x_{0},\dots,x_{m}\}.
    Porque h é sobrejetora, todo elemento y\in X aparece em alguma posição h(s), logo no processo acima cada elemento de X será eventualmente escolhido como algum x_{k}. Assim p:\mathbb{N}\to X definida por p(k)=x_{k} é bijeção: é injetiva por construção (não há repetições na lista) e é sobrejetiva porque cobre todo X. Portanto existe bijeção \mathbb{N}\to X, isto é, X é enumerável.

Resposta

X é enumerável.

Exercícios relacionados