<p>In $\lambda$-calculus the number $n$ is represented by the function which takes as input a function $f$ and outputs the $n$-fold composition $$f^n = \underbrace{f \circ f \circ \cdots \circ f}_n.$$ In a way, the number $n$ is represented by the operation "repeat $n$ times".</p>

CC BY-SA 3.0
2016-09-21T15:43:33.943Z
2016-09-21T15:43:33.943Z
Andrej Bauer
<p>The natural numbers, or counting numbers, are 0,1,2,3,… .</p>

<p>Notice that any natural numebr is either 0 or 1 more an exisiting natural
number. With this idea in hand, we can abstractly say that the natural are
consist of something called “zero” or any natural <code>n</code> prefixed with “suc”
─ which abstracts the +1 operation.</p>

<p>Okay, so we have an abstract notion of natural numbers. How do we implement
this idea concretely; i.e., is there something we can point to and say:
that is a natural number and it can be constructed in such-and-such way!</p>

<p>Below are two routes.</p>

<h1>at home</h1>

<p>If we're at home and our philosophically-inclined room-mate inquires about the
nature of the naturals ─pun somewhat intended─, then we reply as follows.</p>

<p>“While in this room, a stack of books is henceforth known as a
natural number”, we explain fancily.</p>

<p>“Alright, that's a fine and dandy renaming”, our room-mate says suspiciously.
He continues, “how does one actually obtain one of these items?”</p>

<p>“An empty stack, with no books at all, will be called <code>zero</code>”,
we says grinnedly.</p>

<p>“Yet another renaming, fine. So these <code>natural number</code> have only one thing?
Lame!”, our room-mate says disinterestedly.</p>

<p>We continue with cheerful optimism,
“If we have a stack of books then placing any
new book on top results is
obviously another stack of books, which we are calling <code>natural numbers</code>.”.</p>

<p>“Oh, so what others call the number <code>three</code>, we, in this room, identify it
to <em>denote</em> one book on top of another on top of yet another which rests on
the floor!?”, inquires our now ecstatic room-mate.</p>

<p>“Moreover,” he continues,
“if we write <code>Zero</code> for any empty stack and <code>Succ</code> for the operation
of placing a new book on top of an existing stack, say <code>n</code>, then all these
Numbers are either <code>Zero</code> or <code>Succ n</code> for an existing number, erm, stack <code>n</code>!?”</p>

<h1>at the math lab</h1>

<p>The setting is our
math lab ─we meant to become drug dealers but our heavy accent led us
from the world of meth to math ;)</p>

<p>Our lab mates inquire about the nature of counting numbers but they care not
for materials and reject our above argument. They live in an ideal world with
perfect angles and curves and functions, but want to improve their understanding
of natural numbers.</p>

<p>“Do you know the identity function”, we ask gleefully?</p>

<p>“But of course! It is the most fundamental of all!
I have asked for your help and you inquire about my understanding
of the function that takes an argument and returns it unchanged!?
Preposterous!”, replies our lab-mate in a condescending tone.</p>

<p>“I am sorry to offend, but perhaps you can remind me. What precisely
is the rudimentary existence of function?”, we ask curiously.</p>

<p>“If I must! Well, the identity function is known as <code>Id</code> and is defined by
<code>Id = λ x.x</code>, it takes a function and leaves it unchanged.” Explains our
lab mate. “Do you follow?” Yes, we nod politely.
He/she continues, “if you have two functions, call them <code>f</code> and <code>g</code>,
then you can do them in-sequence: <code>f</code> after <code>g</code>. We denote this by a little
circle and define it, <code>f ∘ g = λ x. f (g x)</code>.”
Doubtfully he/she continues, “it's like doing an operation in real life called
<code>g</code> a given input <code>x</code> then taking the result and doing the operation called <code>g</code>. ” We smile; he/she sighs.</p>

<p>“Thank-you, now I am equipped to explain numbers to you in a language you
understand.” We write the following on a chalkboard, and all are eventually pleased.</p>

<p>(0) The naturals numbers are “higher-order functions”, they take functions as
inputs and return functions as outputs.</p>

<p>(1)
There is a natural called “Zero” and it is defined by
$$ Zero = λ f . Id  $$</p>

<p>(2)
For any natural number <code>n</code>, we can form a new one by an operation “Succ”:
$$ Succ \ n = λ f . f ∘ n $$</p>

