Exercise 7.24. of Roger's Theory of Recursive Functions and Effective Computability asks what happens if we take the direct image or the inverse image under a recursive one-to-one function of a productive or creative set. I can prove that
- if $A$ is productive then $f[A]$ is also productive, and
- $f^{-1}[A]$ need not be either creative or productive even if $A$ is: for example, consider an one-to-one enumeration $f:\mathbb{N} \to K$ of a halting set.
I have no idea whether $f[A]$ is creative if $A$ is, however. Thanks for any help. (This is not a homework assignment. I solely prove exercises by my own.)
Here are the relevant definitions:
- $A\subset\mathbb{N}$ is productive if we have a partial recursive function $\psi$ such that if $W_e\subseteq A$ is not empty then $\psi(e)$ halts and $\psi(e)\in A-W_e$.
- $A$ is creative if $A$ is recursively enumerable and its complement is creative. For example, the complement of a halting set is creative under the function $\psi(x)=x$.
(Added in 26 April 2020: I had accidentally swapped the definitions of creativity and productiveness. I have corrected the definitions, but you need some care to read Noah's answer, which is based on my wrong previous definitions.)
The key fact is that we can pull back c.e. sets along computable maps (there's a topological analogy here, identifying "c.e." with "open" and "continuous" with "computable"). Specifically, suppose $f$ is computable and injective and $U$ is c.e. Then $f^{-1}[U]$ is also c.e., and this is uniform (= there is some computable $g$ such that $f^{-1}[W_e]=W_{g(e)}$ for all $e$).
With this in hand, here's how we can show that $f[C]$ is creative whenever $C$ is:
Suppose we're given that $W_e\subseteq f[C]$. Since $f$ is injective we always have $f^{-1}[f[A]]=A$, and so in particular we have $W_{g(e)}\subseteq C$. So $\psi(g(e))\in C\setminus W_{g(e)}$. This gives $f(\psi(g(e)))\in f[C]$, and so $f(\psi(g(e)))\not\in W_e$.
More snappily: if $\psi$ witnesses the creativity of $C$, then $f\circ \psi\circ g$ witnesses the creativity of $f[C]$.
(Incidentally, you don't need $W_e\not=\emptyset$ in the definition of creativity - we can always just nonuniformly pick some $a\in A$, and have $\psi$ start by moving from $W_e$ to $W_e\cup\{a\}$.)