Den Beweis einer starken Normalisierung der Konstruktionsrechnung verstehen

Ich habe Schwierigkeiten, den Beweis einer starken Normalisierung für die Konstruktionsrechnung zu verstehen. Ich versuche, dem Beweis in der Arbeit von Herman Geuvers zu folgen: "Ein kurzer und flexibler Beweis für eine starke Normalisierung für die Berechnung von Konstruktionen".

Ich kann der Hauptargumentation gut folgen. Geuvers konstruiert für jeden Typ eine Interpretation basierend auf einer Auswertung der Typvariablen . Und dann konstruiert er eine Terminterpretation basierend auf einer Bewertung von Termvariablen und beweist, dass für gültige Bewertungen die Behauptung für alle gilt. $T$ $[\![T]\!]_\xi$ $\xi(\alpha)$ $(\!|M|\!)_\rho$ $\rho(x)$ $(\!|M|\!)_\rho \in [\![T]\!]_\xi$ $\Gamma\vdash M:T$

Mein Problem: Für einfache Typen (wie System-F-Typen) ist die Typinterpretation wirklich eine Reihe von Begriffen, also die Behauptung macht Sinn. Bei komplexeren Typen ist die Interpretation jedoch keine Menge von Begriffen, sondern eine Menge von Funktionen eines geeigneten Funktionsraums. Ich denke, ich verstehe fast die Konstruktion der Funktionsräume, kann jedoch für die komplexeren keine Bedeutung zuweisen Typen . $[\![T]\!]_\xi$ $(\!|M|\!)_\rho \in [\![T]\!]_\xi$ $[\![T]\!]_\xi$ $(\!|M|\!)_\rho \in [\![T]\!]_\xi$ $T$

Kann jemand erklären oder Links zu verständlicheren Präsentationen des Beweises geben?

Bearbeiten: Lassen Sie mich versuchen, die Frage klarer zu machen. Ein Kontext enthält Deklarationen für Typvariablen und Objektvariablen. Eine Art Bewertungs gültig ist , wenn für alle mit dann ist gültig. Aber kann ein Element von und nicht nur . Daher kann für keine gültige Termbewertung definiert werden . muss ein Begriff sein und keine Funktion eines Funktionsraums. $\Gamma$ $\alpha:A$ $(\alpha:A) \in \Gamma$ $\Gamma\vdash A:\square$ $\xi(\alpha) \in \nu(A)$ $\nu(A)$ $(SAT)^*$ $SAT$ $\rho(\alpha)$ $\rho(\alpha)$

Edit 2: Beispiel, das nicht funktioniert

Nehmen wir die folgende gültige Ableitung vor:

\begin{array}{llll} []] & ⊢ & * :: ◻ & Axiom \\ [α :: *]] & ⊢ & α :: * & variable Einführung \\ [α :: *]] & ⊢ & * :: ◻ & schwächen \\ []] & ⊢ & (Π α :: * . *) :: ◻ & Produktbildung \\ [β :: Π α :: * . *]] & ⊢ & β :: (Π α :: * . *) & variable Einführung \end{array}

$\begin{array}{llll} [] &\vdash & *:\square &\text{axiom} \\ [\alpha:*] &\vdash& \alpha:* &\text{variable introduction} \\ [\alpha:*] &\vdash& *:\square &\text{weaken} \\ [] &\vdash & (\Pi \alpha:*.*):\square &\text{product formation} \\ [\beta:\Pi \alpha:*.*] &\vdash& \beta:(\Pi \alpha:*.*) &\text{variable introduction} \end{array}$

Im letzten Kontext muss eine gültige Typbewertung erfüllen . Für diese Typbewertung gibt es keine gültige Begriffsbewertung. $\xi(\beta) \in \nu(\Pi \alpha:*.*) = \{f| f:\text{SAT} \to \text{SAT}\}$

lo.logic type-theory lambda-calculus typed-lambda-calculus helmut
quelle

Die Hälfte der Leute, die dies lesen, wird denken, dass ist. Sie sollten erklären, was es ist. Auch Ihre Ableitung scheint ein bisschen seltsam. Die zweite Zeile sollte in ihrer Schlussfolgerung nicht erwähnen , sie sollte so etwas wie lesen, nicht wahr ?

S A T

$SAT$

α

$\alpha$

[α : *] ⊢ * : ◻

$[\alpha : *] \vdash * : \Box$

Andrej Bauer

Ich verwende die Notation von Herman Geuvers (die in diesem Bereich Standard zu sein scheint).

ist die Menge aller gesättigten Mengen von Lambda-Ausdrücken. Für die zweite Zeile meiner Ableitung: Es ist die Einführungsregel für Variablen eines reinen Typsystems. Diese Regel lautet

SAT

$\text{SAT}$

wobei

eine Art ist.

\frac{Γ ⊢ T : s}{Γ, x : T ⊢ x : T}

$\frac{\Gamma \vdash T:s}{\Gamma,x:T\vdash x:T}$

s

$s$

Helmut

Ich verstehe, wie Sie die zweite Zeile erhalten haben, aber es ist nicht die richtige Voraussetzung für die Bildung der dritten Zeile, oder? Welche Regel gibt die dritte Zeile.

Andrej Bauer

Die Produktbildungsregel von PTS sagt

. Die Konstruktionsrechnung hat die Regel

. Dadurch kann ich die erste und die zweite Zeile verwenden, um die dritte abzuleiten. Ich hatte jedoch einen Tippfehler in meinem Beitrag. Der Typ in der dritten Zeile fehlte, den ich jetzt hinzufügte.

\frac{r (s_{1}, s_{2}, s_{3}; Γ ⊢ A : s_{1}; Γ, x : A ⊢ B : s_{2}}{Γ ⊢ (Π x : A . B) : s_{3}}

$\frac{r(s_1,s_2,s_3;\, \Gamma\vdash A:s_1;\: \Gamma,x:A\vdash B:s_2}{\Gamma\vdash (\Pi x:A.B): s_3}$

r (*, *, *)

$r(*,*,*)$

Helmut

Sollte dann nicht die erste Zeile

? Oder hast du irgendwo

und

? Die zweite Zeile kann nicht die zweite Voraussetzung für die Produktbildungsregel sein, da dies bedeuten würde, dass Sie versuchen, so etwas wie

statt

[] ⊢ * : *

$[] \vdash * : *$

*

$*$

◻

$\Box$

\prod α : * . α

$\prod \alpha : * . \alpha$

\prod α : * . *

$\prod \alpha : * . *$

Andrej Bauer

Leider bin ich mir nicht sicher, ob es mehr anfängerfreundliche Ressourcen gibt als Geuvers 'Konto. Sie können diese Notiz von Chris Casinghino ausprobieren, in der mehrere Beweise bis ins kleinste Detail beschrieben werden.

Ich bin mir nicht sicher, ob ich den Kern Ihrer Verwirrung verstehe, aber ich denke, eine wichtige Sache ist das folgende Lemma (Korollar 5.2.14), das im klassischen Barendregt-Text bewiesen ist :

Γ ⊢ M : T \Rightarrow Γ ⊢ T : * or ◻

$\Gamma \vdash M:T\ \Rightarrow\ \Gamma \vdash T:*\mbox{ or }\square$

Dies bedeutet, dass während $[\![T]\!]_\xi$ kanneine komplizierte Funktion sein,wenn $\Gamma \vdash M:T$ gilt, dann $[\![T]\!]_\xi$ muss eine Reihe von Begriffen sein.

Dies wird in der Gliederung (Abschnitt 3.1) unterstellt, wobei $(\!|t|\!)_\sigma\in[\![T]\!]_\xi$ nur wenn $\Gamma \vdash t:T :*$ , was unserer Erwartung entspricht, dass die Interpretation eines Typs eine Menge von Begriffen sein muss, dh ${\cal V}(*)\subseteq{\cal P}(\mathrm{Term})$ (in der Tat) ${\cal V}(*)=\mathrm{SAT}$ !)

In der Typentheorie ist es üblich, dass wir, obwohl wir nur an der "Basisart" interessiert sind (hier $*$ ), immer noch die Semantik für Dinge höherer Arten definieren müssen (daher die Notwendigkeit, $\mathrm{SAT}^*$ einzuführen ). Am Ende dann, denn nur die Art, die von Typen bewohnt wird, ist $*$ (und $\square$ , aber das ist nicht wirklich wichtig).

Cody
quelle

Danke für die Erklärung. Das löst mein Problem, die in Geuvers Beweis verwendeten Funktionen nicht zu verstehen. Ich hatte bereits den Verdacht, Geuvers Artikel gelesen und erneut gelesen zu haben, aber Sie haben es kristallklar gemacht.

Helmut

Den Beweis einer starken Normalisierung der Konstruktionsrechnung verstehen

Antworten: