matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenUni-AnalysisInduktion
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
Forum "Uni-Analysis" - Induktion
Induktion < Analysis < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Analysis"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Induktion: Frage
Status: (Frage) beantwortet Status 
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.

        
Bezug
Induktion: Hilfe zum Induktionsanfang
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
                
Bezug
Induktion: Rückfrage
Status: (Frage) beantwortet Status 
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

Bezug
                        
Bezug
Induktion: Antwort
Status: (Antwort) fertig Status 
Datum: 22:56 Mo 30.05.2005
Autor: Bastiane

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]

Bezug
                                
Bezug
Induktion: Danke
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 23:02 Mo 30.05.2005
Autor: anja1010

Hallo Bastiane!

Vielen Dank. Ich werds gleich mal so versuchen!

Lg Anja

Bezug
        
Bezug
Induktion: vollständiger Bewis
Status: (Antwort) fertig Status 
Datum: 01:13 Di 31.05.2005
Autor: holy_diver_80

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.

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Analysis"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]