Ist die Pfadinduktion konstruktiv?

17

Ich lese das HoTT-Buch und habe es schwer mit der Pfadeinführung.

Wenn ich mir den Typ in Abschnitt 1.12.1 anschaue : ich habe kein Problem zu verstehen, was das bedeutet (ich habe nur den Typ aus dem Speicher geschrieben, um das zu überprüfen).

{ind}_{=_{A}} : \prod_{C : \prod_{x, y : A} (x =_{A} y) \to U} ((\prod_{x : A} C (x, x, {refl}_{x})) \to \prod_{x, y : A} \prod_{p : x =_{A} y} C (x, y, p)),

$\text{ind}_{=_A}:\prod_{C:\prod\limits_{x,y:A}(x=_Ay)\to \mathcal{U}} \left( \left(\prod_{x:A}C(x,x,\text{refl}_x)\right) \to \prod_{x,y:A}\prod_{p:x=_Ay} C(x,y,p) \right),$

Ich habe Probleme mit der nächsten Anweisung: der erste Eindruck war , dass dieser letzte Ausdruck nicht definieren , die resultierende Funktion aber gerade erklärt seine Eigentum .

with the equality {ind}_{=_{A}} (C, c, x, x, {refl}_{x}) :\equiv c (x)

$\text{with the equality}\quad \text{ind}_{=_A}(C,c,x,x,\text{refl}_x):\equiv c(x)$

f : \prod_{x, y : A} \prod_{p : x =_{A} y} C (x, y, p),

$f:\prod_{x,y:A}\prod_{p:x=_Ay} C(x,y,p),$

Dies steht im Gegensatz zu früheren Beispielen der Induktionsprinzipien , oder - dort sind Definitionsgleichungen für diese Elemente - wir tatsächlich wissen , wie die sich ergebende Funktion, die Räumlichkeiten gegeben zu konstruieren. Das stimmt mit der "Konstruktivität" der Typentheorie überein, auf die im gesamten Kapitel hingewiesen wird. $\text{ind}_{A\times B}$ $\text{ind}_{A+B}$ $\text{ind}_\mathbb{N}$

Als ich zurück zu $\text{ind}_{=_A}$ , war ich misstrauisch darüber, dass (wie es aussieht) es nicht definiert ist. Die Aussage, dass das Element $f$ nur existiert, schien mit dem Rest des Kapitels nicht übereinzustimmen . In der Tat scheint der Abschnitt 1.12.1 zu betonen, dass mein Eindruck falsch ist und wir ihn tatsächlich definiert haben

... die Funktion $f:\prod_{x,y:A}\prod_{p:x=_Ay} C(x,y,p),$ definiert durch
von $c:\prod_{x:A}C(x,x,\text{refl}_x)$ , die darüber hinaus
erfüllt $f(x,x,\text{refl}_x):\equiv c(x)$ ...

Das verwirrt mich zutiefst, aber ich habe das Gefühl, dass dieser Punkt für alle weiteren Entwicklungen sehr wichtig ist. Also, mit welcher der beiden Lesungen für soll ich gehen? Oder fehlt mir wahrscheinlich eine wichtige Subtilität und die Antwort lautet "beides"? $\text{ind}_{=_A}$

induction dependent-types homotopy-type-theory Kostya
quelle

Übrigens handelt es sich nicht wirklich um eine HoTT-spezifische Frage, sondern um eine allgemeinere Frage nach "abhängigen Typen".

Cody

12

Es ist eine Illusion, dass die Berechnungsregeln die Objekte, über die sie sprechen, "definieren" oder "konstruieren". Sie haben richtig festgestellt, dass die Gleichung für sie nicht "definiert", aber nicht beachtet, dass dies auch in anderen Fällen der Fall ist. Betrachten wir das Induktionsprinzip für den Einheitentyp , der besonders offensichtlich "bestimmt" zu sein scheint. Gemäß Abschnitt 1.5 des HoTT-Buches haben wir mit die Gleichung Ist dies "definieren" oder "konstruieren" in dem Sinne, dass es keinen Zweifel darüber lässt, was "tut"? Zum Beispiel gesetzt $\mathrm{ind}_{=_A}$ $1$

