Editing Primitive recursive function (section)

== Examples ==

{{unordered list

|<math>C_0^1</math> is a 1-ary function which returns <math>0</math> for every input: <math>C_0^1(x) = 0</math>.

|<math>C_1^1</math> is a 1-ary function which returns <math>1</math> for every input: <math>C_1^1(x) = 1</math>.

|<math>C_3^0</math> is a 0-ary function, i.e. a constant: <math>C_3^0 = 3</math>.

|<math>P_1^1</math> is the identity function on the natural numbers: <math>P_1^1(x) = x</math>.

|<math>P_1^2</math> and <math>P_2^2</math> is the left and right projection on natural number pairs, respectively: <math>P_1^2(x,y) = x</math> and <math>P_2^2(x,y) = y</math>.

|<math>S \circ S</math> is a 1-ary function that adds 2 to its input, <math>(S \circ S)(x) = x+2</math>.

|<math>S \circ C_0^1</math> is a 1-ary function which returns 1 for every input: <math>(S \circ C_0^1)(x) = S(C_0^1(x)) = S(0) = 1</math>. That is, <math>S \circ C_0^1</math> and <math>C_1^1</math> are the same function: <math>S \circ C_0^1 = C_1^1</math>. In a similar way, every <math>C_n^k</math> can be expressed as a composition of appropriately many <math>S</math> and <math>C_0^k</math>. Moreover, <math>C_0^k</math> equals <math>C_0^1 \circ P_1^k</math>, since <math>C_0^k(x_1,\ldots,x_k) = 0 = C_0^1(x_1) = C_0^1(P_1^k(x_1,\ldots,x_k)) = (C_0^1 \circ P_1^k)(x_1,\ldots,x_k)</math>. For these reasons, some authors<ref>E.g.: {{citation | author=Henk Barendregt | author-link=Henk Barendregt | contribution=Functional Programming and Lambda Calculus | pages=321&ndash;364 | isbn=0-444-88074-7 | editor=Jan van Leeuwen | editor-link=Jan van Leeuwen | title=Formal Models and Semantics | publisher=Elsevier | series=Handbook of Theoretical Computer Science | volume=B | year=1990}} Here: 2.2.6 ''initial functions'', Def.2.2.7 ''primitive recursion'', p.331-332.</ref> define <math>C_n^k</math> only for <math>n = 0</math> and <math>k = 1</math>.
}}

===Addition===

A definition of the 2-ary function <math>Add</math>, to compute the sum of its arguments, can be obtained using the primitive recursion operator <math>\rho</math>. To this end, the well-known equations 
:<math>\begin{array}{rcll}
0+y & = & y & \text{ and} \\
S(x)+y & = & S(x+y) & . \\
\end{array}</math>
are "rephrased in primitive recursive function terminology": In the definition of <math>\rho(g,h)</math>, the first equation suggests to choose <math>g = P_1^1</math> to obtain <math>Add(0,y) = g(y) = y</math>; the second equation suggests to choose <math>h = S \circ P_2^3</math> to obtain <math>Add(S(x),y) = h(x,Add(x,y),y) = (S \circ P_2^3)(x,Add(x,y),y) = S(Add(x,y))</math>. Therefore, the addition function can be defined as <math>Add = \rho(P_1^1,S \circ P_2^3)</math>. As a computation example,
:<math>\begin{array}{lll}
& Add(1,7) \\
= & \rho(P_1^1,S \circ P_2^3) \; (S(0),7) & \text{ by Def. } Add, S \\
= & (S \circ P_2^3)(0,Add(0,7),7) & \text{ by case } \rho(g,h) \; (S(...),...) \\
= & S(Add(0,7)) & \text{ by Def. } \circ, P_2^3 \\
= & S( \; \rho(P_1^1,S \circ P_2^3) \; (0,7) \; ) & \text{ by Def. } Add \\
= & S(P_1^1(7)) & \text{ by case } \rho(g,h) \; (0,...) \\
= & S(7) & \text{ by Def. } P_1^1 \\
= & 8 & \text{ by Def. } S . \\ 
\end{array}</math>

