Show that function is recursive

Question

Recursive functions: $\mathbb{N}_0^k \to \mathbb{N}_0$

Class of recursive functions:

The minimal subclass of the class of all the functions $f: \mathbb{N}_0^k \to \mathbb{N}, k=1,2, \dots$ that contains the

1. $f(x)=c$ (constants)
2. $S(x)=x+1$ (successor)
3. $P_n^m(x_1, \dots, x_m)=x_n \ (m \geq n)$ (projections)

and is closed under the following

• If $h,g_1, \dots, g_n: \mathbb{N}_0^m \to \mathbb{N}_0$ are recursive then $f(\overline{x})=h(g_1(\overline{x}), \dots, g_n(\overline{x})): \mathbb{N}_0^m \to \mathbb{N}$ is recursive . (composition)

• If $g: \mathbb{N}_0^{k-1} \to \mathbb{N}_0$ and $h: \mathbb{N}_0^{k+1} \to \mathbb{N}_0$ are recursive then $f: \mathbb{N}_0^k \to \mathbb{N}_0$ is also recursive $$f(0,\overline{y})=g(\overline{y}) \\ f(x+1, \overline{y})=h(x, f(x, \overline{y}), \overline{y})$$ (recursion)

• If $g$ is recursive and $\forall \overline{x} \ \exists z \ g(z, \overline{x})=0\\ f(\overline{x})=\mu z \ (g(z, \overline{x})=0)= \min \{ z \in \mathbb{N}_0 \mid g(z, \overline{x})=0\}$

If $A \subset \mathbb{N}_0^k$ then $A$ is a recursive set iff the characteristic function of $A$ is recursive.

I want to show that the following functions and sets are recursive:

