Beweis der Abzählbarkeit reeller Zahlen?

[Pippen]

1) Wir konstruieren eine Liste reeller Zahlen im Intervall 0-1 nach folgendem Verfahren:

0,0
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,9
0,00 [Wir springen zurück zum Anfang "0,0" und setzen 0-9 dahinter]
0,01
0,02
0,03
0,04
0,05
0,06
0,07
0,08
0,09
0,10 [Wir springen zurück zu "0,1" und setzen 0-9 dahinter]
...
0,99
0,000 [Wir springen zurück zu "0,00" und setzen 0-9 dahinter]
0,001
...

Ich hoffe es wird klar, dass hier ein eindeutiges System zur Generierung reellen Zahlen beschrieben wird, welches nicht in einer Unendlichkeit stecken bleibt, wie wenn man zB erstmal alle Zahlen 0,1... aufschreiben wollte. Auch wenn ich es nicht vermag: Ich bin überzeugt, es gäbe eine Formel, den Algorithmus der Zahlengenerierung konkret aufzuschreiben.

2) Jetzt ist mE eine cantorschen Diagonalzahl nicht mehr möglich. Informeller Beweis: Für die Cantorzahl 0,x1,... gelte: Wenn x=5, dann x=4, sonst x=5. Die erste Zahl der o.g. Liste ist 0,0. Daher wäre die erste Stelle der Cantorzahl: 0,5.... Eine solche Zahl (0,5...) gibt es aber, sogar unendlich viele. Dasgleiche bei der zweiten Stelle. Dafür würde 0,1 bzw. 0,10... stehen. Damit würde die Cantorsche Zahl auf zwei Stellen genau lauten: 0,55.... Auch bei dieser Zahl sehen wir, dass und warum sie problemlos generierbar ist. Egal, welche Zahl "0,x1,...x_n" uns Cantor konstruiert, wir könnten für jedes x_n sicher sein, dass und wo es in der Liste doch vorkommt, denn mit unserem Verfahren erschaffen wir schlicht eine unendlich-lange und unendlich-breite Matrix in der alle Zahlenkombinationen 0-9 irgendwann vorkommen müssen und in der wir auch wüßten, wo genau das ist, weil der Algorithmus genau formulierbar ist und unendliche Zahlenreihen generiert (so dass jede Zahl einmal vorkommen muss).

Das ist natürlich kein Beweis, aber kommt meine Idee heraus? Man müsste eigentlich nur beweisen, dass mit meinem Algorithmus alle Zahlenkombis konstruierbar sind und das sollte leicht möglich sein, weil es intuitiv ziemlich einsehbar scheint. Dann geht Cantor's Diagonalzahl schon deshalb nicht, weil auch sie unter "alle Zahlenkombis" fallen muss.

[tomS]

Ich denke nicht, dass du beweisen kannst, dass dein Erzeugungsverfahren abzählbar ist. Mir ist nicht klar, wie deine Liste wirklich durchnummeriert werden kann.

[Skeltek]

Ja, deine Idee kommt raus. Trotzdem hat jede deiner Zahlen, die sich an einer endlichen Stelle befindet nur endlich viele Nachkommastellen. 4/9 ist zum Beispiel gar nicht dabei.

Ich denke die Schwierigkeit zu verstehen, was Cantor da eigentlich bewiesen hat, kommt von der Inkontinenz des Dezimalsystems (Wortspiel ^^).
Würde man nicht nur numerisch ganzwertige Zahlen als Ziffern zulassen, sondern auch z.B. daraus gebildete z.B. irrationale Konstrukte rekursiv in die Menge der möglichen Ziffern aufnehmen, käme viel besser heraus was Cantor eigentlich damit sagen wollte.
Die Menge aller konstruierbaren existenten Zahlen(auch Cantors Diagonalzahlen zählen dazu) ist abzählbar.