===Doubling===

Given <math>Add</math>, the 1-ary function <math>Add \circ (P_1^1,P_1^1)</math> doubles its argument, <math>(Add \circ (P_1^1,P_1^1))(x) = Add(x,x) = x+x</math>.

===Multiplication===

In a similar way as addition, multiplication can be defined by <math>Mul = \rho(C_0^1,Add \circ(P_2^3,P_3^3))</math>. This reproduces the well-known multiplication equations: 
:<math>\begin{array}{lll}
& Mul(0,y) \\
= & \rho(C_0^1,Add \circ(P_2^3,P_3^3)) \; (0,y) & \text{ by Def. } Mul \\
= & C_0^1(y) & \text{ by case } \rho(g,h) \; (0,...)\\
= & 0 & \text{ by Def. } C_0^1 . \\
\end{array}</math> 
and 
:<math>\begin{array}{lll}
& Mul(S(x),y) \\
= & \rho(C_0^1,Add \circ(P_2^3,P_3^3)) \; (S(x),y) & \text{ by Def. } Mul \\
= & (Add \circ(P_2^3,P_3^3)) \; (x,Mul(x,y),y) & \text{ by case } \rho(g,h) \; (S(...),...) \\
= & Add(Mul(x,y),y) & \text{ by Def. } \circ, P_2^3, P_3^3 \\
= & Mul(x,y)+y & \text{ by property of } Add . \\
\end{array}</math>

===Predecessor===

The predecessor function acts as the "opposite" of the successor function and is recursively defined by the rules <math>Pred(0) = 0</math> and <math>Pred(S(n)) = n</math>. A primitive recursive definition is <math>Pred = \rho(C_0^0, P_1^2)</math>. As a computation example,
:<math>\begin{array}{lll}
& Pred(8) \\
= & \rho(C_0^0, P_1^2) \; (S(7)) & \text{ by Def. } Pred, S \\
= & P_1^2(7,Pred(7)) & \text{ by case } \rho(g,h) \; (S(...),...) \\
= & 7 & \text{ by Def. } P_1^2 . \\
\end{array}</math>

===Truncated subtraction===

The limited subtraction function (also called "[[monus]]", and denoted "<math>\stackrel.-</math>") is definable from the predecessor function. It satisfies the equations 
:<math>\begin{array}{rcll}
y \stackrel.- 0 & = & y & \text{and} \\
y \stackrel.- S(x) & = & Pred(y \stackrel.- x) & . \\
\end{array}</math>
Since the recursion runs over the second argument, we begin with a primitive recursive definition of the reversed subtraction, <math>RSub(y,x) = x \stackrel.- y</math>. Its recursion then runs over the first argument, so its primitive recursive definition can be obtained, similar to addition, as <math>RSub = \rho(P_1^1, Pred \circ P_2^3)</math>. To get rid of the reversed argument order, then define <math>Sub = RSub \circ (P_2^2,P_1^2)</math>. As a computation example,
:<math>\begin{array}{lll}
& Sub(8,1) \\
= & (RSub \circ (P_2^2,P_1^2)) \; (8,1) & \text{ by Def. } Sub \\
= & RSub(1,8) & \text{ by Def. } \circ, P_2^2, P_1^2 \\
= & \rho(P_1^1, Pred \circ P_2^3) \; (S(0),8) & \text{ by Def. } RSub, S \\
= & (Pred \circ P_2^3) \; (0,RSub(0,8),8) & \text{ by case } \rho(g,h) \; (S(...),...) \\
= & Pred(RSub(0,8)) & \text{ by Def. } \circ, P_2^3 \\
= & Pred( \; \rho(P_1^1, Pred \circ P_2^3) \; (0,8) \; ) & \text{ by Def. } RSub \\
= & Pred(P_1^1(8)) & \text{ by case } \rho(g,h) \; (0,...) \\
= & Pred(8) & \text{ by Def. } P_1^1 \\
= & 7 & \text{ by property of } Pred . \\
\end{array}</math>

