|M| + |N| = |M ∪ N| + |M ∩ N|
Wie wäre es mit vollständiger Induktion über a = |M ∩ N| .
Für a=0 sind M und N elementfremd, also steht für jedes
x ∈ M ∪ N eindeutig fest, ob es in M oder in N ist, und da beide
Mengen endlich sind ist |M| + |N| = |M ∪ N|.
Gilt nun die Formel für alle endlichen Mengen mit einem
Durchschnitt von a Elementen, dann wäre zu zeigen,
dass es auch für alle endlichen Mengen mit einem
Durchschnitt von a+1 Elementen gilt.
Da dann der Durchschnitt nicht leer ist, kann man ein
Element x ∈ M ∩ N. Für dieses gilt nach Def. des Durchschnitts
x ∈ M und x ∈ N. Betrachte nun M\{x} und N\{x}
Das sind auch endliche Mengen und ihr Durchschnitt
ist (M ∩ N) \{x} , hat also a Elemente. Somit gilt
|M\{x}| + |N\{x}| = |M\{x} ∪ N\{x}| + |(M ∩ N) \{x}| #
Da x sowohl in M als auch in N ist, gilt
M\{x} ∪ N\{x} = ( M ∪ N) \{x} und damit |M\{x} ∪ N\{x}| = | M ∪ N| -1
Entsprechendes gilt für |M\{x}| und |N\{x}|
Bei # eingesetzt hat man dann
|M|-1 + |N|-1 = |M∪ N| -1 + |(M ∩ N)| - 1
<=> |M| + |N| = |M ∪ N| + |M ∩ N| q.e.d.