Es ist keine Zahlenfolge möglich, die alle Zahlen lückenlos abdeckt.
Cantos Logarithmus ist so gestaltet, dass er durch Rekursion mit der Liste(bzw dem Algorithmus, der deine Liste macht) direkt eine Zahl aus einer dieser Lücken generiert.
Änderst du deinen Logarithmus für die Listenerstellung um diese Diagonalzahlen abzudecken, ändert sich automatisch auch der Logarithmus von Cantor und zeigt dann auf ein anderes Element der noch nicht aufgezählten Zahlen.
Um genau zu sein ist der Logarithmus von Cantor wie ein Zeiger/Pfeil, der nicht auf ein bestimmtes Element, sondern auf eine noch nicht aufgezählte Restklasse zeigt(er zeigt immer in ein Komplement der bereits aufgezählten Zahlen). Cantor beweist, daß diese Restklasse niemals Null wird, egal wieviele Elemente man daraus aufzählt. Die Restklasse ist genauso mächtig wie dein ursprüngliches Intervall [0;1], was eine vollständige Aufzählung aller darin enthaltenen Elemente zu jedem endlichen Zeilennummer der Liste unmöglich macht.

[Pippen]

Ja, deine Idee kommt raus. Trotzdem hat jede deiner Zahlen, die sich an einer endlichen Stelle befindet nur endlich viele Nachkommastellen.

Nein, denn die Liste wäre ja unendlich, also müssten da irgendwann unendlich lange Zahlen stehen. Wenn Cantor das nicht einsieht - und ich könnte das nachvollziehen, denn beim Betrachten einer n-ten Stelle der Liste würde sich immer nur eine endliche Zahl finden - dann kann er auf der anderen Seite auch nicht behaupten, seine Diagonalzahl sei unendlich und erfasse damit die Liste aller reellen Zahlen, denn auch dort gilt: welche n-te Stelle der Diagonalzahl ich auch immer betrachte, die Zahlenfolge wäre endlich und würde daher die Liste der (unendlich vielen) reellen Zahlen nicht komplett erfassen. Entweder er akzpeptiert mein Vorgehen, dann widerlege ich seinen Beweis oder er akzeptiert es nicht, dann klappt aber sein Beweis nicht. Das wäre meine Idee.

@toms: Meine Liste fängt an, von 0,0 bis 0,9 zu zählen, springt dann an die erste Stelle zurück (0,0) und hängt einfach wieder die Zahlen 0-9 dran, springt dann an die zweite Stelle des ersten Blocks (0,1) und hängt wieder die Zahlen 0-9 dran usw., bis alle Kombinationen von 0,00 bis 0,99 gewonnen wurden. Danach wird analog alles für 0,000-0,999 durchgespielt und so geht es dann immer weiter, ad infinitum. Das kann man mE einfach abzählen - jeder Schritt bekommt eine Nummer.

[Skeltek]

Ja, deine Idee kommt raus. Trotzdem hat jede deiner Zahlen, die sich an einer endlichen Stelle befindet nur endlich viele Nachkommastellen.

Nein, denn die Liste wäre ja unendlich, also müssten da irgendwann unendlich lange Zahlen stehen.

Das ist gerade der Trugschluss. Da die Liste kein Ende hat, können dort auch nicht deine "restlichen Zahlen" stehen.

Ich formuliere mal den Kern der aussage um, was wirklich gut die Bedeutung trifft:
Abzählbar bedeutet, daß restlos alle Zahlen eine endliche Position bzw Zeile in der Liste bzw beim aufzählen haben. (*)
Du kannst die Liste nicht so umordnen, dass wirklich restlos alle Zahlen(die, die du als im Unendlichen befindlich annimmst) an einer endlichen Stelle auch tatsächlich vorkommen.

