Vollständige Induktion(Beweis) < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:00 Fr 02.01.2009 | | Autor: | Kevinus |
| Aufgabe 1 | Beweisen Sie durch vollständige Induktion:
a) [mm] A_{1} \cap A_{2} \cap [/mm] . . . [mm] \cap A_{n} [/mm] = [mm] A_{1} [/mm] \ [mm] [(A_{1} [/mm] \ [mm] A_{2}) \cup (A_{1} [/mm] \ [mm] A_{3}) \cup [/mm] . . . [mm] \cup (A_{1} [/mm] \ [mm] A_{n})]
[/mm]
|
| Aufgabe 2 | | b) [mm] (A_{1} [/mm] \ [mm] B_{1}) \cap (A_{2} [/mm] \ [mm] B_{2}) \cap [/mm] . . . [mm] \cap (A_{n} [/mm] \ [mm] B_{n}) [/mm] = [mm] (A_{1} \cap A_{2} \cap [/mm] . . . [mm] \cap A_{n}) [/mm] \ [mm] (B_{1} \cup B_{2} \cup [/mm] . . . [mm] \cup B_{n}) [/mm] |
Leider habe ich keinen Lösungsansatz. Das Prinzip bzw. Verfahren einer vollständigen Induktion ist mir zwar bekannt, trotzdem kann ich es irgendwie nicht auf die Aufgabe übertragen.
Den Induktionsanfang bei a) würde ich vielleicht für n=1 machen. Würde dann [mm] A_{1}=A_{1}. [/mm] So und wie würde das dann mit n+1 funktionieren? Bzw. weiß ich gar nicht wie ich das korrekt aufschreiben soll. Also inwiefern benutzt man das Summenzeichen [mm] \summe_{i=1}^{n}?
[/mm]
Würde mich sehr über ein paar Tipps freuen.
MfG
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:46 Fr 02.01.2009 | | Autor: | uliweil |
Hallo Kevinus,
hier zunächst ein Hinweis zur Schreibweise, damit kannst Du dann ja vielleicht nochmal selber ansetzen:
Man benutzt nicht das Summenzeichen [mm] \summe_{i=1}^{n} [/mm] oder das Produktzeichen [mm] \produkt_{i=1}^{n}, [/mm] sondern die ja ebenfalls in den Eingabehilfen vorkommenden Zeichen für den n-fachen Durchschnitt und die n-fache Vereinigung. Damit würde die erste Behauptung so aussehen:
[mm] \bigcap_{i=1}^{n}A_{i} [/mm] = [mm] A_{1} \backslash \bigcup_{i=2}^{n}(A_{1} \backslash A_{i})
[/mm]
Dies wäre dann ja auch schon die Induktionsannahme. Jetzt mal die Induktionsbehauptung formulieren und unter Benutzung der Ind-Voraussetzung umformen.
Die Definition der/des n-fachen Vereinigung / Durchschnittes erfolgt übrigens wie beim Summen- und Produktzeichen (über vollständige Induktion).
Gruß
Uli
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:21 Sa 03.01.2009 | | Autor: | Kevinus |
Ok danke dir Uli. Das hat mir schon gut geholfen.
Ich habe es versucht mal umzusetzen. Hier meine Lösung:
Induktionsvorraussetzung:
[mm] \bigcap_{i=1}^{n}A_{i} [/mm] = [mm] A_{1} \backslash \bigcup_{i=2}^{n}(A_{1} \backslash A_{i}) [/mm]
1. Induktionsbehauptung: für $ [mm] \bigcap_{i=1}^{n}A_{i} [/mm] $
[mm] \bigcap_{i=1}^{n}A_{i} [/mm] = [mm] \bigcap_{i=1}^{n}A_{i} [/mm] + [mm] \bigcap_{i=1}^{n+1}A_{i}
[/mm]
Wegen Induktionsvorraussetzung gilt also:
[mm] \bigcap_{i=1}^{n}A_{i} [/mm] = [mm] A_{1} \backslash \bigcup_{i=2}^{n}(A_{1} \backslash A_{i}) [/mm] + [mm] \bigcap_{i=1}^{n+1}A_{i}
[/mm]
2. Induktionsbehauptung: für [mm] A_{1} \backslash \bigcup_{i=2}^{n}(A_{1} \backslash A_{i})
[/mm]
[mm] A_{1} \backslash \bigcup_{i=2}^{n}(A_{1} \backslash A_{i}) [/mm] = [mm] A_{1} \backslash \bigcup_{i=2}^{n}(A_{1} \backslash A_{i}) [/mm] + [mm] A_{1} \backslash \bigcup_{i=2}^{n+1}(A_{1} \backslash A_{i})
[/mm]
Wegen Induktionsvorraussetzung gilt also:
[mm] A_{1} \backslash \bigcup_{i=2}^{n}(A_{1} \backslash A_{i}) [/mm] = [mm] \bigcap_{i=1}^{n}A_{i} [/mm] + [mm] A_{1} \backslash \bigcup_{i=2}^{n+1}(A_{1} \backslash A_{i})
[/mm]
Daher kann ich ich die beiden Behauptungen zusammenfassen zu:
[mm] A_{1} \backslash \bigcup_{i=2}^{n}(A_{1} \backslash A_{i}) [/mm] + [mm] \bigcap_{i=1}^{n+1}A_{i} [/mm] = [mm] \bigcap_{i=1}^{n}A_{i} [/mm] + [mm] A_{1} \backslash \bigcup_{i=2}^{n+1}(A_{1} \backslash A_{i})
[/mm]
Und das würde dann 1 = 1 ergeben. Wäre das ein korrekter Beweis?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:03 Sa 03.01.2009 | | Autor: | uliweil |
Hallo Kevinus,
zunächst solltest Du die Induktionsbehauptung einmal komplett hinschreiben bevor Du die beiden Seiten betrachtest:
Ind-Beh.: [mm] \bigcap_{i=1}^{n+1}A_{i} [/mm] = A1 [mm] \backslash \bigcup_{i=2}^{n+1}(A_{1} \backslash A_{i}),
[/mm]
d.h. man ersetzt zunächst nur n durch n+1.
Jetzt kann man auf der linken bzw. rechten Seite umformen:
linke Seite: [mm] \bigcap_{i=1}^{n+1}A_{i} [/mm] = [mm] (\bigcap_{i=1}^{n}A_{i}) \cap A_{n+1} [/mm] hier spaltet man aus dem "großen" Durchschnitt, der bis n+1 geht, das letzte Glied [mm] A_{n+1} [/mm] ab. Du siehst, ein + - Zeichen gibt es nicht, sondern man muss schon weiter mit [mm] \cap [/mm] arbeiten. Hier hilft es, sich vorzustellen, wie das mit "Pünktchen" geschrieben aussieht (so wie in der Aufgabenstellung).
rechte Seite: A1 [mm] \backslash \bigcup_{i=2}^{n+1}(A_{1} \backslash A_{i}) [/mm] =
A1 [mm] \backslash [/mm] [( [mm] \bigcup_{i=2}^{n}(A_{1} \backslash A_{i})) \cup (A_{1} \backslash A_{n+1})].
[/mm]
Wo jetzt weiter umformen? Auf der rechten Seite weitermachen, denn die Struktur ist ja X [mm] \backslash [/mm] [Y [mm] \cup [/mm] Z] und dafür kannt man ja eine Regel zur Umformung, oder links, indem man die Induktionsvoraussetzung einsetzt? Mein Tipp ist rechts unter Verwendung des Distributivgesetzes für [mm] \backslash [/mm] und [mm] \cup.
[/mm]
Gruß
Uli
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:09 So 04.01.2009 | | Autor: | Kevinus |
| Aufgabe | | Würde die Lösung so jetzt stimmen? |
Behauptung:
[mm] A_{1} \backslash \bigcup_{i=2}^{n+1}(A_{1} \backslash A_{i}) =A_{1} \backslash [(\bigcup_{i=2}^{n}(A_{1} \backslash A_{i})) \cup (A_{1} \backslash A_{n+1})]
[/mm]
Nach Distributivgesetzanwendung:
[mm] A_{1} \backslash \bigcup_{i=2}^{n+1}(A_{1} \backslash A_{i}) [/mm] = [mm] A_{1}\backslash( \bigcup_{i=2}^{n}(A_{1} \backslash A_{i}))\cap A_{1}\backslash(A_{1} \backslash A_{n+1})
[/mm]
Einsetzen der Induktionsvorraussetzung: [mm] \bigcap_{i=1}^{n}A_{i} [/mm] = [mm] A_{1} \backslash \bigcup_{i=2}^{n}(A_{1} \backslash A_{i})
[/mm]
[mm] A_{1} \backslash \bigcup_{i=2}^{n+1}(A_{1} \backslash A_{i}) [/mm] = [mm] \bigcap_{i=1}^{n}A_{i} \cap [A_{1}\backslash(A_{1} \backslash A_{n+1})]
[/mm]
Vereinfachen von [mm] [A_{1}\backslash(A_{1} \backslash A_{n+1})] [/mm] :
[mm] A_{1} \backslash \bigcup_{i=2}^{n+1}(A_{1} \backslash A_{i}) [/mm] = [mm] \bigcap_{i=1}^{n}A_{i} \cap A_{1} \cap A_{n+1}
[/mm]
So und nun hab ich ja nur noch das [mm] A_{1} [/mm] zuviel. Da das aber schon in [mm] \bigcap_{i=1}^{n}A_{i} [/mm] enthalten ist bzw. Durchschnitt davon kann man ja eigentlich [mm] A_{1} [/mm] ganz einfach weglassen.
Normal müsste ja [mm] A_{1} \cap A_{2} [/mm] = [mm] A_{1} \cap A_{2} \cap A_{1}
[/mm]
So entsteht:
[mm] A_{1} \backslash \bigcup_{i=2}^{n+1}(A_{1} \backslash A_{i}) [/mm] = [mm] \bigcap_{i=1}^{n}A_{i} \cap A_{n+1}
[/mm]
Und [mm] \bigcap_{i=1}^{n}A_{i} \cap A_{n+1} [/mm] = [mm] \bigcap_{i=1}^{n+1}A_{i} [/mm]
Damit wäre die Behauptung
[mm] \bigcap_{i=1}^{n+1}A_{i} [/mm] = [mm] A_{1} \backslash \bigcup_{i=2}^{n+1}(A_{1} \backslash A_{i}) [/mm] bewiesen.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:22 So 04.01.2009 | | Autor: | uliweil |
Hallo Kevenius,
sieht gut aus; so habe ich mir das vorgestellt.
Gruß
Uli
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:02 So 04.01.2009 | | Autor: | Kevinus |
Danke schön für die Hilfe und die Geduld. :)
|
|
|
|
