Indicando com card
o número de elementos do conjunto finito
, prove:
(a) Se
é finito e
então card
.
(b) Se
e
são finitos então
é finito e
(a) Se
(b) Se
Passo 1
O enunciado pede para usar a noção de conjunto finito e sua cardinalidade (denotada por
) para provar duas coisas:
(a) que se é finito e
então
;
(b) que, se e
são finitos, então
também é finito e satisfaz a fórmula de inclusão-exclusão
(a) que se
(b) que, se
Para isso vamos usar a definição de conjunto finito via bijeções com
e as propriedades de injeções, restrições e uniões disjuntas.
Passo 2
Definição e propriedade fundamental. Dizemos que um conjunto
é finito se existe bijeção
para algum
. Nesse caso chamamos
.
Uma consequência importante é:
se é bijetora e
, então a restrição
Uma consequência importante é:
se
é bijetora entre
e
. Logo
é finito e
.
Passo 3
Prova de (a). Seja
. Pela definição existe bijeção
Como
, o conjunto
é subset de
. A bijeção restrita
mostra que
é finito com
Logo (a) está provado.
Passo 4
Propriedade da diferença e interseção. Se
e
são finitos, então
é finito por (a). Além disso
se decompõe como união disjunta
portanto, como soma de cardinalidades em união disjunta,
Dessa igualdade segue
Passo 5
União de disjuntos. Se
e
são finitos e
, então podemos enumerar
em
e
em
. Uma bijeção para
é dada mandando
Isso mostra que
é finito e
Passo 6
Conclusão de (b). Tome
e
. Sabemos que
é finito por passo 4 e
. Então
Como
e
, obtemos
Resposta
(a) Se
então
.
(b) Se e
são finitos então
é finito e
(b) Se