Die Siebformel berechnet die Anzahl in einer Vereinigung von Mengen, wenn die einzelnen Anzahlen der Mengen und ihrer Durchschnitte bekannt sind. Im einfachsten Fall, bei
-
ist
-
Um die Elemente, die sowohl in als auch in sind, nicht doppelt zu zählen, muss man deren Anzahl abziehen.
Bei drei Mengen
-
ist
-
Es sei eine Menge und es seien
, ,
endliche Teilmengen.
Für eine Teilmenge
sei
-
Dann ist
-
Wir beweisen die Aussage durch Induktion über , wobei der Fall
klar ist. Für
siehe
Aufgabe.
Es ist
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
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
-
je nachdem aufspaltet, ob dazu gehört oder nicht.
Man spricht auch vom Prinzip der Inklusion und Exklusion. Wir geben noch einen zweiten Beweis für die vorstehende Aussage.
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.