Análise real/Enumerabilidade
Conjuntos enumeráveis
editar- Intuitivamente, um conjunto A é enumerável quando é possível construir uma lista com todos os elementos de A.
- Mais formalmente falando, A é enumerável se existir uma bijeção (relação um para um) entre A e o conjunto dos números naturais N (chamam-se de conjuntos de mesma cardinalidade quando existe uma bijeção entre os conjuntos; também diz-se que estes conjuntos são equipotentes).
- Um Conjunto A é enumerável se uma função f bijetiva aos naturais ou ao conjunto , isto é, onde .
- Dizemos que um conjunto A é enumerável se ele é vazio ou se existe uma função injetiva . Caso contrário dizemos que A é não-enumerável.
Teo enu.1: Todo conjunto finito é enumerável
editarSeja um conjunto finito. Seja uma bijeção, onde . Logo f é bijetiva. Portanto X é enumerável.
O conjunto dos naturais é enumerável
editarSeja o conjunto dos números naturais. Seja uma bijeção, onde . Logo f é bijetiva(é fácil mostrar a bijetividade). Portanto é enumerável.
O conjunto dos pares naturais é enumerável
editarSeja o conjunto dos números pares naturais. Seja uma bijeção, onde . Logo f é bijetiva(é fácil mostrar a bijetividade). Portanto é enumerável.
O conjunto dos impares naturais é enumerável
editarSeja o conjunto dos números impares naturais. Seja uma bijeção, onde . Logo f é bijetiva(é fácil mostrar a bijetividade). Portanto é enumerável.
O conjunto dos inteiros é enumerável
editarSeja uma bijeção, onde . Logo f é bijetiva(é fácil mostrar a bijetividade). Portanto é enumerável.
O conjunto dos racionais é enumerável
editarÉ possível provar que os seguintes conjuntos são enumeráveis:
- o conjunto dos números racionais
- o conjunto dos números algébricos
Teo enu.2: Todo conjunto infinito possui um subconjunto enumerável
editarTeo enu.3: Todo subconjunto de um conjunto enumerável é enumerável
editarOu se dado Y enumerável e injetiva, então X é enumerável
- Prova: Dado Y enumerável.
- Se Y é finito, qualquer subconjunto X de Y é finito também, logo X é enumerável.
- Mas se Y é infinito, logo Y possui um subconjunto X enumerável.
- Prova2: Dado X um subconjunto de Y enumerável. Tome de forma que f seja injetiva.
- Assim, se Y é finito, logo X é finito, então dado (onde n é a cardinalidade de X). Implica que X é enumerável. se Y é finito, dado pela injetividade,
=
editarAlém disso, é possível provar que e tem a mesma cardinalidade; uma conjectura interessante neste ponto seria mostrar que todo conjunto infinito é enumerável. Esta conjectura, porém, é falsa.
Conjuntos não-enumeráveis
editarCantor mostrou que o conjunto dos números reais tem mais elementos que o conjunto dos números naturais, no sentido preciso seguinte: existe uma função injetiva , mas não existe uma função bijetiva
Assim, o conjunto dos números reais não é enumerável, assim como qualquer conjunto equipotente a ele (o conjunto dos números complexos, o conjunto das funções contínuas , o conjunto das sequências de números reais, o conjunto das partes de , etc), ou conjuntos de maior cardinalidade (o conjunto das partes de , o conjunto das funções , etc).
Existem várias provas de que não é enumerável; as provas consistem em supor uma sequência de números reais e exibir um número real x que não está nesta sequência.
Uma das provas utiliza o princípio dos intervalos encaixados, que será visto no capítulo Completude; a demonstração está no capítulo Sequências.