Wie definiert man eine überabzählbare Menge?
Hi, ich bin auf folgenden Satz gestoßen:
"Cantor bewies, dass die Menge der algebraischen reellen Zahlen (in moderner Sprechweise) abzählbar ist, während die Menge aller reellen Zahlen überabzählbar (unendlich, aber nicht abzählbar) ist."
Nun konnte ich keine für mich sinnvolle Erklärung finden, was der Unterschied zwischen 'unendlich' und 'unendlich aber nicht zählbar' ist.
Kann mir das jemand verständlich erklären?
3 Antworten
Abzählbar unendlich heißt, man kann alle Elemente der Menge durchnumerieren.
Cantor hat nun gesagt: Wenn mir einer kommt und behauptet, er habe eine Liste gefunden, die alle reellen Zahlen enthält, dann konstruiere ich ihm schnell eine reelle Zahl, die er vergessen hat und entlarve ihn damit als Lügner.
Fazit: Es gibt keine Aufzählung aller reellen Zahlen; diese sind also nicht abzählbar, sondern viel mehr.
Einzeln Aufschreiben funktioniert natürlich nur bei endlichen Mengen. Man darf aber auch ein eindeutiges Regelwerk angeben, mit dem man zu jedem n∈ℕ ein rₙ∈ℝ eindeutig bestimmen kann.
Hier hast Du zwei Beispiele für eine Abbildung ℕ→[0,1[:
- Für 2ⁱ ≤ n < 2ⁱ⁺¹ wähle rₙ := n ∕ 2ⁱ - 1
- Wähle rₙ := sin(n)
Bei 1) sieht man sofort, dass z.B. alle irrationalen Zahlen fehlen. Bei 2) wird es schon kniffliger. Ob ein gegebenes r als Bild auftreten kann, ist allgemein nicht in endlicher Zeit herauszufinden.
Aber mit Cantors zweitem Diagonalargument kann man in beiden Fällen ein r konstruieren, das garantiert von keinem n erwischt wird. Deshalb ist die Menge [0,1[ mächtiger als ℕ (also überabzählbar).
Nun konnte ich keine für mich sinnvolle Erklärung finden was der
unterschied zwischen 'unendlich' und 'unendlich aber nicht zählbar' ist.
Ich würde nicht sagen, dass die Menge der Reellen Zahlen »unendlich, aber nicht abzählbar«, sondern eher, dass die Menge der Rationalen Zahlen und sogar die Menge aller algebraischen Zahlen (√2 oder Φ (Goldener Schnitt) eingeschlossen) unendlich, aber abzählbar ist.
Das finde ich nämlich noch wesentlich erstaunlicher. Die Nichtabzählbarkeit der Menge aller Reellen Zahlen hingegen geht gleichsam in dieselbe Richtung wie die Unendlichkeit schon, nur mindestens einen Schritt weiter.
Zur Frage selbst:
Der Vergleich zwischen zwei Mengen hinsichtlich ihrer Kardinalität, der Zahl ihrer Elemente (respektive deren Verallgemeinerung auf unendliche Kardinalzahlen), lässt sich dadurch formalisieren, dass man versucht, eine Bijektion zwischen beiden Mengen zu finden, eine sowohl umkehrbar eindeutige (injektive) als auch vollständige (surjektive) Abbildung.
Eine Abbildung kann man sich durch das Verteilen von Murmeln auf Mulden vorstellen. Es ist schlicht unmöglich, eine Murmel in zwei verschiedene Mulden gleichzeitig zu legen, und das macht eine Abbildung aus. Injektiv heißt nun, dass in jeder Mulde höchstens eine Murmel liegt, surjektiv heißt, dass in jeder Mulde mindestens eine liegt, und bijektiv heißt natürlich, dass es genau eine ist.
Sind zwei Mengen A und B gleich mächtig, so gibt es eine Bijektion zwischen beiden. Im endlichen Fall ist jede injektive Abbildung auch surjektiv und umgekehrt, was im Unendlichen nicht der Fall zu sein braucht, aber zumindest gibt es eine Bijektion. Ist A mächtiger als B, so gibt es keine injektive, ist B mächtiger, keine surjektive Abbildung A→B.
Die Menge N der Natürlichen Zahlen ist unendlich, aber im Prinzip würde man jede Natürliche Zahl früher oder später erwähnt haben, wenn man nur auch unendlich viel Zeit dazu hätte.
Abzählbar unendlich ist eine Menge M dann, wenn es eine Bijektion N→M gibt.
Überabzählbar unendlich ist eine Menge M dann, wenn man die Nicht-Surjektivität einer beliebigen Abbildung N→M unabhängig von deren konkreten Eigenschaften zeigen kann, dass also anschaulich gesprochen immer mindestens eine Mulde (und dann sind es auch unendlich viele) leer bleibt.
Genau das hat Cantor gemacht.
Dieser Beweis ist falsch. Das steht seit hundert Jahren falsch in den Schulbüchern drin. Der Gödelsche Unvollständigkeitssatz resultiert daraus.
Es sollte bewiesen werden, das die Menge der reellen Zahlen größer ist als die der natürlichen Zahlen. Dadurch wird eine Zuordnung vorgenommen, eine Liste aller reelen Zahlen, zuerst eine erste reelle Zahl, dann eine zweite usw., also für jede natürliche Zahl ein Platz für eine reelle Zahl. Geht das?
Cantor hat eine angenommen, es gäbe eine Liste aller reeller Zahlen, schön durchnummeriert mit den natürlichen Zahlen.
Jetzt hat er eine neue Zahl so konstruiert, das sie zu allen Zahlen in dieser Liste sich unterscheidet: die n-te Ziffer der neuen Zahl ist ungleich der n-ten Ziffer der n-ten Zahl der Liste.
Was er dabei übersah: Diese neue Zahl müsste ja schon in der Liste sein, wenn diese vollständig wäre. Damit wäre die Zahl aber undefiniert an dieser Stelle, denn diese Ziffer kann ja nicht ungleich sich selbst sein. Damit ist der ganze Beweis hinfällig..
Auch kann man tatsächlich eine solche Liste aller reellen Zahlen anlegen, die mit den natürlichen Zahlen durchnummeriert werden:
Man nehme eine Definition der Zahl, wandle diese in Text um (z.B. pdf-datei), und diese Datei dann als riesige natürliche Zahl.
Da jede reelle Zahl eine endliche Definition hat, hat sie auch eine endliche natürliche Zahl, und damit einen wohldefinierten Platz in der Liste.
Was er dabei übersah:
Er hat es nicht übersehen, sondern zeigt mit dem Finger auf diesen Widerspruch.
Damit ist der ganze Beweis hinfällig..
Nicht der ganze Beweis, sondern nur die Beweisannahme "ℝ ist abzählbar".
Da jede reelle Zahl eine endliche Definition hat
Falsch: das sind nur die berechenbaren Zahlen, und davon gibt es natürlich nur abzählbar viele (genau wie Turingmaschinen). Aber schon der Grenzwert einer konvergenten Folge solcher Zahlen muss selbst nicht mehr berechenbar sein. Erst bei den reellen Zahlen hört dieser Spuk auf: die sind wirklich vollständig.
Ah, sie kennen den Beweis über die Diagonalzahl, sehr gut.
Um eine Annahme mit einem Gegenbeispiel zu widerlegen, muss das Gegenbeispiel existieren. Der Existensbeweis ist also Pflicht.
Was fehlt, ist der Existenzbeweis der Diagonalzahl.
Sei z[i] eine Folge der reellen Zahlen im Intervall (0,1).
Falls die Diagonalzahl existiert, gibt es eine natürliche Zahl p, sodaß z[p] gleich dieser Diagonalzahl ist.
Damit ist die p-te Stelle der Diagonalzahl so definiert:
falls die Stelle 5 ist, ist sie 4, und falls sie 4 ist, ist sie 5.
Widerspruch, die Diagonalzahl existiert also nicht, weil ihre Definition sich selbst widerspricht.
Ein Widerspruchsbeweis widerlegt immer die Annahme. Bei Cantor war die Annahme, das die Folge der reellen Zahlen existiert. Was er unterschlug war die Annahme, das die Diagonalzahl existiert. Zu einem Widerspruchsbeweis darf es aber immer nur genau eine Annahme geben, nicht zwei.
Oder als Beispiel: Angenommen, es gibt eine Menge aller Elefanten. Sei e ein fliegender Elefant. e ist nicht in der Menge aller Elefanten. Also gibt es keine Menge aller Elefanten.
Euklids Beweis über die Unendlichkeit der Primzahlen ist dann genauso falsch? Er nimmt eine endliche Liste von Pz an, multipliziert sie und addiert 1. D.h. er konstruiert eine Zahl, die er aber nicht explizit aufschreibt.
Genauso konstruiert Cantor eine reelle, nicht endliche Zahl aus der in einer definierten Reihenfolge aufgeschriebenen Liste von reellen Zahlen. Die Zahl müsste es geben, wenn die Liste vollständig wäre. Es gibt sie aber nicht, also ist die Liste unvollständig.
Sein Denkfehler liegt hier:
Falls die Diagonalzahl existiert, gibt es eine natürliche Zahl p, sodaß z[p] gleich dieser Diagonalzahl ist.
Das gilt eben nur unter der (falschen) Annahme, dass z vollständig ist. Und damit lässt sich natürlich alles beweisen; z.B. dass p nicht existiert, 4=5 ist, oder dass Trump ein guter Präsident wird :-)
@schachpapa:
Den Euklidschen Beweis kann man genauso Ad Absurum führen, wenn man die Beschränkung auf endliche Listen entfernt.
Wenn m eine beliebige Liste von Primzahlen ist, und p dann das Produkt dieser Zahlen plus 1 ist, dann war p nicht in dieser Menge enthalten, also kann die Liste nicht vollständig gewesen sein, also muss die Menge der Primzahlen überabzählbar sein.
@ralphdieter:
Woher weiss man, welche Annahme falsch ist, die Annahme das es möglich ist alle reellen Zahlen aufzulisten, oder die Annahme das die Diagonalzahl existiert?
Das verwirrt mich. Wenn jetzt jemand kommt und meint, er hätte eine Liste aller natürlichen Zahlen könnte ich doch auch einfach irgendeine natürliche Zahl nennen die nicht auf der Liste ist, da die natürlichen Zahlen unendlich sind und er mindestens eine nicht aufgeschrieben haben kann.