Substituição de lema para os tipos

Question

TAPL (página 549) propõe o seguinte lema, a fim de provar a solidez do Sistema F tipo de sistema:

Substituição de lema para tipos:

$E, X, \Delta \vdash t:T \implica que E [X \mapsto T] \Delta \vdash [X \mapsto T]t:[X \mapsto T]T$

A prova de que o T-TApp caso:

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

e por regra T-TApp, temos:

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

então, por hipótese de indução:

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

assim, aplicando-se o T-TApp regra, temos:

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

no entanto, eu deveria necessidade $[Y \mapsto A][X \mapsto T]T = [X \mapsto T][Y \mapsto T$

Eu acho que eu posso supor que $A,S$ não pode conter $Y$.

No entanto, o que se $A$ contém $X$?Em seguida, esses tipos não coincidem.

Suponha $T$ contém $Y$.Em seguida, o lhs tipo de folhas $X$'s no resultado, enquanto o tipo de rhs não deixar qualquer.

Outras fontes

Você pode encontrar uma esboçou prova a prova do lema 17, página 86, do seguinte anotações de aula.Mas este caso parece ser imediata.

Answer 1

A substituição lema prende somente se o que você está substituindo está bem formado: $S$ pode conter apenas as variáveis do tipo listado no $E$.Na aplicação de T-TApp, $Y$ é uma nova variável, não presentes no $E,X,\Delta$.Em particular, $Y e X$, $Y otin S$ e $Y otin de us$.

Existem várias maneiras de modelo nomes de variáveis e mudar o nome.

• Sombreamento permite que um fichário dentro de outro arquivo para usar o mesmo nome (por exemplo, $\lambda x.\lambda x.M$) e, em seguida, o exterior nome é oculto (sombreado) no interior da construção (qualquer ocorrência de $x$ no $M$ refere-se para o interior $x$).Se você quiser se referir para o exterior variável (o que pode acontecer a executar uma versão beta de redução, por exemplo), você precisa primeiro realizar uma explícita alfa de conversão para mudar o nome de uma das variáveis.
• Implícito renomear sempre usa nomes distintos para quaisquer dois ligantes presentes em qualquer parte de uma expressão (por isso, nunca escreva $\color{red}{\lambda x.\lambda x.M}$ ou até $\color{red}{(\lambda x.M) (\lambda x.M)}$, mas $\lambda y.\lambda x.M$ e $(\lambda x.M) (\lambda y.[x \mapsto y]M)$), e há um implícito alfa de conversão após qualquer redução que duplica um prazo.Este é o chamado Barendregt convenção.
• A maioria da literatura afirma usar o Barendregt convenção, mas, na verdade, usa-se um intermédio de convenção onde há aninhadas ligantes nunca use o mesmo nome, mas ligantes que não se sobrepõem uns aos outros pode usar o mesmo nome, e há um implícito alfa de conversão etapa imediatamente após o sombreamento ocorre.Assim, por exemplo, $(\lambda x.M) (\lambda x.M)$ é permitido escrever, mas o meta-notação $x$ nos dois subterms supostamente representam duas variáveis diferentes.Tanto quanto me lembro, TAPL usa essa convenção.

Um ambiente é uma coleção de capas, assim, sem sombreamento, é possível definir o mesmo nome de variável mais de uma vez (sem $\Gamma_1,X,\Gamma_2,X,\Gamma_3$).

Agora, vamos olhar para a aplicação de T-TApp.A premissa é $\Gamma' \vdash t' :\forall Y.T'$ onde $\Gamma' = (E [X \mapsto T] \Delta)$, $t' = [X \mapsto T] t$ e $T' = [X \mapsto T] T$.A partir desta premissa, pode-se concluir $$\Gamma' \vdash \lambda t'[A'] :[Y \mapsto Uma'] T'$$ para qualquer bem formado $A'$.Você quer provar $\Gamma' \vdash [X \mapsto T] (t[A]) :[X \mapsto T] [Y \mapsto T$.Então pegue $A' = [X \mapsto T] de us$.A conclusão é $$\Gamma' \vdash ([X \mapsto T] t)[[X \mapsto T] A] :[Y \mapsto [X \mapsto T] A] [X \mapsto T] T$$ e este é, de facto, $$\Gamma' \vdash [X \mapsto T] (t[A]) :[X \mapsto T] [Y \mapsto T$$ desde $Y e X$ e $Y otin S$.