Menge einer Menge vollständige Induktion

Neue Frage »

02.11.2010, 17:38	pivotvariable	Auf diesen Beitrag antworten »
Menge einer Menge vollständige Induktion Also wir haben heute folgende Aufgabe bekommen, bei der ich ehrlich gesagt bereits Schwierigkeiten habe, diese in eine deutsche Aussage umzuformen. und bei vollständiger Induktion in Bezug auf Mengen weiß ich auch noch keinerlei ansatz: Beweisen sie mit vollständiger Induktion unter der Annahme es seien $\begin{eqnarray} A_{i} ,i\in I:=\left\{ 1,...,n\right\} \end{eqnarray}$ Teilmengen einer endlichen Menge: z.Z. $\begin{eqnarray} \| \cap_{i\in I} A_{i} \| =\sum\limits_{leereMenge\neq J\subseteq I} \left(-1\right)^{\| J \|-1} \| U_{i\in J}A_{i} \| \end{eqnarray}$ Mich würde einmal eine deutsche Übersetzung interessieren und wie gehe ich soetwas mit vollständiger Induktion an??
02.11.2010, 17:57	pivotvariable	Auf diesen Beitrag antworten »
RE: Menge einer Menge vollständige Induktion Ich würde mich wirklich über jederlei Hilfe freuen weil ich habe keinerlei Ansatz....
02.11.2010, 18:31	René Gruber	Auf diesen Beitrag antworten »
Steht da wirklich links der Durchschnitt der Mengen, und rechts in der Summe jeweils Vereinigungen? Sieht etwas ungewohnt aus, denn bei der Siebformel ist es genau umgekehrt. Trotzdem dürfte die Gleichung richtig sein. Und falls du die Siebformel im Beweis verwenden darfst, dann wird dieser Beweis sehr kurz.
02.11.2010, 19:02	pivotvariable	Auf diesen Beitrag antworten »
Schaut zwar ähnlich aus aber wie soll ich von einer indexmenge auf die Wahrscheinlichkeit bitte kommen??
02.11.2010, 19:14	René Gruber	Auf diesen Beitrag antworten »
Wenn du schon nach Siebformel recherchierst, dann aber bitte gründlicher: Die gibt es in zwei Varianten: Einmal für Wahrscheinlichkeiten, dann aber auch für Mengenmächtigkeiten - bisweilen auch Inklusion-Exklusion-Formel genannt.
06.11.2010, 12:09	wirtschaftsmathe	Auf diesen Beitrag antworten »
Ich habe mich jetzt auch einmal durchgerungen diese Aufgabe versuchen zu lösen mit Hilfe der Tipps....allerdings weiß ich zum Beispiel nicht einmal wie der Induktionsanfagn auszusehen hat.......welches Element ist denn mein erste zum Einsetzen?
Anzeige

