Die faszinierende Welt der endlichen Mengen

Ich dachte mir, wenn mir schon mal etwas mathematisch interessantes passiert, was vielleicht die Welt ,,da draußen„ auch interessieren könnte, sollte ich es vielleicht auf meinen Blog schreiben. Obgleich es wohl eher trivial ist (zumindest für jemanden, der die Vorlesungen Mathematische Logik 1 und 2 gehört und verstanden hat), so ist es dennoch interessant, wenn auch nicht im mathematischen, aber wohl doch im philosophischen Sinne, sich über die folgenden Ausführungen Gedanken zu machen. Eventuelle Fehler kann ich leider nicht ausschließen. Ich lasse mich also gerne korrigieren. Formal bin ich nur im notwendigen maße.

Ich wusste schon lange, dass es ein Modell der Zermelo-Fraennkel-Mengenlehre (ZFC) gibt, das eine unendliche $ ni$-Kette besitzt – weil man mir das erzählt hat. Wirklich darüber nachgedacht habe ich nie, war auch jetzt nichts, was mich brennend interessiert hat. Umso überraschender war es, als ich über einige umwege zufällig wieder darauf gestoßen bin.

Aber fangen wir mal am Anfang an: Ich machte mir Gedanken über eine kleine, mir unklare Sache bezüglich der Busy-Bever-Funktion mathbbm{N} rightarrow mathbbm{N}$, eine Funktion, die jeder natürlichen Zahl $ n$ die maximale Anzahl an programmschritten, die ein terminierendes Turingprogramm mit $ n$ Zuständen vor seiner Terminierung haben kann, zuordnet (die Definition auf Wikipedia ist eine Andere, Ähnliche, aber nicht äquivalente, aber ebenfalls nicht effektiv berechenbar). Diese Funktion ist nicht effektiv berechenbar, und ihre Berechenbarkeit ist äquivalent mit der Lösung des Halteproblems. Eine Sache, die mir schon seit Langem nicht ganz klar war, und ich habe mir eigentlich nie die Zeit genommen, mal genauer darüber nachzudenken – früher, noch zu Schulzeiten, einfach aus dem Grund, weil mir das Wissen wohl sowieso gefehlt hätte, aber inzwischen werden viele der Fragen, die ich mir damals stellte, mehr oder weniger trivial. Nur in dieser einen hatte ich soetwas wie eine Denkblockade seit Langem.

Nun, die Frage, die ich mir stellte, lief auf Folgendes hinaus: Angenommen, $ forall n in mathbbm{N} exists k in mathbbm{N}. ensuremath{operatorname{ZFC}} models ensuremath{operatorname{bbf}} (n) = k$, das heißt, angenommen, kein Wert von $ ensuremath{operatorname{bbf}}$ ist unabhängig von ZFC. Dann würde nach dem Vollständigkeitssatz gelten $ forall n in mathbbm{N} exists k in mathbbm{N}. ensuremath{operatorname{ZFC}} vdash ensuremath{operatorname{bbf}} (n) = k$, und somit könnte man mit einem einfachen Beweiscomputer, der alle Beweise so lange durchgeht, bis er eine Aussage der Form $ ensuremath{operatorname{bbf}} (n) = k$ im Sukzedens eines Beweises findet, für jedes $ n$ den Wert von $ ensuremath{operatorname{bbf}} (n)$ effektiv berechnen, denn man weiß, dass der Algorithmus für jedes $ n$ terminieren müsste. Das geht natürlich nicht. Also muss mindestens ein Wert $ ensuremath{operatorname{bbf}} (n)$ unabhängig von ZFC sein, und damit trivialerweise auch alle Werte $ ensuremath{operatorname{bbf}} (m), m > n$. Das heißt – nicht ganz unabhängig, natürlich wäre er durch einige Faktoren nach unten begrenzt, aber ansonsten trotzdem frei wählbar, ohne dass sich ein Widerspruch ergeben dürfte. Dies klang für mich zu Schulzeiten, als ich noch relativ wenig Ahnung über, aber dafür umsomehr Zeit und Interesse für Modelltheorie hatte, unplausibel, sind doch Turing-programme endliche Objekte, und die Aussage, ein Turingprogramm terminiert, ist auf die Aussage über die Endlichkeit einer Zahlensequenz, die einer gewissen Vorschrift genügt, zurückzuführen, und meine naive Überzeugung war, endlichkeit wäre ,,eindeutig„, das heißt, die endlichen Mengen sind in jedem ZFC-Modell die selben, eine Menge, die in einem ZFC-Modell endlich ist, ist auch in jedem anderen ZFC-Modell endlich.

