Arithmetical theorems with λ Calculus

Arithmetical theorems with λ Calculus

6 min read

In this post, I will introduce basic arithmetic with the lens of Lambda Calculus and try to derive some theorems about natural numbers.

We know what it means when a function applies to a number, but what happens when numbers themselves start behaving like functions? Let's start with this. Suppose there is some function \(f\). If this function \(f\) is applied \(n\) number of times to \(x\), then we can notate it by

$$\underset{\text{n times}}{\underbrace{f(f(..f}}(x))) \equiv f^n(x)$$ where \(n\) is a natural number.

So we can say
$$\begin{align}
f^1(x) &= f(x), \\
f^2(x) &= f(f(x)), \\
f^3(x) &= f(f(f(x)))
\end{align}$$ and so on..

What if \(n\) is \(0\)? \(f\) is applied \(0\) number of times to \(x\). Hence

$$f^0(x) = x$$

Before moving ahead, Let me tell you how a function application is written as lambda term.
And the rule is simple, we omit the parenthesis around "\(x\)" in "\(f(x)\)" and write it as just "\(f\ x\)".

Let's now write \(f^n(x)\) in lambda notation, i.e.
$$\begin{align}
f^n(x) &\equiv \overline{n}\ f\ x \\
&or \\
\overline{n}\ f\ x &\equiv \underset{\text{n times}}{\underbrace{(f(f..(f}}\ x))) \label{n1} \tag{n1}
\end{align}$$

What is \(\overline{n}\) here? And how to read the expression \(\overline{n}\ f\ x\)?

  • \(\overline{n}\) (which is \(n\) with bar on top) is Church numeral function associated with the natural number \(n\).

  • \(\overline{n}\ f\ x\) should be read as \((\overline{n}\ f)\ x\) because application in lambda notations is left-associative. Here \(\overline{n}\) is being applied to \(f\), which after application returns a function that gets applied to \(x\). So \(\overline{n}\) is behaving like a higher order function or operator. See examples below:

$$\begin{align}
\overline{0}\ f\ x &= x, \\
\overline{1}\ f\ x &= (f\ x), \\
\overline{2}\ f\ x &= (f\ (f\ x))
\end{align}$$
and so on..

We can constructively create these numerals by Peano's axioms which states:

  1. 0 is a natural number.
  2. If \(n\) is a natural number, then \(n^{+1}\) or \(Succ(n)\) is also a natural number.
    So these axioms states then we can construct all natural numbers using \(0\) and \(Succ\).

Let's write functional definitions for lambda terms associated with \(0\) and \(Succ\) (which are isomorphic to Peano's first two axioms).
$$\begin{align}
\overline{0}\ f\ x &:= x \label{1} \tag{1} \\
Succ\ \overline{n}\ f\ x &:= f\ (\overline{n}\ f\ x) \label{2} \tag{2} \\
\end{align}$$

You can simply understand the above definition of \(Succ\) from following:

Since
$$\underset{\text{n+1 times}}{\underbrace{f(f(..f}}(x))) \equiv f(\underset{\text{n times}}{\underbrace{f(f(..f}}(x))))$$
hence
$$(Succ\ \overline{n})\ f\ x = f\ (\overline{n}\ f\ x)$$
and if we just omit the parenthesis, we obtain \eqref{2}
$$Succ\ \overline{n}\ f\ x = f\ (\overline{n}\ f\ x)$$

Using these constructive terms we can obtain numerals for all natural numbers:
$$\begin{align}
\overline{1} \equiv Succ\ \overline{0} \\
\overline{2} \equiv Succ\ \overline{1} \\
\overline{3} \equiv Succ\ \overline{2} \\
\overline{4} \equiv Succ\ \overline{3}
\end{align}$$

and so on..

I'll omit the bar on top of Church numeral terms from now on. So you should consider all numbers to be church numerals by default in expressions below.

Let's check what \(2\ f\ x\) comes out to be?

$$\begin{align}
2\ f\ x & = Succ\ 1\ f\ x &&\text{(using definition of 2)} \\
& = f\ (1\ f\ x) &&\text{(using definition of Succ)} \\
& = f\ (Succ\ 0\ f\ x) &&\text{(using definition of 1)} \\
& = f\ (f\ ( 0\ f\ x)) &&\text{(using definition of Succ)} \\
& = f\ (f\ x) &&\text{(using definition of 0)} \\
\end{align}$$

which is it ought to be.

Addition

Can we define addition function over these numerals?

We know that
$$Succ\ m = m+1$$
and
$$m+n = (((m\ \underset{\text{n times}}{\underbrace{+1) +1)\ .. +1)}}$$
So
$$Plus\ m\ n = \underset{\text{n times}}{\underbrace{(Succ\ (Succ\ ..(Succ\ }}m)))$$
Hence by \eqref{n1}
$$Plus\ m\ n := n\ Succ\ m \tag{3}$$

Some proofs

$$\begin{align}
Plus\ m\ 0 = 0\ Succ\ m = m \implies m + 0 = m \label{4} \tag{4}
\end{align}$$

$$Succ\ m\ Succ\ n = Succ\ (m\ Succ\ n) \implies n + (m^{+1}) = (n + m)^{+1} \tag{5}$$

