Does $\beta \eta$ reduction preserve free variables?

246 Views Asked by At

It seems to be a know fact that if $M$, $N$ are $\lambda$-terms, and $M \twoheadrightarrow_{\beta\eta} N$, then $fv(N) \subseteq fv(M)$.

My problem is: is it true that if $M \twoheadrightarrow_{\beta\eta} N$ then $fv(N) = fv(M)$?

1

There are 1 best solutions below

1
On BEST ANSWER

No. Let $x, y$ and $z$ be three different variables. Take $M = (\lambda x . y) z$. Then $M$ $\beta$-reduces to $y$. Free variables of $M$ are $y$ and $z$, and the only free variable in $y$ is $y$.