This defines the function f by means of a recipe for its computation: Given
any value for the argument n, multiply that value by itself, and then add one.
Since the function is defined in this explicit way, we can compute its values in a
strictly mechanical fashion. To complete the definition of f, we also must specify
its domain. If, for example, we take the domain to be the set of all integers, then
the range of f will be some subset of the set of positive integers.
Since many very complicated functions can be specified this way, we may
well ask to what extent the notation is universal. If a function is defined (that is,
we know the relation between the elements of its domain and its range), can it be
expressed in such a functional form? To answer the question, we must first
clarify what the permissible forms are. For this we introduce some basic
functions, together with rules for building from them some more complicated
ones.
Primitive Recursive Functions
To keep the discussion simple, we will consider only functions of one or two
variables, whose domain is either I, the set of all nonnegative integers, or I × I,
and whose range is in I. In this setting, we start with the basic functions:
1. The zero function z(x) = 0, for all x ∈ I.
2. The successor function s(x), whose value is the integer next in sequence to
x, that is, in the usual notation, s(x) = x +1.
3. The projector functions
p k (x 1 , x 2 ) = x k , k = 1, 2.
There are two ways of building more complicated functions from these:
1. Composition, by which we construct
f (x, y) = h (g 1 (x, y), g 2 (x, y))
from defined functions g 1 ,g 2 ,h.
2. Primitive recursion, by which a function can be defined recursively
any value for the argument n, multiply that value by itself, and then add one.
Since the function is defined in this explicit way, we can compute its values in a
strictly mechanical fashion. To complete the definition of f, we also must specify
its domain. If, for example, we take the domain to be the set of all integers, then
the range of f will be some subset of the set of positive integers.
Since many very complicated functions can be specified this way, we may
well ask to what extent the notation is universal. If a function is defined (that is,
we know the relation between the elements of its domain and its range), can it be
expressed in such a functional form? To answer the question, we must first
clarify what the permissible forms are. For this we introduce some basic
functions, together with rules for building from them some more complicated
ones.
Primitive Recursive Functions
To keep the discussion simple, we will consider only functions of one or two
variables, whose domain is either I, the set of all nonnegative integers, or I × I,
and whose range is in I. In this setting, we start with the basic functions:
1. The zero function z(x) = 0, for all x ∈ I.
2. The successor function s(x), whose value is the integer next in sequence to
x, that is, in the usual notation, s(x) = x +1.
3. The projector functions
p k (x 1 , x 2 ) = x k , k = 1, 2.
There are two ways of building more complicated functions from these:
1. Composition, by which we construct
f (x, y) = h (g 1 (x, y), g 2 (x, y))
from defined functions g 1 ,g 2 ,h.
2. Primitive recursion, by which a function can be defined recursively