Typentheorie

Inhaltsverzeichnis:

Typentheorie
Typentheorie

Video: Typentheorie

Video: Typentheorie
Video: Type Theory Foundations, Lecture 1 2024, March
Anonim

Eintragsnavigation

  • Eintragsinhalt
  • Literaturverzeichnis
  • Akademische Werkzeuge
  • Freunde PDF Vorschau
  • Autor und Zitierinfo
  • Zurück nach oben

Typentheorie

Erstveröffentlichung Mi 8. Februar 2006; inhaltliche Überarbeitung Di 17.07.2018

Das Thema Typentheorie ist sowohl in der Logik als auch in der Informatik von grundlegender Bedeutung. Wir beschränken uns hier darauf, einige Aspekte zu skizzieren, die für die Logik wichtig sind. Für die Bedeutung von Typen in der Informatik verweisen wir den Leser beispielsweise auf Reynolds 1983 und 1985.

  • 1. Paradoxe und Russells Typentheorien
  • 2. Einfache Typentheorie und der (lambda) - Kalkül
  • 3. Ramified Hierarchy und Impredicative Principles
  • 4. Typentheorie / Mengenlehre
  • 5. Typentheorie / Kategorietheorie
  • 6. Erweiterungen des Typensystems, Polymorphismus, Paradoxe
  • 7. Einwertige Grundlagen
  • Literaturverzeichnis
  • Akademische Werkzeuge
  • Andere Internetquellen
  • Verwandte Einträge

1. Paradoxe und Russells Typentheorien

Die Typentheorie wurde von Russell eingeführt, um mit einigen Widersprüchen fertig zu werden, die er in seinem Bericht über die Mengenlehre gefunden hatte, und wurde in „Anhang B: Die Doktrin der Typen“von Russell 1903 eingeführt. Dieser Widerspruch wurde durch Analyse eines Satzes von Cantor erhalten dass keine Zuordnung

[F: X / rightarrow / Pow (X))

(wobei (Pow (X)) die Klasse von Unterklassen einer Klasse (X) ist) kann surjektiv sein; Das heißt, (F) kann nicht so sein, dass jedes Mitglied (b) von (Pow (X)) für ein Element (a) von / gleich (F (a)) ist (X). Dies kann "intuitiv" ausgedrückt werden als die Tatsache, dass es mehr Teilmengen von (X) als Elemente von (X) gibt. Der Beweis dieser Tatsache ist so einfach und grundlegend, dass es sich lohnt, ihn hier zu geben. Betrachten Sie die folgende Teilmenge von (X):

[A = {x / in X / mid x / not / in F (x) }.)

Diese Teilmenge darf nicht im Bereich von (F) liegen. Für wenn (A = F (a)), für einige (a), dann

) begin {align} a / in F (a) & / text {iff} a / in A \& / text {iff} a / not / in F (a) end {align})

Das ist ein Widerspruch. Einige Bemerkungen sind angebracht. Erstens verwendet der Beweis nicht das Gesetz der ausgeschlossenen Mitte und ist daher intuitiv gültig. Zweitens war die verwendete Methode, Diagonalisierung genannt, bereits in der Arbeit von du Bois-Reymond vorhanden, um reale Funktionen zu erstellen, die schneller wachsen als jede Funktion in einer bestimmten Folge von Funktionen.

Russell analysierte, was passiert, wenn wir diesen Satz auf den Fall anwenden, in dem A die Klasse aller Klassen ist, und gab zu, dass es eine solche Klasse gibt. Er wurde dann veranlasst, die spezielle Klasse von Klassen zu betrachten, die nicht zu sich selbst gehören

) tag {*} R = {w / mid w / not / in w }.)

Wir haben dann

[R / in R / text {iff} R / not / in R.)

Es scheint tatsächlich, dass Cantor sich bereits der Tatsache bewusst war, dass die Klasse aller Mengen nicht selbst als Menge betrachtet werden kann.

Russell teilte Frege dieses Problem mit, und sein Brief erscheint zusammen mit Freges Antwort in van Heijenoort 1967. Es ist wichtig zu wissen, dass die Formulierung (*) nicht so gilt wie für Freges System. Wie Frege selbst in seiner Antwort an Russell schrieb, ist der Ausdruck „ein Prädikat ist ein Prädikat für sich selbst“nicht genau. Frege unterschied zwischen Prädikaten (Konzepten) und Objekten. Ein Prädikat (erster Ordnung) gilt für ein Objekt, kann jedoch kein Prädikat als Argument haben. Die genaue Formulierung des Paradoxons in Freges System verwendet den Begriff der Erweiterung eines Prädikats (P), das wir als (varepsilon P) bezeichnen. Die Erweiterung eines Prädikats ist selbst ein Objekt. Das wichtige Axiom V ist:

) tag {Axiom V} varepsilon P = / varepsilon Q / äquiv / für alle x [P (x) äquiv Q (x)])

Dieses Axiom besagt, dass die Erweiterung von (P) genau dann mit der Erweiterung von (Q) identisch ist, wenn (P) und (Q) materiell äquivalent sind. Wir können dann Russells Paradoxon (*) in Freges System übersetzen, indem wir das Prädikat definieren

[R (x) text {iff} existiert P [x = / varepsilon P / wedge / neg P (x)])

Mit Axiom V kann dann entscheidend überprüft werden, dass

[R (varepsilon R) equiv / neg R (varepsilon R))

und wir haben auch einen Widerspruch. (Beachten Sie, dass wir zur Definition des Prädikats (R) eine improvisatorische existenzielle Quantifizierung für Prädikate verwendet haben. Es kann gezeigt werden, dass die prädikative Version des Frege-Systems konsistent ist (siehe Heck 1996 und weitere Verfeinerungen Ferreira 2002).

Aus diesem Bericht geht hervor, dass in Freges Arbeit bereits eine Idee von Typen vorhanden war: Dort finden wir eine Unterscheidung zwischen Objekten, Prädikaten (oder Konzepten), Prädikaten von Prädikaten usw. (Dieser Punkt wird in Quine 1940 betont.) Diese Hierarchie wird von Russell (1959) als "Extensionshierarchie" bezeichnet, und seine Notwendigkeit wurde von Russell als Folge seines Paradoxons erkannt.

2. Einfache Typentheorie und der (lambda) - Kalkül

Wie wir oben gesehen haben, scheint die Unterscheidung: Objekte, Prädikate, Prädikate von Prädikaten usw. genug zu sein, um Russells Paradoxon zu blockieren (und dies wurde von Chwistek und Ramsey erkannt). Wir beschreiben zuerst die Typstruktur, wie sie in Principia ist, und später in diesem Abschnitt präsentieren wir die elegante Formulierung aufgrund der Kirche 1940, die auf (lambda) - Kalkül basiert. Die Typen können definiert werden als

  1. (i) ist die Art von Individuen
  2. ((,)) ist die Art der Sätze
  3. Wenn (A_1, / ldots, A_n) Typen sind, dann ist ((A_1, / ldots, A_n)) der Typ von (n) - Beziehungen über Objekte des jeweiligen Typs (A_1, / ldots, Ein)

Zum Beispiel ist die Art der binären Beziehungen über Individuen ((i, i)), die Art der binären Verbindungen ist (((,), (,))), die Art der Quantifizierer über Individuen ist \(((ich))).

Zur Bildung von Sätzen verwenden wir diese Typstruktur: Somit ist (R (a_1, / ldots, a_n)) ein Satz, wenn (R) vom Typ ((A_1, / ldots, A_n)) und (a_i) ist vom Typ (A_i) für (i = 1, / ldots, n). Diese Einschränkung macht es unmöglich, einen Satz der Form (P (P)) zu bilden: Der Typ von (P) sollte von der Form ((A)) sein, und (P) kann nur auf Argumente vom Typ (A) angewendet werden und kann daher nicht auf sich selbst angewendet werden, da (A) nicht dasselbe ist wie ((A)).

Eine einfache Typentheorie ist jedoch nicht aussagekräftig: Wir können ein Objekt (Q (x, y)) vom Typ ((i, i)) durch definieren

) für alle P [P (x) supset P (y)])

Angenommen, wir haben zwei Individuen (a) und (b), so dass (Q (a, b)) gilt. Wir können (P (x)) als (Q (x, a)) definieren. Es ist dann klar, dass (P (a)) gilt, da es (Q (a, a)) ist. Daher gilt auch (P (b)). Wir haben auf beeindruckende Weise bewiesen, dass (Q (a, b)) (Q (b, a)) impliziert.

Alternative einfachere Formulierungen, die nur den Begriff der Klassen, Klassen von Klassen usw. beibehalten, wurden von Gödel und Tarski formuliert. Tatsächlich wurde diese einfachere Version von Gödel in seiner Arbeit von 1931 über formal unentscheidbare Sätze verwendet. Die Entdeckung der unentscheidbaren Sätze könnte durch ein heuristisches Argument motiviert worden sein, dass es unwahrscheinlich ist, dass man den Vollständigkeitssatz der Logik erster Ordnung auf die Typentheorie ausweiten kann (siehe das Ende seiner Vorlesung in Königsberg 1930 in Gödel Collected Work, Band III) und Goldfarb 2005). Tarski hatte eine Version des Definierbarkeitssatzes, der in der Typentheorie ausgedrückt wurde (siehe Hodges 2008). Siehe Schiemer und Reck 2013.

Wir haben Objekte vom Typ 0 für Individuen, Objekte vom Typ 1, für Klassen von Individuen, Objekte vom Typ 2, für Klassen von Klassen von Individuen und so weiter. Funktionen von zwei oder mehr Argumenten wie Relationen müssen nicht in primitiven Objekten enthalten sein, da man Relationen als Klassen geordneter Paare und geordnete Paare als Klassen von Klassen definieren kann. Zum Beispiel kann das geordnete Paar von Individuen a, b als ({ {a }, {a, b } }) definiert werden, wobei ({x, y }) bezeichnet die Klasse, deren einzige Elemente (x) und (y) sind. (Wiener 1914 hatte eine ähnliche Reduktion der Beziehungen zu Klassen vorgeschlagen.) In diesem System haben alle Sätze die Form (a (b)), wobei (a) ein Zeichen vom Typ (n + 1) ist. und (b) ein Zeichen vom Typ (n). Somit basiert dieses System auf dem Konzept einer beliebigen Klasse oder Teilmenge von Objekten einer gegebenen Domäne und auf der Tatsache, dass die Sammlung aller Teilmengen der gegebenen Domäne eine neue Domäne des nächsten Typs bilden kann. Ausgehend von einer bestimmten Domäne von Personen wird dieser Prozess dann wiederholt. Wie zum Beispiel in Scott 1993 betont, wird dieser Prozess der Bildung von Teilmengen in der Mengenlehre in das Transfinite iteriert.

