1
$\begingroup$

I am studying lambda calculus for the first time and I was trying to do the reduction beta of the lambda term $(\lambda x.xy)y$. Can I assume that these two free variables $y$ are the same? Or do I need to rename the rightmost $y$?

$\endgroup$
2
$\begingroup$

$y$ is free in the term you have given, so it is indeed the same variable.

You would not have the same variable in case $y$ was bound by the lambda. That would be the case, for example, if the term were to be $(\lambda y.xy)y$; then the rightmost $y$ would be free, but the one in $xy$ would be bound by lambda and, hence, a different variable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.