Sejam
conjuntos finitos disjuntos 2 a 2 . Prove que
Passo 1
O enunciado dá que
são conjuntos finitos e que são disjuntos dois a dois. Ou seja, para quaisquer índices
vale
. O que precisamos provar é a igualdade entre o número de elementos da união e a soma dos números de elementos de cada conjunto:
Lista das informações relevantes que o enunciado fornece:
- Cada
é finito, portanto existe um inteiro não negativo que conta seus elementos. - Os conjuntos são disjuntos dois a dois:
para .
O objetivo é deduzir a fórmula acima usando essas informações.
Passo 2
Vou explicar alguns conceitos que vou usar (bem devagar, passo a passo).
- Definição de finitude e cardinalidade: um conjunto
é finito quando existe um inteiro e uma bijeção . O inteiro é exatamente , o número de elementos de . - Bijeção: uma função é bijetora quando é injetora (valores distintos têm imagens distintas) e sobrejetora (toda posição alvo é atingida). Se existe bijeção entre dois conjuntos, eles têm a mesma cardinalidade.
- Disjunção (dois a dois): se
, então nenhum elemento pertence simultaneamente a e a ; isso evita contagem dupla.
Essas noções permitem construir bijeções explícitas para contar elementos da união quando os conjuntos são disjuntos.
Passo 3
Estratégia do argumento: vou provar a afirmação por indução sobre
.
- Caso base: verifico para
(e também mostrarei detalhadamente , que é a etapa crítica). - Passo indutivo: assumo a afirmação válida para
conjuntos e mostro para conjuntos, usando o caso aplicado à união dos primeiros com o -ésimo conjunto.
Essa escolha é natural porque a operação de união é associativa, e juntar
conjuntos pode ser visto como primeiro juntar
deles e depois unir com o último.
Passo 4
Caso base
. É imediato:
. Portanto a propriedade é verdadeira para
.
Passo 5
Caso
. Este é o passo central: mostrar que, se
e
são conjuntos finitos e
, então
Detalho a prova construtiva.
- Seja
e . Como e são finitos, existem bijeções
- Quero construir uma bijeção
de para . Como e são disjuntos, não há ambiguidade em distinguir um elemento que vem de ou de . - Defino
da seguinte forma: para ponho
e para
ponho
- Verifico que
é bem definida: cada elemento de pertence ou a ou a , e como não há conflito sobre qual caso escolher. - Injetividade de
: suponha . Se e , então e como é injetora obtemos . Se e , argumento análogo com . Se um está em e o outro em , então e , conjuntos disjuntos, portanto não podem ser iguais. Logo é injetora. - Sobrejetividade de
: todo é ou ou . No primeiro caso existe com , logo . No segundo caso existe com , logo . Assim é sobrejetora. - Como
é bijeção, . - Exemplo concreto e rápido para intuir: se
e , então uma contagem organizada é — são elementos, sem duplicação porque e não se sobrepõem.
Passo 6
Passo indutivo: suponha a afirmação verdadeira para
conjuntos disjuntos dois a dois, isto é, supõe-se que
Denote
. Observações:
-
é finito (união finita de conjuntos finitos). - Pelo enunciado,
é disjunto de cada para , logo .
Aplicando o caso(Passo 5) aos conjuntos e , obtemos
Mas
e pela hipótese indutiva
. Substituindo:
o que é exatamente a fórmula desejada para
.
Passo 7
Conclusão por indução: como a propriedade vale para
e o passo indutivo foi estabelecido, segue que para todo
e para quaisquer conjuntos finitos
que sejam disjuntos dois a dois,
Pequeno comentário final de incentivo: a ideia chave é sempre a mesma — quando não há interseção entre conjuntos, não há risco de contar alguém duas vezes, então a união “soma” as contagens; provar isso rigorosamente passa por construir uma bijeção ou usar indução.