Endliche Menge/Siebformel/Fakt/Beweis2

Aus Wikiversity
Zur Navigation springen Zur Suche springen
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 . Dann gibt es für die Teilmengen nur die Möglichkeiten oder . Wir können annehmen, dass

und

ist. Zu einer Teilmenge ist dann einelementig genau dann, wenn ist, und sonst immer leer. Daher ist die rechte Seite gleich

Dies ist bei gleich und sonst nach Aufgabe gleich , was mit der linken Seite übereinstimmt.