Construa uma bijeção
entre os conjuntos
dos naturais e
dos inteiros (demonstrando, dessa forma, que
é enumerável).
Passo 1
Nesse exercício queremos construir uma bijeção f entre os naturais
e os inteiros
, mostrando assim que
é enumerável. O que vamos precisar: entender o conceito de bijeção (injeção + sobrejeção) e encontrar uma forma sistemática de listar todos os inteiros a partir dos naturais.
Passo 2
Uma forma clássica é intercalar inteiros não negativos e negativos usando a paridade de
. Vamos definir f de modo que números pares mapeiem para
e ímpares para
.
Passo 3
Definimos a função f por
Passo 4
Passo 5
Mostramos injetividade. Suponha
. Se esse valor for
, então tanto
quanto
são pares e temos
, logo
. Se for
, ambos são ímpares e
implica
. Assim,
é injetora.
Passo 6
Mostramos sobrejeção. Dado
: se
, escreva
e escolha
, pois
. Se
, escreva
com
e escolha
, pois
. Então todo inteiro tem um pré-imagem em
.
Passo 7
Como
é injetora e sobrejetora, é bijetora, o que prova que
é enumerável.