$\beta$ la desigualdad en $\lambda$-cálculo

Question

Requisitos previos

Considere la posibilidad de la $\lambda$-cálculo donde los términos son clases de equivalencia sobre el $\alpha$-igualdad.

Definimos $\to_\beta$-reducción de la manera habitual, es decir, el menos congruentes relación en $\lambda$-términos (de ahí congruentes con la aplicación y la abstracción) que satisface

$$(\lambda x. M) N \to_\beta M[x := N]$$

Después de esto, $=_\beta$ se define como la relación de equivalencia que contiene a $\to_\beta$.

Pregunta

Ahora, probablemente, uno fácil:

Demostrar que $$\lambda x .x =_\beta x$$ no tiene.

Comentarios

Para mí es evidente que la ecuación anterior no se sostiene. En ambos lados son formas normales, que difieren. Incluso se puede demostrar que el uso de una gran cantidad de maquinaria: Church-Rosser, paralela reducción de la relación y el orden en beta-reducción de las secuencias. Pero parece como si esta debe ser una tarea fácil y sólo estoy con vistas a algo. Siempre estoy buscando ideas para una prueba formal.

El ejercicio está basado en uno del libro "Conferencias sobre el Curry-Howard Isomorfismo" por Sørensen y Urzyczyn.

Answer 1

La Iglesia-Rosser propiedad es todo lo que necesita: $\lambda x.x$ $x$ ambos $\rightarrow_{\beta}$-formas normales de manera que sólo puedan ser $\rightarrow_{\beta}$-equivalente si son $\alpha$-equivalente, que no lo son.

Para explicar esto con más detalle, permítanme escribir $a \rightarrow b$ significa que $b$ puede ser obtenida a partir de a $a$ por las reiteradas $\beta$-reducción. La Iglesia-Rosser propiedad dice que si $a \rightarrow b$$a \rightarrow c$, entonces hay un plazo $d$ tal que $b \rightarrow d$$c \rightarrow d$. Si $\lambda x.x$ $x$ se $\rightarrow_{\beta}$-equivalente, entonces no sería una secuencia de términos $t_1, \ldots, t_n$ $t_1 \equiv \lambda x.x$ $t_n \equiv x$ tal que para cada $i$, $1 \le i < m$ cualquiera de las $t_i\rightarrow t_{i+1}$ o $t_{i+1}\rightarrow t_i$. Church-Rosser permite transformar cualquier triple de la forma $t_{i-1} \leftarrow t_{i} \rightarrow t_{i+1}$ en esta secuencia en un triple de la forma $t_{i-1} \rightarrow t_{i}' \leftarrow t_{i+1}$. En repetidas ocasiones la aplicación de esta transformación, el resultado será una secuencia $t_1', \dots, t_n'$$t_1' \equiv \lambda x.x$$t_n' \equiv x$, de tal manera que $t_1' \rightarrow t_2'$$t_n' \rightarrow t_{n-1}'$. Pero $t_1'$ $t_n'$ ambos $\rightarrow_{\beta}$-formas normales, así que esto es imposible, a menos que $t_1' = t_2' = \ldots = t_{n-1}' = t_n'$, que no es el caso si $t_1' \equiv \lambda x.x$$t_n' \equiv x$.