1
$\begingroup$

What are the diffs between these two?

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

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

and why?

My understanding is that:

For the first one, it is a lambda abstraction, without application. The 2nd one is an application on the final x, but one of my blurry is that are all the x the same as the input x?

  • 1
    @alex.jordan this is lambda calculus, not linear algebra.2012-12-24

1 Answers 1

3

No, the different $x$ in each expression represents slightly different things.

Instead, you can change variables to get:

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

and

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

Note that you can "eliminate" the $x$ from the first expression, because all occurrences of $x$ are inside a $\lambda x.\dots$ expression. You cannot do the same for the second.

It is best to think of $\lambda x.\dots$ as providing a "mechanism" for defining a new function. The variable of the function is called $x$, but it can be called anything, as long as we replace all of the "correct" instances of $x$ inside with the new variable name.

Consider the difference between the expressions:

$$x+2$$ $$f(x)=x+2$$

In the first, you can't just write, $x+2=y+2$, but you can say that if $g(y)=y+2$ and $f(x)=x+2$ then $g=f$.

That said, the two expressions above "evaluate" to the same thing. Both functions are the identity function - that is, both functions are equal to $\lambda w.w$.

  • 0
    for λx.((λx.x)x)=λy.((λz.z)y), can I write it again like this: λx.((λx.x)x)=**λy.((λz.z)x)**?2012-12-27
  • 0
    No, you have to replace that $x$ inside the lambda expression when do the change, while the $x$ in the second expression is outside the lambda expression.2012-12-27