Análise real/Enumerabilidade

Conjuntos enumeráveis

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 $I_{n}$, isto é, $\exists \;f_{bij}:T\mapsto S$ onde $T=\mathbb {N} {\mbox{ ou }}T=I_{n}=\{1,2,...,n\},{\mbox{ de forma que }}T\subset \mathbb {N}$.

Dizemos que um conjunto A é enumerável se ele é vazio ou se existe uma função injetiva $f:A\mapsto \mathbb {N}$. Caso contrário dizemos que A é não-enumerável.

Teo enu.1: Todo conjunto finito é enumerável

Seja $X=\{x_{1},x_{2},...,x_{n}\}$ um conjunto finito. Seja $f:I_{n}\rightarrow X$ uma bijeção, onde $f(i)=x_{i},i=1,...,n\;$. Logo f é bijetiva. Portanto X é enumerável.

O conjunto dos naturais é enumerável

Seja $\mathbb {N} =\{1,2,...\}$ o conjunto dos números naturais. Seja $f:\mathbb {N} \rightarrow \mathbb {N}$ uma bijeção, onde $f(i)=i,i=1,2,...\;$. Logo f é bijetiva(é fácil mostrar a bijetividade). Portanto $\mathbb {N}$ é enumerável.

O conjunto dos pares naturais é enumerável

Seja $2\mathbb {N} =\{2,4,...\}$ o conjunto dos números pares naturais. Seja $f:\mathbb {N} \rightarrow 2\mathbb {N}$ uma bijeção, onde $f(i)=2i,i=1,2,...\;$. Logo f é bijetiva(é fácil mostrar a bijetividade). Portanto $2\mathbb {N}$ é enumerável.

O conjunto dos impares naturais é enumerável

Seja $2\mathbb {N} -1=\{1,3,...\}$ o conjunto dos números impares naturais. Seja $f:\mathbb {N} \rightarrow 2\mathbb {N} -1$ uma bijeção, onde $f(i)=2i-1,i=1,2,...\;$. Logo f é bijetiva(é fácil mostrar a bijetividade). Portanto $2\mathbb {N} -1$ é enumerável.

O conjunto dos inteiros é enumerável

Seja $f:\mathbb {Z} \rightarrow \mathbb {N}$ uma bijeção, onde $f(n)={\begin{cases}2n,se\;n\geq 0\;\\-1-2n,se\;n<0\;\end{cases}}\;$. Logo f é bijetiva(é fácil mostrar a bijetividade). Portanto $\mathbb {Z}$ é enumerável.

O conjunto dos racionais é enumerável

É 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.3: Todo subconjunto de um conjunto enumerável é enumerável

Ou se dado Y enumerável e $f:X\rightarrow Y\;$ 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 $f:X\rightarrow Y$ de forma que f seja injetiva.

• Assim, se Y é finito, logo X é finito, então dado $g:X\rightarrow I_{n}$(onde n é a cardinalidade de X). Implica que X é enumerável. se Y é finito, dado $x_{1},x_{2}\in X$ pela injetividade, $f(x_{1})\not =f(x_{2})\Rightarrow f(X)$

${\displaystyle }$

=

Além disso, é possível provar que $\mathbb {R} \,$ e $\mathbb {R} ^{2}\,$ tem a mesma cardinalidade; uma conjectura interessante neste ponto seria mostrar que todo conjunto infinito é enumerável. Esta conjectura, porém, é falsa. $\;$

$\Rightarrow \;\Leftrightarrow \;\rightarrow \;\exists \;\forall \;{\begin{cases}\;\\\;\end{cases}}\;{a \over b}\;{\bigg \{}{\bigg \}}\;{\sqrt[{3}]{a}}\;{\overline {X}}$

Conjuntos não-enumeráveis

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 $f:\mathbb {N} \to \mathbb {R} \,$, mas não existe uma função bijetiva $f:\mathbb {N} \to \mathbb {R} \,$

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 $f:\mathbb {R} \to \mathbb {R} \,$, o conjunto das sequências de números reais, o conjunto das partes de $\mathbb {N} \,$, etc), ou conjuntos de maior cardinalidade (o conjunto das partes de $\mathbb {R} \,$, o conjunto das funções $f:\mathbb {R} \to \mathbb {R} \,$, etc).

Existem várias provas de que $\mathbb {R} \,$ não é enumerável; as provas consistem em supor uma sequência de números reais $a_{0},a_{1},a_{2},...\,$ 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

• Conjunto Contável