www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

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:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Uni-Analysis-Induktion" - Mengen und Teilmengen
Mengen und Teilmengen < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Analysis-Induktion"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Mengen und Teilmengen: Beweis
Status: (Frage) beantwortet Status 
Datum: 17:59 Di 18.03.2008
Autor: Pacapear

Aufgabe
Es sei [mm] n\in\IN. [/mm] Man zeige, dass eine n-elementige Menge [mm] 2^n [/mm] Teilmengen besitzt.

Hallo.

Ich habe mal wieder eine Frage zu einer Lösung, die ich nicht verstehe [knirsch]



Lösung

Beweis durch vollständige Induktion nach n.

Induktionsanfang
n=1
Menge M mit 1 Element besitzt [mm] 2^1 [/mm] Teilmengen, nämlich M und [mm] \emptyset. [/mm]

Induktionsschritt
n [mm] \to [/mm] n+1
Sei M eine Menge mit n+1 Elementen.
Halte 1. Element fest.
Nach Induktionsvorgabe können wir [mm] 2^n [/mm] Teilmengen aus den übrigen n Elementen bilden.
Jede Teilmenge von M entsteht aus einer dieser Teilmengen durch (nicht) hinzufügen des ersten Elementes.
Also gibt es [mm] 2*2^n=2^{n+1} [/mm] Teilmengen.



Fragen

Also der Induktionsanfang ist mir klar.
Den Anfang vom Induktionsschritt verstehe ich auch noch.
Wir haben jetzt n+1 Elemente, halten das letzte (oder in der Lösung eben das erste) Element fest, und wenden auf die ersten n Elemente die Induktionsvoraussetzung an.
Wieso aber entsteht nun jede Teilmenge von M (mit den n+1 Elementen) aus einer der [mm] 2^n [/mm] Teilmengen mit/ohne hinzufügen des letzten Elementes?

Mir ist klar, dass es keinen Sinn macht, aus mehreren der [mm] 2^n-Teilmengen [/mm] welche zu kombinieren und daraus neue Teilmengen zu bilden, weil die sind in den [mm] 2^n [/mm] ja schon enthalten.
Aber das (n+1)-te Element alleine betrachtet ist doch auch eine Teilmenge der Menge M, oder nicht?
Dann hätte ich nämlich alle [mm] 2^n-Teilmengen, [/mm] alle [mm] 2^n-Teilmengen [/mm] jeweils mit dem (n+1)-ten Element kombiniert und das (n+1)-te element auch noch.
Und das wär dann [mm] 2^{n+1}+1. [/mm]

Wo ist mein Denkfehler?
Ich freu mich auf eine Antwort.

Nadine


        
Bezug
Mengen und Teilmengen: Antwort
Status: (Antwort) fertig Status 
Datum: 18:09 Di 18.03.2008
Autor: abakus


