| Autor |
Beitrag |
    
Benjamin (Benni121)
| | Veröffentlicht am Sonntag, den 06. Mai, 2001 - 22:48: | 
|
habe hier eine aufgabe die ich nicht verstehe und ich nicht weiß was ich machen soll...kann mir das jemand vielleicht vorrechnen??? danke
zeigen sie: hat die Menge A n Elemente, dann hat die Potenzmenge P(A) 2^n Elemente. |
Rincewind77
| | Veröffentlicht am Montag, den 07. Mai, 2001 - 18:49: |
|
Beweis mit vollständiger Induktion:
Induktionsvoraussetzung (IV): #(M)=n => #(Pot(M))=2^n (sprich:Mächtigkeit einer Menge M =n => die Potenzmenge hat 2^n Elemente)
Induktionsanfang:
n=0: M={} => Pot(M)={ {} }, also hat ein Element!
Induktionsschritt: n => n+1
Sei M Menge mit n+1 Elementen z.B. {1,2,...,n,n+1}
Pot(M)=Pot({1,...,n} u {n+1})= ( "u" für vereinigt!)
={Pot({1,...,n}) u {}} u {Pot({1,...,n}) u {n+1}}
=> Pot(M)=2*Pot(M \ {n+1})=2*2^n=2^(n+1)
in Worten: Man betrachte alle Teilmengen der Potenzmenge, die n+1 nicht enthalten, das sind also alle Teilmengen einer n-elementigen Menge, die nach IV 2^n Elemente hat, plus alle Teilmengen der Pot(M), die n+1 enthalten, das sind (laut IV) genausoviele, also hat Pot(M) 2^(n+1) Elemente!
qed
PS: Ich hoffe es ist halbwegs verständlich! |
Benjamin (Benni121)
| | Veröffentlicht am Montag, den 07. Mai, 2001 - 23:17: |
|
gucken ob ich das verstehe....danke |
Matroid (Matroid)
| | Veröffentlicht am Dienstag, den 08. Mai, 2001 - 21:16: |
|
Kannst auch mal hier nachsehen:
http://www.univie.ac.at/future.media/mo/materialien/matroid/files/vi/vi.html#9b unter Mengenlehre.
Vielleicht kann man das besser lesen, es ist aber der gleiche Beweis.
Gruß
Matroid |
|
