(10%) Questão 9. Um conjunto
é dito ser enumerável quando existe uma bijeção
; nesse caso, seus elementos podem ser listados como
.
O produto Cartesiano infinito
nada mais é do que o conjunto das sequências de 0 's e 1 's; ele é enumerável?
O produto Cartesiano infinito
Passo 1
O enunciado pede para responder se o conjunto
é enumerável. Ele já fornece a definição que vou usar: um conjunto
é enumerável quando existe uma bijeção
— isto é, quando é possível listar todos os elementos de
como
.
As informações relevantes são:
-
é o conjunto de todas as sequências infinitas de zeros e uns, isto é, todos os tuplos com para todo . - A pergunta é: existe uma bijeção
? Em palavras: é possível listar todas as sequências binárias infinitas, uma por uma?
Passo 2
Vamos entender a ideia com um exemplo finito para ganhar intuição. Para um número finito de coordenadas:
-
tem elementos — claramente enumerável. -
tem elementos — também enumerável.
Para qualquerfinito, tem elementos, logo é finito e portanto enumerável. Mas quando passamos para produto com infinitas coordenadas, a situação pode mudar: o conjunto pode deixar de ser enumerável. Vou provar rigorosamente que, no caso infinito, não é enumerável.
Passo 3
Estratégia do método: farei uma prova por contradição usando o argumento diagonal de Cantor — um método clássico, curto e direto. Explico por que: se assumirmos que existe uma enumeração (uma bijeção)
, construo explicitamente uma sequência binária que não aparece na lista
. Isso contradiz a suposição de que a lista contém todas as sequências.
Começo supondo que existe uma enumeração
. Para cada
escrevo
onde cada
é a
-ésima coordenada da sequência
. Assim imaginamos uma “tabela” infinita onde a linha
é a sequência
e a coluna
são as
-ésimas coordenadas de todas as sequências.
Passo 4
Agora construo uma nova sequência
em
da seguinte forma: para todo
,
Explicação do porquê isso faz sentido: dado
, a expressão
também é um elemento de
(se
então
; se
então
). Logo
é de fato uma sequência binária infinita, isto é,
.
Passo 5
Mostro que
não pode ser igual a nenhuma sequência da lista
. Tome um índice arbitrário
. Compare
com a sequência
. Pela construção, na coordenada
temos
Portanto
. Isso significa que
difere de
pelo menos na coordenada
. Como
era arbitrário,
difere de
em pelo menos uma coordenada para todo
. Conclusão:
para todo
.
Passo 6
Voltando à suposição inicial: se
fosse uma bijeção
, então toda sequência em
, inclusive
, teria que aparecer na lista
. Mas pelo passo anterior vimos que
não aparece em nenhuma posição da lista. Isso é uma contradição. Logo a hipótese de que existe uma bijeção
é falsa.
Passo 7
Portanto o conjunto
não é enumerável. Em linguagem direta: não existe uma lista que contenha todas as sequências binárias infinitas. Essa é a famosa conclusão do argumento diagonal de Cantor.
Observação pedagógica curta: outra justificativa possível (menos direta) é mapear cada sequência binária a um número em
via expansão binária e usar que
é não enumerável; porém isso exige cuidado com expansões binárias não únicas (números dyádicos). O argumento diagonal que usei evita esses detalhes e é autônomo e elementar.
Resposta
Não,
não é enumerável.