Kann coq seine eigene Metatheorie ausdrücken?

7

Ich lerne etwas über Sprachmetatheorie und Typensysteme und verwende coq , um mein Studium zu formalisieren. Eines der Dinge, die ich tun möchte, ist die Untersuchung von Typsystemen, die abhängige Typen enthalten , was meines Wissens sehr kompliziert ist: Es wäre von unschätzbarem Wert, sich auf coq verlassen zu können.

Da diese Art von Systemfunktion (und andere, einfachere) die Ausdruckskraft meines untersuchten Systems näher an die von coq heranführt, befürchte ich, dass ich auf ein Bootstrapping-Problem stoßen könnte, das sich möglicherweise erst viel später zeigt. Vielleicht kann hier jemand meine Ängste ansprechen, bevor ich mich auf den Weg mache.

Kann coq seine eigene Metatheorie ausdrücken? Wenn nicht, kann es immer noch einfachere Systeme ausdrücken, die gängige Formen der abhängigen Typisierung enthalten?

type-theory dependent-types coq phs
quelle

Antworten:

3

Es ist möglich, die Coq-Logik innerhalb von Coq zu formalisieren, aber nur Teilmengen der Logik wurden bisher formalisiert. Relevante Beiträge sind CoqInCoq , PTS , PTSATR und PTSF .

Rui Baptista
quelle
Ist es möglich, die gesamte Logik von Coq innerhalb von Coq zu formalisieren und nicht nur eine Teilmenge (möglicherweise eine Teilmenge, die für viele praktische Zwecke groß genug ist)? Was genau ist für Sie in der „Formalisierung der Coq-Logik“ enthalten?
Gilles 'SO - hör auf böse zu sein'
1
Die Formalisierung der Coq-Logik würde wahrscheinlich die Formalisierung der Berechnung induktiver Konstruktionen bedeuten. Mich würde auch interessieren, was die Haupthindernisse für die Formalisierung des gesamten CiC sind.
Bellpeace
1
Ich denke, der einzige Teil von Coq, der noch nicht formalisiert wurde, ist der Mechanismus, der (co) induktive und (co) rekursive Definitionen einführt. Unter Berücksichtigung von Gödel sollte es beispielsweise möglich sein, zu beweisen, dass das Fehlen eines Positivitätsprüfers zu Inkonsistenzen führen kann und dass der Positivitätsprüfer gut implementiert ist. Ohne dies ist Coq praktisch nur ECC, das bereits formalisiert wurde, und die Definitionen müssen als Axiome eingeführt oder als Hypothesen beibehalten werden. Ich habe nur einige Formalisierungen aufgelistet, die am einfachsten zu finden waren.
Rui Baptista