=== Converting predicates to numeric functions ===

In some settings it is natural to consider primitive recursive functions that take as inputs tuples that mix numbers with [[truth value]]s (that is <math>t</math> for true and <math>f</math> for false),{{Citation needed|date=January 2025 |reason=Kleene never considers mixed domains - see p.226 where he lists the 4 types of functions he considers. Using N to represent the naturals, and T to represent the truth values: (a) N to N (b) N to T (c) T oto T (d) T to N}} or that produce truth values as outputs.{{sfn|Kleene|1952|pp=226–227}} This can be accomplished by identifying the truth values with numbers in any fixed manner.  For example, it is common to identify the truth value <math>t</math> with the number <math>1</math> and the truth value <math>f</math> with the number <math>0</math>.  Once this identification has been made, the [[indicator function|characteristic function]] of a set <math>A</math>, which always returns <math>1</math> or <math>0</math>, can be viewed as a predicate that tells whether a number is in the set <math>A</math>.  Such an identification of predicates with numeric functions will be assumed for the remainder of this article.

=== Predicate "Is zero" ===

As an example for a primitive recursive predicate, the 1-ary function <math>IsZero</math> shall be defined such that <math>IsZero(x) = 1</math> if <math>x = 0</math>, and 
<math>IsZero(x) = 0</math>, otherwise. This can be achieved by defining <math>IsZero = \rho(C_1^0,C_0^2)</math>. Then, <math>IsZero(0) = \rho(C_1^0,C_0^2)(0) = C_1^0(0) = 1</math> and e.g. <math>IsZero(8) = \rho(C_1^0,C_0^2)(S(7)) = C_0^2(7,IsZero(7)) = 0</math>.

=== Predicate "Less or equal" ===

Using the property <math>x \leq y \iff x \stackrel.- y = 0</math>, the 2-ary function <math>Leq</math> can be defined by <math>Leq = IsZero \circ Sub</math>. Then <math>Leq(x,y) = 1</math> if <math>x \leq y</math>, and <math>Leq(x,y) = 0</math>, otherwise. As a computation example,
:<math>\begin{array}{lll}
& Leq(8,3) \\
= & IsZero(Sub(8,3)) & \text{ by Def. } Leq \\
= & IsZero(5) & \text{ by property of } Sub \\
= & 0  & \text{ by property of } IsZero \\
\end{array}</math>

=== Predicate "Greater or equal" ===

Once a definition of <math>Leq</math> is obtained, the converse predicate can be defined as <math>Geq = Leq \circ (P_2^2,P_1^2)</math>. Then, <math>Geq(x,y) = Leq(y,x)</math> is true (more precisely: has value 1) if, and only if, <math>x \geq y</math>.

=== If-then-else ===

The 3-ary if-then-else operator known from programming languages can be defined by <math>\textit{If} = \rho(P_2^2,P_3^4)</math>. Then, for arbitrary <math>x</math>,
:<math>\begin{array}{lll}
& \textit{If}(S(x),y,z) \\
= & \rho(P_2^2,P_3^4) \; (S(x),y,z) & \text{ by Def. } \textit{If} \\
= & P_3^4(x,\textit{If}(x,y,z),y,z) & \text{ by case } \rho(S(...),...) \\
= & y & \text{ by Def. } P_3^4 \\
\end{array}</math>
and 
:<math>\begin{array}{lll}
& \textit{If}(0,y,z) \\
= & \rho(P_2^2,P_3^4) \; (0,y,z) & \text{ by Def. } \textit{If} \\
= & P_2^2(y,z) & \text{ by case } \rho(0,...) \\
= & z & \text{ by Def. } P_2^2 . \\
\end{array}</math>.
That is, <math>\textit{If}(x,y,z)</math> returns the then-part, <math>y</math>, if the if-part, <math>x</math>, is true, and the else-part, <math>z</math>, otherwise.