In diesen Versionen der Typentheorie sind Funktionen wie in der Mengenlehre keine primitiven Objekte, sondern werden als funktionale Beziehung dargestellt. Die Additionsfunktion wird beispielsweise als ternäre Beziehung durch ein Objekt vom Typ ((i, i, i)) dargestellt. Eine elegante Formulierung der einfachen Typentheorie, die sie durch die Einführung von Funktionen als primitive Objekte erweitert, wurde 1940 von der Kirche gegeben. Sie verwendet die (lambda) - Kalkülnotation (Barendregt 1997). Da eine solche Formulierung in der Informatik, für den Zusammenhang mit der Kategorietheorie und für die Martin-Löf-Typentheorie wichtig ist, beschreiben wir sie ausführlich. In dieser Formulierung werden Prädikate als eine spezielle Art von Funktionen (Satzfunktionen) angesehen, eine Idee, die auf Frege zurückgeht (siehe zum Beispiel Quine 1940). Außerdem,Der Begriff der Funktion wird als primitiver angesehen als der Begriff der Prädikate und Beziehungen, und eine Funktion wird nicht mehr als eine besondere Art von Beziehung definiert. (Oppenheimer und Zalta 2011 präsentieren einige Argumente gegen eine solche primitive Darstellung von Funktionen.) Die Typen dieses Systems werden induktiv wie folgt definiert

  1. Es gibt zwei Grundtypen (i) (die Art der Individuen) und (o) (die Art der Sätze).
  2. Wenn (A, B) Typen sind, dann ist (A / rightarrow B), der Funktionstyp von (A) bis (B), ein Typ

Wir können auf diese Weise die Typen bilden:

(i / rightarrow o) (Art der Prädikate)
((i / rightarrow o) rightarrow o) (Art der Prädikate der Prädikate)

die den Typen ((i)) und ((((i))) entsprechen, aber auch den neuen Typen

(i / rightarrow i) (Art der Funktionen)
((i / rightarrow i) rightarrow i) (Art der Funktionale)

Es ist bequem zu schreiben

[A_1, / ldots, A_n / rightarrow B)

zum

[A_1 / rightarrow (A_2 / rightarrow / ldots / rightarrow (A_n / rightarrow B)))

Auf diese Weise

[A_1, / ldots, A_n / rightarrow o)

entspricht dem Typ ((A_1, / ldots, A_n)).

Die Logik erster Ordnung berücksichtigt nur Typen des Formulars

(i, / ldots, i / rightarrow i) (Art der Funktionssymbole), und
(i, / ldots, i / rightarrow o) (Prädikattyp, Beziehungssymbole)

Beachte das

[A / rightarrow B / rightarrow C)

steht für

[A / rightarrow (B / rightarrow C))

(Assoziation rechts).

Für die Begriffe dieser Logik werden wir nicht dem Bericht der Kirche folgen, sondern einer geringfügigen Abweichung davon, aufgrund von Curry (der ähnliche Ideen hatte, bevor das Papier der Kirche erschien) und der in R. Hindleys Buch über Typentheorie ausführlich vorgestellt wird. Wie Church verwenden wir (lambda) - Kalkül, das eine allgemeine Notation für Funktionen liefert

[M:: = x / mid MM / mid / lambda xM)

Hier haben wir die sogenannte BNF-Notation verwendet, die in der Informatik sehr praktisch ist. Dies gibt eine syntaktische Spezifikation der (lambda) - Begriffe, die, wenn sie erweitert werden, bedeuten:

  • Jede Variable ist ein Funktionssymbol.
  • Jedes Nebeneinander zweier Funktionssymbole ist ein Funktionssymbol.
  • jedes (lambda xM) ist ein Funktionssymbol;
  • Es gibt keine anderen Funktionssymbole.

Die Notation für die Funktionsanwendung (MN) unterscheidet sich ein wenig von der mathematischen Notation, die (M (N)) wäre. Allgemein, [M_1 M_2 M_3)

steht für

[(M_1 M_2) M_3)

(Assoziation links). Der Begriff (lambda xM) repräsentiert die Funktion, die (N) (M [x: = N)] zuordnet. Diese Notation ist so praktisch, dass man sich fragt, warum sie in der Mathematik nicht weit verbreitet ist. Die Hauptgleichung von (lambda) - Kalkül lautet dann ((beta) - Umwandlung)

[(Lambda xM) N = M [x: = N])

Dies drückt die Bedeutung von (lambda xM) als Funktion aus. Wir haben (M [x: = N)] als Notation für den Wert des Ausdrucks verwendet, der sich ergibt, wenn (N) die Variable (x) in der Matrix (M) ersetzt. Man sieht diese Gleichung normalerweise als Umschreiberegel ((beta) - Reduktion)

[(lambda xM) N / rightarrow M [x: = N])

Im untypisierten Lambda-Kalkül kann es sein, dass ein solches Umschreiben nicht endet. Das kanonische Beispiel wird durch den Begriff (Delta = / lambda xx x) und die Anwendung gegeben

) Delta / Delta / rightarrow / Delta / Delta)

(Beachten Sie die Ähnlichkeit mit Russells Paradoxon.) Die Idee von Curry besteht dann darin, Typen als Prädikate über Lambda-Begriffe zu betrachten und (M: A) zu schreiben, um auszudrücken, dass (M) das Prädikat / den Typ (A / erfüllt)). Die Bedeutung von

[N: A / rightarrow B)

ist dann

) forall M, / text {if} M: A / text {then} NM: B)

das rechtfertigt die folgenden Regeln

) frac {N: A / rechter Pfeil BM: A} {NM: B})) frac {M: B [x: A]} { Lambda xM: A / rechter Pfeil B})

Im Allgemeinen arbeitet man mit Urteilen der Form

[x_1: A_1,…, x_n: A_n / vdash M: A)

Dabei sind (x_1,…, x_n) unterschiedliche Variablen und (M) ein Begriff mit allen freien Variablen unter (x_1,…, x_n). Um in der Lage zu sein, das System der Kirche zu erhalten, fügt man einige Konstanten hinzu, um Sätze zu bilden. Typischerweise

nicht: (o / rightarrow o)
implizieren: (o / rightarrow o / rightarrow o)
und: (o / rightarrow o / rightarrow o)
für alle: ((A / rightarrow o) rightarrow o)

Der Begriff

) Lambda x. / neg (xx))

stellt das Prädikat von Prädikaten dar, die nicht für sich selbst gelten. Dieser Begriff hat jedoch keinen Typ, das heißt, es ist nicht möglich, (A) so zu finden, dass

) Lambda x. / neg (xx): (A / rightarrow o) rightarrow o)

Das ist der formale Ausdruck der Tatsache, dass Russells Paradoxon nicht ausgedrückt werden kann. Leibniz Gleichheit

[F: i / rightarrow i / rightarrow o)

wird definiert als

[Q = / Lambda x. / lambda y. / forall (lambda P. / implizieren (P x) (P y)))

Normalerweise schreibt man (forall x [M)] anstelle von (forall (lambda xM)), und die Definition von (Q) kann dann umgeschrieben werden als

[Q = / Lambda x. / Lambda y. / Forall P) implizieren (P x) (P y)])

Dieses Beispiel zeigt erneut, dass wir in der einfachen Typentheorie improvisatorische Definitionen formulieren können.

Die Verwendung von (lambda) - Begriffen und (beta) - Reduktion ist am bequemsten, um die komplexen Substitutionsregeln darzustellen, die in der einfachen Typentheorie benötigt werden. Zum Beispiel, wenn wir das Prädikat (lambda xQ ax) für (P) im Satz ersetzen wollen

) implizieren (P a) (P b))

wir bekommen

) implizieren ((lambda xQ ax) a) ((lambda xQ ax) b))

und unter Verwendung von (beta) - Reduktion,) implizieren (Q aa) (Q ab))

Zusammenfassend lässt sich sagen, dass die einfache Typentheorie die Selbstanwendung verbietet, nicht jedoch die Zirkularität, die in improvisierten Definitionen vorhanden ist.

Der (lambda) - Kalkülformalismus ermöglicht auch eine klarere Analyse von Russells Paradoxon. Wir können es als Definition des Prädikats sehen

[R x = / neg (xx))

Wenn wir uns (beta) - Reduktion als den Prozess der Entfaltung einer Definition vorstellen, sehen wir, dass es bereits ein Problem beim Verständnis der Definition von RR gibt

[RR / rightarrow / neg (RR) rightarrow / neg (neg (RR)) rightarrow / ldots)

In gewissem Sinne haben wir eine unbegründete Definition, die ebenso problematisch ist wie ein Widerspruch (ein Satz, der seiner Negation entspricht). Ein wichtiger Satz, der Normalisierungssatz, besagt, dass dies bei einfachen Typen nicht passieren kann: Wenn wir (M: A) haben, ist (M) stark normalisierbar (jede Folge von Reduktionen ab (M)) endet).

Weitere Informationen zu diesem Thema finden Sie im Eintrag zur einfachen Typentheorie der Kirche.

3. Ramified Hierarchy und Impredicative Principles

Russell führte eine andere Hierarchie ein, die nicht durch formale Paradoxien in einem formalen System motiviert war, sondern durch die Angst vor „Zirkularität“und durch informelle Paradoxien, die dem Paradox des Lügners ähnlich waren. Wenn ein Mann sagt „Ich lüge“, dann haben wir eine Situation, die an Russells Paradoxon erinnert: einen Satz, der seiner eigenen Negation entspricht. Eine andere informelle solche paradoxe Situation ergibt sich, wenn wir eine Ganzzahl als die „kleinste Ganzzahl definieren, die in weniger als 100 Wörtern nicht definierbar ist“. Um solche informellen Paradoxien zu vermeiden, hielt Russell es für notwendig, eine andere Art von Hierarchie einzuführen, die sogenannte „verzweigte Hierarchie“. Die Notwendigkeit einer solchen Hierarchie wird in Anhang B von Russell 1903 angedeutet. Interessanterweise hängt dies dort mit der Frage der Identität äquivalenter Sätze und des logischen Produkts einer Klasse von Sätzen zusammen. Eine ausführliche Diskussion findet sich in Kapitel 10 von Russell 1959. Da dieser Begriff der verzweigten Hierarchie einen großen Einfluss auf die Logik und insbesondere auf die Beweistheorie hatte, beschreiben wir ihn in einigen Details.

Um diese Hierarchie weiter zu motivieren, ist hier ein Beispiel von Russell. Wenn wir sagen

Napoleon war Korsier.

Wir verweisen in diesem Satz nicht auf eine Zusammenstellung von Eigenschaften. Die Eigenschaft "korsisch sein" soll prädikativ sein. Wenn wir andererseits sagen

Napoleon hatte alle Qualitäten eines großen Generals

wir beziehen uns auf eine Gesamtheit von Qualitäten. Die Eigenschaft, „alle Qualitäten eines großen Generals zu haben“, soll einprägsam sein.

Ein anderes Beispiel, das ebenfalls von Russell stammt, zeigt, wie improvisatorische Eigenschaften möglicherweise zu Problemen führen können, die an das Lügnerparadoxon erinnern. Angenommen, wir schlagen die Definition vor

Ein typischer Engländer ist einer, der alle Eigenschaften besitzt, die eine Mehrheit der Engländer besitzt.

Es ist klar, dass die meisten Engländer nicht alle Eigenschaften besitzen, die die meisten Engländer besitzen. Daher sollte ein typischer Engländer nach dieser Definition untypisch sein. Laut Russell besteht das Problem darin, dass das Wort „typisch“durch einen Verweis auf alle Eigenschaften definiert und als eine Eigenschaft behandelt wurde. (Es ist bemerkenswert, dass ähnliche Probleme bei der Definition des Begriffs der Zufallszahlen auftreten, vgl. Martin-Löf „Anmerkungen zur konstruktiven Mathematik“(1970).) Russell führte die verzweigte Hierarchie ein, um die offensichtliche Zirkularität solcher improvisierten Definitionen zu behandeln. Man sollte zwischen Eigenschaften erster Ordnung wie Korsisch unterscheiden, die sich nicht auf die Gesamtheit der Eigenschaften beziehen, und berücksichtigen, dass sich die Eigenschaften zweiter Ordnung nur auf die Gesamtheit der Eigenschaften erster Ordnung beziehen. Man kann dann Eigenschaften dritter Ordnung einführen, die sich auf die Gesamtheit der Eigenschaften zweiter Ordnung beziehen können, und so weiter. Dies beseitigt eindeutig alle Zirkularitäten, die mit improvisierten Definitionen verbunden sind.

Etwa zur gleichen Zeit führte Poincaré eine ähnliche Analyse durch. Er betonte, wie wichtig es sei, „prädikative“Klassifikationen zu verwenden und Elemente einer Klasse nicht anhand einer Quantifizierung über diese Klasse zu definieren (Poincaré 1909). Poincaré verwendete das folgende Beispiel. Angenommen, wir haben eine Sammlung mit den Elementen 0, 1 und einer Operation + befriedigend

) begin {align} x + 0 & = 0 \\ x + (y + 1) & = (x + y) +1 / end {align})

Nehmen wir an, eine Eigenschaft ist induktiv, wenn sie für 0 gilt, und für (x + 1), wenn sie für (x) gilt.

Eine einfache und möglicherweise „gefährliche“Definition wäre, ein Element als Zahl zu definieren, wenn es alle induktiven Eigenschaften erfüllt. Es ist dann leicht zu zeigen, dass diese Eigenschaft „eine Zahl sein“selbst induktiv ist. In der Tat ist 0 eine Zahl, da sie alle induktiven Eigenschaften erfüllt, und wenn (x) alle induktiven Eigenschaften erfüllt, dann auch (x + 1). Ebenso ist es leicht zu zeigen, dass (x + y) eine Zahl ist, wenn (x, y) Zahlen sind. In der Tat ist die Eigenschaft (Q (z)), dass (x + z) eine Zahl ist, induktiv: (Q) (0) gilt seit (x + 0 = x) und wenn (x + z) ist eine Zahl, dann ist (x + (z + 1) = (x + z) +1). Dieses ganze Argument ist jedoch zirkulär, da die Eigenschaft „eine Zahl sein“nicht aussagekräftig ist und mit Argwohn behandelt werden sollte.

Stattdessen sollte eine verzweigte Hierarchie von Eigenschaften und Zahlen eingeführt werden. Zu Beginn hat man nur induktive Eigenschaften erster Ordnung, die sich in ihren Definitionen nicht auf eine Gesamtheit von Eigenschaften beziehen, und man definiert die Zahlen der Ordnung 1 als die Elemente, die alle induktiven Eigenschaften erster Ordnung erfüllen. Als nächstes kann man die induktiven Eigenschaften zweiter Ordnung betrachten, die sich auf die Sammlung von Eigenschaften erster Ordnung beziehen können, und die Zahlen der Ordnung 2, die die Elemente sind, die die induktiven Eigenschaften der Ordnung 2 erfüllen. Man kann dann in ähnlicher Weise die Zahlen der Ordnung betrachten 3 und so weiter. Poincaré betont die Tatsache, dass eine Anzahl von Ordnungen 2 erst recht eine Anzahl von Ordnungen 1 ist und allgemeiner eine Anzahl von Ordnungen (n + 1) erst recht eine Anzahl von Ordnungen (n) ist. Wir haben also eine Folge von immer eingeschränkteren Eigenschaften:induktive Eigenschaften der Ordnung 1, 2,… und eine Folge von immer eingeschränkteren Sammlungen von Objekten: Nummern der Ordnung 1, 2,… Auch die Eigenschaft „eine Zahl der Ordnung (n) sein“ist selbst induktiv Eigenschaft der Ordnung (n + 1).

Es scheint nicht möglich zu sein, zu beweisen, dass (x + y) eine Ordnungszahl (n) ist, wenn (x, y) Ordnungszahlen (n) sind. Andererseits kann gezeigt werden, dass wenn (x) eine Anzahl von Ordnungen (n + 1) und (y) eine Anzahl von Ordnungen (n + 1) ist, dann (x + y) ist eine Anzahl von Ordnungen (n). In der Tat ist die Eigenschaft (P (z)), dass "(x + z) eine Anzahl von Ordnungen (n)" ist, eine induktive Eigenschaft von Ordnung (n + 1: P) (0) gilt, da (x + 0 = x) eine Anzahl von Ordnungen (n + 1) und damit von Ordnungen (n) ist, und wenn (P (z)) gilt, dh wenn (x + z) ist eine Anzahl von Ordnungen (n), dann ist (x + (z + 1) = (x + z) +1) und so (P (z + 1)) hält. Da (y) eine Anzahl von Ordnungen (n + 1) ist und (P (z)) eine induktive Eigenschaft der Ordnung ist, gilt (n + 1, P (y)) und so (x + y) ist eine Anzahl von Ordnungen (n). Dieses Beispiel veranschaulicht gut die Komplexität, die durch die verzweigte Hierarchie eingeführt wird.

Die Komplexität wird weiter verstärkt, wenn man wie Russell wie Frege selbst grundlegende Objekte wie natürliche Zahlen als Klassen von Klassen definiert. Zum Beispiel ist die Zahl 2 definiert als die Klasse aller Klassen von Individuen mit genau zwei Elementen. Wir erhalten wieder natürliche Zahlen verschiedener Ordnungen in der verzweigten Hierarchie. Neben Russell selbst und trotz all dieser Komplikationen versuchte Chwistek, die Arithmetik auf verzweigte Weise zu entwickeln, und das Interesse einer solchen Analyse wurde von Skolem betont. Siehe Burgess und Hazen 1998 für eine aktuelle Entwicklung.

Ein anderes mathematisches Beispiel für eine oft definierte Definition ist die Definition der kleinsten Obergrenze einer begrenzten Klasse von reellen Zahlen. Wenn wir ein Real mit der Menge von Rationalen identifizieren, die kleiner als dieses Real sind, sehen wir, dass diese kleinste Obergrenze als die Vereinigung aller Elemente in dieser Klasse definiert werden kann. Lassen Sie uns Teilmengen der Rationalen als Prädikate identifizieren. Zum Beispiel gilt für rationale Zahlen (q, P (q)), wenn (q) ein Mitglied der als (P) identifizierten Teilmenge ist. Nun definieren wir das Prädikat (L_C) (eine Teilmenge der Rationalen) als die kleinste Obergrenze der Klasse (C) als:

) forall q [L_C (q) leftrightarrow / existiert P [C (P) Keil P (q)])

Das ist beeindruckend: Wir haben ein Prädikat (L) durch eine existenzielle Quantifizierung über alle Prädikate definiert. Wenn in der verzweigten Hierarchie (C) eine Klasse von Rationalklassen erster Ordnung ist, ist (L) eine Klasse von Rationalen zweiter Ordnung. Man erhält dann nicht einen Begriff oder reelle Zahlen, sondern reelle Zahlen verschiedener Ordnungen 1, 2, … Die kleinste Obergrenze einer Sammlung von Reellen der Ordnung 1 wird dann im Allgemeinen mindestens der Ordnung 2 entsprechen.

Wie wir bereits gesehen haben, ist Leibniz 'Definition der Gleichheit ein weiteres Beispiel für eine improvisatorische Definition. Für Leibniz gilt das Prädikat "ist gleich (a)" für (b), wenn (b) alle durch (a) erfüllten Prädikate erfüllt.

Wie soll man mit den Komplikationen umgehen, die durch die verzweigte Hierarchie entstehen? Russell hat in der Einleitung zur zweiten Ausgabe von Principia Mathematica gezeigt, dass diese Komplikationen in einigen Fällen vermieden werden können. In Anhang B der zweiten Ausgabe von Principia Mathematica glaubte er sogar, dass die verzweigte Hierarchie der natürlichen Zahlen der Ordnung 1,2,… bei Ordnung 5 zusammenbricht. Gödel fand jedoch später ein Problem in seiner Argumentation, und tatsächlich war es das auch Myhill 1974 hat gezeigt, dass diese Hierarchie auf keiner endlichen Ebene zusammenbricht. Ein ähnliches Problem,Die von Russell in der Einleitung zur zweiten Ausgabe von Principia Mathematica diskutierte Aussage ergibt sich aus dem Beweis des Cantor-Theorems, dass es keine injektiven Funktionen von der Sammlung aller Prädikate bis zur Sammlung aller Objekte geben kann (die Version von Russells Paradoxon in Freges System, die wir haben in der Einleitung vorgestellt). Kann dies in einer verzweigten Hierarchie erfolgen? Russell bezweifelte, dass dies innerhalb einer verzweigten Hierarchie von Prädikaten geschehen könnte, und dies wurde tatsächlich später bestätigt (Heck 1996).

