Was ist Beta -Äquivalenz?

Question

In dem Skript, das ich gerade auf dem Lambda -Kalkül lese, ist die Beta -Äquivalenz definiert wie folgt:

Die $ beta $ -äquivalenz $ acriv_ Beta $ ist die kleinste Äquivalenz, die $ rightarrow_ Beta $ enthält.

Ich habe keine Ahnung was das heißt. Kann es jemand einfacher erklären? Vielleicht mit einem Beispiel?

Ich brauche es für eine Lemma, die aus dem Theorem der Kirchen-Russer-Theorem folgt und sagt

Wenn m $ acriv_ beta $ n dann gibt es ein L mit m $ twoheadrightarrow_ Beta $ l und n $ Twoheadrightarrow_ Beta $ L.

Answer 1

$ to_ beta $ ist die einstufige Beziehung zwischen den Begriffen im $ lambda $ -Calculus. Diese Beziehung ist weder reflexiv, symmetrisch noch transitiv. Die Äquivalenzbeziehung $ äquiv_ beta $ ist der reflexive, symmetrische Transitive -Verschluss von $ to_ Beta $. Das heisst

1. Wenn $ m to_ beta m '$, dann $ M äquiv_ Beta M' $.
2. Für alle Bedingungen $ M $ hält $ m acriv_ Beta M $.
3. Wenn $ m acriv_ beta m '$, dann $ M' äquiv_ Beta m $.
4. Wenn $ m acriv_ beta m '$ und $ m' äquiv_ beta m '' $, dann $ M äquiv_ Beta M '' $.
5. $ äquiv_ beta $ ist die kleinste Beziehung, die die Bedingungen 1-4 erfüllt.

Konstruktiver, wenden Sie zuerst die Regeln 1 und 2 an, dann wiederholen Sie die Regeln $ 3 $ und 4 $ $ immer wieder, bis sie der Beziehung keine neuen Elemente hinzufügen.

Answer 2

Es ist wirklich elementare Set -Theorie. Sie wissen, wie eine reflexive Beziehung ist, was eine symmetrische Beziehung ist und wie eine transitive Beziehung ist, oder? Eine Äquivalenzbeziehung ist eine, die alle drei dieser Eigenschaften erfüllt.

Sie haben wahrscheinlich von der "transitiven Schließung" einer Beziehung $ R $ gehört? Nun, es ist nichts anderes als das geringste transitive Beziehung Dazu gehören $ R $. Das bedeutet der Begriff "Verschluss". In ähnlicher Weise können Sie über die "symmetrische Schließung" einer Beziehung $ r $, die "reflexive Schließung" einer Beziehung $ r $ und die "Äquivalenzschließung" einer Beziehung $ r $ sprechen.

Mit einigen Gedanken können Sie sich davon überzeugen, dass die transitive Schließung von $ r $ $ r cup r^2 cup r^3 cup ldots $ beträgt. Der symmetrische Verschluss beträgt $ r cup r^{-1} $. Die reflexive Schließung beträgt $ r cup i $ (wobei $ i $ die Identitätsbeziehung ist).

Wir verwenden die Notation $ r^*$ für $ i cup r cup r^2 cup ldots $. Dies ist das Reflexive transsitive Schließung von $ r $. Beachten Sie nun, dass, wenn $ R $ symmetrisch ist, jede der Beziehungen $ i $, $ R $, $ R^2 $, $ R^3 $, ... symmetrisch ist. Daher wird $ r^*$ auch symmetrisch sein.

Der Äquivalenzverschluss von $ r $ ist also der transitive Verschluss seines symmetrischen Verschlusses, dh $ (r cup r^{-1})^*$. Dies stellt eine Abfolge von Schritten dar, von denen einige Vorwärtsschritte ($ R $) und einige Rückwärtsschritte ($ r^{-1} $) sind.

Die Beziehung $ r $ soll das Eigentum von Church-Rosser haben, wenn die Äquivalenzschließung mit der zusammengesetzten Beziehung $ r^* (r^{-1})^* $ ist. Dies stellt eine Folge von Schritten dar, in denen alle Vorwärtsschritte zuerst kommen, gefolgt von allen rückständigen Schritten. Das Kirchen-Rosser-Eigentum besagt also, dass jede Verschachtelung von Vorwärts- und Rückwärtsschritten gleichbedeutend mit den Vorwärts- und Rückwärtsschritten später durchgeführt werden kann.