Reduzieren von Produkten in HoTT auf Church / Scott-Codierungen

Also gehe ich gerade mit einigen Leuten das HoTT-Buch durch. Ich habe die Behauptung aufgestellt, dass die meisten induktiven Typen, die wir sehen werden, auf Typen reduziert werden können, die nur abhängige Funktionstypen und Universen enthalten, indem der Typ des Rekurors als Inspiration für den äquivalenten Typ verwendet wird. Ich fing an zu skizzieren, wie ich dachte, dass dies funktionieren würde, und nach einigem Stolpern kam ich zu dem, was ich für eine Antwort hielt.

\cdot \times \cdot \equiv \prod_{EIN, B., C. :: U.} (EIN \to B. \to C.) \to C.

$\cdot \times \cdot \equiv \prod_{A, B, C : \mathcal{U}} (A \to B \to C) \to C$

(\cdot, \cdot) \equiv λ ein :: EIN . λ b :: B. . λ C. :: U. . λ G :: EIN \to B. \to C. . G (ein) (b)

$(\cdot, \cdot) \equiv \lambda a : A. \lambda b : B. \lambda C : \mathcal{U}. \lambda g : A \to B \to C. g(a)(b)$

i n d_{A \times B} \equiv λ C . λ g . λ p . g (p r_{1} (p)) (p r_{2} (p))

$ind_{A \times B} \equiv \lambda C. \lambda g. \lambda p. g(pr_1(p))(pr_2(p))$

$pr_1$ $pr_2$ $ind_{A \times B}$

{ind}_{A \times B} : \prod_{C : A \times B \to U} (\prod_{a : A} \prod_{b : B} C ((a, b))) \to \prod_{p : A \times B} C ((p r_{1} (p), p r_{2} (p)))

$\text{ind}_{A \times B} : \prod_{C : A \times B \to \mathcal{U}} (\prod_{a:A} \prod_{b:B} C((a, b))) \to \prod_{p : A \times B} C((pr_1(p), pr_2(p)))$

Und es scheint keine einfache Lösung dafür zu geben. Ich habe auch über die folgende Definition nachgedacht.

i n d_{A \times B} \equiv λ C . λ g . λ p . p (C (p)) (g)

$ind_{A \times B} \equiv \lambda C. \lambda g. \lambda p. p(C(p))(g)$

Aber das ist einfach kein typecheck.

$uniq_{A \times B}$ $C((pr_1(p), pr_2(p)))$ $C(p)$ $uniq_{A \times B}$ scheint ohne die richtige Form der Induktion nicht definierbar zu sein. Selbst wenn ich mir Identitätstypen erlauben würde, wie sie im Buch vorgestellt werden, wäre ich einer Definition von nicht näher gekommen $uniq_{A \times B}$

Es scheint also, dass wir hier den Rekorder definieren können, aber nicht den Induktor. Wir können etwas definieren, das dem Induktor ziemlich nahe kommt, es aber nicht ganz schafft. Mit der Rekursion können wir Logik ausführen, wobei dieser Typ die Bedeutung der logischen Konjunktion ist, aber wir können nicht Dinge über Produkte beweisen, die fehlen.

Können wir die Art von Reduzierung vornehmen, die ich behauptet habe? Das heißt, können wir einen Typ definieren, indem wir nur abhängige Funktionstypen und Universen verwenden, die eine Paarungsfunktion und einen Induktor mit denselben definierenden Gleichungen und Typen wie Produkte haben? Es ist mein wachsender Verdacht, dass ich eine falsche Behauptung aufgestellt habe. Es scheint, als könnten wir uns so frustrierend nähern, schaffen es aber nicht ganz. Wenn wir es nicht definieren können, welche Art von Argument erklärt, warum wir es nicht können? Erhöhen Produkte, wie sie im HoTT-Buch vorgestellt werden, die Stärke des Systems?

type-theory type-checking dependent-types homotopy-type-theory Jake
quelle

