implica.

Question

En el contexto de $\lambda$-cálculo, estaba pensando en si o no $$Mx ={\beta\eta} Nx \implies M ={\beta\eta} N$$ if $x\notin FV (M) \cup FV(N)$. Han sido alrededor de este tema durante bastante tiempo, pero no llegar a cualquier lugar útil.

¿Es el caso o no?

Answer 1

Esto es cierto independientemente de si $x \in FV(MN)$.

Prueba. Por hipótesis:

$$Mx =_{\beta\eta} Nx \tag{1}$$

Luego también:

$$(\lambda x.Mx) =_{\beta\eta} (\lambda x.Nx) \tag{2}$$

La justificación de la $(2)$ es que la secuencia de (posiblemente revertir parcialmente) $\beta\eta$-contracciones que demuestre $(1)$ también resultará $(2)$ cuando se aplica a la subterm $Mx$$(\lambda x.Mx)$.

---

Por otro lado, en la teoría formal de $\lambda\beta\eta$ (y también a $\lambda\beta$) este hecho se explica por la debilidad de extensionality' regla de inferencia $\xi$: $$\begin{align} M &\;= M' \\ \hline (\lambda x.M) &\;= (\lambda x.M') \tag{%#%#%} \end{align}$$

Desde

$\xi$$

usted podría, en principio, sólo citar regla de $$\lambda\beta\eta \vdash M = N \iff M =_{\beta\eta} N$ a deducir $\xi$$ (2)$.

---

Además, por la $(1)$-regla: $\eta$$(\lambda x.Mx) =_{\beta\eta} M \tag{3}$$

Así que por $$(\lambda x.Nx) =_{\beta\eta} N \tag{4}$,$(2)$,$(3)$y la simetría y la transitividad de la$(4)$ tenemos:

$=_{\beta\eta}$$

lo que concluye la prueba. $$M =_{\beta\eta} (\lambda x.Mx) =_{\beta\eta} (\lambda x.Nx) =_{\beta\eta} N$

Tenga en cuenta que el $\square$-la regla general es añadido a un $\eta$-de la teoría a hacer extensional (en lugar de intensional), así que la verdad de su declaración de que estaba a la espera.