Question

Kardinalität von Vereinigungen mit Induktion

Aufrufe: 1159 Aktiv: 13.10.2018 um 20:37

0

Die Aufgabe ist es diese Gleichung zu zeigen; #∪j=1nAj=∑J⊂{1,…,n}(-1)1+#J #∩j∈JAj\# \left( \bigcup _ { j = 1 } ^ { n } A _ { j } \right) = \sum _ { J \subset \{ 1 , \ldots , n \} } ( - 1 ) ^ { 1 + \# J } \; \# \left( \bigcap _ { j \in J } A _ { j } \right) Ich habe die Induktion gemacht, aber bei dem letzten Induktionsschritt komme ich nicht weiter (P ist die Potenzmenge) Hier ein Bsp: WhatsApp Image 2018-10-13 at 03.12.25.jpeg

WhatsApp Image 2018-10-13 at 03.12.25.jpeg

WhatsApp Image 2018-10-13 at 03.12.40.jpeg

Der Induktionsschritt (n →n+1): $\# \left( \bigcup _ { j = 1 } ^ { n +1 } A _ { j } \right) = \sum _ { J \subset \{ 1 , \ldots , n+1 \} } ( - 1 ) ^ { 1 + \# J } \; \# \left( \bigcap _ { j \in J } A _ { j } \right)$ #∪j=1n+1Aj=∑J⊂{1,…,n}(-1)1+#J #∩j∈JAj+∑J'∈P {1,…,n+1}\P{1,…,n} (-1)1+#J' #∩j∈J' Aj\# \left( \bigcup _ { j = 1 } ^ { n+1 } A _ { j } \right) = \sum _ { J \subset \{ 1 , \ldots , n \} } ( - 1 ) ^ { 1 + \# J } \; \# \left( \bigcap _ { j \in J } A _ { j } \right) + \sum _ { J\prime \in P \{ 1 , \ldots , n+1 \} \backslash P \{ 1 , \ldots , n \} } ( - 1 ) ^ { 1 + \# J\prime } \; \# \left( \bigcap _ { j \in J\prime } A _ { j } \right) #∪j=1n+1Aj=I.V.#∪j=1nAj +∑J' ∈P {1,…,n+1}\P {1,…,n} (-1)1+# J' #∩j∈J' Aj\# \left( \bigcup _ { j = 1 } ^ { n+1 } A _ { j } \right) \overset{\text{I.V.}}{\underset{\text{}}{=}} \# \left( \bigcup _ { j = 1 } ^ { n } A _ { j } \right) + \sum _ { J\prime \in P \{ 1 , \ldots , n+1 \} \backslash P \{ 1 , \ldots , n \} } ( - 1 ) ^ { 1 + \# J\prime } \; \# \left( \bigcap _ { j \in J\prime } A _ { j } \right) #∪j=1n+1Aj=#∪j=1nAj+#An+1\∪j=1nAj\# \left( \bigcup _ { j = 1 } ^ { n+1 } A _ { j } \right) = \# \left( \bigcup _ { j = 1 } ^ { n } A _ { j } \right) + \# \left( A _ { n + 1 } \backslash \left( \bigcup _ { j = 1 } ^ { n } A _ { j } \right) \right) Hat einer einen Vorschlag wie ich von der vorletzten Zeile in die letzten Zeile komme? bzw. wie das konkret aufschreibe ?

Teilen Diese Frage melden

gefragt 13.10.2018 um 20:37

e365benjamin
Student, Punkte: 13

Kommentar schreiben

2 Antworten

0

Sorry ich dachte Latex Funktioniert

Teilen Diese Antwort melden Link

geantwortet 13.10.2018 um 20:39

e365benjamin
Student, Punkte: 13

du musst den Code folgendermaßen implementieren:

[img alt_text='' description='']https://letsrockmathe.de/fragen/wp-content/uploads/sites/18/2018/10/Screenshot_61.png[/img]

Grüße Christian ─ christian_strack 14.10.2018 um 11:42

Kommentar schreiben

carl-friedrich-gauss · Accepted Answer · 2018-10-14T16:26:14Z

