Ist die Menge aller endlichen Teilmengen von einer abzählbaren Menge M abzählbar?

Neue Frage »

Questionmark? Auf diesen Beitrag antworten »
Ist die Menge aller endlichen Teilmengen von einer abzählbaren Menge M abzählbar?
Meine Frage:
Aufgabe: Es sei M eine abzählbare Menge. Zeige, dass die Menge aller endlichen Teilmengen von M abzählbar ist.
Meine Frage dazu: Ist die Menge aller endlichen Teilmengen von M überhaupt abzählbar?

Meine Ideen:
Es muss eine bijektive Abbildung geben, damit eine Menge abzählbar ist.
Contarsius Auf diesen Beitrag antworten »
RE: Ist die Menge aller endlichen Teilmengen von einer abzählbaren Menge M abzählbar?
Betrachte für die Menge . Ist diese abzählbar?
Questionmark? Auf diesen Beitrag antworten »

Ja, die Menge ist abzählbar, weil es eine Teilmenge von M ist, und diese abzählbar ist. Ich weiß aber leider nicht, wie mir das im Bezug auf meine Frage weiterhilft :/

Die Menge aller Teilmengen ist die Potenzmenge. Allerdings gibt es doch viel mehr Potenzmengen von M als M an sich. Daher ist keine bijektive Abbildung möglich? Oder ist sie doch möglich, da von der Menge aller endlichen Teilmengen gesprochen wird?
Contarsius Auf diesen Beitrag antworten »

ist keine Teilmenge von , sondern eine Menge von Teilmengen von .
Nämlich gerade der Teilmengen, die Elemente haben.
Was ist denn ?

Zu deinen Überlegungen über die Mächtigkeit der Potenzmenge:
Der Satz von Cantor liefert das. Insofern muss man anders vorgehen.
Questionmark? Auf diesen Beitrag antworten »

müsste dann die Menge der Teilmengen von M sein, die ein Element haben? Oder steh ich jetzt komplett auf dem Schlauch?

Der Satz von Cantor besagt, dass keine surjektive Abbildung einer Menge in ihre Potenzmenge besteht. Also kann ich daraus schließen, dass es egal ist, ob es sich um eine ENDLICHE Teilmenge handelt?
Contarsius Auf diesen Beitrag antworten »

Kannst du nun eine Surjektion von auf angeben?

Der Satz von Cantor trifft nur eine Aussage über die gesamte Potenzmenge, das kann man nicht auf den Fall der endlichen Teilemengen hier übertragen. Die zu beweisende Aussage stimmt nämlich.
 
 
Questionmark? Auf diesen Beitrag antworten »

Ich würde sagen ja, da jedes Element von "getroffen" wird?
In dem Fall wäre doch:
M -->
0 --> 0
1 --> 1
2 --> 2
usw. ?
Contarsius Auf diesen Beitrag antworten »

Ja, bzw.

usw., also . Dadurch kannst du eine Surjektion von auf definieren.
Was kannst du damit über die Mächtigkeit von aussagen?
Questionmark? Auf diesen Beitrag antworten »

und sind gleichmächtig.
Aber trifft das dann auch auf zu?
Contarsius Auf diesen Beitrag antworten »

... und das liefert, dass abzählbar ist.

Für betrachte .
Ist abzählbar? ( -> Wurde das in der Vorlesung bewiesen? Oder dass abzählbar ist?)
Questionmark? Auf diesen Beitrag antworten »

Ja, dass abzählbar ist, wurde bewiesen.
Dementsprechend ist dann auch abzählbar...
Contarsius Auf diesen Beitrag antworten »

Okay, gut. Kannst du nun eine Surjektion von auf angeben?
Questionmark? Auf diesen Beitrag antworten »

Die Surjektion müsste dann so aussehen, oder?
-->
0 --> {leere Menge}
1 -->{0}
2 --> {1}
3 --> {0, 1}
4 --> {2}
...
Contarsius Auf diesen Beitrag antworten »

Ich werde daraus grade ehrlich gesagt nicht schlau. Außerdem:

Es geht nicht um eine Abbildung , sondern um .
Man kann, weil abzählbar ist, die Elemente von mit natürlichen Zahlen identifzieren (Man wählt eine "Abzählung", dh. eine Folge, die alle Elemente genau einmal trifft).
Das bietet sich hier allerdings nicht an.

Auch ist die Menge aller -elementigen Teilmengen, du bildest aber auf Teilmengen anderer Größe ab.

Um eine Surjektion zu finden, nimm ein beliebiges Element aus und ordne ihm sinnvoll eines aus zu.
Überlege dir dazu wie denn ein Element von bzw. eines von aussieht.
Questionmark? Auf diesen Beitrag antworten »

Das versteh ich jetzt ehrlich gesagt nicht. Ich muss auch zugeben, dass mir die Vorstellung fehlt, wie ein aussehen könnte. Ich hab das in der Tat die ganze Zeit mit den natürlichen Zahlen gleichgesetzt.
Contarsius Auf diesen Beitrag antworten »

ist die Kurzschreibeweise für das kartesische Produkt, d.h.


...


Als Elemente hat alle geordneten Paare der Form mit und Elemente von sind alle Tupel der Form mit

Jetzt gilt es jedem Tupel eine -elementige Teilmenge von M zuzuordnen.
Questionmark? Auf diesen Beitrag antworten »

Also z.B. wird dann zugeordnet?
aber wie genau sieht dann ein derartiges aus?
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »