# How the the Identity in Church Numerals not the 'succ' function (ie. x + 1)

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

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

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.

• 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 8, 2013 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 8, 2013 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 8, 2013 at 18:12
• No. $1$ is shorthand for $\lambda f.\lambda x. f x$.
– MJD
May 8, 2013 at 18:14
• Okay. I read your edits and it makes much more sense. Thank you very much!
– John
May 8, 2013 at 18:15