Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
@alex.jordan this is lambda calculus, not linear algebra. –  Thomas Andrews Dec 24 '12 at 20:46
add comment

1 Answer

up vote 3 down vote accepted

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

share|improve this answer
    
for λx.((λx.x)x)=λy.((λz.z)y), can I write it again like this: λx.((λx.x)x)=**λy.((λz.z)x)**? –  Jackson Tale Dec 27 '12 at 0:16
    
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. –  Thomas Andrews Dec 27 '12 at 0:23
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.