Beweisen Sie durch starke Induktion über die Mächtigkeit der Menge Y : Seien X und Y endliche disjunkte Mengen, dann ist |X \(\uplus\) Y| = |X| + |Y|.
Hinweis: Y = (Y \ {y}) \(\uplus\) {y} für y \(\in\) Y, Y \(\neq\) \(\emptyset\).
+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 \cup Y| = |X \cup \emptyset | = |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 \cup Y| = \\ | X \cup (Y \backslash \{y\}) \cup \{y\}| =^* \\ | X \cup (Y \backslash \{y\})|+|\{y\}| =^*\\ |X| + |Y \backslash \{y\}| + 1 = \\ |X| +n-1+1 = |X| +n \)
