| Autor |
Beitrag |
    
Ivo Matzekat (Lucifer)
| | Veröffentlicht am Freitag, den 27. Oktober, 2000 - 15:44: | 
|
hi
ich habe folgendes problem
Sei M eine belibige Menge und m=|M| die Anzahl der Elemente von M. Zeige, daß |P(M)|=2^m.
hat vieleicht jemand einen Vorschlag wie man an dieses Problem ran gehen solte?
wir tapen hier alle noch im dunkeln
vielen dank im voraus |
Zaph (Zaph)
| | Veröffentlicht am Freitag, den 27. Oktober, 2000 - 17:08: |
|
Sei A eine Teilmenge von M. Jedes der m Elemente von M kann in A liegen oder nicht (2 Möglichkeiten). Also gibt es 2*2* ... *2 = 2^m Möglichkeiten für A. Also hat M 2^m Teilmengen. |
Matroid (Matroid)
| | Veröffentlicht am Freitag, den 27. Oktober, 2000 - 18:09: |
|
Hi Ivo,
die Potenzmenge P(M) ist die Menge aller Teilmengen von M. Die Frage ist also, wieviele verschiedene Teilmengen man aus m Elementen bilden kann. Um das zu zaehlen gibt es verschiedene Moeglichkeiten, ja nachdem, was man verwenden darf. Was man immer anwenden kann, ist vollständuge Induktion.
A) Wenn M={}, also |M|=0, dann ist P(M)={{}}, denn nur die leere Menge ist Teilmenge der leeren Menge. Also |P(M)|=1=20.
B) Sei nun |M|=n+1. Sei x ein bestimmtes Element aus M. Bilden wir nun alle Teilmengen.
Wir können die Teilmengen aufteilen in
a) die Teilmengen, die x nicht enthalten,
b) die Teilmengen, die x enthalten.
Nach Induktionsvorausetzung wissen wir, das die Anzahl der Teilmengen bei a) = 2n ist, denn es handelt sich ja um alle Teilmengen einer Menge mit n Elementen.
In allen Teilmengen aus b) können wir das Element x entfernen. Dann ist die Anzahl dieser Mengen also auch = 2n, denn es handelt sich auch hier um alle Teilmengen einer Menge mit m Elementen.
Addiere nun die Anzahlen für a) und b)
2n + 2n = 2n+1.
Fertig.
Gruß
Matroid |
|
