Überabzählbarkeit von P(N)?
Hey, die vorherige Aufgabe lautete zu beweisen, dass R (Rationale Zahlen) überabzählbar ist, ich habe es nach folgendem schema gelöst:
nun soll ich aus dieser Erkenntnis zeigen, dass P(N) (Potenzmenge der Natürlichen Zahlen) überabzählbar ist. Ich verstehe nun aber nicht wie ich Cantorschen Diagonalisierungsmethode auf die Potenzmenge der Natürlichen Zahlen anwenden soll.
Danke im Voraus ^^!
4 Antworten
Im Grunde gehst du genauso vor, nur dass du stattdessen eine Menge Generierst.
Nim an, dass P(N) abzählbar ist. Dann existiert eine Abbildung f: N -> P(N) die bijektiv ist.
Versuche nun damit eine Menge M Zu konstruieren, für die gilt: f(i)≠ M für alle i.
Ist M in der Potenzmenge?
Wann sind zwei Mengen ungleich?
Wenn es ein Element in einer Menge gibt, welches nicht in der anderen ist.
Du musst also sorgen, dass die Menge mit jeder anderen Menge sich um mindestens ein Element unterscheidet.
Bei den Reellen Zahlen hast du einfach die k. Ziffer abgeändert
Was kannst du stattdessen bei Mengen machen?
Kann ich also z.B. für die 1. Menge { }, {1}, {2}, 2. Menge {3}, {4}, {5} 3. Menge {6}, {7}, {8}, nutze nun Diagonalisierungsmethode und erhalte { }, {4}, {8},… welche nicht in der Wertetabelle enthalten ist und somit ist P(N) überabzählbar.
Wenn du Abzählbarkeit von P(N) annimmst, dann kannst du jede Teilmenge als Folge von Nullen und Einsen in dein Schema schreiben, 1= "n ist in der Teilmenge enthalten", sonst 0. Dann kannst du diagonal durch Vertauschen von 0 und 1 eine Teilmenge konstruieren, die im Schema nicht enthalten ist. D.h. du hast einen Widerspruch konstruiert.
Ehm, die Menge der rationalen Zahlen sind abzählbar
Verwende den
https://de.wikipedia.org/wiki/Satz_von_Cantor
Oder du überlegst dir warum gilt das R = P(N).
Kann ich also sagen da N abzählbar ist, und N aber weniger mächtig als P(N) ist, dass P(N) dann überabzählbar ist? Wird das wohl als Beweis reichen?
Das ist ein gefährliches Pflaster, du mußt schon ein wenig schärfer formulieren. Kensnt du eigentlich die
https://de.wikipedia.org/wiki/Kontinuumshypothese
Hast du denn schon bewiesen dass die Potenzmenge einer Menge M mächtiger ist als M selbst? Also hast du den Satz von Cantor verstanden?
Nein, kenn ich leider nicht. Ich glaube wir sollten es schon mit der Cantorschen Diagonalisierungsmethode lösen.
Der Satz von Cantor verwendet eine Verallgemeinerung der Diagonalisierungsmethode, da mußt du nur genau hinschauen.
Die Potenzmenge ist ja die Menge aller Teilmengen, somit gibt es bestimmt eine Teilmenge die nicht in N enthalten ist und P(N) ist somit überabzählbar?
Das ist nicht der Beweis. Bitte lies dir meine Links durch. Die solltest du im Studium schon verstehen können.
Jede Teilmenge von N ist offensichtlich in N enthalten. Sonst wäre sie ja keine Teilmenge. Du mußt zeigen dass du die Teilmengen nicht aufzählen kannst.
Da P(N) mächtiger als N ist, besitzt P(N) mehr Elemente, somit ist es unmöglich, alle Elemente der Potenzmenge der natürlichen Zahlen aufzulisten, indem man sie einer natürlichen Zahl zuordnet.
Da P(N) mächtiger als N ist
Wo genau hast du das bewiesen? Hast du den Beweis das es nicht möglich ist die Elemente von P(N) aufzulisten verstanden? Deine Formulierungen sind mathematisch schlicht ungenau.
Nehmen wir an ich beschränke N auf 1 bis 3. P(N) wäre P = {{ }, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1,2,3}}. Wie erstelle ich nun verschiedene Zahlen, wie im obigen Beispiel mit Reelen Zahlen?