Lemme de substitution pour les types

Question

TAPL (page 549) propose le lemme suivant afin de prouver la solidité du système de type Système F :

Lemme de substitution pour les types :

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

Preuve du cas T-TApp :

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

et par règle T-TApp on a :

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

donc par hypothèse d'induction :

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

donc en appliquant la règle T-TApp nous avons :

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

mais j'aurais besoin $[Y \mapsto A][X \mapsto S]T = [X \mapsto S][Y \mapsto A]T$

Je pense que je peux supposer que $A,S$ ne peut pas contenir $Y$.

Cependant, et si $A$ contient $X$?Alors ces types ne coïncident pas.

Supposer $T$ contient $Y$.Puis le type lhs part $X$est dans le résultat alors que le type rhs n'en laisse aucun.

Autres sources

Vous pouvez trouver une preuve esquissée dans la preuve du lemme 17, page 86 de ce qui suit notes de lecture.Mais cette affaire semble immédiate.

Answer 1

Le lemme de substitution n'est valable que si ce que vous remplacez est bien formé : $S$ ne peut contenir que des variables de type répertoriées dans $E$.Dans l'application de T-TApp, $Y$ est une nouvelle variable, non présente dans $E,X,\Delta$.En particulier, $Y e X$, $Y \pas dans S$ et $Y \pas dans A$.

Il existe plusieurs façons de modéliser les noms de variables et de les renommer.

• L'observation permet à un classeur à l'intérieur d'un autre classeur d'utiliser le même nom (par ex. $\lambda x.\lambda x.M$), puis le nom externe est masqué (ombré) dans la construction interne (toute occurrence de $x$ dans M$ fait référence à l'intérieur $x$).Si vous souhaitez faire référence à la variable externe (ce qui peut arriver à effectuer une réduction bêta, par exemple), vous devez d'abord effectuer une conversion alpha explicite pour renommer l'une des variables.
• Le changement de nom implicite utilise toujours des noms distincts pour deux classeurs présents n'importe où dans une expression (vous n'écrivez donc jamais $\color{rouge}{\lambda x.\lambda x.M}$ ou même $\color{rouge}{(\lambda x.M) (\lambdax.M)}$, mais $\lambda y.\lambda x.M$ et $(\lambda x.M) (\lambda y.[x \mapsto y]M)$), et il y a une conversion alpha implicite après toute réduction qui duplique un terme.C'est ce qu'on appelle le Congrès du Barendregt.
• La plupart de la littérature prétend utiliser la convention de Barendregt, mais utilise en fait une convention intermédiaire selon laquelle les classeurs imbriqués n'utilisent jamais le même nom, mais les classeurs qui ne se chevauchent pas peuvent utiliser le même nom, et il y a immédiatement une étape de conversion alpha implicite. après l'observation.Alors par exemple $(\lambda x.M) (\lambda x.M)$ est autorisé par écrit, mais la méta-notation $x$ dans les deux sous-termes sont censés représenter deux variables différentes.Autant que je me souvienne, TAPL utilise cette convention.

Un environnement est une collection de classeurs, donc sans observation, il ne peut pas définir le même nom de variable plus d'une fois (aucun $\Gamma_1,X,\Gamma_2,X,\Gamma_3$).

Voyons maintenant l'application de T-TApp.La prémisse est $\Gamma' \vdash t' :\forall Y.T'$ où $\Gamma' = (E, [X \mapsto S] \Delta)$, $t' = [X \mapsto S] t$ et $T' = [X \mapsto S] T$.De cette prémisse, on peut conclure$$\Gamma' \vdash \lambda t'[A'] :[Y \mapsto A'] T'$$pour tout bien formé $A'$.Tu veux prouver $\Gamma' \vdash [X \mapsto S] (t[A]) :[X \mapsto S] [Y \mapsto A] T$.Alors prenez $A' = [X \mapsto S] A$.La conclusion est$$\Gamma' \vdash ([X \mapsto S] t)[[X \mapsto S] A] :[Y \mapsto [X \mapsto S] A] [X \mapsto S] T$$et c'est effectivement$$\Gamma' \vdash [X \mapsto S] (t[A]) :[X \mapsto S] [Y \mapsto A] T$$depuis $Y e X$ et $Y \pas dans S$.