> Es sei [mm]n\in\IN.[/mm] Man zeige, dass eine n-elementige Menge [mm]2^n[/mm]
> Teilmengen besitzt.
>  Hallo.
>  
> Ich habe mal wieder eine Frage zu einer Lösung, die ich
> nicht verstehe [knirsch]
>  
>
>
> Lösung
>  
> Beweis durch vollständige Induktion nach n.
>  
> Induktionsanfang
>  n=1
>  Menge M mit 1 Element besitzt [mm]2^1[/mm] Teilmengen, nämlich M
> und [mm]\emptyset.[/mm]
>  
> Induktionsschritt
>  n [mm]\to[/mm] n+1
>  Sei M eine Menge mit n+1 Elementen.
>  Halte 1. Element fest.
>  Nach Induktionsvorgabe können wir [mm]2^n[/mm] Teilmengen aus den
> übrigen n Elementen bilden.
>  Jede Teilmenge von M entsteht aus einer dieser Teilmengen
> durch (nicht) hinzufügen des ersten Elementes.
>  Also gibt es [mm]2*2^n=2^{n+1}[/mm] Teilmengen.
>  
>
>
> Fragen
>  
> Also der Induktionsanfang ist mir klar.
>  Den Anfang vom Induktionsschritt verstehe ich auch noch.
>  Wir haben jetzt n+1 Elemente, halten das letzte (oder in
> der Lösung eben das erste) Element fest, und wenden auf die
> ersten n Elemente die Induktionsvoraussetzung an.
>  Wieso aber entsteht nun jede Teilmenge von M (mit den n+1
> Elementen) aus einer der [mm]2^n[/mm] Teilmengen mit/ohne hinzufügen
> des letzten Elementes?
>  
> Mir ist klar, dass es keinen Sinn macht, aus mehreren der
> [mm]2^n-Teilmengen[/mm] welche zu kombinieren und daraus neue
> Teilmengen zu bilden, weil die sind in den [mm]2^n[/mm] ja schon
> enthalten.
>  Aber das (n+1)-te Element alleine betrachtet ist doch auch
> eine Teilmenge der Menge M, oder nicht?
>  Dann hätte ich nämlich alle [mm]2^n-Teilmengen,[/mm] alle
> [mm]2^n-Teilmengen[/mm] jeweils mit dem (n+1)-ten Element kombiniert
> und das (n+1)-te element auch noch.
>  Und das wär dann [mm]2^{n+1}+1.[/mm]
>  
> Wo ist mein Denkfehler?
>  Ich freu mich auf eine Antwort.
>  
> Nadine
>  

Hallp,x
könnte es an der leeren Menge liegen?
Die leere Menge ist Teilmenge jeder Menge. Wenn du die leere Menge mit bereits vorhandenen Menge kombinierst, bekommst du ja nichts neues dazu.
Gruß Abakus


Bezug
                
Bezug
Mengen und Teilmengen: Rückfrage
Status: (Frage) beantwortet Status 
Datum: 18:00 Mi 19.03.2008
Autor: Pacapear

Hallo.

> Hallp,x
>  könnte es an der leeren Menge liegen?
>  Die leere Menge ist Teilmenge jeder Menge. Wenn du die
> leere Menge mit bereits vorhandenen Menge kombinierst,
> bekommst du ja nichts neues dazu.
>  Gruß Abakus

Verstehe ich das richtig, dass du meinst, dass es schon richtig ist, das (n+1)-te Element als eigene Teilmenge mitzuzählen, aber dass ich dann nicht eine Teilmeneg mehr habe, weil ich ja das (n+1)-te Element noch mit der leeren Menge vereinigen muss, dass wiederum wieder die leere Menge ergibt, und diese ja bereits in den [mm] 2^n [/mm] Teilmengen vorhanden ist, und ich sie deshalb nicht mehr mitzählen muss?

LG, Nadine

Bezug
                        
Bezug
Mengen und Teilmengen: Antwort
Status: (Antwort) fertig Status 
Datum: 18:39 Mi 19.03.2008
Autor: piet.t

Hallo,
>  
> Verstehe ich das richtig, dass du meinst, dass es schon
> richtig ist, das (n+1)-te Element als eigene Teilmenge
> mitzuzählen, aber dass ich dann nicht eine Teilmeneg mehr
> habe, weil ich ja das (n+1)-te Element noch mit der leeren
> Menge vereinigen muss, dass wiederum wieder die leere Menge
> ergibt, und diese ja bereits in den [mm]2^n[/mm] Teilmengen
> vorhanden ist, und ich sie deshalb nicht mehr mitzählen
> muss?
>  

So ähnlich...
Sei a unser festgehaltenes Element. wenn ich mir aus den Mengen der Induktionsvoraussetzung nun die leere Menge wähle und dann noch a hinzufüge erhalte ich natürlich die Menge {a}. Die leere Menge (die ich ja auch wieder dabei haben muss, wenn ich alle Teilmengen haben will) bekomme ich, wenn ich wieder die leere Menge nehme und a nicht hinzufüge - dann bleibt sie eben leer.

