HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Definition of integers needs explaining

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
definitionintegersexplainingneeds

Problem

Zero and one are defined by the successor function.

$$
\begin{align*}
&0 ≡ λsz.z \\
&1 ≡ λsz.s(z)
\end{align*}
$$

But why? $λsz.z$ is irreducible to a value. If I call this function on some value, I get back $z$, which is merely a variable in itself. If I call the function on two values, I get back the second value, which is not necessarily zero.

And yet we're just assigning the function the value $0$? Why? Why not assign zero to say $λs.(λz.xyt)$. This seems arbitrary.

This is from the arithmetic section of:
http://www.inf.fu-berlin.de/lehre/WS03/alpi/lambda.pdf

Solution

The natural numbers don't exist natively in the world of lambda calculus, and so if we want to use them, we have to define them somehow. You are describing the Church numerals, one possible definition which supports arithmetic. Church defines $n$ to be the function $(s,z) \mapsto s^{(n)}(z)$ that maps a pair $(s,z)$ into an $n$-fold application of $s$ to $z$. In particular, when $n = 0$ we get $(s,z) \mapsto z$.

Why this definition and not any other one? No reason. It is just a common definition, but you can use any other definition you like, or even come up with a new one. This particular definition supports arithmetic – you can define addition, multiplication and so on. See Wikipedia for the details.

Context

StackExchange Computer Science Q#66846, answer score: 5

Revisions (0)

No revisions yet.