Soweit ich weiß, gibt uns die übliche kirchliche Kodierung einen Typ, der eine nicht abhängige Eliminierung (Recursor), aber keine abhängige Eliminierung (Induktor) zulässt. Ihre Frage könnte mit dieser zusammenhängen . Ich bin mir nicht sicher, ob HoTT diesbezüglich etwas ändert.

Chi

Das scheint hilfreich zu sein. Nach meinem Verständnis würde meine Frage für die prädiktive Berechnung von Konstruktionstypen (Coq minus (co) induktiv) beantwortet. Ich habe nach Papieren gesucht, die diese Modelle durchgehen (Modelle von CoC, die keine Modelle von CiC sind), aber keine finden können. Haben Sie zufällig eine Quelle?

Jake

Leider habe ich keine Referenz zum Teilen. Ich wäre auch daran interessiert, eine Quelle für diese Folklore-Tatsache zu haben.

Chi

Ich finde auch immer wieder folkloristische Hinweise auf diese Tatsache, aber ich kann anscheinend keine Erklärung finden.

Jake

Schöne Frage, aber würde es nicht besser auf cstheory.stackexchange.com

Martin Berger

Antworten:

Die Standardreferenz, die ich oft gebe, ist, dass Induktion in der abhängigen Typentheorie zweiter Ordnung von Herman Geuvers nicht ableitbar ist , die besagt, dass es keinen Typ gibt

N. :: T. y p e

$N : \mathrm{Type}$

mit Funktionen

Z. :: N. S. :: N. \to N.

$Z:N\qquad S:N\rightarrow N$

so dass

ich n d :: Π P. :: N. \to T. y p e . P. Z. \to (Π m :: N. . P. m \to P. (S. m)) \to Π n :: N. . P. n

$\mathrm{ind}:\Pi P:N\rightarrow \mathrm{Type}.P\ Z\rightarrow (\Pi m:N.P\ m\rightarrow P\ (S\ m))\rightarrow \Pi n:N. P\ n$

ist nachweisbar. Dies deutet darauf hin, dass eine solche Codierung tatsächlich nicht für Paare funktionieren kann, wie Sie beschreiben.

Das System, für das dies bewiesen ist, ist eine Teilmenge der Konstruktionsrechnung, die leistungsstarke Produkttypen und ein Universum enthält. Ich vermute, dass dieses Ergebnis auf das System ausgedehnt werden kann, an dem Sie interessiert sind, je nachdem, was Sie haben.

Leider kenne ich die vollständige Antwort auf Ihre Frage nicht. Ich vermute, dass das Hinzufügen bestimmter Parametrizitätsprinzipien "intern" genau das ist, was erforderlich ist, damit diese Codierungen mit dem vollständigen Induktionsprinzip funktionieren. Neel Krishnaswami, dessen Wissen eine strenge Obermenge meiner eigenen ist, schrieb mit Derek Dreyer ein Papier in dieser Richtung:

Internalisierung der relationalen Parametrizität in der Erweiterungsrechnung von Konstruktionen

Interessant ist auch das folgende Papier von Bernardy, Jansson und Patterson (Bernardy hat sich intensiv mit diesen Themen beschäftigt):

Parametrizität und abhängige Typen

Offensichtlich hat Parametrizität eine starke Beziehung zu HoTT im Allgemeinen, aber ich weiß nicht, was die Details sind. Ich denke, Steve Awodey hat diese Fragen berücksichtigt, da der Codierungstrick in Kontexten nützlich ist, in denen wir nicht wirklich wissen, wie die Eliminatoren aussehen sollen.

Cody
quelle

Um Ihre Idee zum Laufen zu bringen, benötigen Sie etwas Besonderes, wie in der Antwort von @ cody hervorgehoben. Sam Speight arbeitete unter der Aufsicht von Steve Awodey, um herauszufinden, was in HoTT mithilfe eines improvisierten Universums erreicht werden kann (siehe Impredikative Codierungen induktiver Typen im HoTT- Blogbeitrag).

Andrej Bauer
quelle