3
$\begingroup$

I've met two different definitions of total recursive functions. One has 0; +1; projections as basic functions and composition; primitive recursion; minimalization as production rules. Another has +; ×; projections; the indicator function of < as basic functions and composition; minimalization as production rules. I know the second one doesn't need primitive recursion. Is primitive recursion indispensable to the first definition? If this is true, then one of +,× and I$_<$ can't be generated from zero, sucessor and projections with composition and minimalization only. Indeed I've tried to do so without success but I want to know if this is truly the case. Thanks.

$\endgroup$
1
$\begingroup$

All the initial functions $0, x+1$ and $I^n_k(x_1, \dots, x_n)$ essentially depend (at most) on one variable. Assume that we have $f(x_1, \dots, x_n), g_1(x_1, \dots, x_m), \dots, g_n(x_1, \dots, x_m)$ and they depend essentially on $x_{i_0}$ and $x_{i_1}, \dots, x_{i_n}$ respectively. Then their composition $$f(g_1(x_1, \dots, x_m), \dots, g_n(x_1, \dots, x_m))$$ depends essentially only on the essential variable of $g_{i_0}$, that is $x_{i_{i_0}}$.

Assume $g(x_1, \dots, x_n, y)$ depends essentially only on one variable and let $$f(x_1, \dots, x_n) = \mu y[g(x_1, \dots, x_n, y) = 0].$$ It is clear that in this case $f$ also depends on the same variable (or doesn't depend on its variables at all, if $g$ depends only on $y$).

The above shows that any function generated by using composition and minimalization from the initial functions depends essentially only on one variable. Hence, for instance, $x + y$ can't be generated this way.

$\endgroup$

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.