Prove os itens abaixo.
Sejam
conjuntos finitos. Mostre que
é finito e
Sejam
Passo 1
O enunciado pede para mostrar que, dados conjuntos finitos
, o produto cartesiano
é também finito e que
O plano é usar indução em
e, no passo de indução, reduzir ao caso de dois fatores, usando que a união disjunta de conjuntos finitos tem cardinal igual à soma dos cardinais.
Passo 2
Caso
.
Aqui , que é finito por hipótese, e
Aqui
o que coincide com a fórmula
. Logo o enunciado vale para
.
Passo 3
Caso
.
Seja com
e
com
. Considere
Seja
Cada conjunto
tem exatamente
elementos e, para
,
e
são disjuntos. Logo é uma união disjunta de
conjuntos de tamanho
. Pelo fato de que a união disjunta de conjuntos finitos tem cardinal igual à soma dos cardinais, segue
Isso prova o caso
.
Passo 4
Indução de
para
.
Suponha que, para algum , valha
Suponha que, para algum
Defina
Pelo passo de indução
é finito e
. Aplicando o caso
a
e
, obtemos
Como
, conclui-se que o enunciado vale para
.
Resposta
Pelo princípio da indução, para todo
o produto cartesiano de
conjuntos finitos continua finito e