Enumerabilidade

Aula de Teoria da Computabilidade de 19.08.2004, Prof Prolo

1 Cantor, conjuntos não enumeráveis, funções não-computáveis e problemas não decidíveis
George Cantor mostrou (1874) que existem cardinais acima de ℵ0 , usando um método que hoje é conhecido como Método da diagonal de Cantor. Nas próximas seções mostramos alguns conjuntos não enumeráveis importantes, utilizando este método. O trabalho de Cantor vai muito além disto, mas aqui nos restringimos ao que nos interessa para a disciplina. Ao final concluimos, a partir de resultados de cardinalidae vistos, que existem funções não computáveis e problemas não decidíveis.

2 O conjunto dos números reais (R) é não-enumerável
Vamos nos restringir aqui apenas ao intervalo (0, 1] por simplicidade. (É óbvio que R não pode ser menor do que (0, 1].
1. A prova é por contradição (ou redução ao absurdo). Primeiro assumimos como Hipótese que o conjunto é enumerável. Ora, nós queremos provar exatamente o contrário, isto é, ao final concluímos que se tal hipótese for verdadeira chega-se a uma contradição, e portanto a hipótese não é verdadeira: o conjunto dos reais não é enumerável.
2. Ora, se o conjunto é enumerável por hipótese, então deve existir uma enumeração para ele (mesmo que nós não saibamos qual/como ela é): r0 , r1 , r2 , r3 , r4 , r5 , r6

3. Nota: Todo número real pode ser representado em decimal com mantissa infinita. Alguns porque
√
naturalmente a tem como 0.033333 · · · , π, abc. Mas mesmo os que tem mantissa finita, como 0.25, podem ser representados como 0.2499999 · · · . Isto não é central ao argumento, apenas mostra que representações com mantissa infinita (sem zeros não significativos à esquerda) tem correspondência bijetora com os reais.
4. O diagrama abaixo mostra esquematicamente uma enumeração qualquer do intervalo (0, 1], que deve existir de acordo com 2 acima. Cada linha representa um número. Cada número é uma sequência infinita de dígitos a partir do ponto decimal (Como estamos