Typentheorie (Mengenlehre)

Russellsche Typhierachie

Um die so genannte Russellsche Antinomie zu vermeiden, hat Bertrand Russell vorgeschlagen, die Mengen in einer Typhierarchie anzuordnen. Man beginnt mit einer Menge von Urelementen (Grundelementen, individuals), die die Mengen der Stufe 0 bilden. Die Stufe 1 enthält diejenigen Mengen, die Elemente der Stufe 0 enthalten. Die Stufe 2 enthält diejenigen Mengen, die Elemente der Stufe 1 enthalten. Und so weiter.

Anmerkungen

Felscher beschreibt die Geschichte der Typhierachie sehr schön: Bertrand Russell hat die zuvor beschriebene Idee einer Typhierachie in der Principia Mathematica weiter ausgearbeitet. Allerdings war seine Hierachie komplizierter als notwendig, da er neben Mengen auch Relationen und Funktionen typisieren musste. Erst nachdem Norbert Wiener und Felix Hausdorff 1914 gezeigt haben, dass geordnete Paare als spezielle Mengen aufgefasst werden können, konnte auf diese Unterscheidung verzichtet werden. Neben der Typhierarchie der Mengen führte Russell eine zweite Hierarchie zur Vermeidung von Antinomien ein, auf die, wie Ernst Ramsey 1926 zeigte, ebenfalls verzichtet werden kann.

Definition: Typhierachie (moderne Variante)

Eine Typhierachie zur Klassifikation von Mengen ist in Stufen eingeteilt: Die Stufe 0 enthält die Urelemente (bei denen es sich nicht um Mengen handelt). Die Stufe n+1 enthält alle möglichen Mengen von Elementen der Stufe n.

Veranschaulichung

Wählt man beispielsweise die natürlichen Zahlen als Elemente der Stufe 0, so ist {1,5,7} ein Element der Stufe 1 und {{1},{5,7}} ein Element der Stufe 2:

Stufe 0: 0, 1, 2, ...
Stufe 1: {}, {0}, {1}, ..., {0,1}, {0,2}, ...,
Stufe 2: {{}}, {{0}}, {{1}}, ..., {{0,1}}, {{0,2}}, ..., ..., {{},{0}}, ..., {{},{0},{0,1}}, ...
Stufe 3: ...

Anmerkung

Diese Typhierarchie reicht aus, um große Teile der Analysis und der Mengenlehre darzustellen. Allerdings ist auch diese Struktur noch ziemlich sperrig. Man kann z.B: keine Mengen der Art {1, {1,2,3}} bilden, da 1 und {1,2,3} auf unterschiedlichen Stufen liegen. Außerdem hat man einen luxuriösen Vorrat an leeren Mengen: Auf jeder Stufe gibt es eine eigene leere Menge.

Definition: Kumulative Typhierachie

Eine kumulative Typhierachie oder kumulative Typenstruktur zur Klassifikation von Mengen ist in Stufen eingeteilt: Die Stufe 0 enthält die Urelemente (bei denen es sich nicht um Mengen handelt). Die Stufe n+1 enthält alle Elemente der Stufe n sowie alle möglichen Mengen von Elementen der Stufe n.

Anmerkungen

Zwei Fragen ergeben sich:

1. Welche Elemente wählt man als Urelemente der Stufe 0? Die Stufe 0 enthält als einzige Stufe keine Mengen.
2. Wie viele Stufen benötigt man?

Zu 1.: Wählt man beispielsweise die natürlichen Zahlen als Elemente der Stufe 0, so ist {1,5,7} ein Element der Stufe 1 und {1,5,{5,7}} ein Element der Stufe 2:

Stufe 0: 0, 1, 2, ...
Stufe 1: 0, 1, 2, ..., {}, {0}, {1}, ..., {0,1}, {0,2}, ...
Stufe 2: 0, 1, 2, ..., {}, {0}, {1}, ..., {0,1}, {0,2}, ..., {{}}, {{}, 0}, {{}, 1}, ..., {{}, {0}}, {{}, 0, {0}}, ..., ...
Stufe 3: ...

