Sind im Hott-Buch die meisten Schriftbildner überflüssig? Und wenn ja, warum?

In Kapitel 1 und Anhang A des Hott-Buches werden mehrere primitive Typenfamilien vorgestellt (Universumstypen, abhängige Funktionstypen, abhängige Paartypen, Coproduct-Typen, Leertyp, Einheitentyp, Typ der natürlichen Zahl und Identitätstypen), um die Grundlage zu bilden für die Homotopietypentheorie.

Es scheint jedoch, dass Sie bei gegebenen Universumstypen und abhängigen Funktionstypen alle diese anderen "primitiven" Typen konstruieren können. Beispielsweise könnte der leere Typ stattdessen als definiert werden

ΠT:U.T

Ich gehe davon aus, dass die anderen Typen auch ähnlich aufgebaut sein könnten, wie sie in reinem CC vorliegen (dh leiten Sie den Typ einfach aus dem induktiven Teil der Definition ab).

Viele dieser Typen werden durch die Induktiv / W-Typen, die in den Kapiteln 5 und 6 vorgestellt werden, explizit überflüssig. Induktiv / W-Typen scheinen jedoch ein optionaler Teil der Theorie zu sein, da offene Fragen zur Interaktion mit HoTT (at Zumindest zu dem Zeitpunkt, als das Buch herauskam.

Daher bin ich sehr verwirrt darüber, warum diese zusätzlichen Typen als primitiv dargestellt werden. Meine Intuition ist, dass eine fundamentale Theorie so minimal wie möglich sein sollte und die Neudefinition eines redundanten Leertyps als Primitiv in der Theorie sehr willkürlich erscheint.

Wurde diese Wahl getroffen?

aus einigen metatheoretischen Gründen, die ich nicht kenne?
Aus historischen Gründen, um die Typentheorie wie frühere Typentheorien aussehen zu lassen (die nicht unbedingt versucht haben, grundlegend zu sein)?
für "Usability" von Computerschnittstellen?
für einen Vorteil bei der Beweissuche, den ich nicht kenne?

Ähnlich wie: Minimale Spezifikation der Martin-Löf-Typentheorie , /cs/82810/reducing-products-in-hott-to-church-scott-encodings/82891#82891

type-theory dependent-type homotopy-type-theory user833970
quelle

Sie sind überflüssig, aber nicht so, wie Sie es vorschlagen. Sie sollten sich fragen, welchen Zweck die "Minimalität der Grundlage" erfüllt. Und interessiert uns der Zweck?

Andrej Bauer

Ich gehe davon aus, dass der technische Aufwand konventionell minimal ist und die Dinge nicht minimal sein müssen, wenn dies offensichtlich zweckmäßig ist oder ausdrücklich anders vermerkt ist. Das Buch hält sich auch an andere Stellen, etwa wenn es Kürzungsarten definiert (durch Regeln definiert, aber ausdrücklich nicht minimal). Wenn ich zum Beispiel die in Bezug auf 0,1,10, den Nachfolger und die Kraftoperation definierten Nats sehen würde, wäre ich verwirrt, aber ich könnte zumindest sehen, warum dies notational zweckmäßig ist. Hott ist ein viel komplexerer Studienbereich und ich möchte wissen, ob mir etwas Offensichtliches fehlt.

user833970

Ich wäre sehr daran interessiert zu erfahren, wie schädlich sie sein können. Sollte ich eine neue Frage dazu stellen?

user833970

@AndrejBauer Ich würde gerne wissen, warum sie auch schädlich sind. Meine Überlegung, dass die Grundsprache minimal sein sollte, ist die Überlegung hinter Occams Rasiermesser, es ist ungerechtfertigte zusätzliche Komplexität. Warum dort aufhören? Warum nicht auch Listen, Strings, Paare, Tripel, Vektoren hinzufügen? Das scheint willkürliche Entscheidungen, was rechtfertigt sie? Bearbeiten: Ich habe gerade bemerkt, dass diese Frage Antworten hat; aber ich werde diesen Kommentar hier lassen, nur um festzustellen, warum ich auch daran interessiert bin.

MaiaVictor

Ich werde einen Blog-Beitrag schreiben.

Andrej Bauer

Antworten:

Lassen Sie mich erklären, warum die vorgeschlagene Kodierung des leeren Typs nicht funktioniert. Wir müssen die Ebenen des Universums genau kennen und dürfen sie nicht unter den Teppich kehren.

Wenn Leute "den leeren Typ" sagen, können sie eines von zwei Dingen bedeuten:

Ein einzelner Typ der in Bezug auf alle Typen leer ist. Eine solche Art hat die Eliminationsregel: für jeden und Typenfamilie , gibt es eine Karte . $E$ $n$ $A : E \to U_n$ $e_{n,A} : E \to A$
Eine Familie von Typen , einem für jede Universum Ebene , derart , dass „der leere Typ ist “. Eine solche Art hat gerecht zu werden , natürlich, und auch: für jede Familie gibt es eine Karte . $E_k$ $k$ $E_k$ $U_k$ $E_k : U_k$ $A : E_{k} \to U_k$ $e_{k,A} : E_{k} \to A$

Ohne Vorbehalte erwarten die Leute, wenn sie "leere Schrift" sagen, die erste obige Bedeutung.

Wie können wir bekommen ? Ein erster Versuch könnte so etwas wie $E$ aber das ist genau die Art unter dem Teppich zu fegendie Verwirrung schafft. Wir müssen explizite Universumsebenen aufschreiben. Wenn wir so etwas wie schreiben

E = Π (T : U) . T

$E = \Pi (T : U) \,.\, T$

dann erhalten wir eine Folge von Typen

, eine für jede Ebene

. Wir könnten hoffendass diese Sequenz der leere Typ ist in dem Sinneoben, aber es ist nicht, weil

in ist

, aber es sollte in seine

E_{k} = Π (T : U_{k}) . T

$E_k = \Pi (T : U_k) \,.\, T$

E_{0}, E_{1}, E_{2}, \dots

$E_0, E_1, E_2, \ldots$

k

$k$

E_{k}

$E_k$

U_{k + 1}

$U_{k+1}$

U_{k}

$U_k$

Ein weiterer Versuch ist

E = Π n . Π (T : U_{n}) . T

$E = \Pi n \,.\,\Pi (T : U_{n}) \,.\, T$

Π n

$\Pi n$

L

$L$

E = Π (n : L) . Π (T : U_{n}) . T

$E = \Pi (n : L) \,.\,\Pi (T : U_{n}) \,.\, T$

E

$E$

L

$L$

$U$ $B : U \to U$ $\Pi (X : U) B(X)$ $U$ $U$ $\Pi (X : U) X$ $U$

Verbesserungsuniversen können arrangiert werden. Ein berühmter Satz von Thierry Coquand (wenn ich mich nicht irre) zeigt jedoch, dass es zu einem Widerspruch führt , wenn zwei prägnante Universen in einem anderen enthalten sind.

Die Moral der Geschichte lautet: Axiomatisieren Sie einfach den leeren Typ direkt und hören Sie auf, Dinge zu kodieren.

Andrej Bauer
quelle

Das ist eine überzeugende Argumentation, um den leeren Typ zu axiomatisieren, aber ich bin immer noch neugierig auf die Argumentation, um all diese schwereren Dinge zu axiomatisieren.

MaiaVictor

@MaiaVictor: Im Gegensatz zu was?

Andrej Bauer

Es tut uns leid? Ich meine nur, Sie haben überzeugend begründet, warum es eine gute Idee ist, insbesondere den leeren Typ zu axiomatisieren. Aber OP fragte auch nach anderen Dingen: "Universumstypen, abhängige Funktionstypen, abhängige Paartypen, Koprodukttypen, Leertyp, Einheitentyp, Typ der natürlichen Zahl und Identitätstypen" (von denen ich annehme, dass sie auch Grundelemente des auf der Website vorgeschlagenen Systems sind) HoTT-Buch). (Ich bitte Sie natürlich nicht, diese alle zu rechtfertigen,

sondern

1 = \prod_{X : U} (X \to X)

$\mathbb{1} = \prod_{X : U} (X \to X)$

@IngoBlechschmidt gespannt auf welche Probleme! Es sieht gut aus für mich ...

MaiaVictor

Sie stellen mehrere Fragen, die ähnlich, aber unterschiedlich sind.

Warum verwendet das HoTT-Buch keine Church-Codierungen für Datentypen?

Kirchenkodierungen funktionieren aus zwei Gründen nicht in der Martin-Löf-Typentheorie.

$n$ $k < n$

Zweitens, auch wenn Sie Datentypen wie die natürlichen Zahlen mit Church-Codierungen definiert haben, benötigen Sie Induktionsprinzipien , um Beweise für diese Typen zu erstellen. Um Induktionsprinzipien für Kirchenkodierungen abzuleiten, müssen Sie ein Argument verwenden, das auf Reynolds 'Parametrizität basiert, und die Frage, wie Parametrizitätsprinzipien in die Typentheorie integriert werden können, ist noch nicht vollständig geklärt. (Der Stand der Technik ist Nuyts, Vezzosi und Devriese des ICFP 2017 Papier Parametric Quantifizierer für Dependent Type Theory - beachten Sie, dass dies auch nach ! Der HoTT Buch geschrieben wurde)
Als nächstes fragen Sie, warum das Fundament nicht minimal ist. Tatsächlich ist dies eines der charakteristischen soziologischen Merkmale typentheoretischer Grundlagen - Typentheoretiker betrachten das Vorhandensein kleiner Regeln als technische Annehmlichkeit ohne große grundsätzliche Bedeutung. Es ist viel wichtiger, die richtigen Regeln zu haben, als die kleinsten .

Wir entwickeln Typ Theorien werden verwendet , von Mathematikern und Programmierern, und es ist sehr, sehr wichtig , dass die Beweise innerhalb Typentheorie geschehen sind diejenigen , die Mathematiker und Programmierer betrachten wie in der richtigen Weise getan. Dies liegt daran, dass die Argumente, die Mathematiker normalerweise für einen guten Stil halten, unter Verwendung der wichtigsten algebraischen und geometrischen Prinzipien des Studienbereichs strukturiert werden. Wenn Sie komplizierte Codierungen verwenden müssen, geht viel Struktur verloren oder wird verdeckt.

Dies ist der Grund, warum selbst typentheoretische Darstellungen der klassischen Aussagenlogik immer alle logischen Verknüpfungen ergeben, obwohl sie formal einer Logik mit nur NAND äquivalent sind. Sicher, alle Booleschen Konnektiven können mit NAND codiert werden, aber diese Codierung verdeckt die Struktur der Logik.

Neel Krishnaswami
quelle

Danke für diese Antwort! Ich werde diese (und deine) Zeitung lesen müssen, und es könnte sinnvoller sein. Aber ich dachte, dass die Universumshierarchie so gestaltet ist, dass sie aussieht, als könnten Sie prädikative Dinge tun: Zum Beispiel würde (λA: U.λa: Aa) (ΠA: UA → A) (λA: Un + 1.λa: Aa) (ΠA: Un.A → A). Ich halte es für eine seltsame redaktionelle Entscheidung, dies nicht zu erklären. In jedem mir bekannten Logikbuch werden mehrere weitere minimale Codierungen wie CNF, DNF, NAND usw. aufgeführt. Und jeder, der es gewohnt ist, die Theorie aufzustellen, erwartet eine "natürliche" Kodierung der Nats, um die Theorie zu demonstrieren. Aber das kann nur meine klassische Vorurteile sein.

user833970

das sollte in meinem letzten Kommentar "anregend" sein

user833970

\prod (T : U_{n}) . T

$\prod (T : U_n) . T$

U_{n}

$U_n$

U_{n + 1}

$U_{n+1}$

U_{n}

$U_n$

Vielleicht verstehe ich etwas über Universumshierarchien falsch. Ich dachte, dass es uns egal ist, in welchem bestimmten Universum sich ein Typ befindet, nur dass die Universumsnummern zugewiesen werden können, wenn wir einen Beweis überprüfen möchten. Technisch gesehen ist ΠT: UT eine Familie von Typen, die über Universen indiziert sind. Genau wie die polymorphe Identität ist eine Familie von Typen über Universen indiziert. Aber haben wir nicht das gleiche Problem mit der polymorphen Identität? Ich würde es wirklich begrüßen, wenn Sie die letzten beiden Sätze erweitern könnten, ich glaube nicht, dass ich das verstehe.

user833970

Wenn Sie sagen, dass es nicht die richtigen Eliminationseigenschaften hat, meinen Sie damit, dass es nach dem Festlegen des Universums Typen in höheren Universen gibt, die nicht direkt durch einen Ausdruck von ΠT: Un.T synthetisiert werden können?

User833970