Welche Teile der Homotopietypentheorie sind in Agda oder Coq nicht möglich?

16

Wenn wir uns das Buch Homotopy Type Theory ansehen , sehen wir die folgenden Themen:

Homotopy type theory 
2.1 Types are higher groupoids
2.2 Functions are functors
2.3 Type families are fibrations
2.4 Homotopies and equivalences
2.5 The higher groupoid structure of type formers
2.6 Cartesian product types
2.7 S-types
2.8 The unit type
2.9 P-types and the function extensionality axiom
2.10 Universes and the univalence axiom
2.11 Identity type
2.12 Coproducts
2.13 Natural numbers
2.14 Example: equality of structures
2.15 Universal properties

Jetzt wissen wir, dass nicht alle Homotopietheorien möglich sind: Agda und Coq .

Meine Frage ist: Welche Teile der Homotopietypentheorie sind in Agda oder Coq nicht möglich?

type-systems Falkenauge
quelle
4
Keine besonders gut formulierte Frage. Welche Beziehung besteht zwischen der Themenliste und der Frage?
Dave Clarke
@ Dave Clarke, Die Themenliste sieht aus wie der Kontext des Geistes des Fragestellers, sodass der Beantworter den Ausgangspunkt des Fragestellers kennt und die Antwort entsprechend anpassen kann. Andere Lernende können die Antwort im selben Kontext auch schätzen und verstehen, dass die Antwort für sie wahrscheinlich nützlich ist, wenn der Antwortende nachdenklich und weise in Bezug auf die menschliche Natur ist. Hoffe das hilft auch bei weiteren zukünftigen Gesprächen.
Codeshot

Antworten:

21

Wenn man sich anschaut , Hinweise zu Kapitel 8 Sie werden sehen , was hat bereits formalisiert, und ich denke , dass eine Menge ist. Es gibt die Coq HoTT-Bibliothek und die Agda HoTT-Agda- Bibliothek, die große Teile der Homotopy Type Theory formalisieren.

Um die Dinge in Coq zu erledigen, benötigten wir eine spezielle Version von Coq, die nur für die Zwecke von HoTT gepatcht wurde. Da sich Coq jedoch in Richtung der Unterstützung der Homotopietypentheorie bewegt, können wir dies möglicherweise in Kürze mit Standard-Coq tun.

In Agda muss man die --without-KOption einschalten , sonst glaubt Agda, dass alle Typen 0-Typen sind. Es gibt einige anhaltende Zweifel, ob --without-Kdie Annahme, dass alles eine 0-Menge ist, wirklich beseitigt wird, oder ob man sie mit kniffligen Verwendungszwecken von Musterübereinstimmungen wieder in Agda einführen könnte.

Die folgenden Aspekte von Coq- und Agda-Formalisierungen sind nicht zufriedenstellend:

  1. Das Univalenz-Axiom wird als Hypothese angegeben. Es wäre besser, wenn es in das System eingebaut wäre. Insbesondere möchten wir, dass Coq und Agda die Berechnungsregeln für das Axiom der Univalenz verstehen.

  2. Ebenso müssen wir Hacks verwenden, um funktionsfähige Typen mit höherer Induktivität zu erhalten. Auch hier wäre es besser, direkte Unterstützung zu haben.

Das Problem mit den oben genannten Mängeln ist, dass niemand weiß, wie man sie sogar theoretisch behebt. Dies ist ein aktives Forschungsgebiet.

Abgesehen davon kann man sagen, dass HoTT meistens in Coq und Agda durchgeführt werden kann, aber nicht optimal.

Andrej Bauer
quelle
1
Danke, gibt es eine gute Beschreibung, warum Univalenz und höherinduktive Typen nicht gut mit Typentheorien wie Agda und Coq zusammenpassen?
Martin Berger
1
@MartinBerger Dies könnte wahrscheinlich eine separate Frage sein (mit einigen Definitionen für gelegentlichere Leser usw.).
Artem Kaznatcheev
4
Das Problem mit Univalenz und HITs ist nicht, dass sie "nicht gut zu Typentheorien wie Agda und Coq passen", sondern dass "wir nicht wissen, wie man sie in irgendeiner Typentheorie richtig macht ".
Andrej Bauer
1
@AndrejBauer Univalenz und höherinduktive Typen werden in der HoTT-Beschreibung formuliert, die eine (semi-formale) Typentheorie ist. Was ist der fehlende Bestandteil, der eine ordnungsgemäße Formalisierung in Agda / Coq verhindert? Wenn Sie bereit sind, Curry-Howard aufzugeben, gibt es dann Schwierigkeiten, Univalenz und höherinduktive Typen in einem LCF-ähnlichen Beweiser wie Isabelle zu formulieren, indem Sie zB LF als Metasprache verwenden, um Beweisregeln zu formalisieren?
Martin Berger
4
Was sind die Berechnungsregeln für uadie Konstante, die das Axiom der Univalenz bezeugt? Was sind die Berechnungsregeln für HITs? Wir haben einige Ideen, aber nichts wasserdichtes.
Andrej Bauer
12

Soweit ich weiß, ist es in Agda möglich, all das zu repräsentieren (dh in Kapitel 2 - es gibt eine Bibliothek auf Github, die dies tut; AFAIK, dasselbe gilt für Coq). Nur wenn Sie zu späteren Kapiteln kommen, wird es schwierig. Es gibt zwei offensichtliche Punkte:

  1. Der Kreis. Dies wird (in Agda) mit einem Postulat dargestellt und ist daher nicht so schön wie andere Dinge.
  2. ∞

Es gibt auch andere Elemente, aber ich habe diesen Teil der Agda-Formalisierung noch nicht gelesen ... Aber im Großen und Ganzen kann der größte Teil von HoTT sowohl in Agda als auch in Coq gut formalisiert werden.

Noch wichtiger ist, dass beide Entwicklerteams aktiv daran arbeiten, ihre Systeme so anzupassen, dass mehr von HoTT gehandhabt werden kann, zumindest wenn eine klare Theorie vorliegt, wie die erforderlichen Funktionen implementiert werden können. Das hat sich in Teilen als herausfordernd erwiesen.

Jacques Carette
quelle