Aufgrund dieser Probleme haben Russell und Whitehead in der ersten Ausgabe von Principia Mathematica das folgende Reduzierbarkeitsaxiom eingeführt: Die Hierarchie der Prädikate erster Ordnung, zweiter Ordnung usw. kollabiert auf Ebene 1. Dies bedeutet, dass für jedes Prädikat eines beliebigen Prädikats Ordnung gibt es ein Prädikat der Ebene erster Ordnung, das dieser entspricht. Im Fall der Gleichheit postulieren wir beispielsweise eine Beziehung erster Ordnung "(a = b)", die äquivalent zu "(a) erfüllt alle Eigenschaften, die (b) erfüllt". Die Motivation für dieses Axiom war rein pragmatisch. Ohne sie werden alle mathematischen Grundbegriffe wie reelle oder natürliche Zahlen in verschiedene Ordnungen geschichtet. Auch scheint das Axiom der Reduzierbarkeit trotz der offensichtlichen Zirkularität der improvisatorischen Definitionen nicht zu Inkonsistenzen zu führen.

Wie jedoch zuerst von Chwistek und später von Ramsey bemerkt wurde, macht es angesichts des Axioms der Reduzierbarkeit eigentlich keinen Sinn, die verzweigte Hierarchie überhaupt einzuführen! Es ist viel einfacher, von Anfang an einprägsame Definitionen zu akzeptieren. Die einfache „Erweiterungshierarchie“von Individuen, Klassen, Klassen von Klassen… ist dann genug. Auf diese Weise erhalten wir die einfacheren Systeme, die in Gödel 1931 oder Church 1940 formalisiert wurden und oben vorgestellt wurden.

Das Axiom der Reduzierbarkeit macht auf den problematischen Status von Impredikativdefinitionen aufmerksam. Um Weyl 1946 zu zitieren, ist das Axiom der Reduzierbarkeit „ein kühnes, fast fantastisches Axiom; In der realen Welt, in der wir leben, gibt es wenig Rechtfertigung dafür und überhaupt keine in den Beweisen, auf denen unser Geist seine Konstruktionen basiert. “Bisher wurden mit dem Reduzierbarkeitsaxiom keine Widersprüche gefunden. Wie wir weiter unten sehen werden, bestätigen beweistheoretische Untersuchungen jedoch die extreme Stärke eines solchen Prinzips.

Die Idee der verzweigten Hierarchie war in der mathematischen Logik äußerst wichtig. Russell betrachtete nur die endliche Iteration der Hierarchie: erste Ordnung, zweite Ordnung usw., aber von Anfang an wurde die Möglichkeit in Betracht gezogen, die Verzweigung auf unbestimmte Zeit zu erweitern. Poincaré (1909) erwähnt die Arbeit von Koenig in dieser Richtung. Für das obige Beispiel von Zahlen unterschiedlicher Ordnung definiert er auch eine Zahl als induktiv für die Ordnung (omega), wenn sie für alle endlichen Ordnungen induktiv ist. Er weist dann darauf hin, dass x + y die Ordnung (omega) induziert, wenn sowohl (x) als auch (y) sind. Dies zeigt, dass die Einführung transfiniter Ordnungen in einigen Fällen die Rolle des Axioms der Reduzierbarkeit spielen kann. Eine solche transfinite Erweiterung der verzweigten Hierarchie wurde von Gödel weiter analysiert, der die entscheidende Tatsache bemerkte, dass die folgende Form des Reduzierbarkeitsaxioms tatsächlich beweisbar ist: Wenn man die verzweigte Hierarchie von Eigenschaften über die natürlichen Zahlen in das Transfinite erweitert, kollabiert diese Hierarchie auf Ebene (omega_1), die am wenigsten unzählige Ordnungszahl (Gödel 1995 und Prawitz 1970). Während auf allen Ebenen (lt / omega_1) die Sammlung von Prädikaten zählbar ist, ist die Sammlung von Prädikaten auf Ebene (omega_1) von Kardinalität (omega_1). Diese Tatsache war eine starke Motivation für Gödels Modell konstruierbarer Mengen. In diesem Modell hat die Sammlung aller Teilmengen der Menge natürlicher Zahlen (dargestellt durch Prädikate) die Kardinalität (omega_1) und ähnelt der verzweigten Hierarchie. Dieses Modell erfüllt auf diese Weise die Kontinuumshypothese und liefert einen relativen Konsistenzbeweis für dieses Axiom. (Die Motivation von Gödel bestand ursprünglich nur darin, ein Modell zu erstellen, bei dem die Sammlung aller Teilmengen natürlicher Zahlen gut geordnet ist.)

Die verzweigte Hierarchie war auch die Quelle vieler Arbeiten in der Beweistheorie. Nach der Entdeckung von Gentzen, dass die Konsistenz der Arithmetik durch transfinite Induktion (über entscheidbare Prädikate) entlang der Ordnungszahl ((varepsilon_0) bewiesen werden konnte, bestand die natürliche Frage darin, die entsprechende Ordnungszahl für die verschiedenen Ebenen der verzweigten Hierarchie zu finden. Schütte (1960) fand heraus, dass für die erste Ebene der verzweigten Hierarchie, dh wenn wir die Arithmetik nur durch Quantifizierung über Eigenschaften erster Ordnung erweitern, ein System der Ordnungsstärke (varepsilon _ { varepsilon_0}) erhalten. Für die zweite Ebene erhalten wir die Ordnungsstärke (varepsilon _ { varepsilon_ { varepsilon_0}}) usw. Wir erinnern uns, dass (varepsilon _ { alpha}) das (alpha) - th / bezeichnet (varepsilon) - Ordnungszahl,eine (varepsilon) - Ordnungszahl ist eine Ordnungszahl (beta), so dass (omega ^ { beta} = / beta), siehe Schütte (1960).

Gödel betonte die Tatsache, dass seine Herangehensweise an das Problem der Kontinuumshypothese nicht konstruktiv war, da es die unzähligen Ordnungszahlen (omega_1) benötigt, und es natürlich war, die verzweigte Hierarchie entlang konstruktiver Ordnungszahlen zu untersuchen. Nach Vorarbeiten von Lorenzen und Wang analysierte Schütte, was passiert, wenn wir konstruktiver vorgehen. Da die Arithmetik für die Ordnungsstärke (varepsilon_0) gilt, betrachten wir zunächst die Iteration der verzweigten Hierarchie bis (varepsilon_0). Schütte berechnete die Ordnungsstärke des resultierenden Systems und fand eine Ordnungsstärke (u (1) gt / varepsilon_0). Wir iterieren dann die verzweigte Hierarchie bis zu dieser Ordnungszahl (u (1)) und erhalten ein System der Ordnungsstärke (u (2) gt u (1)) usw. Jedes (u (k)) kann anhand der sogenannten Veblen-Hierarchie berechnet werden:(u (k + 1)) ist (phi_ {u (k)} (0)). Die Grenze dieses Prozesses ergibt eine Ordnungszahl namens (Gamma_0): Wenn wir die verzweigte Hierarchie bis zur Ordnungszahl (Gamma_0) durchlaufen, erhalten wir ein System der Ordnungsstärke (Gamma_0). Eine solche Ordnungszahl wurde ungefähr zur gleichen Zeit von S. Feferman unabhängig erhalten. Es wurde behauptet, dass (Gamma_0) für prädikative Systeme eine ähnliche Rolle spielt wie (varepsilon_0) für Arithmetik. Neuere beweistheoretische Arbeiten befassen sich jedoch mit Systemen mit größeren beweistheoretischen Ordnungszahlen, die als prädikativ angesehen werden können (siehe zum Beispiel Palmgren 1995). Es wurde behauptet, dass (Gamma_0) für prädikative Systeme eine ähnliche Rolle spielt wie (varepsilon_0) für Arithmetik. Neuere beweistheoretische Arbeiten befassen sich jedoch mit Systemen mit größeren beweistheoretischen Ordnungszahlen, die als prädikativ angesehen werden können (siehe zum Beispiel Palmgren 1995). Es wurde behauptet, dass (Gamma_0) für prädikative Systeme eine ähnliche Rolle spielt wie (varepsilon_0) für Arithmetik. Neuere beweistheoretische Arbeiten befassen sich jedoch mit Systemen mit größeren beweistheoretischen Ordnungszahlen, die als prädikativ angesehen werden können (siehe zum Beispiel Palmgren 1995).

Neben diesen beweistheoretischen Untersuchungen im Zusammenhang mit der verzweigten Hierarchie wurde in der Beweistheorie viel Arbeit darauf verwendet, die Konsistenz des Axioms der Reduzierbarkeit oder gleichwertig die Konsistenz von Impredikativdefinitionen zu analysieren. Nach Gentzens Analyse der Cut-Elimination-Eigenschaft in der Sequenzrechnung fand Takeuti eine elegante Sequenzformulierung der einfachen Typentheorie (ohne Verzweigung) und machte die kühne Vermutung, dass die Cut-Elimination für dieses System gelten sollte. Diese Vermutung schien angesichts der Zirkularität der improvisierten Quantifizierung, die sich in diesem Formalismus gut widerspiegelt, zunächst äußerst zweifelhaft. Die Regel für Quantifizierungen ist in der Tat

) frac { Gamma / vdash / forall X [A (X)]} { Gamma / vdash A [X: = T]})

Dabei ist (T) ein beliebiges Begriffsprädikat, das selbst eine Quantifizierung über alle Prädikate beinhalten kann. Somit kann die Formel (A [X: = T]) selbst viel komplexer sein als die Formel (A (X)).

Ein frühes Ergebnis ist, dass die Cut-Eliminierung für Takeutis Impredikativsystem in endlicher Weise die Konsistenz der Arithmetik zweiter Ordnung impliziert. (Man zeigt, dass dies die Konsistenz einer geeigneten Form des Unendlichkeitsaxioms impliziert, siehe Andrews 2002.) Nach Arbeiten von Schütte wurde später von W. Tait und D. Prawitz gezeigt, dass tatsächlich die Cut-Elimination-Eigenschaft gilt (der Beweis von Dies muss ein stärkeres beweistheoretisches Prinzip verwenden, wie es nach dem Unvollständigkeitssatz sein sollte.)

Wichtig ist hierbei, dass diese Studien die extreme Kraft der impedikativen Quantifizierung oder gleichwertig die extreme Kraft des Axioms der Reduzierbarkeit gezeigt haben. Dies bestätigt in gewisser Weise die Intuitionen von Poincaré und Russell. Die beweistheoretische Stärke der Arithmetik zweiter Ordnung ist vor allem die von Schütte berücksichtigte verzweigte Erweiterung der Arithmetik. Andererseits wurden trotz der Zirkularität der improvisierten Definitionen, die in Takeutis Kalkül so deutlich gemacht wird, noch keine Paradoxien in der Arithmetik zweiter Ordnung gefunden.

Eine andere Forschungsrichtung in der Beweistheorie bestand darin, zu verstehen, wie viel der improvisierten Quantifizierung aus Prinzipien erklärt werden kann, die in der intuitionistischen Mathematik verfügbar sind. Die stärksten dieser Prinzipien sind starke Formen induktiver Definitionen. Mit solchen Prinzipien kann man eine begrenzte Form einer improvisierten Quantifizierung erklären, die als (Pi_ {1} ^ 1) - Verständnis bezeichnet wird und bei der nur eine Ebene der improvisierten Quantifizierung gegenüber Prädikaten verwendet wird. Interessanterweise können fast alle bekannten Verwendungen von Impredikativquantifizierungen: Leibniz-Gleichheit, kleinste Obergrenze usw. mit (Pi_ {1} ^ 1) - Verständnis durchgeführt werden. Diese Reduktion des (Pi_ {1} ^ 1) - Verständnisses wurde zuerst von Takeuti auf ganz indirekte Weise erreicht und später von Buchholz und Schütte unter Verwendung der sogenannten (Omega) - Regel vereinfacht. Es kann als konstruktive Erklärung einiger eingeschränkter, aber nicht trivialer Verwendungen von Impredikativdefinitionen angesehen werden.

4. Typentheorie / Mengenlehre

Die Typentheorie kann als Grundlage für die Mathematik verwendet werden, und tatsächlich wurde sie von Russell in seiner Arbeit von 1908 vorgestellt, die im selben Jahr wie Zermelos Arbeit erschien und die Mengenlehre als Grundlage für die Mathematik vorstellte.

Es ist intuitiv klar, wie wir die Typentheorie in der Mengenlehre erklären können: Ein Typ wird einfach als Menge interpretiert, und Funktionstypen (A / rightarrow B) können unter Verwendung des satztheoretischen Funktionsbegriffs (als funktionale Beziehung) erklärt werden. dh eine Reihe von Elementpaaren). Der Typ (A / rightarrow o) entspricht der Powerset-Operation.

Die andere Richtung ist interessanter. Wie können wir den Begriff der Mengen in Form von Typen erklären? Mit A. Miquel gibt es eine elegante Lösung, die frühere Arbeiten von P. Aczel (1978) ergänzt und auch den Vorteil hat, nicht unbedingt fundierte Mengen a la Finsler zu erklären. Man interpretiert eine Menge einfach als spitzes Diagramm (wobei der Pfeil im Diagramm die Zugehörigkeitsbeziehung darstellt). Dies wird in der Typentheorie sehr bequem dargestellt, wobei ein spitzer Graph einfach durch einen Typ A und ein Elementpaar gegeben ist

[a: A, R: A / rightarrow A / rightarrow o)

Wir können dann in der Typentheorie definieren, wann zwei solcher Mengen (A, a, R) und (B, b, S) gleich sind: Dies ist der Fall, wenn es eine Bisimulation (T) zwischen (A) und (B) so, dass (Tab) gilt. Eine Bisimulation ist eine Beziehung

[T: A / rightarrow B / rightarrow o)

so dass, wann immer (Txy) und (Rxu) halten, es (v) gibt, so dass (Tuv) und (Syv) halten, und wann immer (Txy) und (Ryv) halten, es existiert (u) so, dass (Tuv) und (Rxu) halten. Wir können dann die Zugehörigkeitsbeziehung definieren: Die dargestellte Menge (B, b, S) ist ein Mitglied der durch (A, a, R) dargestellten Menge, wenn es (a_1) gibt, so dass (Ra_1a) und (A, a_1, R) und (B, b, S) sind bisimilar.

Es kann dann überprüft werden, dass alle üblichen Axiome der Mengenerweiterung, der Potenzmenge, der Vereinigung, des Verständnisses über begrenzte Formeln (und sogar der Antifundierung, so dass die Zugehörigkeitsbeziehung nicht begründet sein muss) in diesem einfachen Modell gelten. (Eine begrenzte Formel ist eine Formel, bei der alle Quantifizierungen die Form (forall x / in a / ldots) oder (existiert x / in a / ldots) haben.) Auf diese Weise kann gezeigt werden, dass die einfache Typentheorie der Kirche mit der begrenzten Version von Zermelos Mengenlehre übereinstimmt.

5. Typentheorie / Kategorietheorie

Es gibt tiefe Verbindungen zwischen Typentheorie und Kategorietheorie. Wir beschränken uns darauf, zwei Anwendungen der Typentheorie auf die Kategorietheorie vorzustellen: die Konstruktionen der freien kartesischen geschlossenen Kategorie und der freien Topos (eine Erklärung der „kartesischen geschlossenen“und „Topos“finden Sie im Eintrag zur Kategorietheorie).

Für die Erstellung der freien kartesischen geschlossenen Kategorie erweitern wir die einfache Typentheorie um den Typ 1 (Einheitentyp) und den Produkttyp (A / mal B) für (A, B) Typen. Die Begriffe werden durch Hinzufügen von Paarungsoperationen und Projektionen sowie eines speziellen Elements vom Typ 1 erweitert. Wie bei Lambek und Scott 1986 kann man dann einen Begriff für typisierte Konvertierungen zwischen Begriffen definieren und zeigen, dass diese Beziehung entscheidbar ist. Man kann dann zeigen (Lambek und Scott 1986), dass die Kategorie mit Typen als Objekte und als Morphismen von (A) bis (B) die Menge der geschlossenen Terme vom Typ (A / rightarrow B) (mit Konvertierung) enthält als Gleichheit) ist die freie kartesische geschlossene Kategorie. Dies kann verwendet werden, um zu zeigen, dass die Gleichheit zwischen Pfeilen in dieser Kategorie entscheidbar ist.

Die Theorie der Kirchentypen kann auch verwendet werden, um die freien Topos zu bauen. Dazu nehmen wir als Objekte Paare (A, E) mit (A) Typ und (E) eine partielle Äquivalenzbeziehung, dh einen geschlossenen Term (E: A / rightarrow A / rightarrow o) Das ist symmetrisch und transitiv. Wir nehmen als Morphismen zwischen (A, E) und (B, F) die Beziehungen (R: A / rechtspfeil B / rechtspfeil o), die funktional sind und für jedes (a: A) so sind) befriedigend (E aa) gibt es ein und nur ein (modulo (F)) Element (b) von (B), so dass (F bb) und (R ab). Für den Unterobjektklassifikator nehmen wir das Paar (o, E) mit (E: o / rightarrow o / rightarrow o) definiert als

[EMN = / text {und} (implizieren \, MN) (implizieren \, NM))

Man kann dann zeigen, dass diese Kategorie einen Topos bildet, in der Tat den freien Topos.

Es ist anzumerken, dass die Typentheorie in Lambek und Scott 1986 eine Variation der Typentheorie verwendet, die von Henkin eingeführt und von P. Andrews (2002) verfeinert wurde und eine Extensionsgleichheit als einzige logische Verbindung haben soll, dh eine polymorphe Konstante

) text {eq}: A / rightarrow A / rightarrow o)

und alle logischen Verbindungen aus dieser Verbindung und den Konstanten (T, F: o) zu definieren. Zum Beispiel definiert man

) forall P = _ {df} text {eq} (lambda xT) P)

Die Gleichheit beim Typ (o) ist logische Äquivalenz.

Ein Vorteil der Intensionsformulierung besteht darin, dass sie eine direkte Notation von Beweisen ermöglicht, die auf (lambda) - Kalkül basieren (Martin-Löf 1971 und Coquand 1986).

6. Erweiterungen des Typensystems, Polymorphismus, Paradoxe

Wir haben die Analogie zwischen der Operation A (rightarrow) A (rightarrow) o bei Typen und der Powerset-Operation bei Sets gesehen. In der Mengenlehre kann die Powerset-Operation entlang der kumulativen Hierarchie unbegrenzt iteriert werden. Es ist dann natürlich, nach analogen transfiniten Versionen der Typentheorie zu suchen.

Eine solche Erweiterung der einfachen Typentheorie der Kirche wird durch Hinzufügen von Universen erhalten (Martin-Löf 1970). Das Hinzufügen eines Universums ist ein Reflexionsprozess: Wir fügen einen Typ (U) hinzu, dessen Objekte die bisher betrachteten Typen sind. Für die einfache Typentheorie der Kirche werden wir haben

[o: U, i: U / text {und} A / rightarrow B: U / text {if} A: U, B: U)

und außerdem ist (A) ein Typ, wenn (A: U). Wir können dann Typen wie betrachten

[(A: U) rightarrow A / rightarrow A)

und Funktionen wie

) text {id} = / lambda A. / lambda xx: (A: U) rightarrow A / rightarrow A)

Die Funktions-ID verwendet als Argument einen "kleinen" Typ (A: U) und ein Element (x) vom Typ (A) und gibt ein Element vom Typ (A) aus. Allgemeiner kann man den abhängigen Typ bilden, wenn (T (A)) ein Typ unter der Annahme (A: U) ist

[(A: U) rechter Pfeil T (A))

Dass (M) von diesem Typ ist, bedeutet, dass (MA: T (A)) wann immer (A: U). Auf diese Weise erhalten wir Erweiterungen der Typentheorie, deren Stärke der von Zermelos Mengenlehre ähnlich ist (Miquel 2001). Eine mächtigere Form von Universen wird in (Palmgren 1998) betrachtet. Miquel (2003) präsentiert eine Version der Typentheorie der Festigkeit, die der von Zermelo-Fraenkel entspricht.

