+0  
 
0
648
1
avatar

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\).

 30.11.2020
 #1
avatar+3976 
+1

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 \)

 30.11.2020

2 Benutzer online