Hallo,
hat eigentlich jemand den Beweis verstanden, wieso IR nicht abzählbar ist? Wenn ja, wärs toll, wenn der Betreffende mir das mal erklären könnte. Ich steig da irgendwie nicht dahinter.
Gruß
OLIVER
Hi,
wenn es sich um den berühmten Cantorschen „Diagonalbeweis“ handelt: Viel Zeit nehmen und Schritt für Schritt durcharbeiten. Nicht Schritt n+1 zuwenden, wenn Du Schritt n noch nicht genau verstanden hast (auch, wenn’s sich banal anhört). Mit einer gewissen Investition von Zeit, Geduld und Gehirnschmalz kann den Beweis jeder verstehen.
Mit freundlichem Gruß
Martin
Hallo Oliver,
Ich versuche mal, den Beweis etwas ‚normaler‘ als üblich zu formulieren, vielleicht hilft’s:
Du betrachtest alle reellen Zahlen zwischen 0 und 1 und zeigst, dass bereits diese überabzählbar sind, wie folgt:
Angenommen, die reellen Zahlen zwischen 0 und 1 wären abzählbar.
Dann existiert also eine Abzählung und nach dieser kann man sie in eine vollständige ‚Liste‘ schreiben:
(so ungefähr:smile:
0,036478655667535678000000
0,723456845767869566646365656…
0,5496457685768659767658665466
0,4436765757887687
…
Nun konstruiere eine (weitere) reelle Zahl nach folgender Vorschrift:
Nehme die ‚Diagonale‘, also aus der n-ten Zeile die n-te (Dezimal-)Ziffer, und addiere jeweils 1 (aus 9 wird 0)
In meinem Beispiel wäre der Anfang der Diagonalen 0,0296…
und 1 auf jede Ziffer addiert ergibt 0,1307…
(Jetzt kommt’s:smile:
Diese konstruierte Zahl ist wiederum eine reelle Zahl zwischen 0 und 1, müsste also in der Liste auftauchen,
aber sie kann nicht in der Liste auftauchen, denn dann müsste sie eine Position in der Liste haben (z.B. x) und ihre x-te Stelle wäre laut Liste eine Ziffer d, aber laut obiger Konstruktion d+1. Widerspruch.
qed.
Peace, Kevin.
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Diese konstruierte Zahl ist wiederum eine reelle Zahl zwischen
0 und 1, müsste also in der Liste auftauchen,
aber sie kann nicht in der Liste auftauchen, denn dann müsste
sie eine Position in der Liste haben (z.B. x) und ihre x-te
Stelle wäre laut Liste eine Ziffer d, aber laut obiger
Konstruktion d+1. Widerspruch.qed.
Peace, Kevin.
Hallo Kevin,
soweit hab ich’s verstanden, aber geht denn dieser Beweis nicht auch für rationale Zahlen? Diese sollten jedoch abzählbar sein!
OLIVER
Hallo Kevin,
soweit hab ich’s verstanden, aber geht denn dieser Beweis
nicht auch für rationale Zahlen? Diese sollten jedoch
abzählbar sein!OLIVER
Nein, damit zeigst Du h"ochstens, dass der konstruierte Dezimalausdruck keine rational Zahl sein kann.
"Ubrigens muss man sich noch vor 9-er Perioden sch"utzen, also z.B. auch die 8 durch die 0 ersetzen.
Ciao Lutz
soweit hab ich’s verstanden, aber geht denn dieser Beweis
nicht auch für rationale Zahlen? Diese sollten jedoch
abzählbar sein!OLIVER
Hallo Oliver,
die reellen Zahlen sind nicht abzählbar (Beweis: 2. Diagonalverfahren, s.o.), die rationalen Zahlen hingegen sind abzählbar (zeigt man mithilfe des 1. Diagonalverfahrens). Eine Menge heißt abzählbar, wenn sie zur Menge der natürlichen Zahlen (0,1,2,3,4,5,…) äquivalent ist, anders gesagt, man muß die Elemente der Menge so anordnen können, daß sie von den Elementen der natürlichen Zahlen beschrieben werden können. Ich versuch den Beweis mal aufzuzeichnen. Zunächst schreibst du die rationalen Zahlen auf folgende Art auf:
0
1/1 -1/1 2/1 -2/1 3/1 -3/1 …
1/2 -1/2 2/2 -2/2 3/2 -3/2 …
1/3 -1/3 2/3 -2/3 3/3 -3/3 …
1/4 -1/4 2/4 -2/4 3/4 -3/4 …
1/5 -1/5 2/5 -2/5 3/5 -3/5 …
. . . . . .
. . . . . .
. . . . . .
Verfahren: In den Zeilen erhöhst Du den Zählerbetrag (erst positiv, dann negativ), in den Spalten erhöhst Du den Nenner, und zwar immer jeweils um 1.
Auf diese Art hast Du alle rationalen Zahlen erfaßt. Du könntest nun die Brüche, die Vielfaches von anderen sind, streichen (z.B. ist 2/4 = 1/2, deshalb könnte 2/4 gestrichen werden), dies ist aber nicht zwingend notwendig für den Beweis. Nun wird das Schema „diagonal“ durchlaufen, d.h. in folgender Reihenfolge (zeichne jeweils ein „->“ zwischen die Zahlen) : 0, 1/1, -1/1, 1/2, 1/3, -1/2, 2/1, -2/1, 2/2, -1/3, 1/4, 1/5, -1/4, 2/3, -2/2, 3/1, -3/1, 3/2, -2/3, 2/4, -1/5,…
Prinzip erkannt? Du hast nun alle rationalen Zahlen auf eine bestimmte Art aufgereiht. Jetzt brauchst Du sie nur noch zu „nummerieren“, d.h. den natürlichen Zahlen zuordnen.
0 -> 0 , 1/1 -> 1 , -1/1 -> 2 , 1/2 -> 3 , 1/3 -> 4 , -1/2 -> 5 , 2/1 -> 6 , -2/1 -> 7 , 2/2 -> 8 , -1/3 -> 9 , 1/4 -> 10 , u.s.w.
So, auf diese Weise hast Du die Menge der rationalen Zahlen auf die Menge der natürlichen Zahlen zurückgeführt, sie ist somit abzählbar. Damit müßten alle Klarheiten beseitigt sein.
Gruß Alex
soweit hab ich’s verstanden, aber geht denn dieser Beweis
nicht auch für rationale Zahlen? Diese sollten jedoch
abzählbar sein!
Nein.
Wenn man nur die rationalen Zahlen nimmt, muss man alle nichtabbrechenden und nicht-periodisch-werdenden Dezimalzahlen aus der ursprünglichen Liste streichen. Die konstruierte Zahl wird aber (wie auch schon die Diagonale) nie periodisch und bricht nicht ab!
(wenn das der Fall wäre, gäbe es ab einer gewissen Zeile n in der Liste nur noch Zahlen, die ab der n-ten Stelle übereinstimmen, also gäbe es höchstens endlich viele rationale Zahlen die ab der n-te Stelle voneinander verschieden sind. Widerspruch!)
Eine Abzählung der rationalen Zahlen lässt sich leicht konstruieren (wahrscheinlich kennst Du die schon, aber nur für den Fall, dass nicht):
0/1 0/2 0/3 0/4 0/5 …
1/1 1/2 1/3 1/4 1/5 …
2/1 2/2 2/3 2/4 …
3/1 3/2 3/3 …
und dann die Diagonalen entlang abzählen
usw.
(Die Negativen kriegt man mit untergebracht, wenn man dann noch bei der abzählung nach jeder positiven Zahl noch ihr negatives Komplement einfügt)
Peace, Kevin.
Nein.
Wenn man nur die rationalen Zahlen nimmt, muss man alle
nichtabbrechenden und nicht-periodisch-werdenden Dezimalzahlen
aus der ursprünglichen Liste streichen. Die konstruierte Zahl
wird aber (wie auch schon die Diagonale) nie periodisch und
bricht nicht ab!
(wenn das der Fall wäre, gäbe es ab einer gewissen Zeile n in
der Liste nur noch Zahlen, die ab der n-ten Stelle
übereinstimmen, also gäbe es höchstens endlich viele rationale
Zahlen die ab der n-te Stelle voneinander verschieden sind.
Widerspruch!)
Hallo Kevin.
Schön, ich habs verstanden!
Diesen Diagonalbeweis kann man also NUR auf irrationale Zahlen anwenden, da diese konstruierte Zahl selbst stets irrational ist.
Ich hab inzwischen noch einen anderen Beweis gefunden, wieso IR nicht abzählbar ist, wenn’s jemanden interessiert:
Annahme: es gibt eine Abzählung IR={x1,x2,x3,…}
Nun konstruiert man eine Intervallschachtelung (I_n) nach folgender rekursiver Vorschrift:
-
I_1:=[x1+1;x1+2]
-
I_n+1 entsteht aus I_n, indem man I_n in drei gleichlange Teilinterwalle aufteilt und als I_n+1 das jenige nimmt, in dem nach der obigen Abzählung die Zahl x_n+1 NICHT liegt.
Es entsteht eine unendlich Intervallschachtelung, derart, daß
x_n nicht el. I_n, ist. (für alle n)
Sei nun s diejenige Zahl, die in allen Intervallen liegt:
s el. I_n, für alle n.
Hat diese Zahl in unserer Abzählung die Nummer k, so liegt s = xk natürlich auch im Intervall I_k (liegt ja schließlich in allen Intervallen) und damit liegt die Zahl xk im Intervall I_k, im Widerspruch zur Intervallschachtelungsvorschrift -> es gibt keine Abzählung von IR!
PEACE
Oliver
Spezialfall.
IR ist so maechtig wie die Potenzmenge der natuerlichen Zahlen,
und die Potenzmenge IP einer Menge IM ist immer
maechtiger als diese.
Beweis laeuft folgendermassen: Angenommen, es gaebe eine
Menge, die genauso maechtig ist, wie ihre Potenzmenge,
dann muesste es eine Abbildung f:IP–>IM geben, die bijektiv
ist. Sei nun IN die Menge aller Elemente n von IM, deren Urbild
in IP n nicht enthalten. Die Frage, ob f(IN) in IN liegt,
fuehrt auf einen Widerspruch, also gibt es kein f.
Daraus folgt, IP und IM haben verschiedene Maechtigkeiten.
Die Teilmenge aller einelementigen Mengen aus IP ist so maechtig
wie IM, also ist IP mindestens so maechtig wie IM, mit
obiger Behauptung, dass die beiden nicht gleich maechtig
sein duerfen, folgt, dass IP immer maechtiger ist.
Warum ein komplizierter Diagonalbeweis, wenn der nur
ein Spezialfall von einer einfachen Mengenlehre-Uebungsaufgabe
ist?
Marco
P.S. den Diagonalbeweis habe ich nie ganz verstanden.
Warum sollte Unendlich +1 groesser sein, als 2* Unendlich
(z.B. Die Menge aller ganzen Zahlen)
oder 1+Unendlich (Natuerliche Zahlen mit Null)?
IR ist so maechtig wie die Potenzmenge der natuerlichen
Zahlen,
und die Potenzmenge IP einer Menge IM ist immer
maechtiger als diese.
Erhebt sich nur noch die Frage, wieso das automatisch heißt, daß IR überabzählbar ist? IN ist immerhin abzählbar, und eine größere Menge kann problemlos immer noch abzählbar sein…
Gruß, Kubi
HAllo Marco,
IR ist so maechtig wie die Potenzmenge der natuerlichen
Zahlen,
und die Potenzmenge IP einer Menge IM ist immer
maechtiger als diese.
Selbst wenn das stimmt, mußt du immer noch zeigen, daß die Potenzmenge nicht abzählbar ist: das Problem bleibt das selbe.
P.S. den Diagonalbeweis habe ich nie ganz verstanden.
Warum sollte Unendlich +1 groesser sein, als 2* Unendlich
(z.B. Die Menge aller ganzen Zahlen)
oder 1+Unendlich (Natuerliche Zahlen mit Null)?
Also wenn ich den Diagonalbeweis richtig verstanden habe, wird dort einfach aus der Annahme daß IR abzählbar ist, ein Widerspruch abgeleitet -> die Annahme ist falsch: IR ist nicht abzählbar.
Von Unendlich ist dort doch gar nicht die Rede.
Gruß
OLIVER
… also langsam und ausfuehrlich:
IN ist abzaehlbar. Ist eine Menge mehr als abzaehlbar, so
ist sie laut Definition ueberabzaehlbar. Du kannst Dir das
so vorstellen: In einer Unendlich grossen Legebatterie hat
es eine Unendlich lange Reihe von Huehnerboxen. Jetzt
nehmen wir mal an, Du hast eine Bestimmte Menge von Huehnern,
und willst an jedem Huhn ein Zettelchen anbringen, mit
einer Nummer drauf, die diese Huehner durchnummeriert.
Das ist mathematisch das gleiche, wie wenn man Jedes Huhn
in eine Box stecken moechte, naemlich die kann man
durchnummerieren, und zwar so, dass JEDE natuerliche
Zahl vorkommt. Wenn Du nun am Ende der Reihe immer
noch Huehner uebrig hast, dann gibt es einfach keine
Zahl mehr, mit der man das Huhn nummerieren koennte.
Mit anderen Worten, es sind keine Zettelchen mehr uebrig.
Mit „Ueber“ im Sinne von „mehr“ wird nun Mehralsabzaehlbar
mit ueberabzaehlbar bezeichnet.
Um nun auf die Potenzmenge zu kommen: Stell Dir eine zweite
Legebatterie vor, bei der nicht nur Huehner, sondern auch
Haehne drin sind. Nun nimmst Du Jede Teilmenge von Boxen
heraus, und laesst von jeder Teilmenge Huehner/Haehne
ein Ei produzieren. Es gibt nun genausoviele Eier, wie
es Reelle Zahlen gibt. Wie oben gezeigt, muiss man die nur
ausbrueten, um eine MEnge Huehner zu kriegen, die nicht
mehr in den Stall passen.
Mehr als Abzaehlbar bedeutet also automatisch ueberabzaehlbar.
Marco
P.S. Falls in obigem Falle nur huehner oder nur Haehne
in der ausgewaehlten Teilmenge sind, dann muss man halt
Klonen oder sowas.
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Hierarchien der Unendlichkeit
Hallo Marco,
Warum sollte Unendlich +1 groesser sein, als 2* Unendlich
(z.B. Die Menge aller ganzen Zahlen)
oder 1+Unendlich (Natuerliche Zahlen mit Null)?
die Menge IN ist genauso mächtig wie die Menge ( IN vereinigt mit {1.285, e, pi}), und genauso mächtig wie die Menge aller ungeraden Zahlen, und genauso mächtig wie die Menge der ganzen Zahlen, und genauso mächtig wie die Menge aller ganzzahligen Vielfache von 1000000. Die Mathematiker bezeichnen diese Mächtigkeit mit „Aleph-Null“ (Aleph ist der Anfangsbuchstabe des hebräischen Alphabets sieht ungefähr wie ein „x“ aus). Aleph-Null ist sozusagen die „kleinste Stufe der Unendlichkeit“. Allen diesen unendlichen Mengen ist die Eigenschaft der Abzählbarkeit gemeinsam. „Abzählbar“ heißt, daß man (mindestens) eine bijektive Abbildung zwischen diesen Mengen und IN angeben kann (für die oben genannten Beispiele ist das Auffinden solcher bijektiver Abbildungen trivial).
Nun kann man noch recht einfach zeigen, daß sogar die Menge aller rationalen Zahlen genauso mächtig wie IN ist, daß also Q ebenfalls die Kardinalzahl Aleph-Null besitzt. Um eine bijektive Abbildung zwischen Q und IN herstellen zu können, ordnet man alle existierenden Brüche folgendermaßen in einem zweidimensionalen unendlichen Gitter an…
0/1 1/1 2/1 3/1 4/1 ...
0/2 1/2 2/2 3/2 4/2 ...
0/3 1/3 2/3 3/3 4/3 ...
0/4 1/4 2/4 3/4 4/4 ...
... ... ... ... ... ...
…und führt dann die Abzählung so durch, daß man beginnend bei der „0/1“-Ecke in einem diagonalen Zickzackweg durch das Gitter marschiert (und zusätzlich noch immer Plus und Minus hinzufügt, damit auch die negativen Zahlen mitgezählt werden) und den Bruch einfach immer der nächsthöheren Zahl aus IN zuordnet.
Die Reihenfolge wäre also:
0/1 (wird der 0 zugeordnet),
0/2 (wird der 1 zugeordnet),
1/1 (wird der 2 zugeordnet),
2/1 (wird der 3 zugeordnet),
1/2, ...
0/3, ...
0/4, ...
1/3, ...
usw.
(Dies ist nicht das einzig mögliche Abzählschema, es gibt viele weitere).
Daß „Unendlich + 3“ genausoviel ist wie Unendlich (wobei mit diesem „Unendlich“ hier Aleph-Null gemeint ist) und genauso viel wie „0.000001*Unendlich“ und genauso viel wie „1000000*Unendlich“), kann man intuitiv wohl noch irgendwie nachvollziehen. Bei Q haben wir allerdings so etwas wie „Unendlich zum Quadrat“ vorliegen, und trotzdem ist das offensichtlich immer noch genauso viel wie „Unendlich“, d. h. auch Q ist nur eine Aleph-Null-Menge! Und das ist ja nun schon „ziemlich erstaunlich“ (finden jedenfalls die meisten).
Nach der Untersuchung von Q liegt die Frage nach der Mächtigkeit der Menge der reellen Zahlen nahe. Und hier erbrachte Cantor nun den Beweis dafür, daß R eine echt größere Mächtigkeit als IN besitzt, indem er zeigte, daß R überabzählbar ist. Sein Diagonalbeweis zeigt, daß eine bijektive Abbildung zwischen N und R prinzipiell nicht hergestellt werden kann, so sehr man sich auch bemühen würde. R ist nicht abzählbar.
Die Kardinalzahl von R wird als Aleph-Eins bezeichnet, und das ist wie wir gesehen haben „noch deutlich mehr“ als „Unendlich zum Quadrat“. Man kann zeigen, daß die Potenzmenge von IN ebenfalls die Mächtigkeit Aleph-Eins besitzt. Jede Menge, die Aleph-Eins mächtig ist oder noch mächtiger (die Potenzmenge von R hätte z. B. die Mächtigkeit Aleph-Zwei usw.), ist überabzählbar. Ein weiteres Beispiel für eine Aleph-Eins-mächtige Menge ist die der Punkte auf einer 1 cm langen Strecke. Man kann zeigen, daß die Menge der Punkte auf einer unendlich langen Linie oder die der Punkte des Raumes (und zwar beliebig hoher Dimension) aber ebenfalls „nur“ Aleph-Eins-mächtig ist (Du siehst, hier wimmelt es von Kuriositäten).
Cantor zeigte, daß es tatsächlich eine endlose Hierarchie von Alephs gibt, ohne ein „höchstes“ Aleph. Damit ist allerdings noch nicht die Frage beantwortet, ob damit alle existierenden Alephs erfaßt sind. Cantor fragte sich nämlich, ob es wohl eine Menge geben mag, die mächtiger ist als Aleph-Null, aber nicht so mächtig wie Aleph-Eins (also salopp gesagt, ob es sozusagen so etwas wie ein „Aleph-Einhalb“ geben mag). Cantor glaubte fest daran, daß dem nicht so ist (die sogenannte „Kontinuumshypothese“), und versuchte sein Leben lang (Cantor lebte von 1845 bis 1918), es zu beweisen. Das gelang ihm aber nicht. Kurt Gödel zeigte 1938, daß Cantors Kontinuumshypothese als richtig angesehen werden kann, d. h. daß das Postulat der Nichtexistenz einer solchen Menge in Einklang mit den Axiomen der Mengenlehre steht.
Drei Jahrzehnte später wurde allerdings eine weitere Antwort auf Cantors Frage gefunden – und die hatte es wahrhaft in sich. Gödel hatte gezeigt, daß es kein Problem gibt, wenn man annimmt, es gäbe eine solche Menge nicht , daß also die Kontinuumshyposthese wahr ist. Was Paul J. Cohen 1969 überraschenderweise bewies, war das genaue Gegenteil: Er zeigte, daß es auch zu keinem Widerspruch mit den Axiomen der Mengenlehre führt, wenn man postuliert, daß es mindestens ein Aleph zwischen Aleph-Null und Aleph-Eins gibt (obwohl niemand auch nur die leiseste Vorstellung davon hat, wie eine Menge mit einer solchen Kardinalzahl zu spezifizieren wäre), daß also die Kontinuumshypothese falsch ist.
Manche Mathematiker hoffen, daß irgendwann mal jemand ein weiteres Axiom der Mengenlehre finden wird, mit dessen Hilfe eine Entscheidung über die Kontinuumshypothese gefällt werden kann; andere glauben, daß die Frage für immer unentschieden bleiben wird. Nichtsdestotrotz sind heute jedenfalls nur noch wenige Mathematiker und ein paar Philosophen über die Alephs beunruhigt, und Cantors Beweise zählen zu den brilliantesten und schönsten in der Geschichte der Mathematik.
Mit freundlichem Gruß
Martin
3 „Gefällt mir“
Hallo Marco,
schönes Beispiel mit den Hühnern und so, aber ich denke Kubi wollte nur wissen wie du von Pot(IN) auf IR schließt, was ja eigentlich gefragt war!
Gruß
OLIVER
IR ist so maechtig wie die Potenzmenge der natuerlichen
Zahlen,
Das musst Du noch beweisen.
(das geht über den Satz von Schröder und Bernstein mit Pot(IN)~INnachIN (Menge aller Funktionen von IN nach IN) und einer Konstruktion jeder reellen Zahl aus INnachIN und umgekehrt)
Sei nun IN die Menge aller Elemente n von IM, deren
Urbild
in IP n nicht enthalten.Warum ein komplizierter Diagonalbeweis, wenn der nur
ein Spezialfall von einer einfachen Mengenlehre-Uebungsaufgabe
ist?
Das ist auch ein Diagonalbeweis (nur halt in diesem Fall das erste statt des zweiten Cantorschen Diagonalverfahrens)
Die von Dir definierte Menge
Sei nun IN die Menge aller Elemente n von IM, deren Urbild
in IP n nicht enthalten
ist gerade die Cantorsche Diagonale!
P.S. den Diagonalbeweis habe ich nie ganz verstanden.
Der ist gar nicht so schwer 
Peace, Kevin.
Hallo nochmal,
Dein wunderschönes Hühnerbeispiel in allen Ehren, aber es geht an meiner Frage vorbei.
Was ich wissen will ist: Wieso ist eine größere Menge als IN automatisch überabzählbar? IN ist nicht die größtmögliche abzählbar unendliche Menge. Also ist eine größere Menge als IN NICHT automatisch überabzählbar. Wie also zeigst Du, daß das für IR gilt? Dein Hinweis reicht dazu nämlich nicht aus.
Gruß Kubi