{i n d}_{1} : \prod_{C : 1 \to T y p e} C (⋆) \to \prod_{x : 1} P (x)

$\mathrm{ind}_1 : \prod_{C : 1 \to \mathtt{Type}} C(\star) \to \prod_{x : 1} P(x)$

{i n d}_{1} (C, c, ⋆) = c .

$\mathrm{ind}_1 (C, c, \star) = c.$

{i n d}_{1}

$\mathrm{ind}_1$

{i n d}_{1}

$\mathrm{ind}_1$

C (x) = N

$C(x) = \mathbb{N}$ und , und überlegen Sie, was wir zu für einen gegebenen Ausdruck vom Typ sagen könnten . Ihr erster Gedanke könnte sein, dass wir dies auf reduzieren können, weil " das einzige Element von ". Um genau zu sein, gilt die Gleichung für nur, wenn wir , was zum Beispiel unmöglich ist, wenn eine Variable ist. Wir können versuchen, daraus herauszukommen und sagen, dass wir nur an Berechnungen mit geschlossenen Begriffen interessiert sind, daher sollte geschlossen sein.

a = 42

$a = 42$

{i n d}_{1} (C, 42, e)

$\mathrm{ind}_1(C, 42, e)$

e

$e$

1

$1$

42

$42$

⋆

$\star$

1

$1$

{i n d}_{1}

$\mathrm{ind}_1$

e \equiv ⋆

$e \equiv \star$

e

$e$

e

$e$

Ist es nicht so, dass jeder geschlossene Term vom Typ urteilsmäßig gleich ? Das hängt eigentlich von fiesen Details und komplizierten Normalisierungsnachweisen ab. Im Fall von HoTT lautet die Antwort "nein", da Instanzen des Univalence Axiom enthalten könnte und es nicht klar ist, was dagegen zu tun ist (dies ist das offene Problem in HoTT). $e$ $1$ $\star$ $e$

Wir können die Probleme mit univalance umgehen , indem sie eine Version von Typ - Theorie unter Berücksichtigung der tut so gute Eigenschaften haben , dass jede geschlossene Laufzeit von Typ ist zu judgmentally gleich . In diesem Fall kann man sagen, dass wir wissen , wie man mit berechnet , aber: $1$ $\star$ $\mathrm{ind}_1$

Dasselbe hält für den Identitätstyp, weil jede geschlossene Laufzeit eines Identitätstyp judgmentally gleich sein wird , bis zu einem gewissen , und so dann die Gleichung für wird sagen uns wie man berechnet. $\mathrm{refl}(a)$ $\mathrm{ind}_{=_A}$
Nur weil wir wissen, wie man mit geschlossenen Begriffen eines Typs rechnet, heißt das nicht, dass wir tatsächlich etwas definiert haben, weil ein Typ mehr als seine geschlossenen Begriffe enthält , wie ich einmal zu erklären versucht habe.

Geben Sie beispielsweise Theorie Martin-Löf (ohne die Identität Typen) kann in einer solchen Art und Weise interpretiert domänen theoretisch sein , dass enthält zwei Elemente und , wo entspricht und an nicht-Terminierung. kann nicht benannt werden , da es in der Typentheorie keine Möglichkeit gibt, einen nicht terminierenden Ausdruck aufzuschreiben . Folglich ist die Gleichung für hat nicht uns sagen , wie auf berechnen (die beide offensichtliche Wahl „eifrig“ und „träge“ zu sein). $1$ $\bot$ $\top$ $\top$ $\star$ $\bot$ $\bot$ $\mathrm{ind}_1$ $\bot$

