In this post I wondered, whether a language over a finite alphabet is “stable” with respect to primitive recursiveness, recursiveness and recursive enumerability under different enumerations of the alphabet and the answer was yes. But it give rise to this side question: If I have a set $M$ which is primitive recursive or computable (i.e. recursive ) and a primitive recursive function $f:\mathbb{N} \rightarrow \mathbb{N}$. Is then $f(M)$ again primitive recursive or computable ?

In the above mentioned post, to answer the question, a special case of this more general proposition had to be proven, namely in that post $f$ was also bijective and it's inverse was also primitive recursive. Interestingly, in the more general setting of $M$ being computably enumerable, the above proposition holds in this general case, as it was discussed in a comment to the post.

I'm having doubts the proposition holds as I have stated it here, because I can see no way of showing, that the characteristic function of $f(M)$, $$\chi_{{ }_{f(M)}} (x) = \begin{cases} 1 & x\in f(M)\\ 0 & \textrm{otherwise}\end{cases}\Leftrightarrow\begin{cases} 1 & \exists t\in M:\ f(t)=x\\ 0 & \textrm{otherwise}\end{cases}$$ is primitive recursive/computable if $f$ isn't at least bijective, because I can think of no way in which to show the existence of such a $t$ if I don't have any additional information about $f$.

(In case the proposition does not hold, could someone maybe give a counterexample ?)

  • 1
    $\begingroup$ The set of proofs of PA is primitive recursive, the function that sends every proof to its conclusion is primitive recursive, the set of theorems of PA is not computable, but rather computably enumerable, by Gödel's incompleteness theorem. Is this a counterexample to what you are looking for? $\endgroup$ – Apostolos Jul 3 '11 at 14:59
  • $\begingroup$ See related question on MathOverflow: mathoverflow.net/questions/21087/… $\endgroup$ – JDH Jul 7 '11 at 11:22

No. In fact, every nonempty computably enumerable set can be enumerated by a primitive recursive function.

Here is one way to prove this fact. Let $T(e,n,x)$ be Kleene's $T$-predicate, which is primitive recursive. Suppose that the $e$-th computably enumerable set $$W_e = \lbrace n \in \mathbb{N} : \exists x T(e,n,x)\rbrace$$ is nonempty; say $n_0 \in W_e$. Let $\ell,r:\mathbb{N}\to\mathbb{N}$ be the two primitive recursive projections associated with the Cantor pairing function. Define the primitive recursive function $f:\mathbb{N}\to\mathbb{N}$ by $$f(m) = \begin{cases} \ell(m) & \text{when}\ T(e,\ell(m),r(m)), \\ n_0 & \text{otherwise.} \end{cases}$$ It is clear that $f$ enumerates $W_e$.

  • $\begingroup$ I'm not sure, but I don't thinks this answer answers my question ? (Or am I not seeing it?) If the answer to my question is "no", as you stated, shouldn't you give an example of a, say, primitive recursive set $M$ and a primitive recursive (abbreviated: p.r.) function $f$ such that $f(M)$ isn't p.r.? I can't see the connection between the fact, that every nonempty computably enumerable set can be enumerated by a p.r. function and the fact that there is a, say, p.r. set and a p.r. function such that the image of this set under this function isn't p.r.. $\endgroup$ – temo Jul 7 '11 at 10:25
  • 1
    $\begingroup$ @temo, a counterexample is provided by any c.e. set that is not primitive recursive, and there are many of these; indeed, since any computable set is c.e., you can use any computable set that is not primitive recursive. A more extreme example is provided by the halting problem set, which is c.e. but not primitive recursive. $\endgroup$ – JDH Jul 7 '11 at 11:26

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.