Identifying All Redexes in Lambda Expression

1.3k Views Asked by At

I am self-studying Lambda calculus and have encountered a question where I need to identify all the redexes of the following expression: (λu.(λx.u)u)((λy.y)(λw.(λv.v)w)). Here are all the ones I've come up with, but I'm not sure if they are valid or if I'm missing any. Could somebody help?

1. (λx.(λy.y) (λw.(λv.v) w)) ((λy.y) (λw.(λv.v) w))
2. (λy.y) (λw.(λv.v) w)
3. λw.(λv.v) w
4. (λu.(λx.u) u) ((λy.y) (λv.v))
5. (λx.λv.v) (λv.v)
1

There are 1 best solutions below

2
On BEST ANSWER

A redex of a term is its subterm of the form $(\lambda x.M)N$. Some of your expressions aren't redexes of the given expression, but of some different terms (which you probably computed by evaluating the original one).

Redexes of the original expressions are: $$ \underbrace{(\lambda u.\underbrace{(\lambda x.u)u})(\underbrace{(\lambda y.y)(\lambda w.\underbrace{(\lambda v.v)w})})} $$