Principio di inclusione-esclusione

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\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|+\sum _{1\leq i<j<k\leq n}\left|A_{i}\cap A_{j}\cap A_{k}\right|-\ \cdots \ (-1)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|=$

$=\sum _{i=1}^{n}\left(-1\right)^{i+1}\sum _{1\leq j_{1}<...<j_{i}\leq 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|-\left(|A\cap C|+|B\cap C|-|(A\cap C)\cap (B\cap C)|\right)$

$=|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 ${\binom {k}{1}}$ volte, mentre il secondo termine dello sviluppo della sommatoria, cioè $\sum _{1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|$ conta $x$ esattamente ${\binom {k}{2}}$ volte, ecc.

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

$\sum _{i=1}^{k}(-1)^{i-1}{\binom {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}{\binom {k}{i}}=\sum _{i=0}^{k}(-1)^{i}{\binom {k}{i}}=(1-1)^{k}=0\qquad \Box$

Dimostrazione II (induzione su n)

Abbiamo che

$\left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{k=1}^{n}(-1)^{k+1}\sum _{1\leq i_{1}<\cdots <i_{k}\leq n}\left|A_{i_{1}}\cap A_{i_{2}}\cap \cdots \cap A_{i_{k}}\right|$

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:

$\left|A_{1}\cup A_{2}\right|=\left|A_{1}\right|+\left|A_{2}\right|-\left|A_{1}\cap A_{2}\right|$

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|\left(\bigcup _{i=1}^{n}A_{i}\right)\cap A_{n+1}\right|$

Ovvero

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

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

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

• (EN) principle of inclusion and exclusion, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Principio di inclusione-esclusione, su MathWorld, Wolfram Research.