Cantor-Diagonalisierung

Zum Verständnis der Problematik und des ist es notwendig die unspezifizierte Größe einer Menge durch die in der Mengenlehre formal definierte Mächtigkeit zu ersetzen:

Zwei Mengen sind genau dann gleichmächtig jedem Element der einen Menge genau ein der anderen Menge zugeordnet werden kann und ebenso wenn also eine Bijektion zwischen den Mengen existiert.

Beispielsweise sind die Menge der natürlichen und die Menge der positiven geraden Zahlen denn man kann ein-eindeutig jeder natürlichen Zahl i gerade ihre Doppeltes 2·i zuordnen.

Vorgehen bei der Cantor-Diagonalisierung

Cantors Verfahren wird am besten mit einfachsten unendlich großen Menge den natürlichen Zahlen und den positiven Brüchen (siehe Rationale Zahlen ) veranschaulicht. Die Aussage ist dass die Zahlen und die positiven Brüche gleichmächtig sind.

Dies lässt sich zeigen indem man Brüche folgendermaßen in einem zweidimensionalen Schema anordnet:

 1/1 1/2 1/3 1/4 1/5 ... 2/2 2/3 2/4 2/5 ... 3/1 3/2 3/4 3/5 ... 4/1 4/2 4/3 ... 5/2 ... ...  

und dieses Schema dann 'diagonal' durchläuft wobei man kürzbare Brüche überspringt:

 1.-> 2. 5.-> 6. 11. -> / / / / / / / 3. (-) 7. (-) | / / | / / / 4. 8. (-) / / / 9. (-) | / / 10.  

Man erhält auf diese Weise eine der positiven rationalen Zahlen:

1 1/2 2 3 1/3 1/4 3/2 4 5 1/5 ...

Um nun alle rationalen Zahlen in zu den natürlichen Zahlen zu setzen erweitert die eben gefundene Abzählung um die Null die negativen Brüche:

0 1 -1 1/2 -1/2 2 3 -3 1/3 -1/3 1/4 -1/4 2/3 ...

Mengen welche gleichmächtig zu einer beschränkten der natürlichen Zahlen sind sind endlich . Mengen welche gleichmächtig zur Menge der Zahlen sind heißen abzählbar unendlich (bzw. abzählbar ). Mengen welche gleichmächtig zu irgendeiner Teilmenge natürlichen Zahlen sind heißen abzählbar (bzw. höchstens abzählbar ).

Weitere Beispiele sowie das Cantorsche Diagonalverfahren sind auch im Artikel Hilberts Hotel veranschaulicht.

Mächtigkeit der reellen Zahlen

Die Menge R der reellen Zahlen ist zur Menge der natürlichen Zahlen gleichmächtig. Ihre Mächtigkeit wird als überabzählbar bezeichnet. Man sagt auch die reellen haben die Mächtigkeit des Kontinuums .

Der Beweis der Überabzählbarkeit von R ist Inhalt des zweiten Cantorschen Diagonalbeweises . Siehe dazu den Artikel überabzählbar.

Verallgemeinerung der Cantor-Diagonalisierung

Die erste Cantor-Diagonalisierung kann man verallgemeinern vergleichbare Aussagen über Mengen von Tupeln reeller Zahlen zu machen.

Die folgende Darstellung ist nicht die 'Cantor-Diagonalisierung' sondern eher eine Vorschrift zum Erstellen 'fraktalen' Objektes.

Georg Cantor hat gezeigt dass es Kurven (1-dimensionale Objekte) gibt die Flächen (2-dimensionale Objekte) füllen können und zwar

Man nehme eine quadratische Fläche die durch die Eckpunkte (0 und (3 3) aufgespannt ist. Man ziehe Strecke von (0 0) nach (3 3).

Diese Kurve innerhalb des Quadrates ändere nun so ab: Man teile die quadratische in ein Raster 9 gleichgroßer Quadrate. Man den Kurvenverlauf nun so ab dass folgende die Endpunkte von Teilstrecken bilden:

(0 0) - (1 1) - 2) - (1 3) - (2 2) (1 1) - (2 0) - (3 - (2 2) - (3 3)

Die Kurve hat danach folgendes Aussehen:

Die abgeänderte Kurve hat die Eigenschaft sie ebenfalls das Quadrat durchzieht und den Anfangs- und den selben Endpunkt hat.

Dieses Verfahren wiederhole man nun für der kleinen Teil-Quadrate und die daraus entstandenen und so weiter. Der Grenzwert dieses Verfahrens eine Kurve die das gesamte Quadrat ausfüllt.

Diese (unendlich lange) Grenzkurve ist Bild stetigen Abbildung φ vom Intervall [0 1]. Dazu setzt man zunächst Endpunkte φ(0) = (0 0) φ(1) = 3). Im zweiten Schritt setzt man die der ersten Verfeinerung:

 0 -> (0 0) 1/9 -> 1) 2/9 -> (0 2) 3/9 -> 3) 4/9 -> (2 2) 5/9 -> 1) 6/9 -> (2 0) 7/9 -> 1) 8/9 -> (2 2) 1 -> 3)  

Dann setzt man in jedem Schritt hinzukommenden Eckpunkte auf Werte zwischen den bisherigen Die Grenzkurve ist dann genau das Bild so definierten Abbildung φ. Beachte dass dies Bijektion von [0 1] auf [0 3]×[0 ist da die Abbildung zwar surjektiv aber nicht injektiv ist; z.B. ist φ(1/9) = φ(5/9).

Während die Zahl eindimensional ist sind zugehörigen Koordinaten zweidimensional. Folglich kann man eindimensionale in mehrdimensionale Zahlen überführen und umgekehrt. Mengen Elemente sind somit nicht mächtiger als Mengen Elemente.

Dieser Umstand hatte einige Mathematiker zu Zeit als die Cantor-Diagonalisierung vorgestellt wurde tief gemacht weil diese Erkenntnis nicht der Intuition

Bücher zum Thema Cantor-Diagonalisierung

Dieser Artikel von Wikipedia unterliegt der GNU FDL.