Gruß

piet

Bezug
        
Bezug
Mengen und Teilmengen: Antwort
Status: (Antwort) fertig Status 
Datum: 16:12 Do 20.03.2008
Autor: abakus


> Es sei [mm]n\in\IN.[/mm] Man zeige, dass eine n-elementige Menge [mm]2^n[/mm]
> Teilmengen besitzt.
>  Hallo.
>  
> Ich habe mal wieder eine Frage zu einer Lösung, die ich
> nicht verstehe [knirsch]
>  
>
>
> Lösung
>  
> Beweis durch vollständige Induktion nach n.
>  
> Induktionsanfang
>  n=1
>  Menge M mit 1 Element besitzt [mm]2^1[/mm] Teilmengen, nämlich M
> und [mm]\emptyset.[/mm]
>  
> Induktionsschritt
>  n [mm]\to[/mm] n+1
>  Sei M eine Menge mit n+1 Elementen.
>  Halte 1. Element fest.
>  Nach Induktionsvorgabe können wir [mm]2^n[/mm] Teilmengen aus den
> übrigen n Elementen bilden.
>  Jede Teilmenge von M entsteht aus einer dieser Teilmengen
> durch (nicht) hinzufügen des ersten Elementes.
>  Also gibt es [mm]2*2^n=2^{n+1}[/mm] Teilmengen.
>  
>
>
> Fragen
>  
> Also der Induktionsanfang ist mir klar.
>  Den Anfang vom Induktionsschritt verstehe ich auch noch.
>  Wir haben jetzt n+1 Elemente, halten das letzte (oder in
> der Lösung eben das erste) Element fest, und wenden auf die
> ersten n Elemente die Induktionsvoraussetzung an.
>  Wieso aber entsteht nun jede Teilmenge von M (mit den n+1
> Elementen) aus einer der [mm]2^n[/mm] Teilmengen mit/ohne hinzufügen
> des letzten Elementes?
>  
> Mir ist klar, dass es keinen Sinn macht, aus mehreren der
> [mm]2^n-Teilmengen[/mm] welche zu kombinieren und daraus neue
> Teilmengen zu bilden, weil die sind in den [mm]2^n[/mm] ja schon
> enthalten.
>  Aber das (n+1)-te Element alleine betrachtet ist doch auch
> eine Teilmenge der Menge M, oder nicht?
>  Dann hätte ich nämlich alle [mm]2^n-Teilmengen,[/mm] alle
> [mm]2^n-Teilmengen[/mm] jeweils mit dem (n+1)-ten Element kombiniert
> und das (n+1)-te element auch noch.
>  Und das wär dann [mm]2^{n+1}+1.[/mm]
>  
> Wo ist mein Denkfehler?
>  Ich freu mich auf eine Antwort.
>  
> Nadine

Hallo Nadine,
du machst es dir viel zu schwer. Die Anzahl aller Teilmengen einer n-elementigen Menge ist die Summe der Anzahlen aller Teilmengen mit jeweils 0, 1, 2, ... n-1 bzw. n Elementen.
Diese einzenlne Anzahlen lassen sich kombinatorisch leicht berechnen.
Aus n Elementen lassen sich [mm] \vektor{n \\ k} [/mm] Teilmengen mit k Elementen auswählen. Die Summe aller Binomialkoeffizienten [mm] \vektor{n \\ 0} [/mm] bis [mm] \vektor{n \\ n} [/mm] ist bekanntlich [mm] 2^n. [/mm]
(Wenn das nicht bekannt ist, kann es mit dem biomischen Satz leicht nachgewiesen werden. Es gilt ja
[mm] (a+b)^n= \summe_{k=0}^{n} \vektor{n \\ k}a^k*b^{n-k}. [/mm] Wenn du für a und b jeweils 1 einsetzt, erhältst du die Behauptung.)
Gruß Abakus


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


^ Seitenanfang ^
www.vorhilfe.de