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
|
A
|
{\displaystyle \left|A\right|}
A
{\displaystyle A}
A
1
,
A
2
,
⋯
,
A
n
{\displaystyle A_{1},A_{2},\cdots ,A_{n}}
|
⋃
i
=
1
n
A
i
|
=
∑
i
=
1
n
|
A
i
|
−
∑
1
≤
i
<
j
≤
n
|
A
i
∩
A
j
|
+
∑
1
≤
i
<
j
<
k
≤
n
|
A
i
∩
A
j
∩
A
k
|
−
⋯
(
−
1
)
n
−
1
|
A
1
∩
⋯
∩
A
n
|
=
{\displaystyle \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|=}
=
∑
i
=
1
n
(
−
1
)
i
+
1
∑
1
≤
j
1
<
.
.
.
<
j
i
≤
n
|
⋂
k
=
1
i
A
j
k
|
{\displaystyle =\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
{\displaystyle n=2}
|
A
∪
B
|
=
|
A
|
+
|
B
|
−
|
A
∩
B
|
{\displaystyle |A\cup B|=|A|+|B|-|A\cap B|}
Nel caso
n
=
3
{\displaystyle n=3}
|
A
∪
B
∪
C
|
=
|
A
|
+
|
B
|
+
|
C
|
−
|
A
∩
B
|
−
|
A
∩
C
|
−
|
B
∩
C
|
+
|
A
∩
B
∩
C
|
{\displaystyle |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
∪
B
∪
C
|
=
|
(
A
∪
B
)
∪
C
|
=
|
A
∪
B
|
+
|
C
|
−
|
(
A
∪
B
)
∩
C
|
{\displaystyle |A\cup B\cup C|=|(A\cup B)\cup C|=|A\cup B|+|C|-|(A\cup B)\cap C|}
=
|
A
|
+
|
B
|
−
|
A
∩
B
|
+
|
C
|
−
|
(
A
∩
C
)
∪
(
B
∩
C
)
|
{\displaystyle \,=\,|A|+|B|-|A\cap B|+|C|-|(A\cap C)\cup (B\cap C)|}
=
|
A
|
+
|
B
|
+
|
C
|
−
|
A
∩
B
|
−
(
|
A
∩
C
|
+
|
B
∩
C
|
−
|
(
A
∩
C
)
∩
(
B
∩
C
)
|
)
{\displaystyle =|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
∩
B
|
−
|
A
∩
C
|
−
|
B
∩
C
|
+
|
A
∩
B
∩
C
|
{\displaystyle =|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|}
Si dovrà dimostrare che ogni elemento dell'insieme
⋃
i
=
1
n
A
i
{\displaystyle \bigcup _{i=1}^{n}A_{i}}
x
∈
A
1
∩
A
2
∩
⋯
∩
A
k
{\displaystyle x\in A_{1}\cap A_{2}\cap \cdots \cap A_{k}}
x
∉
A
k
+
1
∩
⋯
∩
A
n
{\displaystyle x\notin A_{k+1}\cap \cdots \cap A_{n}}
x
{\displaystyle x}
k
{\displaystyle k}
Il termine
∑
i
=
1
n
|
A
i
|
{\displaystyle \sum _{i=1}^{n}\left|A_{i}\right|}
x
{\displaystyle x}
(
k
1
)
{\displaystyle {\binom {k}{1}}}
sommatoria , cioè
∑
1
≤
i
<
j
≤
n
|
A
i
∩
A
j
|
{\displaystyle \sum _{1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|}
x
{\displaystyle x}
(
k
2
)
{\displaystyle {\binom {k}{2}}}
Dunque l'elemento
x
{\displaystyle x}
∑
i
=
1
k
(
−
1
)
i
−
1
(
k
i
)
{\displaystyle \sum _{i=1}^{k}(-1)^{i-1}{\binom {k}{i}}}
Osserviamo che l'indice
i
{\displaystyle i}
k
{\displaystyle k}
i
=
k
+
1
{\displaystyle i=k+1}
k
+
1
{\displaystyle k+1}
A
i
{\displaystyle A_{i}}
x
{\displaystyle x}
Si può ora dimostrare facilmente, considerando lo sviluppo del Binomio di Newton , che la sommatoria in questione è uguale a
1
{\displaystyle 1}
1
−
∑
i
=
1
k
(
−
1
)
i
−
1
(
k
i
)
=
∑
i
=
0
k
(
−
1
)
i
(
k
i
)
=
(
1
−
1
)
k
=
0
◻
{\displaystyle 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 )
modifica
Abbiamo che
|
⋃
i
=
1
n
A
i
|
=
∑
k
=
1
n
(
−
1
)
k
+
1
∑
1
≤
i
1
<
⋯
<
i
k
≤
n
|
A
i
1
∩
A
i
2
∩
⋯
∩
A
i
k
|
{\displaystyle \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
{\displaystyle n=2}
n
=
1
{\displaystyle n=1}
|
A
1
|
=
|
A
1
|
{\displaystyle \left|A_{1}\right|=\left|A_{1}\right|}
|
A
1
∪
A
2
|
=
|
A
1
|
+
|
A
2
|
−
|
A
1
∩
A
2
|
{\displaystyle \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
{\displaystyle n}
n
+
1
{\displaystyle n+1}
⋃
i
=
1
n
+
1
A
i
=
(
⋃
i
=
1
n
A
i
)
∪
A
n
+
1
{\displaystyle \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
{\displaystyle n=2}
|
⋃
i
=
1
n
+
1
A
i
|
=
|
⋃
i
=
1
n
A
i
|
+
|
A
n
+
1
|
−
|
(
⋃
i
=
1
n
A
i
)
∩
A
n
+
1
|
{\displaystyle \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
∑
k
=
1
n
(
−
1
)
k
+
1
∑
1
≤
i
1
<
⋯
<
i
k
≤
n
|
A
i
1
∩
⋯
∩
A
i
k
|
+
|
A
n
+
1
|
−
∑
k
=
1
n
(
−
1
)
k
+
1
∑
1
≤
i
1
<
⋯
<
i
k
≤
n
|
A
i
1
∩
⋯
∩
A
i
k
∩
A
n
+
1
|
=
{\displaystyle \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|=}
=
∑
k
=
1
n
+
1
(
−
1
)
k
+
1
∑
1
≤
i
1
<
⋯
<
i
k
≤
n
+
1
|
A
i
1
∩
⋯
∩
A
i
k
|
{\displaystyle =\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 .
Collegamenti esterni
modifica