Hallo,

da hast du eine schöne Aufgabe bekommen. Dann fangen wir mal an:

Die Behauptung lautet :

$\left | \bigcup_{i=1}^{n}A_i \right |=\sum_{S\subseteq \left \{ 1,...,n \right \};S \neq \emptyset}^{ }\left ( -1 \right )^{\left | S \right |-1}\left | \bigcap_{j\in S}^{ }A_j \right |$

Der Induktionsanfang ist trivial. Kommen wir am besten gleich zu dem Induktionsschritt (mit der Voraussetzung, dass die obige Formel für $n-1$ gilt):

$\underline{n-1\rightarrow n:}$

$\left | \bigcup_{i=1}^{n}A_i \right |=\left | \left ( A_1\cup ...\cup A_{n-1} \right )\cup A_n \right |$

$=\left | A_1\cup...\cup A_{n-1} \right |+\left | A_n \right |-\left | \left ( A_1\cup...\cup A_{n-1} \right )\cap A_n \right |$

$=\left | A_1\cup...\cup A_{n-1} \right |+\left | A_n \right |-\left |\left ( A_1\cap A_n \right )\cup...\cup\left ( A_{n-1}\cap A_n \right ) \right |$

$=\sum_{S\subseteq \left \{ 1,...,n-1 \right \};S \neq \emptyset}^{ }\left ( -1 \right )^{\left | S \right |-1}\left | \bigcap_{j\in S}^{ }A_j \right |+\left | A_n \right |-\sum_{S\subseteq \left \{ 1,...,n-1 \right \};S \neq \emptyset}^{ }\left ( -1 \right )^{\left | S \right |-1}\left | \bigcap_{j\in S}^{ }A_j\cap A_n \right |$

$=\sum_{S\subseteq \left \{ 1,...,n-1 \right \};S \neq \emptyset}^{ }\left ( -1 \right )^{\left | S \right |-1}\left | \bigcap_{j\in S}^{ }A_j \right |+\left | A_n \right |-\sum_{S\subseteq \left \{ 1,...,n-1 \right \};S \neq \emptyset}^{ }\left ( -1 \right )^{\left | S \right |-1}\left |\left ( \bigcap_{j\in S}^{ }A_j \right )\cap A_n \right |$

$=\sum_{S\subseteq \left \{ 1,...,n-1 \right \};S \neq \emptyset}^{ }\left ( -1 \right )^{\left | S \right |-1}\left | \bigcap_{j\in S}^{ }A_j \right |+\left | A_n \right |-\sum_{S\subseteq \left \{ 1,...,n-1 \right \};S \neq \emptyset}^{ }\left ( -1 \right )^{\left | S \right |-1}\left |\bigcap_{j\in \left ( S\cup \left \{ n \right \} \right )}^{ }A_j \right |$

$=\sum_{S\subseteq \left \{ 1,...,n-1 \right \};S \neq \emptyset}^{ }\left ( -1 \right )^{\left | S \right |-1}\left | \bigcap_{j\in S}^{ }A_j \right |+
\sum_{S\subseteq \left \{ 1,...,n-1 \right \}}^{ }\left ( -1 \right )^{\left | S \right |}\left |\bigcap_{j\in \left ( S\cup \left \{ n \right \} \right )}^{ }A_j \right |$

$=\sum_{S\subseteq \left \{ 1,...,n-1 \right \};S \neq \emptyset}^{ }\left ( -1 \right )^{\left | S \right |-1}\left | \bigcap_{j\in S}^{ }A_j \right |+
\sum_{S\subseteq \left \{ 1,...,n \right \};n\in S}^{ }\left ( -1 \right )^{\left | S \right |-1}\left |\bigcap_{j\in S}^{ }A_j \right |$

$=\sum_{S\subseteq \left \{ 1,...,n \right \};S\neq \emptyset}^{ }\left ( -1 \right )^{\left | S \right |-1}\left |\bigcap_{j\in S}^{ }A_j \right |$

$QED$

Ich hoffe, ich habe mich jetzt nicht vertippt.

Gruß,

Gauß