In Bezug auf die Softwareentwicklung würde ich sagen, dass wir eine Verwechslung zwischen Spezifikation und Implementierung haben . Die HoTT-Axiome für die Identitätstypen sind eine Spezifikation . Die Gleichung sagt uns nicht, wie man mit berechnet oder wie man konstruiert , aber stattdessen, dass "implementiert" ist, benötigen wir, dass es die Gleichung erfüllt. Es ist eine andere Frage, ob ein solches auf konstruktive Weise erhalten werden kann. $\mathrm{ind}_{=_C}(C,c,x,x,\mathrm{refl}(x)) \equiv c(x)$ $\mathrm{ind}_{=_C}$ $\mathrm{ind}_{=_C}$ $\mathrm{ind}_{=_C}$

Schließlich bin ich ein bisschen müde, wie Sie das Wort "konstruktiv" verwenden. Es sieht so aus, als ob Sie denken, dass "konstruktiv" dasselbe ist wie "definiert". Nach dieser Interpretation ist das Halting-Orakel konstruktiv, da sein Verhalten durch die Anforderung definiert wird, die wir ihm auferlegen (nämlich, dass es 1 oder 0 ausgibt, je nachdem, ob die gegebene Maschine anhält). Es ist durchaus möglich, Objekte zu beschreiben, die nur in einer nicht konstruktiven Umgebung existieren. Umgekehrt ist es durchaus möglich, konstruktiv über Eigenschaften und andere Dinge zu sprechen, die eigentlich nicht berechnet werden können. Hier ist eine: Die Beziehung definiert durch $H \subseteq \mathbb{N} \times \{0,1\}$

H (n, d) ⟺ (d = 1 \Rightarrow n -th machine halts) \land (d = 0 \Rightarrow n -th machine diverges)

$H(n,d) \iff (d = 1 \Rightarrow \text{$n$-th machine halts}) \land (d = 0 \Rightarrow \text{$n$-th machine diverges})$ ist konstruktiv, dh aus konstruktiver Sicht ist an dieser Definition nichts auszusetzen. Es kommt einfach so vor, dass man konstruktiv nicht nachweisen kann, dass eine totale Beziehung ist, und seine charakteristische Abbildung berücksichtigt , daher können wir seine Werte nicht "berechnen".

H

$H$

χ_{H} : N \times {0, 1} \to P r o p

$\chi_H : \mathbb{N} \times \{0,1\} \to \mathsf{Prop}$

b o o l

$\mathtt{bool}$

Nachtrag: Der Titel Ihrer Frage lautet "Ist die Pfadinduktion konstruktiv?" Nachdem wir den Unterschied zwischen "konstruktiv" und "definiert" geklärt haben, können wir die Frage beantworten. Ja, die Pfadinduktion ist in bestimmten Fällen als konstruktiv bekannt:

Wenn wir uns auf die Typentheorie ohne Univalenz beschränken, damit wir eine starke Normalisierung zeigen können, dann ist die Pfadinduktion und alles andere konstruktiv, da es Algorithmen gibt, die das Normalisierungsverfahren durchführen.
Es gibt Realisierbarkeitsmodelle der Typentheorie, die erklären, wie jeder geschlossene Term in der Typentheorie einer Turingmaschine entspricht. Diese Modelle erfüllen jedoch Streichers Axiom K, das die Univalenz ausschließt.
Es gibt eine Übersetzung der Typentheorie (wieder ohne Univalenz) in die konstruktive Mengenlehre CZF. Dies bestätigt erneut Streichers Axiom K.
Innerhalb von Realisierbarkeitsmodellen gibt es ein Gruppenmodell, mit dem wir die Typentheorie ohne Streichers K interpretieren können . Dies ist eine Vorarbeit von Steve Awodey und mir.

Wir müssen wirklich den konstruktiven Status der Univalenz klären.

Andrej Bauer
quelle

Ich glaube, diese Antwort ist (teilweise) veraltet

WorldSEnder

