Lemma sostitutiva per i tipi

Question

TAPL (pagina 549) propone il seguente Lemma per dimostrare la solidità del sistema di sistema di sistema F:

Sostituzione Lemma per i tipi:

$ e, x, \ delta \ vdata t: t \ implica e, [x \ mapsto s] \ delta \ vdash [x \ mapsto s] t: [x \ \ MapSTO S] T $

Prova del caso T-TAPP:

$ e, x, \ delta \ vdata t [A]: [y \ mapsto a] t $

E per regola T-TAPP Abbiamo:

$ e, x, \ delta \ vdata t: \ lambda y. T $

Allora per ipotesi di induzione:

$ e, [x \ mapsto s] \ delta \ vdata [x \ mapsto s] t: \ lambda y. [x \ mapsto s] t $

Quindi applicando la regola T-TAPP abbiamo:

$ e, [x \ mapsto s] \ delta \ vdata [x \ mapsto s] t [a]: [y \ mapsto a] [x \ mapsto s] t $

Tuttavia dovrei aver bisogno di $ [y \ mapsto a] [x \ mapsto s] t= [x \ mapsto s] [y \ mapsto a] t $

Penso di poter presumere che $ A, s $ non può contenere $ y $ . .

Tuttavia, cosa succede se $ A $ contiene $ x $ ? Quindi questi tipi non coincidono.

Assumere $ T $ contiene $ y $ . Quindi il tipo LHS lascia $ x $ 's Nel risultato mentre il tipo RHS non lasceranno.

Altre fonti

Puoi trovare una prova abbozzata nella prova di Lemma 17, pagina 86 del seguente Note sulle lezioni . Ma questo caso sembra essere immediato.

Answer 1

La sostituzione Lemma contiene solo se ciò che stai sostituendo è ben formato: $ s $ può contenere solo variabili di tipo elencati in $ e $ . Nell'applicazione di T-TAPPP, $ y $ è una nuova variabile, non presente in $ e, x, \ delta $ . In particolare, $ y \ ne x $ , $ y \ notin s $ e $ y \ Notin a $ .

Ci sono diversi modi per modellare nomi e rinomina variabili.

.
• Shadowing consente a un legante all'interno di un altro legante di utilizzare lo stesso nome (ad es. $ \ Lambda x. \ Lambda x. m $ ), quindi il nome esterno è nascosto (ombreggiato) nel costrutto interno (qualsiasi discorso di $ x $ in $ m $ si riferisce al Inner $ x $ ). Se si desidera fare riferimento alla variabile esterna (che può verificarsi di eseguire una riduzione beta, ad esempio), è necessario eseguire prima una conversione alfa esplicita per rinominare una delle variabili.
• Il rinominamento implicito utilizza sempre nomi distinti per eventuali due leganti presenti ovunque in un'espressione (quindi non si scrive mai $ \ color {rosso} {\ lambda x. \ Lambda x. m} $ o anche $ \ color {rosso} {(\ lambda x. m) (\ lambda x. m)} $ , ma $ \ Lambda y. \ Lambda x. m $ e $ (\ Lambda XM) (\ Lambda y. [x \ MapSTO Y] M ) $ ), e vi è una conversione alfa implicita dopo qualsiasi riduzione che duplica un termine. Questo è chiamato la convenzione barendregt .
• La maggior parte della letteratura afferma di utilizzare la Convenzione di BarendRegt, ma infatti utilizza una convenzione intermedia in cui i leganti nidificati non usano mai lo stesso nome, ma i leganti che non si sovrappongono a vicenda possono utilizzare lo stesso nome, e c'è un alfa implicito Passaggio di conversione immediatamente dopo l'ombra. Quindi, ad esempio $ (\ Lambda XM) (\ Lambda XM) $ è consentito per iscritto, ma la meta-notazione $ X $ Nei due sottermi dovrebbero rappresentare due variabili diverse. Per quanto mi ricordo, TAPL usa questa convenzione.

Un ambiente è una raccolta di leganti, quindi senza shadowing, non può definire lo stesso nome variabile più di una volta (no $ \ gamma_1, x, \ gamma_2, x, \ gamma_3 $ ).

Ora, guardiamo l'applicazione di T-TAPP. La premessa è $ \ Gamma '\ VDash T': \ Forll Y. T '$ dove $ \ gamma'= ( E, [x \ mapsto s] \ delta) $ , $ t '= [x \ mapsto s] t $ e $ T '= [x \ mapsto s] t $ . Da questa premessa, puoi concludere $$ \ Gamma '\ VDash \ Lambda T' [A ']: [y \ mapsto a'] t '$$ Per qualsiasi elegante $ a '$ . Vuoi dimostrare $ \ gamma '\ vdata [x \ mapsto s] (t [a]): [x \ mapsto s] [y \ mapsto a] t $ . Quindi prendere $ a '= [x \ mapsto s] a $ . La conclusione è $$ \ Gamma '\ VDash ([x \ mapsto s] t) [[x \ mapsto s] A]: [y \ mapsto [x \ mapsto s] A] [x \ mapsto s] t $$ E questo è davvero $$ \ Gamma '\ VDash [x \ mapsto s] (t [a]): [x \ mapsto s] [y \ mapsto a] t $$ Dal momento che $ y \ ne x $ e $ y \ notin s $ .