Unendlich

Cantors grundlegende Entdeckung

»Nun«, sagte der Zauberer während des nächsten Treffens, »habt ihr über die Sache nachgedacht ? Habt ihr eine Idee, ob es nur eine oder aber mehrere Arten der Unendlichkeit gibt ?« Einer der beiden ( ich habe vergessen, wer) tippte auf das eine, der andere auf das andere. »Das erstaunliche an der Sache ist«, sagte der Zauberer, »daß Cantor zunächst vermutete, daß zwei beliebige unendliche Mengen gleich groß sein müßten, und soweit ich weiß, verbrachte er zwölf Jahre damit, diese Vermutung zu beweisen. Im dreizehnten Jahr fand er dann ein Gegenbeispiel - das ich gerne als <Cantorbeispiel> bezeichne. Ja, in der Tat gibt es mehr als nur eine Art Unendlichkeit - es gibt unendlich viele. Und diese grundsätzliche Entdeckung verdanken wir Cantor. Ich komme jetzt zu dem, was Cantor getan hat. Eine Menge wird abzählbar unendlich, oder kürzer gesagt: sie wird abzählbar genannt, wenn sie in eine eindeutige Beziehung zu der Menge der positiven ganzen Zahlen gesetzt werden kann. Demnach lautet die Frage, die sich Cantor gestellt hat : Ist jede unendliche Menge abzählbar? Wie ich bereits gesagt habe, vermutete er zunächst, daß jede unendliche Menge abzählbar sei, und entdeckte erst später den wahren Sachverhalt. In seinen anfänglichen Untersuchungen betrachtete er Mengen, die zu groß erschienen, um abzählbar zu sein, die er aber dann mit Hilfe eines geschickten Kunstgriffs doch abzählen konnte.« »Was meinen Sie mit <Abzählen einer unendlichen Menge> ?« fragte Annabel. »Eine unendliche Menge abzuzählen heißt, sie in eine 1 : 1 Zuordnung mit der Menge der positiven ganzen Zahlen zu bringen. Tatsächlich ist das Wort <abzählbar> synonym mit <abzählbar unendlich>. Wie dem auch sei, Cantor hat, wie bereits gesagt, zig Mengen betrachtet, die zunächst nicht abzählbar zu sein schienen - in der Bedeutung von unendlich, aber nicht abzählbar - , und hat einen trickreichen Weg gefunden, sie doch abzuzählen. Zur Verdeutlichung seiner Methode könnten wir uns vorstellen, ich sei der Satan, und ihr wäret meine Opfer in der Hölle. Sich das vorzustellen ist nicht so schwer, oder ?« Annabel und Alexander mußten über diesen Gedanken herzlich lachen. »Jetzt sage ich euch, daß ich euch prüfen will: Ich denke gerade an eine positive ganze Zahl, die ich auf dieses gefaltete Stück Papier geschrieben habe. Jeden Tag dürft ihr einmal, aber nur ein einziges Mal raten, wie die Zahl lautet. Wenn ihr richtig ratet, kommt ihr frei, aber erst dann. Gibt es nun eine Strategie, mit der ihr früher oder später aus der Hölle herauskommt ?« »Natürlich«, antwortete Alexander. »Am ersten Tag frage ich, ob es eine Eins ist, am zweiten Tag ob es die Zwei ist, und immer so weiter. Früher oder später werde ich die richtige Zahl treffen !« »Richtig«, sagte der Zauberer. »Nun, meine zweite Prüfung ist ein kleines bißchen schwieriger. Diesmal schreibe ich entweder eine positive oder eine negative ganze Zahl auf - ich notiere entweder eine der Zahlen 1,2,3,4, ... oder eine der Zahlen -1, -2, -3, -4, ... und ihr habt jeden Tag wieder genau einen Versuch, die Zahl zu erraten. Habt ihr nun eine Strategie, die euch über kurz oder lang mit Sicherheit heraushilft ?« »Klar«, sagte Annabel. »Am ersten Tag frage ich, ob es die Zahl +1 ist, am nächsten Tag, ob es die -1 ist, und dann mache ich weiter mit +2, -2, +3, -3, +4, -4, .... und so weiter. Früher oder später muß ich Ihre Zahl erraten.« »Richtig«, sagte der Zauberer, »und ihr versteht, was das bedeutet. Oberflächlich betrachtet sieht es so aus, als wäre die Menge der positiven und negativen ganzen Zahlen größer als die Menge der positiven ganzen Zahlen, nämlich genau doppelt so groß. Andererseits habt ihr gerade gesehen, wie man die Menge der positiven und negativen ganzen Zahlen in eine 1 : 1 Beziehung mit den positiven ganzen Zahlen setzt, und demzufolge sind die beiden Mengen tatsächlich gleich groß. Die Menge aller positiven und negativen ganzen Zahlen zusammen ist abzählbar. Das Problem, das ihr gerade gelöst habt, ist größtenteils mit der Problematik der zweiten Aufgabe zu Hilberts Hotel identisch. Wie ihr euch erinnern werdet, gab es abzählbar viele Personen in abzählbar vielen Räumen, und dann erschien eine zweite Menge von abzählbar vielen Leuten, und wir wollten diese beiden Menegen vereinigen und alle unterbringen. Die nächste Prüfung meiner Opfer ist definitiv schwieriger. Diesmal schreibe ich zwei Zahlen, oder möglicherweise auch dieselbe Zahl zweimal, auf einen Zettel. Ich könnte beispielsweise die Zahlen 3 und 57, oder 17 und 206, oder 23 und 23 notieren. Wieder dürft ihr nur ein einziges mal pro Tag raten, welches die Zahlen sind. Es ist euch nicht erlaubt, eine der Zahlen an einem Tag und die andere an einem anderen Tag zu erraten, sondern beide müssen am selben Tag erraten werden. Glaubt ihr nun, daß es eine Vorgehensweise gibt, mit deren Hilfe ihr euch über kurz oder lang befreien könnt ?« »Ich bezweifle es«, sagte Annabel. »Es gibt unendlich viele Möglichkeiten für die Zahl, die sie zuerst aufschreiben, und mit jeder dieser Möglichkeiten auch unendlich viele für die zweite Zahl. Man kann annehmen, daß unendlich mal unendlich größer ist als die Unendlichkeit, von der man ausgeht.« »So mag es erscheinen«, sagte der Zauberer, » und so sah es für viele zu Cantors Zeiten aus, aber das Erscheinungsbild kann manchmal täuschen. Ja, es gibt eine Taktik, mit der man auf jeden Fall entkommt. Die Menge der Möglichkeiten, mit der ihr es zu tun habt, ist trotz allem tatsächlich abzählbar. Könnt ihr die Strategie finden ?« »Erstaunlich !« rief Annabel, und Alexander stimmte ihr zu. Die beiden berieten sich daraufhin und kamen dabei auf eine einfache Methode, die bestimmt funktioniert.

