Abzählbarkeit von IN x IN

Neue Frage »

vongagern Auf diesen Beitrag antworten »
Abzählbarkeit von IN x IN
Ich habe folgendes Problem:

Bewiesen werden soll: IN x IN ist nicht abzählbar. Ist natürlich Quatsch, aber wo liegt im folgenden Beweis der Fehler?

Jede nat. Zahl lässt sich eindeutig darstellen in den Form

mit u_i aus {0, 1}

Also können wir u mit der unendlichen Bitfolge (u0, u1, u2, ...) identifizieren. Dies erweitern wir für die Menge der Paare nat. Zahlen und stellen (u, v) durch die verschränkte Bitfolge (u0, v0, u1, v1 ...) dar.

Wir nehmen nun an, dass eine Aufzählung von IN x IN existiert. Diese ist eine Aufzählung solcher Bitfolgen.

Zählt man alle diese Bitfolgen auf und konstruiert eine neue Bitfolge, indem man einfach die Diagonalelemente nimmt und invertiert, ergibt sich ein Bitstring, der in der Aufzählung nicht vorkommt. Damit ist ein Widerspruch erzeugt und wir folgern, dass IN x IN nicht aufzählbar ist.
Leopold Auf diesen Beitrag antworten »

Zwar kannst du jede natürliche Zahl als solch eine Bitfolge beschreiben, aber nicht jede solche Bitfolge stellt eine natürliche Zahl dar. Die Identifikation von Bitfolge und natürlicher Zahl ist also falsch.

Beispiel: Die Bitfolge (1,0,1,0,1,0,1,0,...)
pumuckl Auf diesen Beitrag antworten »

In dem Beweis fehlt, dass bei der Darstellung natürlicher Zahlen nur endlich viele u_i bzw v_i =1 sind, oder eben umgekehrt, das fast alle u_i, v_i = 0 (sonst würde die Reihe divergieren!)
Wenn du dir jetzt aus so einer Aufzählung die Diagonale nimmst sind dementsprechend auch dort fast alle u_i, v_i = 0, du hast eine weitere Darstellung einer natürlichen Zahl, die allerdings bestimmt irgendwo in deiner aufzählung auch vorkommt. Invertierst du den Kram, divergiert die Reihe und du hast keine natürliche Zahl - da ist der Haken *fg*
maxx03 Auf diesen Beitrag antworten »

Nachdem das obige Problem ja so souverän gelöst wurde, schließ ich gleich mal meine Frage an:

Da unendlich ist, ist nach einem Satz ja die Potenzmenge überabzählbar.

Aber x ...x (i- mal) ist für alle i abzählbar. Wieso kann man jetzt Potenzmenge von nicht schreiben als:
dabei soll die Vereinigung über n1 erfolgen (wie kann man das in Latex unters Vereinigungszeichen bekommen verwirrt ?) .
Da die Mengen über die vereinigt wird abzählbar sind, ist ihre abzählbare Vereinigung ja wieder abzählbar. Der Fehler kann deshalb nur darin liegen, dass eben nicht alle Mengen der Potenzmenge in dieser Vereinigung liegen.
Ich könnte mir vorstellen das zB. die Folge der geraden Zahlen nicht enthalten ist, stimmt das ?

Danke für die Antworten
Leopold Auf diesen Beitrag antworten »

Genau.
Deine Vereinigungsmenge enthält nur endliche Teilmengen von .
pumuckl Auf diesen Beitrag antworten »

Der Haken an der Sache ist, dass du eine Vereinigung über alle endlichen Mengen hast, die aus natürlichen Zahlen bestehen (denn n ist immer endlich). Selbst wenn du jetz dein Beispiel noch derart verfeinerst, dass in den Mengen gilt, hast du wie du schon sagtest die Menge der geraden Zahlen nicht dabei, und auch alle anderen unendlichen Teilmengen von |N nicht
 
 
vongagern Auf diesen Beitrag antworten »

Danke für die kompetente Beantwortung meiner Frage. Ich sitze in einer Vorlesung über mathematische Logik und verstehe außerdem nicht, warum man den folgenden Beweis für reelle Zahlen nicht auch auf rationale Zahlen anwenden kann (wurde in der Vorlesung nicht weiter ausgeführt):

