[Overview] [Previous] [Next]

Examples I

The following examples show how these can be used to define more complicated functions. My examples are taken from those in the textbook, but I prefer the notation s(x) to the abbreviation x+1.

Example. Addition of two numbers.
Strictly according to the form, this is:

add(x, z(x)) = g₁(x)
add(x, s(y)) = h(g₂(x,y), g₃(add(x,y)))

By choosing g₁=p₁, g₂=p₁, g₃=s, and h=p₂, we get

add(x, z(x)) = p₁(x)
add(x, s(y)) = p₂(p₁(x,y), s(add(x,y))) which simplifies to add(x, z(x)) = x
add(x, s(y)) = s(add(x,y))

For example, add(3,2) works as follows: add(s(s(s(z(x)))), s(s(z(x))))
s(add(s(s(s(z(x)))), s(z(x))))
s(s(add(s(s(s(z(x)))), z(x))))
s(s(s(s(s(z(x))))))