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 |
|