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 é, $\mathrm{\exists }{f}_{bij}:T\mapsto S$ onde $T=\mathbb{N}\text{ ou }T=I_n=\{1,2,...,n\},\text{ 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\to 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}\to \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}\to 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}\to 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}\to \mathbb{N}$ uma bijeção, onde $f(n)=\{\begin{array}{c}2n,sen\ge 0\\ -1-2n,sen<0\end{array}$. 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\to 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\to Y$ de forma que f seja injetiva.

• Assim, se Y é finito, logo X é finito, então dado $g:X\to 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)=f(x_2)\Rightarrow f(X)$

${\displaystyle }$

=

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

$\Rightarrow \iff \to \mathrm{\exists }\mathrm{\forall }\{\begin{array}{c}\\ \end{array}\frac{a}{b}\left\{\right\}\sqrt[3]{a}\bar{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 ℝ$, mas não existe uma função bijetiva $f:\mathbb{N}\to ℝ$

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:ℝ\to ℝ$, 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 $ℝ$, o conjunto das funções $f:ℝ\to ℝ$, etc).

Existem várias provas de que $ℝ$ 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|Completude]]; a demonstração está no capítulo [[../Sequências|Sequências]].

Ver também

• Conjunto Contável