Sejam
e
dois conjuntos finitos. Prove que
Passo 1
Beleza, temos dois conjuntos finitos
e
e queremos provar que
Aqui o conteúdo é teoria de conjuntos (diferença, interseção, união) e cardinalidade (número de elementos). Para resolver precisamos:
- Entender que toda a coleção de elementos de
se divide em “os que também estão em ” e “os que não estão em ”. - Usar a propriedade de cardinalidade de uniões de conjuntos disjuntos: se
e não têm elemento em comum, então
Passo 2
Primeiro, vamos ver que
• Definição de diferença:
• Interseção:
Agora, pegue um elemento
. Ou ele está em
(então
) ou não está em
(então
). Logo todos os
de
estão em uma dessas duas partes, e nenhuma sobra fora. Assim a união é exatamente
.
Passo 3
A gente também precisa ver que essas duas partes não “se misturam”, ou seja são disjuntas:
Prova rápida: suponha que exista
nesse encontro. Então
(logo
) e
(logo
). Contradição. Portanto não há elemento em comum.
Passo 4
Agora aplicamos a propriedade de cardinalidade de união de conjuntos disjuntos: se
, então
Substituindo
e
, e lembrando que
, a gente tem
Basta isolar
: