<p>Let <span class="math-container">$L_1 = L_2 = \mathbb{N}$</span> and let <span class="math-container">$M \subseteq \mathbb{N}$</span> be a <a href="https://en.wikipedia.org/wiki/Maximal_set" rel="noreferrer">maximal set</a> and let <span class="math-container">$L = \mathbb{N} \setminus M$</span> be its complement. Recall that <span class="math-container">$L$</span> is infinite, and that every computably enumerable (c.e.) subset <span class="math-container">$S \subseteq \mathbb{N}$</span> contains either finitely many elements of <span class="math-container">$L$</span> or all but finitely many elements of <span class="math-container">$L$</span>.</p>
<p>Let <span class="math-container">$f : \mathbb{N} \to \mathbb{N}$</span> be an enumeration of <span class="math-container">$L$</span> without repetitions. The map <span class="math-container">$f$</span> is not computable, or else <span class="math-container">$M$</span> would be a computable subset of <span class="math-container">$\mathbb{N}$</span>, which a maximal set is not.</p>
<p>We claim that <span class="math-container">$f$</span> is a counter-example to your question. Consider any c.e. subset <span class="math-container">$S \subseteq \mathbb{N}$</span>:</p>
<ol>
<li>If <span class="math-container">$S \cap L$</span> is finite then <span class="math-container">$f^{-1}(S) = f^{-1}(S \cap L)$</span> is finite (as <span class="math-container">$f$</span> is injective) and therefore a computable set.</li>
<li>If <span class="math-container">$S \cap L$</span> contains all but finitely many elements of <span class="math-container">$L$</span> then <span class="math-container">$f^{-1}(S) = f^{-1}(S \cap L)$</span> contains all but finitely many elements of <span class="math-container">$\mathbb{N}$</span>, therefore it is a computable set.</li>
</ol>
<p>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 <span class="math-container">$$\mathcal{E}  = \{S \subseteq \mathbb{N} \mid \text{$S$ is c.e.}\}$$</span> be the set of all c.e. subsets of <span class="math-container">$\mathbb{N}$</span>, and let <span class="math-container">$W : \mathbb{N} \to \mathcal{E}$</span> be a standard enumeration of c.e. sets. We can think of <span class="math-container">$\mathcal{E}$</span> as the &quot;computably open&quot; subsets of <span class="math-container">$\mathbb{N}$</span>. Indeed, they're closed under finite intersections and unions of <em>computable</em> families.</p>
<p>Say that a map <span class="math-container">$F : \mathcal{E} \to \mathcal{E}$</span> is <em>computable</em> if there exists a computable <span class="math-container">$r : \mathbb{N} \to \mathbb{N}$</span> such that <span class="math-container">$F(W_n) = W_{r(n)}$</span> for all <span class="math-container">$n \in \mathbb{N}$</span>. (This is just the standard notion of computability for <a href="https://en.wikipedia.org/wiki/Numbering_(computability_theory)" rel="noreferrer">numbered sets</a>.)</p>
<p>Your question can be rectified into a theorem like this (I just inserted the emphasized &quot;computable&quot;):</p>
<p><strong>Theorem:</strong> <em>A map <span class="math-container">$f : \mathbb{N} \to \mathbb{N}$</span> is computable if, and only if, its inverse image map <span class="math-container">$f^{-1} : \mathcal{P}(\mathbb{N}) \to \mathcal{P}(\mathbb{N})$</span> restricts to a <strong>computable</strong> map <span class="math-container">$f^{-1} : \mathcal{E} \to \mathcal{E}$</span>.</em></p>
<p>I will leave the (easy) proof as an exercise. The above can easily be generalized from number-theoretic maps to languages.</p>

CC BY-SA 4.0
2020-11-11T03:10:17.747Z
Thanks, I didn't know about maximal or r-maximal sets.  I can see how a computable inverse image map could be used to reconstruct $f$, by restricting $f^{-1}$ to singleton sets in its domain and using that to iterate over all the key-value pairs of $f$.  And vice versa, obtaining $f^{-1}$ from a computable $f$ by iterating over key-value pairs.  It's a little disappointing because I was hoping for a way to get computability for $f$ just from the structure of its domain/codomain.
causative
CC BY-SA 4.0
2020-11-10T12:49:44.360Z
2020-11-10T19:36:58.113Z
2020-11-10T19:36:58.113Z
Andrej Bauer
<p>Say <span class="math-container">$L_1$</span> and <span class="math-container">$L_2$</span> are computable languages.  Let <span class="math-container">$f$</span> be a function <span class="math-container">$L_1 \rightarrow L_2$</span>.  Let <span class="math-container">$C$</span> be the statement, &quot;if <span class="math-container">$l \subseteq L_2$</span> and <span class="math-container">$l$</span> is a computable language, the preimage <span class="math-container">$f^{-1}(l)$</span> is a computable language.&quot;  Does <span class="math-container">$C$</span> imply that <span class="math-container">$f$</span> is necessarily a computable function?</p>
<p><span class="math-container">$C$</span> is similar to the topological concept of continuity; a function <span class="math-container">$g$</span> between topological spaces is continuous if, for each open set <span class="math-container">$S$</span> in the codomain of <span class="math-container">$g$</span>, <span class="math-container">$g^{-1}(S)$</span> is an open set in the domain.  Here &quot;open sets&quot; have been replaced with &quot;computable languages.&quot;  (Computable languages can't actually be considered open sets here, because they aren't closed under infinite union.)</p>
<p>The converse, &quot;<span class="math-container">$f$</span> is computable implies <span class="math-container">$C$</span>,&quot; is easily proved.  If <span class="math-container">$f$</span> is computable, and <span class="math-container">$l$</span> is a computable language that's a subset of <span class="math-container">$L_2$</span>, then let <span class="math-container">$l' = f^{-1}(l)$</span>.  You can computably tell whether something is in <span class="math-container">$l'$</span> by first mapping it through <span class="math-container">$f$</span> and asking if the result is in <span class="math-container">$l$</span>.  So <span class="math-container">$l'$</span> must be a computable language, proving <span class="math-container">$C$</span>.</p>

CC BY-SA 4.0
2020-11-10T12:21:28.870Z
The computable languages *can* be seen as a form of *computable* topology because they are closed under *computable* unions. There is a whole area of computable topology which studies these phenomena.
Andrej Bauer
<computability><decidability>
Computability and continuity
causative
# Computability and continuity

(Asked by: username_0 on 2020-11-10)

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

**Tags:** computability, decidability

> **Comments:**
> **username_1**: The computable languages *can* be seen as a form of *computable* topology because they are closed under *computable* unions. There is a whole area of computable topology which studies these phenomena.  

---

## 1 answers

### Answer by username_1 on 2020-11-10. Score: 13 | Accepted answer

Let $L\_1 = L\_2 = \mathbb{N}$ and let $M \subseteq \mathbb{N}$ be a [maximal set](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Numbering_(computability_theory)).)

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.

> **Comments:**
> **username_0**: Thanks, I didn't know about maximal or r-maximal sets.  I can see how a computable inverse image map could be used to reconstruct $f$, by restricting $f^{-1}$ to singleton sets in its domain and using that to iterate over all the key-value pairs of $f$.  And vice versa, obtaining $f^{-1}$ from a computable $f$ by iterating over key-value pairs.  It's a little disappointing because I was hoping for a way to get computability for $f$ just from the structure of its domain/codomain.  

---

