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.

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|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
1  
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
2  
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
add comment

1 Answer

up vote 0 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 "operation of orders" as in conventional mathematics. Things to note are parenthesis are evaluated first.

share|improve this answer
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.