Kardinalität von Vereinigungen mit Induktion


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.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 ?

 

gefragt vor 1 Jahr
e
e365benjamin,
Student, Punkte: 13
 
Kommentar schreiben Diese Frage melden
2 Antworten
1

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ß

geantwortet vor 1 Jahr
carl-friedrich-gauss,
Lehrer/Professor, Punkte: 1964
 
Kommentar schreiben Diese Antwort melden
0

Sorry ich dachte Latex Funktioniert

geantwortet vor 1 Jahr
e
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, verified kommentiert vor 1 Jahr
Kommentar schreiben Diese Antwort melden