Warum reichen kirchlich kodierte Typen nicht aus, um induktive Beweise auszudrücken?

Antworten:

5

Wie würden Sie innerhalb des reinen CoC beweisen, dass das Induktionsprinzip der Kirchenzahlen gilt? Siehe Thomas Streicher's, Unabhängigkeit des Induktionsprinzips und des Axioms der Wahl in der reinen Konstruktionsrechnung .

Martin Berger
quelle
1
Herman Geuvers hat auch ( hier ) bewiesen , dass keine mögliche Codierung der natürlichen Zahlen funktionieren kann.
Cody
Das Ergebnis von @cody Geuvers gilt für abhängige Typen zweiter Ordnung. Ist es offensichtlich, dass es sich auf abhängige Typen höherer Ordnung verallgemeinert?
Martin Berger
1
Es ist nicht offensichtlich, nein. Ich denke jedoch, dass die in diesem Artikel beschriebene Modellkonstruktion verallgemeinert wird, da sie auf einem Modell basiert, das ursprünglich für die vollständige Berechnung entwickelt wurde.
Cody
1

Es gibt ein kürzlich in Annals of Pure and Applied Logic veröffentlichtes Ergebnis, in dem kirchenkodierte Daten Realisierer ihres eigenen Induktionsprinzips sind. In diesem System ist das Induktionsprinzip für natürliche Zahlen, Bäume, Listen ... ableitbar. In den Kernkalkül sind keine Datentypkonstruktoren eingepackt. Er beginnt bei einem extrinsischen (Curry-Stil) System F, das drei Typisierungskonstrukte hinzufügt: implizites Produkt, heterogene Gleichheit und abhängige Schnittmenge.

Das Geuvers-Ergebnis gilt nicht für diesen Kalkül und wird in der Veröffentlichung erwähnt.

Aufsatz: "Von der Realisierbarkeit zur Induktion durch abhängige Schnittmenge" , von Aaron Stump

Eric Bond
quelle