Aus rein mathematischer Sicht ist es gar nicht notwendig, irgendwelche Urelemente zu wählen. Man erhält auch ohne sie genug Objekte (nämlich Mengen), die man mit den übrigen Objekten unserer Anschauung und unseres Denkens identifizieren kann (vgl. Klasse, Abschnitt „Verzicht auf Urelemente“):

Stufe 0: -
Stufe 1: {}
Stufe 2: {}, {{}}
Stufe 3: {}, {{}}, {{{}}}, {{},{{}}}
Stufe 4: ...

Diese Alternative wird heute i. Allg. bevorzugt, da man dann bei Beweisen auf Fallunterscheidungen der Art „Falls x Urelement ist ..., anderenfalls ...“ verzichten kann.

Zu 2.: Die ursprüngliche kumulative Struktur von Russell hatte abzählbar viele Stufen. Allerdings kann und sollte man darüber hinausgehen, wenn man überanzählbare Mengen (wie z.B. die Menge der reellen Zahlen beschreiben können will). Dazu wendet man das so genannte Shoenfield-Prinzip an. Dieses Prinzip ist zwar etwas schwammig formuliert, aber beschreibt die Fortführung der Stufen doch ganz anschaulich:

Man betrachte eine Gesamtheit S von Stufen. Kann man sich eine Situation vorstellen, in der alle Stufen aus S konstruiert sind, so soll es eine Stufe geben, die nach allen Stufen aus S kommt.“

Dieses Prinzip wird z.B. auch bei der transfiniten Induktion und den Ordinalzahlen verwendet. Es besagt, dass nach unendlich vielen Schritten jeweils ein weiterer kommt, der die Ergebnisse dieser unendliche vielen Schritte zusammenfasst.

LISP

John McCarthy greift die Idee der kumulativen Typhierarchie für die Programmiersprache LISP auf. Sowohl die LISP-Anweisungen, als auch die LISP-Datenstrukturen werden ausschließlich mit Hilfe von so genannten LISP-Atomen (Zeichenketten, Zahlen etc.) als „Urelemente“ und geordneten Paaren – anstelle von Mengen – als Element-„Container“ gebildet. Paare können dabei sowohl Atome, als auch andere Paare als Elemente enthalten.

Axiomatisierung

Heute formalisiert man die Mengenlehre i. Allg. nicht mehr auf mit Hilfe von Typhierachien, sondern führt mit Hilfe von allgemeineren Axiomen (siehe z.B. Zermelo-Fraenkel-Mengenlehre, Neumann-Bernays-Gödel-Mengenlehre) Mengen und Klassen ein und kann dann für die meisten dieser Axiome zeigen, dass die kumulative Typenstruktur diese Axiome erfüllt. Das heißt, die kumulative Typenstruktur kann und sollte in vielen Fällen als anschauliches Modell dienen.

Unterschied zwischen Mengen und Unmengen (= echten Klassen)

Die kumulative Typhierachie, kann auch in modernen Axiomensystem sehr vorteilhaft eingesetzt werden. Man kann sich damit den Unterschied zwischen Mengen und Unmengen verdeutlichen:

Sowohl Mengen als auch Unmengen fassen Elemente, die sich auf irgendwelchen Stufen der kumulativen Typenstruktur befinden, zu einer Einheit zusammen. Der Unterschied ist, dass eine Menge selbst auf einer Stufe (und damit auch auf allen höheren Stufen) der Typenstruktur zu liegen kommt. Das heißt, es gibt eine Stufe, die größer ist als die minimalen Stufen aller Elemente dieser Menge (wobei die minimale Stufe einer Menge die erste Stufe bezeichnet, auf der diese Menge zu liegen kommt).

Eine Unmenge dagegen fasst so viele Elemente von unterschiedlichen Stufen zur einer Einheit zusammen, dass es keine größte Stufe der in dieser Klasse enthaltenen Elemente gibt. Zu jedem Element in der Unmenge gibt es beliebig viele weitere Elemente in der Unmenge, die auf beliebig höheren Stufen liegen. Eine Unmenge kann daher auf gar keiner Stufe liegen. Und eine Unmenge enthält also tatsächlich Unmengen von Elementen.

Siehe auch

• Wikipedia:Typentheorie
• Wikipedia:Kumulative Hierarchie