Questão 31 Sejam A um conjunto infinito enumerável e
B_{n}=\left\{\left(a_{1}, a_{2}, \cdots, a_{n}\right) ; a_{k} \in A \text { com } k=1,2, \cdots, n\right\}
onde a_{1}, a_{2}, \cdots, a_{n} não são necessariamente distintos dois a dois. Mostre que B_{n} é enumerável.

Passo 1

O enunciado dá:
  • A é um conjunto infinito enumerável (ou seja, existe uma enumeração de A por números naturais).
  • Para um inteiro fixo n\ge 1,
B_{n}=\left\{\left(a_{1}, a_{2}, \ldots, a_{n}\right) ;\\ a_{k}\in A\text{ para }k=1,\ldots,n\right\}.
O que se pede: mostrar que B_{n} é enumerável (ou seja, que existe uma enumeração por números naturais, ou equivalentemente que há bijeção entre B_{n} e \mathbb{N}).

Passo 2

Vamos usar a ideia básica: como A é enumerável, existe uma bijeção
f:\mathbb{N}\to A.
Explicar o que isso significa: cada elemento de A aparece exatamente uma vez na sequência f(1),f(2),f(3),\ldots. Agora observe que qualquer tupla \left(a_{1},\ldots,a_{n}\right)\in B_{n} corresponde, via f^{-1} coordenada a coordenada, a uma tupla de naturais
\left(f^{-1}(a_{1}),\ldots,f^{-1}(a_{n})\right)\in\mathbb{N}^{n}.
Portanto existe uma bijeção natural entre B_{n} e \mathbb{N}^{n}. Conclusão parcial: basta provar que \mathbb{N}^{n} é enumerável.

Passo 3

Mostrar primeiro que \mathbb{N}\times\mathbb{N} é enumerável. Vou dar uma enumeração explícita (diagonal) e uma fórmula fechada para indexar pares. Enumeração por diagonais: listar todos os pares com soma 2, depois soma 3, depois soma 4, etc. Mais formalmente, para (i,j)\in\mathbb{N}\times\mathbb{N} (aqui \mathbb{N}=\{1,2,3,\ldots\}) defina o inteiro
m=i+j.
O número de pares (i',j') com soma estritamente menor que m é
\sum_{t=2}^{m-1}(t-1)=\frac{(m-1)(m-2)}{2}.
Dentro dos pares com soma igual a m ordenamos por i=1,2,\ldots,m-1. Assim podemos definir a função
\varphi:\mathbb{N}\times\mathbb{N}\to\mathbb{N},\qquad \varphi(i,j)=\frac{(i+j-1)(i+j-2)}{2}+i.
Explicação do que faz \varphi: conta quantos pares vieram antes (a soma menor que i+j) e soma a posição do par na diagonal correspondente. A fórmula acima é bijetora (cada par tem um índice natural distinto e todo natural aparece para algum par), portanto \mathbb{N}\times\mathbb{N} é enumerável.

Passo 4

Agora estendo para dimensões maiores por indução. Se já sabemos que \mathbb{N}^{k} é enumerável para algum k\ge 1, então \mathbb{N}^{k+1}=\mathbb{N}^{k}\times\mathbb{N} é produto de dois conjuntos enumeráveis. Como provado no passo anterior, o produto de dois conjuntos enumeráveis é enumerável (basta aplicar a enumeração de \mathbb{N}^{k} e a de \mathbb{N} e usar o mesmo truque de pareamento/diagonal para enumerar pares de índices). Assim, por indução em k, \mathbb{N}^{n} é enumerável para todo n finito.
Esclarecimento didático: a ideia é reduzir \mathbb{N}^{n} a \mathbb{N}^{2} recursivamente. Se existe bijeção g:\mathbb{N}\to\mathbb{N}^{k}, então a bijeção entre \mathbb{N} e \mathbb{N}^{k}\times\mathbb{N}=\mathbb{N}^{k+1} é obtida compondo g com a bijeção \varphi do passo anterior aplicada aos índices. Assim constrói-se uma enumeração explícita de \mathbb{N}^{n}.

Passo 5

Voltar para B_{n}. Lembrando que havia uma bijeção f:\mathbb{N}\to A. Então a aplicação
F:\mathbb{N}^{n}\to B_{n},\qquad F(k_{1},\ldots,k_{n})=\bigl(f(k_{1}),\ldots,f(k_{n})\bigr)
é bijetora (é inversível via F^{-1}(a_{1},\ldots,a_{n})=(f^{-1}(a_{1}),\ldots,f^{-1}(a_{n}))). Como \mathbb{N}^{n} é enumerável (Passo 4), e B_{n} é bijetivo a \mathbb{N}^{n}, segue que B_{n} é enumerável.
Comentário amigável: em palavras simples, como A pode ser listada como a^{(1)},a^{(2)},\dots, para listar todas as tuplas de comprimento n basta listar todas as combinações de índices (i_{1},\dots,i_{n}) de forma ordenada (por exemplo pelas somas i_1+\cdots+i_n e depois por ordem lexicográfica), e então substituir cada índice pelo elemento correspondente de A. Isso dá uma lista que contém todas as tuplas de A e nada mais.

Resposta

B_{n} é enumerável.

Exercícios relacionados