Mengen und Teilmengen < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | 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]](/images/smileys/knirsch.gif "[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
|
|
| |
|
| Status: |
(Antwort) fertig  | | 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
>
>
>
> 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
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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
>
>
>
> 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
|
|
|
|
