Endliche Menge/Siebformel/Fakt/Beweis

Beweis

Wir beweisen die Aussage durch Induktion über $n$ , wobei der Fall $n = 1$ klar ist. Für $n = 2$ siehe Aufgabe. Es ist

\begin{matrix} # (⋃_{i = 1}^{n + 1} A_{i}) & = # ((⋃_{i = 1}^{n} A_{i}) \cup A_{n + 1}) \\ = # (⋃_{i = 1}^{n} A_{i}) + # (A_{n + 1}) - # ((⋃_{i = 1}^{n} A_{i}) \cap A_{n + 1}) \\ = \sum_{k = 1}^{n} (- 1)^{k + 1} (\sum_{J \subseteq {1, \dots, n}, # (J) = k} # (A_{J})) + # (A_{n + 1}) - # (⋃_{i = 1}^{n} (A_{i} \cap A_{n + 1})) \\ = \sum_{k = 1}^{n} (- 1)^{k + 1} (\sum_{J \subseteq {1, \dots, n}, # (J) = k} # (A_{J})) + # (A_{n + 1}) - \sum_{ℓ = 1}^{n} (- 1)^{ℓ + 1} (\sum_{L \subseteq {1, \dots, n}, # (L) = ℓ} # (A_{L} \cap A_{n + 1})) \\ = \sum_{k = 1}^{n + 1} (- 1)^{k + 1} (\sum_{J \subseteq {1, \dots, n, n + 1}, n + 1 \notin J, # (J) = k} # (A_{J})) + \sum_{k = 1}^{n + 1} (- 1)^{k + 1} (\sum_{J \subseteq {1, \dots, n, n + 1}, # (J) = k, n + 1 \in J} # (A_{J})) \\ = \sum_{k = 1}^{n + 1} (- 1)^{k + 1} (\sum_{J \subseteq {1, \dots, n, n + 1}, # (J) = k} # (A_{J})), \end{matrix}

wobei wir für die zweite Gleichung den Fall von zwei Teilmengen und für die dritte und die vierte Gleichung die Induktionsvoraussetzung verwendet haben. Für die fünfte Gleichung führen wir hinten die Indexverschiebung $k = ℓ + 1$ durch, und der mittlere Term wird in die rechte Summe integriert. Die sechste Gleichung ergibt sich von unten nach oben gelesen, wenn man die Teilmengen

J \subseteq {1, \dots, n, n + 1}

je nachdem aufspaltet, ob $n + 1$ dazu gehört oder nicht.

Zur bewiesenen Aussage