# Comparing computability in two topologies

Djamel Eddine Amir, Mathieu Hoyrup

► To cite this version:

Djamel Eddine Amir, Mathieu Hoyrup. Comparing computability in two topologies. The Journal of Symbolic Logic, 2023, pp.1-19. 10.1017/jsl.2023.17. hal-03702999

HAL Id: hal-03702999

https://inria.hal.science/hal-03702999

Submitted on 23 Jun 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Comparing computability in two topologies

Djamel Eddine Amir and Mathieu Hoyrup

Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France
djamel-eddine.amir@loria.fr, mathieu.hoyrup@inria.fr

Abstract

Computable analysis provides ways of representing points in a topo-
logical space, and therefore of defining a notion of computable points
of the space. In this article, we investigate when two topologies on the
same space induce different sets of computable points.

We first study a purely topological version of the problem, which
is to understand when two topologies are not σ-homeomorphic. We
obtain a characterization leading to an effective version, and we prove
that two topologies satisfying this condition induce different sets of
computable points. Along the way, we propose an effective version of
the Baire category theorem which captures the construction technique,
and enables one to build points satisfying properties that are co-meager
w.r.t. a topology, and are computable w.r.t. another topology. Finally,
we generalize the result to three topologies and give an application
to prove that certain sets do not have computable type, i.e. have a
homeomorphic copy that is semicomputable but not computable.

Contents

<table>
  <tbody>
    <tr>
      <td>1</td>
      <td>Introduction</td>
      <td>2</td>
    </tr>
    <tr>
      <td>1.1</td>
      <td>Content</td>
      <td>3</td>
    </tr>
    <tr>
      <td>1.2</td>
      <td>Background</td>
      <td>4</td>
    </tr>
    <tr>
      <td>2</td>
      <td>A computable Baire category theorem</td>
      <td>5</td>
    </tr>
    <tr>
      <td>2.1</td>
      <td>On the Baire space</td>
      <td>6</td>
    </tr>
    <tr>
      <td>2.2</td>
      <td>Extension to computable Polish spaces</td>
      <td>9</td>
    </tr>
    <tr>
      <td>3</td>
      <td>Generically weaker topology</td>
      <td>10</td>
    </tr>
    <tr>
      <td>3.1</td>
      <td>Definition</td>
      <td>11</td>
    </tr>
    <tr>
      <td>3.2</td>
      <td>Characterization</td>
      <td>12</td>
    </tr>
  </tbody>
</table>
<table><tr><td>3.3 Examples</td><td>14</td></tr><tr><td>3.4 Effective version</td><td>15</td></tr><tr><td>3.5 Weihrauch degree</td><td>18</td></tr><tr><td>3.6 Level of generality</td><td>19</td></tr><tr><td><b>4 Three topologies</b></td><td><b>23</b></td></tr><tr><td>4.1 τ-generically weaker topology</td><td>24</td></tr><tr><td>4.2 Effective version</td><td>25</td></tr><tr><td><b>5 An application</b></td><td><b>27</b></td></tr><tr><td>5.1 Background on computable type</td><td>27</td></tr><tr><td>5.2 An application</td><td>28</td></tr></table>

# 1 Introduction

Computable analysis provides a way to perform computations on mathematical objects, by representing them using infinite sequences of bits or natural numbers. A class of objects can be represented in several ways, and the choice of the representation has a direct impact on the computation power of the Turing machine. In particular, each representation induces its own class of computable objects. In this article, we are interested in understanding when two representations on a set induce different subsets of computable points. This problem being too general to be analyzed, we restrict our attention to standard representations of countably-based topological spaces. It is a widespread class of representations capturing most natural cases, and it enables us to develop a topological understanding of the problem.

With this restriction, the problem can be stated as follows: given two countably-based topologies on the same set, when do they induce different sets of computable points?

Our main goals are to clarify the relationship between topology and computability, and to obtain general results that can be applied in concrete cases to separate computability notions. Indeed, such separation results can be challenging in practice, which means that a theoretical development of this problem is needed. Moreover, understanding when a separation result is possible is at least more informative as the separation result itself. We give an application which would be tedious to obtain directly, which is to build a copy of a given compact set which is semicomputable but not computable.

In order to study the problem of separating the notions of computable points associated to two topologies, we first relativize it, which yields a purely topological problem: whether two topologies are σ-homeomorphic,
i.e., whether the space can be decomposed as a countable union of subsets
such that the two topologies agree on each subset. The relationship between
the computability-theoretic content of points and the σ-homeomorphism
class of the space was thoroughly investigated by Kihara, Pauly and Ng
[KP22, KNP19].

In this article, we use Baire category to study the problem of comparing
two topologies and their computable contents, so we need one of the two
topologies to be Polish, or that the space can also be endowed with a third
topology which is Polish.

Given a set with a Polish topology τ and a weaker topology τ', we give a
characterization of the case when τ and τ' are not σ-homeomorphic. We then
use this characterization to propose an effective version, implying that the
two topologies induce different sets of computable points. We also extend
the results to the case when τ is not Polish, but a third Polish topology is
available.

The constructions underlying the separation results are based on the
priority method with finite injury. We recast the construction into a more
general result of independent interest. It is an effective version of the Baire
category theorem, in which simple topological conditions are identified that
make the construction possible.

**1.1 Content**

Let $(X, \tau)$ be a Polish space and $\tau'$ a countably-based topology on $X$ that is weaker than $\tau$, i.e. such that every $\tau'$-open set is also $\tau$-open. For the effective results, we will also assume that these topologies are effective in some sense.

In Section 2, we start with an effective version of the Baire category
theorem that builds $\tau$-computable points in a set that is co-meager w.r.t. $\tau$
(Theorem 2.2). This result captures the building technique that is needed
for the rest of the paper, and is based on the priority method. This theorem
is of independent interest and can hopefully be applied in other contexts.

In Section 3 we introduce a definition expressing that $\tau'$ is “significantly weaker” than $\tau$ in the sense that when $\tau'$ and $\tau$ coincide on a set, that set must be small in the sense of Baire category. We then say that $\tau'$ is generically weaker than $\tau$ (Definition 3.3). This notion immediately implies that $\tau'$ is not $\sigma$-homeomorphic to $\tau$. Using a result by Solecki and Pawlikowski-Sabok, we then show that this apparently stronger notion is actually the general case, up to restricting to some subspace: $\tau'$ is not $\sigma$-homeomorphic to $\tau$ if and only if there exists a Polish subspace $(Y, \tau_Y)$ of $(X, \tau)$ on which the
subspace topology $\tau'_Y$ is generically weaker than the subspace topology $\tau_Y$ (Theorem 3.3). We then prove that when $\tau'$ is generically weaker than $\tau$ in an effective way, there exist $\tau'$-computable points that are not $\tau$-computable (Theorem 3.1). This construction is obtained by applying the effective Baire category theorem from Section 2.

In Section 4 we generalize the results to a case when the two topologies to be compared are not Polish, but a third topology is available, which is Polish.

We end in Section 5 with an application, which is a complete proof of a result announced in [AH22a] about the notion of computable type (Theorem 5.2).

## 1.2 Background

We assume familiarity with basic notions from computability theory: **computationally enumerable (c.e.)** subset of $\mathbb{N}$, **computable function** from $\mathbb{N}$ to $\mathbb{N}$ or from the Baire space $\mathcal{N} = \mathbb{N}^\mathbb{N}$ to itself. We now recall a few classical notions from computable analysis, that can be found in [Wei00] or [Sch21].

An **effective countably-based space** is a topological space $(X, \tau)$ consisting with a numbered basis $(B_i)_{i \in \mathbb{N}}$ and a c.e. set $E \subseteq \mathbb{N}^3$ such that $B_i \cap B_j = \bigcup_{(i,j,k) \in E} B_k$. A set $U \subseteq X$ is an **effective open set** if $U = \bigcup_{\sigma \in W} B_\sigma$ for some c.e. set $W \subseteq \mathbb{N}$.

The **Baire space** $\mathcal{N} = \mathbb{N}^\mathbb{N}$ endowed with the product of the discrete topology is naturally an effective countable-based $T_0$-space. Basic open sets are given by the **cylinders**: if $\sigma \in \mathbb{N}^*$ is any finite sequence of natural numbers, then the cylinder $[\sigma]$ is the set of infinite extensions of $\sigma$.

A **representation** of a set $X$ is a surjective partial map $\delta_X : \mathcal{N} \to X$. A $\delta_X$-name of $x \in X$ is any $p \in \text{dom}(\delta_X)$ such that $\delta_X(p) = x$. A point $x \in X$ is **computable** if it has a computable name.

A function $f : X \to Y$ between represented spaces is **computable** if there exists a computable partial function $F : \mathcal{N} \to \mathcal{N}$ such that $f \circ \delta_X = \delta_Y \circ F$. $F$ is called a **realizer** of $f$.

An effective countably-based $T_0$-space $X$ can be equipped with its **standard representation** $\delta_X$ encoding a point by any enumeration its basic neighborhoods, and defined as follows: a $\delta_X$-name of $x$ is any $p \in \mathcal{N}$ such that for all $i \in \mathbb{N}$, $x \in B_i \iff \exists n \in \mathbb{N}, p(n) = i + 1$. We will say that a point $x \in X$ is **$\tau$-computable** if $x$ is computable w.r.t. the standard representation associated with the topology $\tau$. A function $f : X \to Y$ between effective countable-based $T_0$-spaces is computable if and only if the preimages of basic open sets $f^{-1}(B_i^Y)$ are effectively open, uniformly in $i$.
A **computable metric space** is a metric space $(X, d)$ coming with a dense sequence $(s_i)_{i \in \mathbb{N}}$ such that the function $(i, j) \mapsto d(s_i, s_j)$ is computable. It is an effective countably-based space, by taking the basis of metric balls $B(s_i, r)$ for positive rational $r$.

A **computable Polish space** is a computable metric space whose metric is complete. For every computable Polish space, there exists a computable surjective function $f : \mathcal{N} \to X$ which is effectively open, i.e. such that the images of cylinders $f([\sigma])$ are effectively open, uniformly in $\sigma$ (see [Sel15] for instance).

On a set $X$ endowed with two effective countably-based topologies $\tau_1, \tau_2$, we saw that $\tau_1$ is **effectively weaker** than $\tau_2$ if the basic $\tau_1$-open sets are effective $\tau_2$-open sets, uniformly.

## 2 A computable Baire category theorem

In this section, we prove an effective version of the Baire category theorem. In a computable Polish space, it allows to build points in a co-meager set, that are computable w.r.t. another topology. It will be applied in the next sections to build points with specific properties.

The Baire category theorem is known to help proving existence results. First, it has many classical applications in mathematics, some of which can be found in the survey [Jon99] by Jones. Computable versions of the Baire category theorem have been developed. The simplest one allows to build computable points, and was studied by Yasugi, Mori and Tusjii [YMT99], Brattka [Bra01], Brattka, Hendtlass and Kreutzer [BHK18], Kalantari [Kal03]. Jockush [Joc80] introduced 1-genericity as an effective version of Baire category that enables one to build 0'-computable points. A notion of genericity that enables one to build points that are computable w.r.t. a given topology was proposed by Hoyrup in [Hoy17]. A complexity-theoretic version of Baire category was introduced by Breutzmann, Juedes and Lutz [BJL04] in order to build polynomial-time computable points.

We work in a computable Polish space $(X, \tau)$, coming with an effectively weaker countably-based topology $\tau'$. We identify a condition for a sequence of subsets $A_n$ of $X$ which imply the existence of a $\tau'$-computable point in $\bigcap_n A_n$.

We first prove the result on the Baire space and then easily extend it to arbitrary computable Polish spaces. We work on the Baire space first for two reasons: it is simpler to work in a concrete space, and we need to decide whether a point belongs to a basic open set, which is only possible if the
basic open sets are clopen, i.e. if the space is zero-dimensional.

## 2.1 On the Baire space

The Baire space is endowed with its usual Polish topology $\tau$. We assume a countably-based topology $\tau'$ that is effectively weaker than $\tau$: its numbered basis $(V_i)_{i \in \mathbb{N}}$ consists of uniformly effective $\tau$-open sets. When topological notions are expressed with no reference to $\tau$ or $\tau'$, they are implicitly understood w.r.t. $\tau$ (for instance, interior, density, etc.).

We identify a condition on a sequence of subsets $A_n$ of the Baire space implying the existence of a $\tau'$-computable point in $\bigcap_n A_n$.

Let $O_\tau(\mathcal{N})$ be the set of effective $\tau$-open subsets of $\mathcal{N}$.

**Definition 2.1.** A density function for a set $A \subseteq \mathcal{N}$ is a function $\Delta : \mathbb{N}^* \to O_\tau(\mathcal{N})$ such that for all finite sequences $\sigma \in \mathbb{N}^*$, $\Delta(\sigma)$ is a non-empty subset of $[\sigma] \cap A$.

A set $A$ has a density function if and only if its interior is dense in $\mathcal{N}$. The simplest computable version of the Baire category theorem, as in [YMT99] or [Bra01], is that if sets $A_n$ have uniformly computable density functions, then $\bigcap_n A_n$ contains a $\tau$-computable point. However, having computable density functions is too strong for our purposes: typically, we want to build points that are *not* $\tau$-computable, but $\tau'$-computable. Therefore, the sets we will deal with usually have no computable density functions.

We introduce the following notion: $A$ is effectively dense if it has a density function which is computable with finitely many mind-changes, with some restriction on the way the algorithm can change its mind; the topology $\tau'$ is only involved in that restriction.

**Definition 2.2.** A set $A \subseteq \mathcal{N}$ is effectively dense w.r.t. $(\tau, \tau')$ if there exists a computable sequence of functions $\Delta[s] : \mathbb{N}^* \to O_\tau(\mathcal{N})$, with $s \in \mathbb{N}$, satisfying:

1. Each $\Delta[s](\sigma)$ is a non-empty subset of $[\sigma]$,

2. The functions $\Delta[s]$ converge to a density function $\Delta$: for each $\sigma$, if $s$ is sufficiently large then $\Delta[s](\sigma) = \Delta(\sigma) \subseteq [\sigma] \cap A$,

3. Each $\Delta[s](\sigma)$ is contained in the $\tau'$-closure of $\Delta[s+1](\sigma)$.

The programs behind the computable functions actually output indices of effective open sets, and for each $\sigma$ the sequence of indices is eventually constant as $s$ grows. One should think of $\Delta[s](\sigma)$ as a guess, at stage $s$,
for a subset of $[\sigma] \cap A$, which may be updated at a later stage if we obtain more information about $A$ and discover that it is a wrong guess. In particular, $\Delta[s](\sigma)$ may not be contained in $A$ for the first values of $s$.

What makes this notion more specific than finite mind-change computability is condition 3., which says that when there is a mind-change from $\Delta[s](\sigma)$ to $\Delta[s+1](\sigma)$, the $\tau'$-closures of the corresponding sets can only grow.

The main result of this section states that a $\tau'$-computable point satisfying countably many properties can be built, if these properties are effectively dense w.r.t. $(\tau, \tau')$. The proof implicitly used the priority method with finite injury.

**Theorem 2.1 (An effective Baire category theorem).** Let $A_n \subseteq \mathcal{N}$ be effectively dense sets w.r.t. $(\tau, \tau')$, uniformly in $n$. Their intersection $\bigcap_n A_n$ contains a $\tau'$-computable point.

Uniformity means that each $A_n$ comes with functions $\Delta_n[s](\sigma)$ witnessing its effective density, and that $\Delta_n[s](\sigma)$ is a computable function of $n, s, \sigma$.

*Proof.* Let $\Delta_n[s](\sigma)$ be uniformly computable functions witnessing the effective density of $A_n$. We can assume w.l.o.g. that the strings defining the open sets $\Delta_n[s](\sigma)$ are proper extensions of $\sigma$, which can be achieved by appending a 0 at the end of each string if needed. We recall that the basic $\tau'$-open sets $V_i$ are uniformly effective $\tau$-open sets. Let $V_i[s]$ be the finite union of cylinders obtained at stage $s$ in the computable enumeration of $V_i$.

The $\tau'$-computable point $x$ will be defined as a limit $x = \lim_s \lim_n \sigma_n[s]$ of a computable double-sequence of finite strings $\sigma_n[s]$. We will build this double-sequence with the following properties:

(i) The string $\sigma_{n+1}[s]$ extends some string defining $\Delta_n[s](\sigma_n[s])$. Therefore, $\sigma_{n+1}[s]$ properly extends $\sigma_n[s]$ and these strings converge to some $x[s] = \lim_n \sigma_n[s]$,

(ii) For each $n$, if $s$ is sufficiently large then $\sigma_n[s]$ is constant and $[\sigma_n[s]] \subseteq A_n$, so $x[s]$ converge to some $x \in \bigcap_n A_n$,

(iii) For $i \le r \le s$, if $x[r] \in V_i[r]$, then $x[s] \in V_i$ and $x \in V_i$.

*Claim 1.* Condition (iii) implies that $x$ is $\tau'$-computable.

*Proof of the claim.* It implies that for each $i$, one has

$$x \in V_i \iff \exists s \ge i \text{ such that } x[s] \in V_i[s]. \quad (1)$$
The backward direction is immediate, using $r = s$. The forward direction is also easy: if $x \in V_i$ then $x \in V_i[r]$ for some $r \ge i$, so $x[s] \in V_i[r]$ for some $s \ge r$ as $x[s]$ converges to $x$ and $V_i[r]$ is open. As $V_i[r] \subseteq V_i[s]$, one has $x[s] \in V_i[s]$ and moreover $s \ge r \ge i$.

As the right hand-side of (1) is c.e., the set $\{i : x \in V_i\}$ is c.e. so $x$ is $\tau'$-computable. $\square$

Therefore, conditions (i), (ii) and (iii) imply the result. It might be helpful to have in mind that in addition to condition (i), for each $s$, $\sigma_{n+1}[s]$ will be exactly one of the strings defining $\Delta_n[s](\sigma_n[s])$ for almost all $n$.

We now build the double-sequence $\sigma_n[s]$, by induction on $s$. We first consider the case $s = 0$: let $\sigma_0[0]$ be the empty string, and inductively let $\sigma_{n+1}[0]$ be the first (or any) string defining $\Delta_n[0](\sigma_n[0])$.

Let $s \in \mathbb{N}$ and assume that $\sigma_n[r]$ has been defined for all $r \le s$ and all $n$ and satisfy conditions (i) and (iii). Start with $n = 0$, and as long as $\Delta_n[s+1](\sigma_n[s]) = \Delta_n[s](\sigma_n[s])$, define $\sigma_n[s+1] = \sigma_n[s]$ and increment $n$. If equality holds for all $n$, then we are done, otherwise let $n$ be minimal such that $\Delta_n[s+1](\sigma_n[s]) \ne \Delta_n[s](\sigma_n[s])$.

We now define $\sigma_n[s+1]$. To lighten the notations, let $C = \Delta_n[s](\sigma_n[s])$ and $D = \Delta_n[s+1](\sigma_n[s])$. By assumption, $C$ is contained in the $\tau'$-closure of $D$. Let $V$ be the finite intersection of the $V_i$'s such that there exists $r$ satisfying $i \le r \le s$ and $x[r] \in V_i[r]$. It is a $\tau'$-open set.

*Claim 2. $V$ intersects $C$.*

*Proof of the claim.* Both $V$ and $C$ contain $x[s]$. Indeed, if $i \le r \le s$ and $x[r] \in V_i[r]$, then $x[s] \in V_i$ by induction hypothesis (iii), so $x[s] \in V$. Moreover, $x[s]$ extends $\sigma_{n+1}[s]$ which extends a string defining $\Delta_n[s](\sigma_n[s]) = C$ by (i), so $x[s] \in C$. $\square$

As $C$ is contained in the $\tau'$-closure of $D$, $V$ must intersect $D$. As a result, one can effectively find a string $\sigma$ such that $[\sigma] \subseteq D \cap V$. We then define $\sigma_n[s+1] = \sigma$, and inductively for $m \ge n$,

$\sigma_{m+1}[s+1]$ is the first string defining $\Delta_m[s+1](\sigma_m[s+1])$.

Conditions (i) and (iii) are satisfied by construction. Condition (ii) holds by induction on $n$: if $\sigma_n[s]$ is constant for sufficiently large $s$, then so is $\Delta_n[s](\sigma_n[s])$ is because $\Delta_n[s]$ converges to $\Delta_n$, so $\sigma_{n+1}[s+1] = \sigma_{n+1}[s]$ for sufficiently large $s$. As a result, $\sigma_{n+1}[s]$ is eventually constant when $s$ grows. $\square$
## 2.2 Extension to computable Polish spaces

The result easily extends to any computable Polish space $(X, \tau)$. Again, let $\tau'$ be an additional countably-based topology on $X$ which is effectively weaker than $\tau$, i.e. which has a basis $(V_i)_{i \in \mathbb{N}}$ consisting of uniformly effective $\tau$-open sets.

First, the definition of an effectively dense set extends as follows.

**Definition 2.3.** A set $A \subseteq X$ is **effectively dense w.r.t.** $(\tau, \tau')$ if there is a computable procedure that given a non-empty basic $\tau$-open set $B$, outputs a sequence of non-empty effective $\tau$-open sets $U_s \subseteq B$ satisfying:

* $U_s$ is eventually constant, with limit $U_\infty \subseteq B \cap A$,

* $U_s$ is contained in $\text{cl}_{\tau'}(U_{s+1})$.

The procedure actually outputs indices of effective open sets, and the sequence of indices is eventually constant.

*Example 2.1.* Here is the simplest example of an effectively dense set. If $A \subseteq X$ is an effective $\tau$-open set that is dense w.r.t. $\tau$, then $A$ is effectively dense w.r.t. $(\tau, \tau')$, whatever $\tau'$ is. Indeed, given $B$, one can directly compute $U = B \cap A$ with no mind-change. In other words, we define $U_s = U_\infty = B \cap A$ for all $s$.

**Theorem 2.1** can then be extended to any computable Polish space.

**Theorem 2.2** (An effective Baire category theorem). Let $(X, \tau)$ be a computable Polish space and $\tau'$ a countably-based topology that is effectively weaker than $\tau$. If $A_n \subseteq X$ are uniformly effectively dense w.r.t. $(\tau, \tau')$, then $\bigcap_n A_n$ contains a $\tau'$-computable point.

*Proof.* As $X$ is a computable Polish space, there exists a computable effectively open surjective map $f: \mathcal{N} \to X$ (see [Sel15] for instance). Using $f$, we can work in the Baire space, by considering the sets $f^{-1}(A_n)$ and the topology $\tau'_f := f^{-1}(\tau')$. It suffices to show that these sets are effectively dense w.r.t. $(\tau_\mathcal{N}, \tau'_f)$, and that a point $x \in \mathcal{N}$ is $\tau'_f$-computable if and only if $f(x)$ is $\tau'$-computable, so we can apply Theorem 2.1.

First, we show how to compute $\Delta_n[s](\sigma)$ associated to $f^{-1}(A_n)$. Given a finite string $\sigma$, compute a basic $\tau$-open set $B \subseteq f([\sigma])$, then compute $U_s$ and let $\Delta[s](\sigma) = [\sigma] \cap f^{-1}(U_s)$. The function $\Delta_n[s](\sigma)$ easily satisfies conditions 1. and 2. in Definition 2.2. We check condition 3. If $V \in \tau'$ is such that $f^{-1}(V)$ intersects $[\sigma] \cap f^{-1}(U_s)$, then $V$ intersects $U_s$. As $U_s$ is contained in the $\tau'$-closure of $U_{s+1}$, $V$ intersects $U_{s+1}$. As $U_{s+1} \subseteq B \subseteq f([\sigma])$, $f^{-1}(V)$
intersects $[\sigma] \cap f^{-1}(U_{s+1})$. Therefore, $\Delta[s](\sigma) = [\sigma] \cap f^{-1}(U_s)$ is contained in the $\tau'_f$-closure of $\Delta[s+1](\sigma) = [\sigma] \cap f^{-1}(U_{s+1})$.

Finally, the basic $\tau'_f$-neighborhoods of $x \in \mathcal{N}$ are precisely the preimages of the basic $\tau'$-neighborhoods of $f(x)$, so $x$ is $\tau'_f$-computable iff $f(x)$ is $\tau'$-computable. $\square$

In the sequel, we will see applications of this technique.

As the classical Baire category theorem, Theorem 2.2 is very modular: if one can build a $\tau'$-computable point satisfying properties $A_n$ and a $\tau'$-computable point satisfying properties $B_n$, both using Theorem 2.2, then one can build a $\tau'$-computable point satisfying $A_n$ and $B_n$ at the same time. We state a direct consequence which is particularly useful in practice. Say that $P \subseteq X$ is a $\Pi_2^0(\tau)$-set if $P$ is the intersection of a sequence of uniformly effective $\tau$-open sets. Under the same assumptions as Theorem 2.2, we obtain:

**Corollary 2.1.** Let $A_n \subseteq X$ be uniformly effective dense w.r.t. $(\tau, \tau')$ and $P \subseteq X$ be a $\Pi_2^0(\tau)$-set that is dense w.r.t. $\tau$. The set $P \cap \bigcap_n A_n$ contains a $\tau'$-computable point.

*Proof*. The set $P$ can be written as $\bigcap_n P_n$ where $P_n$ are uniformly effective $\tau$-open sets that are dense w.r.t. $\tau$. The sets $P_n$ are uniformly effectively dense w.r.t. $(\tau, \tau')$ as explained in Example 2.1. Therefore, one can apply Theorem 2.2 to the sets $A_n$ and $P_n$. $\square$

# 3 Generically weaker topology

We now come to the main topic of this article. Let $X$ be a set endowed with two countably-based topologies $\tau, \tau'$ where $\tau'$ is weaker than $\tau$. We want to understand when it is the case that every $\tau'$-computable point is $\tau$-computable.

We first study a relativized version of this problem, which is whether id : $(X, \tau') \to (X, \tau)$ is $\sigma$-continuous, i.e., whether $X$ can be decomposed as a countable union $X = \bigcup_{n \in \mathbb{N}} X_n$ such that the restriction of id to each $X_n$ is continuous w.r.t. the corresponding subspace topologies.

Formal relationship between these two problems can be obtained, topological conditions being equivalent to suitable relatizations of computability-theoretic conditions (more details can be found in [KP22, KNP19]). Let us just give more informal connections:
1. If id : $(X, \tau') \to (X, \tau)$ is $\sigma$-continuous, then there exists an oracle $A$ such that id is $\sigma$-computable relative to $A$. In the effective case when id is $\sigma$-computable, every $\tau'$-computable point is $\tau$-computable.

2. If id : $(X, \tau') \to (X, \tau)$ is not $\sigma$-continuous, then there exists a point $x$ whose $\tau$-names cannot be computed from its $\tau'$-names. We are looking for an effective version where such an $x$ can be effectively built, i.e., where $x$ is $\tau'$-computable but not $\tau$-computable.

We now give a characterization, when $\tau$ is Polish, of the cases when id :
$(X, \tau') \to (X, \tau)$ is not $\sigma$-continuous. We first give a sufficient condition, we
show that it is also necessary, up to restricting to some subspace, and we
study its effective version.

**3.1 Definition**

Let $(X, \tau)$ be a Polish space and $\tau'$ be a countably-based topology on $X$, which is weaker than $\tau$ (i.e., $\tau' \subseteq \tau$). A common reason preventing id : $(X, \tau') \to (X, \tau)$ to be $\sigma$-continuous is that any set $C \subseteq X$ on which id is continuous is *meager* w.r.t. $\tau$: it implies that $X$ cannot be decomposed as a countable union of such sets, because $(X, \tau)$ is a Polish space so it is not a countable union of meager sets by the Baire category theorem. We will see that this sufficient condition, which seems stronger at first, is actually necessary, up to restricting to some subspace (Theorem 3.3).

If $C$ is a subset of $X$, then a topology on $X$ induces a topology on $C$, obtained by intersecting the open sets with $C$. We say that $\tau$ and $\tau'$ agree on $C$ if they induce the same topology on $C$, which is the same as saying that the restriction of id : $(X, \tau') \to (X, \tau)$ to $C$ is continuous.

**Definition 3.1.** We say that $\tau'$ is **generically weaker** than $\tau$ if every $C \subseteq X$ on which $\tau$ and $\tau'$ agree is meager in $(X, \tau)$.

As discussed above, if $\tau'$ is generically weaker than $\tau$ then id : $(X, \tau') \to (X, \tau)$ is not $\sigma$-continuous so there exists $x \in X$ such that no Turing machine translates its $\tau'$-names into $\tau$-names. In Section 3.4 we will be interested in building such $x$ effectively to make it $\tau'$-computable.

That $\tau'$ is generically weaker than $\tau$ is a sufficient condition to make id :
$(X, \tau') \to (X, \tau)$ not $\sigma$-continuous. It is not a necessary condition, because
the discontinuity of id may happen only in a small set. In Section 3.6 we
show that it is almost necessary: if id : $(X, \tau') \to (X, \tau)$ is not $\sigma$-continuous,
then it is possible to restrict to a subset on which $\tau'$ is generically weaker
than $\tau$. It is a consequence of a result by Solecki [Sol98], Pawlikowski and Sabok [PS12].

We now investigate our notion of generically weaker topology.

## 3.2 Characterization

Checking that $\tau'$ is generically weaker than $\tau$ may be difficult, using the raw definition. We give a characterization that is easier to check in practice, and which will lead to an effective version.

The following notions witness that some $\tau$-open sets are far from being $\tau'$-open.

**Definition 3.2 (Witness).** Let $B$ be a non-empty $\tau$-open set.

* An $X$-witness is a non-empty $\tau$-open set $U \subseteq X$ that does not contain any non-empty $\tau'$-open set,

* A $B$-witness is a non-empty $\tau$-open set $U \subseteq B$ that does not contain any non-empty $V \cap B$ where $V$ is $\tau'$-open.

*Remark 3.1.* Let us list a few equivalent formulations that may help understanding this notion. $U$ is a $B$-witness if and only if:

1. In the subspace $B$ with the topology inherited from $\tau'$, $U$ has empty interior,

2. Every $\tau'$-open set intersecting $B$ already intersects $B \setminus U$,

3. $B \setminus U$ is $\tau'$-dense in $B$,

4. $U$ is contained in the $\tau'$-closure of $B \setminus U$.

The following algorithmic intuition is helpful: if $U$ is a $B$-witness, then for any point $x \in U$, it is not possible to know in finite time that $x$ belongs to $U$ if we are given a name of $x$ in the topology $\tau'$, even with the extra information that $x \in B$.

It is also helpful to have a formulation in terms of converging sequences, illustrated in Figure 1.

**Proposition 3.1.** A non-empty open set $U \subseteq B$ is a $B$-witness if and only if every $x \in U$ is a limit, in the topology $\tau'$, of a sequence $(x_n)_{n \in \mathbb{N}}$ contained in $B \setminus U$.
*Proof.* As the topology $\tau'$ is countably-based, the $\tau'$-closure of $B\setminus U$ is the set of limits of sequences in $B\setminus U$. Therefore, the condition in the statement is equivalent to $U$ being contained in the $\tau'$-closure of $B\setminus U$, which is condition 4. in Remark 3.1. $\square$

<figure><img src="image_2.png" /><figcaption>Figure 1: Illustration of Proposition 3.1: $x_n$ converge to $x$ in the topology $\tau'$</figcaption></figure>

We now state and prove the main result of this section, which is a characterization of generically weaker topologies.

**Proposition 3.2** (A characterization of generically weaker topologies). *Let $(X, \tau)$ be a Polish space and $\tau'$ be a weaker countably-based topology on $X$.*

$\tau'$ is generically weaker than $\tau$ if and only if every non-empty $\tau$-open set $B$ has a $B$-witness.

This result usually makes it very easy to check that $\tau'$ is generically weaker than $\tau$. In practice, one should start showing the existence of an $X$-witness, and then adapting the proof to any subspace $B \in \tau$ in order to obtain a $B$-witness. Moreover, this characterization will naturally lead to an effective version (Definition 3.3).

*Proof.* Assume that some non-empty $B \in \tau$ has no $B$-witness. We first show that for every non-empty $\tau$-open set $U \subseteq B$, there exists $V \in \tau'$ such that $B \cap \text{cl}_{\tau}(V) = B \cap \text{cl}_{\tau}(U)$. We express $U$ as the union of all the $\tau$-basic open sets $U_i \subseteq U$. Each $U_i$ is not a $B$-witness, so there exists $V_i \in \tau'$ such that $\emptyset \neq B \cap V_i \subseteq U_i$. Let $V = \cup_i V_i$. One has $B \cap V \subseteq U$, and $B \cap U \subseteq \text{cl}_{\tau}(V)$ as $V$ intersects each $B \cap U_i$. As a result, $B \cap \text{cl}_{\tau}(V) = B \cap \text{cl}_{\tau}(U)$.

Let $(U_n)_{n \in \mathbb{N}}$ be an enumeration of the basic $\tau$-open sets contained in $B$ and let $(V_n)_{n \in \mathbb{N}}$ be $\tau'$-open sets such that $B \cap \text{cl}_{\tau'}(V_n) = B \cap \text{cl}_{\tau'}(U_n)$. Let $C = \bigcap_n (U_n \Delta V_n)^c$. By definition of $C$, $\tau'$ and $\tau$ agree on $C$, because $U_n \cap C =$
$V_n \cap C$ for all $n$. We show that $C$ is $\tau$-co-meager in $B$. It is sufficient to show that each $U_n \Delta V_n$ is nowhere $\tau$-dense in $B$, and indeed

$$ 
\begin{align*}
B \cap \mathrm{cl}_{\tau}(U_n \Delta V_n) &= B \cap (\mathrm{cl}_{\tau}(U_n \setminus V_n) \cup \mathrm{cl}_{\tau}(V_n \setminus U_n)) \\
&\subseteq B \cap (\mathrm{cl}_{\tau}(U_n) \setminus V_n \cup \mathrm{cl}_{\tau}(V_n) \setminus U_n) \\
&= B \cap (\mathrm{cl}_{\tau}(V_n) \setminus V_n \cup \mathrm{cl}_{\tau}(U_n) \setminus U_n) \\
&= B \cap (\partial_{\tau}V_n \cup \partial_{\tau}U_n).
\end{align*}
$$

The sets $\partial_{\tau}V_n$ and $\partial_{\tau}U_n$ are $\tau$-boundaries of $\tau$-open sets, so they are nowhere $\tau$-dense. Therefore, $\tau'$ is not generically weaker than $\tau$.

Conversely, assume that each non-empty $B \in \tau$ has a $B$-witness. Let $C \subseteq X$ be such that $\tau'$ and $\tau$ agree on $C$, and let us show that $C$ is nowhere dense. Given a non-empty $\tau$-open set $B$, we need to find a non-empty $\tau$-open set $W \subseteq B$ disjoint from $C$. Let $U$ be a $B$-witness and $B'$ be a non-empty $\tau$-open set such that $\mathrm{cl}_{\tau}(B') \subseteq U$. If $B'$ is disjoint from $C$ then take $W = B'$. If $B'$ intersects $C$, then let $V \in \tau'$ be such that $B' \cap C = V \cap C$. $V$ intersects $U$ so $V$ intersects $B \setminus U$ hence $B \setminus \mathrm{cl}_{\tau}(B')$. Therefore $W = V \cap B \setminus \mathrm{cl}_{\tau}(B')$ is non-empty and disjoint from $C$. $\square$

We finally observe that in Definition 3.1, one can replace the condition of being “meager” by the apparently stronger condition of being “nowhere dense”, giving the same notion.

**Proposition 3.3** (Meager versus nowhere dense). Let $(X, \tau)$ be a Polish space and $\tau'$ be a countably-based topology on $X$ that is generically weaker than $\tau$.

If $\tau'$ and $\tau$ agree on a set $C \subseteq X$, then $C$ is nowhere dense.

*Proof.* The idea is that we can always assume that $C$ is a $G_{\delta}$-set w.r.t. $\tau$, and that a $G_{\delta}$-set is meager if and only if it is nowhere dense.

More precisely, if $\tau$ and $\tau'$ agree on $C$, then let $(U_n)_{n \in \mathbb{N}}$ be a basis of $\tau$ and let $V_n$ be $\tau'$-open sets such that $U_n \cap C = V_n \cap C$ for each $n$. The set $C' = \bigcap_n (U_n \Delta V_n)^c$ is a $G_{\delta}$-set w.r.t. $\tau$ containing $C$, and $\tau'$ agrees with $\tau$ on $C'$ because $U_n \cap C' = V_n \cap C'$ for each $n$. As $\tau'$ is generically weaker than $\tau$, it implies that $C'$ is meager. As $C'$ is a $G_{\delta}$-set, it is nowhere dense. As $C \subseteq C'$, $C$ is nowhere dense as well. $\square$

## 3.3 Examples

We give several examples of generically weaker topologies. They also illustrate how Proposition 3.2 makes it easy to show that a topology is generically weaker than another one.
*Example 3.1 (Cantor vs Scott).* Let $(X, \tau)$ be the Cantor space with the Cantor topology generated by the cylinders, and $\tau'$ be the Scott topology generated by the sets $\{x \in X : x_n = 1\}$, where $n \in \mathbb{N}$ and $x_n$ is the bit of $x$ at position $n$. It is easy to see that $\tau'$ is generically weaker than $\tau$.

First, the cylinder $[0]$ contains no non-empty Scott open set so it is an $X$-witness. More generally, for any cylinder $[u]$, the cylinder $[u0]$ contains no Scott open set intersected with $[u]$, so $[u0]$ is a $[u]$-witness.

When the topologies are induced by norms on a vector space, if a topology is strictly weaker than it is generically weaker, and there is no intermediate case. This phenomenon is at the core of Pour-El and Richards first main theorem [PER89].

**Proposition 3.4.** Let $X$ be a Banach space with a norm $\|\cdot\|_1$. Let $\|\cdot\|_2$ be a strictly weaker norm on $X$. The topology induced by $\|\cdot\|_2$ is generically weaker than the topology induced by $\|\cdot\|_1$.

*Proof.* Let $(x_n)_{n \in \mathbb{N}}$ be a sequence satisfying $\|x_n\|_1 = 1$ and $\|x_n\|_2 \to 0$. The ball $B_1(x, r/3)$ is a $B_1(x, r)$-witness because any $y \in B_1(x, r/3)$ is the limit in the $\|\cdot\|_2$ norm of $y + (2r/3)x_n \in B_1(x, r) \setminus B_1(x, r/3)$. $\square$

*Example 3.2 (Uniform norm versus $L^1$ norm).* Let $(C[0, 1], \tau_\infty)$ be the Polish space of continuous real-valued functions with the topology of the uniform norm, and $\tau_1$ be the topology of the $L^1$ norm. As $\tau_1$ is strictly weaker than $\tau_\infty$, $\tau_1$ is generically weaker than $\tau_\infty$ by Proposition 3.4.

*Example 3.3 (A non-example).* Let $(X, \tau)$ be the space of real numbers with the Euclidean topology, let $f(x) = x^2$ and $\tau'$ the initial topology of $f$, consisting of the open subsets of $\mathbb{R}$ that are symmetric around 0. Although $\tau'$ is strictly weaker than $\tau$, $\tau'$ is not generically weaker than $\tau$.

Indeed, there is no $(0, +\infty)$-witness, because on $(0, +\infty)$, $\tau$ and $\tau'$ induce the same topology. Note that there exists an $X$-witness: the open interval $(1, 2)$ contains no non-empty $\tau'$-open set.

## 3.4 Effective version

As previously discussed, if $\tau'$-generically weaker than $\tau$ then $\mathrm{id} : (X, \tau') \to (X, \tau)$ is not $\sigma$-continuous. In particular, there exists $x \in X$ whose $\tau$-names cannot be computed from $\tau'$-names.

We now want to effectively build such an $x$, i.e. we want to build a $\tau'$-computable point that is not $\tau$-computable. To achieve this, we need an effective version of the notion of generically weaker topology, which we formulate using the characterization given by Proposition 3.2.
**Definition 3.3.** Say that $\tau'$ is effectively generically weaker than $\tau$ if there is a computable function sending each basic $\tau$-open set $B$ to a $B$-witness $U_B$.

Note that $U_B$ can be assumed to be a basic $\tau$-open set (because a non-empty subset of a $B$-witness is also a $B$-witness), and the computation takes an index of $B$ as input and outputs an index of $U_B$.

We expect that in any concrete case, the proof that $\tau'$ is generically weaker than $\tau$ gives explicit witnesses and actually shows that $\tau'$ is effectively generically weaker than $\tau$. All the examples given in the previous section are effective. The following example is particularly interesting.

*Example 3.4 (Norms).* Proposition 3.4 is effective: if $\|\cdot\|_1$ and $\|\cdot\|_2$ are computable norms over a computable vector space (defined by Pour-El Richards in [PER89]), and $\|\cdot\|_2$ is strictly weaker than $\|\cdot\|_1$, then $\|\cdot\|_2$ is effectively generically weaker than $\|\cdot\|_1$ because witnesses are straightforward to compute.

We now state the main result of this section, giving relatively simple conditions implying that $\tau$ and $\tau'$ do not induce the same computable points. Our effective Baire category theorem (Theorem 2.2) makes the proof very easy: we essentially have to give the strategy to defeat one Turing machine attempting to $\tau$-compute $x$, and the effective Baire category theorem takes charge of the intertwining between the strategies.

**Theorem 3.1.** Let $(X, \tau)$ be a computable Polish space and $\tau'$ an effectively weaker countably-based topology. If $\tau'$ is effectively generically weaker than $\tau$ then there exists a $\tau'$-computable point that is not $\tau$-computable. Moreover, such a point can be found in any dense $\Pi_2^0(\tau)$-set.

*Proof.* We apply our effective Baire category theorem (Theorem 2.2). Let $A_n$ be the set of points $x$ whose $\tau$-neighborhood basis is not indexed by $W_n$, the $n$th c.e. subset of $\mathbb{N}$. We show that $A_n$ is effectively dense w.r.t. $(\tau, \tau')$ (Definition 2.3), uniformly in $n$.

First, we can assume that for each basic $\tau$-open set $B$, the $B$-witness $U_B$ satisfies: $U_B$ is contained in the $\tau'$-closure of $B \setminus \text{cl}_\tau(U_B)$. Indeed, it can be achieved by replacing $U_B$, which is a metric ball $B(s, r)$ by the ball $B(s, r/2)$.

Let us now show that $A_n$ is effectively dense w.r.t. $(\tau, \tau')$. Given a basic $\tau$-open ball $B$, we output $U_B$ as long as the index of $U_B$ does not appear in $W_n$, and then switch to $B \setminus \text{cl}_\tau(U_B)$ if it appears. More precisely, let

$$U_s = \begin{cases} U_B & \text{if } W_n[s] \text{ does not contain the index of } U_B, \\ B \setminus \text{cl}_\tau(U_B) & \text{otherwise.} \end{cases}$$
We check the three conditions in Definition 2.3. First, $U_s \subseteq B$ by definition. Condition 1: there is at most one mind-change, if the index of $U_B$ appears in $W_n$ at stage $s$. Condition 2: the limit set is $U_\infty = B \setminus \text{cl}_\tau(U_B)$ if the index of $U_B$ belongs to $W_n$, and $U_B$ if it does not. In any case, $W_n$ is not the set of basic $\tau$-neighborhoods of any point in $U_\infty$, so $U_\infty$ is contained in $A_n$. Condition 3: $U_B$ is contained in the $\tau'$-closure of $B \setminus \text{cl}_\tau(U_B)$, so $U_s$ is always contained in the $\tau'$-closure of $U_{s+1}$.

We can apply Theorem 2.2, which produces a $\tau'$-computable point that belongs to $\bigcap_n A_n$, i.e. that is not $\tau$-computable.

Moreover, one can build such a point in $\bigcap_n O_n$, where $O_n$ are dense uniformly effective open sets, because $O_n$ are uniformly effectively dense in the sense of Definition 2.3. $\square$

**Example 3.5 (Norms).** We continue with Proposition 3.4 and Example 3.4. Let $\|\cdot\|_1$ and $\|\cdot\|_2$ be complete computable norms over a computable vector space, in the sense of Pour-El Richards [PER89]. If $\|\cdot\|_2$ is strictly weaker than $\|\cdot\|_1$, then $\|\cdot\|_2$ is effectively generically weaker than $\|\cdot\|_1$, so by Theorem 3.1 there exists a point $x$ that is computable in the norm $\|\cdot\|_2$ but not in the norm $\|\cdot\|_1$. It is a particular case of Pour-El Richards First Main Theorem [PER89]. Pour-El and Richards' full result can actually be recovered by working in the Polish space formed by the graph of the linear operator, endowed with the product topology and with the topology on the first component. Details are explained in [Hoy14].

**Example 3.6 (Ergodic decomposition).** This example is taken from [Hoy14, Hoy17]. Theorem 3.4.1 in [Hoy17] states the existence of two non-computable shift-invariant ergodic measures $\mu_1, \mu_2$ whose average $\frac{\mu_1+\mu_2}{2}$ is computable. Theorem 3.1 can be applied to prove this result.

Let $X$ be the space of pairs of shift-invariant measures. Let $\tau$ be the product of the weak* topology. Consider the average operator $f: X \to \mathcal{M}(2^N)$ sending $(\mu_1, \mu_2)$ to $\frac{\mu_1+\mu_2}{2}$, and let $\tau'$ be the initial topology of $f$. Theorem 3.4.2 in [Hoy17] implies that $\tau'$ is effectively generically weaker than $\tau$, although it is not expressed in the same way. The idea is that if $(\mu_1, \mu_2)$ is a pair such that $\mu_1 \neq \mu_2$, then for $\lambda \in [0, 1]$, the pairs

$$((1 - \lambda)\mu_1 + \lambda\mu_2, (1 - \lambda)\mu_2 + \lambda\mu_1)$$

have the same $\tau'$-neighborhoods as $(\mu_1, \mu_2)$ and their proximity to $(\mu_1, \mu_2)$ in the topology $\tau$ can be freely controlled by the choice of $\lambda$.

In $(X, \tau)$, the set of pairs of ergodic measures is a dense $\Pi_2^0$-set. Therefore, Theorem 3.1 implies the existence of a pair $(\mu_1, \mu_2)$ of ergodic measures
which is $\tau'$-computable but not $\tau$-computable; in other words, $\mu_1$ and $\mu_2$ are not computable but their average is.

## 3.5 Weihrauch degree

If $x$ is a point provided by Theorem 3.1, then $\tau$-names of $x$ contain strictly more information than $\tau'$-names of $x$. The proof of Theorem 3.1 can be adapted to show what type of non-computable information can be encoded in $\tau$-names, that cannot be obtained from $\tau'$-names. Namely, computing $\tau$-names from $\tau'$-names is at least as hard as computing a limit, or equivalently the Turing jump.

Formally, we show that the problem of computing limits is Weihrauch reducible to the problem of converting $\tau'$-names into $\tau$-names. Let us recall the appropriate definitions, more details can be found in [BGP21].

**Definition 3.4.** Let $f: X \to Y$ and $g: Z \to W$ be functions between represented spaces.

Say that $f$ is **Weihrauch reducible** to $g$, written $f \leq_W g$, if there exist computable functions $H, K: \subseteq \mathcal{N} \to \mathcal{N}$ such that for any realizer $G: \subseteq \mathcal{N} \to \mathcal{N}$ of $g$, the function $p \mapsto H(G(K(p)), p)$ is a realizer of $f$.

Say that $f$ is **strongly Weihrauch reducible** to $g$, written $f \leq_W g$, if there exist computable functions $H, K: \subseteq \mathcal{N} \to \mathcal{N}$ such that for any realizer $G: \subseteq \mathcal{N} \to \mathcal{N}$ of $g$, the function $p \mapsto H(G(K(p)))$ is a realizer of $f$.

**Definition 3.5.** The function $\lim$ sends a converging sequence of elements of the Baire space to its limit.

**Theorem 3.2 (Weihrauch reduction of $\lim$ is necessary).** If $\tau'$ is effectively generically weaker than $\tau$, then $\lim$ is Weihrauch reducible to $\mathrm{id}: (X, \tau') \to (X, \tau)$.

*Proof idea.* The function $\lim$ is strongly Weihrauch equivalent to the function $\mathrm{id}: \mathcal{N} \to 2^\mathbb{N}$ sending $p \in \mathcal{N}$ to the set $\mathrm{id}(p) = \{p(n) : n \in \mathbb{N}\}$, so we show how to reduce $\mathrm{id}$ to $\mathrm{id}$.

Let $p \in \mathcal{N}$, be given as oracle. We apply the construction of the proof of Theorem 2.2. The sets $A_n$ are implicitly defined by their density functions approximations as follows: given $B$, let

$$U_s = \begin{cases} U_B & \text{if } n \notin \{p(0), \dots, p(s)\}, \\ B \setminus \mathrm{cl}_\tau(U_B) & \text{if } n \in \{p(0), \dots, p(s)\}. \end{cases}$$

The construction builds a point $x_p$ that is $\tau'$-computable (relative to $p$). If one is given $x_p$ in the topology $\tau$, together with $p$, then it is possible to
inductively find for each $n$ whether $n \in \text{im}(p)$. The idea is that if we are given $x_p$ in the topology $\tau$, then we can decide whether $x_p \in U_B$ or $x_p \in B \setminus \text{cl}_{\tau}(U_B)$, from which we can deduce whether $n \in \text{im}(p)$. $\square$

We do not know whether a strong Weihrauch reduction can be obtained. However, we will see in the next section that it is always possible to obtain a strong Weihrauch reduction, relative to some oracle.

## 3.6 Level of generality

We now show two results, based on theorems by Solecki and Pawlikowski-Sabok. The first one is that when $\text{id} : (X, \tau') \to (X, \tau)$ is not $\sigma$-continuous, $\tau'$ is generically weaker than $\tau$ after restricting to a subspace. The second result is another relationship between the discontinuity of $\text{id}$ and the difference between $\tau'$-computability and $\tau$-computability, expressed in terms of Weihrauch reducibility. We gather these results into one statement.

**Theorem 3.3.** Let $(X, \tau)$ be Polish, $\tau' \subseteq \tau$ be countably-based $T_0$ and let $f = \text{id} : (X, \tau') \to (X, \tau)$. The following conditions are equivalent:

1. $f$ is not $\sigma$-continuous,

2. There exists $Y \subseteq X$ such that $\tau_Y$ is Polish and $\tau'_Y$ is generically weaker than $\tau_Y$,

3. $\lim$ is Weihrauch reducible to $f$ relative to an oracle,

4. $\lim$ is strongly Weihrauch reducible to $f$ relative to an oracle.

In that case $(Y, \tau_Y)$ is even homeomorphic to the Baire space $N$. The proof uses a strong result from Descriptive Set Theory, Pawlikowski-Sabok's theorem [PS12]. This theorem says that every sufficiently definable map between metric spaces is either $\sigma$-continuous, or contains one particular function $P$, which is not $\sigma$-continuous. Let us state this result precisely.

A subset $A$ of a Polish space $X$ is **analytic** if it is the image of a continuous function $f: N \to X$. A set $A \subseteq X$ is **bianalytic** if both $A$ and $X \setminus A$ are analytic. A topological space is **analytic** if it embeds as an analytic subset of a Polish space. A function $f: X \to Y$ between analytic spaces is **bianalytic** if the preimage of every bianalytic set is bianalytic.

The Baire space $N = \mathbb{N}^\mathbb{N}$ is endowed with two different topologies, both obtained as the product topology of some topology on $\mathbb{N}$. The first one is the usual topology obtained $\tau_N$ from the discrete topology on $\mathbb{N}$. The second one, $\tau'_N$, is obtained by identifying $\mathbb{N}$ with $\{0\} \cup \{2^{-n} : n \in \mathbb{N}\} \subseteq \mathbb{R}$,
via $0 \mapsto 0$ and $n \mapsto 2^{-n+1}$ for $n \ge 1$. It makes $(\mathcal{N}, \tau'_\mathcal{N})$ homeomorphic to the Cantor space.

**Definition 3.6.** Pawlikowski's function is defined as

$$P = \mathrm{id} : (\mathcal{N}, \tau'_\mathcal{N}) \to (\mathcal{N}, \tau_\mathcal{N}).$$

**Theorem 3.4 (Pawlikowski-Sabok [PS12]).** Let $X, Y$ be analytic spaces and $f: X \to Y$ be bianalytic. Either $f$ is $\sigma$-continuous or $f$ contains $P$ in the following sense: there exist two topological embeddings $\varphi : (\mathcal{N}, \tau'_\mathcal{N}) \to X$ and $\psi : (\mathcal{N}, \tau_\mathcal{N}) \to Y$ such that $f \circ \varphi = \psi \circ P$.

This result was first proved by Solecki for Baire class 1 functions in [Sol98], and then improved in this form by Pawlikowski and Sabok. It was observed by Carroy (personal communication) that this result has a direct consequence in terms of Weihrauch reducibility: if $P$ embeds in $f$ as in the statement, then $P$ is strongly Weihrauch reducible to $f$ relative to an oracle. We also mention an effective version of the result by Debs [Deb14].

We use the result in our setting, showing at the same time that some version of the result holds when $X$ is not metrizable but still countably-based.

We start by reducing countably-based spaces to metrizable spaces. It is possible because the standard representation of countably-based spaces has very good properties, already exploited in [dBY09, dB13, CH20], that allow to reduce DST on countably-based spaces to DST on subspaces of the Baire space. We give another manifestation of this phenomenon, which is proved using similar techniques.

**Lemma 3.1 ($\sigma$-computable vs $\sigma$-computable realizer).** Let $X, Y$ be (effective) countably-based $T_0$-spaces with their standard representations. A function $f: X \to Y$ is $\sigma$-continuous ($\sigma$-computable) iff it has a $\sigma$-continuous ($\sigma$-computable) realizer.

*Proof.* We prove the effective version, the non-effective version being obtained by relativization to any oracle.

One implication is straightforward. Assume that $f$ is $\sigma$-computable, i.e. $X = \bigcup_{n \in \mathbb{N}} X_n$ and each $f|_{X_n}$ is computable. We can assume that the sets $X_n$ are pairwise disjoint, replacing $X_n$ with $X_n \setminus (X_0 \cup \cdots \cup X_{n-1})$ if needed. Each $f|_{X_n}$ has a computable realizer $F_n : \delta_X^{-1}(X_n) \to \mathcal{N}$. The combination of all $F_n$'s is a $\sigma$-computable realizer of $f$.

We now prove the other implication. Assume that $f$ has a $\sigma$-computable realizer $F : \mathrm{dom}(\delta_X) \to \mathcal{N}$, with $\mathrm{dom}(\delta_X) = \bigcup_{n \in \mathbb{N}} A_n$ and each $F|_{A_n}$ is
computable. For each $n \in \mathbb{N}$ and $\sigma \in \mathbb{N}^*$, let

$$X_{n,\sigma} = \{x \in \delta_X([\sigma]): A_n \text{ is dense in } \delta_X^{-1}(x) \cap [\sigma]\},$$

where a set $A$ is dense in a set $B$ if $B$ is contained in the closure of $A \cap B$.

Let us show that the restriction $f|_{X_{n,\sigma}}$ is computable. Let $B_i \subseteq Y$ be a basic open set. We want to show that the preimage of $B_i$ under this restriction is an effective open subset of $X_{n,\sigma}$, uniformly in $i$. As $\delta_Y \circ F$ is computable on $A_n$, there exists an effective open set $U_i \subseteq \mathcal{N}$, that can be computed uniformly in $i$, such that

$$U_i \cap A_n = (\delta_Y \circ F)^{-1}(B_i) \cap A_n = (f \circ \delta_X)^{-1}(B_i) \cap A_n. \quad (2)$$

Claim 3. One has

$$f^{-1}(B_i) \cap X_{n,\sigma} = \delta_X([\sigma] \cap U_i) \cap X_{n,\sigma}.$$

*Proof of the claim.* If $x \in X_{n,\sigma}$, then $x$ has a $\delta_X$-name $p \in [\sigma] \cap A_n$. If $x \in f^{-1}(B_i)$ then $p \in (f \circ \delta_X)^{-1}(B_i)$ so by (2), $p \in U_i$, which implies that $x \in \delta_X([\sigma] \cap U_i)$.

Conversely, if $x \in X_{n,\sigma}$ has a name $p \in [\sigma] \cap U_i$, then it has a name $q \in [\sigma] \cap U_i \cap A_n$ because $A_n$ is dense in $[\sigma] \cap \delta_X^{-1}(x)$ and $U_i$ is open. Again by (2), $q \in (f \circ \delta_X)^{-1}(B_i)$ so $x \in f^{-1}(B_i)$. $\square$

The set $\delta_X([\sigma] \cap U_i)$ is an effective open set, uniformly in $i$, so $f|_{X_{n,\sigma}}$ is computable.

It remains to show that $X = \bigcup_{n,\sigma} X_{n,\sigma}$. For $x \in X$, $\delta_X^{-1}(x)$ is Polish and is covered by $\bigcup_{n \in \mathbb{N}} A_n$, so some $A_n$ must be somewhere dense in $\delta_X^{-1}(x)$. In other words, there must exist some $n \in \mathbb{N}$ and some $\sigma \in \mathbb{N}^*$ such that $A_n$ is dense in $\delta_X^{-1}(x) \cap [\sigma]$, therefore $x \in X_{n,\sigma}$. $\square$

**Lemma 3.2.** On $\mathcal{N}$, the topology $\tau'_\mathcal{N}$ is generically weaker than $\tau_\mathcal{N}$.

*Proof.* Given a finite string $u \in \mathbb{N}^*$, a $[u]$-witness is given by $[u0]$. Indeed, every $p \in [u0]$ is the limit, in the topology $\tau'_\mathcal{N}$, of the sequence $p_n$ obtained by replacing 0 by $n$ in $p$ at position $|u|$. One has $p_n \in [u] \setminus [u0]$, which shows that $[u0]$ is a $[u]$-witness by Proposition 3.1. $\square$

*Proof of Theorem 3.3.* Of course, each one of conditions 2., 3. and 4. implies 1.

We show that 1. implies 2., 3. and 4. Let $\delta, \delta'$ be representations of $X$ that are admissible w.r.t. $\tau$ and $\tau'$ respectively. We can assume that they are
open and that $\delta$ is total as $\tau$ is Polish. Assume that $f$ is not $\sigma$-continuous. We apply Theorem 3.4 to $g := f \circ \delta' : \text{dom}(\delta') \to X$, where $X$ is endowed with the Polish topology $\tau$. We need to check that $\text{dom}(\delta')$ is analytic and $g$ is bianalytic. As $\text{id} : (X, \tau) \to (X, \tau')$ is continuous, it has a continuous realizer $I : \mathcal{N} \to \text{dom}(\delta')$, satisfying $\delta' \circ I = \delta$. The set

$$ \begin{aligned} R &= \{(p, q) \in \mathcal{N} \times \mathcal{N} : \delta'(p) = \delta(q)\} \\ &= \{(p, q) \in \mathcal{N} \times \mathcal{N} : \delta'(p) = \delta' \circ I(q)\} \end{aligned} $$

is a $\Pi_2^0$-subset of $\mathcal{N} \times \mathcal{N}$, therefore its first projection, which is exactly $\text{dom}(\delta')$, is analytic.

Let $A \subseteq (X, \tau)$ be bianalytic. Its preimage by $g$ is

$$ \begin{aligned} g^{-1}(A) &= \{p \in \text{dom}(\delta') : f \circ \delta'(p) \in A\} \\ &= \{p \in \text{dom}(\delta') : \exists q \in \mathcal{N}, \delta'(p) = \delta(q) \text{ and } \delta(q) \in A\} \end{aligned} $$

which is analytic. Applying the same argument to $g^{-1}(X \setminus A)$, we obtain that $g^{-1}(A)$ is bianalytic. Therefore $g$ satisfies the assumptions of Theorem 3.4.

Now, $g$ is not $\sigma$-continuous. Indeed, $g = f \circ \delta'$ has the same realizers as $f$. Applying Lemma 3.1 in one direction to $f$ and in the other direction to $g$, we have: $f$ is not $\sigma$-continuous, so it has no $\sigma$-continuous realizer as well as $g$, so $g$ is not $\sigma$-continuous.

We can now apply Theorem 3.4 to $g$, which provides topological embeddings

$$ \begin{aligned} \psi : (\mathcal{N}, \tau_{\mathcal{N}}) &\to (X, \tau), \\ \varphi : (\mathcal{N}, \tau'_{\mathcal{N}}) &\to (\mathcal{N}, \tau_{\mathcal{N}}), \end{aligned} $$

satisfying $g \circ \varphi = \psi \circ P$, i.e. $f \circ \delta' \circ \varphi = \psi \circ P$. As observed by Carroy (personal communication), it implies that $P$ is strongly Weihrauch reducible to $f$ relative to an oracle computing $\varphi$ and $\psi$. We have proved condition 4., which also implies condition 3.

Let us prove condition 2. Both $f$ and $P$ are the identity functions, with different topologies on their input and output spaces. Therefore, the condition $f \circ \delta' \circ \varphi = \psi \circ P$ can be rewritten as $\delta' \circ \varphi = \psi$. As a result, we have:

1. $\psi : (\mathcal{N}, \tau_{\mathcal{N}}) \to (X, \tau)$ is a topological embedding,

2. $\psi = \delta' \circ \varphi : (\mathcal{N}, \tau'_{\mathcal{N}}) \to (X, \tau')$ is continuous.
Let $Y = \text{im}(\psi)$ and $\tau_N''$ be the preimage of the topology $\tau'_Y$ by $\psi$. Both functions

$$ \psi : (\mathcal{N}, \tau_N) \to (Y, \tau_Y), $$

$$ \psi : (\mathcal{N}, \tau_N'') \to (Y, \tau'_Y) $$

are homeomorphisms. The first one comes from 1. above. The second one comes from the fact that $\psi$ is a bijection, is continuous and open, so it is a homeomorphism.

We now need to prove that $\tau_N''$ is generically weaker than $\tau_N$, which will conclude the proof.

By 2., $\tau_N''$ is weaker than $\tau_N'$ which is generically weaker than $\tau_N$, so $\tau_N''$ is also generically weaker than $\tau_N$. As a result, $\tau'_Y$ is generically weaker than $\tau_Y$. Note that $\tau_Y$ is Polish because $(Y, \tau_Y)$ is homeomorphic to $(\mathcal{N}, \tau_N)$.

<figure><img src="image_3.png" /></figure>

Although Theorem 3.3 shows that the topological versions of Weihrauch reducibility and strong Weihrauch reducibility are equivalent in this context, we do not know whether their computable versions are still equivalent. In particular, we do not know whether Theorem 3.2 can be improved to obtain a strong Weihrauch reduction.

*Open question* 1. Let $(X, \tau)$ be an effective Polish space and $\tau'$ be a countably-based $T_0$-topology that is effectively weaker than $\tau$. Are the following statements equivalent?

* $\lim$ is Weihrauch reducible to $\text{id} : (X, \tau') \to (X, \tau)$,

* $\lim$ is strongly Weihrauch reducible to $\text{id} : (X, \tau') \to (X, \tau)$.

# 4 Three topologies

The previous results have limitations. In this section, we propose a generalization that can be applied in other situations, which will be applied in the next section.

Let $\tau_1, \tau_2$ be two topologies on a set $X$, where $\tau_1$ is weaker than $\tau_2$. Our goal is again to build a point $x$ that is $\tau_1$-computable but not $\tau_2$-computable. The previous results cannot be applied if for instance:

* The topology $\tau_2$ is not Polish,

* Or the topology $\tau_2$ is Polish, but the sets where $\tau_1$ and $\tau_2$ agree are not $\tau_2$-meager.
In this section, we show how the results can be extended when there exists a third topology $\tau$ that is Polish and stronger than $\tau_2$. One can think of $\tau_1$ and $\tau_2$ as the topologies we want to compare, and of $\tau$ as an auxiliary topology which drives the construction.

## 4.1 $\tau$-generically weaker topology

Let $(X, \tau)$ be a computable Polish space and $\tau_1, \tau_2$ be effective countably-based topologies such that $\tau_1$ is effectively weaker than $\tau_2$ and $\tau_2$ is effectively weaker than $\tau$. In other words, the following functions are computable:

$$ (X, \tau) \xrightarrow{\text{id}} (X, \tau_2) \xrightarrow{\text{id}} (X, \tau_1) $$

We want to build a $\tau_1$-computable point that is not $\tau_2$-computable. The previous results can be extended to this more general setting.

**Definition 4.1.** We say that $\tau_1$ is $\tau$-generically weaker than $\tau_2$ if every set $C \subseteq X$ on which $\tau_1$ and $\tau_2$ agree is $\tau$-meager.

Again, “meager” can be equivalently replaced by “nowhere dense”, with the same argument as in Proposition 3.3. This notion is a generalization of Definition 3.1, which can be obtained by taking $\tau_1 = \tau'$ and $\tau_2 = \tau$.

Again, we give more concrete characterizations of this notion, which will eventually lead to an effective version.

**Proposition 4.1** (Characterization of $\tau$-generically weaker topologies). The following statements are equivalent:

1. $\tau_1$ is $\tau$-generically weaker than $\tau_2$,

2. For every non-empty $B \in \tau$, there exists $U \in \tau_2$ such that there is no $V \in \tau_1$ satisfying

$$ B \cap \mathrm{cl}_{\tau}(U) = B \cap \mathrm{cl}_{\tau}(V), $$

3. For every non-empty $B \in \tau$, there exist non-empty $\tau$-open sets $B'$, $B'' \subseteq B$ such that

$B'$ is disjoint from $\mathrm{cl}_{\tau_2}(B'')$,
and $B'$ is contained in $\mathrm{cl}_{\tau_1}(B'')$.

In condition 2., one can restrict $B$ and $U$ to be basic open sets in their respective topologies. In condition 3., $B$ and $B'$ can also be assumed to be basic open sets, but not $B''$.
Proof. 1. ⇒ 2. Let $B \in \tau$ be non-empty. We assume that for every $U \in \tau_2$ there exists $V \in \tau_1$ such that $B \cap \text{cl}_\tau(U) = B \cap \text{cl}_\tau(V)$, and show that $\tau_1$ is not $\tau$-generically weaker than $\tau_2$. Let $(U_n)_{n \in \mathbb{N}}$ be an enumeration of the basic $\tau_2$-open sets, and let $(V_n)_{n \in \mathbb{N}}$ be the corresponding $\tau_1$-open sets. Let $C = \bigcap_n (U_n \Delta V_n)^c$. By definition of $C$, each $U_n$ coincides with $V_n$ on $C$, so $\tau_1$ and $\tau_2$ agree on $C$. We show that $C$ is $\tau$-dense in $B$. Each $(U_n \Delta V_n)^c$ is a $G_\delta$-set for the topology $\tau$, so it is sufficient to show that each one of them is $\tau$-dense in $B$. The $\tau$-closure of its complement is $\text{cl}_\tau(U_n \Delta V_n)$, and its intersection with $B$ is contained in $\partial U_n \cup \partial V_n$, so it is nowhere $\tau$-dense in $B$. Therefore, $C$ is $\tau$-dense (even co-meager) in $B$. As a result, $\tau_1$ is not $\tau$-generically weaker than $\tau_2$.

2. ⇒ 1. Assume condition 2. holds. Let $C$ be such that $\tau_1$ and $\tau_2$ agree on $C$. We show that $C$ is nowhere $\tau$-dense. Let $B \in \tau$ be non-empty, we want to show that $B$ contain a non-empty $\tau$-open $W$ set disjoint from $C$. Let $U \in \tau_2$ come from condition 2. applied to $B$. As $\tau_1$ and $\tau_2$ agree on $C$, there exists $V \in \tau_1$ such that $U \cap C = V \cap C$. Let

$$W = B \cap (U \setminus \text{cl}_\tau(V) \cup V \setminus \text{cl}_\tau(U)).$$

$W$ is disjoint from $C$, is contained in $B$ and is non-empty: if it was empty, then $B \cap \text{cl}_\tau(U) = B \cap \text{cl}_\tau(V)$ would hold.

2. ⇒ 3. Let $B \in \tau$ and let $U \in \tau_2$ be such that there is no $V \in \tau_1$ satisfying $B \cap \text{cl}_\tau(U) = B \cap \text{cl}_\tau(V)$. Let $V$ be the largest $\tau_1$-open set such that $B \cap V \subseteq \text{cl}_\tau(U)$. One has $B \cap \text{cl}_\tau(V) \subseteq B \cap \text{cl}_\tau(U)$ so the inclusion is strict. Therefore, there exists a non-empty $\tau$-open set $B' \subseteq B \cap U$ that is disjoint from $V$. Take $B'' = B \setminus \text{cl}_\tau(U)$. As $U \in \tau_2$ contains $B'$ and is disjoint from $B''$, one has $B' \cap \text{cl}_{\tau_2}(B'') = \emptyset$. If a $\tau_1$-open set $W$ intersects $B'$, then $W \cap B \not\subseteq \text{cl}_\tau(U)$ so $W$ intersects $B \setminus \text{cl}_\tau(U) = B''$. Therefore, $B' \subseteq \text{cl}_{\tau_1}(B'')$.

3. ⇒ 2. Let $B \in \tau$ and let $B', B'' \subseteq B$ satisfy $B' \cap \text{cl}_{\tau_2}(B'') = \emptyset$ and $B' \subseteq \text{cl}_{\tau_1}(B'')$. Define $U = X \setminus \text{cl}_{\tau_2}(B'')$. Assume for a contradiction that there exists $V \in \tau_1$ such that $B \cap \text{cl}_\tau(U) = B \cap \text{cl}_\tau(V)$. $B'$ is contained in $B \cap U \subseteq B \cap \text{cl}_\tau(V)$, so $V$ intersects $B'$. As $B' \subseteq \text{cl}_{\tau_1}(B'')$, $V$ intersects $B''$. It implies that $U$ intersects $B''$, which contradicts the definition of $U$. □

## 4.2 Effective version

We introduce an effective version of being generically $\tau$-weaker, which will lead to Theorem 4.1. It is indeed an effective version, because the plain notion is obtained by relativization to an oracle.
Again $(X, \tau)$ is a computable Polish space and $\tau_1, \tau_2$ are countably-based topologies such that $\tau_1$ is effectively weaker than $\tau_2$ and $\tau_2$ is effectively weaker than $\tau$.

**Definition 4.2.** Say that $\tau_1$ is effectively $\tau$-generically weaker than $\tau_2$ if given $B \in \tau$, one can compute non-empty $B', B'' \in \tau$ and $U \in \tau_2$ such that:

* $B' \subseteq B \cap U$,

* $B'' \subseteq B \setminus U$,

* $B' \subseteq \text{cl}_{\tau_1}(B'')$, i.e., every $\tau_1$-open set intersecting $B'$ intersects $B''$.

<figure><img src="image_4.png" /><figcaption>Figure 2: Illustration of Definition 4.2</figcaption></figure>

Here, $B, B'$ and $U$ are basic open sets represented by indices, but $B''$ may be a general effective open set. Note that when $\tau_2 = \tau$, this definition is equivalent to Definition 3.3 (in one direction, take $U = B' = U_B$ and $B'' = B \setminus \text{cl}_\tau(U_B)$; in the other direction, take $U_B = B'$).

It is an effective version of condition 3. in Proposition 4.1, as the set $U$ witnesses that $B'$ is disjoint from $\text{cl}_{\tau_2}(B'')$. We now state the main result of this section. Again, it is easily proved thanks to our effective Baire category theorem 2.2.

**Theorem 4.1** ($\tau_1$-computable but not $\tau_2$-computable). Let $(X, \tau)$ be a computable Polish space, $\tau_1, \tau_2$ be effective countably-based topologies such that $\tau_1$ is effectively weaker than $\tau_2$ which is effectively weaker than $\tau$.

If $\tau_1$ is effectively $\tau$-generically weaker than $\tau_2$, then there exists $x \in X$ that is $\tau_1$-computable but not $\tau_2$-computable. Moreover, such a point can be found in any $\tau$-dense $\Pi_2^0(\tau)$-set.

*Proof.* As in the proof of Theorem 3.1, let $A_n$ be the set of points $x$ whose set of $\tau''$-neighborhoods is not $W_n$. The sets $A_n$ are uniformly effectively dense. Indeed, given $B$, output $U_s = B'$ as long as $W_n[s]$ does not contain the index of $U$, and then $U_s = B''$ if $W_n[s]$ contains that index. $\square$
# 5 An application

In this section, we give an application of Theorem 4.1 to give a clear and complete proof of a result that was stated in [AH22a], just with a proof idea. A complete proof appears in the unpublished preprint [AH22b] but is very technical and difficult to read. Our effective Baire category theorem enables us to give a simpler proof, as it captures most of the technicality of the construction.

Let us first introduce the relevant notions.

## 5.1 Background on computable type

A compact pair $(X, A)$ where $X$ is a compact Polish space and $A \subseteq X$ is a compact subset. The Hilbert cube is the computable Polish space $Q = [0, 1]^N$ endowed with the metric

$$d_Q(x, y) = \sum_{i \in \mathbb{N}} 2^{-i} |x_i - y_i|.$$

If $X$ is a compact space and $f, g : X \to Q$ are continuous functions, we define their distance $d_X(f, g) = \max_{x \in X} d_Q(f(x), g(x))$.

**Definition 5.1.** A compact set $X \subseteq Q$ is **semicomputable** if the set $Q \setminus X$ is an effective open set. A compact set $X \subseteq Q$ is **computable** if it is semicomputable and contains a dense computable sequence.

A compact pair $(X, A)$ has **computable type** if for every pair $(Y, B)$ in $Q$ that is homeomorphic to $(X, A)$, if $Y$ and $B$ are semicomputable then $Y$ is computable.

A compact space $X$ has **computable type** if the pair $(X, \emptyset)$ has computable type.

Miller [Mil02] proved that each sphere $S_n$ and each pair $(\mathbb{B}_{n+1}, \mathbb{S}_n)$ have computable type. Iljazović and Sušić [IS18] proved that for each compact manifold $M$ and each compact manifold with boundary $(M, \partial M)$ have computable type.

In [AH22a] we studied this property for simplicial pairs, i.e. compact pairs $(X, A)$ consisting of a finite simplicial complex $X$ and a subcomplex $A$. We gave a purely topological characterization of the simplicial pairs having computable type.

**Definition 5.2.** Let $\epsilon > 0$. A compact pair $(X, A) \subseteq Q$ has the $\epsilon$-surjection property if every continuous function $f : X \to X$ satisfying $f|_A = \text{id}_A$ and $d_X(f, \text{id}_X) < \epsilon$ is surjective.
**Theorem 5.1 ([AH22a])**. A simplicial pair $(X, A)$ has computable type if and only if it has the $\epsilon$-surjection property for some $\epsilon > 0$.

One implication of this theorem is that if $(X, A)$ fails to have the $\epsilon$-surjection property for every $\epsilon > 0$ in an effective way (Definition 5.3), then $(X, A)$ does not have computable type, i.e. has a copy $(Y, B)$ in $Q$ consisting of semicomputable sets, such that $Y$ is not computable.

In order to formulate the definition, we recall the definition of the Hausdorff distance between non-empty compact sets $A, B \subseteq Q$:

$$d_H(A, B) = \max \left( \max_{a \in A} \min_{b \in B} d_Q(a, b), \max_{b \in B} \min_{a \in A} d_Q(a, b) \right).$$

**Definition 5.3.** Let $(X, A)$ be a computable compact pair in $Q$. For $\epsilon > 0$, say that $\delta > 0$ is an $\epsilon$-witness if there exists a continuous function $f: X \to X$ satisfying $f|_A = \text{id}_A$ and $d_X(f, \text{id}_X) < \epsilon$, such that $d_H(X, f(X)) > \delta$.

Say that $(X, A)$ has **computable witnesses** if there exists a computable function sending each rational $\epsilon > 0$ to a rational $\epsilon$-witness $\delta > 0$.

## 5.2 An application

We now state the result from [AH22a], and give a proof by applying Theorem 4.1 and therefore using our effective Baire category theorem, Theorem 2.2.

**Theorem 5.2.** Let $(X, A) \subseteq Q$ be a pair of semicomputable sets. If it has computable witnesses, then $(X, A)$ does not have computable type, i.e. there exists a semicomputable copy of $(X, A)$ such that $X$ is not computable.

*Remark 5.1.* The statement given here is slightly stronger than the statement appearing in [AH22a]. Indeed, in [AH22a] the pair $(X, A)$ is assumed to be computable. However, the simpler proof presented here only needs $(X, A)$ to be semicomputable.

We now present the proof of this result.

We assume that $(X, A)$ is embedded as a semicomputable pair in $Q$ which has computable witnesses. First, if $X$ is not computable then $(X, A)$ does not have computable type and the result is proved. Therefore, we can assume for the rest of the proof that $X$ is computable (however, $A$ may not be computable). Consider the space $C(X, Q)$ of continuous functions from $X$ to $Q$. It is endowed with a complete computable metric $d(f, g) = \max_{x \in Q} d_Q(f, g(x))$, inducing a topology $\tau$. The subspace $\mathcal{I}(X, Q)$ of injective continuous functions from $X$ to $Q$ is a dense $\Pi_2^0$-subset, in particular it contains a dense computable sequence. We consider two weaker topologies $\tau_1$ and $\tau_2$ on $C(X, Q)$.
For each pair $(U, V)$ of finite unions of basic open subsets of $Q$, let

$$ \mathcal{V}_{U,V} = \{f \in \mathcal{C}(X, Q) : f(X) \subseteq U, f(A) \subseteq V\} $$

and let $\tau_1$ be the topology generated by the sets $\mathcal{V}_{U,V}$ as a subbasis.

For each basic open subset $B$ of $Q$, let

$$ \mathcal{U}_B = \{f \in \mathcal{C}(X, Q) : f(X) \cap B \neq \emptyset\} $$

and let $\tau_2$ be the topology generated by the sets $\mathcal{U}_B$ and $\mathcal{V}_{U,V}$ as a subbasis.

Our goal is to build an injective continuous function $f \in \mathcal{C}(X, Q)$ such that $f(X)$ and $f(A)$ are semicomputable but $f(X)$ is not computable; in other words, we want $f$ to be $\tau_1$-computable but not $\tau_2$-computable.

We will apply Theorem 4.1, so we need to show that $\tau_1$ is $\tau$-generally weaker than $\tau_2$.

**Lemma 5.1.** Let $X \subseteq Q$ be computable and $A \subseteq X$ be semicomputable. If the pair $(X, A)$ has computable witnesses, then the topology $\tau_1$ is effectively generically $\tau$-weaker than $\tau_2$.

*Proof.* We can assume that the centers of the basic metric balls in $(\mathcal{C}(X, Q), d)$ are injective functions. Given a metric ball $B = B_d(g_0, \epsilon)$ in $\mathcal{C}(X, Q)$ (where $g_0$ and $\epsilon$ are computable and $g_0$ is injective), we need to compute $B'$, $B''$, $U$ as in Definition 4.2. We are going to compute some suitable positive $\epsilon' < \epsilon$ and define:

$$ \bullet B' = B_d(g_0, \epsilon'), $$

$$ \bullet B'' = \{g \in \mathcal{C}(X, Q) : d(g, g_0) < \epsilon \text{ and } d_H(g(X), g_0(X)) > \epsilon'\}, $$

$$ \bullet U = \{g \in \mathcal{C}(X, Q) : d_H(g(X), g_0(X)) < \epsilon'\}. $$

These sets are clearly effective open sets in the respective topologies. Note that $B' \subseteq B \cap U$ and $B'' \subseteq B \setminus U$. We now explain how to choose $\epsilon'$ so that $B'$ is contained in $\mathrm{cl}_{\tau_1}(B'')$.

Compute $\delta < \epsilon/2$ such that $d_Q(x, y) < \delta$ implies $d_Q(g_0(x), g_0(y)) < \epsilon/2$. It implies that for all continuous functions $g, h : Q \to Q$,

$$ \text{If } d(h, g_0) < \delta \text{ and } d(g, \mathrm{id}_X) < \delta, \text{ then } d(h \circ g, g_0) < \epsilon. \quad (3) $$

$$ \text{Indeed, } d(h \circ g, g_0) \le d(h \circ g, g_0 \circ g) + d(g_0 \circ g, g_0) < \delta + \epsilon/2 \le \epsilon. $$

Compute $\beta$, a $\delta$-witness for $(X, A)$. Compute $\epsilon' \le \delta$ such that for all $x, y \in X$, $d_Q(g_0(x), g_0(y)) \le 2\epsilon'$ implies $d_Q(x, y) \le \beta$. It implies that for all non-empty compact sets $Y, Z \subseteq X$,

$$ \text{If } d_H(Y, Z) > \beta, \text{ then } d_H(g_0(Y), g_0(Z)) > 2\epsilon'. \quad (4) $$
We now check that $B'$ is contained in $cl_{\tau_1}(B'')$. Let $h \in B' = B_d(g_0, \epsilon')$. As $\beta$ is an $\delta$-witness, there exists $g: X \to X$ such that $g|_A = \text{id}_A$, $d(g, \text{id}_X) < \delta$ and $d_H(X, g(X)) > \beta$. We define $g_1 = h \circ g$ and show that $g_1 \in B''$. One has $d(g_1, g_0) < \epsilon$ by (3), and

$$d_H(g_1(X), g_0(X)) \ge d_H(g_0(X), g_0 \circ g(X)) - d_H(g_0 \circ g(X), h \circ g(X)) \\ > 2\epsilon' - d(g_0, h) > \epsilon' \quad \text{by (4),}$$

so $g_1 \in B''$. Moreover, $g_1(X) = h(g(X))$ is contained in $h(X)$ and $g_1(A) = h(g(A)) = h(A)$, so $h$ belongs to $cl_{\tau_1}(\{g_1\}) \subseteq cl_{\tau_1}(B'')$. We have proved that $B' \subseteq cl_{\tau_1}(B'')$. $\square$

*Proof of Theorem 5.2.* The subset of injective continuous functions from $X$ to $Q$ is a $\tau$-dense $\Pi_2^0(\tau)$-subset of $C(X, Q)$. Therefore, applying Theorem 4.1, there exists an injective continuous function $f: X \to Q$ that is $\tau_1$-computable but not $\tau_2$-computable. In other words, the pair $(f(X), f(A))$ is semicomputable, but $f(X)$ is not computable. $\square$

It may seem that using Theorems 2.2 and 4.1 is a rather convoluted path to proving Theorem 5.2. A more direct proof is indeed possible (see [AH22b]), but at the cost of readability, because there are many ingredients to take care of and to put together. Our abstract results isolate the appropriate concepts that make the construction possible, separating the specific properties of the application (Lemma 5.1) from the general construction (Theorems 2.2 and 4.1), and can hopefully be applied in other contexts.

Moreover, even for concrete pairs $(X, A)$, building a semicomputable copy which is not computable can be challenging and we are not aware of any simpler argument than the one presented here. Let us give such a concrete example. First, it is straightforward to show that the line segment does not have computable type: if $r > 0$ is a non-computable right-c.e. real number, then $[0, r]$ is a semicomputable copy of the line segment which is not computable. However it seems that there is no such simple argument for slightly more elaborate sets, such as the set $X$ shown in Figure 3, consisting of a disk attached to a pinched hollow torus. The results in [AH22a] imply that the set $X$ does not have the $\epsilon$-surjection property for any $\epsilon > 0$, and that it has computable witnesses (Definition 5.3), so Theorem 5.2 implies that $X$ does not have computable type.

We are not aware of any simpler and more concrete way of building a semicomputable copy of the set $X$ which is not computable. It seems that the technique underlying the proof of Theorem 5.2 is the only way to build
<figure><img src="image_5.png" /><figcaption>Figure 3: A space that does not have computable type, in a non-obvious way</figcaption></figure>

such a copy. We find it striking that the priority method is needed to prove
simple computability properties of such concrete sets.

References

[AH22a] Djamel Eddine Amir and Mathieu Hoyrup. Computability of finite simplicial complexes. In *ICALP 2022*, LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. To appear.

[AH22b] Djamel Eddine Amir and Mathieu Hoyrup. Computability of finite simplicial complexes. working paper or preprint, February 2022.

[BGP21] Vasco Brattka, Guido Gherardi, and Arno Pauly. Weihrauch complexity in computable analysis. In Vasco Brattka and Peter Hertling, editors, *Handbook of Computability and Complexity in Analysis, Theory and Applications of Computability*, pages 367–417. Springer, Cham, 2021.

[BHK18] Vasco Brattka, Matthew Hendtlass, and Alexander P. Kreuzer. On the uniform computational content of the Baire category theorem. *Notre Dame J. Formal Log.*, 59:605–636, 2018.

[BJL04] Josef M. Breutzmann, David W. Juedes, and Jack H. Lutz. Baire category and nowhere differentiability for feasible real functions. *Math. Log. Q.*, 50(4-5):460–472, 2004.

[Bra01] Vasco Brattka. Computable versions of Baire's category theorem. In Jiri Sgall, Ales Pultr, and Petr Kolman, editors, *MFCS*, pages 224–235, London, UK, 2001. Springer-Verlag.
[CH20] Antonin Callard and Mathieu Hoyrup. Descriptive complexity on non-Polish spaces. In Christophe Paul and Markus Bläser, editors, *37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France*, volume 154 of LIPICS, pages 8:1–8:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.

[dB13] Matthew de Brecht. Quasi-Polish spaces. *Ann. Pure Appl. Logic*, 164(3):356–381, 2013.

[dBY09] Matthew de Brecht and Akihiro Yamamoto. $\Sigma_\alpha^0$ - Admissible Representations (Extended Abstract). In Andrej Bauer, Peter Hertling, and Ker-I Ko, editors, *6th International Conference on Computability and Complexity in Analysis (CCA'09)*, volume 11 of OpenAccess Series in Informatics (OASICS), Dagstuhl, Germany, 2009. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

[Deb14] Gabriel Debs. Effective decomposition of $\sigma$-continuous Borel functions. *Fundamenta Mathematicae*, 224:187–202, 2014.

[Hoy14] Mathieu Hoyrup. Irreversible computable functions. In Ernst W. Mayr and Natacha Portier, editors, *31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), STACS 2014, March 5-8, 2014, Lyon, France*, volume 25 of LIPICS, pages 362–373. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2014.

[Hoy17] Mathieu Hoyrup. Genericity of weakly computable objects. *Theory Comput. Syst.*, 60(3):396–420, 2017.

[IS18] Zvonko Iljazović and Igor Sušić. Semicomputable manifolds in computable topological spaces. *J. Complex.*, 45:83–114, 2018.

[Joc80] Carl G. Jockush. Degrees of generic sets. In F. R. Drake and S. S. Wainer, editors, *Recursion Theory: its Generalisations and Applications*, pages 110–139. Cambridge University Press, 1980.

[Jon99] Sara Hawtrey Jones. Applications of the Baire category theorem. *Real Anal. Exchange*, 23(2):363–394, 1999.

[Kal03] Iraj Kalantari. Density & Baire category in recursive topology. In Vasco Brattka, Matthias Schröder, Klaus Weihrauch, and Ning
Zhong, editors, *Computability and Complexity in Analysis*, volume 302 of *Informatik Berichte*, pages 15–18. FernUniversität in Hagen, August 2003. International Conference, CCA 2003, Cincinnati, USA, August 28–30, 2003.

[KNP19] Takayuki Kihara, Keng Meng Ng, and Arno Pauly. Enumeration degrees and non-metrizable topology. arXiv:1904.04107, 2019.

[KP22] Takayuki Kihara and Arno Pauly. Point degree spectra of represented spaces. *Forum of Mathematics, Sigma*, 10:e31, 2022.

[Mil02] Joseph S. Miller. Effectiveness for embedded spheres and balls. *Electronic Notes in Theoretical Computer Science*, 66(1):127 – 138, 2002. CCA 2002, Computability and Complexity in Analysis (ICALP 2002 Satellite Workshop).

[PER89] Marian B. Pour-El and J. Ian Richards. *Computability in Analysis and Physics*. Perspectives in Mathematical Logic. Springer, Berlin, 1989.

[PS12] Janusz Pawlikowski and Marcin Sabok. Decomposing Borel functions and structure at finite levels of the Baire hierarchy. *Annals of Pure and Applied Logic*, 163(12):1748–1764, 2012.

[Sch21] Matthias Schröder. Admissibly represented spaces and Qcb-spaces. In Vasco Brattka and Peter Hertling, editors, *Handbook of Computability and Complexity in Analysis*. Springer, 2021.

[Sel15] Victor Selivanov. Towards the effective descriptive set theory. In Arnold Beckmann, Victor Mitrana, and Mariya Soskova, editors, *Evolving Computability*, pages 324–333, Cham, 2015. Springer International Publishing.

[Sol98] Slawomir Solecki. Decomposing Borel sets and functions and the structure of Baire class 1 functions. *Journal of the American Mathematical Society*, 11(3):521–550, 1998.

[Wei00] Klaus Weihrauch. *Computable Analysis*. Springer, Berlin, 2000.

[YMT99] Mariko Yasugi, Takakazu Mori, and Yoshiki Tsujii. Effective properties of sets and functions in metric spaces with computability structure. *Theoretical Computer Science*, 219(1-2):467–486, 1999.