Principio di inclusione-esclusione

Template:F In matematica ed in particolare nella teoria degli insiemi, il principio di inclusione-esclusione è un'identità che mette in relazione la cardinalità di un insieme, espresso come unione di insiemi finiti, con le cardinalità di intersezioni tra questi insiemi.

Denotiamo con $\left|A\right|$ la cardinalità di un insieme $A$ e consideriamo una famiglia finita di insiemi finiti: $A_1,A_2,\cdots ,A_n$. Per la cardinalità dell'unione di tale famiglia si ha

$\left|\bigcup _{i=1}^n{A}_i\right|=\sum _{i=1}^n\left|A_i\right|-\sum _{1\le i<j\le n}|A_i\cap A_j|+\sum _{1\le i<j<k\le n}|A_i\cap A_j\cap A_k|-\cdots (-1{)}^{n-1}|A_1\cap \cdots \cap A_n|=$

$=\sum _{i=1}^n{(-1)}^{i+1}\sum _{1\le j_1<...<j_i\le n}\left|\bigcap _{k=1}^i{A}_{j_k}\right|$

Rappresentazione con un diagramma di Eulero-Venn del caso per tre insiemi

Nel caso $n=2$ la formula si riduce a quella, molto intuitiva e ricavabile dalle definizioni, esprimibile come

$|A\cup B|=|A|+|B|-|A\cap B|$

Nel caso $n=3$ il principio si esprime con l'uguaglianza

$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$

Questa si dimostra servendosi più volte della precedente e della distributività della intersezione rispetto alla unione:

$|A\cup B\cup C|=|(A\cup B)\cup C|=|A\cup B|+|C|-|(A\cup B)\cap C|$

$=|A|+|B|-|A\cap B|+|C|-|(A\cap C)\cup (B\cap C)|$

$=|A|+|B|+|C|-|A\cap B|-(|A\cap C|+|B\cap C|-|(A\cap C)\cap (B\cap C)|)$

$=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$

Dimostrazioni

Dimostrazione I

Si dovrà dimostrare che ogni elemento dell'insieme $\bigcup _{i=1}^n{A}_i$ viene contato una e una sola volta. Sia $x\in A_1\cap A_2\cap \cdots \cap A_k$ e $x\notin A_{k+1}\cap \cdots \cap A_n$, riordinando cioè gli insiemi e supponendo che $x$ appartenga ai primi $k$.

Il termine $\sum _{i=1}^n\left|A_i\right|$ conta $x$ esattamente $(\genfrac{}{}{0ex}{}{k}{1})$ volte, mentre il secondo termine dello sviluppo della sommatoria, cioè $\sum _{1\le i<j\le n}|A_i\cap A_j|$ conta $x$ esattamente $(\genfrac{}{}{0ex}{}{k}{2})$ volte, ecc.

Dunque l'elemento $x$ nel principio di inclusione-esclusione è contato esattamente

$\sum _{i=1}^k(-1{)}^{i-1}(\genfrac{}{}{0ex}{}{k}{i})$ volte

Osserviamo che l'indice $i$ varia fino a $k$ perché considerando $i=k+1$, l'intersezione di $k+1$ con gli altri $A_i$ non conterrà $x$.

Si può ora dimostrare facilmente, considerando lo sviluppo del Binomio di Newton, che la sommatoria in questione è uguale a $1$:

$1-\sum _{i=1}^k(-1{)}^{i-1}(\genfrac{}{}{0ex}{}{k}{i})=\sum _{i=0}^k(-1{)}^i(\genfrac{}{}{0ex}{}{k}{i})=(1-1{)}^k=0◻$

Dimostrazione II (induzione su n)

Abbiamo che

$\left|\bigcup _{i=1}^n{A}_i\right|=\sum _{k=1}^n(-1{)}^{k+1}\sum _{1\le i_1<\cdots <i_k\le n}|A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_k}|$

Verifichiamola per $n=2$, dato che per $n=1$ è banalmente $\left|A_1\right|=\left|A_1\right|$, e il caso tornerà poi utile nel proseguimento della dimostrazione:

$|A_1\cup A_2|=\left|A_1\right|+\left|A_2\right|-|A_1\cap A_2|$

Ipotizziamo ora vero il principio per $n$ insiemi, e dimostriamo che allora è vero anche per $n+1$ insiemi. Vale che

$\bigcup _{i=1}^{n+1}{A}_i=\left(\bigcup _{i=1}^n{A}_i\right)\cup A_{n+1}$

Poiché l'ipotesi è vera per $n=2$ vale

$\left|\bigcup _{i=1}^{n+1}{A}_i\right|=\left|\bigcup _{i=1}^n{A}_i\right|+\left|A_{n+1}\right|-|\left(\bigcup _{i=1}^n{A}_i\right)\cap A_{n+1}|$

Ovvero

$\sum _{k=1}^n(-1{)}^{k+1}\sum _{1\le i_1<\cdots <i_k\le n}|A_{i_1}\cap \cdots \cap A_{i_k}|+\left|A_{n+1}\right|-\sum _{k=1}^n(-1{)}^{k+1}\sum _{1\le i_1<\cdots <i_k\le n}|A_{i_1}\cap \cdots \cap A_{i_k}\cap A_{n+1}|=$

$=\sum _{k=1}^{n+1}(-1{)}^{k+1}\sum _{1\le i_1<\cdots <i_k\le n+1}|A_{i_1}\cap \cdots \cap A_{i_k}|$

Tale proposizione è vera in quanto i due termini dell'uguaglianza hanno gli stessi addendi con lo stesso segno. Come volevasi dimostrare.

Storia

Il principio è stato utilizzato da Nicolaus II Bernoulli (1695-1726); la formula viene attribuita ad Abraham de Moivre (1667-1754); per il suo utilizzo e per la comprensione della sua portata vengono ricordati Joseph Sylvester (1814-1897) ed Henri Poincaré (1854-1912).

Voci correlate

• Formula di inversione di Moebius-Rota
• Disuguaglianze di Boole e di Bonferroni
• Teorema della probabilità totale
• Reticolo booleano

Collegamenti esterni

• Template:Collegamenti esterni