- 1 -

Welche Methode wird bestimmt funktionieren ?

Lösung : Für jedes n gibt es nur endlich viele Möglichkeiten für ein Zahlenpaar, dessen größere Zahl gleich n ist - und zwar gibt es genau n Möglichkeiten. Also gibt es nur eine Möglichkeit für das Paar, dessen größere Zahl 1 ist, nämlich (1, 1). Für das Paar mit 2 als größter Zahl gibt es zwei Möglichkeiten : (1, 2) und (2, 2) Weiter gibt es drei Möglichkeiten für das Paar mit größter Zahl 3, und zwar (1, 1), (1, 2), (1, 3), und so weiter. Und wir zählen sie in folgender Reihenfolge ab : (1, 1), (1, 2), (2, 2), (1, 3), (2, 3), (3, 3), (1, 4), (2, 4), (3, 4), (4, 4), ... (1, n), (2, n),... (n - 1,n), (n, n), ...

»Nehmen wir an, ich erschwere die Fragestellung nun ein wenig, indem ich verlange, daß ihr jetzt nicht nur die beiden Zahlen erraten müßt, sondern auch, in welcher Reihenfolge sie aufgeschrieben wurden - sagen wir, eine steht links von der anderen. Könnt ihr immer noch sicher entkommen ?« »Natürlich«, erwiderte Annabel »Nachdem das letzte Problem gelöst ist, ist dies ganz einfach.«

- 2 -

Wie sieht die Lösung aus ?

