Topologia e conjuntos em exercícios

Seja $f:\omega \rightarrow \{0,1\}$. Então temos que 
$$f(0)= a_0;\ f(1)=a_1;\ ...\;f(n)=a_n,\ ... $$
onde $a_i$ é $0$ ou $1$.
\\
Note que podemos representar cada $f$ unicamente pela sequência formada pelos elementos $a_i$ como feito a cima, portanto basta mostrarmos que o conjunto formado por **todas** as sequências infinitas enumeráveis com elementos $0$ ou $1$ não é enumerável.
\\
\\
**Afirmação:** O conjunto $A=\{a^n = (a^n_1,\ a^n_2,\ ...)\ |\ a_i \in \{0,1\},\ \forall i\in \mathbb{N}\}$ é não enumerável.
\\
Suponha que $A$ é enumerável. Então podemos criar uma lista com **todos** as sequências binárias enumeráveis $a^n$:

$$a^0 =   (a^0_1,\ a^0_2,\ a^0_3,\ a^0_4,\ a^0_5,\ ...)$$
$$a^1 =  (a^1_1,\ a^1_2,\ a^1_3,\ a^1_4,\ a^1_5,\ ...)$$
$$a^2 =   (a^2_1,\ a^2_2,\ a^2_3,\ a^2_4,\ a^2_5,\ ...)$$
$$...$$
$$a^n =   (a^n_1,\ a^n_2,\ a^n_3,\ a^n_4,\ a^n_5,\ ...)$$
$$...$$
Onde cada $a^j_i \in \{0,1\}$.
\\
\\
Considere agora a sequência enumerável binária $s=(s_1,\ s_2,\ s_3...)$  formada pelos elementos da diagonal da tabela a cima trocados, ou seja:

$$s_i=
\begin{cases}
0, & \text{se } a^i_i=1
\\
1, & \text{se } a^i_i=0
\end{cases}$$

Claramente, $s\in A$, porém $s$ não é nenhum elemento da lista. Absurdo!\\
Logo, A é não enumerável e pela observação inicial, vale o resultado para as funções de $\omega$ em $\{0,1\}$ .

\\
\\
Essa técnica que utilizamos para resolver o problema chama-se Argumento pela Diagonal de Cantor. Você pode querer ler mais sobre isso em [[http://en.wikipedia.org/wiki/Cantor's_diagonal_argument]]
Topologia e conjuntos em exercícios

Ferramentas do usuário

Ferramentas do site

Ferramentas da página
