Welche Rolle spielt Prädikativität bei induktiven Definitionen in der Typentheorie?

Wir wollen oft ein Objekt nach bestimmten Inferenzregeln definieren. Diese Regeln bezeichnen eine Erzeugungsfunktion die, wenn sie monoton ist, einen am wenigsten festen Punkt ergibt . Wir nehmen die "induktive Definition" von sein . Darüber hinaus erlaubt uns die Monotonie von , mit dem "Induktionsprinzip" zu argumentieren, um zu bestimmen, wann eine Menge enthält (dh wann eine Eigenschaft universell für ).F μ F A : = μ F A F A $A \in U$$F$$\mu F$$A := \mu F$$A$$F$$A$$A$

In Coq entspricht dies dem Schreiben einer -Definition von mit expliziten Einführungsbegriffen. Während diese Definition eine bestimmte Funktion , ist diese Funktion nicht notwendigerweise monoton. Coq verwendet daher einige syntaktische Überprüfungen, um die "Formtreue" der Definition zu gewährleisten. In gewisser Näherung werden Vorkommen von in negativen Positionen in den Typen der Einführungsterme verworfen. A F $\mathtt{Inductive}$$A$$F$$A$

(Wenn mein Verständnis bis zu diesem Punkt fehlerhaft ist, korrigieren Sie mich bitte!)

Zunächst einige Fragen im Zusammenhang mit Coq:

1) Ist die syntaktische Überprüfung in Coq lediglich dazu dienen , um sicherzustellen , dass die Definition von ist prädikativen ? (Wenn ja, ist Impredativität die einzige Art und Weise, in der die Definition falsch definiert wird?) Oder wird auf Monotonie geprüft? (Ist Nicht-Monotonie dementsprechend das, was es töten könnte?)$A$

2) Ist eine solche negative Auftreten von notwendigerweise implizieren , dass ‚s Definition ist imprädikative / nicht-monotonen? Oder kann Coq einfach nicht überprüfen, ob es in diesem Fall gut definiert ist?$A$$A$

Und allgemeiner:

3) Welche Beziehung besteht zwischen der Prädikativität einer induktiven Definition und der Monotonie der Erzeugungsfunktion dieser Definition? Sind das zwei Seiten einer Medaille? Sind sie nicht verwandt? Informell, was zählt mehr?

Nein, in diesem Fall hängen Prädikativität und Monotonie nicht eng zusammen.

Die Positivitätsprüfung in Coq / Adga dient dazu, sicherzustellen, dass Sie ungefähr den kleinsten Fixpunkt einer monotonen Sache nehmen.

