1

I'm now starting the syntax of the lambda calculus, and have a very simple question about the parentheses for free and bound variable.

Are " x1:= λx.x x " and " x2:= (λx.x) x " represent the same? In other word, is the second "x" in x1 free? I know the second "x" in x2 is free for sure, I just wonder what the purpose put parentheses there.

BTW, x3:= λx.x y and x4:= (λy.x) y, I think "y" in x3 is free and "x" in x4 is free, anyone could check for me ? Thanks

Student
  • 119
  • 1
    I think usually $\lambda$ is treated as having a "low binding strength" or "low operator precedence" so I'd interpret x1 as $\lambda x . (x ~ x)$. – Daniel Schepler Feb 14 '18 at 20:51

3 Answers3

1

The lambda calculus syntax rules/conventions are:

1) application has higher precedence than abstraction. This is:

λx.AB = λx.(AB) ≠ (λx.A)B

2) application is left associative. This means:

ABC = (AB)C ≠ A(BC)

In your specific examples, the semantic difference would be:

  • "x1:= λx.x x" Here x1 is a function that takes a value x and returns x x. So if we apply the function x1 to a free variable z we get: x1 z -reduces to-> z z
  • "x2:= (λx.x) x" Here we have the identity function (λx.x takes an x and returns it as is) applied to the free variable x. So this will reduce to x.

Your guesses about free variables inside x3 and x4 are correct.

Euge
  • 171
  • so does x1 has free variable ? – Student Feb 14 '18 at 23:07
  • what do you think? here's one article on free variables https://en.wikipedia.org/wiki/Free_variables_and_bound_variables – Euge Feb 14 '18 at 23:34
  • I have no idea, base on the previous discussion another person post, it should be no free variable. But I think you two are opposite, it makes me confuse – Student Feb 14 '18 at 23:37
  • No free variables inside λx.x x. In that expression both xs are bounded to the λx part. In the other case, (λx.x) x, the parenthesis are leaving the last x out of the scope of the lambda and thus we have a bounded x on the left and a free x on the right – Euge Feb 15 '18 at 02:12
0

Yes because $\lambda(x\cdot x)$ is a coefficient and can be substituted.

Mostafa Ayaz
  • 31,924
0

It is customary in the $\lambda$-calculus to take $\lambda$-abstraction to have lower precedence than function application. That means that the $\lambda x.y\,z$ is read as $\lambda x.(y\,z)$ and not $(\lambda x.y) z$. So your $\lambda x . x\,x$ is read as $\lambda x . (x\,x)$ (no free variables and the term denotes the operation that applies a term to itself) and you would need to put in the brackets if you meant $(\lambda x. x) x$ (third $x$ is free and the term denotes application of the identity function to $x$).

Rob Arthan
  • 48,577
  • sorry, you mean λx.xx = λx.(xx) is closed ? xx is not a free variable, in this case, I see xx as one, why it does not work? – Student Feb 14 '18 at 21:43
  • I've put the spaces that you were expecting in, but, in fact, in the $\lambda$-calculus literature $xy$ is usually read as $x$ applied to $y$ and not a variable with two letters in its name. – Rob Arthan Feb 14 '18 at 21:49