Intro in die Martin-Löf-Theorie

Question

Was wäre die beste Einführung in die Ideen von Martin-Löfs über die Typentheorie? Ich habe mir einige Vorträge der Oregon Pl -Sommerschule angesehen, aber ich bin immer noch verwirrt von der folgenden Frage:

Was ist ein Typ?

Ich weiß, was ein Satz ist, da Sie sie durch die üblichen ZF -Axiome definieren können und sie ein sehr intuitives Betonmodell haben. Denken Sie nur an einen Korb voller Sachen. Ich habe jedoch noch keine vernünftige Definition eines Typs gesehen und habe mich gefragt, ob es eine Quelle gibt, die diese Idee für Dummy destillieren würde.

Answer 1

Ein Typ ist eine Eigenschaft von Berechnungen. Es ist das, was Sie auf der rechten Seite eines Dickdarms schreiben.

Lassen Sie mich das näher erläutern. Beachten Sie, dass die Terminologie nicht vollständig Standard ist: Einige Artikel oder Bücher können unterschiedliche Wörter für bestimmte Konzepte verwenden.

EIN Begriff ist ein Element einer abstrakten Syntax, die die Berechnung darstellen soll. Intuitiv ist es ein Parse -Baum. Formell ist es ein endlicher Baum, an dem die Knoten zu einem Alphabet gehören. Ein ungutät Infinitesimalrechnung definiert eine Syntax für Begriffe. Zum Beispiel die (Untyped) Lambda -Kalkül Enthält Begriffe (geschrieben $ M $, $ n $ usw.), die aus drei Arten von Knoten erstellt wurden:

• Variablen, von Arity 0 (eine abgerundbare Sammlung davon), geschrieben $ x $, $ y $ usw.;
• Anwendung einer Variablen, von Arity 1 (eine reneuelbare Sammlung davon, mit einer Bijection an Variablen), geschrieben $ lambda x. M $ usw.;
• Anwendung von Arity 2, geschrieben $ m , n $.

Ein Begriff ist eine syntaktische Konstruktion. EIN Semantik bezieht Begriffe auf Berechnungen. Es gibt viele Arten von Semantik, das häufigste Wesen operativ (beschreiben, wie Begriffe in andere Begriffe umgewandelt werden können) oder Bezeichnung (Beschreibung der Begriffe durch eine Transformation in einen anderen Raum, der normalerweise aus der festgelegten Theorie erstellt wurde).

EIN Typ ist ein Eigentum von Begriffen. EIN Typ System Für einen ungyed Calculus beschreibt die Begriffe, welche Typen. Mathematisch ist ein Typsystem im Kern eine Beziehung zwischen Begriffen und Typen. Genauer gesagt ist ein Typsystem eine Familie mit solchen Beziehungen, indiziert von Kontexte - Normalerweise enthält ein Kontext mindestens Typen für Variablen (dh ein Kontext ist eine Teilfunktion von Variablen zu Typen), so dass ein Begriff möglicherweise nur einen Typ in Kontexten hat, der einen Typ für alle freien Variablen liefert. Welche Art von mathematischen Objekt ein Typ ist, hängt vom Typsystem ab.

Einige Typsysteme werden mit Typen als Sets beschrieben, wobei Begriffe der festgelegten Theorie wie Kreuzung, Vereinigung und Verständnis verwendet werden. Dies hat den Vorteil, sich auf bekannte mathematische Grundlagen auszuruhen. Eine Einschränkung dieses Ansatzes besteht darin, dass er kein Denken über äquivalente Typen zulässt.

Viele Typsysteme beschreiben Typen selbst als Begriffe in einem Kalkül von Typen. Abhängig vom Typsystem können dies die gleichen oder unterschiedlichen Begriffe sein. Ich werde den Satz verwenden Basisbegriff sich auf einen Begriff des Kalküls beziehen, der die Berechnung beschreibt. Zum Beispiel die Einfach tippte Lambda -Kalkül verwendet den folgenden Arten von Typen (geschrieben $ tau $ usw.):

• Basistypen von Arity 0 (eine endliche oder abgerundbare Sammlung davon), geschrieben $ a $, $ B $ usw.;
• Funktion, von Arity 2, geschrieben $ Tau_0 Rightarrow Tau_1 $.

Die Beziehung zwischen Begriffen und Typen, die den einfach typisierten Lambda -Kalkül definieren, wird normalerweise durch definiert durch Schreibregeln. Tippregeln sind nicht die einzige Möglichkeit, ein Typsystem zu definieren, aber sie sind häufig. Sie eignen sich gut für Kompositionssysteme, dh Typsysteme, bei denen die Typen eines Begriffs aus den Arten von Subterms hergestellt werden. Typisierungsregeln definieren ein induktives Typsystem: Jede Typierungsregel ist ein Axiom, das feststellt, dass für jede Instanziierung der Formeln über der horizontalen Regel auch die Formel unter der Regel wahr ist. Sehen Wie lese ich Schreibregeln? für mehr Details. Gibt es eine turende, typisierte Lambda -Berechnung? kann auch von Interesse sein.

Für den einfach typisierten Lambda -Kalkül die Urteiltyp $ Gamma vdash m: tau $ bedeutet, dass $ M $ den Typ $ tau $ im Kontext $ gamma $ hat. Ich habe die formale Definition von Kontexten weggelassen. $$ dfrac {x: tau in gamma} { gamma vdash x: tau} ( gamma) qquad dfrac { gamma { gamma {{ gamma vdash lambda xm: tau_0 rightarrow tau_1} ( mathord { rightarrow} i) qquad dfrac { gamma vdash m: tau_0 tau_0 quad gamma vdash n: tau { Gamma vdash m , n: tau_1} ( mathord { rightarrow} e) $$

Wenn beispielsweise $ A $ und $ B $ basiert, sind $ lambda x. lambda y. x , y $ hat den Typ $ (a rightarrow b) rightarrow a rightarrow b $ in einem beliebigen Kontext (von unten nach oben, $ $ ( mathord { rightarrow} i) $ zweimal, dann $ ( mathord { rightarrow} e) $ und schließlich $ ( gamma) $ in jeder Filiale).

Es ist möglich, die Arten der einfach typisierten Lambda -Kalkül als Sätze zu interpretieren. Dies ergibt eine Denotationssemantik für die Typen. Eine gute Denotationssemantik für die Basisbegriffe würde jedem Basisbegriff ein Mitglied der Bezeichnung aller ihrer Typen zuweisen.

Intuitionistische Typtheorie (Auch als Martin-Löf-Theorie bekannt) ist komplexer, der einfach Lambda-Kalkül tippt, da sie im Kalkül der Typen viel mehr Elemente aufweist (und auch einige Konstanten zu den Basisbegriffen hinzufügt). Aber die Kernprinzipien sind gleich. Ein wichtiges Merkmal der Martin-Löf-Theorie ist, dass Typen Basisbegriffe enthalten können (sie sind abhängige Typen): Das Universum der Basisbegriffe und das Universum der Typen sind gleich, obwohl sie durch einfache syntaktische Regeln unterschieden werden können (normalerweise als Sortierung bezeichnet, dh in der Umschreibung der Theorie zugewiesen).

Es gibt Typsysteme, die weiter gehen und die Typen und Basisbegriffe vollständig mischen, sodass zwischen beiden keine Unterscheidung besteht. Solche Typsysteme sollen sein Auftrag von oben. In solchen Kalkül haben Typen Typen-ein Typ kann auf der linken Seite des $: $ erscheinen. Das Konstruktionsberechnung ist das Paradigma von abhängigen Typen höherer Ordnung. Das Lambda Würfel (Auch als Barendregt Cube bekannt) klassifiziert Typsysteme in Bezug darauf, ob sie zuzulassen, dass die Begriffe von Typen abhängen (Typen (Typen)Polymorphismus - Einige Basisbegriffe enthalten Typen als Subterms), Typen, die von Begriffen (abhängigen Typen) abhängen oder von Typen abhängen (von Typen abhängen (von Typen) (von Typen abhängig (Typ Operatoren - Der Arten von Typen hat einen Begriff der Berechnung).

Die meisten Typsysteme wurden set-theoretische Semantik gegeben, um sie mit den üblichen Grundlagen der Mathematik zu binden.Wie hängen Programmiersprachen und Grundlagen der Mathematik zusammen? undWas ist der Unterschied zwischen den semantischen und syntaktischen Ansichten der Funktionstypen? kann hier von Interesse sein. Es hat auch gearbeitet, die Typentheorie als Grundlage für die Mathematik zu verwenden - Set -Theorie ist die historische Grundlage, ist aber nicht die einzig mögliche Wahl. Homotopie -Typ Theorie ist ein wichtiger Meilenstein in dieser Richtung: Es beschreibt die Semantik von beabsichtigt intuitionistische Typtheorie in Bezug auf Homotopie -Theorie und konstruiert die festgelegte Theorie in diesem Rahmen.

Ich empfehle Benjamin Pierces Bücher Typen und Programmiersprachen und Fortschritte Themen in Typen und Programmiersprachen. Sie sind für jeden Studenten zugänglich, der keine andere Voraussetzung als die grundlegende Vertrautheit mit formalen mathematischen Argumentation hat. Tapl beschreibt viele Typsysteme; Abhängige Typen sind Gegenstand von Kapitel 2 von Attapl.

Answer 2

Vielleicht ist eine bessere Frage für jemanden, der aus der festgelegten Theorie stammt und sich mit der Unterscheidung der Theorie und der Martin-Löf-Theorie unterscheidet, darüber nachzudenken, was Sätze sind. Ihre Intuitionen über die festgelegte Theorie und die Grundlagen der Mathematik werden mit unbestrittenen set-theoretischen Annahmen infiziert, die Sie für selbstverständlich halten. Alas Martin-Löf-Theorie teilt diese Annahmen nicht.

Im Gegensatz zum konventionellen Verständnis ist die festgelegte Theorie eine Theorie von zweiBeziehungen: Gleichberechtigung und Mitgliedschaft setzen, nicht nur die Mitgliedschaft festlegen. Und diese beiden Beziehungen sind in wesentlichen unterschiedlichen Phasen aufgebaut.

1. Wir bauen Logik erster Ordnung als Theorie der Gleichheit willkürlicher Dinge auf (nicht nur Sätze). Logik erster Ordnung verwendet eine informell Begriff des Beweises. Der Konzeptbeweis ist selbst in Logik erster Ordnung nicht allein in formell formell ausdrückbar.

2. Dann bauen wir als Theorie der Sets ein Set-Theory auf der Logik erster Ordnung auf und setzen die Mitgliedschaft.

3. SET -Mitgliedschaft und Gleichheit werden dann durch das Axiom der Erweiterung in Verbindung gebracht, die besagt, dass zwei Sätze genau gleich sind, wenn sie die gleichen Mitglieder haben.

4. Schließlich erhält das informelle Beweiskonzept aus (1) eine Ex-Post-Rationalisierung als bestimmte Sätze (Proof-Bäume).

Es ist wichtig zu erkennen, dass der Begriff vonnachweisen ist also a Bürger der zweiten Klasse in der festgelegten Theorie.

Dieses Setup funktioniert einwandfrei für herkömmliche kleine/mittelgroße Mathematik, aber da wir jetzt große Beweise wie die Klassifizierung aller endlichen einfachen Gruppen oder die Überprüfung nicht trivialer Computerprogramme in Anspruch nehmen, fällt es auseinander, weil es auseinander fällt, weil es auseinander fällt Es führt nicht zu einer einfachen Mechanisierung.

Die Theorie vom Typ Martin-Löf ist unterschiedlich: Sie baut den Begriff des Beweises und den Typ (was ungefähr die Martin-Löf-Typ Theorie ist, welche Sätze die Theorie festlegen sollen) in einem Fell-Schlag. Das heisst Beweise sind erstklassige Bürger der Theorie. Während ein Set von seinen Mitgliedern gegeben wird, werden die Theorie -Ablagerungen formell angegeben, was als Beweis dafür gilt, dass etwas ein festgelegtes Mitglied ist. Im Gegensatz dazu wird ein Typ durch seine Beweisnachweise angegeben. Sie verstehen also einen Typ $ t $ genau, wenn Sie verstehen, was als Beweis von $ t $ zählt.

Was sind diese Beweise, die Typen bewohnen? Vereinfachung ein bisschen (und weglassen Identitätstypen), sie sind Funktionsprogramme, genauer gesagt Begriffe in $ lambda $ -Calculus, die typbar sind. Dies ist als Curry-Howard-Korrespondenz bekannt. Es gibt eine schöne neue und weniger Ad-hoc-Grundlage für konstruktive Mathematik. Es funktioniert nicht so gut für klassische Mathematik -Hart.

Answer 3

Ich bin mir der einfachen Wege in die Martin-Löf-Theorie nicht bewusst. Ich denke, das folgende könnte als Einführungen dienen.

• B. Nordström, K. Petersson, JM Smith, Martin-Löfs Typentheorie.
• B. Nordström, K. Petersson, JM Smith, Programmierung in Martin-Löfs Typentheorie.

Wenn Sie sich jedoch von der Frage "Was ist ein Typ" verwirrt, schlage ich vor, zuerst in viel einfachere Typ-Theorien einzugehen. Jede typisierte Programmiersprache wird jedoch tun, aber z. B. OCAML, F# und Haskell wären besonders nützlich. Wenn man ein wenig vereinfacht, könnte man sagen, dass die Martin-Löf-Theorie die Typen hinter den oben genannten Sprachen auf zwei Arten erweitert:

1. Mit abhängige Typen. Sie finden sie in zahmer Form in verschiedenen Programmiersprachen.
2. Mit Identitätstypen. Dies ist die Hauptinnovation von Martin-Löfs über früheren abhängigen Theorien.

Die Schlüsselidee hinter abhängigen Typen ist einfach: Typen können durch Programme parameterisiert werden. Dies ist nicht möglich (ein bisschen vereinfacht) in herkömmlichen Typierungssystemen wie den oben genannten. Die Konsequenzen sind zwar tiefgreifend: Die abhängigen Typen heben die Curry-Howard-Korrespondenz zur konstruktiven Logik erster Ordnung an. Identitätstypen sind etwas ungewöhnlich. Wenn/wenn Sie sich mit einer Sprache wie Haskell wohl fühlen, können Sie lernen Agda, was im Grunde genommen Haskell mit der Martin-Löf-Theorie ist. Ich bin der Meinung, dass AGDA für einen Programmierer viel einfacher zu lernen ist als die oben genannten Bücher zu lesen.