Tatsächlich gab die kubische Typentheorie in der Zwischenzeit eine positive Antwort: Es gibt ein konstruktives Modell der Theorie des einwertigen Typs.

Andrej Bauer

7

Ich bin keine HoTT-Person, aber ich werfe meine zwei Cent ein.

Angenommen, wir möchten eine Funktion Wie würden wir das tun? Nehmen wir an, wir bekommen ein und einen Beweis für ihre Gleichheit . Da ich nichts über den beliebigen Typ weiß, weiß ich nichts über die Struktur von . Ich weiß jedoch etwas über den spezifischen Gleichheitstyp: Er hat einen einzelnen Konstruktor, Daher für ein , aber dies würde erzwingen . Wenn wir also ein Element von für ein beliebiges

f_{A} : \prod_{x, y : A} \prod_{p : x =_{A} y} C (x, y, p)

$f_A : \prod_{x,y : A}\prod_{p : x =_A y} C(x,y,p)$

x, y : A

$x,y : A$

p : x =_{A} y

$p : x =_A y$

A

$A$

x, y

$x,y$

{r e f l}_{a} : a =_{A} a, for any a : A

$\mathsf{refl}_a : a =_A a, \text{ for any } a : A$

p \equiv {r e f l}_{a}

$p \equiv \mathsf{refl}_a$

a : A

$a : A$

x = a = y

$x=a=y$

C (x, x, {r e f l}_{x})

$C(x,x,\mathsf{refl}_x)$

x : A

$x : A$ ; dh wenn wir eine Funktion (für unser spezifisches ), dann kann unsere Funktion wie folgt definiert werden: .

b a s e_{C} : \prod_{x : A} C (x, x, {r e f l}_{x})

$base_C : \prod_{x:A}C(x,x,\mathsf{refl}_x)$

C

$C$

f_{A}

$f_A$

f_{A} (x, y, p) := b a s e_{C} (x, x, p)

$f_A(x,y,p) := base_C(x,x,p)$

Das Entfernen der Indizes führt zur allgemeinen induktiven Definition.

Ich hoffe, das hilft!

PS. Ich bin kein HoTT-Typ, also gehe ich von Axiom K aus. Genauer gesagt gehe ich davon aus, dass ein Element vom Typ das Ergebnis wiederholter Anwendungen des Konstruktors von . Soviel ich weiß, wirft HoTT, wahrscheinlich ab Kapitel 2, diesen Gedanken weg ... und das ergibt für mich absolut keinen Sinn. $e$ $E$ $E$

Musa Al-hassy
quelle

1

Vielleicht können Sie etwas Sinnvolles daraus machen oder sich zumindest Sorgen über Ihre aktuellen Intuitionen machen, indem Sie die Elemente eines induktiven Typs untersuchen, in denen ich zu erklären versuche, warum Es ist schädlich zu glauben, dass die geschlossenen Begriffe eines Typs alles sind, was es für einen Typ gibt.

Andrej Bauer

2

Übrigens brauchen Sie Axiom K nicht anzunehmen. Damit Ihre Antwort einen Sinn ergibt, müssen Sie wissen, dass sich jeder geschlossene Begriff eines Identitätstyps zu normalisiert . Dies hat nichts mit Axiom K zu tun, da eine solche Normalisierungseigenschaft weder Axiom K beweist noch aus Axiom K folgt.

r e f l

$\mathsf{refl}$

Andrej Bauer

3

Ich bin ein Amateur- Typ von HoTT, also werde ich versuchen, Moses 'bereits großartige Antwort zu ergänzen. Lassen Sie mich als Beispiel den Typ . Das von Martin-Löf skizzierte Grundprinzip der konstruktiven Typentheorie ist, dass * jedes Element von als im Bild des Konstruktors beschrieben wird: dieser Philosophie erlaubt uns zu definieren Eliminierung : eine Funktion aufzubauen out der genügt es , seine Wirkung auf dem beschreiben Bild . $A\times B$ $A\times B$

