Substitutionslemma für Typen

Question

TAPL (Seite 549) schlägt das folgende Lemma vor, um die Solidität des Systems vom Typ System F zu beweisen:

Substitutionslemma für Typen:

$E, X, \Delta \vdash t:T \impliziert E, [X \mapsto S] \Updelta \vdash [X \mapsto S]t:[X \mapsto S]T$

Beweis des T-TApp-Falls:

$ E,X,\Delta \vdash t[A]:[Y \mapsto A]T $

und nach Regel T-TApp haben wir:

$ E,X,\Delta \vdash t:\lambda Y .T $

also nach Induktionshypothese:

$E, [X \mapsto S] \Delta \vdash [X \mapsto S]t:\lambda Y.[X \mapsto S]T$

Wenn wir also die T-TApp-Regel anwenden, erhalten wir:

$E, [X \mapsto S] \Delta \vdash [X \mapsto S]t[A]:[Y \mapsto A][X \mapsto S]T$

aber ich sollte es brauchen $[Y \mapsto A][X \mapsto S]T = [X \mapsto S][Y \mapsto A]T$

Ich denke, dass ich davon ausgehen kann $A,S$ nicht enthalten kann $Y$.

Was wäre jedoch, wenn $A$ enthält $X$?Dann stimmen diese Typen nicht überein.

Annehmen $T$ enthält $Y$.Dann geht der linke Typ $X$ist im Ergebnis, während der rhs-Typ keine hinterlässt.

Andere Quellen

Einen skizzierten Beweis finden Sie im Beweis von Lemma 17, Seite 86 des Folgenden Vorlesungsnotizen.Aber dieser Fall scheint unmittelbar zu sein.

Answer 1

Das Substitutionslemma gilt nur, wenn das, was Sie ersetzen, wohlgeformt ist: $S$ kann nur Typvariablen enthalten, die in aufgeführt sind $E$.Bei der Anwendung von T-TApp, $Y$ ist eine neue Variable, die in nicht vorhanden ist $E,X,\Delta$.Insbesondere, $Y e X$, $Y otin S$ Und $Y otin A$.

Es gibt verschiedene Möglichkeiten, Variablennamen und Umbenennungen zu modellieren.

• Durch das Schattieren kann ein Ordner innerhalb eines anderen Ordners denselben Namen verwenden (z. B. $\lambda x.\lambda x.M$), und dann wird der äußere Name im inneren Konstrukt ausgeblendet (schattiert) (jedes Vorkommen von $x$ In $M$ bezieht sich auf das Innere $x$).Wenn Sie auf die äußere Variable verweisen möchten (was beispielsweise passieren kann, um eine Beta-Reduktion durchzuführen), müssen Sie zunächst eine explizite Alpha-Konvertierung durchführen, um eine der Variablen umzubenennen.
• Beim impliziten Umbenennen werden immer unterschiedliche Namen für zwei beliebige Ordner verwendet, die irgendwo in einem Ausdruck vorhanden sind (Sie schreiben also nie $\color{red}{\lambda x.\lambda x.M}$ oder auch $\color{red}{(\lambda x.M) (\lambda x.M)}$, Aber $\lambda y.\lambda x.M$ Und $(\lambda x.M) (\lambda y.[x \mapsto y]M)$), und nach jeder Reduktion, die einen Begriff dupliziert, erfolgt eine implizite Alpha-Konvertierung.Dies nennt man Barendregt-Konferenz.
• Die meiste Literatur behauptet, die Barendregt-Konvention zu verwenden, verwendet jedoch tatsächlich eine Zwischenkonvention, bei der verschachtelte Ordner niemals denselben Namen verwenden, Ordner, die sich nicht überlappen, jedoch denselben Namen verwenden können, und es gibt sofort einen impliziten Alpha-Konvertierungsschritt nachdem eine Abschattung auftritt.Also zum Beispiel $(\lambda x.M) (\lambda x.M)$ ist schriftlich erlaubt, jedoch die Metanotation $x$ in den beiden Teiltermen sollen zwei unterschiedliche Variablen darstellen.Soweit ich mich erinnere, verwendet TAPL diese Konvention.

Eine Umgebung ist eine Sammlung von Ordnern. Ohne Shadowing kann sie denselben Variablennamen nicht mehr als einmal definieren (Nr $\Gamma_1,X,\Gamma_2,X,\Gamma_3$).

Schauen wir uns nun die Anwendung von T-TApp an.Die Prämisse ist $\Gamma' \vdash t' :\forall Y.T'$ Wo $\Gamma' = (E, [X \mapsto S] \Delta)$, $t' = [X \mapsto S] t$ Und $T' = [X \mapsto S] T$.Aus dieser Prämisse können Sie schließen$$\Gamma' \vdash \lambda t'[A'] :[Y \mapsto A'] T'$$für jeden wohlgeformten $A'$.Du willst beweisen $\Gamma' \vdash [X \mapsto S] (t[A]) :[X \mapsto S] [Y \mapsto A] T$.So nimm $A' = [X \mapsto S] A$.Die Schlussfolgerung ist$$\Gamma' \vdash ([X \mapsto S] t)[[X \mapsto S] A] :[Y \mapsto [X \mapsto S] A] [X \mapsto S] T$$und das ist tatsächlich der Fall$$\Gamma' \vdash [X \mapsto S] (t[A]) :[X \mapsto S] [Y \mapsto A] T$$seit $Y e X$ Und $Y otin S$.