Teilmengen der Potenzmenge mit gerader und ungerader Anzahl an Elementen gleich mächtig?

Question

Sei M eine endliche, nicht leere Menge, so sind die Menge ℘⁰(M) ⊂ ℘(M) der Teilmengen, die aus einer geraden Anzahl von Elementen bestehen, und die Menge ℘¹(M) der Teilmengen, die aus einer ungeraden Anzahl von Elementen bestehen, gleich mächtig.

Soweit die Aufgabenstellung. Wenn ich solche Mengen betrachte, sehe ich, dass die Anzahl an Teilmengen mit gerader Anzahl von Elementen tatsächlich genau so groß ist, wie die mit ungerader Anzahl von Elementen. (Vorausgesetzt, man betrachtet die leere Menge als Menge mit gerader Anzahl an Elementen). Ich weiß jetzt aber nicht, wie ich einen Beweis dafür ansetzen soll.

Gibt es dafür irgendwelche Hilfestellungen?

Comments

Schau z.B. schon mal hier: https://www.mathelounge.de/51903/nichtleere-menge-anzahl-teilmengen-geraden-anzahl-elementen 

Answer 1

Hallo jd,

man man das mit vollständiger Induktion zeigen: 

Die Aussage (A)  ist richtig für Mengen mit einem Element  [ A(1) ] 

Sie sei richtig für Mengen mit n Elementen (IV)    [ A(n) ]

A(n) → A(n+1)  

Bei einer Menge M  mit  n+1 Elementen kann man dann ein beliebiges Element e herausnehmen, so dass die Restmenge R noch n Elemente hat und die Aussage A(n) für diese nach IV wahr ist.

Die Teilmengen von M  sind dann die von R und die, die man erhält, wenn man jeweils zu einer Teilmenge von R das Element e wieder hinzufügt. Dabei dreht sich "Mächtigkeit gerade bzw. ungerade" um. Man hat also bei M jeweils doppelt so viele gerade bzw. ungerade "Mächtigkeiten" wie bei R und dort sind beide gleich. Die Aussage A(n+1) ist also auch für M richtig.

Gruß Wolfgang