Princípio de Inclusão-Exclusão

Diz respeito à cardinalidade de uma união de conjuntos finitos em termo das cardinalidades deles e de suas intersecções.

Sua demonstração usa o princípio aditivo para o caso com dois conjuntos e o princípio da indução para generalizar para qualquer número de conjuntos.

Vou assumir aqui o princípio aditivo (que demonstrarei em outro tópico). O princípio da indução é um axioma.

Princípio aditivo:
n=2: Se A e B são conjuntos disjuntos, então |A U B| = |A| + |B|.
Geral: Se A_1,...,A_n são conjuntos disjuntos dois a dois, então |A_1 U ... U A_n| = |A_1| + ... + |A_n| = Σ_{i=1}^{n} |A_i|

Princípio da indução:
Primeira formulação: Se A é um conjunto de números naturais tal que 1 pertence a A e tal que, para todo k em A, k+1 também está em A, então A=N, isto é, A é o próprio conjunto de todos os números naturais.
(Aqui zero é entendido como não sendo natural. Se quisermos denotar todos os inteiros não negativos escreveremos N_0.)
Consequência (será demonstrada em outro tópico): Se P é um predicado sobre números naturais, P(1) é proposição verdadeira e para um k fixo qualquer "se P(k) então P(k+1)" é proposição verdadeira, então P(n) é verdade para todo n natural.

Princípio de Inclusão-Exclusão para n=2: Se A e B são dois conjuntos finitos quaisquer, então |A U B| = |A| + |B| - |A∩B|


Demonstração: 
A U B = (A-B) U B
A-B e B são conjuntos disjuntos, portanto, usando o princípio aditivo,
|A U B| = |(A-B) U B| = |A-B| + |B|
Mas (A-B) U (A∩B) = A, e A-B e A∩B são conjuntos disjuntos, portanto
|A|=|(A-B) U (A∩B)| = |A-B| + |A∩B|
=> |A-B| = |A| - |A∩B|
Substituindo a expressão obtida para |A-B| na expressão para |A U B|, obtemos
|A U B| = |A-B| + |B| = |A| + |B| - |A∩B|
como queríamos provar.

Princípio de Inclusão-Exclusão para n=3: Se A, B e C são conjuntos finitos quaisquer então |A U B U C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|


Isso é pra mostrar qual será a idéia do passo indutivo na demonstracão do caso geral com um caso mais simples.


Demonstração:
|A U B U C| = |(A U B) U C| = |A U B| + |C| - |(A U B)∩C| = |A| + |B| - |A∩B| + |C| - |(A∩C)U(B∩C)| = |A| + |B| + |C| - |A∩B| - (|A∩C|+|B∩C| - |A∩B∩C|) = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|


Aqui foi usado o resultado já obtido para n=2, além de propriedades básicas de união e intersecção de conjuntos, como associatividade, distributividade, comutatividade e idempotência.

Princípio de Inclusão-Exclusão: Se A_1, ... , A_n são conjuntos finitos, então |A_1 U ... U A_n| = Σ_{k=1}^{n} (-1)^(k+1) Σ_{1<=i_1<...<i_k<=n} |A_{i_1} ∩ ... ∩ A_{i_k}|


Demonstração:
Para o caso n=2 ele já foi demonstrado.


Passo indutivo:
Suponha que seja verdade para certo m fixo, isto é, para quaisquer m conjuntos finitos A_1, ... , A_m, temos que
|A_1 U ... U A_m| = Σ_{k=1}^{m} (-1)^(k+1) Σ_{1<=i_1<...<i_k<=m} |A_{i_1} ∩ ... ∩ A_{i_k}|


Então, seja A_{m+1} um outro conjunto finito qualquer.
Temos que
|A_1 U ... U A_m U A_{m+1}| = |(A_1 U ... U A_m) U A_{m+1}|
= |A_1 U ... U A_m| + |A_{m+1}| - |(A_1 U ... U A_m) ∩ A_{m+1}| 
= (Σ_{k=1}^{m} (-1)^(k+1) Σ_{1<=i_1<...<i_k<=m} |A_{i_1} ∩ ... ∩ A_{i_k}|) + |A_{m+1}| - |(A_1 ∩ A_{m+1}) U ... U (A_m ∩ A_{m+1})| 
= (Σ_{k=1}^{m} (-1)^(k+1) Σ_{1<=i_1<...<i_k<=m} |A_{i_1} ∩ ... ∩ A_{i_k}|) + |A_{m+1}| - (Σ_{k=1}^{m} (-1)^(k+1) Σ_{1<=i_1<...<i_k<=m} |A_{i_1} ∩ ... ∩ A_{i_k} ∩ A_{m+1}|) 
= |A_1| + ... + |A_m| + |A_{m+1}| - (Σ_{1<=i_1<i_2<m} |A_{i_1} ∩ A_{i_2}| + Σ_{1<=i_1<=m} |A_{i_1} ∩ A_{m+1}|) + ... + (-1)^(m+1)*(|A_1 ∩ ... ∩ A_m| + Σ_{1<=i_1<...<i_{m-1}<=m} |A_{i_1} ∩ ... ∩ A_{i_{m-1}} ∩ A_{m+1}|) + (-1)^(m+2)*|A_1 ∩ ... ∩ A_m ∩ A_{m+1}|
= Σ_{1<=i_1<=m+1} |A_{i_1}| - Σ_{1<=i_1<i_2<=m+1} |A_{i_1} ∩ A_{i_2}| + ... + (-1)^(m+1) Σ_{1<=i_1<...<i_m<m+1} |A_{i_1} ∩ ... ∩ A_{i_m}| + (-1)^(m+2)*|A_1 ∩ ... ∩ A_m ∩ A_{m+1}|
= Σ_{k=1}^{m+1} (-1)^(k+1) Σ_{1<=i_1<...<i_k<m+1} |A_{i_1} ∩ ... ∩ A_{i_k}|


O passo indutivo se verificou. Logo, pelo princípio da indução, o princípio de inclusão-exclusão é válido para todo n natural.