Подстановка лемма для типов

Question

tapl (стр. 549) предлагает следующую лемму, чтобы доказать надежность системы типа F System:

<Сильные> Замена Лемма для типов:

$ e, x, \ delta \ vdash t: t \ htrooms e, [x \ mapsto s] \ delta \ vdash [x \ mapsto s] t: [x \ mapsto s] t $

<Сильное> Доказательство корпуса T-TAPT:

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

и по правилу T-TAPP у нас есть:

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

Так что по гипотезе индукции:

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

Так что применяя правило T-TAPP, имеющее:

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

Однако мне нужно

Class="Math-Container"> $ [y \ mapsto a] [x \ mapsto s] t= [x \ mapsto s] [y \ mapsto a] t $

Я думаю, что я могу предположить, что $ a, s $ не может содержать $ y $ . .

Тем не менее, что, если $ a $ содержит $ x $ ? Тогда эти типы не совпадают.

Предположим, $ t $ содержит $ y $ . Затем LHS Type Leake $ x $ в результате, когда тип RHS не оставляет ни одного.

<Сильные> Другие источники

Вы можете найти нарисованное доказательство в доказательстве леммы 17, стр. 86 из следующих Лекционные ноты . Но этот случай кажется немедленным.

Answer 1

Лемма замещения поддержания только в том случае, если вы заменяете, хорошо сформирован: $ S $ может содержать только переменные типа, перечисленные в $ e $ . В приложении T-TAPP, $ y $ - это свежая переменная, не присутствующая в $ e, x, \ delta $ . В частности, $ \ Ne x $ , $ y \ notin s $ и $ y \ notin a $ .

Есть несколько способов моделировать имена переменной и переименования.

.
• Затенение позволяет связующему внутри другого связующего, чтобы использовать одно и то же имя (например, $ \ lambda x. \ lambda x. m $ ), а затем внешнее имя Скрытый (затененный) во внутренней конструкции (любое происшествие $ x $ в $ m $ относится к Внутренний $ x $ ). Если вы хотите обратиться к внешней переменной (например, которая может произойти для выполнения бета-восстановления), вам необходимо сначала выполнить явное преобразование Alpha для переименования одного из переменных.
• Неявное переименование всегда использует различные имена для любых двух связных присутствующих в любом месте выражения (так что вы никогда не пишете $ \ Color {Red} {\ lambda x. \ lambda x. m} $ или даже $ \ color {красный} {(\ lambda x. m) (\ lambda x. m)} $ , но $ \ lambda y. \ lambda x. m $ и $ (\ lambda xm) (\ lambda y. [x \ mapsto y] m. ) $ ), и есть неявный альфа-преобразование после любого снижения, которое дублирует термин. Это называется Конвенция Barendegt .
• Большинство литературных претензий к использованию Конвенции Barendegt, но на самом деле использует промежуточную конвенцию, где там вложенные связующие никогда не используют одно и то же имя, но связующие, которые не перекрывают друг друга, могут использовать одно и то же имя, и есть неявная альфа Шаг преобразования сразу после затенения. Таким образом, например, $ (\ lambda xm) (\ lambda xm) $ разрешено в письменном виде, но мета-нотация $ X $ В двух подругах предполагается представлять две разные переменные. Насколько я помню, TAPL использует эту конвенцию.

Окружающая среда - это коллекция связующих, поэтому без затенения, она не может определить одно и то же имя переменной, не раз (No $ \ gamma_1, x, \ gamma_2, x, \ gamma_3 $ ).

Теперь давайте посмотрим на приложение T-TAPP. Предпосылка - $ \ Gamma '\ vdash t': \ forall Y. t '$ где $ \ gamma'= ( E, [x \ mapsto s] \ delta) $ , $ t '= [x \ mapsto s] t $ и $ t '= [x \ mapsto s] t $ . Из этой предпосылки вы можете заключить $$ \ gamma '\ vdash \ lambda t' [a ']: [y \ mapsto a'] t '$$ Для любого хорошо сформированного $ a '$ . Вы хотите доказать $ \ Gamma '\ vdash [x \ mapsto s] (t [a]): [x \ mapsto s] [y \ mapsto a] t $ Так что возьмите $ a '= [x \ mapsto s] A $ . Заключение есть $$ \ Gamma '\ vdash ([x \ mapsto s] t) [[x \ mapsto s] a]: [y \ mapsto [x \ mapsto s] a] [x \ mapsto s] t $$ И это действительно $$ \ gamma '\ vdash [x \ mapsto s] (t [a]): [x \ mapsto s] [y \ mapsto a] t $$ Поскольку $ y \ ne x $ и $ y \ notin s $ .