Warum eine unendliche Typhierarchie?

18

Coq, Agda und Idris haben eine unendliche Typhierarchie (Typ 1: Typ 2: Typ 3: ...). Aber warum nicht stattdessen λC, das System im Lambda-Würfel, das der Konstruktionsrechnung am nächsten kommt und nur zwei Sorten und und diese Regeln hat? $*$ $◽$

\frac{}{\emptyset ⊢ * : ◽}

$\frac {} {∅ ⊢ * : ◽}$

\frac{Γ ⊢ T_{1} : s_{1} Γ, x : T_{1} ⊢ t : T_{2}}{Γ ⊢ (λ x : T_{1}, t) : (Π x : T_{1}, T_{2})}

$\frac {Γ ⊢ T _ 1 : s _ 1 \qquad Γ, \: x : T _ 1 ⊢ t : T _ 2} {Γ ⊢ (λ \: x : T _ 1, \: t) : (Π \: x : T _ 1, \: T _ 2)}$

\frac{Γ ⊢ T_{1} : s_{1} Γ, x : T_{1} ⊢ T_{2} : s_{2}}{Γ ⊢ (Π x : T_{1}, T_{2}) : s_{2}}

$\frac {Γ ⊢ T _ 1 : s _ 1 \qquad Γ, \: x : T _ 1 ⊢ T _ 2 : s _ 2} {Γ ⊢ (Π \: x : T _ 1, \: T _ 2) : s _ 2}$

Das scheint einfacher zu sein. Hat dieses System wichtige Einschränkungen?

coq dependent-type calculus-of-constructions Rui Baptista
quelle

19

Tatsächlich ist der Ansatz des CoC aussagekräftiger - er ermöglicht eine willkürliche und aussagekräftige Quantifizierung. Zum Beispiel der Typ $\forall a.\; a \to a$ kann mit sich selbst instanziiert werden, um $(\forall a.\; a \to a) \to (\forall a.\; a \to a)$ , was mit einer Universumshierarchie nicht möglich ist.

Der Grund, warum es nicht weit verbreitet ist, liegt darin, dass eine improvisierte Quantifizierung mit der klassischen Logik nicht vereinbar ist. Wenn Sie es haben, können Sie kein typentheoretisches Modell angeben, in dem Typen auf naive Weise als Mengen interpretiert werden - siehe John Reynolds berühmte Arbeit Polymorphism is Not Set-theoretic .

Da viele Leute die Typentheorie verwenden möchten, um gewöhnliche mathematische Beweise maschinell zu überprüfen, sind sie im Allgemeinen nicht begeistert von typentheoretischen Merkmalen, die mit den üblichen Grundlagen unvereinbar sind. Tatsächlich unterstützte Coq ursprünglich Impredicativity, aber sie haben es stetig aufgegeben.

Neel Krishnaswami
quelle

9

Ich beglückwünsche Neels (wie immer ausgezeichnet) Antwort mit einer etwas ausführlicheren Erklärung, warum Levels in der Praxis verwendet werden.

Die erste wichtige Einschränkung von CoC ist, dass es trivial ist! Eine überraschende Beobachtung ist, dass es keinen Typ gibt, für den man beweisen kann , dass er mehr als ein Element hat, geschweige denn eine unendliche Anzahl von ihnen. Wenn Sie nur 2 Universen hinzufügen, erhalten Sie die natürlichen Zahlen mit nachweislich unendlich vielen Elementen und allen "einfachen" Datentypen.

Die zweite Einschränkung sind die Berechnungsregeln: CoC unterstützt nur die Iteration , dh die wiederverwendbaren Funktionen haben keinen Zugriff auf die Unterausdrücke ihrer Argumente. Aus diesem Grund ist es praktischer, induktive Typen als primitive Konstruktion hinzuzufügen, wodurch der CIC entsteht. Jetzt tritt jedoch ein anderes Problem auf: Die natürlichste Induktionsregel ( in diesem Zusammenhang als Eliminierung bezeichnet ) widerspricht der Ausgeschlossenen Mitte! Diese Probleme treten nicht auf, wenn Sie die Induktionsregel auf prädikative Typen mit Universen beschränken.

Zusammenfassend lässt sich sagen, dass CoC weder die Ausdruckskraft noch die Robustheit in Bezug auf die Konsistenz aufweist, die Sie in einem Basissystem wünschen. Das Hinzufügen von Universen löst viele dieser Probleme.

Cody
quelle

Haben Sie einige Referenzen für die erste Einschränkung? Wenn nicht, könnten Sie Hinweise geben, wie das zweite Universum hilft, die (propositionale? Meta-?) Ungleichung zu beweisen?

Łukasz Lew

@ ŁukaszLew Es ist eigentlich eine einfache Konsequenz des "Proof irrelevant" -Modells, das einigermaßen leicht gegoogelt werden kann. In diesem Modell hat kein Typ mehr als 1 Element. Mit 2 Universen wird verhindert, dass dieses Modell existiert. Alexandre Miquels These liefert eine Referenz für einen Typ mit unendlich vielen Elementen mit 2 Universen.

Cody

Warum eine unendliche Typhierarchie?

Antworten: