Análise real/Enumerabilidade

Origem: Wikilivros, livros abertos por um mundo aberto.

Conjuntos enumeráveis[editar | editar código-fonte]

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 | editar código-fonte]

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

O conjunto dos naturais é enumerável[editar | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]

Seja uma bijeção, onde . Logo f é bijetiva(é fácil mostrar a bijetividade). Portanto é enumerável.

O conjunto dos racionais é enumerável[editar | editar código-fonte]

É 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 | editar código-fonte]

Teo enu.3: Todo subconjunto de um conjunto enumerável é enumerável[editar | editar código-fonte]

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,

=[editar | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]