Mostre que o conjunto de todas as funções de
para
é enumerável.
Dica: Seja
o conjunto de todas as funções de
para
. Mostre que a função
:
definida por
é uma bijeção.
Passo 1
O enunciado quer mostrar que o conjunto
de todas as funções de em
é enumerável. Para isso vamos usar o conceito de bijeção: uma vez que
já é conhecido como enumerável, basta construir uma bijeção
.
A dica já nos dá a definição
de todas as funções de
A dica já nos dá a definição
Passo 2
Mostramos que
é injetora. Suponha duas funções
com
.
Então
com
Então
Daí
e
. Mas como
e
são definidas em todo o conjunto
, isso implica
para
e
, ou seja,
. Logo,
é injetora.
Passo 3
Mostramos que
é sobrejetora. Tome um par qualquer
.
Defina por
Defina
Então
.
Como era um elemento arbitrário de
, segue que todo elemento desse produto tem contraimagem em
. Logo,
é sobrejetora.
Como
Passo 4
Concluímos que
é bijeção entre
e
. Como é clássico (por exemplo, pelo argumento da diagonal de Cantor ou pela função de pareamento de Cantor) que
é enumerável, segue que
também é enumerável.
Resposta
O conjunto
é enumerável, pois existe uma bijeção natural
que associa a cada função o par
, e
é enumerável.
que associa a cada função