Beweise: Potenzmenge hat gleich viele "gerade" wie "ungerade" Teilmengen |
| 04.10.2016, 15:07 | Mimir | Auf diesen Beitrag antworten » | ||
| Beweise: Potenzmenge hat gleich viele "gerade" wie "ungerade" Teilmengen Hallo 
Ich weiss, dass der Titel etwas falsch formuliert ist, aber ich wollte ihn so kurz wie möglich halten. Ich habe die Aufgabe, zu beweisen, dass die Anzahl aller Teilmengen von der nichtleeren endlichen Teilmenge N mit einer geraden Anzahl Elementen gleich der Anzahl aller Teilmengen von N mit einer ungeraden Anzahl Elementen ist. Ausserdem soll ich angeben, wie gross diese Zahl ist. Meine Ideen: Die Menge aller Teilmengen von N entspricht ja der Potenzmenge von N. Meine Idee ist die folgende: Ich beweise die Behauptung per Induktion. Sei n die Mächtigkeit der Menge N. Dann gilt die Aussage für n=1, da die Potenzmenge von N nur folgende zwei Elemente enthält: die leere Menge, welche 0 Elemente (also eine gerade Anzahl Elemente) enthält und das einzige Element, was wir hier einmal {x} nennen. {x} hat ein Element und hat somit eine ungerade Anzahl Elemente. Jetzt muss ich das ganze für n+1 zeigen. Ich kann die Menge N nun wie folgt schreiben: N = N\{x} {x} Für N\{x} weiss ich, dass die Menge die Mächtigkeit n hat. Für n haben wir die Behauptung bereits beweisen. Es bleibt noch zu zeigen, dass die Vereinigung mit {x} immer noch gleich viele Teilmengen mit gerader Anzahl Elementen wie Teilmengen ungerader Anzahl Elementen hat. Dafür habe ich mir überlegt, dass die Potenzmenzge von N = N\{x} {x} gleich der Potenzmenge von N\{x} ist vereint mit der Menge, in der jedes Element (jede Teilmenge) der Potenzmenge von N\{x} noch mit {x} vereint ist. Dann habe ich doppelt so viele Elemente in der Potenzmenge durch die Erhöhung der Mächtigkeit von N um 1. Das heisst, dass die Potenzmenge einer Menge mit n Elementen 2^n Elemente enthält. Aber zurück zum Beweis: N\{x} hat genau gleich viele Teilmengen mit gerader Anzahl Elementen wie Teilmengen mit ungerader Anzahl Elementen. Wie sieht es aber mit der oben erwähnten Vereinigung aus? Wenn wir jedes Element (jede Teilmenge) der Potenzmenge von N\{x} mit {x} vereinen, dann haben nun alle Teilmengen, die zuvor eine ungerade Anzahl Elemente hatten nun eine gerade Anzahl Elemente. Das heisst aber auch, dass die Teilmengen, die zuvor eine gerade Anzahl Elemente hatten nun eine ungerade Anzahl Elemente haben. Das Verhältnis zwischen den Teilmengen gerader Anzahl Elemente und Teilmengen ungerader Anzahl Elemente hat sich also nicht verändert, woraus folgt, dass die Behauptung auch für die nichtleere endliche Menge N der Mächtigkeit n+1 gilt. Meine Frage: Ist der Beweis korrekt? Ein Freund von mir hatte einen anderen Ansatz. Er wollte die Behauptung mittels Erläuterung der Permutationen anhand des Binominalkoeffizienten beweisen. Kann man die Behauptung auf beide dieser Arten beweisen? Vielen Dank für eure Hilfe!
|
||||
| 04.10.2016, 15:19 | Guppi12 | Auf diesen Beitrag antworten » | ||
Hallo Mimir, herzlich Willkommen im Forum 
Dein Beweis ist korrekt. Es fehlt nur die Erwähnung, dass x irgendein beliebiges Element aus N sein soll. Dass das eine Element im Induktionsanfang x hieß, ist egal, im Induktionsschritt ist N eine andere Menge, als vorher. Ansonsten sehr gut 
Ich kann natürlich nicht sagen, ob der Beweis deines Freundes korrekt ist. Es gibt aber durchaus Ansätze, die Behauptung zu beweisen, die auf dem Binomialkoeffizienten und dem binomischen Lehrsatz beruhen. |
||||
| 04.10.2016, 15:40 | Mimir(2) | Auf diesen Beitrag antworten » | ||
Vielen Dank für die Antwort und die Begrüssung
Dann bin ich froh, dass der Beweis korrekt ist. Dass x ein beliebiges Element aus N sein kann werde ich noch ergänzen, vielen Dank für den Hinweis. Ich kann mich leider nicht einloggen, weil ich mein Passwort nicht weiss und wenn ich auf Passwort vergessen klicke, erhalte ich zwar eine Mail, in der ich mein Passwort zurücksetzen kann, aber der Link führt auf eine Unterseite mit einem Runtime Error. Schade, aber vielleicht geht es ja später wieder. Ich wünsche dir noch einen schönen Tag
|
||||
| 04.10.2016, 17:04 | Guppi12 | Auf diesen Beitrag antworten » | ||
Dir auch einen schönen Tag noch, danke. Du kannst dein Passwortproblem hier: Fragen zum MatheBoard & click for knowledge nochmal schildern, dann sehen sich die Admins das mal an. Ich selbst konnte das Problem nicht reproduzieren. Edit: Sehe gerade, das hast du selbst schon gefunden und auch gleich eine Lösung mit dazu.
|
||||
|
|
