¿Qué es la equivalencia beta?

21

En el script que estoy leyendo actualmente sobre el cálculo lambda, la equivalencia beta se define así:

La equivalencia β es la equivalencia más pequeña que contiene β .βββ

No tengo idea de lo que eso significa. ¿Alguien puede explicarlo en términos más simples? Tal vez con un ejemplo?

Lo necesito para un lema que sigue el teorema de Church-Russer, que dice

βββ

magnético
fuente
Lo siento si el idioma no es perfecto, traduje las citas del alemán.
magnético

Respuestas:

20

es la relación de un paso entre los términos en elcálculo λ . Esta relación no es reflexiva, simétrica ni transitiva. La relación de equivalenciaβ es el cierre reflexivo, simétrico y transitivo deβ . Esto significaβλββ

  1. Si entonces M β M .MβMMβM
  2. Para todos los términos , M β M se cumple.MMβM
  3. Si MβM , entonces MβM .
  4. MβM , entonces.MβMMβM
  5. β es la relación más pequeña que satisface las condiciones 1-4.

De manera más constructiva, primero aplique las reglas 1 y 2, luego repita las reglas y una y otra vez hasta que no agreguen elementos nuevos a la relación.34

Dave Clarke
fuente
1
Ok gracias, creo que lo entiendo entonces. Mi primera suposición fue que significa que M de alguna manera puede reducirse a N, pero eso no necesariamente tiene que sostenerse porque obviamente también son equivalentes si pueden reducirse al mismo término. Debido a su punto 3, esto se puede construir entonces, supongo. Gracias, eso ayudó mucho. MβN
magnético
¿No es la relación infinitamente grande? ¿No siempre puedo encontrar un término L para un término M de modo que ? LβM
magnético
Lo es, pero eso no debería ser problemático. ¿Por qué estás buscando tal ? L
Dave Clarke
No lo sé. Estaba discutiendo con mi pareja si siempre sería infinitamente grande. Gracias por la explicación. :)
magnético
11

Es la teoría de conjuntos elemental realmente. Sabes qué es una relación reflexiva, qué es una relación simétrica y qué es una relación transitiva, ¿verdad? Una relación de equivalencia es aquella que satisface las tres propiedades.

Probablemente has oído hablar del "cierre transitivo" de una relación ? Bueno, no es más que la relación transitiva menos que incluye R . Eso es lo que significa el término "cierre". Del mismo modo, puede hablar sobre el "cierre simétrico" de una relación R , el "cierre reflexivo" de una relación R y el "cierre de equivalencia" de una relación R exactamente de la misma manera.RRRRR

Con un poco de pensamiento, puedes convencerte de que el cierre transitivo de es R R 2R 3 . El cierre simétrico es R R - 1 . El cierre reflexivo es R I (donde I es la relación de identidad). RRR2R3RR1RII

Usamos la notación para I R R 2 . Este es el cierre transitivo reflexivo de R . Ahora observe que si R es simétrico, cada una de las relaciones I , R , R 2 , R 3 , ... es simétrica. Por lo tanto, R también será simétrico.RIRR2RRIRR2R3R

Entonces, el cierre de equivalencia de es el cierre transitivo de su cierre simétrico, es decir, ( R R - 1 ) . Esto representa una secuencia de pasos, algunos de los cuales son pasos hacia adelante ( R ) y algunos pasos hacia atrás ( R - 1 ).R(RR1)RR1

Se dice que la relación tiene la propiedad Church-Rosser si el cierre de equivalencia es el mismo que la relación compuesta R ( R - 1 ) . Esto representa una secuencia de pasos en la que todos los pasos hacia adelante son lo primero, seguidos por todos los pasos hacia atrás. Por lo tanto, la propiedad Church-Rosser dice que cualquier intercalación de pasos hacia adelante y hacia atrás se puede llevar a cabo de manera equivalente haciendo pasos hacia adelante primero y hacia atrás más tarde.RR(R1)

Uday Reddy
fuente
2
Si agrega una oración final para relacionarse con la pregunta, esta sería una buena respuesta.
Raphael
Todo es tan elemental que uno llega al final y se pregunta "¿dónde está la respuesta, en realidad?"
Marco Faustinelli