¿Qué es beta equivalencia?

Question

En el guión que estoy leyendo actualmente en el cálculo lambda, la equivalencia beta se define como la siguiente:

El $ \ beta $ -equivalence $ \ equiv_ \ $ beta es la equivalencia más pequeño que contiene $ \ rightarrow_ \ beta $.

No tengo idea de lo que significa. ¿Puede alguien explicar en términos más simples? Tal vez con un ejemplo?

Lo necesito para un lema siguiente del teorema de Church-Russer, diciendo

Si M $ \ equiv_ \ beta $ N, entonces hay una L con M $ \ twoheadrightarrow_ \ beta $ L y N $ \ twoheadrightarrow_ \ beta $ L.

Answer 1

$ \ to_ \ beta $ es la relación de un solo paso entre los términos de la $ \ lambda $ -calculus. Esta relación no es ni reflexiva, simétrica o transitivo. La relación de equivalencia $ \ equiv_ \ $ beta es el reflexiva, simétrica cierre transitivo de $ \ to_ \ beta $. Este medio de

1. Si $ M \ to_ \ beta M 'M \ equiv_ \ beta M $ entonces $' $.
2. Para todos los términos $ M $, $ M \ equiv_ \ beta M $ se mantiene.
3. Si $ M \ equiv_ \ beta M '$, entonces $ M' \ equiv_ \ beta M $.
4. Si $ M \ equiv_ \ beta M '$ y $ M' \ equiv_ \ beta M '' $, entonces $ M \ equiv_ \ beta M '' $.
5. $ \ equiv_ \ beta $ es la relación más pequeño que satisface las condiciones 1-4.

Más constructivamente, aplicar primero las reglas 1 y 2, a continuación, repita gobierna $ $ 3 y $ 4 $ y otra vez hasta que añaden nuevos elementos a la relación.

Answer 2

Es la teoría de conjuntos elemental realmente. Usted sabe lo que es una relación reflexiva, lo que es una relación simétrica, y lo que es una relación transitiva, ¿verdad? Una relación de equivalencia es aquel que satisface los tres de esas propiedades.

Usted probablemente ha oído hablar de la "clausura transitiva" de una relación R $ $? Bueno, no es más que el relación transitiva menos que incluye $ R $. Eso es lo que significa el término "cierre". Del mismo modo, se puede hablar de la "clausura simétrica" ??de una relación $ R $, la "clausura reflexiva" de una relación $ R $ y el "cierre de equivalencia" de una relación $ R $ exactamente de la misma manera.

Con un poco de pensamiento, puede convencerse de que el cierre transitivo de $ R $ es $ R \ R ^ 2 taza \ taza de R ^ 3 \ taza \ ldots $. El cierre es simétrica $ R taza R \ ^ {- 1} $. El cierre es reflexiva $ R \ taza I $ (donde $ I $ es la relación de identidad).

Utilizamos la notación R $ ^ $ * $ para I \ R taza \ taza de R ^ 2 \ taza \ ldots $. Este es el clausura transitiva reflexiva de $ R $. Ahora note que si $ R $ es simétrica, cada una de las relaciones de $ I $, $ R $, $ R $ ^ 2, R $ ^ $ 3, ... es simétrica. Por lo tanto R $ ^ $ * También será simétrico.

Así que el cierre de equivalencia de $ R $ es la clausura transitiva de su cierre simétrica, es decir, $ (R \ R ^ {taza - 1}) ^ * $. Esto representa una secuencia de pasos, algunos de los cuales son pasos hacia adelante ($ R $) y algunos pasos hacia atrás ($ R ^ {- 1} $).

Se dice que la relación $ R $ a tener la propiedad de la Iglesia-Rosser si el cierre de equivalencia es el mismo que el compuesto relación R $ ^ * (R ^ {- 1}) ^ * $. Esto representa una secuencia de pasos en la que todos los pasos hacia adelante vienen primero, seguido de todos los pasos hacia atrás. Por lo tanto, la propiedad de la Iglesia-Rosser dice que cualquier entrelazado de pasos adelante y hacia atrás se puede llevar a cabo de forma equivalente al hacer avanzar los pasos primero y pasos hacia atrás después.