Ferramentas do usuário
Enumerabilidade
Denotamos por $\omega$ o conjunto dos números naturais.
Dizemos que um conjunto $X$ é enumerável se existe $f: \omega \rightarrow X$ sobrejetora.
1 Mostre que $\omega \times \omega$ é enumerável.Dica
2 Mostre que $X$ é enumerável se, e somente se, podemos escrever $X = \{x_n: n \in \omega\}$.
3 Mostre que, se $A$ é enumerável e $B \subset A$, então $B$ é enumerável.
4 Mostre que se $A$ e $B$ são enumeráveis, então $A \times B$ é enumerável.
5 Mostre que $\omega^n$ é enumerável para todo $n \in \omega$ com $n > 0$.Dica
6 Mostre que se $X$ é enumerável e existe $f: X \to Y$ sobrejetora, então $Y$ é enumerável.
7 Mostre que se cada $A_n$ é enumerável, então $\bigcup_{n \in \omega} A_n$ é enumerável.Dica
8 Mostre que $2^\omega$ (conjunto das funções de $\omega$ em $\{0, 1\}$) não é enumerável.DicaSolução
9 Mostre que existe uma bijeção entre $2^\omega$ e $\wp(\omega)$ (conjunto de todos os subconjuntos de $\omega$).DicaSolução
Dizemos que $X$ é finito se existe uma função injetora de $X$ em $\{1, \ldots, n\}$ para algum $n \in \omega$.
10 Mostre que se $X$ é enumerável e infinito, então existe $f: X \to \omega$ função bijetora.Dica
Seja $A$ um conjunto. Denotamos por $[A]^{<\omega}$ a coleção de todos os subconjuntos finitos de $A$ (isto é, $\{X \subset A: X$ é finito$\}$).
11 Seja $A$ é enumerável. Defina, para cada $n \in \omega$, $A_n = \{B \subset A: B$ tem $n$ elementos$\}$.
11.1 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.Solução
11.2 Mostre que cada $A_n$ é enumerável.
11.3 Mostre que $\bigcup_{n \in \omega} A_n = [A]^{<\omega}$.
11.4 Conclua que $[A]^{<\omega}$ é enumerável.
12 Mostre que, se $A$ é enumerável e infinito, então $\wp(A)$ é não enumerável.Solução
13 Mostre que o conjunto dos subconjuntos infinitos de $\omega$ é não enumerável.
Ferramentas da página
