View source for Primitive recursive function

<!--
p0746101.png
$#A+1 = 47 n = 0
$#C+1 = 47 : ~/encyclopedia/old_files/data/P074/P.0704610 Primitive recursive function
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

A function from natural numbers to natural numbers which can be obtained from the initial functions

$$ 
s ( x)  =  x + 1,\ \ 
o ( x)  =  0,\ \ 
I _ {m}  ^ {n} ( x _ {1} \dots x _ {n} )  =  x _ {m}  $$

by a finite number of the operations of composition and [[Primitive recursion|primitive recursion]].

Since the initial functions are computable and the operators of superposition and primitive recursion preserve computability, the set of all primitive recursive functions is a subclass of the class of all computable functions (cf. [[Computable function|Computable function]]). Every primitive recursive function is specified by a description of its construction from the initial functions (a primitive recursive description); hence the class of primitive recursive functions is countable. Practically all arithmetic functions used in mathematics for some concrete reason are primitive recursive functions; e.g.  $  x + y $, 
$  x \cdot y $, 
$  x  ^ {y} $, 
$   \mathop{\rm sign} ( x) $, 
$  [ x/y] $(
the remainder from division of  $  x $
by  $  y $), 
$  \pi ( x) $(
the prime number with index  $  x $), 
etc.

A relation  $  P ( x _ {1} \dots x _ {n} ) $
on natural numbers is called a primitive recursive relation if the function  $  g ( x _ {1} \dots x _ {n} ) $, 
equal to 1 if  $  P ( x _ {1} \dots x _ {n} ) $
is true and 0 if  $  P ( x _ {1} \dots x _ {n} ) $
is false, is primitive recursive. One says that the relation  $  P ( x _ {1} \dots x _ {n} , z) $
has been obtained from a relation  $  Q ( x _ {1} \dots x _ {n} , y, z) $
by means of a bounded quantifier if

$$ 
P ( x _ {1} \dots x _ {n} , z)  \iff \ 
\forall y  ( y \leq  z \Rightarrow Q
( x _ {1} \dots x _ {n} , y, z))
$$

or

$$ 
P ( x _ {1} \dots x _ {n} , z)  \iff \ 
\exists y  ( y \leq  z \& Q
( x _ {1} \dots x _ {n} , y, z)).
$$

The class of primitive recursive relations is closed under the application of logical connectives (including negation) and bounded quantifiers.

Suppose that  $  f _ {1} \dots f _ {s + 1 }  $
are  $  n $-
place primitive recursive functions, and let  $  P _ {1} \dots P _ {s} $
be primitive recursive relations such that for any set of argument values at most one of them is true. Then the function

$$ \tag{* }
f ( x _ {1} \dots x _ {n} )  = \ 
\left \{

is primitive recursive.

One says that the function  $  f ( x _ {1} \dots x _ {n} , z) $
has been obtained from an everywhere-defined function  $  g ( x _ {1} \dots x _ {n} , y, z) $
by means of the bounded minimization operator if  $  f ( x _ {1} \dots x _ {n} , z) $
is equal to the minimal  $  y $
such that  $  y \leq  z $
and  $  g ( x _ {1} \dots x _ {n} , y, z) = 0 $, 
and is equal to  $  z + 1 $
otherwise. The class of primitive recursive functions is closed under bounded minimization operators.

A function  $  \Phi ( y, x _ {1} \dots x _ {n} ) $
is called universal for the class of  $  n $-
place primitive recursive functions if for each such function  $  f ( x _ {1} \dots x _ {n} ) $
there is a natural number  $  k $
such that

$$ 
f ( x _ {1} \dots x _ {n} )  = \ 
\Phi ( k, x _ {1} \dots x _ {n} ).
$$

There exists a universal function for every  $  n \geq  1 $, 
but it need not be primitive recursive.

Every recursively enumerable set is the range of values of a primitive recursive function; every recursively enumerable relation  $  R ( x _ {1} \dots x _ {n} ) $
can be represented as  $  \exists y  A ( y, x _ {1} \dots x _ {n} ) $, 
where  $  A $
is a primitive recursive relation. Every primitive recursive function can be represented in formal arithmetic (cf. [[Arithmetic, formal|Arithmetic, formal]]); i.e. for each primitive recursive function  $  f ( x _ {1} \dots x _ {n} ) $
there is an arithmetical formula  $  F ( y, x _ {1} \dots x _ {n} ) $
such that for all natural numbers  $  k _ {1} \dots k _ {n} , m $, 
the formula  $  F ( \overline{m}\; , \overline{k}\; _ {1} \dots \overline{k}\; _ {n} ) $
is derivable in formal arithmetic if  $  f ( k _ {1} \dots k _ {n} ) = m $, 
while  $  \neg F ( \overline{m}\; , \overline{k}\; _ {1} \dots \overline{k}\; _ {n} ) $
is derivable if  $  f ( k _ {1} \dots k _ {n} ) \neq m $. 
(Here  $  \overline{k}\; _ {1} \dots \overline{k}\; _ {n} , \overline{m}\; $
are arithmetical terms reflecting the natural numbers  $  k _ {1} \dots k _ {n} , m $
in formal arithmetic.) This fact takes a central position in the proof of the incompleteness of formal arithmetic (cf. [[#References|[4]]]).

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  V.A. Uspenskii,   "Leçons sur les fonctions calculables" , Hermann  (1966)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  A.I. Mal'tsev,   "Algorithms and recursive functions" , Wolters-Noordhoff  (1970)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  H. Rogers jr.,   "Theory of recursive functions and effective computability" , McGraw-Hill  (1967)  pp. 164–165</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  E. Mendelson,   "Introduction to mathematical logic" , v. Nostrand  (1964)</TD></TR></table>

====Comments====
The fact that the function (*) is primitive recursive under the given assumptions is often rephrased as: the class of primitive recursive functions is closed under  "definition by cases" .

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  C. Calude,   "Theories of computational complexity" , North-Holland  (1988)</TD></TR></table>