@MISC{COMPUT_1.MIZ,
  AUTHOR = {Bancerek, Grzegorz and Rudnicki, Piotr},
  TITLE = {The Set of Primitive Recursive Functions},
  NOTE = {This work has been supported by NSERC Grant OGP9207,
NATO CRG 951368 and TYPES grant IST-1999-29001.},
  SECTION1 = {Preliminaries},
  SECTION2 = {Sets of Compatible Functions},
  SECTION3 = {Homogeneous Relations},
  SECTION4 = {Primitive Recursiveness},
  SECTION5 = {The Set of Primitive Recursive Functions},
  SECTION6 = {Examples},
  DAY = {27},
  MONTH = {July},
  YEAR = {2001},
  ADDRESS1 = {University of Bia{\l}ystok\\Shinshu University, Nagano},
  ADDRESS2 = {University of Alberta\\Edmonton},
  SUMMARY = {We follow \cite{Uspenski60} in defining the set of primitive
recursive functions.  The important helper notion is
the homogeneous function from finite sequences of natural numbers
into natural numbers where homogeneous means that all the sequences
in the domain are of the same length.  The set of all such functions
is then used to define the notion of a set closed under composition
of functions and under primitive recursion.  We call a set primitively
recursively closed iff it contains the initial functions (nullary constant
function returning 0, unary successor and projection functions for all
arities) and is closed under composition and primitive recursion. The
set of primitive recursive functions is then defined as the smallest set
of functions which is primitive recursively closed.  We show
that this set can be obtained by primitive recursive approximation.
We finish with showing that some simple and well known functions are
primitive recursive.}}

