Es reicht zu zeigen, dass für beliebige endliche Mengen A und B gilt, dass ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣, denn dann folgt die zu beweisende Aussage unmittelbar über die Substitution B→(B∪C) und entsprechende Mengenumformungen.
Wir dürfen aufgrund der Endlichkeit annehmen, dass A={a1,...,an} und B={b1,...,bm} mit entsprechenden Mächtigkeiten ∣A∣=n und ∣B∣=m.
Weiter nehmen wir o.B.d.A. an, dass a1=b1,...,ak=bk für ein k≤min(n,m), also A∩B={a1,...,ak}={b1,...,bk} und insbesondere ∣A∩B∣=k.
Es folgt A∪B=(A∖(A∩B))∪B und offenbar sind die Mengen A∖(A∩B) und B disjunkt.
Damit gilt ∣A∪B∣=∣(A∖(A∩B))∪B∣=∣A∖(A∩B)∣+∣B∣.
Da A∖(A∩B)={ak+1,...,an} folgt offenbar ∣A∖(A∩B)∣=n−k=∣A∣−∣A∩B∣.
Entsprechend folgt schlussendlich ∣A∪B∣=∣A∣−∣A∩B∣+∣B∣=∣A∣+∣B∣−∣A∩B∣.