Was ist Beta-Äquivalenz?

21

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

Die -Äquivalenz ist die kleinste Äquivalenz, die .β ββββ

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

Ich brauche es für ein Lemma, das sich aus dem Church-Russer-Theorem ergibt

Wenn M N ist, dann gibt es ein L mit M L und N \ twoheadrightarrow_ \ beta L.βββ

großartig
quelle
Tut mir leid, wenn die Sprache nicht perfekt ist, ich habe die Zitate aus dem Deutschen übersetzt.
Magnattic

Antworten:

20

β ist die einstufige Beziehung zwischen Begriffen im λ Kalkül. Diese Beziehung ist weder reflexiv noch symmetrisch oder transitiv. Die Äquivalenzrelation β ist der reflexive, symmetrische, transitive Abschluss von β . Das heisst

  1. Wenn MβM dann MβM .
  2. Für alle Begriffe , hält.MMβM
  3. Wenn'dann .MβMMβM
  4. Wenn und , dann .MβMMβMMβM
  5. β ist die kleinste Beziehung, die die Bedingungen 1-4 erfüllt.

Konstruktiver: Wenden Sie zuerst die Regeln 1 und 2 an und wiederholen Sie dann die Regeln und so oft, bis der Beziehung keine neuen Elemente mehr hinzugefügt werden.34

Dave Clarke
quelle
1
Ok danke, ich glaube ich verstehe es dann. Meine erste Annahme war, dass bedeutet, dass M irgendwie auf N reduziert werden kann, aber das muss nicht unbedingt gelten, weil sie offensichtlich auch äquivalent sind, wenn sie auf denselben Term reduziert werden können. Aufgrund Ihres Punktes 3 kann dieser dann konstruiert werden, denke ich. Danke, das hat mir sehr geholfen. MβN
Magnattic
Ist die Beziehung nicht unendlich groß? Kann ich nicht immer einen Begriff L für einen Begriff M finden, sodass ? LβM
Magnattic
Es ist, aber das sollte nicht problematisch sein. Warum suchst du so ein ? L
Dave Clarke
Ich weiß es nicht. Ich habe gerade mit meinem Partner gestritten, ob es immer unendlich groß sein würde. Danke fürs Erklären. :)
Magnattic
11

Es ist wirklich elementare Mengenlehre. Sie wissen, was ist eine reflexive Beziehung, was ist eine symmetrische Beziehung und was ist eine transitive Beziehung, richtig? Eine Äquivalenzrelation ist eine, die alle drei dieser Eigenschaften erfüllt.

Sie haben wahrscheinlich von der "transitiven Schließung" einer Beziehung ? Nun, es ist nichts als die am wenigsten transitiven Beziehung , die . Das ist, was der Begriff "Schließung" bedeutet. Genauso kann man über den "symmetrischen Abschluß" einer Relation , den "reflexiven Abschluß" einer Relation und den "Äquivalenzabschluß" einer Relation sprechen .RRRRR

Mit einigem Nachdenken, können Sie sich selbst davon überzeugen , dass die transitive Hülle von ist . Der symmetrische Verschluss ist . Der reflexive Verschluss ist (wobei die Identitätsbeziehung ist). RRR2R3RR1RII

Wir verwenden die Notation für . Dies ist die reflexive transitive Schließung von . Beachten Sie nun, dass, wenn symmetrisch ist, jede der Beziehungen , , , , ... symmetrisch ist. Daher wird auch symmetrisch sein.RIRR2RRIRR2R3R

Der Äquivalenzschluss von ist also der transitive Abschluss seines symmetrischen Abschlusses, dh . Dies stellt eine Folge von Schritten dar, von denen einige Vorwärtsschritte ( ) und einige Rückwärtsschritte ( ) sind.R(RR1)RR1

Die Beziehung soll die Church-Rosser-Eigenschaft haben, wenn der Äquivalenzschluss mit der zusammengesetzten Beziehung identisch ist . Dies stellt eine Abfolge von Schritten dar, bei denen alle Vorwärtsschritte an erster Stelle stehen, gefolgt von allen Rückwärtsschritten. Die Church-Rosser-Eigenschaft besagt also, dass eine Verschachtelung von Vorwärts- und Rückwärtsschritten in gleicher Weise durchgeführt werden kann, indem zuerst Vorwärtsschritte und später Rückwärtsschritte ausgeführt werden.RR(R1)

Uday Reddy
quelle
2
Wenn Sie einen letzten Satz hinzufügen, um sich auf die Frage zu beziehen, wäre dies eine gute Antwort.
Raphael
Es ist alles so elementar, dass man zum Ende kommt und sich fragt, "wo ist eigentlich die Antwort?"
Marco Faustinelli