=== Junctors ===

Based on the <math>\textit{If}</math> function, it is easy to define logical junctors. For example, defining <math>And = \textit{If} \circ (P_1^2,P_2^2,C_0^2)</math>, one obtains <math>And(x,y) = \textit{If}(x,y,0)</math>, that is, <math>And(x,y)</math> is true [[if, and only if]], both <math>x</math> and <math>y</math> are true ([[logical conjunction]] of <math>x</math> and <math>y</math>).

Similarly, <math>Or = \textit{If} \circ (P_1^2,C_1^2,P_2^2)</math> and <math>Not = \textit{If} \circ (P_1^1,C_0^1,C_1^1)</math> lead to appropriate definitions of [[disjunction]] and [[negation]]: <math>Or(x,y) = \textit{If}(x,1,y)</math> and <math>Not(x) = \textit{If}(x,0,1)</math>.

=== Equality predicate ===

Using the above functions <math>Leq</math>, <math>Geq</math> and <math>And</math>, the definition <math>Eq = And \circ (Leq, Geq)</math> implements the equality predicate. In fact, <math>Eq(x,y) = And( Leq(x,y) , Geq(x,y) )</math> is true if, and only if, <math>x</math> equals <math>y</math>.

Similarly, the definition <math>Lt = Not \circ Geq</math> implements the predicate "less-than", and <math>Gt = Not \circ Leq</math> implements "greater-than".

=== Other operations on natural numbers ===

[[Exponentiation]] and [[primality test]]ing are primitive recursive. Given primitive recursive functions <math>e</math>, <math>f</math>, <math>g</math>, and <math>h</math>, a function that returns the value of <math>g</math> when <math>e \leq f</math> and the value of <math>h</math> otherwise is primitive recursive.

=== Operations on integers and rational numbers ===

By using [[Gödel numbering]]s, the primitive recursive functions can be extended to operate on other objects such as integers and [[rational number]]s.  If integers are encoded by Gödel numbers in a standard way, the arithmetic operations including addition, subtraction, and multiplication are all primitive recursive.  Similarly, if the rationals are represented by Gödel numbers then the [[Field (mathematics)|field]] operations are all primitive recursive.

=== Some common primitive recursive functions ===
The following examples and definitions are from {{harvtxt|Kleene|1952|pp=222–231}}. Many appear with proofs. Most also appear with similar names, either as proofs or as examples, in {{harvtxt|Boolos|Burgess|Jeffrey|2002|pp=63–70}} they add the logarithm lo(x, y) or lg(x, y) depending on the exact derivation.

In the following the mark " ' ", e.g. a', is the primitive mark meaning "the successor of", usually thought of as " +1", e.g. a +1 =<sub>def</sub> a'. The functions 16–20 and #G are of particular interest with respect to converting primitive recursive predicates to, and extracting them from, their "arithmetical" form expressed as [[Gödel number]]s.