p a i r : A \to B \to A \times B

$\mathrm{pair}\ :\ A\rightarrow B\rightarrow A\times B$

f

$f$

A \times B

$A\times B$ $\mathrm{pair}$

Aber da ein Konstruktor ist (und insbesondere injektiv), bedeutet dies genau, dass es ausreicht, um eine Funktion zu erstellen , die Aktion auf ein Elementpaar in und , also reicht aus, um ein solches zu beschreiben . Zusammenfassend kann gesagt werden, dass es eine kanonische Möglichkeit gibt, Funktionen außerhalb von zu definieren , und dies kann in den Typ eingekapselt werden, aber genau dies ist der Fall die Art von . $\mathrm{pair}$ $f:A\times B\rightarrow C$ $A$ $B$

f^{'} : A \to B \to C

$f':A\rightarrow B\rightarrow C$

f

$f$

A \times B

$A\times B$

(A \to B \to C) \to (A \times B \to C)

$(A\rightarrow B\rightarrow C)\rightarrow(A\times B\rightarrow C)$

{i n d}_{A \times B}

$\mathrm{ind}_{A\times B}$

Dies ist jedoch nur die halbe Wahrheit: Was passiert, wenn dieses neu konstruierte auf ein gegebenes angewendet wird ? Nun, dann sollte mit seiner Definitionsfunktion übereinstimmen , dh dh und dies sollte definitiv (oder rechnerisch ) gelten, was bedeutet, dass die beiden in allen Situationen vollständig austauschbar sein sollten (was sich stark unterscheidet von das in HoTT). $f$ $\mathrm{pair}(a,b)$ $f$ $f'$

f (p a i r (a, b)) := f^{'} a b

$f(\mathrm{pair}(a,b))\ :=\ f'\ a\ b$

{i n d}_{A \times B} f^{'} p a i r (a, b) := f^{'} a b

$\mathrm{ind}_{A\times B}\ f'\ \mathrm{pair}(a,b)\ :=\ f'\ a\ b$

=

$=$

Sie sehen also, dass die Definition eines Eliminators für induktiven Typ mit gegebenen Konstruktoren in zwei Schritten erfolgt:

ein Existenzprinzip , das den Typ von . $\mathrm{ind}$
ein Kohärenzprinzip, das das Rechenverhalten von . In der Kategorietheorie würde dies in gewissem Sinne der Eindeutigkeit des Eliminators entsprechen . $\mathrm{ind}$

Lassen Sie mich argumentieren, dass dies auch für den Typ . Wir wollen mit und ein Element von (wir vergessen die Abhängigkeiten zur Vereinfachung). Dazu müssen wir annehmen, dass mit einem Konstruktor für den Typ , der für einige nur . Das heißt, um eine Funktion zu geben, genügt es, eine Funktion die für (wieder die Abhängigkeiten in vergessen ). $=_A$ $x,y:A$ $p:x=y$ $C$ $p$ $x=y$ $\mathrm{refl}(z)$ $z$

f : Π x, y : A, x = y \to C

$f:\Pi x, y:A, x=y\rightarrow C$

f^{'} : Π z : A, C

$f':\Pi z:A, C$

r e f l (z)

$\mathrm{refl}(z)$

C

$C$

Was sagt nun das Kohärenzprinzip aus? Nun einfach, wenn auf einen bekannten Konstruktor angewendet wird, sollte es sich wie verhalten , was $f$ $f'$

f z z r e f l (z) := f^{'} z

$f\ z\ z\ \mathrm{refl}(z):= f'\ z$

Aber genau das haben Sie oben! Das gleiche Prinzip, das uns die Existenz und Kohärenz für den Eliminator von gibt uns die Existenz und Kohärenz für den Eliminator von . $A\times B$ $=_A$

Cody
quelle

Ist die Pfadinduktion konstruktiv?

Antworten: