Questão 2. Sejam
conjuntos enumeráveis. Mostre que
é também enumerável.
Dica: Use as bijeções
e defina
dada por
.
Dica: Use as bijeções
Passo 1
O enunciado pede para mostrar que
é enumerável, sabendo que cada conjunto
é enumerável. O que foi dado explicitamente:
- Para cada
existe uma bijeção .
A tarefa é produzir uma enumeração de(ou seja, mostrar que existe uma bijeção , ou pelo menos uma surjeção seguida de uma padronização que torne bijetiva).
Passo 2
Defina a função
Primeiro ver que
está bem definida: para qualquer par
tem-se
, logo
é realmente um elemento de
. Portanto
é uma aplicação com domínio
e contradomínio
.
Passo 3
Mostre que
é sobrejetora (surjetiva). Tome
. Pelo modo como
foi definido, existe algum índice
tal que
. Como
é bijeção
, existe
com
. Então
Isso prova que para todo
existe
com
; logo
é sobrejetora.
Passo 4
Agora precisamos usar que
é enumerável. Vou construir explicitamente uma bijeção
. Uma maneira clássica (método das diagonais / função de Cantor) é a seguinte. Para
defina
A função
é bijetora (é a função de pareamento de Cantor). Uma explicação sucinta do porquê ela é bijetora:
- Os números da forma
são os números triangulares . Para cada existe um único tal que . - Dado
, defina como o inteiro que satisfaz , e então e . Esses são não-negativos e verificam . Isso dá a inversa explícita de , provando que é bijetora.
Comoé bijeção , sua inversa é uma bijeção . (Intuitivamente: enumeramos os pares por diagonais .)
Passo 5
Agora compose as funções: defina
. Para cada
,
Como
é sobrejetora e
é bijetora (em particular sobrejetora), a composição
é sobrejetora. Assim existe uma enumeração (possivelmente com repetições) de todos os elementos de
dada pela sequência
.
Passo 6
Transformar a enumeração sobrejetora
em uma bijeção explicitando os elementos sem repetição (procedimento padrão). Construa a sequência
por recorrência:
-
. - Suponha
já escolhidos; então escolha com mínimo tal que .
Porqueé sobrejetora, todo elemento aparece em alguma posição , logo no processo acima cada elemento de será eventualmente escolhido como algum . Assim definida por é bijeção: é injetiva por construção (não há repetições na lista) e é sobrejetiva porque cobre todo . Portanto existe bijeção , isto é, é enumerável.