ベータ等価とは何ですか？

Question

私が現在Lambda Calculusで読んでいるスクリプトでは、ベータの等価性が次のように定義されています。

$ beta $ equivalence $ equiv_ beta $は、$ rightArrow_ beta $を含む最小の等価性です。

それが何を意味するのか分かりません。誰かが簡単に説明できますか？たぶん例がありますか？

私は教会の熟練した定理からフォローする補題のためにそれを必要とします

m $ equiv_ beta $ nの場合、m $ twoheadrightArrow_ beta $ lおよびn $ twoheadrightArrow_ beta $ lのLがあります。

Answer 1

$ to_ beta $は、$ lambda $ -calculusの用語間の1段階の関係です。この関係は、反射的、対称的、または推移的ではありません。等価関係$ equiv_ beta $は、$ to_ beta $の反射的、対称的、推移的閉鎖です。これの意味は

1. $ m to_ beta m '$の場合、$ m equiv_ beta m' $。
2. すべての条件に対して、$ m $、$ m equiv_ beta m $ holdが保留されます。
3. $ m equiv_ beta m '$の場合、$ m' equiv_ beta m $。
4. $ m equiv_ beta m '$ and $ m' equiv_ beta m '' $の場合、$ m equiv_ beta m '' $。
5. $ equiv_ beta $は、満足のいく条件1-4です。

より建設的には、最初にルール1と2を適用し、次に、関係に新しい要素を追加しないまで、ルール$ 3 $と$ 4 $を何度も繰り返します。

Answer 2

それは本当に基本的な理論です。あなたは反射的な関係とは何か、対称的な関係とは何ですか、そして推移的な関係とは何ですか？同等の関係は、これらのプロパティの3つすべてを満たすものです。

おそらく、$ r $の関係の「推移的閉鎖」について聞いたことがあるでしょうか？まあ、それはそれに他なりません 最小推移的な関係 これには$ r $が含まれます。それが「閉鎖」という用語の意味です。同様に、関係$ r $の「対称閉鎖」、関係$ r $の「再帰的閉鎖」、および関係$ r $の「等価閉鎖」について、まったく同じ方法で話すことができます。

ある程度考えれば、$ r $の推移的閉鎖は$ r cup r^2 cup r^3 cup ldots $であると確信できます。対称閉鎖は$ r cup r^{-1} $です。再帰的閉鎖は$ r cup i $（$ i $はアイデンティティの関係です）です。

$ i cup r cup r^2 cup ldots $の表記$ r^*$を使用します。これは 反射的な推移的閉鎖 $ r $の。ここで、$ r $が対称である場合、それぞれの関係は$ i $、$ r $、$ r^2 $、$ r^3 $、...対称であることに注意してください。したがって、$ r^*$も対称になります。

したがって、$ r $の等価閉鎖は、対称閉鎖の推移的閉鎖、すなわち$（r cup r^{-1}）^*$です。これは、一連のステップを表し、その一部はフォワードステップ（$ r $）といくつかの後方ステップ（$ r^{-1} $）です。

同等の閉鎖が複合関係$ r^*（r^{-1}）^* $と同じである場合、$ r $は教会rosserのプロパティを持っていると言われています。これは、すべてのフォワードステップが最初に来る一連のステップを表し、その後にすべての後方ステップが続きます。したがって、教会ロッサーの財産は、前後のステップのインターリーブは、最初に順方向と後方の手順を実行することで同等に実行できると述べています。