Qu'est-ce que l'équivalence bêta?

21

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

L' équivalence est la plus petite équivalence qui contient .βββ

Je n'ai aucune idée de ce que ça veut dire. Quelqu'un peut-il l'expliquer en termes plus simples? Peut-être avec un exemple?

J'en ai besoin pour un lemme suivant le théorème de Church-Russer, disant

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

magnétique
la source
Désolé si la langue n'est pas parfaite, j'ai traduit les citations de l'allemand.
2012

Réponses:

20

β est la relation en une étape entre les termes du λ -calculus. Cette relation n'est ni réflexive, ni symétrique, ni transitive. La relation d'équivalence β est la fermeture réflexive, symétrique et transitive de β . Ça signifie

  1. Si MβM alors MβM .
  2. Pour tous les termes M , MβM est valable.
  3. Si MβM'alors MβM .
  4. Si MβM et MβM , alors MβM .
  5. β est la plus petite relation satisfaisant aux conditions 1-4.

De manière plus constructive, appliquez d'abord les règles 1 et 2, puis répétez les règles et encore et encore jusqu'à ce qu'elles n'ajoutent aucun nouvel élément à la relation.34

Dave Clarke
la source
1
Ok merci, je pense que je comprends alors. Ma première hypothèse était que signifie que M peut en quelque sorte être réduit à N, mais cela ne doit pas nécessairement tenir car ils sont évidemment également équivalents s'ils peuvent être réduits au même terme. En raison de votre point 3, cela peut être construit alors, je suppose. Merci, cela a beaucoup aidé. MβN
Magnattic
La relation n'est-elle pas infiniment grande? Suis-je pas toujours en mesure de trouver un terme L pour un terme M de sorte que ? LβM
Magnattic
C'est vrai, mais cela ne devrait pas être problématique. Pourquoi cherchez-vous un tel ? L
Dave Clarke
Je ne sais pas. Je me disais juste avec mon partenaire si ce serait toujours infiniment grand. Merci d'avoir expliqué. :)
magnétique
11

C'est vraiment de la théorie des ensembles élémentaires. Vous savez ce qu'est une relation réflexive, qu'est-ce qu'une relation symétrique et qu'est-ce qu'une relation transitive, n'est-ce pas? Une relation d'équivalence est une relation qui satisfait à ces trois propriétés.

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

Avec un peu de réflexion, vous pouvez vous convaincre que la fermeture transitive de est . La fermeture symétrique est . La fermeture réflexive est (où est la relation d'identité). RRR2R3RR1RII

Nous utilisons la notation pour . Ceci est la fermeture réflexive et transitive de . Remarquez maintenant que si est symétrique, chacune des relations , , , , ... est symétrique. Par conséquent, sera également symétrique.RIRR2RRIRR2R3R

La fermeture d'équivalence de est donc la fermeture transitive de sa fermeture symétrique, c'est-à-dire . Cela représente une séquence d'étapes, dont certaines sont des étapes avant ( ) et des étapes arrière ( ).R(RR1)RR1

On dit que la relation a la propriété de Church-Rosser si la fermeture d'équivalence est la même que la relation composite . Cela représente une séquence d'étapes dans laquelle toutes les étapes avant viennent en premier, suivies de toutes les étapes arrière. Ainsi, la propriété Church-Rosser indique que tout entrelacement des étapes avant et arrière peut être effectué de manière équivalente en effectuant des étapes avant d'abord et des étapes arrière plus tard.RR(R1)

Uday Reddy
la source
2
Si vous avez ajouté une dernière phrase pour se rapporter à la question, ce serait une bonne réponse.
Raphael
Tout est si élémentaire que l'on arrive à la fin et se demande "où est la réponse, en fait?"
Marco Faustinelli