10
$\begingroup$

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?

$\endgroup$

2 Answers 2

10
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ thank you very much for your helpful answer. I guess the answer is no but I cannot find a counter example. I am a neophyte who learn computability theory and I am unfamiliar with forcing. Thanks again. $\endgroup$
    – Cheng Peng
    Dec 27, 2011 at 16:24
  • $\begingroup$ One doesn't need forcing to construct the set $A$, if you follow my instructions. You build a set $A$ by ensuring for each c.e. set $W_e$ either that $A\intersect W_e$ is finite or that $A-W_e$ is finite. Given such a set $A$, any bijection $f:\mathbb{N}\to A$ has the desired property, but $f$ may not be computable. $\endgroup$ Dec 27, 2011 at 16:30
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.