Lösung : In diesem Fall werden wir vielleicht doppelt so lange brauchen, um hinauszukommen, aber früher oder später muß es uns gelingen durch das Abzählen der geordneten Paare in der Reihenfolge (1, 1), (1,2), (2,1), (2,2), (1, 3), (2, 3), (3, 3), (3, 2), (3, 1), ... (1, n) (2, n) ... (n - 1,n), (n, n), (n, n - 1), ... (n, 2), (n, 1), (1, n+1), ...

»Dann laßt mich folgende Frage stellen«, sagte der Zauberer. »Wie steht es mit der Menge aller positiven Brüche ? Ist diese Menge abzählbar oder nicht ? Ihr habt nun gute Voraussetzungen, diese Frage zu beantworten. Mit einem positiven Bruch ist einfach der Quotient zweier positiver ganzer Zahlen gemeint - Zahlen wie beispielsweise 3/7 oder 21/13.«

- 3 -

Ist die Menge der positiven Brüche abzählbar ?

Lösung : Dies ist fast dasselbe Problem wie das letzte, nur daß wir jetzt eine Zahl über der anderen (dem Nenner) haben statt einer Zahl links neben der anderen. Damit können wir die positiven Brüche in der Reihenfolge 1/1, 1/2, 2/2, 1/3, 2/3, 3/3, 3/2, 3/1, 1/4, 2/4, 3/4, 4/4, 4/3, 4/2, 4/1, ... abzählen. Natürlich können wir ein bißchen schneller vorangehen, indem wir die doppelt auftretenden Brüche auslassen, so 2/2 (welches gleich 1/1 ist), 3/3 sowie 2/4 (was schon als 1/2 vorkommt) und so fort.

»Die Antwort ist zu Cantors Zeiten für viele Mathematiker ein ziemlicher Schock gewesen«, sagte der Zauberer. »Und nun habe ich ein schwierigeres Problem für euch. Diesmal schreibe ich eine endliche Menge von positiven ganzen Zahlen auf. Weder verrate ich, wie viele Zahlen in der Menge sind, noch, welches die größte Zahl ist. Jeden Tag habt ihr nur genau einen Versuch, um die Menge zu erraten. Wenn ihr die Menge ermitteln könnt, seid ihr frei. Nun, glaubt ihr, daß es eine Strategie gibt, um frei zu werden ?« Die beiden waren der Meinung, daß dies ziemlich unwahrscheinlich war. »Es gibt eine solche Strategie«, sagte der Zauberer. »Die Menge aller endlichen Mengen positiver ganzer Zahlen ist abzählbar.«

- 4 -

Wie kann man die Menge aller positiver ganzer Zahlen abzählen ? Welche Strategie muß man benutzen, um freizukommen ?

Lösung : Eine Menge mit den Elementen a1, a2, ....an schreibt man in der Weise (a1, a2, .....an). Es gibt nun nur eine Menge, die als größte Zahl die 1 hat, nämlich (1). Es gibt zwei Mengen, die als größte Zahl die 2 enthalten, nämlich (1, 2) und (2). Weiter gibt es vier Mengen mit der 3 als größter Zahl, nämlich (3), (1, 3), (2, 3), (1, 2, 3). Allgemein gibt es für jedes positive n nun 2 hoch n -1 Mengen mit n als höchster Zahl. Der Grund ist dieser : Für jedes n gibt es 2 hoch n Teilmengen der Menge der positiven ganzen Zahlen von 1 bis n (inclusive der leeren Menge !). Also besteht jede Menge, die als höchste Zahl n enthält, aus n sowie einer Teilmenge der Zahlen von 1 bis n-1, und von diesen Teilmengen gibt es 2 hoch n -1. Der wichtige Punkt ist jedenfalls der, daß es für jedes n nur endlich viele Mengen von positiven ganzen Zahlen gibt, die n als größte Zahl enthalten. Zuerst nenne ich die leere Menge, und dann die Menge mit 1 als größter Zahl. Dann gehe ich durch die Mengen, die 2 als größte Zahl enthalten (die Reihenfolge spielt keine Rolle), dann durch die Mengen mit 3 als größter Zahl, und so weiter.

