Must a function that 'preserves r.e.-ness' be computable itself?

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?

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.

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.