Eine sehr starke Form des Universums wird durch Hinzufügen des Axioms (U: U) erhalten. Dies wurde 1970 von P. Martin-Löf vorgeschlagen. JY Girard zeigte, dass die resultierende Typentheorie als logisches System inkonsistent ist (Girard 1972). Obwohl es zunächst so aussieht, als könnte man Russells Paradoxon unter Verwendung einer Menge aller Mengen direkt reproduzieren, ist ein solches direktes Paradox aufgrund des Unterschieds zwischen Mengen und Typen tatsächlich nicht möglich. In der Tat ist die Ableitung eines Widerspruchs in einem solchen System subtil und eher indirekt (obwohl sie, wie in Miquel 2001 bemerkt, jetzt auf Russells Paradox reduziert werden kann, indem Mengen als spitze Graphen dargestellt werden). JY Girard erhielt zuerst sein Paradoxon für ein schwächeres System. Dieses Paradoxon wurde später verfeinert (Coquand 1994 und Hurkens 1995). (Der Begriff des reinen Typsystems, eingeführt in Barendregt 1992,ist praktisch, um eine scharfe Formulierung dieser Paradoxien zu erhalten.) Anstelle des Axioms (U: U) wird nur angenommen

[(A: U) rechter Pfeil T (A): U)

if (T (A): U [A: U]). Beachten Sie die Zirkularität, die tatsächlich von der gleichen Art ist wie die, die von der verzweigten Hierarchie abgelehnt wird: Wir definieren ein Element vom Typ (U), indem wir über alle Elemente von (U) quantifizieren. Zum Beispiel der Typ

[(A: U) rightarrow A / rightarrow A: U)

wird der Typ der polymorphen Identitätsfunktion sein. Trotz dieser Zirkularität konnte JY Girard eine Normalisierung für Typsysteme mit dieser Form des Polymorphismus zeigen. Die Erweiterung der einfachen Typentheorie der Kirche um den Polymorphismus ist jedoch als logisches System inkonsistent, dh alle Sätze (Begriffe des Typs o) sind beweisbar.

JY Girards Motivation, ein Typsystem mit Polymorphismus in Betracht zu ziehen, bestand darin, Gödels Dialectica-Interpretation (Gödel 1958) auf Arithmetik zweiter Ordnung auszudehnen. Er bewies die Normalisierung mit der Reduzierbarkeitsmethode, die Tait (1967) bei der Analyse von Gödel 1958 eingeführt hatte. Es ist bemerkenswert, dass die der Impredikativität innewohnende Zirkularität nicht zu nicht normalisierbaren Begriffen führt. (Girards Argument wurde dann verwendet, um zu zeigen, dass die Eliminierung von Schnitten in Takeutis oben dargestelltem Sequenzkalkül endet.) Ein ähnliches System wurde unabhängig von J. Reynolds (1974) eingeführt, während der Begriff des Polymorphismus in der Informatik analysiert wurde.

Martin-Löfs Einführung eines Typs aller Typen beruht auf der Identifizierung des Konzepts von Sätzen und Typen, das von Curry und Howard vorgeschlagen wurde. An dieser Stelle sei an seine drei Motivationspunkte erinnert:

  1. Russells Definition von Typen als Bedeutungsbereiche von Satzfunktionen
  2. die Tatsache, dass man über alle Sätze quantifizieren muss (Impredikativität der einfachen Typentheorie)
  3. Identifizierung von Aussagen und Typen

Unter (1) und (2) sollten wir eine Art von Sätzen haben (wie in der einfachen Typentheorie), und unter (3) sollte dies auch die Art aller Arten sein. Girards Paradoxon zeigt, dass man nicht gleichzeitig (1), (2) und (3) haben kann. Martin-Löfs Wahl war es, (2) wegzunehmen und die Typentheorie auf Prädikative zu beschränken (und tatsächlich erschien der Begriff des Universums zuerst in der Typentheorie als prädikative Version des Typs aller Typen). Die alternative Wahl des Mitnehmens (3) wird in Coquand 1986 diskutiert.

7. Einwertige Grundlagen

Die Verbindungen zwischen Typentheorie, Mengenlehre und Kategorietheorie erhalten durch die Arbeit an univalenten Grundlagen (Voevodsky 2015) und dem Axiom der Univalenz ein neues Licht. Dies beinhaltet im Wesentlichen die Erweiterung der im vorherigen Abschnitt beschriebenen Typentheorie, insbesondere abhängige Typen, die Sicht auf Sätze als Typen und den Begriff des Universums der Typen. Diese Entwicklungen sind auch relevant für die Erörterung des Strukturbegriffs, dessen Bedeutung beispielsweise in Russell 1959 hervorgehoben wurde.

Martin-Löf 1975 [1973] führte einen neuen Grundtyp (mathbf {Id} _A (a, b)) ein, wenn (a) und (b) vom Typ (A) sind, Dies kann als die Art der Gleichheitsnachweise des Elements (a) und (b) angesehen werden. Ein wichtiges Merkmal dieses neuen Typs ist, dass er iteriert werden kann, so dass wir den Typ (mathbf {Id} _ { mathbf {Id} _A (a, b)} (p, q)) if berücksichtigen können (p) und (q) sind vom Typ (mathbf {Id} _A (a, b)). Wenn wir uns einen Typ als eine besondere Art von Menge vorstellen, ist es natürlich anzunehmen, dass ein solcher Typ von Gleichheitsbeweisen immer für zwei beliebige Gleichheitsbeweise (p) und (q) bewohnt ist. In der Tat scheint es intuitiv höchstens einen Gleichheitsnachweis zwischen zwei Elementen (a) und (b) zu geben. Überraschenderweise haben Hofmann und Streicher 1996 ein Modell der abhängigen Typentheorie entworfen, bei dem dies nicht gültig ist. Das ist ein Modell, bei dem es sich um unterschiedliche Beweise dafür handeln kann, dass zwei Elemente gleich sind. In diesem Modell wird ein Typ von einem Groupoid und der Typ (mathbf {Id} _A (a, b)) durch die Menge von Isomorphismen zwischen (a) und (b) interpretiert, die möglicherweise gesetzt werden mehr als ein Element haben. Die Existenz dieses Modells hat zur Folge, dass in der Typentheorie nicht allgemein nachgewiesen werden kann, dass ein Gleichheitstyp höchstens ein Element aufweist. Diese gruppenförmige Interpretation wurde folgendermaßen verallgemeinert, was eine intuitive Interpretation des Identitätstyps ermöglicht. Ein Typ wird durch einen topologischen Raum bis zur Homotopie interpretiert, und ein Typ (mathbf {Id} _A (a, b)) wird durch die Art der Pfade interpretiert, die (a) und (b) verbinden.. (Siehe Awodey et al. 2013 und [HoTT 2013, Other Internet Resources].)Ein Typ wird von einem Groupoid und der Typ (mathbf {Id} _A (a, b)) durch die Menge von Isomorphismen zwischen (a) und (b) interpretiert, die mehr als eine haben können Element. Die Existenz dieses Modells hat zur Folge, dass in der Typentheorie nicht allgemein nachgewiesen werden kann, dass ein Gleichheitstyp höchstens ein Element aufweist. Diese gruppenförmige Interpretation wurde folgendermaßen verallgemeinert, was eine intuitive Interpretation des Identitätstyps ermöglicht. Ein Typ wird durch einen topologischen Raum bis zur Homotopie interpretiert, und ein Typ (mathbf {Id} _A (a, b)) wird durch die Art der Pfade interpretiert, die (a) und (b) verbinden.. (Siehe Awodey et al. 2013 und [HoTT 2013, Other Internet Resources].)Ein Typ wird von einem Groupoid und der Typ (mathbf {Id} _A (a, b)) durch die Menge von Isomorphismen zwischen (a) und (b) interpretiert, die mehr als eine haben können Element. Die Existenz dieses Modells hat zur Folge, dass in der Typentheorie nicht allgemein nachgewiesen werden kann, dass ein Gleichheitstyp höchstens ein Element aufweist. Diese gruppenförmige Interpretation wurde folgendermaßen verallgemeinert, was eine intuitive Interpretation des Identitätstyps ermöglicht. Ein Typ wird durch einen topologischen Raum bis zur Homotopie interpretiert, und ein Typ (mathbf {Id} _A (a, b)) wird durch die Art der Pfade interpretiert, die (a) und (b) verbinden.. (Siehe Awodey et al. 2013 und [HoTT 2013, Other Internet Resources].)Die Existenz dieses Modells hat zur Folge, dass in der Typentheorie nicht allgemein nachgewiesen werden kann, dass ein Gleichheitstyp höchstens ein Element aufweist. Diese gruppenförmige Interpretation wurde folgendermaßen verallgemeinert, was eine intuitive Interpretation des Identitätstyps ermöglicht. Ein Typ wird durch einen topologischen Raum bis zur Homotopie interpretiert, und ein Typ (mathbf {Id} _A (a, b)) wird durch die Art der Pfade interpretiert, die (a) und (b) verbinden.. (Siehe Awodey et al. 2013 und [HoTT 2013, Other Internet Resources].)Die Existenz dieses Modells hat zur Folge, dass in der Typentheorie nicht allgemein nachgewiesen werden kann, dass ein Gleichheitstyp höchstens ein Element aufweist. Diese gruppenförmige Interpretation wurde folgendermaßen verallgemeinert, was eine intuitive Interpretation des Identitätstyps ermöglicht. Ein Typ wird durch einen topologischen Raum bis zur Homotopie interpretiert, und ein Typ (mathbf {Id} _A (a, b)) wird durch die Art der Pfade interpretiert, die (a) und (b) verbinden.. (Siehe Awodey et al. 2013 und [HoTT 2013, Other Internet Resources].)b)) wird durch die Art der Pfade interpretiert, die (a) und (b) verbinden. (Siehe Awodey et al. 2013 und [HoTT 2013, Other Internet Resources].)b)) wird durch die Art der Pfade interpretiert, die (a) und (b) verbinden. (Siehe Awodey et al. 2013 und [HoTT 2013, Other Internet Resources].)

