Primitive recursive function: Difference between revisions

Revision as of 10:38, 4 July 2025

Latest revision as of 15:58, 14 August 2025

(2 intermediate revisions by 2 users not shown)

Line 117:

===Truncated subtraction===

The limited subtraction function (also called "[[monus]]", and denoted "<math>\stackrel.mathbin{\dot{-}}</math>") is definable from the predecessor function. It satisfies the equations

:<math>\begin{array}{rcll}

y \stackrel.mathbin{\dot{-}} 0 & = & y & \text{and} \\

y \stackrel.mathbin{\dot{-}} S(x) & = & Pred(y \stackrel.mathbin{\dot{-}} 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.mathbin{\dot{-}} 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) \\

Line 147:

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

Using the property <math>x \leq y \iff x \stackrel.mathbin{\dot{-}} 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) \\

Line 281:

===Constant functions===

Instead of <math>C_n^k</math>,

alternative definitions use just one 0-ary ''zero function'' <math>C_0^0</math> as a primitive function that always returns zero, and built the constant functions from the zero function, the successor function and the composition operator.{{Citation needed|date=July 2025}}

=== Iterative functions ===

Line 393:

| first = M. D.

| doi = 10.2307/2270177

| journal = [[The Journal of Symbolic Logic]]

| mr = 224460

| pages = 505–508

Line 468:

| first = Raphael M.

| doi = 10.1090/S0002-9904-1947-08911-4

| journal = [[Bulletin of the American Mathematical Society]]

| mr = 22536

| pages = 925–942