Questão 38 Seja
A=\left\{\left(a_{1}, a_{2}, \cdots, a_{n}, \cdots,\right)\right\}
onde a_{i} \in\{0,1\} ; \forall i \in \mathbb{N}. Mostre que A é um conjunto não-enumerável.

Passo 1

O enunciado nos dá o conjunto
A=\left\{\left(a_{1}, a_{2}, \ldots, a_{n}, \ldots\right)\mid a_{i}\in\{0,1\}\\ \forall i\in\mathbb{N}\right\}.
A pergunta é: mostrar que A é um conjunto não-enumerável (ou seja, não é possível listar todos os seus elementos numa sequência enumerando-os por 1,2,3,\dots).
Informações relevantes fornecidas:
  • Cada elemento de A é uma sequência infinita de zeros e uns.
  • Para todo índice i\in\mathbb{N}, o termo a_i vale ou 0 ou 1.
  • Deve-se provar que não existe uma enumeração de todos esses elementos (não existe bijeção entre \mathbb{N} e A).

Passo 2

O que significa “enumerável” com precisão — uma mini-aula rápida e necessária.
  • Dizemos que um conjunto X é enumerável (ou numerável) quando existe uma bijeção f:\mathbb{N}\to X. Informalmente, consegue-se listar todos os elementos de X como x_1,x_2,x_3,\dots de modo que cada elemento apareça em alguma posição da lista.
  • Um conjunto é não-enumerável (incontável, uncountable) quando não existe tal bijeção.
    Exemplos rápidos para firmar a ideia: \mathbb{N} e \mathbb{Z} são enumeráveis; o intervalo (0,1) é não-enumerável (resultado clássico de Cantor). Aqui queremos mostrar que A é não-enumerável.

Passo 3

Escolhendo o método: vamos usar o argumento diagonal de Cantor. Por que esse método? Porque é simples, direto e é o método padrão para mostrar que conjuntos de sequências binárias (ou o conjunto das partes de \mathbb{N}) não são enumeráveis. A ideia básica é: suponha que exista uma lista enumerando todos os elementos; então constrói-se explicitamente uma sequência que difere da k-ésima sequência da lista na posição k, garantindo que a nova sequência não está na lista — contradição.

Passo 4

Começando a prova por contradição — montar a hipótese que vamos contradizer.
Suponha, por absurdo, que A seja enumerável. Então existe uma enumeração (lista) que contém todos os elementos de A:
s_{1}, s_{2}, s_{3}, \dots
onde cada s_{k} é uma sequência
s_{k}=\left(a_{k1}, a_{k2}, a_{k3}, \dots\right)
e cada termo a_{ki} pertence a \{0,1\}. Aqui a_{ki} é o i-ésimo componente da k-ésima sequência da lista. A hipótese é que toda sequência em A aparece em alguma posição k dessa lista.

Passo 5

Construção da sequência diagonal — a alma do argumento.
Definimos uma nova sequência b=\left(b_{1}, b_{2}, b_{3}, \dots\right) por:
\text{para cada }i\in\mathbb{N},\quad b_{i}=1-a_{ii}.
Explicando devagar: para cada i olhamos o elemento da lista s_{i} e pegamos o i-ésimo termo dessa sequência, que é a_{ii} (isto é a “diagonal” da tabela das entradas). Se a_{ii}=0 colocamos b_{i}=1; se a_{ii}=1 colocamos b_{i}=0. Assim cada b_{i} ainda vale em \{0,1\}, logo b\in A.

Passo 6

Mostrando que b não pode estar na lista — verificando a diferença coordenada a coordenada.
Tomemos um índice arbitrário k\in\mathbb{N}. Compare b com a sequência s_{k}=(a_{k1},a_{k2},\dots). Olhando a coordenada k-ésima:
b_{k}=1-a_{kk}.
Em particular b_{k}\neq a_{kk}. Mas a_{kk} é justamente a k-ésima coordenada de s_{k}. Logo b difere de s_{k} na coordenada k. Como isso vale para todo k, b difere de cada sequência da lista em pelo menos uma posição. Portanto b não coincide com nem s_{1}, nem s_{2}, nem s_{3}, e assim por diante — isto é, b não está em nenhuma posição da lista.

Passo 7

Contradição e conclusão.
Chegamos a uma contradição: a hipótese inicial afirmava que a lista s_{1},s_{2},\dots continha todas as sequências de A, mas construímos uma sequência b\in A que não aparece em nenhuma posição dessa lista. Logo a hipótese de que A é enumerável é falsa. Portanto A é não-enumerável.

Passo 8

Observação adicional (intuitiva e útil para provas relacionadas).
Há uma bijeção natural entre A e o conjunto das partes de \mathbb{N}, \mathcal{P}(\mathbb{N}): associar a cada sequência \left(a_{1},a_{2},\dots\right) o subconjunto \{i\in\mathbb{N}\mid a_{i}=1\}. Como já se sabe pelo teorema de Cantor que \mathcal{P}(\mathbb{N}) é não-enumerável, isso dá outra forma imediata de ver que A é não-enumerável. Aqui o argumento diagonal que fizemos é, essencialmente, o mesmo argumento que prova que \mathcal{P}(\mathbb{N}) não é enumerável.

Resposta

O conjunto A é não-enumerável.

Exercícios relacionados