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

\begin{equation} [[S]](x,y)= \begin{cases} & x-y \quad \text{if} \quad x \geq y \\&0 \quad \quad \text{otherwise} \end{cases} \tag{1} \end{equation}

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!


(I am assuming that you are just looking to fill in the details for your subtraction function symbol.)

You are essentially there. Recall that the primitive recursive function symbol $\newcommand{\FUN}[1]{[\![\, #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 ).$$

  • $\begingroup$ 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? $\endgroup$
    – user111731
    Dec 1 '13 at 14:25
  • $\begingroup$ @user111731: That's what I would do. $\endgroup$
    – user642796
    Dec 1 '13 at 14:40
  • $\begingroup$ 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. $\endgroup$
    – user111731
    Dec 1 '13 at 22:06
  • $\begingroup$ @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) )$. $\endgroup$
    – user642796
    Dec 2 '13 at 3:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.