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

I'm a bit new to lambda calculus and was wondering about the equivalence of two expressions

$$(\lambda x.\lambda y.xy)\lambda z.z\overset{?}=(\lambda x.\lambda y.xy)(\lambda z.z)$$

Can anyone help out?

share|cite|improve this question
Please make sure that I didn’t introduce any errors when I converted to $\LaTeX$. – Brian M. Scott Mar 2 '13 at 17:56
No, looks good. Thanks. – John Roberts Mar 2 '13 at 17:57
In $\lambda$-calculus the $\lambda$ symbol behaves similarly to a quantifier and its scope spans until the enclosing parenthesis or end of term. The two expressions are equivalent syntactically. – dtldarek Mar 2 '13 at 18:04
@dtldarek I'm not sure what you mean by syntactically - if they're equivalent syntactically, aren't they equivalent generally as well? – John Roberts Mar 2 '13 at 18:37
I believe that @dtldarek is saying that the difference is purely cosmetic, like that between $\exists x\varphi(x)$ and $\exists x\big(\varphi(x)\big)$, and hence that the two are trivially equivalent. – Brian M. Scott Mar 2 '13 at 18:44
up vote 1 down vote accepted

By convention the outer most parenthesis are dropped for minimal clutter. $$\color{red}{(\lambda x.\lambda y.xy)}\color{blue}{\lambda z.z}\iff\color{red}{(\lambda x.\lambda y.xy)}\color{blue}{(\lambda z.z)}$$ The same thing is done in algebra: $$\color{red}{(z)}\color{blue}{(x+y)}\iff \color{red}z\color{blue}{(x+y)}$$ In lambda calculus there is a similar "order of operations" as in conventional mathematics. Things to note are parenthesis are evaluated first.

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.