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:
Provar que \mathbb{N}\times\mathbb{N} é enumerável (caso n=2), construindo explicitamente uma enumeração.
Usar indução em n para obter que \mathbb{N}^n é enumerável para todo n.
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
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
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