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

editar

Seja um conjunto finito. Seja uma bijeção, onde . Logo f é bijetiva. Portanto X é enumerável.

O conjunto dos naturais é enumerável

editar

Seja 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

editar

Seja 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

editar

Seja 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

editar

Seja 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

editar

Teo enu.3: Todo subconjunto de um conjunto enumerável é enumerável

editar

Ou 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,

Alé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

editar

Cantor 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.

Ver também

editar