Prova de Barendregt de redução de assunto para

Eu encontrei um problema na prova de redução de assunto de Barendregt (Thm 4.2.5 do cálculo Lambda com tipos ).

A última etapa da prova (página 60) diz:

"e, portanto, pelo lema 4.1.19 (1), . " $\quad\Gamma,x:\rho\vdash P:\sigma'$

No entanto, de acordo com o Lema 4.1.19 (1) ele deve ser , uma vez que a substituição é feita para todo o contexto, não apenas a . $\Gamma[\vec{\alpha}:=\vec{\tau}],x:\rho\vdash P:\sigma'$ $x:\rho'$

Eu acho que a solução padrão pode ser de alguma forma provar que , mas não sei ao certo como. $\vec{\alpha}\notin FV(\Gamma)$

Eu tinha uma prova para simplificá-lo, relaxando o lema de abstração da geração, mas descobri recentemente que houve um erro e minha prova está errada, por isso não tenho mais certeza de como resolver esse problema.

Alguém pode me dizer o que estou perdendo aqui?

lo.logic type-theory lambda-calculus proof-theory Alejandro DC
fonte

Barendregt assume o chamado convenção variável, que nomes de variáveis ligadas e nomes de variáveis livres são padronizados para além , ou seja, assumimos implicitamente que eles são diferentes (usando

-Conversão Talvez isso ajude..

α

$\alpha$

Dave Clarke

Γ, x : ρ ⊢ P : σ^{'}

$\Gamma,x:\rho\vdash P:\sigma'$

Γ, x : ρ^{'} ⊢ P : σ^{″}

$\Gamma,x:\rho'\vdash P:\sigma''$

ρ^{'} [\vec{α} := \vec{τ}] = ρ

$\rho'[\vec{\alpha}:=\vec{\tau}]=\rho$

σ^{″} [\vec{α} := \vec{τ}] = σ^{'}

$\sigma''[\vec{\alpha}:=\vec{\tau}]=\sigma'$ , então, usando esse lema, ele pode fazer a mesma substituição no contexto e o tipo inferido ao mesmo tempo ... mas ele apenas substitui no x: \ rho ', nem todo o contexto! E esse é o meu problema ...

Alejandro DC

Prova de Barendregt de redução de assunto para

Respostas: