Church Numerals make all numbers the results of funtions

(written by lawrence krubner, however indented passages are often quotes). You can contact lawrence at: lawrence@krubner.com, or follow me on Twitter.

Lately I’ve been wondering a lot about where numbers come from. My research lead me to this interesting post about Church Numerals.

Assume we have a programming language that doesn’t support numbers or booleans: a lambda is
the only value it provides. It is an interesting question whether we can nonetheless create some
system that allows us to count, add, multiply, and do all the other things we do with numbers.
Church numerals use lambdas to create a representation of numbers. The idea is closely related to
the functional representation of natural numbers, i.e. to have a natural number representing “zero”
and a function “succ” that returns the successor of the natural number it was given. The choice of
“zero” and “succ” is arbitrary, all that matters is that there is a zero and that there is a function
that can provide the successor.
Church numerals are an extension of this. All Church numerals are functions with two parameters:
λf . λx . something
The first parameter, f, is the successor function that should be used. The second parameter, x, is
the value that represents zero. Therefore, the Church numeral for zero is:
C0 = λf . λx . x
Whenever it is applied, it returns the value representing zero. The Church numeral for one applies
the successor function to the value representing zero exactly once:
C1 = λf . λx . fx
The Church numerals that follow just have additional applications of the successor function:
C2 = λf . λx . f(fx)
C3 = λf . λx . f(f(fx))
C4 = λf . λx . f(f(f(fx)))
Cn = λf . λx . fnx
It is important to note that in this minimal lambda calculus, we can’t really do very much with these
Church numerals. We can count and add and multiply (more about that below), but to understand
the result, we have to count the applications of the successor function.
If we had a language that were a little more powerful, however, we could do the following:
S = λr .“ring the small bell (ding) and apply r”
Z = λr .“ring the big bell (dong)”

The application of C4 to S and Z would then produce “ding ding ding ding dong”, since C4 is
f(f(f(fx))).
If we add numbers to our language, then we can convert Church numerals to decimal numbers if we
define S and Z as follows:
S = λr . 1 + r()
Z = λr . 0
Now C4SZ is equivalent to 1+1+1+1+0, so it actually evaluates to 4. Without using “side effects”
like ringing bells or being able to turn Church numerals into decimal numbers, we have to count the
applications – there’s no way around that – and this violates the encapsulation of functions. We do
not treat lambdas as black boxes anymore, we look at their bodies and count…

1.1 Addition
We can easily perform addition using Church numerals if we realize that they do everything relative
to the value they consider zero. C1 is one more than C0, and C4 is one more than C3; therefore, C1
represents 1 relative to C0, and C4 represents 1 relative to C3.
If we want to add 3 to 4 using Church numerals, we simply create a new Church numeral and use
one of the summands as zero for the other:
C3+4 = λf . λx . C3 f (C4 f x)
C3+4 is a function with two parameters – just like any Church numeral – but it applies C3 to f, the
successor function, and C4fx, which now acts as value for zero. Written out, C3+4 is (parameters
have been renamed to avoid shadowing)
C3+4 = λf . λx . (λf3 . λx3 . f3(f3(f3x3))) f (λf4 . λx4 . f4(f4(f4(f4x4))) f x)
= λf . λx . f(f(f(λf4 . λx4 . f4(f4(f4(f4x4))) f x)))
= λf . λx . f(f(f(f(f(f(fx))))))
= C7
We can therefore define a function add that takes two Church numerals M and N and returns the
sum of them:
add = λM . λN . λf . λx . N f (M f x)
add C4 C7 = C7
add actually has four lambdas, not just two for M and N, since the result is a Church numeral,
which is a function with two parameters.

Post external references

  1. 1
    http://www.cs.rice.edu/~javaplt/311/Readings/supplemental.pdf
Source