Vollständige Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:24 Di 27.10.2009 | | Autor: | xtraxtra |
| Aufgabe | | Es seien [mm] A_i,i\inI_n:=\{1,...,n\}, [/mm] Teilmengen einer endlicher Menge. Zeigen Sie mit vollständiger Induktion [mm] |\bigcap_{i \in I_n}A_i|=\summe_{\emptyset\not=J \subset I_n}(-1)^{|J|-1}|\bigcup_{i \in J}A_i|. [/mm] |
Prinzipiell hab ich glaube ich Induktionsbeweise verstanden.
Allerdings komm ich hier überhaupt nicht klar.
Ich kann die Gleichung einfach nicht lesen.
Und wo kommt J her? Ich weiß dass es eine Menge sein soll, aber was ist in dieser Menge drin?
Ich versteh einfach nicht, wie man soetwas am besten angeht.
Wäre cool wenn mir da jemand etwas auf die Sprünge hilft.
(Ich möchte bitte keine komplette Lösung. Da ichs gerne selbst verstehen und nicht nur Abschreiben möchte.)
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:54 Di 27.10.2009 | | Autor: | piet.t |
Hallo,
die Gleichung sieht wirklich zunächst etwas erschreckend aus, aber vielleicht macht man sich das alles erst mal an einem einfachen Beispiel klar.
Betrachten wir einfach mal drei Mengen [mm] $A_1, A_2, A_3$. [/mm] Dann ist also [mm] $I_n [/mm] = [mm] \{1,2,3\}$ [/mm] und die linke Seite lautet einfach [mm] $|A_1 \cap A_2 \cap A_3|$, [/mm] also die Mächtigkeit der Schnittmenge.
Jetzt aber zur rechten Seite. Summiert wird über [mm] $\emptyset \neq [/mm] J [mm] \subset I_n$, [/mm] wir betrachten also alle Teilmengen $J$ von [mm] $I_n$, [/mm] die nicht leer sind. In unserem Beispiel gibt es da 7 Stück: [mm] $\{1\}, \{2\}, \{3\}, \{1,2\},\{2,3\}, \{1,3\}, \{1,2,3\}$.
[/mm]
Für jede dieser Teilmengen wird ein Summand gebildet; im Beipspiel sieht die rechte Seite dann also ausgeschrieben so aus:
[mm] $(-1)^0 |A_1| [/mm] + [mm] (-1)^0 |A_2| [/mm] + [mm] (-1)^0 |A_3| [/mm] + [mm] (-1)^1 |A_1\cup A_2| [/mm] + [mm] (-1)^1 |A_2\cup A_3| [/mm] + [mm] (-1)^1 |A_1\cup A_3| [/mm] + [mm] (-1)^2 |A_1\cup A_2 \cup A_3|$.
[/mm]
Die Induktion läuft über die Anzahl der beteiligten Mengen und um das Prinzip der Formel zu verstehen schau dir einfach mal den Übergang von zwei auf drei beteiligte Mengen an. Wenn du das durchschaut hast ist die größte Schwierigkeit der Aufgabe, das ganze sauber aufzuschreiben...
Gruß
piet
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:37 Di 27.10.2009 | | Autor: | xtraxtra |
Vielen Dank erstmal ich habe es denk ich soweit verstanden.
Es ist also so, das erstmal die Mächtigkeit aller einzelnen Teilmengen addiert wird.
Alle Elemente die jetzt in 2 Mengen enthalten sind werden dann abgezogen.
Jedoch werden alle Elemente, die in 3 Mengen enthalten sind doppelt abgezogen, sodass diese wieder dazugezählt werden ...
D.h. also, dass die Anzahl der Elemente die in x Mengen vorkommen, wobei x eine ungerade Zahl ist werden addiert und die Anzahl der Elemente, die in y Mengen vorkommen, wobei y eine gerade Zahl ist, werden abgezogen.
Soweit ist mir das klar.
Aber wie mache an dieser stelle weiter. Weil ich weiß ja nicht ob n gerade oder ungerade ist ...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:02 Mi 28.10.2009 | | Autor: | felixf |
Hallo!
> Vielen Dank erstmal ich habe es denk ich soweit
> verstanden.
> Es ist also so, das erstmal die Mächtigkeit aller
> einzelnen Teilmengen addiert wird.
> Alle Elemente die jetzt in 2 Mengen enthalten sind werden
> dann abgezogen.
> Jedoch werden alle Elemente, die in 3 Mengen enthalten sind
> doppelt abgezogen, sodass diese wieder dazugezählt werden
> ...
> D.h. also, dass die Anzahl der Elemente die in x Mengen
> vorkommen, wobei x eine ungerade Zahl ist werden addiert
> und die Anzahl der Elemente, die in y Mengen vorkommen,
> wobei y eine gerade Zahl ist, werden abgezogen.
> Soweit ist mir das klar.
> Aber wie mache an dieser stelle weiter. Weil ich weiß ja
> nicht ob n gerade oder ungerade ist ...
Du machst hier einen Fehler: du versuchst es wieder direkt zu beweisen.
Vergiss dies mal.
Fuer $n = 2$ hast du ja die einfache Formel [mm] $|A_1 \cap A_2| [/mm] = [mm] |A_1| [/mm] + [mm] |A_2| [/mm] - [mm] |A_1 \cup A_2|$.
[/mm]
Jetzt willst du [mm] $|A_1 \cap A_2 \cap A_3|$ [/mm] ausrechnen. Dazu ist ja [mm] $|A_1 \cap A_2 \cap A_3| [/mm] = [mm] |(A_1 \cap A_2) \cap A_3| [/mm] = [mm] |A_1 \cap A_2| [/mm] + [mm] |A_3| [/mm] - [mm] |(A_1 \cap A_2) \cup A_3| [/mm] = [mm] |A_1 \cap A_2| [/mm] + [mm] |A_3| [/mm] - [mm] |(A_1 \cup A_3) \cap (A_2 \cup A_3)|$.
[/mm]
Wenn du jetzt die (zukuenftige) "Induktionsvoraussetzung" (fuer $n = 2$) auf [mm] $|A_1 \cap A_2|$ [/mm] und [mm] $|(A_1 \cup A_3) \cap (A_2 \cup A_3)|$ [/mm] anwendest, bekommst du
[mm] $|A_1 \cap A_2| [/mm] = [mm] |A_1| [/mm] + [mm] |A_2| [/mm] - [mm] |A_1 \cap A_2|$
[/mm]
und
[mm] $|(A_1 \cup A_3) \cap (A_2 \cup A_3)| [/mm] = [mm] |A_1 \cup A_3| [/mm] + [mm] |A_2 \cup A_3| [/mm] - [mm] |A_1 \cup A_2 \cup A_3|$.
[/mm]
Zusammengesetzt:
[mm] $|A_1 \cap A_2 \cap A_3| [/mm] = [mm] [|A_1| [/mm] + [mm] |A_2| [/mm] - [mm] |A_1 \cap A_2|] [/mm] + [mm] |A_3| [/mm] - [mm] [|A_1 \cup A_3| [/mm] + [mm] |A_2 \cup A_3| [/mm] - [mm] |A_1 \cup A_2 \cup A_3|]$
[/mm]
Wenn du das umsortierst, siehst du, dass es das ist was du haben willst.
Jetzt versuch mal ganz allgemein den Fall fuer ein beliebiges $n > 2$ mit der Induktionsvoraussetzung fuer $n - 1$ und $n = 2$ zu beweisen. Du wirst da etwas mit Summen rumhantieren muessen.
(Wenn du dir die zu beweisende Gleichung anschaust: auf der rechten Seite unterteilst du die Summe ueber alle Teilmengen [mm] $\emptyset [/mm] = J [mm] \subset I_{n+1}$ [/mm] in die Teilmengen $J$ mit $n + 1 [mm] \in [/mm] J$ und die mit $n + 1 [mm] \not\in [/mm] J$.)
LG Felix
|
|
|
|
