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
    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