Typentheorie (Mengenlehre): Unterschied zwischen den Versionen
Kowa (Diskussion | Beiträge) |
Kowa (Diskussion | Beiträge) |
||
| (22 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
= | ==Russellsche Typhierachie== | ||
Um die so genannte [[Russellsche Antinomie]] zu vermeiden, hat [[Bertrand Russell]] vorgeschlagen, die {{Menge}}n in einer '''Typhierarchie''' | Um die so genannte [[Russellsche Antinomie]] zu vermeiden, hat [[Bertrand Russell]] vorgeschlagen, die {{Menge}}n in einer '''Typhierarchie''' | ||
anzuordnen.<ref>{{Quelle|Russell, B. (1903): The Principles of Mathematics}}, [http://fair-use.org/bertrand-russell/the-principles-of-mathematics/s497 | anzuordnen.<ref>{{Quelle|Russell, B. (1903): The Principles of Mathematics}}, [http://fair-use.org/bertrand-russell/the-principles-of-mathematics/s497 §§497–500.]</ref><ref>{{Quelle|Russell, B. (1908): Mathematical Logic as Based on the Theory of Types}}, S. 236ff</ref> | ||
Man beginnt mit einer Menge von [[Urelement]]en (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 0 enthalten. Die Stufe 2 enthält diejenigen Mengen, | ||
die Elemente der Stufe 1 enthalten. Und so weiter. | die Elemente der Stufe 1 enthalten. Und so weiter. | ||
== | ===Anmerkungen=== | ||
Felscher<ref name="Felscher I">{{Quelle|Felscher, W. (1978): Naive Mengen und abstrakte Zahlen I}}</ref> beschreibt die Geschichte der Typhierachie sehr schön: | Felscher<ref name="Felscher I">{{Quelle|Felscher, W. (1978): Naive Mengen und abstrakte Zahlen I}}</ref> beschreibt die Geschichte der Typhierachie sehr schön: | ||
Russell hat die zuvor beschriebene Idee einer Typhierachie in der Principia Mathematica<ref>{{Quelle|Whitehead, A.N.; Russell, B. (1910): Principia Mathematica – Volume I}}</ref> weiter ausgearbeitet. Allerdings war seine Hierachie komplizierter als notwendig, da er neben Mengen auch Relationen und Funktionen typisieren musste. | [[Bertrand Russell]] hat die zuvor beschriebene Idee einer Typhierachie in der Principia Mathematica<ref>{{Quelle|Whitehead, A.N.; Russell, B. (1910): Principia Mathematica – Volume I}}</ref> weiter ausgearbeitet. Allerdings war seine Hierachie komplizierter als notwendig, da er neben Mengen auch Relationen und Funktionen typisieren musste. | ||
Erst nachdem Wiener | Erst nachdem [[Norbert Wiener]] und [[Felix Hausdorff]] [[1914]] gezeigt haben, dass [[geordnetes Paar|geordnete Paare]] als spezielle Mengen aufgefasst werden können<ref>{{Quelle|Wiener (1914)}}</ref><ref>{{Quelle|Hausdorff (1914)}}</ref>, 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<ref>'''Quelle fehlt'''</ref>, ebenfalls verzichtet werden kann. | wie [[Ernst Ramsey]] [[1926]] zeigte<ref>'''Quelle fehlt'''</ref>, ebenfalls verzichtet werden kann. | ||
=Definition: Typhierachie (moderne Variante)= | ==Definition: Typhierachie (moderne Variante<ref name="Felscher I" />)== | ||
Eine '''Typhierachie''' zur Klassifikation von {{Menge}}n ist in Stufen eingeteilt: Die Stufe 0 enthält die | Eine '''Typhierachie''' zur Klassifikation von {{Menge}}n 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== | ===Veranschaulichung=== | ||
Wählt man beispielsweise die natürlichen Zahlen als Elemente der Stufe 0, so ist | Wählt man beispielsweise die natürlichen Zahlen als Elemente der Stufe 0, so ist | ||
| Zeile 25: | Zeile 26: | ||
Stufe 3: ... | Stufe 3: ... | ||
== | ===Anmerkung=== | ||
Diese Typhierarchie reicht aus, um große | Diese Typhierarchie reicht aus, um große | ||
Teile der Analysis und der Mengenlehre darzustellen. | Teile der Analysis und der Mengenlehre darzustellen. | ||
Allerdings ist auch diese Struktur noch ziemlich sperrig. | 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 | 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 | hat man einen luxuriösen Vorrat an leeren Mengen: Auf jeder Stufe gibt es eine eigene leere Menge.<ref name="Felscher I" /> | ||
= Definition: Kumulative Typhierachie<ref name="Felscher I"/>= | == Definition: Kumulative Typhierachie<ref name="Felscher I" /><ref name="Schwichtenberg">{{Quelle|Schwichtenberg, H. (2000): Mathematische Logik}}</ref>== | ||
Eine '''kumulative Typhierachie''' zur Klassifikation von {{Menge}}n ist in Stufen eingeteilt: Die Stufe 0 enthält die | Eine '''kumulative Typhierachie''' oder '''kumulative Typenstruktur''' zur Klassifikation von {{Menge}}n 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: | Zwei Fragen ergeben sich: | ||
# Welche Elemente wählt man als | # Welche Elemente wählt man als Urelemente der Stufe 0? Die Stufe 0 enthält als einzige Stufe keine Mengen. | ||
# Wie viele Stufen benötigt man? | # Wie viele Stufen benötigt man? | ||
Zu 1.: Wählt man beispielsweise die natürlichen Zahlen als Elemente der Stufe 0, so ist | 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: | {1,5,7} ein Element der Stufe 1 und {1,5,{5,7}} ein Element der Stufe 2: | ||
Stufe 0: 0, 1, 2, ...<br /> | |||
Stufe 1: 0, 1, 2, ..., {}, {0}, {1}, ..., {0,1}, {0,2}, ...<br /> | |||
Stufe 2: 0, 1, 2, ..., {}, {0}, {1}, ..., {0,1}, {0,2}, ..., {{}}, {{}, 0}, {{}, 1}, ..., {{}, {0}}, {{}, 0, {0}}, ..., ...<br /> | |||
Stufe 3: ... | |||
Aus rein mathematischer Sicht ist es gar nicht notwendig, irgendwelche | 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: | Objekte (nämlich Mengen), die man mit den übrigen Objekten unserer Anschauung und unseres Denkens identifizieren kann | ||
(vgl. [[Klasse (Mengenlehre)#Verzicht auf Urelemente|Klasse, Abschnitt „Verzicht auf Urelemente“]]): | |||
Stufe 0: -<br /> | Stufe 0: -<br /> | ||
| Zeile 54: | Zeile 61: | ||
Stufe 4: ... | Stufe 4: ... | ||
Diese Alternative wird heute i. Allg. bevorzugt, da man dann bei Beweisen auf | Diese Alternative wird heute i. Allg. bevorzugt, da man dann bei Beweisen auf Fallunterscheidungen der Art | ||
„Falls x | „Falls x Urelement ist ..., anderenfalls ...“ verzichten kann. | ||
Zu 2.: Die ursprüngliche kumulative Struktur von Russell hatte | 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.<ref name="Schwichtenberg"/> | Dazu wendet man das so genannte [[Shoenfield-Prinzip]] an.<ref name="Schwichtenberg" /> | ||
Dieses Prinzip ist zwar etwas schwammig formuliert, aber beschreibt die Fortführung der Stufen doch ganz anschaulich: | Dieses Prinzip ist zwar etwas schwammig formuliert, aber beschreibt die Fortführung der Stufen doch ganz anschaulich: | ||
{{Quote|Man betrachte eine Gesamtheit S von Stufen. | {{Quote|Man betrachte eine Gesamtheit S von Stufen. | ||
| Zeile 69: | Zeile 76: | ||
unendliche vielen Schritte zusammenfasst. | unendliche vielen Schritte zusammenfasst. | ||
===LISP=== | |||
[[John McCarthy]] greift die Idee der Typhierarchie für die Programmiersprache [[LISP]] auf. | [[John McCarthy]] greift die Idee der kumulativen Typhierarchie für die Programmiersprache [[LISP]] auf. | ||
Sowohl die LISP-Anweisungen, als auch die LISP-[[Datenstruktur]]en werden ausschließlich mit Hilfe von | Sowohl die LISP-Anweisungen, als auch die LISP-[[Datenstruktur]]en werden ausschließlich mit Hilfe von | ||
so genannten LISP-Atomen (Zeichenketten, Zahlen etc.) als „Urelemente“ und [[geordnetes Paar|geordneten Paaren]] | so genannten LISP-Atomen (Zeichenketten, Zahlen etc.) als „Urelemente“ und [[geordnetes Paar|geordneten Paaren]] | ||
| Zeile 77: | Zeile 84: | ||
Paare als Elemente enthalten.<ref>{{Quelle|McCarthy, J. et. al. (1960): LISP I Programmer's Manual}}</ref> | Paare als Elemente enthalten.<ref>{{Quelle|McCarthy, J. et. al. (1960): LISP I Programmer's Manual}}</ref> | ||
= | ===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]]) {{Menge}}n und {{Klasse}}n 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. | 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]]) {{Menge}}n und {{Klasse}}n 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)=== | ====Unterschied zwischen Mengen und Unmengen (= echten Klassen)==== | ||
Man kann sich | Die kumulative Typhierachie, kann auch in modernen Axiomensystem sehr vorteilhaft eingesetzt werden. | ||
Man kann sich damit den Unterschied zwischen {{Menge}}n und {{Unmenge}}n verdeutlichen: | |||
Sowohl Mengen als auch Unmengen fassen Elemente, die sich auf irgendwelchen Stufen der kumulativen Typenstruktur befinden, | Sowohl Mengen als auch Unmengen fassen Elemente, die sich auf irgendwelchen Stufen der kumulativen Typenstruktur befinden, | ||
| Zeile 97: | Zeile 101: | ||
Und eine Unmenge enthält also tatsächlich Unmengen von Elementen. | Und eine Unmenge enthält also tatsächlich Unmengen von Elementen. | ||
=Quellen= | ==Quellen== | ||
<references/> | <references /> | ||
=Siehe auch= | ==Siehe auch== | ||
*[[Wikipedia:Typentheorie]] | *[[Wikipedia:Typentheorie]] | ||
*[[Wikipedia:Kumulative Hierarchie]] | |||
[[Kategorie:Mengenlehre]] | [[Kategorie:Mengenlehre]] | ||
[[Kategorie:Glossar]] | [[Kategorie:Glossar]] | ||
Aktuelle Version vom 30. Mai 2019, 15:54 Uhr
Russellsche Typhierachie
Um die so genannte Russellsche Antinomie zu vermeiden, hat Bertrand Russell vorgeschlagen, die Mengen in einer Typhierarchie anzuordnen.[1][2] 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[3] beschreibt die Geschichte der Typhierachie sehr schön: Bertrand Russell hat die zuvor beschriebene Idee einer Typhierachie in der Principia Mathematica[4] 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[5][6], 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[7], ebenfalls verzichtet werden kann.
Definition: Typhierachie (moderne Variante[3])
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.[3]
Definition: Kumulative Typhierachie[3][8]
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:
- Welche Elemente wählt man als Urelemente der Stufe 0? Die Stufe 0 enthält als einzige Stufe keine Mengen.
- 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.[8] 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.“[9]
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.[10]
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.
Quellen
- ↑ Russell (1903): Bertrand Russell; The Principles of Mathematics; Auflage: 2; Verlag: W. W. Norton & Company; Adresse: Berlin; Web-Link; 1903; Quellengüte: 5 (Buch), §§497–500.
- ↑ Russell (1908): Bertrand Russell; Mathematical Logic as Based on the Theory of Types; in: American Journal of Mathematics; Band: 30; Nummer: 3; Seite(n): 222–262; Verlag: The Johns Hopkins University Presss; Adresse: Baltimore; Web-Link 0, Web-Link 1; 1908; Quellengüte: 5 (Artikel), S. 236ff
- ↑ 3,0 3,1 3,2 3,3 Felscher (1978): W. Felscher; Naive Mengen und abstrakte Zahlen; Band: 1; Verlag: BI-Wissenschaftsverlag; Adresse: Mannheim; ISBN: 3-411-01538-1; 1978; Quellengüte: 5 (Buch)
- ↑ Whitehead, Russell (1910): Alfred North Whitehead und Bertrand Russell; Principia Mathematica; Band: 1; Verlag: Cambridge University Press; Adresse: Cambridge; Web-Link 0, Web-Link 1; 1910; Quellengüte: 5 (Buch)
- ↑ Wiener (1914): Norbert Wiener; A Simplification of the Logic of Relations; in: Proceedings of Cambridge Philosophical Society; Band: 17; Seite(n): 387-390; Web-Link; 1914; Quellengüte: 5 (Artikel)
- ↑ Hausdorff (1914): Felix Hausdorff; Grundzüge der Mengenlehre; Verlag: Veit and Company; Adresse: Leipzig; Web-Link; 1914; Quellengüte: 5 (Buch)
- ↑ Quelle fehlt
- ↑ 8,0 8,1 Schwichtenberg (2000): Helmut Schwichtenberg; Mathematische Logik; Hochschule: Ludwig-Maximilians-Universität; Adresse: München; Web-Link; 2000; Quellengüte: 5 (Skript)
- ↑ Shoenfield (1967): Joseph R. Shoenfield; Mathematical Logic; Verlag: Addison-Wesley; Adresse: Reading, Massachusetts; ISBN: 0201070286; 1967; Quellengüte: 5 (Buch)
- ↑
