Exemplo 3. (Um conjunto não-enumerável.) Seja S o conjunto de todas as seqüências infinitas, como s=(01100010 \ldots), formadas com os símbolos 0 e 1. Noutras palavras, S é o conjunto de todas as funções s: \mathbb{N} \rightarrow\{0,1\}. Para cada n \in \mathbb{N}, o valor s(n), igual a 0 ou 1 , é o n-ésimo termo da seqüência s. Afirmamos que nenhum subconjunto enumerável X=\left\{s_{1}, s_{2}, \ldots, s_{n}, \ldots\right\} \subset S é igual a S. Com efeito, dado X, indiquemos com s_{n m} o n-ésimo termo da seqüência s_{m} \in X. Formamos uma nova seqüência s^{*} \in S tomando o n-ésimo termo de s^{*} igual a 0 se for s_{n n}=1, ou igual a 1 se for s_{n n}=0. A seqüência s^{*} não pertence ao conjunto X porque seu n-ésimo termo é diferente do n-ésimo termo de s_{n}. (Este raciocínio, devido a G. Cantor, é conhecido como “método da diagonal”.)
No capítulo seguinte mostraremos que o conjunto \mathbb{R} dos números reais não é enumerável.

Passo 1

O enunciado define o conjunto
S = \{\,s: \mathbb{N}\to\{0,1\}\}
de todas as sequências infinitas binárias, e pede para mostrar que não existe uma enumeração
\,X=\{s_{1},s_{2},\dots,s_{n},\dots\}\subset S
que cubra todo S. O conteúdo é o argumento diagonal de Cantor, que prova que S não é enumerável.

Passo 2

Suponha, por absurdo, que exista uma enumeração
\,X=\{s_{1},s_{2},\dots\}
tal que X = S. Denote por s_{nm} o valor do termo de índice n na sequência s_{m}, ou seja,
s_{m}(n)=s_{nm}\in\{0,1\}.

Passo 3

Construa uma nova sequência s^{*}\in S\) definindo seu \(n\)-ésimo termo por \[s^{*}(n)= \begin{cases} 0, &\text{se }s_{nn}=1,\\\\ 1, &\text{se }s_{nn}=0. \end{cases}
Essa regra garante que s^{*}(n)\neq s_{nn}\] para todo \(n.

Passo 4

Mostre que s^{*} não pode estar em X. De fato, se tentássemos ter s^{*}=s_{m} para algum m, olharíamos o termo de índice m de cada uma:
s^{*}(m)\neq s_{mm}=s_{m}(m),
logo s^{*} difere de s_{m} em pelo menos um lugar, o que impede s^{*}=s_{m}.

Passo 5

Como s^{*}\in S mas s^{*}\notin X, concluímos que X\neq S. Isso vale para qualquer enumeração X, logo não há enumeração que cubra todo S.

Resposta

O conjunto S não é enumerável.

Exercícios relacionados