Abzählbarkeit
-
Ich habe ein Problem mit folgender Aufgabe:
Ist die Menge aller Teilmengen von N abzählbar?
Im Grunde läugt das ja darauf hinaus dass ich zeigen muss dass die Menge aller unendlichen Teilmengen überabzählbar ist.
Nur leider habe ich KEINEN blassen Schimmer wie ich das anstellen soll.
Irgendwie müsste ich das doch auf den Beweis für die Überabzählbarkeit von R zurückführen können oder?Zu 2 anderen Problemen würde ich gern wissen ob meine Ansätze richtig sind:
Ist für ein beliebiges festes k aus N die Menge aller k-elementigen Teilmengen von N abzählbar?
Mein Ansatz:
Die k-elementigen Teilmengen zB für k=3 sind ja sowas in der Art
{3,7,9} wobei kein Element doppelt vorkommen darf.
Diese Menge ist eine Art echte Teilmenge zu N^k.
In N^k sind ja alle geordneten Tupel enthalten, also enthält das sozusagen alles was ich brauche. Und da N abzählbar ist muss N^k auch abzählbar sein (Cantor-Paarungsfunktion).
Als Teilmenge ist dann die Menge aller k-elementigen Teilmengen auch abzählbar meiner Meinung nach.
Nur weiß ich leider nicht wie ich das mathematisch korrekt hinschreiben soll.2. Ist die Menge aller endlichen Teilmengen von N abzählbar?
Für mich hört sich das so an als ob das einfach nur:
Vereinigung von i=0 bis unendlich aller i-elementigen Teilmengen von N ist.
Also im Grunde die obige Aufgabe nur dass für jedes k die Mengen vereinigt werden.
Demnach dürfte das als Vereinigung abzählbarer Mengen auch wieder abzählbar sein, oder?
-
Ist die Menge aller Teilmengen von N abzählbar?
Also die Potenzmenge.
Nur leider habe ich KEINEN blassen Schimmer wie ich das anstellen soll.
Diagonalisierungstrick von Cantor.
N^k
Fuer beliebiges aber festes k ist N^k abzaehlbar. Zeige einfach, dass NxN abzaehlbar ist (siehe gebrochen rationale Zahlen) ist. Dann gilt es auch fuer MxN, falls M abzaehlbar ist. Esetze M durch NxN und schon hast du NxNxN als abzaehlbar bewiesen. Fahre so fort fuer alle weiteren ... bis k halt.
Potenzmenge
Fuer die Potenzmenge funktioniert das nicht. Aber da hilft dir wikipedia weiter.
-
shisha schrieb:
Ich habe ein Problem mit folgender Aufgabe:
Ist die Menge aller Teilmengen von N abzählbar?
[...]
Irgendwie müsste ich das doch auf den Beweis für die Überabzählbarkeit von R zurückführen können oder?
Genau. Versuch mal eine Bijektion zwischen der Potenzmenge von N und dem Intervall [0;1) zu finden. (Hint: Binärdarstellung)
-
vielen dank,
mit diesen tipps sollte ich in der lage sein das zu lösen
Was ist aber mit den Aufgaben unten von denen ich denke dass ich sie schon gelöst habe?
Kann ich so argumentieren?
Und wenn ja wie schreib ich das hin ? Schließlich kann ich Tupel ja nicht einfach mit Megen gleichsetzen...
-
1.) habe ich bereits schon angedeutet und
2. Ist die Menge aller endlichen Teilmengen von N abzählbar?
Ja, ueberlege dir einfach eine Abbildung in die natuerlichen Zahlen. Dabei hilft es die endlichen Teilmengen (die auch geordnet sein sollten) lexikographisch zu ordnen. Ich wuerde nicht so argumentieren wie du, da Unendlich oder aber unendliche Vereinigung immer Probleme bereitet. Auch kann ich dir beim Aufschreiben nicht helfen, da das Forum keinen Fuellerfederhalter unterstuetzt. Auch solltst du ja auch noch etwas fuer deine Hausaufgabe machen.