Prove os itens abaixo.
Sejam
conjuntos finitos. Mostre que
é finito e
Sejam
Passo 1
O enunciado afirma que
e
são conjuntos finitos e pede para mostrar que o produto cartesiano
também é finito e que
O conteúdo principal aqui é a noção de bijeção e a contagem de pares ordenados a partir de enumerações de conjuntos finitos.
Passo 2
Como
é finito, existe bijeção
onde
. De modo análogo, como
é finito, existe bijeção
onde
.
Passo 3
Definimos
Mostramos que
é bijetora:
- Injetividade: se
então e . Pela injetividade de e segue e . - Sobrejetividade: dado qualquer par
, como e são sobrejetoras, existem e tais que , . Então .
Passo 4
Logo
é finito, pois bijete-se com o conjunto finito
. Resta contar quantos elementos tem
. Para cada
há exatamente
pares
com
. Assim
Passo 5
Como há bijeção
segue
Resposta
Mostramos que
é finito e