Principio di inclusione ed esclusione

Il termine principio di inclusione ed esclusione viene usato per denotare una formula che permette di esprimere la cardinalità di un insieme individuato come unione di insiemi finiti mediante le cardinalità di intersezioni di 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-1}\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|\cup\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

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica