1. Semester Mathematik < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 05:07 Do 23.10.2014 | | Autor: | unfaehik |
| Aufgabe | | Zeigen Sie mit Hilfe des Prinzips der vollständigen Induktion: Für eine n-elementige Menge X gilt [mm] |P(X)|=2^n. [/mm] |
Zu 3: Mein Anfang würde so aussehen: n=0
|P(X)|=1 weil da nur die leere Menge ist. [mm] 2^n=1
[/mm]
dann
n→n+1
Ab hier steck ich fest. Ich weiß warum [mm] 2^n [/mm] richtig ist, allerdings kann ich nicht zeigen wieso.
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
http://www.onlinemathe.de/forum/1-Semster-Mathematik
und
http://www.matheboard.de/thread.php?threadid=547365
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 05:19 Do 23.10.2014 | | Autor: | Fulla |
Hallo unfaehik!
> Zeigen Sie mit Hilfe des Prinzips der vollständigen
> Induktion: Für eine n-elementige Menge X gilt [mm]|P(X)|=2^n.[/mm]
> Zu 3: Mein Anfang würde so aussehen: n=0
> |P(X)|=1 weil da nur die leere Menge ist. [mm]2^n=1[/mm]
> dann
> n→n+1
> Ab hier steck ich fest. Ich weiß warum [mm]2^n[/mm] richtig ist,
> allerdings kann ich nicht zeigen wieso.
Zunächstmal solltest du die Induktionsvoraussetzung aufschreiben. (Sei die Behauptung bereits für ein n bewiesen... Also dürfen wir verwenden, dass [mm]|X|=n\quad |P(X)|=2^n[/mm])
Versuche zu beschreiben, wie sich die Mächtigkeit von $P(X)$ ändert, wenn X ein Element mehr bekommt.
Lieben Gruß,
Fulla
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:52 Do 23.10.2014 | | Autor: | unfaehik |
Soo, das würde ich dann so beantworten.
|X| = n
|P(X)| = [mm] 2^n
[/mm]
Wir setzten n = 0
|X| = 0
|P(X)| = 1 wegen der leeren Menge.
[mm] 2^0 [/mm] = 1
Das heißt wenn wir |X| = n+1 setzen dann ist |P(X)| = 2^(n+1). Dabei gibt es n+1 Element mehr bei der Menge X:
X = { [mm] e_n_+_1 [/mm] }
usw.
Jedes Element wird aufgeschrieben dann werden alle Elemente miteinander kombiniert. So kommt das [mm] 2^n [/mm] zustande.
Wäre es so richtig beantwortet ?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:58 Do 23.10.2014 | | Autor: | sissile |
Hallo unfaehik,
Der Induktionanfang passt.
Die Induktionsvoraussetzung ist: Für |X|=n ist [mm] |P(X)|=2^n
[/mm]
In Worten:Wenn X genau n Elemente hat, dann hat die Potenzmenge [mm] 2^n [/mm] Elemente.
Im Induktionsschritt musst du von n-> n+1 kommen, also was ist zuzeigen?
ZZ.: Für |X|=n+1 ist [mm] |P(X)|=2^{n+1}
[/mm]
Unsere Menge X hat nun n+1 Elemente, also ein Element mehr als in der Induktionsvoraussetzung. Du teilst die Potenzmenge von X auf in die Menge der Potenzmengen die das (n+1)-te Element enthalten, und in jene die das (n+1)-te Element nicht enthalten.
Ich nenne, das (n+1)-te Element [mm] s_{n+1}
[/mm]
[mm] |P(X)|=|\{S:S\subset X \wedge s_{n+1} \in S\} \cup \{S:S\subset X \wedge s_{n+1} \not\in S\}|
[/mm]
Nun "zählst" du jeweils die Anzahl der Mengen, wobei dir die Induktionsvoraussetzung hilft.
Liebe Grüße,
sissi
|
|
|
|
