Can we represent computable functions by r.e. sets ?

Question

As we know, if $f$ is a computable function, then every pre-image of a r.e. set under $f$ is also a r.e. set, i.e. $f^{-1}(X)$ is a r.e.set if $X$ is a r.e. set. So I want to know that if a function satisfies that every pre-image of a r.e. set is also a r.e. set, then can we conclude that $f$ is a computable function?

Answer 1

If your hypothesis has a degree of uniformity, so that we may uniformly enumerate $f^{-1}X$ from an enumeration of $X$, that is, if given an index $e$ for a c.e. se $W_e$, then we may compute an index for $f^{-1}W_e$, then the answer is yes. To compute $f(n)$, simply consider indices for the singleton sets $W_{e_m}=\{m\}$, start enumerating the pre-images $f^{-1}W_{e_m}$, and if $n$ shows up in $f^{-1}W_{e_m}$, then you know $f(n)=m$, and is otherwise not defined.

And indeed, in your observation, if $f$ is computable, then we obtain the desired degree of uniformity, since there is a uniform procedure to enumerate $f^{-1}X$ from any enumeration of $X$.

In the general case, however, the answer is no. Since there are only countably many c.e. sets, we may enumerate them, and then construct an infinite set $A\subset\mathbb{N}$ such that for every c.e. set $B$, either $A\subset^* B$, meaning all except finitely many elements of $A$ are in $B$, or else $A\cap B$ is finite. In other words, the set $A$ generates an ultrafilter on the c.e. sets modulo finite difference. One can build such an $A$ in stages, by making a finite promise to the positive elements of $A$, and a steadily shrinking set of possible additional elements. At each stage $e$, then add the next possible element to $A$, and if $W_e$ has infinite intersection with the set of possible additions, then shrink it to be inside $W_e$; otherwise, our set is guarranteed to have finite intersection with $W_e$. This is just like finding a set that is pseudo generic for Mathias forcing, for those who enjoy the connection between computability theoretic constructions and forcing.

Now, with such a set $A$, let $f:\mathbb{N}\to A$ be any non-computable bijective function. Consider any c.e. set $W_e$. If it happens that $W_e\cap A$ is finite, then $f^{-1}W_e$ is also finite and hence c.e. Otherwise, it must happen by the choice $A$ that $A$ is almost included in $W_e$, in which case $f^{-1}W_e$ includes all but finitely many elements of $\mathbb{N}$, and hence is also c.e.

So this is a case where $f$ is a total function, and $f^{-1}W_e$ is computable for any c.e. set $W_e$, but $f$ is not computable.

Finally, let me add that this is a great question!

Answer 2

Some related functions have the following application (D. Myers 2007, unpublished).

Define $$ A\le B\quad\Longleftrightarrow\quad A=f^{-1}(B) \quad\text{ for some $f$ that maps every $\Sigma^0_n$ set to a $\Sigma^0_n$ set, for each $n$} $$ Theorem: For each $n\ge 1$, the properly $\Sigma^0_n$ sets (the sets in $\Sigma^0_n\backslash \Delta^0_n$) form a single equivalence class under the equivalence relation induced by $\le$. As do the properly $\Pi^0_n$ sets.

Thus $\le$ allows us to look at the arithmetical hierarchy as a degree structure. It is not clear whether this can be done with an arithmetical relation in place of $\le$. (Turing reducibility is $\Sigma^0_3$ hence arithmetical, but the relation $\le$ is on its face $\Sigma^1_1$ only.)