• $f(x,y)=x+y$
• $f(x,y)=xy$
• $\DeclareMathOperator{sign}{sign}\sign(x)=\begin{cases} 1 &, x=0 \\ 0 & , x>0 \end{cases}.$
• $f(x)=\begin{cases} 1 &, g(x)=0 \\ 0 &, h(x)=0 \end{cases}$, under the term that $g,h: \mathbb{N}_0 \to \mathbb{N}_0$ are recursive and $\forall x(g(x)h(x)=0, g(x)+h(x)>0)$
• $f(y)=\prod_{x=0}^y g(x)$
• $B = \{ y \mid \exists x \leq y \ x \in A \}, C = \{ y \mid \forall x \leq y \ x \in A\}$ if $A$ recursive.
• $x \dot{-} y=\left\{\begin{matrix} x-y &, x \geq y \\ 0 &, \text{otherwise} \end{matrix}\right.$
• $f(y)=\sum_{x=0}^y g(x)$ if $g$ is recursive

Since I haven't seen any example, could you maybe explain to me with an example how we show that a specific function is recursive using the above definition?

Answer 1

Solution strategy:

One tries to express the candidate function in terms of the given known to be recursive functions (constant functions, successor function, projection functions) and the given operations which keep the recursive property (composition, recursion, $\mu$-recursion), meaning they result in a recursive function each. If this succeeds one can argue that the candidate function is recursive too.

Re 1.:

Adding $x$ to $y$ is the same as $x$ times incrementing $y$ by one: $$ f(x, y) = x + y = S^x (y) \quad (x, y \in \mathbb{N}_0 ) \\ $$ where we explain the finite many compositions ($x$ times) of the successor function by $$ S^0(y) = y \\ S^{x+1}(y) = (S \circ S^x)(y) $$ using single composition and primitive recursion. We need the middle operation, for $k = 2$, then we define $$ g(y) = y $$ and we want $$ h(x, f(x,y), y) = S(f(x,y)) $$ to have $f(x,y) = S^x(y)$. This means we have to define $$ h = S \circ P_2^3 $$ then $$ h(x, f(x,y), y) = S(P_2^3(x, f(x,y), y)) = S(f(x,y)) $$ We now have to argue that $g$ and $h$ are recursive to have $f$ recursive. For $g$ we note $$ g(x) = x = P_1^1(x) \iff \\ g = P_1^1 $$ which is recursive by definition. For $h$ we note it is the composition of the successor function and the projection of the second component of three tuples, which are both recursive functions. Composition is admissible by the first operation using $m=3$, $n=1$, $h = S$ and $g_1 = P_2^3$.

Re 2.:

Here we can define $$ f(x, y) = x \, y $$ via recursion $$ f(0, y) = 0 \\ f(x+1, y) = y + f(x, y) $$ so we define $g(y) = 0$ and $h(x,f(x,y),y) = y + f(x,y)$ which means $$ h = P_2^3 + P_3^3 $$ As $g$ is a constant function it is recursive, as are the projections and addition we showed above as recursive, so $h$ is recursive and so is $f$.

Re 3.:

This one is tricky, how to make the function vanishing for $x \ge 1$? From the given means only the recursion operation seems to be promising and we need to have something like the predecessor function $P(x) = x \dot{-} 1$, to reach from $x=1$ to $x=0$ and use that one to zero the function, which seems only possible via the first argument of $h$, which we have made no use of so far anyway.

We define $g(y) = 1$ and $h = P_1^3 \cdot P_2^3$ where the product of two functions is defined by $(f\cdot g)(x) = f(x)\, g(x)$ for each argument value $x$ so the recursion operation and these choices for $g$ and $h$ give a recursive $f$ as $$ f(0, y) = g(y) = 1 \\ f(x+1, y) = h(x, f(x, y), y) = x f(x,y) $$ and this results in \begin{align} f(0, y) &= g(y) = 1 \\ f(1, y) &= f(0+1, y) = 0 \, f(0, y) = 0 \cdot 1 = 0 \\ f(2, y) &= f(1+1, y) = 1 \, f(1, y) = 1 \cdot 0 = 0 \\ f(3, y) &= f(2+1, y) = 2 \, f(2, y) = 2 \cdot 0 = 0 \end{align} and so on which looks good. So we end up with $$ f(x,y) = \sign(x) \quad (x, y \in \mathbb{N}_0 ) $$ where $f$ is recursive thanks to $g$ and $h$ being recursive and multiplication being recursive too, as we showed above.

So we can compute $\sign(x) = f(x, 0)$.

Re 4.:

The definitions for $g$ and $h$ ensure that for every argument value one of the two functions is zero while the other one is non-zero. So we can express $f$ as $$ f(x) = \sign(g(x)) \iff \\ f = \sign \circ g $$ Such a composition of recursive functions $\sign$ (showed above) and $g$ (ensured) is recursive.

Re 5.:

We note $$ f(0) = g(0) \\ f(x+1) = \prod_{z=0}^{x+1} g(z) = g(x+1) \prod_{z=0}^x g(z) = g(x+1) \, f(x) $$ so we define $$ F(0, y) = G(y) = g(0) \\ F(x + 1, y) = H(x, F(x, y), y) = g(x+1) \, F(x, y) $$ which means $$ G = g \circ 0 \\ H = (g \circ S \circ P_1^3) \cdot P_2^3 $$ where $0$ is the constant function $f(x) = 0$. If $g$ is recursive, so are $G$ and $H$ and recursion gives a recursive $F$ with $F(x, y) = f(x)$.

So we can compute $f(x) = F(x, 42)$.

Answer 2

Re second set:

We note $$ \chi_C(y) = \prod_{x=0}^y \chi_A(x) $$ which is recursive because $A$ recursive implies its characteristic function $\chi_A$ is recursive. The used product results in a recursive function, as shown for the fifth task above. Thus $C$ is recursive.

Re first set:

The idea here is to use logical negation to express the needed OR expression by an AND expression: $$ \chi_B(y) = \sign\left( \prod_{x=0}^y \sign\left(\chi_A(x) \right) \right) $$