Formeller Beweis Überabzählbarkeit Potenzmenge?
Quelle: https://www.google.de/books/edition/Analysis_I_und_Analysis_II/elxGMwEACAAJ?hl=de
Ich verstehe den 2. Fall nicht ganz, kann das jemand anders erklären? Vielleicht verstehe ich auch die Definition von U nicht ganz
2 Antworten
Zum Beweis des Gegenteils nehmen wir an, die Potenzmenge von N wäre abzählbar, d.h. es gäbe eine bijektive Funktion (eine "Abzählung") zwischen N und P(N), d.h. die natürlichen Zahlen wären eineindeutig den Mengen von natürlichen Zahlen zugeordnet. Zu jeder natürlichen Zahl gäbe es also eine ihr zugeordnete Menge von natürlichen Zahlen, und zu jeder beliebigen Menge von natürlichen Zahlen gäbe es eine natürliche Zahl, der sie zugeordnet ist. Nun kann es bei einer beliebigen natürlichen Zahl n natürlich sein, daß n in der ihr zugeordneten Menge M(n) selber enthalten ist, das wird ja durch nichts ausgeschlossen. Es kann aber auch sein, daß dies nicht der Fall ist. Mit "U" bezeichnen wir nun die Menge aller natürlichen Zahlen, bei denen dies nicht der Fall ist, also die Menge aller natürlichen Zahlen, die in der ihnen durch M zugeordneten Menge eben nicht enthalten sind. Nun ist U eine Menge von natürlichen Zahlen, müßte also in der Abzählung irgendwo "vorkommen", d.h. es müßte eine natürliche Zahl n0 geben, der sie zugeordnet ist. Nun fragen wir: Ist n0 selber ein Element der ihr zugeordneten Menge U oder nicht? Angenommen, n0 ist in U drin, dann würde n0 also zu den natürlichen Zahlen gehören, die in der ihnen zugeordneten Menge enthalten sind. U ist aber gerade definiert als die Menge aller natürlichen Zahlen, bei denen das nicht der Fall ist, also führt die Annahme, daß n0 in U ist, zu einem Widerspruch. Ist n0 aber nicht in U, dann ist sie also nicht in der ihr zugeordneten Menge enthalten, aber U enthält ja per definitionem die und nur die natürlichen Zahlen, die nicht in der ihnen zugeordneten Menge enthalten sind, also muß n0 doch in U sein. Sowohl die Annahme, daß n0 in U ist, als auch die Annahme, daß n0 nicht in U ist, führt also zu einem Widerspruch. Daher gibt es also keine natürliche Zahl, der U durch die Abbildung M zugeordnet ist, d.h. M ist nicht surjektiv und also nicht bijektiv. Es gibt also keine solche bijektive Abbildung zwischen N und P(N), d.h. P(N) ist nicht abzählbar.
Ich weiß nicht so ganz was da Erklärungsbedürftig ist. Was bedeutet denn die Definition der Menge U? Weißt du überhaupt was die Abbildung M bedeutet? Bedenke dass da Zahlen auf Mengen abgebildet werden. Hast du den (einfachereren) Beweis das R überabzählbar ist verstanden? Der hier beschriebene Beweis funktioniert ähnlich und ist eine Variante der sogenannten Diagonalisierung.
U ist eine Menge, und zwar eine Teilmenge der natürlichen Zahlen (selbst wenn sie leer wäre wäre es eine Teilmenge, denn die leere Menge ist Teilmenge jeder Menge). Wenn U eine Teilmenge der natürlichen Zahlen ist ist U ein Element der Potenzmenge. Da M surjektiv ist wird jedes Element der Potenzmenge von M "getroffen". Es muß also ein n € N geben, welches durch M auf U abgebildet wird.
Nun gibt es zwei Möglichkeiten, nämlich entweder dieses n ist selbst Element von U oder dieses n ist NICHT selbst Element von U. Beides kann über die angenommene Eigenschaft von U zu einem Widerspruch geführt werden.
Wieso gibt es was nicht? Ich glaube dir fehlen schlicht die Grundlagen um den Beweis zu verstehen.
ja schon, mir ist halt nur nicht klar, warum es überhaupt ein n Element N gibt, das in dieses U reinkommt und wie es dann weiter geht mit dem Beweis