Questão 38 Seja
onde
. Mostre que
é um conjunto não-enumerável.
Passo 1
O enunciado nos dá o conjunto
A pergunta é: mostrar que
é um conjunto não-enumerável (ou seja, não é possível listar todos os seus elementos numa sequência enumerando-os por
).
Informações relevantes fornecidas:
Informações relevantes fornecidas:
- Cada elemento de
é uma sequência infinita de zeros e uns. - Para todo índice
, o termo vale ou ou . - Deve-se provar que não existe uma enumeração de todos esses elementos (não existe bijeção entre
e ).
Passo 2
O que significa “enumerável” com precisão — uma mini-aula rápida e necessária.
- Dizemos que um conjunto
é enumerável (ou numerável) quando existe uma bijeção . Informalmente, consegue-se listar todos os elementos de como 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:e são enumeráveis; o intervalo é não-enumerável (resultado clássico de Cantor). Aqui queremos mostrar que é 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
) 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
-ésima sequência da lista na posição
, 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 seja enumerável. Então existe uma enumeração (lista) que contém todos os elementos de
:
Suponha, por absurdo, que
onde cada
é uma sequência
e cada termo
pertence a
. Aqui
é o
-ésimo componente da
-ésima sequência da lista. A hipótese é que toda sequência em
aparece em alguma posição
dessa lista.
Passo 5
Construção da sequência diagonal — a alma do argumento.
Definimos uma nova sequência por:
Definimos uma nova sequência
Explicando devagar: para cada
olhamos o elemento da lista
e pegamos o
-ésimo termo dessa sequência, que é
(isto é a “diagonal” da tabela das entradas). Se
colocamos
; se
colocamos
. Assim cada
ainda vale em
, logo
.
Passo 6
Mostrando que
não pode estar na lista — verificando a diferença coordenada a coordenada.
Tomemos um índice arbitrário . Compare
com a sequência
. Olhando a coordenada
-ésima:
Tomemos um índice arbitrário
Em particular
. Mas
é justamente a
-ésima coordenada de
. Logo
difere de
na coordenada
. Como isso vale para todo
,
difere de cada sequência da lista em pelo menos uma posição. Portanto
não coincide com nem
, nem
, nem
, e assim por diante — isto é,
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 continha todas as sequências de
, mas construímos uma sequência
que não aparece em nenhuma posição dessa lista. Logo a hipótese de que
é enumerável é falsa. Portanto
é não-enumerável.
Chegamos a uma contradição: a hipótese inicial afirmava que a lista
Passo 8
Observação adicional (intuitiva e útil para provas relacionadas).
Há uma bijeção natural entre e o conjunto das partes de
,
: associar a cada sequência
o subconjunto
. Como já se sabe pelo teorema de Cantor que
é não-enumerável, isso dá outra forma imediata de ver que
é não-enumerável. Aqui o argumento diagonal que fizemos é, essencialmente, o mesmo argumento que prova que
não é enumerável.
Há uma bijeção natural entre
Resposta
O conjunto
é não-enumerável.