Man kann folgendermaßen beweisen, dass IR in [0, 1] nicht abzählbar ist: Man nimmt das Gegenteil an, betrachtet eine Aufzählung der Elemente in [0, 1]. Das i-te Element soll mit einem Intervall der Länge 10^(-i) mit i = 1, 2, 3... umgeben werden.

Die Vereinigung ergibt eine vollständige Überdeckung des Intervalls [0, 1]. Betrachtet man jedoch die Summe der Intervalllängen , so erhält man einen Wert kleiner 1 (das verstehe ich z.B. schon nicht. Damit ergibt sich ein Widerspruch.

Warum kann man diesen Beweis nicht auf die rationalen Zahlen übertragen?
flixgott Auf diesen Beitrag antworten »

den beweis mit den intervalllängen habe ich auch noch nicht gesehen, aber es gibt verschiedenste einfach diagonilisungsbeweise, deren nicht-übertragbarkeit auch ziemlich trivial ist. aber ich hab mal einen gedanken anstoss zu rationalen und reellen zahlen, der vielleicht zum grundsätzlichen verständnis der unterschiedlichen mächtigkeiten von rationalen und reellen beiträgt:

betrachtet man die rationalen zahlen zusammen mit der kleinergleich-relation (diese ordnet die rationalen zahlen in eindeutiger weise). jetzt gibt es in den rationalen zahlen teilmengen, die beschränkt und nicht leer sind und trotzdem weder supremum noch infimum besitzen: das ist mit den reellen zahlen nicht möglich!
pumuckl Auf diesen Beitrag antworten »

Zitat:
Original von vongagern
nimmt das Gegenteil an, betrachtet eine Aufzählung der Elemente in [0, 1]. Das i-te Element soll mit einem Intervall der Länge 10^(-i) mit i = 1, 2, 3...


Das sieht mir so aus als ob da irgendwas fehlt: "Das ite Element soll mit einem Intervall... "

Eine andre Möglichkeit wie die Abzählbarkeit von Q ganz leicht einzusehen ist:
Betrachte die Abbildung f:Q+ --> NxN f(a/b) = (a,b) nach vollständiger Kürzung von a/b.
Die Abbildung ist nichtmal surjektiv, da z.B. 1 auf (1,1) abgebildet wird, nicht aber auf (2,2), (3,3) usw.
vongagern Auf diesen Beitrag antworten »

Hab meinen Eintrag um die fehlenden Teile ergänzt. Die anderen Beweise kenne und verstehe ich auch, aber es geht mir ganz konkret um diesen Beweis. Ich kann einfach nicht einsehen, warum das mit Q nicht gehen soll.
pumuckl Auf diesen Beitrag antworten »

Die Sache bei R ist die: Das intervall [0,1] ist nur deswegen vollständig abgedeckt, weil jeder Punkt den du in dem Intervall findest, Element davon ist und damit von seinem eigenen I abgedeckt worden ist.
Wenn du das ganze mit Q versuchst, hast du überabzählbar viele Punkte, die nicht in Q liegen, und die werden nicht alle mit den I abgedeckt.

Beweis dafür: Nim ein Intervall [a,b] das noch nicht abgedeckt ist, und zwar ein Intervall, das größer als ist.
(Dass das geht folgt daraus, wenn du bei i=1 anfängst und deine Intervalle immer genau in die Mitte des kleinsten nicht abgedeckten Intervalls packst, bekommst du zwei Intervalle der größe )
Wenn du dein Intervall da reingepackt hast, bleibt mindestens ein nicht abgedecktes Intervall, das größer ist als dein nächstes Abdeck-Intervall. Das kannst du zwar unendlich so weiter machen, aber am Ende bleibt laut Intervallschachtelungsprinzip (du schachtelst die nicht abgedeckten Intervalle) immernoch ein Punkt über, den du nicht abgedeckt hast. Damit ist [0,1] nicht mehr vollständig abgedeckt...
Neue Frage »
Antworten »



Verwandte Themen

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