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?
$\begingroup$
$\endgroup$
5
-
$\begingroup$ Please make sure that I didn’t introduce any errors when I converted to $\LaTeX$. $\endgroup$– Brian M. ScottCommented Mar 2, 2013 at 17:56
-
$\begingroup$ No, looks good. Thanks. $\endgroup$– John RobertsCommented Mar 2, 2013 at 17:57
-
1$\begingroup$ 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. $\endgroup$– dtldarekCommented Mar 2, 2013 at 18:04
-
$\begingroup$ @dtldarek I'm not sure what you mean by syntactically - if they're equivalent syntactically, aren't they equivalent generally as well? $\endgroup$– John RobertsCommented Mar 2, 2013 at 18:37
-
2$\begingroup$ 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. $\endgroup$– Brian M. ScottCommented Mar 2, 2013 at 18:44
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Sep 1, 2013 at 23:55