Endliche Menge/Siebformel/Fakt/Beweis2

Beweis

Beide Seiten der Siebformel verhalten sich additiv, wenn eine disjunkte Zerlegung der Grundmenge vorliegt. Deshalb genügt es, die Aussage für eine einelementige Menge zu zeigen (man fragt sich für jedes Element, wie oft es links und wie oft es rechts gezählt wird). Sei also  $G=\{x\}$.  Dann gibt es für die Teilmengen $A_i$ nur die Möglichkeiten  $A_i=\{x\}$  oder  $A_i=\mathrm{\varnothing }$.  Wir können annehmen, dass

$A_1=\dots =A_r=\{x\}$

und

$A_{r+1}=\dots =A_n=\mathrm{\varnothing }$

ist. Zu einer Teilmenge  $J\subseteq \{1,\dots ,n\}$  ist dann  $A_J=\{x\}$  einelementig genau dann, wenn  $J\subseteq \{1,\dots ,r\}$  ist, und sonst immer leer. Daher ist die rechte Seite gleich

$\begin{array}{cc}\sum _{k=1}^r(-1{)}^{k+1}\left(\sum _{J\subseteq \{1,\dots ,r\},\mathrm{\#}\left(J\right)=k}\mathrm{\#}\left(A_J\right)\right)& =\sum _{k=1}^r(-1{)}^{k+1}\sum _{J\subseteq \{1,\dots ,r\},\mathrm{\#}\left(J\right)=k}1\\ & =\sum _{k=1}^r(-1{)}^{k+1}(\genfrac{}{}{0ex}{}{r}{k}).\end{array}$

Dies ist bei  $r=0$  gleich $0$ und sonst nach Aufgabe gleich $1$, was mit der linken Seite übereinstimmt.

Zur bewiesenen Aussage