We have seen "\(m + 0 = m\)".
Let's try to prove "\(0 + m = m\)" by induction
Hypothesis: \(m\ Succ\ 0 = m\)
Case: \(m = 0\)
$$\begin{align}
Plus\ 0\ 0 = 0 &&\text{(using \eqref{4})}
\end{align}$$
Case: \(m = Succ\ n\)
$$\begin{align}
Plus\ 0\ (Succ\ n) & = (Succ\ n)\ Succ\ 0 && \text{(using definition of Plus)} \\
& = Succ\ n\ Succ\ 0 && \text{(omitting parenthesis)} \\
& = Succ\ (n\ Succ\ 0) && \text{(using definition of Succ)} \\
& = Succ\ n && \text{(using induction hypothesis)}
\end{align}$$
Hence
$$\begin{align}
\begin{split}
Plus\ 0\ m & = m \\
or & \\
m\ Succ\ 0 & = m
\end{split} \label{6} \tag{6}
\end{align}$$

Composition function

The composition function "\(\circ\)" is an infix operator and is defined by

$$Compose\ f\ g\ x \equiv (f\ \circ\ g)\ x := f\ (g\ x) \label{7} \tag{7}$$

Multiplication

Let's define function for multiplication over numerals
We know that
$$m\ \times\ n = 0\ \underset{\text{n times}}{\underbrace{+\ m\ +m\ +\ ..\ +m}}$$
So
$$\begin{align}
Mult\ m\ n & = \underset{\text{n times}}{\underbrace{((m\ Succ)\ ((m\ Succ)..((m\ Succ)}}\ 0))) \\
& = n\ (m\ Succ)\ 0 && \text{(by notation \eqref{n1})}\\
& = (n\ \circ\ m)\ Succ\ 0 && \text{(using \eqref{7} Composition operator def.)} \\
& = (n\ \circ\ m) && \text{(using \eqref{6} ‘m Succ 0 = m')}
\end{align}$$

Hence

$$\begin{align}
Mult\ m\ n &= n\ \circ\ m \label{8} \tag{8}
\end{align}$$

Multiplication of two numerals is just the composition of them.

Power

Let's define power (exponentiation) function for numerals

We know that if \(n\) is a numeral then
$$\begin{align}
\overline{n}\ f\ x &\equiv \underset{\text{n times}}{\underbrace{(f\ (f\ (..(f}}\ x))) \\
&= \underset{\text{n times}}{\underbrace{(f\ \circ f\ \circ\ ..\ \circ\ f)}}\ x && \text{(using \eqref{7} definition of Composition operator)}
\end{align}$$

hence we can say, (by omitting the \(x\) in above equation)
$$\begin{align}
\overline{n}\ f \equiv \underset{\text{n times}}{\underbrace{(f\ \circ f\ \circ\ ..\ \circ\ f)}} \label{9} \tag{9}
\end{align}$$

Again, by definition of power
$$m^n = \underset{\text{n times}}{\underbrace{m\ \times\ m\ \times\ ..\ \times\ m}}$$

Hence we can define \(Power\) function as
$$\begin{align}
Power\ m\ n &= \underset{\text{n times}}{\underbrace{m\ \circ\ m\ \circ\ ..\ \circ\ m}} && \text{(using \eqref{8} definiion of Multiplication)} \\
&= (n\ m) && \text{(using \eqref{9})}
\end{align}$$

Hence
$$\begin{align}
Power\ m\ n = n\ m \label{10} \tag{10}
\end{align}$$

Power operation for two numerals is just the application between them.

Insights

Let's define identity function
$$I\ x = x \tag{11}$$

We know that
$$\begin{align}
0\ n\ x = x && \text{(by definition of 0)}
\end{align}$$
hence, \((0\ n)\) must be equal to Identity function \(I\) so that appying \(x\) to it returns \(x\). So
$$0\ n = I \label{12} \tag{12}$$

Again, we know that
$$\begin{align}
&& 1\ f\ x &= f\ x && \text{(by definition of 1)} \\
or && 1\ f &= f && \text{(omitting x both side)}
\end{align}$$
hence \(1\) is nothing but Identity function \(I\)
$$1 = I \label{13} \tag{13}$$

\eqref{12} & \eqref{13} implies
$$0\ n = 1 \tag{14}$$
If we see above equation in context of \eqref{10} then it states \(Power\ n\ 0 = 1\) or arithmetically

$$\bbox[10px,border:1px solid #777]
{n^0 = 1}
$$

What a classical result!

More theorems?

By composition operator definition \eqref{7},

$$(l\ (m\ n)) \equiv (l\ \circ\ m)\ n$$

If \(l\), \(m\) and \(n\) are numerals then (by \eqref{8} and \eqref{10}) above equation is equivalent to

$$\begin{align}
Power\ (Power\ n\ m)\ l \equiv Power\ n\ (Mult\ m\ l) \label{15} \tag{15}
\end{align}$$

or arithmetically,

$$\bbox[10px,border:1px solid #777]
{(n^m)^l = n^{m\ \times\ l}}
$$

Everything is making sense!! :D

Let's do same in Haskell interactive shell

Launch ghci

Here in shell, we'll define arithmetical operations given by above definitions and do computations using them.

let zero f x = x
let succ n f x = f (n f x)

let one = succ zero
let two = succ one
let three = succ two
let four = succ three

let plus m n = n succ m
let mult m n = n . m
let power m n = n m

let convert n = n (+ 1) 0

We've defined convert function to convert church numeral (which is a function) to number so that we can confirm our computation.

Let's do some computations using defined functions. (in ghci shell)

Prelude> convert (plus two three)   -- 2 + 3
5
Prelude> convert (mult two three)   -- 2 x 3
6
Prelude> convert (power two three)  -- 2 ^ 3
8

Prelude> convert (four . three)     -- 3 x 4
12
Prelude> convert (two three)        -- 3 ^ 2
9
Prelude> convert (three two two)    -- 2 ^ (2 ^ 3)
256

So we saw that, arithmetic operations can be defined in untyped Lambda Calculus without using any prior definition if natural numbers are treated as Church numerals.