2
$\begingroup$

I realize this is probably a simple question for most people, but it is something that I am just having a hard time understanding. The numbers 1 and 2 is defined as:

$1 = \lambda f. \lambda x. \space \space f \space x$

$2 = \lambda f. \lambda x. \space \space f ( \space f \space x \space)$

And, as I understand it (which could be wrong), the identity for one looks like:

$1 \space f \space x$

But wouldn't this be the same as saying

$1(f(x))$

Which would expand out to

$f(f(x))$

Which to me looks like the definition for 2, but I thought this was supposed to be the identity function. My main source here is Wikipedia (possibly not the best source... lol).

$\endgroup$
1
  • 1
    $\begingroup$ The order of lambdas in your definition of 1 and 2 were swapped; I fixed it for clarity. $\endgroup$ May 8, 2013 at 18:24

1 Answer 1

4
$\begingroup$

By convention, $$1 f x$$ is shorthand for $$((1 f) x),$$ not for $$(1 (f x)).$$


$((1 f) x)$ evaluates as follows: $((1 f) x) = (((\lambda g.\lambda y. g y) f) x) = ((\lambda y. f y) x) = (f x)$, because $1$ is nothing but the identity function.

$((2 f) x)$, on the other hand, evaluates to $(f (f x))$.

The successor function $S$ is $$\lambda n.\lambda f.\lambda x.(f (n f x)).$$

If we calculate $((S 1) f x)$ we get $(f (1 f x)) = (f (f x)) = (2 f x)$, which means that $(S 1)$ is the same function as $2$—that is, if we give $1$ to the successor function $S$, it returns $2$.


$1(f(x))$ does not expand to $f(f(x))$ anyway; it expands to $(\lambda g.\lambda y. g y) (f x)$, which then $\beta$-reduces to $\lambda y. ((f x) y)$, which is $\eta$-equivalent to just $(f x)$. $1$ is nothing but the identity function.

$\endgroup$
5
  • $\begingroup$ Okay, so that sortof makes sense. So I understand that lambda calculus does not have numbers, so what exactly does $((1f)x)$ mean? Or more so, what importance does the 1 play here? $\endgroup$
    – John
    May 8, 2013 at 18:04
  • $\begingroup$ Sorry, I don't understand your questions. The point of the definitions of $1$ and $2$ that you gave is that lambda-calculus does have numbers, and it's possible to define a $+$ function so that $(+ 1 1)$ is the same as $2$. $\endgroup$
    – MJD
    May 8, 2013 at 18:06
  • $\begingroup$ Sure, but 1 is just syntactical shorthand for $f(x)$ so the last step in your answer could expand to $(f(x)(fx))$ right? $\endgroup$
    – John
    May 8, 2013 at 18:12
  • 1
    $\begingroup$ No. $1$ is shorthand for $\lambda f.\lambda x. f x$. $\endgroup$
    – MJD
    May 8, 2013 at 18:14
  • $\begingroup$ Okay. I read your edits and it makes much more sense. Thank you very much! $\endgroup$
    – John
    May 8, 2013 at 18:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .