Exemplo 3. (Um conjunto não-enumerável.) Seja
o conjunto de todas as seqüências infinitas, como
, formadas com os símbolos 0 e 1. Noutras palavras,
é o conjunto de todas as funções
. Para cada
, o valor
, igual a 0 ou 1 , é o
-ésimo termo da seqüência
. Afirmamos que nenhum subconjunto enumerável
é igual a
. Com efeito, dado
, indiquemos com
o
-ésimo termo da seqüência
. Formamos uma nova seqüência
tomando o
-ésimo termo de
igual a 0 se for
, ou igual a 1 se for
. A seqüência
não pertence ao conjunto
porque seu
-ésimo termo é diferente do
-ésimo termo de
. (Este raciocínio, devido a G. Cantor, é conhecido como “método da diagonal”.)
No capítulo seguinte mostraremos que o conjunto
dos números reais não é enumerável.
Passo 1
O enunciado define o conjunto
de todas as sequências infinitas binárias, e pede para mostrar que não existe uma enumeração
que cubra todo . O conteúdo é o argumento diagonal de Cantor, que prova que
não é enumerável.
que cubra todo
Passo 2
Suponha, por absurdo, que exista uma enumeração
tal que . Denote por
o valor do termo de índice
na sequência
, ou seja,
tal que
Passo 3
Construa uma nova sequência
Essa regra garante que
.
Passo 4
Mostre que
não pode estar em
. De fato, se tentássemos ter
para algum
, olharíamos o termo de índice
de cada uma:
logo
difere de
em pelo menos um lugar, o que impede
.
Passo 5
Como
mas
, concluímos que
. Isso vale para qualquer enumeração
, logo não há enumeração que cubra todo
.
Resposta
O conjunto
não é enumerável.