Sejam
e
dois conjuntos finitos. Prove que
símbolo
representa o número de elementos do conjunto
.
Passo 1
O enunciado pede para provar a fórmula de inclusão-exclusão para dois conjuntos finitos
e
, isto é,
O conteúdo aqui é contagem de elementos em uniões de conjuntos e vamos usar a ideia de particionar os conjuntos em partes disjuntas e depois aplicar a aditividade da cardinalidade sobre uniões disjuntas.
Passo 2
Definimos as três partes disjuntas a seguir:
Esses três conjuntos são mutuamente disjuntos (não têm elemento em comum) e satisfazem
Passo 3
Como a cardinalidade é aditiva em uniões de conjuntos disjuntos, temos
Passo 4
Por outro lado, cada um dos conjuntos
e
também se decompõe em duas partes disjuntas:
Logo
Passo 5
Somando as duas últimas igualdades, obtemos
Comparando com a expressão de
do Passo 3, vemos que
e, isolando
, segue-se a fórmula desejada: