Effective topos and computability in topological spaces

Question

The classical computability theory taking place in $\mathbb{N}$, can be extended to more general spaces, like $T_0$ second countable topological spaces $(X, \mathcal{O}, v)$ where $\mathcal{O}$ is a countable basis of $X$ and $v:\mathbb{N} \rightarrow \mathcal{O}$ a total surjection. Then we say that $f:X \rightarrow Y$ is computable if given any enumeration of all basic open sets containing $x$, one can compute (in the sense of Turing) an enumeration of all basic open sets contaning $f(x)$. Equivalently we can state that for any basic open set $O$ of $Y$, we have that $f^{-1}(O)$ is a recursively enumerable open in the sence that $f^{-1}(O)=\cup_n O_n$ where $O_n$ is a recursively enumerable sequence of basic open sets of $X$

This brings some sort of a generalization of Turing reduction, when $X$ and $Y$ are both the Cantor space.

Now, I am wondering if it is possible to have a categorical point of view on all this. My research brought me to Topoi, the effective topos and the recursive topos. I have some difficulties to understand what is the effective topos (as I have to understand what is the recursive topos).

Before I spend a lot of time to study them, I would like to know if there are somehow related to what I've stated above (i.e., does one of them contains in some way the computable functions between topological spaces ? is there only continuous functions between topological spaces in these Topos ? can we even talk about topological spaces in these topos ?) or are hey something completely different ?

I apologize if my question seems too general. Any answer will be appreciated :)

Answer 1

There are many realizability toposes, of which the effective topos is just one. Each realizability topos has its own internal language in which topology and analysis can be developed to a considerable degree. Thus we get many notions of computable topology, not just one.

If you are interested in computable topology in the effective topos specifically, but would like to study the topic without first learning the machinery, you should look at Dieter Spreen's JSL paper On Effective Topological Spaces (doi:10.2307/2586596, JSTOR).

If you are just getting into the topic of computable analysis, you should look at Klaus Weihrauch's Computable Analysis: an introduction.

If you would like to understand more generally why there are many kinds of computable topology, not just one, you can read my Ph.D. thesis. This may also serve as a general introduction to computable analysis and topology.

Answer 2

Look at the paper of Cockett and Hofstra on Turing categories. (Here is another link and also DOI: 10.1016/j.apal.2008.04.005.)

Answer 3

Without certain additional assumptions, the two characterizations of computability in topological spaces are not equivalent also in the case when uniformity is required in the second characterization. Indeed, the following property follows then from computability in the second sense: a partial recursive function $\iota$ exists such that, whenever $O$ is a basic open set of $Y$, $j$ is an index of $O$ in the given surjection of $\mathbb{N}$ onto the basis of $Y$, and $f^{-1}(O)$ is non-empty, then the number $j$ belongs to the domain of $\iota$, and the set with index $\iota(j)$ in the given surjection of $\mathbb{N}$ onto the basis of $X$ is a subset of $f^{-1}(O)$. On the other hand, computability in the first sense can be present without having this property. To construct an example for this, we can proceed as follows. We first construct such a partition of $\mathbb{N}$ into disjoint two-elements sets of the form {$n_0,n_0+1$},{$n_1,n_1+2$},{$n_2,n_2+3$},{$n_3,n_3+4$},$\ldots$ that no recursive function exists whose value at $j$ belongs to {$n_j,n_j+j+1$} for all $j$ in $\mathbb{N}$. Then we take $X=Y=\mathbb{N}$ with the discrete topology, its basis consisting of all singletons in $\mathbb{N}$, but with different surjections of $\mathbb{N}$ onto this basis. For the space $X$, let both numbers $n_i$ and $n_i+i+1$ be indices of the basic set {$i$}, and in the case of $Y$, let $j$ be the only index of {$j$}. Let $f(x)=x$ for all $x$ in $\mathbb{N}$. Then $f$ is computable in the first sense, since, given any enumeration $k_0,k_1,k_2,\ldots$ of the set {$n_x,n_x+x+1$}, we have the equality $x=|k_l-k_{l+1}|-1$, where $l$ is the first $m$ such that $k_m\ne k_{m+1}$. However, $f$ has not the above-formulated property.

For assumptions which guarantee the equivalence of the two characterizations, cf. Theorem 3.3 in M. Korovina's and O. Kudinov's paper "Towards Computability over Effectively Enumerable Topological Spaces", Electron. Notes Theor. Comput. Sci., 221 (2008) 115--125, https://doi.org/10.1016/j.entcs.2008.12.011 (Unfortunately, the formulation of the theorem needs a correction. For the validity of its conclusion some additional assumption is needed. For instance, it is sufficient to add the assumption that $\alpha i$ is empty for some $i$).

Remark. A partition of $\mathbb{N}$ with the properties used in the above counter-example can be made as follows. We take a sequence $k_0,k_1,k_2,\ldots\,$ of natural numbers which is dominated by no recursive function and satisfies $k_{l+1}>k_l+2l+1$ for all $l$ in $\mathbb{N}$. Then we form subsets $C_0,C_1,C_2,\ldots$ of $\mathbb{N}^2$ so that $C_0$ consists of the pairs $(k_l,k_l+2l+1)$ for $l=0,1,2,3,\ldots$, and, for all $r$ in $\mathbb{N}$, $C_{r+1}$ is obtained from $C_r$ by adding a pair $(\bar{n},\bar{m})$ of natural numbers such that $\bar{n}<\bar{m}$ and next three conditions are satisfied:
1. The numbers $\bar{n}$ and $\bar{m}$ occur in no pair from $C_r$.
2. Whenever $(n,m)\in C_r$, the inequality $\bar{m}-\bar{n}\ne m-n$ holds.
3. If $r$ is even then $\bar{n}$ is the least natural number which occurs in no pair from $C_r$, otherwise $\bar{m}-\bar{n}$ is the least positive integer different from all differences $m-n$, where $(n,m)\in C_r$.
Let $C$ be the union of the sets $C_0,C_1,C_2,\ldots$ Then, for any $j$ in $\mathbb{N}$, exactly one pair $(n,m)$ in $C$ exists such that $m-n=j+1$. We set $n_j=n$ for this pair.