Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
  1. In recursion for λ calculus, I was wondering why the following two are equal

    (λx.g (x x)) (λx.g (x x))

    g ((λx.g (x x)) (λx.g (x x)))

  2. How shall I understand g ((λx.g (x x)) (λx.g (x x)))?

I am learning λ calculus from Wikipedia, and I can understand many of its basics.


share|cite|improve this question
up vote 3 down vote accepted

When you evaluate $(\lambda x.g(x x)) (y)$, it is equivalent to $g(y y)$ (This is called $\beta$-reduction). Therefore, when you do $$ (\lambda \, x.g(x \, x))(\lambda \, x.g(x \, x)) $$ You can see the second parenthesis as the "big chunk you're putting as an argument in your abstraction on the left", so that $$ (\lambda \, x.g(x \, x))(\, Y \,) \quad \underset{\beta}{\rightarrow} \quad g(\,Y \quad Y\,) \quad \rightarrow \quad g( (\lambda \, x.g(x\, x)) (\lambda\, x.g(x \,x)) ) $$ (I used the right-arrow to say "reads as". This is standard for $\beta$-reduction.)

Wikipedia is not a place to learn, it's a reference. You should use it only to take a look at fun stuff or recall something you've already learned. For learning, you should use books or tutorials, it's a better idea. Try this as a tutorial :

Hope that helps,

share|cite|improve this answer

Your Answer


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.