Voevodsky 2015 führte die folgende Schichtung von Typen ein. (Diese Schichtung wurde teilweise durch diese Interpretation eines Typs als topologischen Raum motiviert, kann aber ohne Bezugnahme auf diese Interpretation direkt verstanden werden.) Wir sagen, dass ein Typ (A) ein Satz ist, wenn wir (mathbf haben {Id} _A (a, b)) für jedes Element (a) und (b) von (A) (dies bedeutet, dass der Typ (A) höchstens ein Element hat). Wir sagen, dass ein Typ (A) eine Menge ist, wenn der Typ (mathbf {Id} _A (a, b)) ein Satz für jedes Element (a) und (b) von / ist (EIN). Wir sagen, dass ein Typ (A) ein Groupoid ist, wenn der Typ (mathbf {Id} _A (a, b)) eine Menge für jedes Element (a) und (b) von / ist (EIN). Die Rechtfertigung dieser Terminologie ist, dass nur unter Verwendung der Regeln der Typentheorie gezeigt werden kann, dass ein solcher Typ tatsächlich als Groupoid im üblichen kategorialen Sinne angesehen werden kann. Wenn die Objekte die Elemente dieses Typs sind, wird die Menge der Morphismen zwischen (a) und (b) durch die Menge (mathbf {Id} _A (a, b)) dargestellt. Die Komposition ist der Beweis für die Transitivität der Gleichheit, und der Identitätsmorphismus ist der Beweis für die Reflexivität der Gleichheit. Die Tatsache, dass jeder Morphismus eine Umkehrung hat, entspricht der Tatsache, dass Identität eine symmetrische Beziehung ist. Diese Schichtung kann dann erweitert werden und wir können definieren, wann ein Typ ein 2-Gruppenoid, ein 3-Gruppenoid usw. ist. In dieser Ansicht erscheint die Typentheorie als eine weitgehende Verallgemeinerung der Mengenlehre, da eine Menge eine bestimmte Art von Typ ist.und der Identitätsmorphismus ist der Beweis der Reflexivität der Gleichheit. Die Tatsache, dass jeder Morphismus eine Umkehrung hat, entspricht der Tatsache, dass Identität eine symmetrische Beziehung ist. Diese Schichtung kann dann erweitert werden und wir können definieren, wann ein Typ ein 2-Gruppenoid, ein 3-Gruppenoid usw. ist. In dieser Ansicht erscheint die Typentheorie als eine weitgehende Verallgemeinerung der Mengenlehre, da eine Menge eine bestimmte Art von Typ ist.und der Identitätsmorphismus ist der Beweis der Reflexivität der Gleichheit. Die Tatsache, dass jeder Morphismus eine Umkehrung hat, entspricht der Tatsache, dass Identität eine symmetrische Beziehung ist. Diese Schichtung kann dann erweitert werden und wir können definieren, wann ein Typ ein 2-Gruppenoid, ein 3-Gruppenoid usw. ist. In dieser Ansicht erscheint die Typentheorie als eine weitgehende Verallgemeinerung der Mengenlehre, da eine Menge eine bestimmte Art von Typ ist.

Voevodsky 2015 führt auch einen Begriff der Äquivalenz zwischen Typen ein, der die Begriffe der logischen Äquivalenz zwischen Sätzen, der Bijektion zwischen Mengen, der kategorialen Äquivalenz zwischen Gruppoiden usw. auf einheitliche Weise verallgemeinert. Wir sagen, dass eine Karte (f: A / rechter Pfeil B) eine Äquivalenz ist, wenn für jedes Element (b) in (B) der Paartyp (a, p) wobei (p) ist vom Typ (mathbf {Id} _B (fa, b)), ist ein Satz und wird bewohnt. Dies drückt auf starke Weise aus, dass ein Element in (B) das Bild von genau einem Element in (A) ist, und wenn (A) und (B) Mengen sind, stellen wir den üblichen Begriff wieder her der Bijektion zwischen Sätzen. (Wenn (f: A / rightarrow B) eine Äquivalenz ist, haben wir im Allgemeinen eine Karte (B / rightarrow A), die als Umkehrung von (f) angesehen werden kann.) Es kann zum Beispiel gezeigt werden, dass die Identitätskarte immer eine Äquivalenz ist. Sei (text {Equiv} (A, B)) der Paartyp (f, p), wobei (f: A / rightarrow B) und (p) ein Beweis dafür sind, dass (f) ist eine Äquivalenz. Unter Verwendung der Tatsache, dass die Identitätszuordnung eine Äquivalenz ist, haben wir ein Element von (text {Equiv} (A, A)) für jeden Typ (A). Dies impliziert, dass wir eine Karte haben

) mathbf {Id} _U (A, B) rightarrow / text {Equiv} (A, B))

und das Axiom der Univalenz besagt, dass diese Karte eine Äquivalenz ist. Insbesondere haben wir die Implikation

) text {Equiv} (A, B) rightarrow / mathbf {Id} _U (A, B))

Wenn es also eine Äquivalenz zwischen zwei kleinen Typen gibt, sind diese Typen gleich.

Dieses Axiom kann als starke Form des Extensionalitätsprinzips angesehen werden. Es verallgemeinert in der Tat das von der Kirche 1940 erwähnte Axiom der Satzerweiterung, das besagt, dass zwei logisch äquivalente Sätze gleich sind. Überraschenderweise impliziert es auch das Axiom der Funktionserweiterung, Axiom 10 in Church 1940, das besagt, dass zwei punktweise gleiche Funktionen gleich sind (Voevodsky 2015). Dies impliziert auch direkt, dass zwei isomorphe Mengen gleich sind, dass zwei kategorisch äquivalente Groupoide gleich sind und somit eine.

Dies kann verwendet werden, um eine Formulierung des Begriffs des Transports von Strukturen (Bourbaki 1957) entlang von Äquivalenzen zu geben. Zum Beispiel sei (MA) der Typ der Monoidstrukturen auf der Menge (A): Dies ist der Typ der Tupel (m, e, p), wobei (m) eine binäre Operation ist (A) und (e) ein Element von (A) und (p) ein Beweis dafür, dass diese Elemente die üblichen Monoidgesetze erfüllen. Die Regel der Substitution von gleich durch gleich hat die Form

) mathbf {Id} _U (A, B) rightarrow MA / rightarrow MB)

Wenn es eine Bijektion zwischen (A) und (B) gibt, sind sie nach dem Axiom der Univalenz gleich, und wir können diese Implikation verwenden, um jede Monoidstruktur von (A) in einer Monoidstruktur von (B).

Wir können diesen Rahmen auch verwenden, um die Diskussion von Russell 1959 über den Begriff der Struktur zu verfeinern. Zum Beispiel sei Monoid der Typ von Paaren (A, p), wobei (p) ein Element von (MA) ist. Zwei solche Paare (A, p) und (B, q) sind isomorph, wenn eine Bijektion (f) von (A) nach (B) existiert, so dass (q) ist gleich dem Transport der Struktur von (p) entlang (f). Eine Konsequenz des Axioms der Univalenz ist, dass zwei isomorphe Elemente vom Typ Monoid sindsind gleich und haben daher die gleichen Eigenschaften. Beachten Sie, dass ein solcher allgemeiner Transport von Eigenschaften nicht möglich ist, wenn Strukturen in einem festgelegten theoretischen Rahmen formuliert werden. In einem satztheoretischen Rahmen ist es tatsächlich möglich, Eigenschaften unter Verwendung der Zugehörigkeitsrelationen zu formulieren, beispielsweise die Eigenschaft, dass der Trägersatz der Struktur die natürliche Zahl (0) enthält, eine Eigenschaft, die im Allgemeinen nicht durch Isomorphismen erhalten bleibt. Intuitiv ist die festgelegte theoretische Beschreibung einer Struktur nicht abstrakt genug, da wir darüber sprechen können, wie diese Struktur aufgebaut ist. Dieser Unterschied zwischen Mengen- und Typentheorie ist ein weiteres Beispiel für die Charakterisierung einer Typstruktur durch J. Reynolds 1983 als „syntaktische Disziplin zur Durchsetzung des Abstraktionsniveaus“.

