In Reference 7 we develop the recursive functions of a class of symbolic expressions in terms of the conditional expression and recursive function formalism.

As an example of the use of recursive function definitions, we
shall give recursive definitions of a number of functions over the
integers. We do this for three reasons: to help the reader familiarize
himself with recursive definition, to show how much simpler in
practice our methods of recursive definition are than either Turing
machines or Kleene's formalism, and to prove that any partial
recursive function (Kleene) on the non-negative integers is in
where contains only the successor function and the predicate
equality.

Let *I* be the set of non-negative integers {0,1,2,...} and
denote the successor of an integer *n* by *n*' and denote the equality of
integers and by . If we define functions *succ* and *eq* by

then we write = . We are interested in . Clearly all functions in will have either integers or truth values as values.

First we define the predecessor function *pred*(not defined for *n* = 0) by

We shall denote *pred*(*n*) by

Now we define the sum

the product

the difference

which is defined only for The inequality predicate is defined by

The strict inequality *m* < *n* is defined by

The integer valued quotient *m*/*n* is defined by

The remainder on dividing *m* by *n* is defined by

and the divisibility of a number *n* by a number *m*,

The primeness of a number is defined by

where

The Euclidean algorithm defines the greatest common divisor, and we write

and we can define Euler's -function by

where

is the number of numbers less than *n* and relatively prime to *n*.

The above shows that our form of recursion is a convenient way of
defining arithmetical functions. We shall see how some of the
properties of the arithmetical functions can conveniently be derived
in this formalism in a later section.

Wed May 1 20:03:21 PDT 1996