Does there exist a non-recursive function (say, from naturals to naturals) such that the inverse of every r.e. set is r.e.?

If yes, how to construct one? If no, how to prove that? Any References?

  • 1
    $\begingroup$ This is the reverse direction of a trivial theorem, namely: if $f$ is recursive, then $\{n | f(n) \in A\}$ is r.e. whenever $A$ is r.e. The question asks: if $f$ satisfies the latter condition, must it then be recursive? $\endgroup$ – Anonymous Jun 25 '12 at 10:16
  • $\begingroup$ This is a very natural and interesting question. Although I gave one answer, you might consider waiting for a while before accepting any answer, to see if someone else has a different or more elementary construction. $\endgroup$ – Carl Mummert Jun 25 '12 at 11:47
  • $\begingroup$ Ok (I already accepted your answer before seeing this comment - but I've un-accepted it, now.) You're right - it would be nice if there'd be a more elementary answer. My attempts with 'simple' sets all fail, so far. $\endgroup$ – Anonymous Jun 25 '12 at 14:46

For any sequence $\mathcal{B} = \langle B_i : i \in \mathbb{N}\rangle$ of subsets of $\mathbb{N}$, there is a $\mathcal{B}$-cohesive set $A$: an infinite set such that, for any $B_i \in \mathcal{B}$, either there are only finitely many elements of $A$ in $B_i$, or all but finitely many elements of $A$ are in $B_i$. The set $A$ is called "cohesive" because, although it is infinite, none of the sets $B_i$ is able to split it into two infinite pieces.

Apply that fact with $\mathcal{B}$ containing all the r.e. sets to obtain a cohesive set $A$. Let $f$ be the function that enumerates $A$ in increasing order. First, $A$ is not computable, or even r.e., because if $A$ was r.e. then we could use that enumeration to effectively enumerate "every other element" of $A$, which would give us an r.e. set that splits $A$ into two infinite pieces, which is impossible. Moreover, because $A$ is not computable, $f$ is not computable - if we could compute $f$ then we could enumerate $A$ in increasing order, which would imply $A$ is computable.

Now let $B$ be any r.e. set. Then, because $A$ is cohesive for r.e. sets, one of two things must happen:

  • All but finitely many elements of $A$ are in $B$. In this case $f^{-1}(B)$ is cofinite, and hence is computable.
  • Only finitely many elements of $A$ are in $B$. In this case, $f^{-1}(B)$ is a finite set, and is thus computable.

Either way $f^{-1}(B)$ is not only r.e., it is computable.

  • $\begingroup$ This is a very nice answer, do you have a reference for the result about the existence of cohesive sets? $\endgroup$ – Sam Jones Jun 25 '12 at 12:10
  • $\begingroup$ Once we have the r.e.-cohesive set A, we could also proceed as follows, I think: any bijection from N to N that leaves all elements from N\A pointwise fixed, will preserve r.e. sets, and there are uncountably many of such bijections, as A is infinite. $\endgroup$ – Anonymous Jun 25 '12 at 14:42
  • $\begingroup$ @Sam Jones Don't have a reference, but a proof-sketch: make a sequence $(C_i)$ such that: for all $i$: $C_i$ is either $B_i$ or $N$ \ $B_i$ and such that $C_0 \cap ... \cap C_i$ is infinite for all $i$. Then pick a distinct $x_i$ from each $C_0 \cap ... \cap C_i$, and define $A = \{x_0, ...\}$. $\endgroup$ – Anonymous Jun 25 '12 at 14:52
  • 2
    $\begingroup$ @Sam Jones: They're well known in computability theory, for example Soare p. 187. $\endgroup$ – Carl Mummert Jun 25 '12 at 17:02

Just to clarify I assumed the question was asking about bijective functions (since they are more interesting) so I showed that answer was yes in that case as well.

If you just want any old function you can simply use Galvin-Prikry style forcing. Define a finite initial segment of the function and keep an infinite set $S$ of possible future values for elements in the range. At stage $i$ you subtract $W_i$ from $S$ unless that would leave it finite in which case you shrink $S$ to be a subset of $W_i$. Really it's the same technique but I like it better.

As for the bijective case the answer is still yes.

Let $\mathscr{E}$ denote the structure with domain consisting of c.e. (aka r.e.) sets under the relation $\subseteq$. An automorphism of $\mathscr{E}$ is just a bijective function on c.e. sets respecting $\subseteq$.

It is a result of (?) (Perhaps Soare as it appears in his textbook) that any automorphism of $\mathscr{E}$ is induced by a permutation of $\omega$ (i.e. bijection of $\omega$ with itself).

There are several different ways to see that not all automorphisms of $\mathscr{E}$ are induced by a computable permutation. Lachlan's argument is my favorite because it works even on $\mathscr{E}$ modulo finite differences.

Given that all computable permutations give rise to automorphisms one may fix a co-c.e. cohesive set $C$, e.g., the compliment of a maximal set, and note that any permutation $p_C$ of $C$ union the identity on $C$ compliment induces an injective map $p(W)= (W \cap \bar{C}) \cup p_C(W \cap C)$. Since $C$ is cohesive either $W \cap C$ is finite so $p(W)$ is a c.e. set union a finite set and hence c.e. or $W$ almost covers $C$ so $C - W$ is finite. Hence $p_C(W \cap C)$ only differs finitely from $C$ and thus only differs finitely from $W \cap C$. Therefore $p(W)$ differs only finitely from $W$ so $p(W)$ is c.e. Hence $p$ is an automorphism of the c.e. sets (since it is clearly a surjective function on all sets).

Lachlan's proof relies on defining computable permutations on larger and large computable subsets of $\omega$. We start with $R_0=\emptyset$ and build a sequence $R_0 \subseteq R_1 \ldots $ of computable sets such that $\omega - R_i$ is never finite but $\bigcup R_i = \omega$. On each $R_{i+1} - R_i$ we define a permutation and let the final permutation to be the union of these partial permutations. The key idea is similar to what we used above: if $W \cap C$ is finite or $C - W$ is finite then however we define our permutation on $C$ it can't interfere with mapping $W$ to another c.e. set.

At stage $i+1$ choose some computable $R_{i+1}$ not almost equal to $\omega$ infinitely extending $R_{i}$ containing $W_i$ or $\bar{W_i}$. Then select the first c.e. set $W$ not yet dealt with such that $W \cap (R_{i+1}-R_i)$ is infinite and $(R_{i+1}-R_i) - W$ is infinite. Let $C$ be infinite computable subset of $W \cap (R_{i+1}-R_i)$. Let $p_0$ be the identity on $(R_{i+1}-R_i)$. Let $p_1$ be the permutation on $(R_{i+1}-R_i)$ exchanging $C$ and $\bar{C} \cap (R_{i+1}-R_i)$.

Clearly both $p_0$ and $p_1$ and computable and as $\bar{C} \cap (R_{i+1}-R_i)$ contains infinitely many elements outside of $W$ it follows that $p_1(W)$ is not almost equal to $W$. Since $R_{i+1}$ either contains $W_i$ or $\bar{W_i}$ every c.e. set has it's image determined by a computable permutation giving rise to an automorphism. However, any infinite string of $0$'s and $1$'s gives rise to a unique automorphism.

Importantly, since $p_0$ and $p_1$ always map c.e. sets to sets that differ by infinitely much this shows the stronger result that we there are $2^\omega$ many automorphisms differing non-trivially.

  • $\begingroup$ Just to explain: $\endgroup$ – Peter Gerdes Jun 27 '12 at 20:03
  • $\begingroup$ Yes, and this gives both image and inverse $\endgroup$ – Peter Gerdes Jun 27 '12 at 23:50
  • $\begingroup$ Do you have a citation for Lachlan's result? $\endgroup$ – Bjørn Kjos-Hanssen Jan 24 '15 at 0:19
  • $\begingroup$ I'm pretty sure you can find it in Soare. I believe that is where I read it. $\endgroup$ – Peter Gerdes Jun 3 '15 at 12:55

I guess that you have meant image instead of inverse...

In that case in my opinion the answer is that such a function exists. Since you can construct a function $\phi$ as follows: for numbers representing valid pairs (code of a Turing machine, input) return 1, if the machine halts on the input, 0 otherwise. For all other numbers, return 0. This function is clearly not recursive. However, for all r.e. sets, the image is either $\{0\}$, or $\{0,1\}$, which are both r.e.

  • $\begingroup$ Nope, I meant inverse: $f^{-1}(A)$ is r.e. whenever $A$ is r.e. $\endgroup$ – Anonymous Jun 25 '12 at 10:09
  • $\begingroup$ Also: no counterexample can exist with $Im(f)$ finite, because then you have a partition of the domain $N$ into finitely many r.e. sets; hence each of these sets is recursive, etc.etc. and the function is recursive. $\endgroup$ – Anonymous Jun 25 '12 at 10:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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