Induktion < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:55 Mo 30.05.2005 | | Autor: | anja1010 |
Hallo!
Habe folgende Aufgabe zu machen:
Beweisen sie mittels vollständiger Induktion:
Die Potenzmenge für n-elementige Menge M enthält [mm] 2^{n} [/mm] Elemente. (Vergessen sie nicht, dass immer [mm] \emptyset \subset [/mm] M )
Mein Problem ist, dass ich nicht weiß, wie ich daraus einen Induktionsanfang ableiten bzw. wie ich die Induktion durchführen soll???
Lg Anja
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:08 Mo 30.05.2005 | | Autor: | Faenol |
Hi !
Der Induktionsanfang:
n=1: Sei [mm] M=\{a\} [/mm] dann ist [mm] P(A)=\{\{a\},\{\}\} [/mm] also die Anzahl [mm] =2=2^{1}
[/mm]
n=2: Sei [mm] M=\{a,b\} [/mm] dann ist [mm] P(A)=\{\{a,b\},\{a\},\{b\},\{\}\} [/mm] also die Anzahl [mm] =4=2^{2}
[/mm]
Kommst du jetzt auf den Induktionsschritt ?
Gruß
Faenôl
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:22 Mo 30.05.2005 | | Autor: | anja1010 |
Hallo Faenôl!!
Erstmal vielen Dank für deine Antwort!
Mein Problem ist, dass ich die vollständige Induktion bisher nur an, ich den sie einfachmal "richtige Beispiele", gemacht haben. Komm also nicht so richtig weiter...
Kannst du mir vielleicht weiter helfen??
Lg ANja
|
|
|
| |
|
Hallo!
Also zuerst nochmal zu dem Induktionsanfang:
Unsere Tutorin hat im ersten Semester immer bemängelt, dass wir bei 1 angefangen haben, obwohl man doch bei 0 anfangen könnte. Also würde ich sagen, dass wir hier auch bei 0 anfangen.
Also:
Induktion nach n:
IA: n=0
[mm] M=\{\}, [/mm] also |M|=0 [mm] \Rightarrow \cal{P}(M)=\{\{\}\} [/mm] (die Menge, die nur die leere Menge enthält!), also [mm] |\cal{P}(M)| [/mm] = [mm] 2^0=1 [/mm] - stimmt 
IV: wenn M n-elemtig ist, dann ist [mm] \cal{P}(M) [/mm] eben [mm] 2^n-elementig \forall [/mm] n
IS: [mm] n\to [/mm] n+1
Eigentlich ist das gar nicht so schwierig. Ich erkläre es zuerst mal kurz in Worten:
Du weißt ja, dass bei einer n-elementigen Menge die Potenzmenge [mm] 2^n [/mm] Elemente enthält. Nun hast du ein Element mehr, nämlich n+1 Elemente. Du musst dir also überlegen, welche Elemente in der Potenzmenge hinzukommen. Du weißt, was die Potenzmenge ist? Die Potenzmenge ist die Menge aller Teilmengen. Wenn nun ein Element zu deiner ursprünglichen Menge dazukommt, dann bekommst du in der Potenzmenge genau doppelt so viele Elemente, wie vorher. Nämlich zu jedem Element der Potenzmenge bekommst du noch das Element der Potenzmenge hinzu, dass zusätzlich aus dem neuen Element besteht. Oje - ich glaub', ich hab' mich schlecht ausgedrückt. Ich probier's mal mit einem Beispiel:
n=2
M={1,2}
[mm]\cal{P}(M)[/mm]=[mm] \{\{\},\{1\},\{2\},\{1,2\}\}[/mm]
[mm] |\cal{P}(M)| [/mm] = [mm] 2^2=4
[/mm]
neues Element: 0
also n=3
[mm] \Rightarrow M=\{0,1,2\}
[/mm]
[mm] \cal{P}(M) [/mm] = [mm] \{\{\},\{1\},\{2\},\{1,2\}\}\cup\{\{0\},\{0,1\},\{0,2\},\{0,1,2\}\}
[/mm]
Also ich habe bei jedem Element der Potenzmenge (die Elemente der Potenzmenge sind ja Mengen) noch das neue Element - die 0 - hinzugefügt.
[mm] |\cal{P}(M)| [/mm] = [mm] 4+4=8=2^3
[/mm]
So, und ich weiß gar nicht, wie man das wirklich als Induktion aufschreiben soll - eigentlich muss man das, was ich gerade erklärt habe, einfach allgemein formulieren. Also du sagst, deine Menge hat n Elemente und damit hat die Potenzmenge [mm] 2^n [/mm] Elemente. Wenn nun ein Element hinzukommt (also n+1), dann bildest du die Potenzmenge so, wie ich es gerade beschrieben habe. Und dann erhältst du automatisch [mm] 2^{n+1} [/mm] Elemente.
Viele Grüße
Bastiane
![[banane]](/images/smileys/banane.gif "[banane]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:02 Mo 30.05.2005 | | Autor: | anja1010 |
Hallo Bastiane!
Vielen Dank. Ich werds gleich mal so versuchen!
Lg Anja
|
|
|
| |
|
Sei n=0
=> [mm] M=\{\} [/mm] => [mm] P(M)=\{\{\}\}
[/mm]
Es gilt also #M=0 und #P(M) = 1 = [mm] 2^0
[/mm]
(#A bezeichnet die Mächtigkeit einer Menge A)
Sei Die Aussage für n bewiesen. Zeige sie für n+1.
Sei [mm] M_{n+1}=\{a_1, a_2, ... , a_{n+1}\} [/mm] und [mm] M_n=\{a_1, a_2, ... , a_n\}
[/mm]
Dann lassen sich die Teilmengen von [mm] M_{n+1} [/mm] in 2 Kategorien unterteilen. Jene, die das Element [mm] a_{n+1} [/mm] NICHT enthalten, und jene die das Element [mm] a_{n+1} [/mm] enthalten.
Enthält eine Teilmenge NICHT [mm] a_{n+1}, [/mm] so erhält man eine Teilmenge der zweiten Kategorie, indem man [mm] a_{n+1} [/mm] dazugibt. Umgekehrt kann man eine Teilmenge der zweiten Kategorie durch entfernen des Elements [mm] a_{n+1} [/mm] zu einer Teilmenge des ersten Typs machen.
Damit ist gezeigt, dass beide Kategorien gleich viele Mengen enthalten.
Nun wissen wir aber wie viele Teilmengen es in der ersten Kategorie gibt. Da sie alle das Element [mm] a_{n+1} [/mm] NICHT enthalten, sind das ALLE Teilmengen von [mm] M_n. [/mm] Nach Induktionsvoraussetzung hat [mm] P(M_n) [/mm] aber [mm] 2^n [/mm] Elemente.
Daher gilt # [mm] P(M_{n+1}) [/mm] = [mm] 2^n+2^n=2^{n+1}
[/mm]
Damit ist die Behauptung bewiesen.
|
|
|
|
