Erbliche Substitution durch eine Universushierarchie

Ich habe über die erbliche Substitution des einfachen Lambda-Kalküls und des logischen Rahmens mit unterschiedlichen Begriffen und Typen gelesen .

Ich frage mich, gibt es Beispiele für erbliche Substitution in einem abhängig typisierten System mit einer Universumshierarchie? dh wo $True : Set_0 : Set_1:Set_2$ usw.

Ich frage mich insbesondere, wie man in einem solchen System eine Induktionsmaßnahme etabliert. Die einfach eingegebene Version nimmt strukturell im Typ der zu ersetzenden Variablen ab. Dies funktioniert nicht mit abhängigen Typen. Für LF verwendet das von mir verknüpfte Papier das einfach getippte Löschen der Begriffe, wodurch die Form des Typs induziert wird.

Das Löschen auf einfache Typen funktioniert jedoch nicht mit einer Universumshierarchie, da, wenn Sie so etwas haben:

• $f : (x : Set_1)\to x \to True$ impliziert dies
• $f\ ((y : True) \to True \to True ): True \to True \to True$

Das Anwenden einer Funktion führte zu einem strukturell größeren Typ.

Ich gehe davon aus, dass die Lösung etwas mit den Universumsindizes zu tun hat, aber wenn es eine vorhandene Technik gibt, mit der festgestellt werden kann, dass die Induktion begründet ist, würde ich sie lieber zitieren, als mir selbst etwas auszudenken.

Hier ist eine Referenz für das prädikative System F. Das Maß umfasst tatsächlich die Mehrfachmenge der Universalebenen in einem Typ. Ich kann nicht viel darüber sagen, ob sich dieser Ansatz auf die prädikativ abhängige Typentheorie verallgemeinert.

Ab November 2018 ist offen, wie dies für abhängige Typentheorien mit großen Eliminierungen zu tun ist.

Es ist nicht schlecht festzustellen, dass die Rekursion begründet ist. Sie können den Satz von Pataraia verwenden, um zu beweisen, dass der gewünschte Fixpunkt existiert. Eine Anleitung finden Sie unter Robert Harpers * Konstruieren von Typsystemen über eine Betriebssemantik . (Sie können dies auch über eine induktiv-rekursive Definition tun.)

Der schwierige Teil besteht darin, die erbliche Substitution auf nette Weise zu formulieren - die natürliche Richtung führt Sie dazu, nicht einen Begriff, sondern eine vollständige Substitution für einen Kontext zu ersetzen, und dies wirft viele Fragen auf, wann und wie Eigenschaften von Dingen festgelegt werden können wie Kompositionen von (erblichen) Substitutionen.

Wenn es sich als unmöglich herausstellen würde, wäre ich äußerst schockiert. Derzeit hat es jedoch niemand getan. Wenn Sie daran arbeiten möchten, würde ich vorschlagen, sich mit Andreas Abel, Dan Licata und Mike Shulman in Verbindung zu setzen. (Oder ich für diese Angelegenheit.)