Bei einer Sache kann man dir aber durchaus recht geben:
Cantor postuliert, daß die Liste vollständig wie oben(*) beschrieben bereits(!) aufgezählt ist.
Nun beschreibt er durch seinen Algorithmus einen Pointer in die "noch nicht" aufgezählten Zahlenbereiche hinein,
wobei er annimmt(!), daß die Grenzliste mit n aufgezählten Zahlen für n->unendlich identisch ist mit einer vollständigen Liste(was nicht bewisen ist).
Er zeigt, daß der beschriebene Pointer in einen Bereich zeigt, der niemals Null wird -> Grenzliste und vollständige Liste sind nicht identisch -> hat also einen Widerspruch herbeigeführt der zeigt, daß eine vollständige Liste nicht existiert(falsche Formulierung).
Es gibt also keine totalgeordnete Reihenfolge, die durch abzählen sicherstellt, daß jedes Element eine endliche Zeilennummer besitzt.
Abzählbare und überabzählbare Mengen verhalten sich also ähnlich wie offene und abgeschlossene Mengen; wo man wieder einen Bogen schlagen kann zu [0,unendlich] und [0,unendlich[.
Wäre R abgeschlossen im Mengentechnischen Sinn, hättest du durchaus recht, allerdings existiert keine vollständige Aufzählung aller reelen Zahlen.
Cantor beweist nicht, dass in einer vollständigen Liste nicht alle Zahlen vorkommen,
sondern beweist durch Widerspruch, dass so eine Liste nicht existiert; was den Blickwinkel der Konstruktivisten widerspiegelt.

Stelle dir einen Baum vor, dessen Äste sich jeweils nach einem Meter verzweigen.
Die Astgabeln(innere Knoten) kann man alle durchnummerieren(was den Zahlen in deiner Liste gleichkommt),
die hypotetischen(!) äußersten Astspitzen(das wären Cantors Diagonalzahlen) jedoch nicht.
Cantor beweist sozusagen, dass du durch umverteilen der Spitzen auf zusätzliche innere Astgabelungen, die Anzahl der Spitzen niemals vollständig eliminieren kannst.
Deshalb existiert kein Baum, der sowohl vollständig ist als auch keine Astspitzen besitzt, ganz egal wie seine inneren Knoten angeordnet sind oder wie oft sie sich teilen.
Ich hoffe das Beispiel ist gut nachzuvollziehen oder hilft etwas.

Noch etwas lustiges:
Mann kann alle inneren Knoten des Baumes vollständig totalordnen, also in einer Kette anordnen in der jedes innere Element maximal einen Vorgänger und genau einen Nachfolger hat.
Die "Astspitzen" sitzen sozusagen "am Ende" der Kette, können auch totalgeordnet werden. Sie bleiben aber trotzdem überabzählbar.
Könnte man die Astspitzen abzählen, wären sie innere Punkte und keine Spitzen.

Cantor sagt nicht, dass ein solcher Baum existiert. Er sagt auch nicht, dass ein solcher "vollständig" ausgewachsener Baum seine Astspitzen nicht beinhaltet.
Er sagt lediglich:
Wenn man annimmt der Baum sei "vollständig" ausgewachsen,
dann impliziert das, dass man seine Spitzen nicht zählen kann bzw diese durch Umstrukturierung des Baumes nicht restlos innere Knoten werden können.

[breaker]

Meine Liste fängt an, von 0,0 bis 0,9 zu zählen, springt dann an die erste Stelle zurück (0,0) und hängt einfach wieder die Zahlen 0-9 dran, springt dann an die zweite Stelle des ersten Blocks (0,1) und hängt wieder die Zahlen 0-9 dran usw., bis alle Kombinationen von 0,00 bis 0,99 gewonnen wurden. Danach wird analog alles für 0,000-0,999 durchgespielt und so geht es dann immer weiter, ad infinitum.

So bekommst Du in der Tat nur rationale Zahlen.

Dein Argument scheint nun so zu lauten: Wenn meine Zahlen nur endliche Länge haben, dann hat Cantors Zahl auch nur endliche Länge.
Das kannst du nicht so einfach sagen. Du konstruierst eine Menge; Cantor konstruiert eine einzige Zahl. Das sind völlig unterschiedliche Dinge.
Jede Zahl in Deiner Menge hat nur endlich viele Nachkommastellen und ist damit rational.
Wenn man aber eine einzige Zahl konstruiert, reicht es aus, jede der Nachkommastellen anzugeben.

[Skeltek]

Das kannst du nicht so einfach sagen. Du konstruierst eine Menge; Cantor konstruiert eine einzige Zahl.

Kann man das andere aber auch so einfach sagen?
Der Grenzwert (auf den der Restklassenalgorithmus von Cantor abzielt) ist für eine vollendete unendliche Länge nicht zwangsläufig von einer algebraischen Zahl unterscheidbar.
Das ist als würde man sagen (lim[n->unendlich] von 1/n = 0) aber (1/n != 0).

Cantor folgert aus (1/n != 0), dass (lim[n->unendlich] von 1/n auch != 0)
Entsprechend folgert er, daß aus der Unterscheidbarkeit einer endlichen Ziffernfolge die er generiert von einer algebraischen Zahl
automatisch die Unterscheidbarkeit der "vollendeten" unendlichen Diagonalzahl von einer algebraischen Zahl folgt.
Das ist als würde man analog sagen "unendlich ist keine ganze Zahl", was entsprechend nicht zwangsläufig Sinn machen muss, aber durchaus machen könnte.

[Pippen]

Cantor widerlegt sich doch so: Er nimmt eine Liste IR mit Zeilen an, wo die reellen Zahlen drin stehen und aufgelistet sind. Dann konstruiert er eine Diagonalzahl "0,x1x2..." mit jeweils einer (diagonalisierten) Stelle für eine Zeile der Liste, so dass jede Zeile der Liste von der Diagonalzahl unterschieden werden kann. Aber welche Diagonalzahl er mir auch konkret zeigt, meine Liste wird mind. eine weitere Zeile haben. Also muss er so tun, als ob seine Diagonalzahl unendlich-stellig ist. Aber dann ist auch die Liste unendlich-zeilig. Wie kommt Cantor darauf, diese beiden Unendlichkeiten so zu vergleichen, dass die unendlich-stellige Diagonalzahl alle Zahlen der unendlich-zeiligen Liste erfasst und nicht umgekehrt, die unendlich-zeilige Liste immer eine Zeile mehr auf Lager hat als die Diagonalzahl Stellen? Dann würde nämlich dieser Beweis nicht funktionieren.

[tomS]

Der Punkt ist, dass reelle Zahlen (und bereits rationale Zahlen) unendlich viele Dezimalzahlen haben müssen! Z.B. 1/3.

Cantor muss also von einer Liste ausgehen, die unendlich-stellige Zahlen enthält. Wie er zu dieser Liste gelangt ist gleichgültig, er nimmt ihre Existenz als gegeben an, und führt dies zusammen mit der zweiten Annahme der Abzählbarkeit zu einem Widerspruch.

Du gibst nun einen Algorithmus an, eine ganz bestimmte Liste zu konstruieren. Nach endlich vielen Schritten hast du aber nur endlich viele Zahlen erzeugt, und insbs. nur ganz bestimmte rationale Zahlen, so dass deine Liste aufgrund ihrer Konstruktion "zu klein" ist.

Wo in deiner Liste steht z.B. die Zahl 1/3 ?

[breaker]

Wie kommt Cantor darauf, diese beiden Unendlichkeiten so zu vergleichen, dass die unendlich-stellige Diagonalzahl alle Zahlen der unendlich-zeiligen Liste erfasst und nicht umgekehrt, die unendlich-zeilige Liste immer eine Zeile mehr auf Lager hat als die Diagonalzahl Stellen? Dann würde nämlich dieser Beweis nicht funktionieren.

1. Du tust immernoch so, als ob man die Liste im Nachhinein abändern dürfte. Sie wird aber als fest gegeben angenommen und genau deshalb funktioniert der Beweis.
1. Es ist auch nicht so, dass man die Zahl immer wieder nach endlich vielen Schritten mit der Liste vergleicht. Das würde überhaupt nichts zeigen. Aber der Grenzwert (d.h. die fertige Diagonalzahl mit unendlich vielen Stellen) liegt nicht in der Liste und das ist der wesentliche Punkt im Beweis.

[Pippen]

1. Wenn ich meinen Algorithmus unendlich oft anwende, dann müssen "hintenraus" unendliche Zahlen rauskommen, d.h. die Stelligkeiten der Zahlen "nähern sich der Unendlichkeit". Wenn ich von Eins beginnend unendlich oft um Eines weiterzähle (also: 1,2,3,4,...), dann müsste irgendwann eine unendliche Zahlenkette rauskommen (die nur deshalb keine nat. Zahl wäre, weil PA 2 einen Nachfolger fordert und dieser bei einer unendlichen Zahl nicht existieren kann).

2. Wir sind uns sicherlich einig, dass die Liste IR unendlich viele Zeilen hat, ja? Wir sind uns sicherlich auch einig, dass Cantor's konstruierte Diagonalzahl unendlich viele Stellen hat, wobei jede Stelle für eine bestimmte Zahl einer Listenzeile steht (um so sicherzustellen, dass sie von der Zahl in der Listenzeile unterschieden ist). Woher weiß Cantor, dass er mit den unendlich vielen Stellen der Diagonalzahl auf alle Zeilen der ja unendlichen Liste referiert? Zeigt nicht Hilbert's Hotel, dass das nicht geht und man selbst mit unendlich vielen Gästen das Hotel nicht voll bekommt? Nun, die Diagonalzahl sind hier die unendlich vielen Gäste und die Liste ist das Hotel...und damit klappt dieser Beweis nicht, auch für Nicht-Konstruktivisten.

[tomS]

1. Wenn ich meinen Algorithmus unendlich oft anwende, dann müssen "hintenraus" unendliche Zahlen rauskommen, ...

Ja, aber sicher nicht überabzählbar viele.

Dein Problem ist, dass dein Algorithmus höchstens abzählbar viele Zahlen konstruieren kann. Daher greift das Diagonalelement hier nicht. Das liegt aber nicht an letzterem, sondern an deinem Algorithmus.

2. ... Woher weiß Cantor, dass er mit den unendlich vielen Stellen der Diagonalzahl auf alle Zeilen der ja unendlichen Liste referiert?

Das ist genau der Kernpunkt seines Beweises. Er nimmt an, dass seine Liste vollständig ist. Dann konstruiert er seine Diagonalzahl so, dass sie auf jede Zeile referenziert. Und dann zeigt er, dass die Diagonalzahl selbst nicht in der Liste enthalten sein kann. Also Widerspruch zur Annahme.

Zeigt nicht Hilbert's Hotel, dass das nicht geht und man selbst mit unendlich vielen Gästen das Hotel nicht voll bekommt?

Das hat zunächst nichts miteinander zu tun. Z.B. ist die Liste der natürlichen Zahlen sicher vollständig, und Cantors Nummerierung der rationalen Zahlen ebenfalls.

...und damit klappt dieser Beweis nicht, auch für Nicht-Konstruktivisten.

Nochmal: Cantor will einen Widerspruch konstruieren, er will also tatsächlich, dass das nicht klappt.

[breaker]

1. Wenn ich meinen Algorithmus unendlich oft anwende, dann müssen "hintenraus" unendliche Zahlen rauskommen...

Hier musst du genau dazu sagen, wie dein Algorithmus gemeint ist. Wenn man alle Zahlen nimmt, die sich mit endlich vielen Schritten konstruieren lassen, kommen am Ende nur rationale Zahlen heraus (und nicht einmal alle davon, wie Toms Beispiel mit 1/3 zeigt).
Wenn es aber so gemeint ist, dass du zustzlich alle Grenzwerte von Folgen solcher Zahlen nimmst, dann bekommst du (wahrscheinlich) alle reellen Zahlen. Aber dann ist deine Konstruktionsvorschrift auch nicht mehr abzählbar.

Woher weiß Cantor, dass er mit den unendlich vielen Stellen der Diagonalzahl auf alle Zeilen der ja unendlichen Liste referiert?

Naja, man kann eben einen Beweis der Form
"Angenommen, die Diagonalzahl wäre in der Liste ... daraus folgt ... Widerspruch"
machen. Damit ist dann klar, dass sie nicht in der Liste liegt.

[Pippen]

Das ist genau der Kernpunkt seines Beweises. Er nimmt an, dass seine Liste vollständig ist.

...aber eben auch unendlich-zeilig!

Dann konstruiert er seine Diagonalzahl so, dass sie auf jede Zeile referenziert.

Präziser: Er konstruiert eine Diagonalzahl, die sich in n-Stellen von n-Zeilen der Listenzahlen unterscheidet. Weil aber die Liste nicht nur vollständig, sondern auch unendlich ist, kann man immer n+1-Zeilen hinzuzählen, so dass die Diagonalzahl die Liste nie vollständig erfassen würde. Wieso macht Cantor diese Überlegung nicht? Wieso geht Cantor wie von selbst davon aus, dass die Unendlichkeit der Diagonalzahlstellen die Unendlichkeit der Listenzeilen erfasst?

[Pippen]

Naja, man kann eben einen Beweis der Form
"Angenommen, die Diagonalzahl wäre in der Liste ... daraus folgt ... Widerspruch"
machen. Damit ist dann klar, dass sie nicht in der Liste liegt.

Wie kann man bei einer unendlichen Liste sagen, dass etwas dort nicht vorkommt, wenn die Liste gerade nie ein Ende hat?

[breaker]

Weil die Annahme, es läge in der Liste, zum Widerspruch führt.

[tomS]

Wie kann man bei einer unendlichen Liste sagen, dass etwas dort nicht vorkommt, wenn die Liste gerade nie ein Ende hat?

In der unendlichen Liste {2,4,6,...} kommt 1 sicher nie vor ;-)

Weil aber die Liste nicht nur vollständig, sondern auch unendlich ist, kann man immer n+1-Zeilen hinzuzählen, ...

Die Liste ist gemäß Annahme VOLLSTÄNDIG, also kann man eben KEINE Zeile mehr hinzufügen.

Natürlich kann man die Liste verlängern, aber dann wäre sie ja eben gerade NICHT vollständig.

Wieso geht Cantor wie von selbst davon aus, ...

Cantor will die Annahme der Vollständigkeit der abzählbaren Liste zum Widerspruch führen.

Cantor beweist schlüssig, dass KEINE ABZÄHLBARE Liste jemals ALLE reellen Zahlen umfassen kann. Es geht nicht um eine bestimmte Liste, sondern um alle überhaupt möglichen abzählbaren Listen.

[Pippen]

Die Liste ist gemäß Annahme VOLLSTÄNDIG, also kann man eben KEINE Zeile mehr hinzufügen.

Dann wäre sie doch aber endlich und das wäre genauso absurd.

@breaker: Mein Argument geht ja so: Wenn ich annehme, dass es eine unendlich-zeilige Liste IR gibt, die alle reellen Zahlen beinhaltet, dann kann ich keine reelle Diagonalzahl konstruieren, die beweisbar nicht in der Liste liegt. Grund: Die Liste hat unendlich viele Zeilen, d.h. wie viele Stellen meine Diagonalzahl auch hat, sie wird per definitionem nie alle Zeilen der Liste erfassen können. Dann gibt es keinen Widerspruch mehr. Die Annahme der vollständigen Liste wäre verträglich mit dem Scheitern, eine reelle Zahl zu konstruieren, die nicht in der Liste liegen kann. Ich verstehe nicht, wie Cantor bzw. ihr hier denkt.

[Skeltek]

null komma periode neun gleich eins.

Das einzige was am Beweis bemängelbar ist wäre, dass automatisch angenommen wird, dass ein Ziffernunterschied der sich im potentiell unendlichen befindet eine andere Zahl bedeutet(darauf wird nicht näher eingegangen, was aber nicht falsch sein muss).
Der Rest ist soweit völlig korrekt.
Cantor hat bewiesen, dass eine vollständige Liste nicht existiert(vollständig in dem Sinn wie vollendet, abgeschlossen).
Gerade binär kann man sehen, dass Cantors Diagonalzahl durch ihre rekursive Definition mit ihrer Konstruktionsvorschrift immer der Liste voraus ist.


Neuer Erklärungsversuch
Angenommen deine Liste deckt alle endlichen Algorithmen ab oder anschaulich besser:
1: Es sei [m;m+1] die Koordinate der differierenden Ziffer wenn deine Liste(ihr Algorithmus) so gestaltet ist, dass deine Zahlen der Diagonalzahl immer genau eine Stelle "hinterher" sind.
Wenn du annimmst, deine Liste sei komplett, dann befindet sich deine Zahl genau in der Reihe mit der Nummer m mit (m/m+1)=1, nämlich genau dann, wenn der Winkel zur differierenden Stelle 45° wird, der nummerische Wertunterschied wird dort Null.
Das passiert jedoch erst "im Unendlichen", weshalb die Zahl einfach nicht in der Liste vorkommen kann.
Deshalb gibt es keine aktual unendlichen Listenlängen.

Jetzt im Vergleich:
2: Würde deine Liste nicht nur den oberen, sondern ALLE möglichen Algorithmen zur Generierung von möglicher Diagonalzahlen abdecken, würde jede Zeile die der Diagonalzahl "hinterher jagd" auf der Liste ultraexponentiel nach unten rücken.
Hier würdest du mindestens m! Zeilen benötigen um eine Zahl zu generieren, die mit nur m+1 Zeilen der Diagonalzahl übereinstimmt(Habe m! der Einfachheit halber gewählt; m repräsentativ für die Komplexität der Konstruktionsvorschrift). Dann wäre die Reihe mit der Nummer m mit (m!/m+1)=1 die gesuchte Diagonalzahl.

Wie man bei 1 annehmen könnte, jagd hier die Unendlichkeit der Reihennummern der Unendlichkeit der Diagonalzahllänge nur knapp hinterher.
Wie man jedoch bei 2 sieht, gibt es einen deutlichen Unterschied:
lim[m->unendlich](m/m+1)=1
lim[m->unendlich](m!/m+1)=unendlich
Dies spiegelt sich in den unterschiedlichen Mächtigkeiten von N und R wieder, da die Anzahl der möglichen Konstruktionsvorschriften für Diagonalzahlen mit zunehmendem m steigt.

Die Gesammtheit aller Diagonalzahlen rückt so gesehen an das Ende deiner hypotetischen aktual unendlich langen Liste.Ähnlich wie bei einem Zweig der sich unendlich oft teilt, lassen sich durch "umkleben" aller Verzweigungen sämmtliche Knoten eliminieren. Trotzdem hat der Baum "im Unendlichen" unendlich viele Spitzen.

Wie kann man bei einer unendlichen Liste sagen, dass etwas dort nicht vorkommt, wenn die Liste gerade nie ein Ende hat?

Das ist der Punkt, die gesuchte Zahl befindet sich theoretisch "am" bzw hinter dem Ende der unendlich langen Liste. Sie kann darin dann gar nicht vorkommen.


Habe mich mit dem Thema Jahre beschäfftigt, allerdings ist es schwer eine gute Erklärung zu finden, wenn man nicht auf die Standardbeispiele und Standarderklärungen zurückgreift
Schönen Gruß, Skel

[tomS]

Die Liste ist gemäß Annahme VOLLSTÄNDIG, also kann man eben KEINE Zeile mehr hinzufügen.

Dann wäre sie doch aber endlich und das wäre genauso absurd.

Nö, wieso?

Betrachten wir doch eine abzählbar unendliche und vollständige Liste der natürlichen Zahlen, also {1,2,3,...}. Diese Liste ist vollständig, da jedes n bereits enthalten ist. Du kannst also keinen Eintrag mehr hinzufügen.

Genau im selben Sinne kannst du auch eine abzählbar unendliche und vollständige Liste der rationalen Zahlen konstruieren.

Cantor zeigt, dass eine in diesem Sinne abzählbar unendliche und zugleich vollständige Liste der reellen Zahlen prinzipiell nicht existieren kann. Das hat wenig mit Hilberts Hotel zu tun, das verwirrt dich hier nur.

[breaker]

@breaker: Mein Argument geht ja so: Wenn ich annehme, dass es eine unendlich-zeilige Liste IR gibt, die alle reellen Zahlen beinhaltet, dann kann ich keine reelle Diagonalzahl konstruieren, die beweisbar nicht in der Liste liegt. Grund: Die Liste hat unendlich viele Zeilen, d.h. wie viele Stellen meine Diagonalzahl auch hat, sie wird per definitionem nie alle Zeilen der Liste erfassen können. Dann gibt es keinen Widerspruch mehr. Die Annahme der vollständigen Liste wäre verträglich mit dem Scheitern, eine reelle Zahl zu konstruieren, die nicht in der Liste liegen kann. Ich verstehe nicht, wie Cantor bzw. ihr hier denkt.

Das Ganze wird wieder auf das gleiche Problem hinauslaufen, dass du früher schonmal hattest. Der Widerspruchsbeweis geht grob so:
Angenommen, die Diagonalzahl läge in der Liste. Daraus folgt, dass sie an irgendeiner (endlichen) Stelle steht. Nennen wir diese Stelle N. Nach Konstruktion der Diagonalzahl wissen wir aber, dass sie sich an der N-ten Nachkommastelle von der Zahl unterscheidet, die in der Liste an Stelle N steht. Widerspruch.
Also muss die Annahme falsch gewesen sein. Diese war, dass die Diagonalzahl in der Liste liegt.

[Skeltek]

Betrachten wir doch eine abzählbar unendliche und vollständige Liste der natürlichen Zahlen, also {1,2,3,...}. Diese Liste ist vollständig, da jedes n bereits enthalten ist. Du kannst also keinen Eintrag mehr hinzufügen.

Man kann ans Ende der Liste was hinzufügen

Mal eine ganz andere Frage:
Können eine Folge rationaler Zahlen und eine Folge "Diagonalzahlen" auf denselben Grenzwert zustreben? ^^
Wenn man zwei solche Folgen hat, ist entscheidbar ob sie denselben Grenzwert haben? Ist der Grenzwert eine Diagonalzahl oder eine rationale Zahl?
Ist es sinnvoll in dem Kontext überhaupt von rational zu sprechen? Per Definition sollen ja Nenner und Zähler endliche natürliche Zahlen sein...
Soll jetzt nicht zur Diskussion anregen, aber ich dachte ich schreibe es mal auf wo mir die Fragen so geschickt einfallen, vielleicht für eine etwaige spätere Diskussion/Ideensammlung.

[tomS]

Betrachten wir doch eine abzählbar unendliche und vollständige Liste der natürlichen Zahlen, also {1,2,3,...}. Diese Liste ist vollständig, da jedes n bereits enthalten ist. Du kannst also keinen Eintrag mehr hinzufügen.

Man kann ans Ende der Liste was hinzufügen ;-)

Nein, kann man nicht. Zumindest keine neue natürliche Zahl, da diese bereits alle enthalten sind.

Der Beweis von Cantor geht davon aus, dass diese abzählbar unendliche und zugleich vollständige Liste für natürliche Zahlen existiert (und nicht durch endliche Algorithmen elementweise erzeugt werden muss). Wenn das bereits eine problematische Vorstellung für euch ist, dann ist es ziemlich sinnlos, über seinen Beweis zur Überabzählbarkeit der reellen Zahlen nachzudenken.

[Skeltek]

Ich merke du erkennst ernst gemeinte Aussagen wenn ich sie mache. Hinter das letzte Element einer unendlich langen Liste kann man stellen was und wieviel man will, muss nicht zwangsläufig eine algebraische Zahl sein.

[tomS]

Gut, also dann

{1,2,3,...,n,..."Bratwurst","Schweinsbraten",...}

Aber bringt nix ;-)