So stellen Sie sich induktive Typen in Form von Gittern und monotonen Operatoren vor. Erinnern wir uns, dass das Knaster-Tarski-Theorem besagt, dass auf einem vollständigen Gitter jeder monotone Operator einen kleinsten festen Punkt . Als nächstes können wir uns die Typen in einer Typentheorie als ein Gitter unter Beweisbarkeit vorstellen. Das heißt, Typ liegt unter wenn die Wahrheit von die von . Nun möchten wir einen monotonen Operator für Typen nehmen und Knaster-Tarski verwenden, um eine Interpretation des kleinsten Fixpunkts dieses Operators . f : L → L μ ( f ) S T S T F μ ( F $L$$f : L \to L$$\mu(f)$$S$$T$$S$$T$$F$$\mu(F)$

Typen in der Typentheorie sind jedoch nicht nur ein Gitter: Sie bilden eine Kategorie. Das heißt, da zwei Typen und gibt es möglicherweise viele Möglichkeiten für unter seinen , mit einer Art und Weise für jeden Beweis . Ein Typoperator auch bei diesen Beweisen etwas Vernünftiges tun. Die entsprechende Verallgemeinerung der Monotonie ist Funktorialität . Das heißt, wir möchten, dass einen Operator für Typen und auch eine Aktion für Beweise hat, so dass, wenn , dann .T S T e : S → T F F e : S → T F ( e ) : F ( S ) → F ( T $S$$T$$S$$T$$e : S \to T$$F$$F$$e : S \to T$$F(e) : F(S) \to F(T)$

Nun wird die Funktionalität durch Summen und Produkte bewahrt (dh wenn und Endofunktoren für Typen sind, dann sind und (punktweise) auch Funktoren für Typen (vorausgesetzt, wir haben Summen und Produkte in unserer Algebra) Es wird jedoch nicht vom Funktionsraum beibehalten, da der Exponential-Bifunktor in seinem linken Argument kontravariant ist. Wenn Sie also eine induktive Typdefinition schreiben, definieren Sie einen Funktor, der einen kleinsten festen Punkt annimmt Um sicherzustellen, dass es sich tatsächlich um einen Funktor handelt, müssen Sie Vorkommen des rekursiven Parameters auf der linken Seite von Funktionsräumen ausschließen - daher die Positivitätsprüfung.G F + G F × G F → $F$$G$$F+G$$F\times G$$F \to G$

Impredikativität (im Sinne von System F) wird generell vermieden, da es sich um ein Prinzip handelt, das Sie zwingt, zwischen klassischer Logik und satztheoretischen Modellen zu wählen. Sie können Typen in der klassischen Mengenlehre nicht als Mengen interpretieren, wenn Sie über eine Indexierung im F-Stil verfügen. (Siehe Reynolds 'berühmter "Polymorphismus ist nicht satztheoretisch".)

Kategorisch bedingt besagt die Impredikativität im F-Stil, dass die Kategorie von Typen und Begriffen eine kleine vollständige Kategorie bildet (dh, homs und objects sind beide Mengen und Grenzen aller kleinen Diagramme existieren). Klassischerweise erzwingt dies, dass eine Kategorie ein Poset ist. Viele Konstruktivisten sind konstruktiv, weil sie wollen, dass ihre Theoreme mehr Systeme als nur klassische Logik enthalten, und deshalb nichts beweisen wollen, was klassisch falsch wäre. Daher sind sie misstrauisch gegenüber dem anmaßenden Polymorphismus.

Mit Polymorphismus können Sie jedoch viele Bedingungen angeben, die Ihrer Typentheorie nach klassisch "groß" sind - und Positivität ist eine davon! Ein Typoperator ist funktional, wenn Sie einen polymorphen Term erzeugen können:$F$

Sehen Sie, wie dies Funktionalität entspricht? IMO, dies wäre eine sehr schöne Option in Coq, da Sie damit viel einfacher generische Programme erstellen könnten. Die syntaktische Natur der Positivitätsprüfung ist ein großes Hindernis für die generische Programmierung, und ich würde gerne die Möglichkeit klassischer Axiome gegen flexiblere Funktionsprogramme eintauschen.

EDIT: Die Frage, die Sie nach dem Unterschied zwischen Prop und Set stellen, ergibt sich aus der Tatsache, dass die Coq-Entwickler Ihnen erlauben möchten, über Coq-Theoreme in naiven satztheoretischen Begriffen nachzudenken, wenn Sie möchten, ohne Sie dazu zu zwingen . Technisch gesehen teilen sie Prop und Set auf und verhindern dann, dass Sets vom rechnerischen Inhalt von Prop abhängen.

So können Sie Prop als Wahrheitswerte in ZFC interpretieren, bei denen es sich um die booleschen Werte true und false handelt. In dieser Welt sind alle Beweise von Sätzen gleich, und so sollte es offensichtlich nicht möglich sein, auf den Beweis eines Satzes zu verzweigen. Das Verbot von Sätzen in Abhängigkeit vom Recheninhalt von Proofs of Prop ist also durchaus sinnvoll. Darüber hinaus ist das 2-Element-Boolesche Gitter offensichtlich ein vollständiges Gitter, so dass es eine aussagekräftige Indizierung unterstützen sollte, da willkürlich festgelegte Übereinstimmungen existieren. Die Einschränkung der Prädikativität für Mengen ergibt sich aus der Tatsache (oben erwähnt), dass die Indexierung im F-Stil in klassischen satztheoretischen Modellen degeneriert ist.

Coq hat andere Modelle (es ist konstruktive Logik!), Aber der Punkt ist, dass es von der Stange nie beweisen wird, dass ein klassischer Mathematiker verwirrt wäre.

Es gibt eine sehr tiefe Verbindung zwischen induktiven Definitionen und Impredikativität, aber nach meinem Verständnis ist die Prädikativität im Zusammenhang mit dem, was Sie sprechen, nicht besonders relevant, und der Test dient lediglich der Gewährleistung der Monotonie, so dass die Fixpunkttheorie dies sein kann angewendet, nämlich, dass das Prinzip der Induktion gut definiert ist. (Ich bin bereit, in diesem Punkt korrigiert zu werden.)

Die Beziehung zwischen Impredikativität und induktiven Definitionen wird in diesem Vortrag von Coquand untersucht. Es geht auf einige Ergebnisse aus den 50er Jahren von G. Takeuti zurück, wonach improvisierte Definitionen auf induktive Definitionen reduziert werden können. Das Buch

• Beweistheorie improvisatorischer Teilsysteme der Analysis - Monographien und Lehrbücher der Physik 2 von W. Buchholz, K. Schutte

Gibt eine gute Analyse des Themas, wenn Sie es in die Finger bekommen können. Diese Folien geben einen Überblick.

Um die ausgezeichnete Erklärung von Neil zu vervollständigen, hat Impredikativität einen "weichen" Sinn: Die Definition von Mengen oder Sammlungen unter Verwendung eines Verweises auf sich selbst. In diesem Sinne:

Inductive Lam : Set :=
| Var : Nat -> Lam
| App : Lam -> Lam -> Lam
| Abs : (Lam -> Lam) -> Lam

ist eine improvisatorische Definition, da sie einen induktiven Typ definiert, Lam unter Verwendung eines Funktionsraums (Lam -> Lam), der sich auf die Sammlung selbst bezieht. In dieser Situation ist Impredikativität schädlich : Es ist möglich, Cantors Theorem zu verwenden, um Falsch zu beweisen. Tatsächlich handelt es sich hierbei um dieselbe Art von Impredikativität, die die naive Mengenlehre als konsistente Grundlage für die Mathematik außer Acht lässt. Es ist daher in Coq verboten. Wie Sie wissen, ist eine andere Form der Impredikativität zulässig:

Definition Unit : Prop := forall X:Prop, X -> X

Die Definition der Einheit als Satz bezieht sich auf die Sammlung aller Sätze, zu denen sie gehört. Aus für mich etwas undurchsichtigen Gründen ist diese Eindeutigkeit jedoch nicht schädlich, da sie in ZFC (in Form eines unbegrenzten Verständnisses ) vorliegt, von dem nicht bekannt ist, dass sie inkonsistent ist.

Zusammenfassend ist das negative Auftreten induktiver Typen in Definitionen eine Form der Impredikativität, aber nicht diejenige, auf die üblicherweise Bezug genommen wird, wenn von CoC als einem improvisierten Rahmen gesprochen wird .