:# Addition: a+b
:# Multiplication: a×b
:# Exponentiation: a<sup>b</sup>
:# Factorial a! : 0! = 1, a'! = a!×a'
:# pred(a): (Predecessor or decrement): If a > 0 then a−1 else 0
:# Proper subtraction a ∸ b: If a ≥ b then a−b else 0
:# Minimum(a<sub>1</sub>, ... a<sub>n</sub>)
:# Maximum(a<sub>1</sub>, ... a<sub>n</sub>)
:# Absolute difference: | a−b | =<sub>def</sub> (a ∸ b) + (b ∸ a)
:# ~sg(a): NOT[signum(a)]: If a=0 then 1 else 0
:# sg(a): signum(a): If a=0 then 0 else 1
:# a | b: (a divides b): If b=k×a for some k then 0 else 1
:# Remainder(a, b): the leftover if b does not divide a "evenly".  Also called MOD(a, b)
:# a = b: sg | a − b |  (Kleene's convention was to represent ''true'' by 0 and ''false'' by 1; presently, especially in computers, the most common convention is the reverse, namely to represent ''true'' by 1 and ''false'' by 0, which amounts to changing sg into ~sg here and in the next item)
:# a < b: sg( a' ∸ b )
:# Pr(a): a is a prime number Pr(a) =<sub>def</sub>  a>1 & NOT(Exists c)<sub>1<c<a</sub> [ c|a ]
:# p<sub>i</sub>: the i+1th prime number
:# (a)<sub>i</sub>: exponent of p<sub>i</sub> in a: the unique x such that p<sub>i</sub><sup>x</sup>|a & NOT(p<sub>i</sub><sup>x'</sup>|a)
:# lh(a): the "length" or number of non-vanishing exponents in a
:# lo(a, b): (logarithm of a to base b): If a, b > 1 then the greatest x such that b<sup>x</sup> | a else 0

: ''In the following, the abbreviation '''x''' =<sub>def</sub>  x<sub>1</sub>, ... x<sub>n</sub>; subscripts may be applied if the meaning requires.''

* #A:  A function φ definable explicitly from functions Ψ and constants q<sub>1</sub>, ... q<sub>n</sub> is primitive recursive in Ψ.
* #B:  The finite sum Σ<sub>y<z</sub> ψ('''x''', y) and product Π<sub>y<z</sub>ψ('''x''', y) are primitive recursive in ψ.
* #C:  A ''predicate'' P obtained by substituting functions χ<sub>1</sub>,..., χ<sub>m</sub> for the respective variables of a predicate Q is primitive recursive in χ<sub>1</sub>,..., χ<sub>m</sub>, Q.
* #D:  The following ''predicates'' are primitive recursive in Q and R:
::* NOT_Q('''x''') .
::* Q OR R: Q('''x''') V R('''x'''),
::* Q AND R: Q('''x''') & R('''x'''),
::* Q IMPLIES R: Q('''x''') → R('''x''')
::* Q is equivalent to R: Q('''x''') ≡ R('''x''')
* #E:  The following ''predicates'' are primitive recursive in the ''predicate'' R:
::* (Ey)<sub>y<z</sub> R('''x''', y) where (Ey)<sub>y<z</sub> denotes "there exists at least one y that is less than z such that"
::* (y)<sub>y<z</sub> R('''x''', y) where (y)<sub>y<z</sub> denotes "for all y less than z it is true that"
::* μy<sub>y<z</sub> R('''x''', y).  The operator μy<sub>y<z</sub> R('''x''', y) is a ''bounded'' form of the so-called minimization- or [[mu-operator]]: Defined as "the least value of y less than z such that R('''x''', y) is true; or z if there is no such value."
* #F:  Definition by cases: The function defined thus, where Q<sub>1</sub>, ..., Q<sub>m</sub> are mutually exclusive ''predicates'' (or "ψ('''x''') shall have the value given by the first clause that applies), is primitive recursive in φ<sub>1</sub>, ..., Q<sub>1</sub>, ... Q<sub>m</sub>:
::  φ('''x''') =
::* φ<sub>1</sub>('''x''') if Q<sub>1</sub>('''x''') is true,
::* .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
::* φ<sub>m</sub>('''x''') if Q<sub>m</sub>('''x''') is true
::* φ<sub>m+1</sub>('''x''') otherwise
* #G: If φ satisfies the equation:
::  φ(y,'''x''') = χ(y, COURSE-φ(y; x<sub>2</sub>, ... x<sub>n</sub> ), x<sub>2</sub>, ... x<sub>n</sub> then φ is primitive recursive in χ. The value COURSE-φ(y; '''x'''<sub>2 to n</sub> ) of the course-of-values function encodes the sequence of values φ(0,'''x'''<sub>2 to n</sub>), ..., φ(y-1,'''x'''<sub>2 to n</sub>) of the original function.