<p>“OH! I get it now”, our induction-friendly lab-mate exclaims.
“The natural number three that others use is <em>denoted</em> by the higher-order
function <code>three = λ f . f ∘ f ∘ f</code>!?”
He/she continues in her/his excitement,
“If we write <code>fⁿ</code> for the <code>n</code>-fold composition of <code>f</code> with it-self, i.e.,
<code>f ∘ f ∘ ⋯ ∘ f</code>, <code>n</code>-times, then a natural number <code>n</code> is <em>denoted</em> by the
operation <code>λ f . fⁿ</code>! And this is the relation between our denotation and
the numbers ℕ others use daily, eh? Pretty clever for a layman.”</p>

<p>We smile, and make an excuse to leave.</p>

CC BY-SA 3.0
2016-09-18T00:43:33.170Z
2016-09-18T00:43:33.170Z
Musa Al-hassy
<p>Consider the first two Church numbers:</p>

<p>$\mathbf{0}=\lambda a.\lambda b.b$</p>

<p>$\mathbf{1}=\lambda a.\lambda b.(a)b$</p>

<p>and the successor function:</p>

<p>$\mathbf{Suc}=\lambda a.\lambda b.\lambda c.(b)((a) b)c$.</p>

<p>I do not understand how to interprete either of them. If I am correct, the successor function applied to a Church number returns the next Church number. But how can a function represent a number?</p>

<p>Comment - If I apply $\mathbf{1}$ to a number $\alpha$, I obtain</p>

<p>$(\lambda a.\lambda b.(a)b)\alpha\rightarrow_\beta \lambda b.(\alpha)b\rightarrow_\beta \alpha$,</p>

<p>which corresponds to $f(\alpha)=\alpha$.</p>

CC BY-SA 3.0
2016-09-17T22:45:21.710Z
Why is my question downvoted? I tried to state it as clearly as possible. Would it be more suited for the _Computer science SE_? In that case, I would like to request a migration.
Karlo
CC BY-SA 3.0
2016-09-22T00:11:07.207Z
Please read the [help/on-topic] carefully to understand what questions are suitable here.  If you'd like it to be migrated, flag it for moderator attention and ask them to migrate it, using "flag" under the question.  But this question might not be so well-received at CS.SE either, as we have an expectation there that you try to solve your question on your own by reading standard resources before asking and show us in the question what self-study and attempts you've made.  This topic is well-documented in standard textbooks.
D.W.
CC BY-SA 3.0
2016-09-22T22:57:24.430Z
@D.W. OK, sorry for the inconvenience. I had missed that the question should be research-level.
Karlo
CC BY-SA 3.0
2016-09-23T18:00:15.840Z
I flagged it for deletion.
Karlo
<lambda-calculus>
How to interpret Church numbers and the successor function in Lambda calculus
Karlo
# How to interpret Church numbers and the successor function in Lambda calculus

(Asked by: username_0 on 2016-09-17)

Consider the first two Church numbers:

$\mathbf{0}=\lambda a.\lambda b.b$

$\mathbf{1}=\lambda a.\lambda b.(a)b$

and the successor function:

$\mathbf{Suc}=\lambda a.\lambda b.\lambda c.(b)((a) b)c$.

I do not understand how to interprete either of them. If I am correct, the successor function applied to a Church number returns the next Church number. But how can a function represent a number?

Comment - If I apply $\mathbf{1}$ to a number $\alpha$, I obtain

$(\lambda a.\lambda b.(a)b)\alpha\rightarrow\_\beta \lambda b.(\alpha)b\rightarrow\_\beta \alpha$,

which corresponds to $f(\alpha)=\alpha$.

**Tags:** lambda-calculus
> **Comments:**
> **username_0**: Why is my question downvoted? I tried to state it as clearly as possible. Would it be more suited for the _Computer science SE_? In that case, I would like to request a migration.  
> **username_1**: Please read the [help/on-topic] carefully to understand what questions are suitable here.  If you'd like it to be migrated, flag it for moderator attention and ask them to migrate it, using "flag" under the question.  But this question might not be so well-received at CS.SE either, as we have an expectation there that you try to solve your question on your own by reading standard resources before asking and show us in the question what self-study and attempts you've made.  This topic is well-documented in standard textbooks.  
> **username_0**: @D.W. OK, sorry for the inconvenience. I had missed that the question should be research-level.  
> **username_0**: I flagged it for deletion.  