»Und wie ist es mit der Menge aller Mengen von positiven ganzen Zahlen - sowohl der endlichen als auch der unendlichen Mengen ?« fragte Annabel. »Ist diese Menge abzählbar oder nicht ? Oder ist die Antwort unbekannt ?« »Ah !« sagte der Zauberer. »Daß diese Menge nicht abzählbar ist, war Cantors große Entdeckung !« »Hat niemand bis jetzt einen Weg gefunden, diese Menge abzuzählen ?« fragte Alexander. »Nein, und niemand wird es jemals können, denn es ist logisch unmöglich, diese Mengen abzuzählen.« »Woher weiß man das ?« wollte Annabel wissen. »Also, laßt es uns folgendermaßen betrachten: Stellt euch ein Buch mit abzählbar endlich vielen Seiten vor - Seite 1, Seite 2, Seite 3, .... Seite n, ... Auf jeder Seite steht eine Beschreibung einer Menge von positiven ganzen Zahlen. Das Buch gehört euch. Wenn jede Menge positiver ganzer Zahlen in diesem Buch aufgelistet ist, gewinnt ihr einen großen Preis. Aber ich sage euch nun, daß ihr den Preis nicht gewinnen könnt, da ich eine Menge positiver ganzer Zahlen beschreiben kann, die unmöglich auf irgendeiner Seite des Buches aufgeführt worden sein kann.«

- 5 -

Man beschreibe eine Menge positiver ganzer Zahlen, die definitiv auf keiner Seite des Buches aufgeführt wird !

Lösung : Ist eine Zahl n gegeben, dann gehört sie entweder zu der Menge auf Seite n, oder sie gehört nicht dazu. Es sei nun S die Menge aller Zahlen n, so daß n nicht zu der Menge auf Seite n gehört. Für jedes n sei Sn die Menge auf Seite n. Wir definieren S so, daß für alle n die Menge S ungleich der Menge Sn ist. Denn n gehört nur dann zu S, wenn es nicht zu Sn gehört. Dies bedeutet, daß n entweder in S, aber nicht in Sn, oder in Sn, aber dann nicht in S enthalten ist. In jedem Fall muß S verschieden von Sn sein, denn eine dieser beiden Mengen enthält n und die andere nicht. Um eine besssere Vorstellung der Konstruktion der Menge S zu geben, denken wir uns die Mengen der ersten zehn Seiten wie folgt:

Seite 1 - Menge aller geraden Zahlen,

Seite 2 - Menge aller (positiven ganzen) Zahlen,

Seite 3 - Die leere Menge,

Seite 4 - Menge aller Zahlen größer als 100,

Seite 5 - Menge alle Zahlen kleiner als 58,

Seite 6 - Menge aller Primzahlen,

Seite 7 - Menge aller Zahlen, die nicht prim sind,

Seite 8 - Menge aller durch 4 teilbaren Zahlen,

Seite 9 - Menge aller durch 7 teilbaren Zahlen,

Seite 10 - Menge aller durch 5 teilbaren Zahlen.

Ich habe diese zehn Mengen zufällig ausgesucht. Wie wird nun S aussehen, soweit es die ersten Zahlen betrifft ? Was ist mit der 1; muß S die 1 enthalten ? Ist 1 ein Element der Menge von Seite 1; ist also 1 eine gerade Zahl ? Nein, und damit gehört 1 nicht zu S1; also fügen wir 1 in S ein. Und die 2 ? Die 2 ist natürlich in S2 enthalten (denn 2 ist eine positive ganze Zahl), und so darf die 2 nicht zu S gehören. Die 3 ist sicher nicht in S3 (denn dies ist die leere Menge), und daher ist die 3 ein weiteres Element von S. Weiter ist die 4 nicht in S4 (4 ist nicht größer als 100), also ist die 4 in S. Wir lassen den Leser die nächsten sechs Fälle selbst prüfen: 5 ist in S,denn 5 ist nicht in S5; 6 ist nicht in S6 (6 ist keine Primzahl), also ist 6 in S; 7 ist nicht in S7, also in S; 8 ist in SS8, also nicht in S; 9 ist nicht in S9, also gehört 9 in S; 10 ist in S10 (10 ist durch 5 teilbar) und gehört damit nicht in S. Um nun eine Liste der Einträge von S zu machen, schreiben wir die Zahl n an die nte Stelle, wenn n in S ist, und wir setzen einen Strich an die nte Stelle, um anzuzeigen, daß n definitiv nicht zu S gehört. Dann sehen die ersten zehn Plätze unserer Liste so aus : 1, -,3,4,5,6,7,-,9,-,... Nun sehen wir, daß S verschieden von S1 ist, weil es die 1 enthält, S1 aber nicht. S ist ebenfalls ungleich S2, denn es enthält nicht die 2, im Gegensatz zu S2. Und so sieht man, daß für jedes n entweder S das n enthält und Sn nicht, oder n ist nicht in S, aber in Sn. Demzufolge ist die Menge S verschieden von allen Mengen, die in diesem Buch aufgelistet sind. Natürlich brauchen wir nicht unbedingt das Buch, um diese Argumentation zu bestätigen. der zentrale Punkt ist der, daß für jede gegebene Abzählung S1, S2, .... Sn, ... nicht alle Mengen der positiven ganzen Zahlen, da die Menge S nicht einbezogen ist. Also ist die Menge aller Mengen der positiven ganzen Zahlen nicht abzählbar.


»Wie ihr seht«, fuhr der Zauberer fort, nachdem er die Lösung des letzten Problems gegeben hatte, »ist die Menge aller Mengen positiver ganzer Zahlen nicht abzählbar. Sie ist größer als die Menge der positiven ganzen Zahlen.« »Das haben Sie nicht gezeigt«, warf Annabel ein. »Sie haben nur gezeigt, daß die Menge aller Mengen positiver ganzer Zahlen - gibt es übrigens einen Namen für diese Menge ?« »Ja«, sagte der Zauberer. »Für alle Mengen A heißt die Menge aller Teilmengen von A die Potenzmenge von A, und diese wird mit P(A) bezeichnet. Wir können die Menge aller postiven ganzen Zahlen N nennen, und dann ist die Menge aller Teilmengen von N - welche die Menge aller Mengen positiver ganzer Zahlen ist - folglich die Potenzmenge von N und wird mit P(N) bezeichnet.« »Ganz richtig«, sagte Annabel. »Sie haben jedenfalls gezeigt, daß P(N) nicht abzählbar ist - daß es keine eindeutige Zuordnung zwischen P(N) und N geben kann, und P(N) ist natürlich unendlich; aber es ist ungerechtfertigt, daraus zu schließen, daß P(N) größer als N ist, weil Sie nicht gezeigt haben, daß es eine eindeutige Beziehung von N zu einer Teilmenge von P(N) gibt. Ist das nicht notwendig, um Ihre Argumentation zu vervollständigen ?« »Wir haben bereits N in eine solche Zuordnung zu einer Teilmenge von P(N) gebracht«, antwortete der Zauberer.

- 6 -

Wann ist das geschehen ?

Lösung : Bei Problem 4 haben wir gezeigt, daß die Menge aller endlichen Teilmengen von N abzählbar ist und daß N damit in eine eindeutige Beziehung zur Menge aller endlichen Teilmengen von N gesetzt werden kann. Ganz offensichtlich ist die Menge E aller endlichen Teilmengen von N eine Teilmenge der Menge aller Teilmengen von N - damit ist E eine Teilmenge von P(N), und es gibt eine eindeutige Beziehung von N zu E.

Nachdem der Zauberer Annabel an das vierte Problem erinnert hatte, stellte einer der beiden ( ich habe vergessen, ob es Annabel oder Alexander war ) eine Frage : »Wir haben gesehen, daß die Menge aller endlichen Mengen positiver ganzer Zahlen abzählbar ist ; demnach kann sie mit Hilfe einer unendlichen Folge S1, S2, ....Sn,.... abgezählt werden. Warum können wir nicht Cantors Argumentation anwenden und bekommen so eine Menge S, die sich von allen Mengen S1, S2,...Sn,.... unterscheidet ? Entsteht daraus nicht ein Paradoxon ?«

- 7 -

Ergibt das ein Paradoxon ?

Lösung : Natürlich nicht ! Die Menge S unterscheidet sich tatsächlich von jeder der endlichen Mengen Sn, aber dies heißt nur, daß die Menge S nicht endlich ist.

