2
$\begingroup$

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 ?)

  • 0
    See related question on MathOverflow: http://mathoverflow.net/questions/21087/is-there-a-primitive-recursively-enumerable-set-whose-complement-is-not-such2011-07-07

1 Answers 1

3

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

  • 1
    @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.2011-07-07