Questão
é um conjunto enumerável, mostre que, para cada
é enumerável.
Passo 1
O enunciado dá que o produto finito
é um conjunto enumerável. O que se pede: mostrar que, para cada índice
fixo, o conjunto
também é enumerável.
Informações relevantes extraídas do enunciado:
- Há um número finito
. - Sabe-se que
é enumerável (ou seja, é finito ou numerável por bijeção com os naturais). - Precisa-se provar a afirmativa para cada
.
Observação importante (vou deixar clara já aqui): se
então pelo menos um dos
é vazio; o conjunto vazio é finito e portanto enumerável, mas isso não força outros fatores a serem enumeráveis. Por isso, a conclusão interessante e habitual que se prova é feita assumindo que o produto é enumerável e não vazio (ou, equivalente, que todos os
sejam não vazios). Abaixo tratei ambos os pontos: a observação sobre o caso vazio e, em seguida, a prova no caso não vazio.
Passo 2
Definições e lemmas que vamos usar (explicados devagarinho).
- Definição de enumerável: um conjunto
é enumerável quando é finito ou quando existe uma bijeção de com o conjunto dos naturais . Intuitivamente: dá para listar os elementos de numa sequência (talvez terminando, se for finito). - Projeção canônica: para cada
define-se a aplicação por . Essa aplicação pega um n-tuplo e retorna a sua componente . - Fato simples sobre imagens por aplicações: se
é sobrejetora (surjetiva) e é enumerável, então também é enumerável. Vou provar esse fato mais adiante, porque é a peça chave.
Passo 3
Caso especial: o produto pode ser vazio.
- Se
, então existe pelo menos um tal que . O conjunto vazio é finito, logo enumerável, então para esse índice a conclusão “ é enumerável” é verdadeira. - Porém, esse caso não permite deduzir que todos os outros
são enumeráveis (ex.: e dá enumerável, mas não é enumerável). Portanto, a implicação “produto enumerável cada fator enumerável” só pode ser provada de forma geral quando o produto é enumerável e não vazio (ou então se supõe já que todos os fatores são não vazios). A partir daqui, suponho que é enumerável e não vazio.
Passo 4
Mostrando que as projeções
são sobrejetoras (explicação passo a passo).
- Como
não é vazio, existe pelo menos um elemento . Isso significa que cada . - Tome um índice fixo
e um elemento arbitrário . Considere o n-tuplo
. - Cada coordenada de
pertence ao conjunto correspondente (as coordenadas são que sabemos pertencerem a ; a coordenada é ), logo . - Aplicando a projeção,
. Como foi um elemento arbitrário de , segue que é sobrejetora: cada tem uma pré-imagem no produto.
Passo 5
Prova do lema: imagem sobrejetora de conjunto enumerável é enumerável.
- Caso 1:
é finito. Então é também finito, logo enumerável. - Caso 2:
é numerável infinito. Então existe enumeração . Considere a sequência em . - Essa sequência pode ter repetições, mas podemos eliminar repetições mantendo a ordem da primeira ocorrência: percorre-se a sequência e escreve-se cada novo valor de
somente na primeira vez que aparece. O resultado é uma sequência (finita ou infinita) que lista exatamente todos os elementos de . - Assim
é enumerável (se a sequência ficar finita, é finito; caso contrário é numerável infinito).
- Essa sequência pode ter repetições, mas podemos eliminar repetições mantendo a ordem da primeira ocorrência: percorre-se a sequência e escreve-se cada novo valor de
- Conclusão do lema: se
é sobrejetora e é enumerável então é enumerável.
Passo 6
Aplicando o lema às projeções.
- Para cada
, construímos e mostramos que é sobrejetora. - Como
é enumerável por hipótese, o lema garante que a imagem é enumerável. - Isso vale para todo
. Portanto cada fator é enumerável.
Passo 7
Recapitulando em linguagem de prova curta (mas já explicada): assumindo
enumerável e não vazio, a projeção canônica em cada coordenada é sobrejetora; imagem sobrejetora de conjunto enumerável é enumerável; logo cada
é enumerável. Se o produto for o vazio, então ao menos um fator é vazio (e portanto enumerável), mas não se pode concluir nada sobre os outros fatores.
Resposta
Para cada
,
é enumerável.