Quelle est l'équivalence bêta?

Question

Dans le script que je lis actuellement sur le lambda-calcul, l'équivalence bêta est définie comme ceci:

  

\ beta $ -equivalence $ \ equiv_ \ beta $ est l'équivalence qui contient le plus petit $ \ rightarrow_ \ beta $.

Je ne sais pas ce que cela signifie. Quelqu'un peut-il expliquer en termes simples? Peut-être avec un exemple?

J'ai besoin pour un lemme suivant du théorème Eglise Russer, en disant

  

Si M $ \ equiv_ \ beta $ N alors il y a un L avec M $ \ twoheadrightarrow_ \ L beta $ et N $ \ twoheadrightarrow_ \ beta $ L.

Answer 1

$ \ to_ \ beta $ est la relation d'un pas entre termes dans le $ \ lambda $ -calcul. Cette relation est ni réflexive, symétrique ou transitive. La relation d'équivalence $ \ equiv_ \ beta $ est réflexive, symétrique, fermeture transitive de $ \ to_ \ beta $. Ce moyen

1. Si $ M \ to_ \ M beta '$, alors M $ \ equiv_ \ M beta' $.
2. Pour tous les termes $ M $, $ M \ equiv_ \ beta M $ détient.
3. Si $ M \ equiv_ \ M beta '$, alors M $ \ equiv_ $ \ M beta.
4. Si $ M \ equiv_ \ M beta '$ et $ M' \ equiv_ \ M beta '' $, alors M $ \ equiv_ \ M beta '' $.
5. $ \ equiv_ \ beta $ est la plus petite relation satisfaisant les conditions 1-4.

Plus constructive, d'abord appliquer les règles 1 et 2, puis répétez les règles $ 3 $ et 4 $ plus et plus jusqu'à ce qu'ils ajoutent pas d'éléments nouveaux à la relation.

Answer 2

Il est la théorie des ensembles élémentaire vraiment. Vous savez ce qui est une relation réflexive, ce qui est une relation symétrique, et ce qui est une relation transitive, non? Une relation d'équivalence est celle qui satisfait à tous les trois de ces propriétés.

Vous avez probablement entendu parler de la « fermeture transitive » d'une relation $ R $? Eh bien, il n'y a rien, mais le moins transitive relation qui comprend $ R $. C'est ce que le terme signifie « de fermeture ». De même, vous pouvez parler de la « fermeture symétrique » d'une relation $ R $, la « fermeture réflexive » d'une relation $ R $ et la « fermeture d'équivalence » d'une relation $ R $ exactement de la même manière.

Avec une pensée, vous pouvez vous convaincre que la fermeture transitive de $ R $ est $ R \ cup R ^ 2 \ tasse R ^ 3 \ cup \ ldots $. La fermeture est symétrique $ R \ cup R ^ {- 1} $. La fermeture réflexive est $ R \ tasse I $ (où $ I $ est la relation d'identité).

Nous utilisons la notation $ R ^ * $ pour $ I \ tasse R \ tasse R ^ 2 \ cup \ ldots $. Ceci est la réflexif fermeture transitive de $ R $. Maintenant, remarquez que si $ R $ est symétrique, chacun des rapports I $ $, $ R $, $ R ^ 2 $, $ R ^ 3 $, ... est symétrique. Par conséquent $ R ^ * $ sera également symétrique.

Ainsi, la fermeture d'équivalence de $ R $ est la fermeture transitive de sa fermeture symétrique, à savoir, $ (R \ cup R ^ {- 1}) ^ * $. Cela représente une séquence d'étapes, dont certaines sont pas en avant ($ R $) et quelques pas en arrière (R $ ^ {- 1} $).

La relation $ R $ est dit d'avoir la propriété de Church-Rosser si la fermeture d'équivalence est le même que la relation composite $ R ^ * (R ^ {- 1}) ^ * $. Cela représente une séquence d'étapes dans laquelle toutes les étapes avant viennent en premier, suivi par toutes les étapes en amont. Ainsi, la propriété de Church-Rosser dit que tout entrelacer des pas en avant et en arrière peuvent être effectués par manière équivalente suivant les étapes en avant première et pas en arrière plus tard.