Questão 30 Mostre que o produto cartesiano de n conjuntos infinitos enumeráveis é também um conjunto enumerável.

Passo 1

O enunciado pede para mostrar que o produto cartesiano de n conjuntos infinitos enumeráveis é também enumerável.
Dados que temos:
  • Um número natural fixo n\ge 1.
  • Conjuntos A_1,A_2,\dots,A_n, cada um infinito e enumerável. Ou seja, para cada i existe uma bijeção f_i:\mathbb{N}\to A_i.
O que se pede:
  • Provar que o conjunto
A_1\times A_2\times\cdots\times A_n
é enumerável, isto é, existe uma bijeção entre esse produto cartesiano e \mathbb{N} (ou, equivalentemente, que ele pode ser listado em uma sequência enumerável).

Passo 2

Estratégia geral (sem resolver ainda): primeiro reduzir o problema ao caso padrão onde cada conjunto é \mathbb{N}. Como cada A_i é enumerável, existe bijeção f_i:\mathbb{N}\to A_i; assim basta mostrar que \mathbb{N}^n=\mathbb{N}\times\cdots\times\mathbb{N} é enumerável. Depois, compor a enumeração de \mathbb{N}^n com as bijeções f_i dá uma enumeração de A_1\times\cdots\times A_n.
Vou então:
  1. Provar que \mathbb{N}\times\mathbb{N} é enumerável (caso n=2), construindo explicitamente uma enumeração.
  2. Usar indução em n para obter que \mathbb{N}^n é enumerável para todo n.
  3. Voltar para os conjuntos A_i usando as bijeções f_i.

Passo 3

Provar que \mathbb{N}\times\mathbb{N} é enumerável (caso base útil).
Construção por anti-diagonais (ideia intuitiva):
  • Para cada par (k,\ell)\in\mathbb{N}\times\mathbb{N} considere a soma s=k+\ell.
  • Liste todos os pares por camadas crescentes de s: primeiro todos com s=0 (isto é (0,0)), depois todos com s=1 (isto é (0,1),(1,0)), depois s=2 (isto é (0,2),(1,1),(2,0)), e assim por diante.
  • Dentro de cada camada s pode-se fixar uma ordem (por exemplo, listar (0,s),(1,s-1),\dots,(s,0)).
Por que isso enumera tudo e sem repetições?
  • Surjetividade: dado qualquer par (k,\ell), sua soma s=k+\ell é um número natural; esse par aparece exatamente na camada s, portanto aparece em posição finita da lista.
  • Injetividade: um par (k,\ell) tem soma s=k+\ell única; nas regras acima, cada camada s contém exatamente os pares (i,s-i) para i=0,\dots,s, cada um aparece uma vez. Logo não há repetições.
Assim existe uma bijeção explícita h:\mathbb{N}\to\mathbb{N}\times\mathbb{N} dada pela enumeração por camadas. Uma fórmula fechada bem conhecida (função de Cantor) que dá bijeção é
\pi(k,\ell)=\frac{(k+\ell)(k+\ell+1)}{2}+k,
onde \pi:\mathbb{N}\times\mathbb{N}\to\mathbb{N} é bijetora; mas a construção por anti-diagonais é suficiente e mais intuitiva.

Passo 4

Indução para \mathbb{N}^n.
Base já tratada: para n=1 trivialmente \mathbb{N} é enumerável; para n=2 vimos que \mathbb{N}\times\mathbb{N} é enumerável.
Passo indutivo: suponha que \mathbb{N}^{m} é enumerável para algum m\ge 2. Então existe bijeção
g:\mathbb{N}\to\mathbb{N}^{m}.
Considere \mathbb{N}^{m+1}=\mathbb{N}^{m}\times\mathbb{N}. Defina a aplicação
G:\mathbb{N}\times\mathbb{N}\to\mathbb{N}^{m+1}
por
G(i,j)=(g(i),j).
A aplicação G é bijetora se e somente se g é bijetora (fácil de ver: dado qualquer (\mathbf{v},j)\in\mathbb{N}^{m}\times\mathbb{N} existe único i tal que g(i)=\mathbf{v}, logo (i,j) é a única pré-imagem). Como \mathbb{N}\times\mathbb{N} é enumerável (Passo 3), existe bijeção h:\mathbb{N}\to\mathbb{N}\times\mathbb{N}. Compondo G com h obtemos bijeção
G\circ h:\mathbb{N}\xrightarrow{h}\mathbb{N}\times\mathbb{N}\xrightarrow{G}\mathbb{N}^{m+1},
logo \mathbb{N}^{m+1} é enumerável.
Pelo princípio da indução, concluímos que \mathbb{N}^n é enumerável para todo n\in\mathbb{N}, n\ge 1.
Comentário intuitivo alternativo (sem indução formal): também se pode enumerar \mathbb{N}^n por “hiper-superfícies” de soma constante k_1+\cdots+k_n=s, listando todas as tuplas com soma s em ordem crescente de s; a mesma ideia das anti-diagonais em dimensão maior.

Passo 5

Voltar aos conjuntos A_1,\dots,A_n.
Cada A_i é enumerável, portanto existe bijeção f_i:\mathbb{N}\to A_i, para i=1,\dots,n. Defina a aplicação
F:\mathbb{N}^n\to A_1\times\cdots\times A_n
por
F(k_1,k_2,\dots,k_n)=\bigl(f_1(k_1),f_2(k_2),\dots,f_n(k_n)\bigr).
Como cada f_i é bijetora, a aplicação F é bijetora (produto de bijeções é bijeção coordenada a coordenada). Já provimos que \mathbb{N}^n é enumerável; então existe bijeção
\varphi:\mathbb{N}\to\mathbb{N}^n.
Compondo \varphi com F obtemos bijeção
F\circ\varphi:\mathbb{N}\to A_1\times\cdots\times A_n.
Portanto A_1\times\cdots\times A_n é enumerável.

Resposta

O produto cartesiano A_1\times A_2\times\cdots\times A_n é enumerável.

Exercícios relacionados