# Primitive Recursion Functions (Programs)

The set $F_{n}$ of primitive recursive function symbols of arty $n$ can be defined inductively as \begin{array}[lr] & Z, \text{Succ} \in F_{1} & \\ \pi_{j}^{n} \in F_{n} \quad \text{for each} \quad j=1,\dots, n \\ &\text{if} \quad f \in F_{n} \quad \text{and} g_{1},\dots, g_{n} \in F_{m}, \text{then} \circ_{n}^{m}[f,g_{1},\dots,g_{n}]\in F_{m} & \\ &\text{if} \quad f \in F_{n+2} \quad \text{and} \quad g \in F_{n}, \text{then} \quad \text{Rec}^{n}[f,g]\in F_{n} & \end{array} Given the interpretation $f \in F_{n}$, $[[f]]:\mathbb{N}^{n} \to \mathbb{N}$ \begin{array}[lr] [[Z]](k)&=& 0 \\ [[\text{Succ}]](k) &= &k+1 \\ [[\pi_{j}^{n}]](k_{1},\dots,k_{n}) &= &k_{j} \\ [[\circ_{n}^{m}[f,g_{1},\dots,g_{n}]]](k_{1},\dots,k_{m}) &= &[[f]]([[g_{1}]](k_{1},\dots,k_{m}),\dots, [[g_{n}]](k_{1},\dots, k_{m})) \\ [[\text{Rec}^{n}[f,g]]](k_{1},\dots,k_{n},0) &= & [[g]](k_{1},\dots,k_{n}) \\ [[\text{Rec}^{n}[f,g]]](k_{1},\dots,k_{n},m+1) &= & [[f]](k_{1},\dots,k_{n},m,[[\text{Rec}^{n}[f,g]]](k_{1},\dots,k_{n},m) \end{array}

Inspired by the progress I achieved, due to the help from this forum (see Recursion, multiplication and exponential), I decided to tackle a more demanding problem, namely to determine a function $R \in F_{2}$ such that: $$[[R]](x,y)=\text{min}(x,y)$$

I realize that in order to obtain such a recursive function I first need a function $S \in F_{2}$ that satisfy

Nevertheless, to achieve this I also need another function, the so-called predecessor function, $P \in F_{1}$. Now, I have managed to obtained the following function $P$

\begin{equation} P=\circ_{2}^{1}[\text{Rec}^{1}[Z,\pi_{2}^{3}],Z,\pi_{1}^{1}] \end{equation}

which satisfies the criteria $[[P(0)]]=0$, and $[[P(k+1)]]=k$. The next stage then is to find a primitive recursive function for (1). Now, we see from (1) that

\begin{equation} x-(y+1)= \begin{cases} 0   &\text{if} \quad n-m=0 \\ (x-y)-1 &\text{if} \quad x-y >0\end{cases}\end{equation}

Thus we can repress (1) as:

\begin{equation}x-y= \begin{cases} x &\text{if} \quad y=0\\ P(x-(y-1)) &\text{if} \quad y>0\end{cases} \tag{2}\end{equation} Now, our concerns turn to determine such a function. \begin{align} k_{1} &=k_{1}-0 \\ &=[[S]](k_{1},0) \\&=[[\text{Rec}^{1}[f,g]]](k_{1},0) \\ &=[[g]](k_{1}) \end{align}

and so $[[g]](k_{1})=k_{1}$ for all $k_{1} \in \mathbb{N}$; which is satisfied by $\pi_{1}^{1}$. But it is here, when I'm trying to do the inductive case, that my argument seems to fall apart. I have

\begin{align} (k_{1}-m)-1&=k_{1}-(m+1) \\ &=[[\text{Rec}^{1}[f,g]]](k_{1},m+1) \\ &=[[f]](\;k_1 , m , \text{Rec^1 [ F , G ]} (k_1,m)\;) \\ &=[[f]](\;k_1 , m , {S} (k_1,m))\; \\&=[[f]](k_{1},m,k_{1}-m) \\ &=? \end{align}

It would be very much appreciated if anyone would care to help me out. Thanks!

You are essentially there. Recall that the primitive recursive function symbol $\newcommand{\FUN}{[\![\, #1 \,]\!]}\newcommand{\Pred}{\mathsf{P}}\Pred$ has the property that $$\FUN{ \Pred } ( x ) = x - 1,$$ (where, as you have been doing, if the usual subtraction would result in a negative number we assign it the value $0$). So at the point you are stuck, you just need to notice that $$\FUN{ \Pred } ( k_1 - m ) = ( k_1 - m ) - 1 = \cdots = \FUN{ \mathsf{f} } ( k_1 , m , k_1 - m ).$$
• I take it I should choose the third argument $\pi_{3}^{3}$ and take the predecessor function on that; which is to say $[[\circ_{1}^{3}[\text{P},\pi_{3}^{3}]]](k_{1},m,k_{1}-m)$. Right? Dec 1 '13 at 14:25
• How would your minimum recursive function look like? Would it involve the maximum function? Or is it sufficient to use the subtraction function, as written above, and divide the $[[M]]$-function into two cases $m \geq n$ and $m <n$. In the latter case I would have $[[S]](m,n)=0$ and so I need some argument such that the program recognizes that it should choose $m$ in this case. Dec 1 '13 at 22:06
• @user111731 The (first) trick here is to use the characteristic function of the $>$ relation, let's call it $\chi_>$. (So $\chi_> (x,y) = 1$ if $x > y$ and $\chi_> = 0$ if $x \leq y$. Then $\min (x,y) = y \cdot \chi_> (x,y) + x \cdot ( 1 - \chi_> (x,y) )$. Dec 2 '13 at 3:27