06.11.2010, 15:59	pivotvariable	Auf diesen Beitrag antworten »
Also ich habe mich jetzt einmal mit dem Prinzip der vollständigen Induktion auseinandergesetzt und stelle mich nun auch die Frage ob die Schnittmenge und Vereinigunsmenge falsch gesetzt worden sind oder ob diese Aufgabe auch so lösbar wäre... $\begin{eqnarray} \| \cap _{i\in I} A_{i}\|=\sum _ {leere Menge \neq J\subseteq I} \| \cup _{i\in J} A_{i} \| -\sum _{leereMenge\neq J\subseteq I} \| \cup _{i\in J} A_{i} \| \end{eqnarray}$ wobei der erste Minuend für J ungerade zählt und der zweite für J gerade aber ich habe z.B. keine Ahnung wenn ich 1 als den Induktionsanfang anschaue, was ich aus der Menge J verwenden soll??
07.11.2010, 00:14	_-Alex-_	Auf diesen Beitrag antworten »
Also ich muss ja auch die Aufgabe machen^^. Sind ja schon ein paar Threads mit den gleichen Aufgaben aufgetaucht. Also ich hab mir hierzu bisher folgendes überlegt ohne diese Siebformel: Allgemein besagt die Summe, dass ich immer die Mächtigkeit von Teilmengen betrachte, deren Index sich nach $\begin{eqnarray} \binom{n}{k} \end{eqnarray}$ ergibt. Also zunächst gilt k=1, dann k=2 und so weiter. So bekomme ich immer Vereinigungen von den Teilmengen, bei geradem k kommt jeweils noch ein (-) vor meine Mächtigkeitsklammer. Wenn ich jetzt einen neuen Index (n+1) habe, kommt zunächst ja auf jeden Fall mal die Mächtigkeit $\begin{eqnarray} \lvert A_{n+1} \rvert \end{eqnarray}$ hinzu. Zudem kommen noch für alle folgenden Paare an Teilmengen, die Fälle hinzu, bei denen ich die Teilmenge $\begin{eqnarray} \lvert A_{n+1} \rvert \end{eqnarray}$ beachten muss. Ich hab mir jetzt also die Gleichung zurechtsummiert, die $\begin{eqnarray} \sum_{leere Menge \neq J \subseteq I'} (-1)^{\lvert J \rvert -1} \lvert \bigcup_{i \in J} A_i \rvert \end{eqnarray}$ mit $\begin{eqnarray} I' = \lbrace 1,...,n+1 \rbrace \end{eqnarray}$ ersetzt, nämlich: $\begin{eqnarray} \sum_{leere Menge \neq J \subseteq I} (-1)^{\lvert J \rvert -1} \lvert \bigcup_{i \in J} A_i \rvert + \lvert A_{n+1} \rvert + \sum_{leere Menge \neq J \subseteq I} (-1)^{\lvert J \rvert} \lvert \bigcup_{i \in J} A_i \cup A_{n+1}\rvert \end{eqnarray}$ aber wieder mit $\begin{eqnarray} I = \lbrace 1,...,n \rbrace \end{eqnarray}$ Den Beweis wäre ich jetzt so angegangen, dass ich sage: $\begin{eqnarray} \lvert \bigcap_{i \in I'} A_i \rvert = \lvert \bigcap_{i \in I} A_i \cap A_{n+1} \rvert = \sum_{leere Menge \neq J \subseteq I} (-1)^{\lvert J \rvert -1} \lvert \bigcup_{i \in J} A_i \rvert + \lvert A_{n+1} \rvert + \sum_{leere Menge \neq J \subseteq I} (-1)^{\lvert J \rvert} \lvert \bigcup_{i \in J} A_i \cup A_{n+1}\rvert = \lvert A_{n+1} \rvert + \sum_{leere Menge \neq J \subseteq I} (-1)^{\lvert J \rvert -1} ( \lvert \bigcup_{i \in J} A_i \rvert - \lvert \bigcup_{i \in J} A_i \cup A_{n+1} \rvert ) = \sum_{leere Menge \neq J \subseteq I'} (-1)^{\lvert J \rvert -1} \lvert \bigcup_{i \in J} A_i \rvert \end{eqnarray}$ Ich weiß jetzt aber nicht ob das schon reicht. Könntet ihr da weiterhelfen? MfG
07.11.2010, 11:00	René Gruber	Auf diesen Beitrag antworten »
Ja, sieht soweit in Ordnung aus. Wobei es sicher nicht schaden kann, den letzten Umformungsschritt der Gleichungskette verbal etwas genauer zu erläutern, d.h. wieso man jetzt wirklich genau alle nichtleeren Teilmengen von $\begin{eqnarray} I' = I \cup \{n+1\} \end{eqnarray}$ erfasst hat und das mit dem Vorzeichen auch hinhaut. ------------------------------------------------------ Insgesamt entspricht das vom Aufbau genau dem Beweis der Siebformel (für Mengenmächtigkeiten). Darf man die Siebformel jedoch bereits verwenden, so kann man sich den Aufwand weitgehend sparen, indem man die Siebformel auf die Mengen $\begin{eqnarray} B_i := \Omega\setminus A_i \end{eqnarray}$ anwendet, dabei ist $\begin{eqnarray} \Omega \end{eqnarray}$ die laut Voraussetzung existente endliche "Obermenge".
07.11.2010, 15:12	_-Alex-_	Auf diesen Beitrag antworten »
Ja, aber ich möchte sie jetzt net direkt verwenden, da ich mir jetzt die Mühe gemacht habe und das alles auseinandergezogen und sonst was hat. Wäre schade um die Zeit . Das war auch mein Problem bisher, also dass ich nicht weiß ob ich am Ende da noch genauer umformen muss, was mir bisher nicht eingefallen ist. Ich finde nur, wenn man sich die Summen genau anschaut, kommt man einfach am Ende auf den Schluss, dass die Summen gleich sind. Ich könnte höchstens noch einen Satz hinschreiben, der das genauer erläutert, aber wie ich das formal noch genauer hinschreibe weiß ich leider nicht. Ich hoffe mal, dass das so jetzt auch schon geht.
07.11.2010, 15:16	René Gruber	Auf diesen Beitrag antworten »
Ich hab ja auch keine Einwände, könnte mir aber vorstellen, dass ein "pingeliger" Korrektor das doch genauer erläutert haben will: So mancher verwendet nämlich die Begründung "trivial" an Stellen, die er selbst gar nicht genau erklären kann. Kommt auf das Pokerface an, ob einem das abgekauft wird.
08.11.2010, 20:14	_-Alex-_	Auf diesen Beitrag antworten »
Also ich habe jetzt noch einen Satz dazugeschrieben, dass man erkennt, dass das stimmt, wenn man sich die Terme anschaut und welche eben fehlen, wenn ich meine Indexmenge um ein Element n+1 vergrößere. Vorsichtshalber - sozusagen doppelt gemoppelt - habe ich auch nochmal die Siebformel erwähnt. Aber ich hab es kürzer gefasst. Also gesagt: $\begin{eqnarray} \lvert X \cap B \rvert = \lvert X \rvert + \lvert B \rvert - \lvert X \cup B \rvert \end{eqnarray}$ Und gesagt, dass: $\begin{eqnarray} B=A_{n+1} und X= \bigcap_{i \in J} A_i = \sum_{leere Menge \neq J \subseteq I} (-1)^{\lvert J \rvert -1} (\bigcup_{i \in J} A_i) \end{eqnarray}$ Und dass aus $\begin{eqnarray} \lvert X \cup B \rvert dann \sum_{leere Menge \neq J \subseteq I} (-1)^{\lvert J \rvert} \lvert \bigcup_{i \in J} A_i \cup A_{n+1} \rvert \end{eqnarray}$ wird, da die Mächtigkeit von Vereinigungen mit gerade Anzahl an Teilmengen abgezogen werden müssen, was aus der Induktionsannahme (dass die Formel für I mit n Elementen) hervorgeht. Ich hoffe, dass diese zusätzliche Erklärung mehr besser erklärt als sie noch verwirrt, aber ich hab keine Lust, am Ende keine Punkte drauf zu bekommen, dafür steckt da zu viel Zeit drin

Neue Frage »

Antworten »

Menge einer Menge vollständige Induktion

Verwandte Themen