Sejam X e Y dois conjuntos enumeráveis quaisquer. Prove que o produto cartesiano X times Y=(x, y) ; x in X e y in Y também é um conjunto enumerável.

Passo 1

O enunciado diz que X e Y são conjuntos enumeráveis, ou seja, cada um deles pode ser posto em bijeção com o conjunto dos naturais N. O objetivo é mostrar que o produto cartesiano
Xtimes Y = (x,y)mid xin X,;yin Y
também admite uma bijeção com N, provando assim que Xtimes Y é enumerável. Vamos usar conceitos de bijeções e a função de emparelhamento de Cantor.

Passo 2

Como X e Y são enumeráveis, existem bijeções
fcolon Nto X e gcolon Nto Y
Elas nos permitem listar todos os elementos de X como f(0),f(1),f(2),dots e de Y como g(0),g(1),g(2),dots.

Passo 3

É sabido que o conjunto N^2 também é enumerável. Uma bijeção clássica de Cantor é
picolon N^2 to N, pi(i,j) = (i+j)(i+j+1)2 + j
Esse pi é bijetora, portanto existe inversa
pi^-1colon Nto N^2,
que para cada natural k fornece um par l(i,jr).

Passo 4

Agora construímos uma bijeção
hcolon Nto Xtimes Y
como composição de pi^-1 com f e g. Definimos
h(k) = l(f(i),,g(j)r) onde (i,j)=pi^-1(k)
Como pi^-1 percorre todos os pares (i,j)inN^2 exatamente uma vez, e f e g são bijections, segue que h é bijetora de N em Xtimes Y.

Resposta

Como existe bijeção hcolon Nto Xtimes Y, concluímos que Xtimes Y é enumerável.

Exercícios relacionados