vollständige Induktion < Induktion < Analysis < Oberstufe < Schule < Mathe < Vorhilfe
|
| Aufgabe | | Sei n [mm] \in \IN. [/mm] Zeigen Sie, dass die Potenzmenge [mm] \mathcal{P}(M) [/mm] einer n-elementigen Menge M Kardinalität [mm] 2^{n} [/mm] hat, dass also [mm] |\mathcal{P}(M)| [/mm] = [mm] 2^{n} [/mm] gilt. |
Hallo zusammen!
Ich habe diese Aufgabe im Rahmen einer LA Übung gestellt bekommen und der Tutor hat uns das irgendwie vorgerechnet und dann gemeint, dass bei solchen Aufgabenstellungen die vollständige Induktion immer ein hilfreiches Prinzip sei.
Nun, ich verstehe zwar die AUfgabenstellung und was [mm] |\mathcal{P}(M)| [/mm] = [mm] 2^{n} [/mm] bedeuten soll leuchtet mir auch ein. DIe Potenzmenge [mm] \mathcal{P} [/mm] steht ja für die Anzahl bzw. Menge aller Teilmengen einer Menge. Wenn ich jetzt also von n=1 ausgehe, (was dann mein INduktionsanfang wäre?), so kann ich mir ja überlegen, dass die Menge (nennen wir sie mal A) A = {1} die Potenzmenge 2 hat, denn A beinhaltet die leere Menge und die Menge {1}. FÜr [mm] 2^{1} [/mm] kommt 2 heraus, somit würde die AUssage stimmen.
Mein Problem liegt jetzt hier. Wie mache ich weiter? Um das für n oder n+1 zu zeigen bräuchte ich doch auf der linken Seite von [mm] |\mathcal{P}(M)| [/mm] = [mm] 2^{n} [/mm] irgendwie... etwas, in dem n auch vorkommt? Meine Frage ist nun im Grunde: Kann ich den Betrag der Potenzmenge von M, also [mm] |\mathcal{P}(M)|, [/mm] irgendwie so umschreiben, dass sich die vollständige Induktion auch darauf anwenden lässt?
Grüße,
HoagsObject
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:04 Sa 27.10.2012 | | Autor: | fred97 |
Schau mal hier:
http://www.gefilde.de/ashome/vorlesungen/arithalgebra/skript/kapitel03.pdf
FRED
|
|
|
| |
|
Oh wow, das ist ja noch um einiges komplizierter als ich eigentlich angenommen hatte! :) Aber vielen Dank für den Link, die ausführliche Erklärung war auf jeden Fall hilfreich!
Grüße, HoagsObject
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:13 Sa 27.10.2012 | | Autor: | leduart |
Hallo
M enthält n elemente nenn es [mm] M_n
[/mm]
Ind. Vors: [mm] K(P(M_n))=2^n
[/mm]
[mm] M_{n+1} [/mm] enthält ein element mehr als [mm] M_n
[/mm]
Behauptung: [mm] K(P(M_{n+1}=2^{n+1}
[/mm]
und jetz musst du mit dem einen Element mehr die "zusatzlichen" Teilmengen berechenen. wenn du die von n Elementen kennst.
Gruss leduart
|
|
|
|
