(A.43) Sejam
e
dois conjuntos finitos. Provar que
Passo 1
O enunciado dá exatamente isto:
- Dois conjuntos finitos
e . - Pede provar a identidade
Vou listar claramente o que se pede e o que é dado:
- Dado:
e são finitos (logo têm número finito de elementos). - Pedido: demonstrar a igualdade acima entre as cardinalidades (números de elementos) dos conjuntos.
Passo 2
Vamos lembrar (explicar) alguns conceitos e uma propriedade básica que usarei passo a passo.
Definições e fatos úteis:
-
significa o número de elementos do conjunto (cardinalidade). - A diferença de conjuntos
é o conjunto dos elementos que estão em e não estão em . - Dois conjuntos
e são disjuntos quando (sem elemento em comum). - Propriedade básica de contagem (que aceitamos/explanamos aqui): se
e são conjuntos finitos e disjuntos então
Explicação dessa propriedade: como
e
não têm elementos em comum, ao formar
cada elemento vem ou de
ou de
, sem duplicação; portanto o total é a soma dos totais. Formalmente pode-se construir uma enumeração dos elementos de
listando primeiro os de
depois os de
, obtendo
elementos no total.
Passo 3
Fazer uma decomposição útil de
em partes disjuntas.
Qualquer elemento
pertence a pelo menos um dos conjuntos
ou
. Há exatamente três casos mutuamente exclusivos para um
:
-
e (ou seja, ); -
e (ou seja, ); -
e (ou seja, ).
Esses três conjuntos são mutuamente disjuntos (não se sobrepõem):
-
claramente; -
porque não tem elementos de ; -
por analogia.
Portanto podemos escrever a união como união disjunta destas três partes:
com as três partes sendo disjuntas entre si.
Passo 4
Aplicar a propriedade de soma de cardinalidades para união de conjuntos disjuntos.
Como as três partes são disjuntas e finitas, podemos somar suas cardinalidades:
Passo 5
Expressar
e
em termos das mesmas partes.
Repare que
se decompõe em duas partes disjuntas:
portanto, pela propriedade de soma:
Analogamente,
Passo 6
Somar
e
e relacionar com
.
Somando as duas igualdades do passo anterior:
Agrupando termos:
Comparando com a expressão do passo 4,
vemos que a soma
tem exatamente um
a mais do que
. Subtraindo
de ambos os lados da expressão para
obtemos:
Passo 7
Interpretação curta e alternativa (intuitiva):
- Ao somar
conta-se cada elemento que está em duas vezes (uma vez em e outra em ). Para corrigir essa dupla contagem, subtrai-se uma vez. Isso leva diretamente à fórmula desejada.