Literaturverzeichnis

  • Aczel, P., 1978, „Die typentheoretische Interpretation der konstruktiven Mengenlehre“, Logic Colloquium '77, Amsterdam: Nordholland, 55–66.
  • Andrews, P., 2002, Eine Einführung in die mathematische Logik und Typentheorie: Wahrheit durch Beweis (Applied Logic Series: Band 27), Dordrecht: Kluwer Academic Publishers, 2. Auflage.
  • Awodey, S., Pelayo, A., Warren, M. 2013, „Das Axiom der Univalenz in der Homotopietypentheorie“, Notices of the American Mathematical Society, 60 (9): 1157–1164.
  • Barendregt, H., 1997, „Der Einfluss des Lambda-Kalküls auf Logik und Informatik“, Bulletin of Symbolic Logic, 3 (2): 181–215.
  • –––, 1992, Lambda-Kalküle mit Typen. Handbuch der Logik in der Informatik, Band 2, Oxford, New York: Oxford University Press, 117–309.
  • Bell, JL, 2012, „Typen, Mengen und Kategorien“, im Akihiro Kanamory-Handbuch zur Geschichte der Logik. Band 6: Sets und Erweiterungen im 20. Jahrhundert, Amsterdam: Nordholland.
  • Bourbaki, N., 1958, Théorie des Ensembles, 3. Auflage, Paris: Hermann.
  • de Bruijn, NG, 1980, „Ein Überblick über das Projekt AUTOMATH“, in To HB Curry: Aufsätze zu kombinatorischer Logik, Lambda-Kalkül und Formalismus, London-New York: Academic Press, 579–606.
  • Burgess JP und Hazen AP, 1998, „Predicative Logic and Formal Arithmetic Source“, Notre Dame J. Formal Logic, 39 (1): 1–17.
  • Buchholz, W. und K. Schütte, 1988, Beweistheorie der impredikativen Teilsysteme der Analyse (Studien zur Beweistheorie: Monographie 2), Neapel: Bibliopolis.
  • Church, A., 1940, „Eine Formulierung der einfachen Typentheorie“, Journal of Symbolic Logic, 5: 56–68
  • –––, 1984, „Russells Theorie der Identität von Sätzen“, Philosophia Naturalis, 21: 513–522
  • Chwistek, L., 1948, Die Grenzen der Wissenschaft: Überblick über die Logik und die Methodik der exakten Wissenschaften, London: Routledge und Kegan Paul.
  • Coquand, T., 1986, „Eine Analyse von Girards Paradoxon“, Proceedings of the IEEE Symposium on Logic in Computer Science, 227–236.
  • –––, 1994, „Ein neues Paradoxon in der Typentheorie“, Stud. Logik gefunden. Mathematik. (Band 134), Amsterdam: Nordholland, 555–570.
  • du Bois-Reymond, P., 1875, „Über asymptotische Wertehe, infintaere Appproximationen und infitaere Aufloesung von Gleichungen“, Mathematische Annalen, 8: 363–414.
  • Feferman, S., 1964, „Systems of Predicative Analysis“, Journal of Symbolic Logic, 29: 1–30.
  • Ferreira, F. und Wehmeier, K., 2002, „Zur Konsistenz des Delta-1-1-CA-Fragments von Freges Grundgesetzen“, Journal of Philosophic Logic, 31: 301–311.
  • Girard, JY, 1972, Interpretation fonctionelle et eleimination des coupures dans l'arithmetique d'ordre superieure, These d'Etat, Université Paris 7.
  • Goldfarb, Warren, 2005. „Auf Gödels Weg: Der Einfluss von Rudolf Carnap.“Bulletin of Symbolic Logic 11 (2): 185–193.
  • Gödel, K., 1995, Collected Works Volume III, Unveröffentlichte Essays and Lectures, Oxford: Oxford University Press, 1995.
  • –––, 1931, „Über formale unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I“, Monatshefte fü Mathematik und Physik, 38: 173–198.
  • –––, 1944, „Russells mathematische Logik“, in Die Philosophie von Bertrand Russell, PA Schilpp (Hrsg.), Evanston: Northwestern University Press, 123–153.
  • –––, 1958, „Über eine frühere noch nicht benannte Kontrolle des finiten Rechtees“, Dialectica, 12: 280–287.
  • Heck, R., Jr., 1996, „Die Konsistenz prädikativer Fragmente von Freges Grundgesetzen der Arithmetik“, History and Philosophy of Logic, 17 (4): 209–220.
  • van Heijenoort, 1967, Von Frege nach Gödel. Ein Quellenbuch in mathematischer Logik 1879–1931, Cambridge, MA: Harvard University Press.
  • Hindley, R., 1997, Basic Simple Type Theory, Cambridge: Cambridge University Press.
  • Hodges, W., 2008, „Tarski über Padoas Methode: Ein Testfall zum Verständnis von Logikern anderer Traditionen“, in Logic, Navya-Nyāya und Anwendungen: Hommage an Bimal Krishna Matilal, Mihir K. Chakraborti et al. (Hrsg.), London: College Publications, S. 155–169
  • Hofmann, M. und Streicher, Th. 1996, „The Groupoid Interpretation of Type Theory“, in 25 Jahren konstruktiver Typentheorie (Oxford Logic Guides: Band 36), Oxford, New York: Oxford University Press, 83–111.
  • Howard, WA, 1980, „Der Begriff der Konstruktion als Formeln als Typen“in To HB Curry: Aufsätze zu kombinatorischer Logik, Lambda-Kalkül und Formalismus, London, New York: Academic Press, 480–490.
  • Hurkens, AJC, 1995, „Eine Vereinfachung von Girards Paradoxon. Typisierte Lambda-Kalküle und -Anwendungen “in Lecture Notes in Computer Science (Band 902), Berlin: Springer: 266–278.
  • Lambek, J., 1980. "Von (lambda) - Kalkül zu kartesischen geschlossenen Kategorien" in To HB Curry: Essays on Combinatory Logic, (lambda) - Kalkül und Formalismus, J. Seldin und J. Hindley (Hrsg.), London, New York: Academic Press. S. 375–402.
  • Lambek, J. und Scott, PJ, 1986, Einführung in die kategoriale Logik höherer Ordnung (Cambridge Studies in Advanced Mathematics: Band 7), Cambridge: Cambridge University Press; Nachdruck 1988.
  • Lawvere, FW und Rosebrugh, R., 2003, Sets for Mathematics, Cambridge: Cambridge University Press.
  • Martin-Löf, P., 1970, Anmerkungen zur konstruktiven Mathematik, Stockholm: Almqvist & Wiksell.
  • –––, 1971, A Theory of Types, Technischer Bericht 71–3, Stockholm: Universität Stockholm.
  • –––, 1998, „Eine intuitionistische Typentheorie“, in 25 Jahren konstruktiver Typentheorie (Oxford Logic Guides: Band 36), Oxford, New York: Oxford University Press, 127–172.
  • –––, 1975 [1973], „Eine intuitionistische Typentheorie: Prädikativer Teil“, im Logic Colloquium '73 (Proceedings of the Logic Colloquium, Bristol 1973) (Studium der Logik und der Grundlagen der Mathematik: Band 80), HE Rose und JC Shepherdson (Hrsg.), Amsterdam: Nordholland, 73–118.
  • Myhill, J., 1974, „Die Undefinierbarkeit der Menge natürlicher Zahlen in den Ramified Principia“, in Bertrand Russells Philosophie, G. Nakhnikian (Hrsg.), London: Duckworth, 19–27.
  • Miquel, A., 2001, Le Calcul des Constructions implicite: syntaxe et sémantique, Doktorat, Université Paris 7.
  • –––, 2003, „Eine stark normalisierende Curry-Howard-Korrespondenz für die IZF-Mengenlehre“, in Computer Science Logic (Lecture Notes in Computer Science, 2803), Berlin: Springer: 441–454.
  • Oppenheimer, P. und E. Zalta, 2011, „Beziehungen versus Funktionen an den Grundlagen der Logik: typtheoretische Überlegungen“, Journal of Logic and Computation, 21: 351–374.
  • Palmgren, Erik, 1998, „Über Universen in der Typentheorie“, in 25 Jahren konstruktiver Typentheorie (Oxford Logic Guides: Band 36), Oxford, New York: Oxford University Press, 191–204.
  • Poincaré, 1909, „H. La logique de l'infini”Revue de metaphysique et de moral, 17: 461–482.
  • Prawitz, D., 1967, „Vollständigkeit und Hauptsatz für Logik zweiter Ordnung“, Theoria, 33: 246–258.
  • –––, 1970, „Zur Beweistheorie der mathematischen Analyse“, in Logik und Wert (Aufsätze, die Thorild Dahlquist an seinem fünfzigsten Geburtstag gewidmet sind), Filosofiska Studier (Filosof. Föreningen och Filosof. Inst.), Nr. 9, Uppsala: Universität Uppsala, 169–180.
  • Quine, W., 1940, "Review of Church" Eine Formulierung der einfachen Theorie der Typen ", Journal of Symbolic Logic, 5: 114.
  • Ramsey, FP, 1926, „Die Grundlagen der Mathematik“, Proceedings of the London Mathematical Society, s2–25 (1), 338–384.
  • Russell, B., 1903, The Principles of Mathematics, Cambridge: Cambridge University Press.
  • –––, 1908, „Mathematische Logik basierend auf der Typentheorie“, American Journal of Mathematics, 30: 222–262.
  • –––, 1959, Meine philosophische Entwicklung, London, New York: Routledge.
  • Russell, B. und Whitehead, A., 1910, 1912, 1913, Principia Mathematica (3 Bände), Cambridge: Cambidge University Press.
  • Reynolds, J., 1974, „Auf dem Weg zu einer Theorie der Typstruktur“, in Programming Symposium (Lecture Notes in Computer Science: Band 19), Berlin: Springer, 408–425.
  • –––, 1983, „Typen, Abstraktion und parametrischer Polymorphismus“, Tagungsband des 9. IFIP World Computer Congress, Paris, 513–523.
  • –––, 1984, „Polymorphismus ist nicht satztheoretisch. Semantik von Datentypen “, Lecture Notes in Computer Science (Band 173), Berlin: Springer, 145–156.
  • –––, 1985, „Drei Ansätze zur Typstruktur. Mathematische Grundlagen der Softwareentwicklung “in Lecture Notes in Computer Science (Band 185), Berlin: Springer, 97–138.
  • Schiemer, G. und Reck, EH, 2013, „Logik in den 1930er Jahren: Typentheorie und Modelltheorie“, The Bulletin of Symbolic Logic, 19 (4): 433–472.
  • Schütte, K., 1960, Beweistheorie, Berlin: Springer-Verlag.
  • Scott, D., 1993 „Eine typentheoretische Alternative zu ISWIM, CUCH, OWHY“, Theoretical Computer Science, 121: 411–440.
  • Skolem, T., 1970, Ausgewählte Werke der Logik, Jens Erik Fenstad (Hrsg.), Oslo: Universitetsforlaget.
  • Tait, WW, 1967, „Intensivinterpretationen von Funktionalen endlichen Typs“, Journal of Symbolic Logic, 32 (2): 198–212.
  • Takeuti, G., 1955 „Über die grundlegende Vermutung von GLC: I“, Journal der Mathematical Society of Japan, 7: 249–275.
  • –––, 1967, „Konsistenzbeweise von Subsystemen der klassischen Analyse“, The Annals of Mathematics (Second Series), 86 (2): 299–348.
  • Tarski, A., 1931, „Sur les ensembles definissables de nombres reels I“, Fundamenta Mathematicae, 17: 210–239.
  • Urquhart, A., 2003, "The Theory of Types", in The Cambridge Companion von Bertrand Russell, Nicholas Griffin (Hrsg.), Cambridge: Cambridge University Press.
  • Voevodsky, V., 2015, „Eine experimentelle Bibliothek formalisierter Mathematik auf der Grundlage einwertiger Grundlagen“, Mathematical Structures in Computer Science, 25: 1278–1294, online verfügbar.
  • Wiener, N., 1914, „Eine Vereinfachung der Logik der Beziehungen“, Proceedings of the Cambridge Philosophical Society, 17: 387–390.
  • Weyl, H., 1946, „Mathematik und Logik“, American Mathematical Monthly, 53: 2–13.
  • Zermelo, E., 1908, „Untersuchungen über die Grundlagen der Mengenlehre I“, Mathematische Annalen, 65: 261–281.

Akademische Werkzeuge

Sep Mann Symbol
Sep Mann Symbol
Wie man diesen Eintrag zitiert.
Sep Mann Symbol
Sep Mann Symbol
Vorschau der PDF-Version dieses Eintrags bei den Freunden der SEP-Gesellschaft.
Inpho-Symbol
Inpho-Symbol
Schlagen Sie dieses Eintragsthema im Internet Philosophy Ontology Project (InPhO) nach.
Phil Papers Ikone
Phil Papers Ikone
Erweiterte Bibliographie für diesen Eintrag bei PhilPapers mit Links zu seiner Datenbank.

Andere Internetquellen

  • Kubota, K., 2018, „Grundlagen der Mathematik. Genealogie und Überblick “, Manuskript, Entwurf vom 27. März 2018.
  • [HoTT 2013], Homotopietypentheorie: Univalente Grundlagen der Mathematik, Institut für fortgeschrittene Studien.

Empfohlen: