Skip to main content
Added negative answer in general case; deleted 8 characters in body
Source Link
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

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

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

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!

Post Undeleted by Joel David Hamkins
Post Deleted by Joel David Hamkins
Source Link
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

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