Natürlich war genau das der Trugschluss. Nun, reflektieren wir kurz über Endlichkeit. Für die meisten Mathematiker ist eine Menge genau dann Endlich, wenn es eine Bijektion auf eine Menge der Form $ {1, 2, ldots, n}, n in mathbbm{N}$ gibt. Dies setzt aber die Bekanntheit von $ mathbbm{N}$ voraus, und führt zu dem Zyrkelschluss, $ mathbbm{N}$ als Menge der endlichen (Ordinal)Zahlen zu definieren – oder als kleinste Ordinalzahl, die unendlich ist. Aber auch das ist ein Zyrkelschluss – was ist unendlich? Nun, ich bevorzuge die intrinsische Definition, die man allgemein als Dedekind-Endlichkeit bezeichnet. Eine Menge $ X$ ist demnach genau dann Endlich, wenn es keine Injektion X rightarrow X$ gibt, die nicht auch Bijektion ist. Bezeichne das Kürzel $ ensuremath{operatorname{end}} (X)$ diesen Fakt (ich überlasse es dem gewandten Leser jetzt, die Aussage formal hinzuschreiben). Als Zahlen nimmt man wohl am Besten die Ordinalzahlen, es gibt mehrere äquivalente Definitionen der Ordinalzahlen, sucht euch doch selber eine aus, auf Wikipedia stehen eine ganze Menge, die in ZFC äquivalent sind, drücke $ ensuremath{operatorname{ord}} (X)$ aus, dass $ X$ eine Ordinalzahl ist. Für Ordinalzahlen giltx < y Leftrightarrow x in y$.

So, dann können wir also z.B. definieren ={x vert ensuremath{operatorname{ord}} (x) wedge ensuremath{operatorname{end}} (x)}$. Jetzt, da wir die Begrifflichkeiten auch für alle Nichtmengentheoretiker soweit geklärt haben (den Mengentheoretikern stellen sich wahrscheinlich inzwischen sowieso die Zehennägel über so viel Un-Formalismus…), komme ich vielleicht mal zum punkt. Bezeichne ZFC die Menge der ZFC-Axiome, $ L_{ensuremath{operatorname{ZFC}}} ={in, varnothing}$, wobei wir eigentlich auch $ varnothing$ nicht brauchen, aber mei, es ist halt etwas praktischer manchmal.. Sei $ L_{ensuremath{operatorname{ZFC}}'} = L_{ensuremath{operatorname{ZFC}}} cup {x}$, wobei $ x$ eine Konstante (nullstelliges Funktionssymbol) sei. Wir betrachten die Menge $ ensuremath{operatorname{ZFC}}' = ensuremath{operatorname{ZFC}} cup { lc... ...ame{end}} (x) rceil } cup { lceil n in x rceil vert n in mathbbm{N}}$. Oh, wie unübersichtlich. $ lceil cdot rceil$ drücke aus, dass die syntaktische Aussage, also die Zeichenkette, die die Aussage repräsentiert, gemeint ist. Wir fügen also $ ensuremath{operatorname{ZFC}}$ Axiome zu, dass die Konstante $ x$ für eine endliche Ordinalzahl steht, und dass $ n in x$ für jede endliche Ordinalzahl $ n$, also anders gesagt $ n < x$. Wenn wir davon ausgehen, dass $ ensuremath{operatorname{ZFC}}$ erfüllbar ist, folgt aus dem Kompaktheitssatz, dass auch $ ensuremath{operatorname{ZFC}}'$ erfüllbar ist, denn jede endliche Teilmenge von $ ensuremath{operatorname{ZFC}}'$ ist offensichtlich erfüllbar, wir müssen nur $ x = n + 1$ für das größte vorkommende $ n$ setzen.

