Prove que o conjunto \mathcal{F}(\mathbb{N},\{0,1\}), ou seja, das sequências s: \mathbb{N} \longrightarrow\{0,1\}, é não-enumerável. (Lembre que uma sequência s_{1} de \mathcal{F}(\mathbb{N},\{0,1\}) é uma sequência binária do tipo (1011010 \ldots) )
15. O conjunto
A=\left\{\left.\frac{1}{n} \right\rvert\, n \in \mathbb{N}\right\}

Passo 1

O enunciado pede para mostrar que o conjunto
\mathcal F(\mathbb N,\{0,1\})=\{\,s\mid s:\mathbb N\to\{0,1\}\}
não é enumerável. Aqui “enumerável” significa que existe uma bijeção entre \mathbb N e \mathcal F(\mathbb N,\{0,1\}). Vamos usar o argumento diagonal de Cantor.

Passo 2

Suponha, por absurdo, que \mathcal F(\mathbb N,\{0,1\}) seja enumerável. Então existe uma lista que contém todas as sequências binárias:
s_{1},s_{2},s_{3},\dots
onde cada s_{k} é uma função s_{k}:\mathbb N\to\{0,1\}. Podemos pensar em s_{k} como a sequência
(s_{k}(1),\,s_{k}(2),\,s_{k}(3),\dots).

Passo 3

Vamos construir uma nova sequência \tilde s de modo que ela difira de cada s_{n} na posição n. Defina
\tilde s(n)=1 - s_{n}(n),
ou seja, no “diagonal” do quadro em que as linhas são as s_{n} e as colunas são os índices naturais, \tilde s sempre inverte o bit.

Passo 4

Mostramos que \tilde s não pode coincidir com nenhum s_{n}. De fato, se por acaso \tilde s = s_{n} para algum n, então olhando a posição n teríamos
\tilde s(n)=s_{n}(n),
mas pela construção \tilde s(n)=1 - s_{n}(n). Isso gera a contradição
s_{n}(n)=1 - s_{n}(n).

Resposta

Não existe enumeração de \mathcal F(\mathbb N,\{0,1\}). Portanto, este conjunto é não-enumerável.

Exercícios relacionados