So suppose we have a primitive recursive function $f$ with the following property:

$x\lt y \Rightarrow f(x)\lt f(y) $

Can we somehow prove that $X=rng(f) $ is also a primitive recursive set? I mean i can use the Church–Turing thesis to assume $f$ is computable with a procedure $A$ and then use $A$ to create an algorithm $B$ for $X$ and therefor $X$ is atleast $\mu-recursive$. But how can i prove its not just $\mu-recursive$ but a $primitive$ $recursive function$?

  • $\begingroup$ Yes. To be precise, the characteristic function of this set is primitive recursive. $\endgroup$ – realdonaldtrump May 27 '18 at 16:49

I believe the following works:

Following Godel, we're basically going to show that coding is primitive recursive. This will work for any p.r. function; we're then going to use the fact that $f$ is increasing to show that we can go one step further and get the characteristic function of the range of $f$.

The argument breaks down into a series of generally useful lemmas:

Mapping to primes: The function $p$ sending $i$ to the $i$th prime is primitive recursive; hence, if $g$ is primitive recursive, so is $g_p:=p\circ g$.

(Actually, the proof of this fact basically encapsulates the ideas in this problem, but it's more concrete so it might be easier to do first. Note that to prove this we're going to need a primitive recursive bound on how far we have to search for the next prime; luckily, Euclid's argument for the infinitude of primes shows that the factorial function will do the job.)

This is going to let us build a sequence out of the values of a function up to a certain point. The following lemma is really the heart of this whole argument:

Collecting values: If $h$ is primitive recursive, then so is $h_c: i\mapsto\prod_{j\le i}h(j)$.

The function we're interested in now is $f_{p_c}$: this function codes up the "history" of $f$ up to the input. The final step says that we can extract the information we want:

Decoding: The function $j$ which sends $(a, b)$ to $1$ if $p(a)\vert b$ and to $0$ otherwise is primitive recursive.

Putting these together, we now simply observe that, since $f$ is increasing, the range of $f$ is exactly $$\{a: j(a, f_{p_c}(a))=1\}.$$ Or, put another way, the function $i: a\mapsto j(a, f_{p_c}(a))$ is the characteristic function of the range of $f$; and it's clear $i$ is primitive recursive.


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.