»Ich habe eine Frage«, sagte Alexander, nachdem die letzte Frage geklärt worden war. »Wir wissen, daß die Menge aller endlichen Mengen positiver ganzer Zahlen abzählbar ist. Wie steht es mit der Menge aller unendlichen Mengen positiver ganzer Zahlen ? Ist diese Menge abzählbar oder nicht ?«

- 8 -

Wie lautet die Antwort auf Alexanders Frage ?

Lösung : Wir wissen, daß die Menge aller endlichen Mengen von positiven Zahlen abzählbar ist; damit kann sie in einer endlichen Folge E1, E2, ...En.. abgezählt werden. Jeder positiven Zahl n läßt sich also eine endliche Menge von positiven Zahlen En zuordnen, und diese Zuordnung ist dergestalt, daß jede endliche Menge von positiven ganzen Zahlen gleich einer dieser Mengen En ist. Stellen wir uns nun vor, die Menge aller unendlichen Mengen von positiven ganzen Zahlen wäre abzählbar. Dann ließe sich diese in einer unendlichen Folge U1, U2, ...Un,... aufzählen, wobei für jede Zahl n Un die der Zahl n zugeordnete unendliche Menge wäre. Doch dann könnten wir alle Mengen von positiven ganzen Zahlen - endliche und unendliche - aufzählen, nämlich in der Reihenfolge E1, U1, E2, U2, ..., En, Un, ... Dies widerspricht jedoch der Tatsache, daß die Menge aller Mengen von positiven ganzen Zahlen nicht abzählbar ist.

»Eine weiter Frage : Wir haben gesehen, daß P(N) größer ist als N. Gibt es eine Menge, die größer ist als P(N) ?« fragte Annabel. »Aber natürlich«, gab der Zauberer zurück. "Die Tatsache, daß P(N) größer als N ist, ist nur ein spezieller Fall von Cantors Theorem, das folgendermaßen lautet :

Theorem C (Cantors Theorem): Für jede Menge A ist die Menge P(A) aller Teilmengen von A stets größer als A.

»Der Beweis von Cantors Theorem«, sagte der Zauberer, »unterscheidet sich im Prinzip kaum von dem Beweis, den ich euch für den Spezialfall, daß A die Menge N der positiven ganzen Zahlen ist, gegeben habe. Die Idee, die hinter dem Beweis steht, wurde von Smullyan in folgendem Problem sehr schön veranschaulicht : In einem bestimmten Universum bildet jede Menge von Bewohnern einen Verein. Der höchste Verwaltungsbeamte des Universums möchte jeden Verein nach einem Bewohner benennen, und zwar so, daß keine zwei Vereine den Namen desselben Bewohners tragen und daß jeder Bewohner ein Namensgeber für einen Verein ist. Es ist nicht unbedingt notwendig, daß die Person ein Mitglied des Vereins ist, der seinen Namen trägt. Nun, für ein Universum mit nur endlich vielen Menschen ist dies eindeutig unmöglich, denn es existieren mehr Vereine als Bewohner (wenn n die Zahl der Bewohner ist, dann ist 2n die Zahl der Vereine). Allerdings hat dieses bestimmte Universum unendlich viele Einwohner, und deswegen sieht der höchste Verwaltungsbeamte keinen Grund, warum dies nicht möglich sein sollte. Jedoch hat bisher jedes Schema, das er ausprobierte, versagt - es blieben immer Vereine übrig. Warum ist es unmöglich, das Schema des Beamten auszuführen ?«

- 9 -

Warum ist es unmöglich, ein solches Schema zu finden, und wie hängt dies mit Cantors Theorem zusammen ?

