Kardinalität Potenzmenge

Neue Frage »

Svenja1986 Auf diesen Beitrag antworten »
Kardinalität Potenzmenge
Hey Wink

Es geht um folgende Aufgabe:

Zeigen Sie bitte auf folgende beiden Weisen, dass eine endliche Menge M mit m Elementen genau Teilmengen besitzt, d. h. die Kardinalität der Potenzmenge von M ist

.

(a)
Beweisen Sie die Behauptung mit Hilfe der vollständigen Induktion.
Hinweis: Beschreiben Sie im Induktionsschritt ausgehend von einer Menge M' mit m Elementen die Menge m+1 Elementen mit , wobei ist, und betrachten Sie die Teilemngen von M, die x enthalten bzw. nicht enthalten.

(b)
Für jede Zahl beschreibt der Binomialkoeffizient die Anzahl der n-elementigen Teilmengen von M.
Dann ist die Gesamtzahl aller Teilmengen von M gerade die Summe aller Teilmengen mit Kardinalität .
Zeigen Sie, dass somit aus dem Binomischen Lehrsatz folgt:
.


zu (a) Da habe ich irgendwie überhaupt keine Ahnung unglücklich

zu (b) Habe mal für m 1 eingesetzt, wo dann 2 rauskommen würde. Aber das ist ja kein Beweis, sondern nur ein Beispiel. Könnte man das Beispiel vll als Induktionsanfang nehmen oder soll man hier gar nicht die vollständige Induktion verwenden? Naja, wenn ich dann mit m+1 weitermachen würde, würde ich ja aber auch nicht wirklich auf ein sinnvolles Ergebnis kommen...

Helft mir mal bitte auf die Sprünge... Tanzen
Leopold Auf diesen Beitrag antworten »

Zu a): Nehmen wir einmal die Gültigkeit für an. Dann betrachten wir irgendeine Menge mit 4 Elementen . Die ersten drei sollen die Menge bilden. Dann gilt offenbar



Es gibt nun Teilmengen von , die nicht enthalten (Kategorie I). Das müssen dann die Teilmengen von sein. Da drei Elemente enthält, sind das Stück. Und das sind sie:



Und jetzt betrachte die Kategorie II derjenigen Teilmengen von , die enthalten. Wie stehen die mit den Teilmengen der Kategorie I in Zusammenhang? Genauer: Wie kann man die Teilmengen der Kategorie I denjenigen der Kategorie II eineindeutig zuordnen? Was passiert also bei jedem hinzukommenden Element (Induktionsschritt)?
 
 
Svenja1986 Auf diesen Beitrag antworten »

Auf Anhieb würde ich jetzt sagen, dass man jedes Element der Potenzmenge mit {x} vereinigt...

usw.

Man erhält dann zusätzlich zu den 8, die du oben genannt hast, die folgenden 8:


Man hat dann also insgesamt 16 Elemente

Und wenn wir jetzt noch eine Teilmenge M'' = {y} hätten, hätten wir die 16 bestehenden Elemente und die 16 Elemente vereinigt mit {y}, insgesamt dann 32=2^5.

Richtig? Aber das ist ja noch kein Beweis... leider unglücklich
Leopold Auf diesen Beitrag antworten »

Zitat:
Original von Svenja1986
Richtig? Aber das ist ja noch kein Beweis... leider unglücklich


Doch! Das ist schon der Beweis. Oder sagen wir besser: die Beweisidee! Das Ganze ist jetzt nur noch nicht formalisiert. Versuche einmal, von dem konkreten Beispiel wegzukommen und allgemein zu formulieren: . Dann hast du es.

Ich helfe dir einmal. Nehmen wir die Behauptung als für alle Mengen mit Elementen als bewiesen an. Und betrachten wir nun eine Menge mit Elementen, unter denen wir eines, nennen wir es , auszeichnen. Die restlichen Elemente bilden dann eine Menge mit Elementen. Es gilt:



Und jetzt betrachte wieder die Kategorien I und II ...

Und zu guter Letzt schließlich den Induktionsanfang nicht vergessen.
Svenja1986 Auf diesen Beitrag antworten »

Ok...

Es gilt also:







Wäre das als Induktionsschritt/schluss ausreichend?
Leopold Auf diesen Beitrag antworten »

Huch! Was machst du denn da?
Du mußt eine Menge von ihrer Kardinalität unterscheiden:



Gesucht ist nun , wobei nach Induktionsannahme eine Menge mit Elementen Teilmengen besitzt.

Die Teilmengen von zerfallen in zwei Kategorien, solche, die nicht enthalten, sie bilden die I. Kategorie (das ist nichts anderes als ), und solche, die enthalten, sie bilden die II. Kategorie . Die Vereinigung



ist eine disjunkte Vereinigung. Es gilt daher:



Und jetzt wende auf die beiden Summanden die Induktionsvoraussetzung an. Beim zweiten Summanden mußt du zuvor noch eine Bijektion herstellen. Das geht genau so wie im Spezialfall .

Und ganz wichtig: Mathematik besteht nicht aus Formeln, sondern aus Inhalten. Die Formeln müssen daher durch Text verbunden werden, sonst entstehen diese Inhalte nicht. Was ich oben an Text geschrieben habe, ist also kein hübsches, aber überflüssiges Beiwerk, sondern zum Verständnis notwendig.
Svenja1986 Auf diesen Beitrag antworten »

Ok, alles klar. DANKE Tanzen

Hat noch jmd einen Tipp für die (b)?
Leopold Auf diesen Beitrag antworten »

Der Tip steht ja eigentlich schon bei der Aufgabe: Binomischer Lehrsatz.



Und jetzt spezialisiere hier . Und dann mußt du noch die Bedeutung der Binomialkoeffizienten für die Kombinatorik kennen. Aber das steht ja auch schon in der Aufgabe ...
Svenja1986 Auf diesen Beitrag antworten »

Ok, ich habe das jetzt mal für a=b=1 ausprobiert:



So, dann habe ich mal m=1 gewählt:









Was habe ich jetzt schon wieder falsch gemacht? unglücklich traurig
saeff Auf diesen Beitrag antworten »
weitere frage
wie stelle ich diese Bijektion für M II im Allgemeinfall her?
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »