===== Enumerabilidade =====

<WRAP info>
Denotamos por $\omega$ o conjunto dos números naturais.
</WRAP>

<WRAP info>
Dizemos que um conjunto $X$ é {{entry>enumerável}} se existe $f: \omega \rightarrow X$ sobrejetora.
</WRAP>

**~~#~~** Mostre que $\omega \times \omega$ é enumerável.<wrap tip>[[Dica:produtoEnum|Dica]]</wrap><wrap help>[[Solucao:omegacartesomega|Solução]]</wrap>

**~~#~~** Mostre que $X$ é enumerável se, e somente se, podemos escrever $X = \{x_n: n \in \omega\}$. <wrap help>[[Solucao:condnecessariaesuficiente|Solução]]</wrap>

**~~#~~** Mostre que, se $A$ é enumerável e $B \subset A$, então $B$ é enumerável.

**~~#~~** Mostre que se $X$ é enumerável e existe $f: X \to Y$ sobrejetora, então $Y$ é enumerável.<wrap help>[[Solucao:solucao6|Solução]]</wrap>

**~~#~~** Mostre que se $A$ e $B$ são enumeráveis, então $A \times B$ é enumerável.<wrap help>[[Solucao:acartesianob|Solução]]</wrap>

**~~#~~** Mostre que $\omega^n$ é enumerável para todo $n \in \omega$ com $n > 0$.<wrap tip>[[dica:potenciaOmega|Dica]]</wrap>


**~~#~~** Mostre que se cada $A_n$ é enumerável, então $\bigcup_{n \in \omega} A_n$ é enumerável.<wrap tip>[[Dica:uniaoEnum|Dica]]</wrap>

**~~#~~** Mostre que $2^\omega$ (conjunto das funções de $\omega$ em $\{0, 1\}$) não é enumerável.<wrap tip>[[Dica:funNEm|Dica]]</wrap><wrap help>[[Solucao:funcNem01|Solução]]</wrap>

**~~#~~** Mostre que existe uma bijeção entre $2^\omega$ e $\wp(\omega)$ (conjunto de todos os subconjuntos de $\omega$).<wrap tip>[[Dica:partesOmega|Dica]]</wrap><wrap help>[[Solucao:BijPartesOmega|Solução]]</wrap> 

<WRAP info> Dizemos que $X$ é {{entry>finito}} se existe uma função injetora de $X$ em $\{1, ..., n\}$ para algum $n \in \omega$.
</WRAP>

**~~#~~** Mostre que se $X$ é infinito (isto é, não finito), existe $f: \omega \to X$ injetora. 

**~~#~~** Este é um roteiro para mostrar que se $X$ é enumerável e infinito, então existe $f: \omega \to X$ função bijetora. Fixe $g: \omega \to X$ sobrejetora. 

**~~#.#~~** Construa por indução $(k_n)_{n \in \omega}$ da seguinte forma: $k_0 = 0$, $k_{n + 1} = \min\{a \in \omega: g(a) \neq g(k_j)$ para todo $j \leq n\}$.

**~~#.#~~** Defina $f: \omega \to X$ como $f(n) = g(k_n)$. Mostre que $f$ é injetora.

**~~#.#~~** Mostre que $f$ é sobrejetora.<wrap tip>[[dica:ehtodomundo|Dica]]</wrap>

<WRAP info>
Seja $A$ um conjunto. Denotamos por $[A]^{<\omega}$ a coleção de todos os subconjuntos finitos de $A$ (isto é, $\{X \subset A: X$ é finito$\}$). 
</WRAP>

**~~#~~** Seja $A$ enumerável. Defina, para cada $n \in \omega$, $A_n = \{B \subset A: B$ tem $n$ elementos$\}$.

**~~#.#~~** Dado $n \in \omega$ com $n \neq 0$, mostre que existe uma função $\varphi: A_n \times A \to A_n \cup A_{n + 1}$ sobrejetora.<wrap help>[[Solucao:uniao|Solução]]</wrap>

**~~#.#~~** Mostre que cada $A_n$ é enumerável. <wrap help>[[Solucao:A_n-enumeravel|Solução]]</wrap>

**~~#.#~~** Mostre que $\bigcup_{n \in \omega} A_n = [A]^{<\omega}$.

**~~#.#~~** Conclua que $[A]^{<\omega}$ é enumerável.

**~~#~~** Mostre que, se $A$ é enumerável e infinito, então $\wp(A)$ é não enumerável.<wrap help>[[Solucao:partesdeA|Solução]]</wrap>

**~~#~~** Mostre que o conjunto dos subconjuntos infinitos de $\omega$ é não enumerável.