Lambda Calculus - reduction with a shorthand term

Asked Aug 30 '16 at 23:03

Active Aug 31 '16 at 09:14

Viewed 74 times

I'm new to lambda calculus and am having trouble understand how a shorthand acts when reducing.

Given: $((\lambda xy.x)(\lambda y.y))y$

What I have:

since $\lambda xy.x = \lambda x.\lambda y.x$

$((\lambda x.\lambda y.x)(\lambda y.y))y$

Now from here, I'm not sure how to continue with the reduction. I believe the whole thing is supposed to simplify to $xy$ but I'm not sure how to get there.

edited Aug 31 '16 at 09:14

amd

53,693

asked Aug 30 '16 at 23:03

greenteam

1

There is a typo, in the last lamda expression it should be ((Lx.Ly.x)(Ly.y))y. – Caleb Stanford Aug 30 '16 at 23:05
@6005 Thanks, fixed it – greenteam Aug 30 '16 at 23:07
After simplifying, I get $\lambda y. y$, not $xy$. – Caleb Stanford Aug 30 '16 at 23:07
@6005
is this the proper steps? ((Lx.Ly.x)(Ly.y))y = (Ly.(Ly.y)) y = (Ly.y)
– greenteam Aug 30 '16 at 23:10
2

No you have to do a variable change before the first application, because there are two Lys. – Caleb Stanford Aug 30 '16 at 23:11
Ah gotcha. With variable changes you're allowed to use any variable name right? So it could be ((Lx.Ly.x)(Ly.y))y = ((Lx.Lw.x)(Ly.y)y = (Lw.(Ly.y))y = Ly.y – greenteam Aug 30 '16 at 23:15
1

Yep! Now you got it. – Caleb Stanford Aug 30 '16 at 23:15
@6005 awesome thanks so much! – greenteam Aug 30 '16 at 23:17

Lambda Calculus - reduction with a shorthand term

0 Answers0