Mostre que o conjunto de todas as funções de 0,1 para N é enumerável.
Dica: Seja F(0,1, N) o conjunto de todas as funções de 0,1 para N. Mostre que a função Phi : F(0,1, N) N times N definida por Phi(f)=(f(0), f(1)) é uma bijeção.

Passo 1

O enunciado quer mostrar que o conjunto
F(0,1,N)
de todas as funções de 0,1 em N é enumerável. Para isso vamos usar o conceito de bijeção: uma vez que NtimesN já é conhecido como enumerável, basta construir uma bijeção
Phicolon F(0,1,N) to NtimesN.
A dica já nos dá a definição
Phi(f) = l(f(0),,f(1)r)

Passo 2

Mostramos que Phi é injetora. Suponha duas funções
f,gin F(0,1,N)
com
Phi(f)=Phi(g).
Então
(f(0),f(1)) ;=;(g(0),g(1))
Daí f(0)=g(0) e f(1)=g(1). Mas como f e g são definidas em todo o conjunto 0,1, isso implica f(x)=g(x) para x=0 e x=1, ou seja, f=g. Logo, Phi é injetora.

Passo 3

Mostramos que Phi é sobrejetora. Tome um par qualquer
(a,b)in NtimesN.
Defina fcolon0,1toN por
f(0)=a, f(1)=b
Então
Phi(f)=(f(0),f(1))=(a,b).
Como (a,b) era um elemento arbitrário de NtimesN, segue que todo elemento desse produto tem contraimagem em F(0,1,N). Logo, Phi é sobrejetora.

Passo 4

Concluímos que Phi é bijeção entre F(0,1,N) e NtimesN. Como é clássico (por exemplo, pelo argumento da diagonal de Cantor ou pela função de pareamento de Cantor) que NtimesN é enumerável, segue que F(0,1,N) também é enumerável.

Resposta

O conjunto F(0,1,N) é enumerável, pois existe uma bijeção natural
Phicolon F(0,1,N)toNtimesN
que associa a cada função f o par (f(0),f(1)), e NtimesN é enumerável.

Exercícios relacionados