タイプの代替レンマ

Question

TAPL（549ページ）は、システムF型システムの健全性を証明するために、次の補題を提案します。

種類のための置換された補題：

$ E、X、\ Delta \ VDASH T：T \ Icmese 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-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 [a]：[y \ mapsto a] [x \ mapsto s] t $

しかし、 $ [y \ mapsto a] [x \ mapsto s] t= [x \ mapsto s] [y \ mapsto a] t $

$ a、s $ に

しかし、 $ a $ の場合、 $ x $ が含まれている場合はどうなりますか？それからこれらのタイプは一致しません。

$ t $ にassups $ y $ が含まれています。その後、LHSタイプは結果に $ X $ が残りません。

その他のソース

次の講義ノート。しかし、この場合は即時のようです。

Answer 1

置換策は、置換されているものが整形式である場合にのみ保持されます。 $ s $ には、 $ y $ は、 $ e、x、\ deltaに存在しない新鮮な変数です。 $ 。特に、 $ y \ ne x $ 、 $ y \ notin s $ と $ Y \ Notin $ 。

変数名と名前を変更するにはいくつかの方法があります。

• Shadowingを使用すると、別のバインダー内のバインダーが同じ名前を使用できます（例： $ \ lambda x。m $ ）、そして外側の名前は $ m $ 内の内部構成（ $ x $ の発生）に隠された（shadowed）。内部 $ x $ ）。外部変数（たとえば、ベータリダクションを実行できます）を参照したい場合は、最初に明示的なアルファ変換を実行して、変数の1つを変更する必要があります。
• 暗黙の名前の変更は、常に式の任意の2つのバインダーに対して常に異なる名前を使用しています（ $ \ color {red}} {\ lambda x。m} $ または $ \ color {red} {（\ lambda x.m）} $ 、 $ \ Lambda \ Lambda x。m $ と $（\ Lambda xm）（\ Lambda y. [X \ mapsto y] m ）$ ）、そして用語を複製するために、削減後に暗黙的なアルファ変換があります。これは Barendregt Convention です。
• ほとんどの文献はBarendregt条約を使用すると主張していますが、実際にはネストされたバインダーが同じ名前を使用しない中間条約を使用していますが、互いに重ならないバインダーは同じ名前を使用でき、暗黙のアルファがあります。シャドウイングが発生した直後の変換ステップ。たとえば、 $（\ LAMBDA xm）（\ Lambda xm）（\ Lambda xm）$ は、メタ表記 $です。 2つのサブターム内のX $ は、2つの異なる変数を表すことになっています。私が覚えている限り、TAPLはこの条約を使用しています。

環境はバインダーの集まりです。そうせずに同じ変数名を複数回定義できません（ $ \ gamma_1、x、\ gamma_2、x、\ gamma_3 $ ）

今、T-TAPPのアプリケーションを見てみましょう。前提は $ \ gamma '\ vdash t'：\ forall y '$ ここで、 $ \ 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 a] [y \ mapsto a] t $ 。そのため、 $ a '= [x \ mapsto s] $ 。結論は $$ \ 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 $ 。