---

## 2 answers

### Answer by username_2 on 2016-09-21. Score: 5

In $\lambda$-calculus the number $n$ is represented by the function which takes as input a function $f$ and outputs the $n$-fold composition $$f^n = \underbrace{f \circ f \circ \cdots \circ f}\_n.$$ In a way, the number $n$ is represented by the operation "repeat $n$ times".


---

### Answer by username_3 on 2016-09-18. Score: 3

The natural numbers, or counting numbers, are 0,1,2,3,… .

Notice that any natural numebr is either 0 or 1 more an exisiting natural
number. With this idea in hand, we can abstractly say that the natural are
consist of something called “zero” or any natural `n` prefixed with “suc”
─ which abstracts the +1 operation.

Okay, so we have an abstract notion of natural numbers. How do we implement
this idea concretely; i.e., is there something we can point to and say:
that is a natural number and it can be constructed in such-and-such way!

Below are two routes.

# at home

If we're at home and our philosophically-inclined room-mate inquires about the
nature of the naturals ─pun somewhat intended─, then we reply as follows.

“While in this room, a stack of books is henceforth known as a
natural number”, we explain fancily.

“Alright, that's a fine and dandy renaming”, our room-mate says suspiciously.
He continues, “how does one actually obtain one of these items?”

“An empty stack, with no books at all, will be called `zero`”,
we says grinnedly.

“Yet another renaming, fine. So these `natural number` have only one thing?
Lame!”, our room-mate says disinterestedly.

We continue with cheerful optimism,
“If we have a stack of books then placing any
new book on top results is
obviously another stack of books, which we are calling `natural numbers`.”.

“Oh, so what others call the number `three`, we, in this room, identify it
to *denote* one book on top of another on top of yet another which rests on
the floor!?”, inquires our now ecstatic room-mate.

“Moreover,” he continues,
“if we write `Zero` for any empty stack and `Succ` for the operation
of placing a new book on top of an existing stack, say `n`, then all these
Numbers are either `Zero` or `Succ n` for an existing number, erm, stack `n`!?”

# at the math lab

The setting is our
math lab ─we meant to become drug dealers but our heavy accent led us
from the world of meth to math ;)

Our lab mates inquire about the nature of counting numbers but they care not
for materials and reject our above argument. They live in an ideal world with
perfect angles and curves and functions, but want to improve their understanding
of natural numbers.

“Do you know the identity function”, we ask gleefully?

“But of course! It is the most fundamental of all!
I have asked for your help and you inquire about my understanding
of the function that takes an argument and returns it unchanged!?
Preposterous!”, replies our lab-mate in a condescending tone.

“I am sorry to offend, but perhaps you can remind me. What precisely
is the rudimentary existence of function?”, we ask curiously.

“If I must! Well, the identity function is known as `Id` and is defined by
`Id = λ x.x`, it takes a function and leaves it unchanged.” Explains our
lab mate. “Do you follow?” Yes, we nod politely.
He/she continues, “if you have two functions, call them `f` and `g`,
then you can do them in-sequence: `f` after `g`. We denote this by a little
circle and define it, `f ∘ g = λ x. f (g x)`.”
Doubtfully he/she continues, “it's like doing an operation in real life called
`g` a given input `x` then taking the result and doing the operation called `g`. ” We smile; he/she sighs.

“Thank-you, now I am equipped to explain numbers to you in a language you
understand.” We write the following on a chalkboard, and all are eventually pleased.

(0) The naturals numbers are “higher-order functions”, they take functions as
inputs and return functions as outputs.

(1)
There is a natural called “Zero” and it is defined by
$$ Zero = λ f . Id $$

(2)
For any natural number `n`, we can form a new one by an operation “Succ”:
$$ Succ \ n = λ f . f ∘ n $$

“OH! I get it now”, our induction-friendly lab-mate exclaims.
“The natural number three that others use is *denoted* by the higher-order
function `three = λ f . f ∘ f ∘ f`!?”
He/she continues in her/his excitement,
“If we write `fⁿ` for the `n`-fold composition of `f` with it-self, i.e.,
`f ∘ f ∘ ⋯ ∘ f`, `n`-times, then a natural number `n` is *denoted* by the
operation `λ f . fⁿ`! And this is the relation between our denotation and
the numbers ℕ others use daily, eh? Pretty clever for a layman.”

We smile, and make an excuse to leave.


---

