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_{1}(x)

add(x, s(y)) = h(g_{2}(x,y), g_{3}(add(x,y)))

By choosing g_{1}=p_{1}, g_{2}=p_{1}, g_{3}=s,
and h=p_{2}, we get

add(x, z(x)) = p_{1}(x)

add(x, s(y)) = p_{2}(p_{1}(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))))))

Copyright © 1996 by David Matuszek

Last modified Apr 18, 1996