Questão 31 Sejam
um conjunto infinito enumerável e
onde
não são necessariamente distintos dois a dois. Mostre que
é enumerável.
Passo 1
O enunciado dá:
-
é um conjunto infinito enumerável (ou seja, existe uma enumeração de por números naturais). - Para um inteiro fixo
,
O que se pede: mostrar que
é enumerável (ou seja, que existe uma enumeração por números naturais, ou equivalentemente que há bijeção entre
e
).
Passo 2
Vamos usar a ideia básica: como
é enumerável, existe uma bijeção
Explicar o que isso significa: cada elemento de
aparece exatamente uma vez na sequência
. Agora observe que qualquer tupla
corresponde, via
coordenada a coordenada, a uma tupla de naturais
Portanto existe uma bijeção natural entre
e
. Conclusão parcial: basta provar que
é enumerável.
Passo 3
Mostrar primeiro que
é enumerável. Vou dar uma enumeração explícita (diagonal) e uma fórmula fechada para indexar pares. Enumeração por diagonais: listar todos os pares com soma
, depois soma
, depois soma
, etc. Mais formalmente, para
(aqui
) defina o inteiro
O número de pares
com soma estritamente menor que
é
Dentro dos pares com soma igual a
ordenamos por
. Assim podemos definir a função
Explicação do que faz
: conta quantos pares vieram antes (a soma menor que
) e soma a posição do par na diagonal correspondente. A fórmula acima é bijetora (cada par tem um índice natural distinto e todo natural aparece para algum par), portanto
é enumerável.
Passo 4
Agora estendo para dimensões maiores por indução. Se já sabemos que
é enumerável para algum
, então
é produto de dois conjuntos enumeráveis. Como provado no passo anterior, o produto de dois conjuntos enumeráveis é enumerável (basta aplicar a enumeração de
e a de
e usar o mesmo truque de pareamento/diagonal para enumerar pares de índices). Assim, por indução em
,
é enumerável para todo
finito.
Esclarecimento didático: a ideia é reduzir
a
recursivamente. Se existe bijeção
, então a bijeção entre
e
é obtida compondo
com a bijeção
do passo anterior aplicada aos índices. Assim constrói-se uma enumeração explícita de
.
Passo 5
Voltar para
. Lembrando que havia uma bijeção
. Então a aplicação
é bijetora (é inversível via
). Como
é enumerável (Passo 4), e
é bijetivo a
, segue que
é enumerável.
Comentário amigável: em palavras simples, como
pode ser listada como
, para listar todas as tuplas de comprimento
basta listar todas as combinações de índices
de forma ordenada (por exemplo pelas somas
e depois por ordem lexicográfica), e então substituir cada índice pelo elemento correspondente de
. Isso dá uma lista que contém todas as tuplas de
e nada mais.