According to the book that I'm reading, we can define the $\mu-$recursive functions inductively, as follows:
- The constant, projection, and successor functions are all $\mu-$recursive.
- If $g_1, \dots , g_m$ are $n-$variable $\mu-$recursive functions and $h$ is an $m-$variable $\mu-$recursive function, then the composite function $f=h \circ (g_1, \dots , g_m)$ is also $\mu-$recursive.
- If $g$ and $h$ are $n-$ and $(n+2)-$variable $\mu-$recursive functions, then the function $f$ defined from $g$ and $h$ by primitive recursion is also $\mu-$recursive.
- If $g$ is a total $(n+1)-$variable $\mu-$recursive function, then the function $f$ defined from $g$ by unbounded minimalization is also $\mu-$recursive.
The definition of a primitive recursive function is the following:
- The constant, projection, and successor functions are all primitive recursive functions.
- If $g_1, \dots , g_m$ are $n-$variable primitive recursive functions, and if $h$ is an $m-$variable primitve recursive function, then the composite function $h \circ (g_1, \dots , g_m)$ is also a primitive recursive function.
- If $g$ and $h$ are $n-$ and $(n+1)-$variable primitive recursive functions, then $(n+1)-$variable function $f$ defined from $g$ and $h$ by primitive recursion is also a primitive recursive function.
The difference between these two definitions is the minimalization, or not??
The minimalzation is the following:
$$f(\overline{x})= \left\{\begin{matrix} \mu z(g(z,\overline{x})=0)=\min \{z \in \mathbb{N}_0 \mid g(z, \overline{x})=0\} & \text{ if } ( \exists z) (g(z,\overline{x})=0)\\ \text{ undefiniert } & \text{ otherwise } \end{matrix}\right.$$
All primitve recursive functions are $\mu-$recursive, but the inverse doesn't hold, right??
Does this statement stand because of the minimalization??