Es gibt also ein $ ensuremath{operatorname{ZFC}}'$-Modell. Schauen wir uns dieses $ x$ mal an. Dieses $ x$ ist größer als jede ,,unserer„ natürlichen Zahlen. Andererseits haben wir gefordert, dass $ x$ selbst Ordinalzahl ist, und vor Allem, dass $ x$ endlich ist. Aber $ x$ ist doch ,,offensichtlich„ unendlich. Es kommt noch viel lustiger: Jede endliche Ordinalzahl, die von 0 verschieden ist, hat einen Vorgänger. Also hat auch $ x$ einen Vorgänger, dieser kann nicht in ,,unserem„ $ mathbbm{N}$ liegen, und dessen Vorgänger ebenfalls nicht, es gibt also ,,unendliche„ endliche Zahlen $ x, x - 1, x - 2, ldots$ in diesem Modell, und es gilt $ x ni x - 1 ni x - 2 ni ldots$ – es gibt also sogar eine unendliche absteigende $ in$-Kette. Trotzdem muss ein solches Modell $ ensuremath{operatorname{ZFC}}$ erfüllen, immerhin ist $ ensuremath{operatorname{ZFC}} subseteq ensuremath{operatorname{ZFC}}'$. Was ist da los?

Die Antwort ist ziemlich leicht, wenn man sich an die Definition der Dedekind-Endlichkeit erinnert. Das Modell von $ ensuremath{operatorname{ZFC}}'$ glaubt, $ x$ sei endlich, einfach, weil es keine Injektion $ x rightarrow x$ kennt, die nicht auch Bijektion ist.

Es geht noch weiter. Offensichtlich kann man in einem $ ensuremath{operatorname{ZFC}}'$-Modell kein ZFC-Modell finden, von dem $ ensuremath{operatorname{ZFC}}'$ weiß, dass es ein ZFC-Modell ist, und das ,,weniger„ endliche Zahlen enthält, heißt, dass nicht auch ein Adäquat zu diesem $ x$ enthält, von dem es glaubt, es sei endlich – das folgt einfach daraus, weil man per Induktion zeigen kann, dass jedes Modell von ZFC alle natürlichen Zahlen enthalten muss ( $ varnothing$ ist in jedem Modell per Axiom, und wenn die Ordinalzahl $ n$ enthalten ist, dann auch deren potenzmenge, also $ n + 1$ im endlichen Fall), was im Falle eines $ ensuremath{operatorname{ZFC}}'$-Modells bedeutet, dass alle Zahlen, von denen dieses Modell glaubt, sie seien endlich, darin enthalten sein müssen.

Das heißt, ,,philosophisch„ betrachtet, wenn man sich ,,in„ einem ZFC-Modell befindet, kann man sich kein ZFC-Modell vorstellen, das ,,weniger„ endliche Mengen hat, als das Modell, in dem man sich befindet. Das verhält sich mit dem ZFC-Modell unserer Intuition (falls es ein solches überhaupt eindeutig gibt – der platonist würde wohl sagen, ein solches Modell existiert) dann nicht anders. Das lässt aber auch die philosophische Ansicht zu, dass es vielleicht über unserem intuitiven ZFC-Modell ein für uns nicht plausibles ZFC-Modell geben kann, für das bestimmte Zahlen, die wir für endlich halten, unendlich ist. Um es naiv auszudrücken: Vielleicht kennt irgendein uns nicht plausibles ZFC-Modell eine Injektion von $ {0, 1}$ nach $ {0, 1}$, die nicht bijektiv ist – also glaubt, dass unsere $ 2$ eine unendliche Menge ist. Für uns ist das nicht plausibel – so wie für jedes $ ensuremath{operatorname{ZFC}}'$-Modell nicht plausibel ist, dass $ x$ eine unendliche Menge sein kann.

Ok, das ist jetzt alles wie gesagt mathematisch nicht besonders tiefgründig, aber der Gedanke ist trotzdem irgendwie interessant, finde ich. Also auch mal etwas so einfaches wie ,,Endlichkeit„ zu hinterfragen.

Entschuldigung für die schlechten Formeln… Das Zeug hab ich mit Latex2HTML erzeugen lassen. Ich werd mal bei Gelegenheit nach was Besserem suchen.

Schreibe einen Kommentar

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

%d Bloggern gefällt das: