(10%) Questão 9. Um conjunto
é dito ser enumerável quando existe uma bijeção
; nesse caso, seus elementos podem ser listados como
.
Mostre que
é enumerável.
Mostre que
Passo 1
O enunciado dá a definição: um conjunto
é enumerável quando existe uma bijeção
. Pede para mostrar que
é enumerável.
Informações relevantes do enunciado:
Informações relevantes do enunciado:
- Domínio disponível para a bijeção:
(lista ). - Conjunto alvo:
(inteiros positivos, negativos e zero).
O que exatamente é pedido: construir (e provar) uma bijeção, i.e., uma função bem definida que seja injetiva e sobrejetiva.
Passo 2
O que é preciso mostrar na prática (reminder didático, passo a passo):
- Bijeção significa que a função é simultaneamente injetiva e sobrejetiva.
- Definição de injetiva:
é injetiva se, para quaisquer , implica . - Definição de sobrejetiva:
é sobrejetiva se, para todo , existe tal que .
- Definição de injetiva:
- Estratégia prática comum: listar os inteiros em uma sequência que passe por todos eles sem repetir; por exemplo,
. Essa lista sugere uma fórmula sistemática para .
Passo 3
Propondo a função explícita (essa é a construção da bijeção):
Defina por
Defina
e, para todo
com
,
Interpretação concreta:
lista os inteiros na ordem
. Aqui
envia
positivo e
envia
.
Passo 4
Mostrar que
é sobrejetiva (cobre todos os inteiros):
- Seja
. Três casos: - Se
, então . - Se
, escreva com . Então . - Se
, escreva com . Então .
- Se
- Em cada caso existe um
(explicitamente , ou ) com . Logo é sobrejetiva.
Passo 5
Mostrar que
é injetiva (não repete valores para índices distintos):
Uma maneira simples e organizada é construir a inversa explícita e verificar que
é função inversa de
. Defina
Uma maneira simples e organizada é construir a inversa explícita
Verificações rápidas:
- Para todo
com , tem-se . - Para
, escreva como ou . Se então e . Se então e .
Portantoé a identidade em , o que implica que tem inversa à esquerda e, em particular, é injetiva. (Como já mostramos sobrejetividade, ter inversa à esquerda é suficiente para concluir bijetividade; aqui temos inversa de ambos os lados.)
Passo 6
Conclusão final do argumento:
- Construímos
explicitamente e mostramos que para todo existe com (sobrejetiva). - Construímos
e verificamos para todo (logo é injetiva e é a inversa de ).
Portantoé bijeção entre e . Assim é enumerável.
Resposta
A bijeção
é