Cantor-Diagonalisierung

Stichpunkte

Allgemein
	auch Cantorsches Diagonalverfahren genannt
	Die Cantor-Diagonalisierung
	mit dem man zeigen kann
	ist ein mathematisches Beweisverfahren
	ob zwei Mengen gleichmächtig sind
	Angewendet wird es insbesondere bei unendlichen Mengen
	Entwickelt wurde dieses Verfahren von Georg Cantor
	wenn jedem Element der einen Menge genau ein Element der anderen Menge zugeordnet werden kann
	und umgekehrt ebenso
	wenn also eine Bijektion zwischen den Mengen existiert. Während dies bei Mengen mit endlich vielen Elementen klar ist ({1
	10} sind gleichmächtig)
	die unspezifizierte Größe einer Menge durch die in der Mengenlehre formal definierte Mächtigkeit zu ersetzen: Zwei Mengen sind genau dann gleichmächtig
	3} und {6
	8
	wird bei Mengen mit unendlich vielen Elementen die Problematik offensichtlich
	2
	Zum Verständnis der Problematik und des Beweises ist es notwendig
	"Verbergen") 1 Vorgehen bei der Cantor-Diagonalisierung 2 Mächtigkeit der reellen Zahlen 3 Verallgemeinerung der Cantor-Diagonalisierung 4 Verwandte Themen [Bearbeiten]
	denn man kann ein-eindeutig jeder natürlichen Zahl i ihr Doppeltes 2·i zuordnen. Inhaltsverzeichnis showTocToggle("Anzeigen"
	Beispielsweise sind die Menge der natürlichen Zahlen und die Menge der positiven geraden Zahlen gleichmächtig
Vorgehen bei der Cantor-Diagonalisierung
	und den positiven Brüchen (siehe Rationale Zahlen) veranschaulicht
	den natürlichen Zahlen
	Cantors Verfahren wird am besten mit der einfachsten unendlich großen Menge
	dass die natürlichen Zahlen und die positiven Brüche gleichmächtig sind
	Die Aussage ist
	2
	1/3
	3/2
	4
	3
	1/4
	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 Abzählung der positiven rationalen Zahlen: 1
	indem man die Brüche folgendermaßen in einem zweidimensionalen Schema anordnet: 1/1 1/2 1/3 1/4 1/5 ... 2/1 2/2 2/3 2/4 2/5 ... 3/1 3/2 3/3 3/4 3/5 ... 4/1 4/2 4/3 ... 5/1 5/2 ... ... und dieses Schema dann 'diagonal' durchläuft (abzählt)
	1/2
	... Durch das Überspringen kürzbarer Brüche liegt für jede positive rationale Zahl genau ein Repräsentant (der nicht mehr kürzbare Bruch) in dieser Abzählung
	Dies lässt sich zeigen
	1/5
	5
	wodurch die gewünschte Bijektion hergestellt ist
	2/3
	-1
	1/2
	sind endlich
	1
	erweitert man die eben gefundene Abzählung um die Null und die negativen Brüche: 0
	-1/2
	2
	-2/3
	welche gleichmächtig zu einer beschränkten Teilmenge der natürlichen Zahlen sind
	-2
	-1/3
	-1/4
	-3
	2/3
	... Mengen
	1/3
	3
	Um nun alle rationalen Zahlen in Bijektion zu den natürlichen Zahlen zu setzen
	1/4
	welche gleichmächtig zur Menge der natürlichen Zahlen sind
	heißen abzählbar unendlich (bzw. abzählbar)
	Mengen
	welche gleichmächtig zu irgendeiner Teilmenge der natürlichen Zahlen sind
	Mengen
	heißen abzählbar (bzw. höchstens abzählbar)
	Weitere Beispiele sowie das Cantorsche Diagonalverfahren selbst sind auch im Artikel Hilberts Hotel veranschaulicht. [Bearbeiten]
Mächtigkeit der reellen Zahlen
	Die Menge R der reellen Zahlen ist zur Menge der natürlichen Zahlen nicht gleichmächtig
	Ihre Mächtigkeit wird als überabzählbar bezeichnet
	Man sagt auch
	die reellen Zahlen haben die Mächtigkeit des Kontinuums
	Der Beweis der Überabzählbarkeit von R ist Inhalt des zweiten Cantorschen Diagonalbeweises. [Bearbeiten]
Verallgemeinerung der Cantor-Diagonalisierung
	um vergleichbare Aussagen über Mengen von Tupeln reeller Zahlen zu machen
	Die erste Cantor-Diagonalisierung kann man verallgemeinern
	Die folgende Darstellung ist nicht die traditionelle 'Cantor-Diagonalisierung'
	sondern eher eine Vorschrift zum Erstellen eines 'fraktalen' Objektes
	und zwar so: Man nehme eine quadratische Fläche
	Georg Cantor hat gezeigt
	0) und (3
	dass es Kurven (1-dimensionale Objekte) gibt
	die durch die Eckpunkte (0
	3) aufgespannt ist
	die Flächen (2-dimensionale Objekte) füllen können
	3). Diese Kurve innerhalb des Quadrates ändere man nun so ab: Man teile die quadratische Fläche in ein Raster 9 gleichgroßer Quadrate
	0) nach (3
	Man ziehe eine Strecke von (0
	0) - (1
	3) - (2
	2) - (3
	0) - (3
	dass sie ebenfalls das Quadrat durchzieht und den selben Anfangs- und den selben Endpunkt hat
	3) Die Kurve hat danach folgendes Aussehen: Die abgeänderte Kurve hat die Eigenschaft
	2) - (1
	Man ändere den Kurvenverlauf nun so ab
	2) - (1
	dass folgende Punkte die Endpunkte von Teilstrecken bilden: (0
	1) - (0
	1) - (2
	1) - (2
	und die daraus entstandenen Teil-Quadrate und so weiter
	Dieses Verfahren wiederhole man nun für jedes der kleinen Teil-Quadrate
	Der Grenzwert dieses Verfahrens ist eine Kurve
	die das gesamte Quadrat ausfüllt
	1]
	Diese (unendlich lange) Grenzkurve ist Bild einer stetigen Abbildung φ vom Intervall [0
	3)
	φ(1) = (3
	Dazu setzt man zunächst die Endpunkte φ(0) = (0
	0)
	1) 8/9 -> (2
	0) 1/9 -> (1
	1) 6/9 -> (2
	2) 1 -> (3
	3) 4/9 -> (2
	0) 7/9 -> (3
	Im zweiten Schritt setzt man die Eckpunkte der ersten Verfeinerung: 0 -> (0
	2) 3/9 -> (1
	3) Dann setzt man in jedem Schritt die hinzukommenden Eckpunkte auf Werte zwischen den bisherigen Zahlen
	2) 5/9 -> (1
	1) 2/9 -> (0
	Die Grenzkurve ist dann genau das Bild der so definierten Abbildung φ
	da die Abbildung zwar surjektiv
	3] ist
	3]×[0
	1] auf [0
	dass dies keine Bijektion von [0
	aber nicht injektiv ist; z.B. ist φ(1/9) = φ(5/9)
	Beachte
	Während die Zahl eindimensional ist
	sind die zugehörigen Koordinaten zweidimensional
	Folglich kann man eindimensionale Zahlen in mehrdimensionale Zahlen überführen und umgekehrt
	Mengen mehrdimensionaler Elemente sind somit nicht mächtiger als Mengen eindimensionaler Elemente
	Dieser Umstand hatte einige Mathematiker zu der Zeit
	tief unglücklich gemacht
	weil diese Erkenntnis nicht der Intuition entspricht. [Bearbeiten]
	als die Cantor-Diagonalisierung vorgestellt wurde
Verwandte Themen
	Cantorsche Paarungsfunktion en:Cantor's diagonal argument fr:Argument de la diagonale de Cantor he:×”×?לכסון של קנטור ja:カントールã?®å¯¾è§’線論法 nl:Diagonaalbewijs van Cantor pl:Rozumowanie przekÄ…tniowe

Dieser Artikel basiert auf dem Artikel Cantor-Diagonalisierung aus der freien Enzyklopädie wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der wikipedia ist eine Liste der Autoren verfügbar.