استبدال Lemma لأنواع

Question

Tapl (صفحة 549) تقترح LEMMA التالي من أجل إثبات سلامة نظام نظام النظام F:

lemma lemma لأنواع:

$ e، x، \ delta \ vdash t: t \ implies e، [x \ mapsto s] \ delta \ vdash [x \ mapsto s] t: [x \ Mapsto S] T $

إثبات حالة T-Tapp:

$ 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] $

ومع ذلك يجب أن أحتاج إلى $ [y \ mapsto a] [x \ mapsto s] t= [x \ mapsto s] [y \ mapsto a] t $

أعتقد أنني أستطيع أن أفترض أن $ A، S $ لا يمكن أن تحتوي على $ y $ .

ومع ذلك، ماذا لو $ A $ يحتوي على $ x $ ؟ ثم هذه الأنواع لا تتزامن.

افترض $ T $ يحتوي على $ Y $ . ثم يترك نوع LHS $ x $ في النتيجة أثناء عدم ترك نوع RHS.

مصادر أخرى

يمكنك العثور على دليل رسمي في إثبات Lemma 17، صفحة 86 من التالي ملاحظات المحاضرات . ولكن يبدو أن هذه القضية فورية.

Answer 1

استبدال Lemma يحمل فقط إذا تم استبداله بشكل جيد: $ S $ يمكن أن تحتوي فقط على متغيرات النوع المدرجة في $ e $ . في تطبيق T-Tapp، $ y $ هو متغير جديد، غير موجود في $ e، x، \ delta $ . على وجه الخصوص، $ y \ ne x $ ، $ y \ notin s $ and $ y \ notin $ .

هناك عدة طرق لنموذج أسماء متغيرة وإعادة تسمية.

• التظليل يسمح للموثق داخل موثق آخر لاستخدام نفس الاسم (على سبيل المثال $ \ lambda x. \ Lambda x. M $ )، ثم الاسم الخارجي مخفية (مظللة) في البنية الداخلية (أي حدوث $ x $ في $ m $ يشير إلى $ x $ ). إذا كنت ترغب في الرجوع إلى المتغير الخارجي (الذي يمكن أن يحدث لإجراء تخفيض تجريبي، على سبيل المثال)، تحتاج أولا إلى إجراء تحويل ألفا صريح لإعادة تسمية أحد المتغيرات.
• إعادة تسمية ضمنية تستخدم دائما أسماء متميزة لأي مقاستين موجودين في أي مكان في تعبير (حتى لا تكتب $ \ color {red} {\ lambda x. \ lambda x. m} $ أو حتى $ \ color {red} {(\ lambda x. m) (\ lambda x. m)} $ ، ولكن $ \ Lambda y. \ Lambda x. M $ و $ (\ lambda xm) (\ lambda y. [x \ mapsto y] m ) $ )، وهناك تحويل ألفا الضمني بعد أي تخفيض يكرر مصطلح. وهذا ما يسمى اتفاقية barendregt .
• معظم أدب المطالبات لاستخدام اتفاقية barendegt، ولكن في الواقع تستخدم اتفاقية وسيطة حيث لا تستخدم المجلدات المتداخلة نفس الاسم، ولكن المجلدات التي لا تتداخل مع بعضها البعض يمكن أن تستخدم نفس الاسم، وهناك ألفا ضمنية خطوة التحويل مباشرة بعد التظليل يحدث. لذلك على سبيل المثال $ (\ lambda xm) (\ lambda xm) $ مسموح به في الكتابة، ولكن NETA-Notation $ X $ من المفترض أن تمثل المرتبة الفرعية اثنين من المتغيرات المختلفة. بقدر ما أتذكر، يستخدم Tapl هذه الاتفاقية.

بيئة هي مجموعة من المجلدات، لذلك دون التظليل، لا يمكن تحديد نفس اسم المتغير أكثر من مرة (لا $ \ gamma_1، x، \ gamma_2، x، \ gamma_3 $ ).

الآن، دعونا نلقي نظرة على تطبيق T-Tapp. الفرضية هي $ \ gamma '\ vdash t': \ forall y. t '$ حيث $ \ gamma'= ( ه، [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] $ . الاستنتاج هو $$ \ gamma '\ vdash ([x \ mapsto s] [[x \ mapsto s] a]: [y \ mapsto [x \ mapsto s] [x \ Mapsto S] T $$ وهذا هو في الواقع $ \ gamma '\ vdash [x \ mapsto s] (t [a]): [x \ mapsto s] [y \ mapsto a] t $ منذ $ y \ ne x $ and $ y \ notin s $ .