(10%) Questão 9. Um conjunto A é dito ser enumerável quando existe uma bijeção f: \mathbb{N} \rightarrow A; nesse caso, seus elementos podem ser listados como f(1), f(2), f(3), \ldots.
O produto Cartesiano infinito
\{0,1\}^{\mathbb{N}}=\{0,1\} \times\{0,1\} \times\{0,1\} \times \cdots
nada mais é do que o conjunto das sequências de 0 's e 1 's; ele é enumerável?

Passo 1

O enunciado pede para responder se o conjunto \{0,1\}^{\mathbb{N}} é enumerável. Ele já fornece a definição que vou usar: um conjunto A é enumerável quando existe uma bijeção f:\mathbb{N}\to A — isto é, quando é possível listar todos os elementos de A como f(1),f(2),f(3),\dots.
As informações relevantes são:
  • \{0,1\}^{\mathbb{N}} é o conjunto de todas as sequências infinitas de zeros e uns, isto é, todos os tuplos (x_1,x_2,x_3,\dots) com x_i\in\{0,1\} para todo i.
  • A pergunta é: existe uma bijeção f:\mathbb{N}\to\{0,1\}^{\mathbb{N}}? 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:
  • \{0,1\}^1=\{(0),(1)\} tem 2 elementos — claramente enumerável.
  • \{0,1\}^2=\{(0,0),(0,1),(1,0),(1,1)\} tem 2^2=4 elementos — também enumerável.
    Para qualquer k finito, \{0,1\}^k tem 2^k 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, \{0,1\}^{\mathbb{N}} 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) f, construo explicitamente uma sequência binária que não aparece na lista f(1),f(2),\dots. Isso contradiz a suposição de que a lista contém todas as sequências.
Começo supondo que existe uma enumeração f:\mathbb{N}\to\{0,1\}^{\mathbb{N}}. Para cada n\in\mathbb{N} escrevo
f(n) = \big(a_{n,1},\,a_{n,2},\,a_{n,3},\,\dots\big),
onde cada a_{n,k}\in\{0,1\} é a k-ésima coordenada da sequência f(n). Assim imaginamos uma “tabela” infinita onde a linha n é a sequência f(n) e a coluna k são as k-ésimas coordenadas de todas as sequências.

Passo 4

Agora construo uma nova sequência b=(b_1,b_2,b_3,\dots) em \{0,1\}^{\mathbb{N}} da seguinte forma: para todo k\in\mathbb{N},
b_k = 1 - a_{k,k}.
Explicação do porquê isso faz sentido: dado a_{k,k}\in\{0,1\}, a expressão 1-a_{k,k} também é um elemento de \{0,1\} (se a_{k,k}=0 então b_k=1; se a_{k,k}=1 então b_k=0). Logo b é de fato uma sequência binária infinita, isto é, b\in\{0,1\}^{\mathbb{N}}.

Passo 5

Mostro que b não pode ser igual a nenhuma sequência da lista f(1),f(2),\dots. Tome um índice arbitrário n\in\mathbb{N}. Compare b com a sequência f(n)=(a_{n,1},a_{n,2},\dots). Pela construção, na coordenada n temos
b_n = 1 - a_{n,n}.
Portanto b_n \neq a_{n,n}. Isso significa que b difere de f(n) pelo menos na coordenada n. Como n era arbitrário, b difere de f(n) em pelo menos uma coordenada para todo n. Conclusão: b\neq f(n) para todo n.

Passo 6

Voltando à suposição inicial: se f fosse uma bijeção \mathbb{N}\to\{0,1\}^{\mathbb{N}}, então toda sequência em \{0,1\}^{\mathbb{N}}, inclusive b, teria que aparecer na lista f(1),f(2),\dots. Mas pelo passo anterior vimos que b não aparece em nenhuma posição da lista. Isso é uma contradição. Logo a hipótese de que existe uma bijeção f é falsa.

Passo 7

Portanto o conjunto \{0,1\}^{\mathbb{N}} 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 [0,1] via expansão binária e usar que [0,1] é 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, \{0,1\}^{\mathbb{N}} não é enumerável.

Exercícios relacionados