Beweisen Sie durch starke Induktion über die Mächtigkeit der Menge Y : Seien X und Y endliche disjunkte Mengen, dann ist |X ⊎ Y| = |X| + |Y|.
Hinweis: Y = (Y \ {y}) ⊎ {y} für y ∈ Y, Y ≠ ∅.
+3976 Ich nutze im Folgenden mal nur das "normale" Vereinigungs-Symbol - sämtliche Mengen, die vereinigt werden, sind aber disjunkt.
Der Induktionsanfang ist wie so oft relativ einfach:
Ist |Y| =0, so ist |X∪Y|=|X∪∅|=|X|=|X|+0=|X|+|Y|.
Sei nun |Y|=n. Wir nehmen nun an, dass die Aussage für alle natürlichen Zahlen kleiner n gilt (Nutzung wird mit * gekennzeichnet), und zeigen damit, dass die Aussage auch für n gilt:
|X∪Y|=|X∪(Y∖{y})∪{y}|=∗|X∪(Y∖{y})|+|{y}|=∗|X|+|Y∖{y}|+1=|X|+n−1+1=|X|+n
