Sejam
e
dois conjuntos enumeráveis quaisquer. Prove que o produto cartesiano
e
também é um conjunto enumerável.
Passo 1
O enunciado diz que
e
são conjuntos enumeráveis, ou seja, cada um deles pode ser posto em bijeção com o conjunto dos naturais
. O objetivo é mostrar que o produto cartesiano
também admite uma bijeção com
, provando assim que
é enumerável. Vamos usar conceitos de bijeções e a função de emparelhamento de Cantor.
Passo 2
Como
e
são enumeráveis, existem bijeções
Elas nos permitem listar todos os elementos de
como
e de
como
.
Passo 3
É sabido que o conjunto
também é enumerável. Uma bijeção clássica de Cantor é
Esse
é bijetora, portanto existe inversa
que para cada natural
fornece um par
.
Passo 4
Agora construímos uma bijeção
como composição de
com
e
. Definimos
Como
percorre todos os pares
exatamente uma vez, e
e
são bijections, segue que
é bijetora de
em
.
Resposta
Como existe bijeção
, concluímos que
é enumerável.