Computability and continuity

Question

Say $L_1$ and $L_2$ are computable languages. Let $f$ be a function $L_1 \rightarrow L_2$. Let $C$ be the statement, "if $l \subseteq L_2$ and $l$ is a computable language, the preimage $f^{-1}(l)$ is a computable language." Does $C$ imply that $f$ is necessarily a computable function?

$C$ is similar to the topological concept of continuity; a function $g$ between topological spaces is continuous if, for each open set $S$ in the codomain of $g$, $g^{-1}(S)$ is an open set in the domain. Here "open sets" have been replaced with "computable languages." (Computable languages can't actually be considered open sets here, because they aren't closed under infinite union.)

The converse, "$f$ is computable implies $C$," is easily proved. If $f$ is computable, and $l$ is a computable language that's a subset of $L_2$, then let $l' = f^{-1}(l)$. You can computably tell whether something is in $l'$ by first mapping it through $f$ and asking if the result is in $l$. So $l'$ must be a computable language, proving $C$.

Answer 1

Let $L_1 = L_2 = \mathbb{N}$ and let $M \subseteq \mathbb{N}$ be a maximal set and let $L = \mathbb{N} \setminus M$ be its complement. Recall that $L$ is infinite, and that every computably enumerable (c.e.) subset $S \subseteq \mathbb{N}$ contains either finitely many elements of $L$ or all but finitely many elements of $L$.

Let $f : \mathbb{N} \to \mathbb{N}$ be an enumeration of $L$ without repetitions. The map $f$ is not computable, or else $M$ would be a computable subset of $\mathbb{N}$, which a maximal set is not.

We claim that $f$ is a counter-example to your question. Consider any c.e. subset $S \subseteq \mathbb{N}$:

1. If $S \cap L$ is finite then $f^{-1}(S) = f^{-1}(S \cap L)$ is finite (as $f$ is injective) and therefore a computable set.
2. If $S \cap L$ contains all but finitely many elements of $L$ then $f^{-1}(S) = f^{-1}(S \cap L)$ contains all but finitely many elements of $\mathbb{N}$, therefore it is a computable set.

In your question you hint at the analogy between computability and continuity. Indeed there is one, but we need to be a bit more sensitive about computability. Let $$\mathcal{E} = \{S \subseteq \mathbb{N} \mid \text{$S$ is c.e.}\}$$ be the set of all c.e. subsets of $\mathbb{N}$, and let $W : \mathbb{N} \to \mathcal{E}$ be a standard enumeration of c.e. sets. We can think of $\mathcal{E}$ as the "computably open" subsets of $\mathbb{N}$. Indeed, they're closed under finite intersections and unions of computable families.

Say that a map $F : \mathcal{E} \to \mathcal{E}$ is computable if there exists a computable $r : \mathbb{N} \to \mathbb{N}$ such that $F(W_n) = W_{r(n)}$ for all $n \in \mathbb{N}$. (This is just the standard notion of computability for numbered sets.)

Your question can be rectified into a theorem like this (I just inserted the emphasized "computable"):

Theorem: A map $f : \mathbb{N} \to \mathbb{N}$ is computable if, and only if, its inverse image map $f^{-1} : \mathcal{P}(\mathbb{N}) \to \mathcal{P}(\mathbb{N})$ restricts to a computable map $f^{-1} : \mathcal{E} \to \mathcal{E}$.

I will leave the (easy) proof as an exercise. The above can easily be generalized from number-theoretic maps to languages.