2

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).

Community
  • 1
John
  • 123

1 Answers1

4

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.

MJD
  • 65,394
  • 39
  • 298
  • 580
  • 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? – John May 08 '13 at 18:04
  • 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$. – MJD May 08 '13 at 18:06
  • Sure, but 1 is just syntactical shorthand for $f(x)$ so the last step in your answer could expand to $(f(x)(fx))$ right? – John May 08 '13 at 18:12
  • 1
    No. $1$ is shorthand for $\lambda f.\lambda x. f x$. – MJD May 08 '13 at 18:14
  • Okay. I read your edits and it makes much more sense. Thank you very much! – John May 08 '13 at 18:15