"Minimale" intuitionistische Typentheorie?

Ich bin überrascht, dass immer wieder neue Typen in Typentheorien aufgenommen werden, aber niemand scheint eine Minimal-Theorie zu erwähnen (oder ich kann sie nicht finden). Ich dachte, Mathematiker lieben minimale Dinge, nicht wahr?

Wenn ich richtig verstehe, Propgenügen in einer Typentheorie mit einem Impredikativ λ-Abstraktion und Π-Typen. Mit "ausreichend" meine ich, dass es als intuitionistische Logik verwendet werden könnte. Andere Typen können wie folgt definiert werden:

⊥ \overset{d e f}{=} Π α : P r o p . α \neg A \overset{d e f}{=} A \to ⊥ A \land B \overset{d e f}{=} Π C : P r o p . (A \to B \to C) \to C A \lor B \overset{d e f}{=} Π C : P r o p . (A \to C) \to (B \to C) \to C \exists_{x : S} (P (x)) \overset{d e f}{=} Π α : P r o p . (Π x : S . P x \to α) \to α

$\bot \stackrel{def}{=} \Pi \alpha: Prop. \alpha \\ \neg A \stackrel{def}{=} A \to \bot \\ A \land B \stackrel{def}{=} \Pi C: Prop. (A \to B \to C) \to C \\ A \lor B \stackrel{def}{=} \Pi C: Prop. (A \to C) \to (B \to C) \to C \\ \exists_{x: S}(P(x)) \stackrel{def}{=} \Pi \alpha: Prop. (\Pi x: S. P x \to \alpha) \to \alpha \\$

Meine erste Frage ist, tun sie ( λ, Π) wirklich ausreichen? Meine zweite Frage ist, was brauchen wir minimal, wenn wir kein Impredicative haben Prop, wie in MLTT? In MLTT funktioniert die Codierung Church / Scott / whatever nicht.

Bearbeiten: verwandt

type-theory dependent-types 盛安安
quelle

Was wäre ein "minimaler" Typ? welche immobilien hätte es deiner meinung nach?

Raphael

In der Lage zu beweisen, was Coq beweisen kann? Ich gebe zu, ich habe keine klare Antwort im Kopf D:

盛安安

Aber ich habe gehört, dass Coq den Universumspolymorphismus hinzugefügt hat, für den das von mir vorgeschlagene Minimalsystem offensichtlich nicht funktioniert. Was ist mit "In der Lage zu sein zu beweisen, was MLTT (im normalen Sinne) beweisen kann."? Ich dachte, W-Typen können simuliert werden? Obwohl ich mich im Allgemeinen nicht darum gekümmert habe.

16.

Warten Sie, es scheint, dass Propwir mit improvisierten nicht einmal Gleichheit brauchen.

16.

Antworten:

Eine Typentheorie mit improvisiertem Prop und abhängigen Typen kann als ein Teilsystem der Konstruktionsrechnung angesehen werden, das typisch für die Typentheorie der Kirche ist . Die Beziehung zwischen der Typentheorie von Church und dem CoC ist nicht so einfach, wurde aber insbesondere von Geuvers hervorragendem Artikel untersucht .

In den meisten Fällen können die Systeme jedoch als gleichwertig angesehen werden. In der Tat kommt man mit sehr wenig aus, insbesondere wenn Sie sich nicht für klassische Logik interessieren, dann ist das einzige, was Sie wirklich brauchen, ein Axiom der Unendlichkeit : Es ist in CoC nicht nachweisbar, dass ein Typ mehr als ein Element hat! Aber mit nur einem Axiom, das ausdrückt, dass ein Typ unendlich ist, sagen wir, ein natürlicher Zahlentyp mit dem Induktionsprinzip und dem Axiom , können Sie ziemlich weit kommen: Die meisten Mathematikstudenten können in diesem System formalisiert werden (irgendwie ist es schwierig) einige Dinge ohne die ausgeschlossene Mitte zu tun). $0\neq 1$

Ohne Verbesserungsvorschlag brauchst du ein bisschen mehr Arbeit. Wie in den Kommentaren erwähnt, kann ein Extensionssystem (ein System mit funktionaler Extensionalität in der Gleichheitsrelation) mit nur und Typen, auskommen $\Sigma$ $\Pi$ , die leer und Einheitentypen und und W-Typen. In der Intensiveinstellung ist das nicht möglich: Sie benötigen viel mehr Induktivitäten. Beachtendass nützliche W-Typen zu bauen, Sie müssenLage seinTypen zu bauen durch Eliminierung über wie folgt: $\mathrm{Bool}$ $\bot$ $\top$ $\mathrm{Bool}$

i f b t h e n ⊤ e l s e ⊥

$\mathrm{if}\ b\ \mathrm{then}\ \top\ \mathrm{else}\ \bot$

Um Metamathematik zu machen, benötigen Sie wahrscheinlich mindestens ein Universum (zum Beispiel, um ein Modell der Heyting-Arithmetik zu erstellen).

$\Pi\Sigma$

Eine nützliche Übersicht ist der Artikel Ist ZF ein Hack? von Freek Wiedijk, der die harten Zahlen aller dieser Systeme (Anzahl der Regeln und Axiome) tatsächlich vergleicht.

Cody
quelle

Sind

Typen in ETT definierbar?

Σ

$\Sigma$

Nein, ich glaube, Sie müssen auch davon ausgehen. Mein Fehler.

Cody

Das Problem mit den Kodierungen in der Kirche ist, dass Sie keine Induktionsprinzipien für Ihre Typen erhalten können, was bedeutet, dass diese so gut wie unbrauchbar sind, um Aussagen darüber zu beweisen.

In Bezug auf die Minimalität des Systems wird in den Kommentaren als Pfad die Verwendung von Containern und (W / M) -Typen erwähnt. Diese sind jedoch eher erweiterungsfähig, sodass die Arbeit mit Systemen wie Coq oder Agda nicht sehr praktisch ist.

Ein praktikablerer Ansatz ist die Verwendung eines Polynomfunktors, der als Erweiterung einer Beschreibung und nicht als Erweiterung eines Containers definiert ist. Die Wirtstheorie muss nur unter , $\Pi$ $\Sigma$ $\mu$ $\nu$

Verschachtelte Fixpoints sind umständlicher, können aber behandelt werden. Ich habe keine vollständig ausgearbeitete Geschichte über alternierende geschrieben oder gesehen $\mu$ $\nu$

Gallais
quelle