3
$\begingroup$

I am studying partial recursive functions, and while I think I understand most elements of how to prove a given function is primitive recursive, there is one particular pattern that I can't come up with a good explanation for.

Specifically, how would I show that the following function is primitive recursive?

$f(x_1, \dots, x_n, i) = x_i$

This is equivalent to a projection function $\pi_{i, n}$, but the projection function used depends on $i$, which is also a function parameter. It seems intuitive that this should be primitive recursive, and I can see that for some fixed arity you could do a definition by cases, e.g. for $ n = 2 $:

$f(x_1, x_2, i) = \begin{cases} \pi_{1,2}(x_1, x_2) &\text{if } i = 1\\ \pi_{2,2}(x_1, x_2) &\text{if } i = 2 \end{cases}$

What I'm unsure of is how to show this is true for the general case.

Note I have also seen this question, but it just defines the function; it doesn't prove it is primitive recursive.

For some context as to where this may be used, consider the summation:

$f(x_1, \dots, x_n) = \sum_{i=1}^{n} x_i$

The normal proof that a summation $\sum_{i=1}^{k} g(x_1, \dots, x_n, i)$ is primitive recursive requires proving that $g$ is primitive recursive - so for the simple case of summing up all arguments the function I'm concerned about must be shown to be primitive recursive!

$\endgroup$
3
  • $\begingroup$ If you can deal with the summation then $ f(x_{1},\ldots,x_{n},i) = \sum_{j=1}^{i} h(i,j)\cdot x_{j}$, where $h(x,y):=1$ if $x=y$, $0$ otherwise, might work. $\endgroup$ – wet Nov 10 '17 at 2:01
  • $\begingroup$ @wet That would work actually! And it can be easily shown to be primitive recursive (since summation is, multiplication is, and $h$ is just the characteristic function $\chi_{=}$). $\endgroup$ – AvianIsTheTerm Nov 10 '17 at 2:32
  • $\begingroup$ Primitive recursion doesn't support variable length arguments, so your solution is the general solution. The solutions that use sums are just obfuscated ways of doing exactly what you figured out yourself. There is no way around defining a different set of functions for each arity. $\endgroup$ – DanielV Nov 10 '17 at 5:51
2
$\begingroup$

As per @wet's comment on the post, $f$ may be defined by:

$f(x_1, \dots, x_n, i) = \sum_{j=0}^{i} \chi_{=}(i, j) \cdot x_j$

Where $\chi_{=}(x, y)$ is the characteristic function for the predicate $x = y$.

Then, since summation, multiplication and $\chi_{=}$ are all primitive recursive (by the usual proofs for each), and $f$ is a composition of these, $f$ must also be primitive recursive.

EDIT: As mentioned in further comments - this doesn't actually solve the issue. It is essentially required to define by cases for each desired arity; that said pretty clearly each is primitive recursive.

$\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.