Question

I have the following expression and need help doing the reduction. The left hand expression has to equal to the right hand expression.

  1. (λn.(λs.(s (λx.λy.y))n) λx.x)(λx.λy.y) = λx.x
  2. (λn.(λs.(s (λxy.y))n) λx.x)(λxy.y) = λx.x
Was it helpful?

Solution

Here are the reduction steps for each:

(λn.(λs.(s (λx.λy.y))n) λx.x)(λx.λy.y)
(λs.(s (λx.λy.y)) λx.x)(λx.λy.y)
(λx.x (λx.λy.y))(λx.λy.y)
(λx.λy.y)(λx.λy.y)
λy.y

(λn.(λs.(s (λxy.y))n) λx.x)(λxy.y) 
(λs.(s (λxy.y)) λx.x)(λxy.y)
(λx.x (λxy.y))(λxy.y)
λxy.y (λxy.y) 
λy.y

Side note: 1 and 2 are equivalent since (λx.λy.y) = (λxy.y)

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top