Lösung : Angenommen, das Schema des Verwalters könnte durchgeführt werden. Dann erhalten wir einen Widerspruch wie folgt : Wir nennen einen Einwohner gesellig, wenn er dem nach ihm benannten Verein angehört, sonst nennen wir ihn ungesellig. Weil in diesem Universum jede Menge von Einwohnern einen Verein bildet, bildet auch die Gruppe der ungeselligen Einwohner einen Verein. Dieser Verein ist nach jemanden benannt - sagen wir John. Also ist jedes Mitglied von Johns Verein ungesellig, und jeder ungesellige Einwohner gehört zu Johns Verein. Ist John gesellig oder nicht ? In jedem Fall erhalten wir hier einen Widerspruch: Nehmen wir zunächst einmal an, John ist gesellig: Dies bedeutet, daß John zu Johns Verein gehört, jedoch gehören nur ungesellige Menschen zu Johns Verein, dies ist also ausgeschlossen. Nehmen wir also an, daß John ungesellig ist: Da jeder ungesellige Einwohner in Johns Verein ist, müßte auch John als ungeselliger Einwohner zu Johns Verein gehören, was ihn aber gesellig macht. Und so ist John weder gesellig noch ungesellig; wir erhalten einen Widerspruch. Deswegen kann das Schema des Verwalters nicht funktionieren. Der Zusammenhang dieses Problems mit Cantors Theorem ist wohl offensichtlich - es ist einfach ein Spezialfall davon. Anstelle eines Universums von Leuten betrachten wir eine beliebige Menge A. Nehmen wir an, daß wir eine eindeutige Zuordnung zwischen A und der Menge P(A) aller Teilmengen von A haben. Wir erhalten den folgenden Widerspruch : Jedes Element x von A ist einer und genau einer Teilmenge von A zugeordnet, welche wir die x-Menge nennen. Nun sei S die Menge aller der Elemente x von A, für die gilt, daß x nicht zu der x-Menge gehört. (Im obigen Problem entspricht S der Menge der ungeselligen Einwohner.) Ein Element b von A ist dieser Menge S zugeordnet, also ist die b-Menge die Menge aller x mit der Eigenschaft, daß x nicht in der x-Menge ist. Wenn b in der b-Menge ist, dann ist b eines der Elemente mit der Eigenschaft, nicht zu der b-Menge zu gehören, und das ergibt einen Widerspruch. Wenn b nicht in der b-Menge ist, hat b die Eigenschaft, nicht zu der b-Menge zu gehören, aber jedes Element mit dieser Eigenschaft liegt in der b-Menge, also müßte b doch in der b-Menge liegen, was wieder einen Widerspruch ergibt. Damit ist bewiesen, daß es keine eindeutige Beziehung zwischen A und seiner Potenzmenge P(A) geben kann. Natürlich kann man A wie folgt in eine eindeutige Zuordnung zu einer Teilmenge von P(A) setzen : Für jedes Elemet x ist mit (x) eine Menge gemeint, deren einziges Element x ist. (Solch eine Menge (x) wird Einermenge oder einelementige Menge genannt. Sie hat nur ein Element, unabhängig davon, wieviele Elemente x selbst haben mag). Wir können nun jedes einzelne Element x von A mit der einelementigen Menge (x) in Beziehung setzen. Diese Zuordnung ist offensichtlich umkehrbar, und natürlich ist (x) eine Teilmenge von A (denn jedes Element von (x), wovon es nur eins gibt - x selbst -, ist ein Element von A). Dementsprechend steht A in einer eindeutigen Beziehung zu einer Menge, die aus einigen Elementen von P(A) besteht. Da A in eine eindeutige Beziehung mit einer Teilmenge von P(A) gesetzt werden kann und nicht in eine eindeutige Beziehung mit der ganzen Menge P(A) (wie wir gezeigt haben), ist per definition P(A) größer als A. Damit ist Cantors Theorem bewiesen.

»Als Konsequenz von Cantors Theorem«, erklärte der Zauberer, nachdem Annabel und Alexander den Beweis verstanden hatten, »muß es unendlich viele verschieden große Unendlichkeiten geben, denn wir können mit N, der Menge der positiven ganzen Zahlen, starten, als nächstes haben wir ihre Potenzmenge P(N) - die Menge aller Teilmengen von N -, welche größer als N ist, dann ist wiederum nach Cantors Theorem die Potenzmenge dieser neuen Menge - also P(P(N)))- größer als P(N), die Menge P(P(P(N))) wiederum ist noch größer als jene, und so fort. Das heißt, zu jeder Menge gibt es eine größere Menge, und deswegen gibt es auch unendlich viele Größen von Mengen.«


HIER GEHTS WIDERSPRÜCHLICH WEITER