Computable topological presentations

Mathieu Hoyrup, Alexander Melnikov, Keng Meng Ng

► To cite this version:

Mathieu Hoyrup, Alexander Melnikov, Keng Meng Ng. Computable topological presentations. The Journal of Symbolic Logic, In press. hal-04848634

HAL Id: hal-04848634

https://inria.hal.science/hal-04848634v1

Submitted on 19 Dec 2024

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
COMPUTABLE TOPOLOGICAL PRESENTATIONS

MATHIEU HOYRUP, ALEXANDER G. MELNIKOV, AND KENG MENG NG

ABSTRACT. A computable topological presentation of a space is given by an effective list of a countable basis of non-empty open sets so that the intersection of the basic sets is uniformly effectively enumerable.

We show that every countably based $T_0$-space has a computable topological presentation, and that, conversely, every (formal) computable topological presentation represents some Polish space. In the compact case, we give a computable uniform list of computable topological presentations such that every compact Polish space is represented by exactly one presentation from the list. Note that none of these results assume that the Polish (or $T_0$) spaces are effective.

Quite surprisingly, the *effectively compact* topological presentations turn out to be rather well behaved. Not only do such presentations allow one to construct a $\Delta_2^0$ (complete) metric compatible with the topology, but also, under a mild extra condition, they can be turned into a computably compact Polish presentation of the space.

# 1. INTRODUCTION

The present paper contributes to the recent framework [GKP17, HTMN20, HKS20] that seeks to establish the foundations of computably presented separable structures, akin to computable algebra [GK02, EG00], which focuses on countable discrete structures. The study of effectively presented algebraic structures has become a prominent part of recursion theory [AK00, EG00]. Various algebraic structures, such as linear orders, groups, and Boolean algebras, have been classified regarding different notions of effective presentability, distinguishing between these notions [Khi98, Fei70b, Hig61]. Following this pattern, many standard notions of effective presentability for spaces have been compared and separated in [BMN, HTMN20, HKS20, LMN23, BHTM23, KMN, GKP17] by various authors.

The main purpose of the present article is to demonstrate that the notion of a *computable topological presentation* (Def. 1.1) can be extremely ill-behaved in general. In the special case of compact spaces however, we obtain a number of positive results.

There are several definitions of a computable topological space that can be found in Kalantari and Weitkamp [KW85], Korovina and Kudinov [KK08], and Sreen [Spr90]. We will use the following version of this definition. This version appears to be standard in the modern literature; e.g., [KK17, Def. 3.1] and [GW07, Def. 3.1].

<footnote>Ng was supported by the Ministry of Education, Singapore, under its Academic Research Fund Tier 2 (MOE-T2EP20222-0018). Melnikov was partially supported by Rutherford Discovery Fellowship (Wellington) RDF-VUW1902, Royal Society Te Aparangi.</footnote>
**Definition 1.1.** A computable topological presentation of a countably-based topological space $M$ is given by a sequence $(B_i)_{i \in \omega}$ of non-empty basic open sets of $M$ and a computably enumerable set $W$ such that

$$B_i \cap B_j = \bigcup \{B_k : (i, j, k) \in W\},$$

for any $i, j \in \omega$.

Note that the important restriction in the definition is that the basic open sets must be non-empty. If one drops this assumption from the definition, then every countably-based space trivially admits a computable presentation, because one can pick any countable sub-basis and close it under finite intersections. The indices can clearly be assigned effectively, providing a countable basis for which finite intersections can be computed.

Conversely, under some mild restrictions, such as $\{k : (i, i, k) \in W\} \neq \emptyset$ (see section 3.2 for a detailed discussion), every c.e. set $W$ can be viewed as a (collection of indices of) some formal topological presentation. However it is not entirely clear that every formal computable topological presentation actually represents some space. Further, it is not difficult to see that non-homeomorphic spaces can share the exact same topological presentation. Indeed, any dense subset of a (computably topologically) represented space $M$ will share a same presentation as $M$. This contrasts greatly the situation with computable Polish presentations (Def. 1.2), and with pretty much every single notion of effective presentation ever used in algebra, such as finite presentations of groups [Hig61], and computable, decidable, and $\Sigma_n^0$-presentations of structures [EG00, AK00]). Nonetheless, despite its apparent weakness and limitations, the notion of a computable topological space is rather common in the literature.

**1.1. Which spaces are computable topological?** Whenever a notion of effective presentability is proposed, one of the first tasks is to test it by producing examples and counterexamples to understand its relationship with existing notions. For instance, the following question appears to be fundamental.

**Question 1:** Which (countably based $T_0$) topological spaces admit a computable topological presentation? Conversely, which (formal) topological presentations represent some topological space?

For example, which Polish spaces admit a computable topological presentation? To discuss what is known about partial solutions to the question, we need another commonly studied notion of effective presentability in topology (e.g., Ceitin [Cei59] and Moschovakis [Mos64]).

**Definition 1.2.** A Polish presentation of a (Polish-able) space $M$ is given by a countable metric space $X = ((x_i)_{i \in \omega}, d)$ so that the completion of $X$ is homeomorphic to $M$. A presentation $X$ is:

- right-c.e. if $\{r \in \mathbb{Q} : d(x_i, x_j) < r\}$ is c.e. uniformly in $i, j$;

- left-c.e. if $\{r \in \mathbb{Q} : d(x_i, x_j) > r\}$ is c.e. uniformly in $i, j$;

- computable if it is both left-c.e. and right-c.e.

We call each $x_i$ a special point of $M$.

It is well-known that the open rational balls $\{y : d(x_i, y) < r\}$ in every right-c.e. (upper semi-computable) Polish space form a computable topological presentation of the underlying topology (folklore). However, quite surprisingly, until
recently not much was known beyond this elementary observation. It has recently been shown in [KMN23] that every computable topological, locally compact Polish group admits a right-c.e. Polish presentation. Thus, for topological groups Definition 1.1 is well-behaved. But of course, this result from [KMN23] additionally assumes that the group operations are effective. Under the (seemingly strong) extra assumption of effective regularity, a computable topological space can be effectively metrised [Sch98]. In contrast with these results, there exists a computable topological (locally compact) Polish space not homeomorphic to any hyperarithmetical Polish space [MN23].

The strongest positive result in the literature known to us is as follows: Every $\Delta_2^0$-Polish space has a computable topological presentation [BMN]. The proof in [BMN] was a computability-theoretic approximation construction, mimicking those commonly encountered in computable structure theory. The resulting computable topological structure is $\Delta_3^0$-homeomorphic to that induced by the $\Delta_2^0$-metric. While such proofs tend to give more fine-grained analysis of the constructed objects, they clearly have their limitations. For example, it is not clear at all whether the construction from [BMN] can be iterated to show that every arithmetical space is computable topological, let alone every hyperarithmetical space or beyond.

The main technical idea of the present article is to abandon the effective dynamic intuition almost entirely and use *purely topological* methods. The first main result of the paper is:

**Theorem 1.1.**

(1) Every countably-based $T_0$-space has a computable topological presentation.

(2) Conversely, every (formal) computable topological presentation is a presentation of a zero-dimensional Polish space.

While this result says that computable topological presentations are essentially “useless”, we will see that more can be said in the particularly important case of compact Polish spaces.

**1.2. Classifying presentations of compact Polish spaces.** We will see that given a computable topological presentation of a Polish space, one can detect (using a number of quantifiers) the basic open sets containing exactly one point. Therefore, one can detect the number of isolated points and whether or not the isolated points are dense. Our second result implies in particular that these properties are the only ones that can be detected from a presentation, and that all the spaces that behave the same w.r.t. these properties actually share a computable topological presentation.

**Theorem 1.2.** There is a uniformly computable sequence of computable topological presentations $(T_i)_{i \in \omega}$, so that every compact Polish space is represented by exactly one $T_i$ from this sequence.

The uniform sequence is given by parameters describing the cases (1)-(4):

(1) The space is finite.

(2) The space has a perfect kernel and has exactly $m \ge 0$ isolated points, $m \in \omega$.

(3) Compact Polish spaces with infinitely many isolated points, in which isolated points are dense.
(4) Compact Polish spaces having infinitely many isolated points, but so that the isolated points are not dense.

For example, in (2) with $m = 0$, the presentation can be taken to be the standard computable topological presentation of $2^\omega$, given by an effective numbering of its non-empty clopen sets.

**1.3. Effective compactness.** All results so far confirm our intuition that computable topological presentations are too weak to be of much use, at least without any extra assumptions. In the present paper we will look at one such extra condition which appears to be among the most popular (and widely used) in the modern literature.

We say that a compact computable topological space is effectively compact if we can effectively list all tuples of basic open sets covering the space. A Polish space is computably compact if it has a computable Polish presentation (Def. 1.2) and is effectively compact. Computably compact presentations are very common in the modern literature; we cite the two recent surveys [IK21, DM23]. In particular, the notion of a computably compact Polish space is exceptionally robust, as it admits many equivalent formulations; for example, a compact computable Polish space is computably compact iff the continuous diagram of the space is decidable [DM23]. Our third result gives a somewhat unexpected, further characterisation of computably compact Polish spaces in terms of computable topological presentations. It is as follows.

**Theorem 1.3.** For a compact Polish space $X$, the following are equivalent:

(1) $X$ has an effectively compact $\cap$-decidable (Def. 4.2) topological presentation.

(2) $X$ admits a computably compact Polish presentation.

Thus by relativization, every effectively compact topological space admits a $\Delta_2^0$-Polish presentation. This is also sharp (i.e., $\Delta_2^0$ cannot be improved to "computable" in general).

(To obtain the notion of a $\cap$-decidable presentation, we require that the non-emptiness of the intersection of basic sets in Definition 1.1 is decidable rather than merely c.e.) It follows from Theorem 1.3 that, in the context of compact spaces, effective compactness “fixes” the issues with the general computable topological presentation. In particular, effectively compact topological presentations completely determine the topological structure on the represented space, as one can effectively metrize the space (as we will show in due course).

We finish the introduction with an open question.

**Question 1.** Is it true that the following are equivalent?

(1) The space admits an effectively compact topological presentation.

(2) The space admits an effectively compact right-c.e. Polish presentation.

The implication (2) $\rightarrow$ (1) is of course obvious, and we will show in Proposition 4.1 that (1) $\rightarrow$ (2) holds for Stone spaces.

Our main theorem, Theorem 1.1, provides a computable topological presentation for every countably-based $T_0$-space. On the surface this might seem to be a near impossible task given the richness and the variety of topological types. We do this by exploiting the fact that very different spaces can appear (via emedding
into a universal space) as being very similar to each other. An important step
in our analysis is the following fact which was already mentioned earlier in the
introduction:

If $X$ is a dense subset of $Y$ then any computable topological presentation of $Y$
is also a computable topological presentation of $X$.

Using the afore-mentioned fact, the main steps in our proof of Theorem 1.1
proceed as follows:

(1) We first obtain a computable topological presentation for every compact Polish space. Compact spaces are somewhat more tractable than the general case.

(2) Since every separable metrizable space $X$ embeds as a dense subset of a compact Polish space $Y$, (1) will provide a computable topological presentation for $X$.

(3) To extend (2) to all countably-based $T_0$-spaces, we note that every such space can be embedded into $\mathcal{P}(\omega)$ with the Scott topology. Therefore it is sufficient to provide a computable topological presentation of every closed subspace of $\mathcal{P}(\omega)$.

(4) Each closed subset $X$ of $\mathcal{P}(\omega)$ will itself have a zero-dimensional dense subset $M \subseteq X$. Each zero-dimensional subset is metrizable and therefore (2) provides a computable topological presentation for $M$.

(5) Since $M$ is a subset of $X$, it is not immediate that (4) gives a computable topological presentation for $X$. However we shall show that (4) can be extended to a computable topological presentation for $X$.

For technical reasons, we shall first prove Theorem 1.2, then we will apply the techniques developed in the proof of Theorem 1.2 to establish Theorem 1.1, and only after that we will demonstrate Theorem 1.3. We also chose to present notions and technical facts when needed, instead of creating a preliminaries section.

## 2. COMPACT SPACES: PROOF OF THEOREM 1.2

It this section we prove Theorem 1.2 that every compact Polish space admits a
computable topological presentation.

In order to prove Theorem 1.2, we will classify all compact Polish spaces under
the following congruence:

(†) $X \sim Y \iff X$ and $Y$ share a computable topological presentation.

We will see that these classes are completely described by the four cases listed
after the statement of Theorem 1.2. The techniques accumulated in the proof of
Theorem 1.2 will be used throughout the rest of the paper, in particular, to prove
Theorem 1.1 covering non-compact spaces.

2.1. **Detecting the behaviour of isolated points.** We use $\sim$ as defined by (†).

**Lemma 2.1.** *Suppose $X \sim Y$. If $X$ has at least $n$ isolated points, then so does $Y$,*

*Proof.* Suppose $X \sim Y$ is witnessed by a computable topological presentation $P$. We can express that a basic open $D \in P$ isolates a point by saying that there are no $B_0, B_1$ such that $B_i \cap D \neq \emptyset$, $i = 0, 1$, and $B_0 \cap B_1 = \emptyset$. Further, we can say that $P$ has at least $n$ isolated points if there are disjoint basic open $D_0, D_1, \dots, D_{n-1}$ each isolating a point. $\square$
In particular, it follows that the number of isolated points in X is ~-invariant.

**Lemma 2.2.** Suppose $X \sim Y$. If the isolated points in X are dense, then the same is true in Y.

*Proof.* If the isolated points are dense, then for every basic B there exists a D isolating a point (see the proof of Lemma 2.1) so that $B \cap D \neq \emptyset$. □

Note that the lemmas above really say that the number of isolated points and their density in the space are definable properties (in the language where terms are built using only $\cap$, and where we only allow comparison between a term and $\emptyset$). We conclude that the following are ~-invariant properties of compact Polish spaces:

(1) Case 1: The space is finite of size $n > 0$. (There are $n$ isolated points and isolated points are dense.)

(2) Case 2: The space has a perfect kernel and has exactly $m \ge 0$ isolated points. (There are $m$ isolated points and they are not dense.)

(3) Case 3: The space has infinitely many isolated points which are dense in the space.

(4) Case 4: The space has infinitely many isolated points which are not dense in the space.

Note these cases cover all possible compact Polish spaces. Our next task is to show that in each case, all spaces share the exact same fixed computable presentation, and thus are all pairwise ~-equivalent. We will see that, furthermore, given the parameters describing each case, we can uniformly produce the computable topological presentation shared between all compact spaces that satisfy the conditions of this case. This will give Theorem 1.2.

**2.2. Quotient maps and almost injective functions.** Before we go over the cases (1)-(4), we need to accumulate enough technical facts that will allow us to handle ~-equivalent spaces.

It is well-known that any continuous surjective function from a compact space X to a Hausdorff space Y is a quotient map, in the sense that for all $U \subseteq Y$, $f^{-1}(U)$ is open iff U is open. Moreover, the next result shows that any basis of X canonically induces a basis of Y, assuming it is closed under finite unions.

**Proposition 2.1.** Let X be compact and Y be Hausdorff and $(B_i)_{i \in I}$ be a basis of the topology of X which is closed under finite unions. Let $f: X \to Y$ be surjective continuous and define

$$C_i = Y \setminus f(X \setminus B_i) = \{y \in Y : f^{-1}(y) \subseteq B_i\}.$$

The family $(C_i)_{i \in I}$ is a basis of the topology of Y. If $(B_i)_{i \in I}$ is moreover closed under finite intersections, then $B_i \cap B_j = B_k$ implies $C_i \cap C_j = C_k$.

*Proof.* First, each $C_i$ is open: $X \setminus B_i$ is compact so $f(X \setminus B_i)$ is compact hence closed.

Let $U \subseteq Y$ be open and $y \in U$. One has $f^{-1}(y) \subseteq f^{-1}(U)$. As $f^{-1}(y)$ is compact and $(B_i)_{i \in I}$ is closed under finite unions, there exists $i$ such $f^{-1}(y) \subseteq B_i \subseteq f^{-1}(U)$. Therefore, $y \in C_i \subseteq f(B_i) \subseteq U$. Therefore, $(C_i)_{i \in I}$ is a basis.

If $B_i \cap B_j = B_k$, then $C_i \cap C_j = Y \setminus f(X \setminus (B_i \cap B_j)) = Y \setminus f(X \setminus B_k)) = C_k$. □
Note that if $C_i \neq \emptyset$ then $B_i \neq \emptyset$ but the converse implication fails in general. However, we will see that when the function is "almost injective" (to be defined), we obtain an equivalence.

For a function $f: X \to Y$, we define

$$D_f = \{x \in X : f^{-1}(f(x)) = \{x\}\},$$

which is the set of points at which $f$ is injective.

**Definition 2.1.** A function $f: X \to Y$ is **almost injective** if the set

$$D_f = \{x \in X : f^{-1}(f(x)) = \{x\}\}$$

is dense.

**Proposition 2.2.** If $f: X \to Y$ is almost injective, then for each $i \in I$, $B_i \neq \emptyset$ iff $C_i \neq \emptyset$.

*Proof.* If $B_i$ is non-empty then it contains a point $x$ such that $f^{-1}(f(x)) = \{x\}$. As a result, $C_i$ contains $f(x)$ and is therefore non-empty. □

These simple results enable one to easily transfer a presentation from a space to another, as follows.

**Corollary 2.1.** Let $X$ be compact and $(B_i)_{i \in \mathbb{N}}$ be a basis of $X$ which is closed under finite unions and intersections. If $Y$ is Hausdorff and $f: X \to Y$ is continuous, surjective and almost injective, then the presentation of $X$ induces a presentation of $Y$.

Our next task will be to build almost injective functions from known spaces to arbitrary compact Polish spaces. Before that, we need to investigate further properties of almost injective functions.

First, almost injectiveness is preserved by composition.

**Proposition 2.3.** If $f: X \to Y$ is almost injective and $A \subseteq Y$ is dense, then $f^{-1}(A)$ is dense.

*Assume that $X, Y$ are compact Polish. If $f: X \to Y$ and $g: Y \to Z$ are almost injective, then so is $g \circ f: X \to Z$.*

*Proof.* Let $B_i$ be non-empty. $C_i$ is a non-empty open subset of $Y$ (Proposition 2.2) so it intersects $A$. Let $y \in C_i \cap A$. One has $f^{-1}(y) \subseteq B_i \cap f^{-1}(A)$, so $f^{-1}(A)$ intersects $B_i$.

We show that if $X$ is compact Polish, $Y$ is Hausdorff and $f: X \to Y$ is continuous, then $\{x \in X : f^{-1}(f(x)) = x\}$ is a $G_\delta$-set. Let $(B_i)_{i \in \mathbb{N}}$ be a countable basis of $X$ and $E = \{(i, j) : \text{cl}(B_i) \cap \text{cl}(B_j) = \emptyset\}$. Let $A = \bigcup_{(i,j) \in E} f(\text{cl}(B_i)) \cap f(\text{cl}(B_j))$. It is an $F_\sigma$-subset of $Y$. One has $D_f = X \setminus f^{-1}(A)$. Indeed, $x \notin D_f \iff f^{-1}(f(x))$ contains at least two points $\iff \exists(i, j) \in E, f(x) \in f(\text{cl}(B_i)) \cap f(\text{cl}(B_j))$.

As $g$ is almost injective, the set $D_g := \{y \in Y : g^{-1}(g(y))\}$ is dense. As $f$ is almost injective, $f^{-1}(D_g)$ is dense by the first assertion. Therefore, $f^{-1}(D_g)$ and $D_f$ are dense $G_\delta$-sets, so their intersection is dense by the Baire category theorem. If $x$ belongs to the intersection, then

$$ \begin{align*} (g \circ f)^{-1}(g \circ f(x)) &= f^{-1}(g^{-1}(g(f(x)))) \\ &= f^{-1}(f(x)) \qquad \text{as } f(x) \in D_g \\ &= \{x\} \qquad \text{as } x \in D_f. \end{align*} $$

Therefore, $g \circ f$ is almost injective. □
Next, isolated points are preserved by almost injective functions.

**Proposition 2.4.** If $f: X \to Y$ is almost injective, surjective continuous, then it bijectively maps the isolated points of $X$ to the isolated points of $Y$.

*Proof.* If $x \in X$ is isolated, then $\{x\}$ is open so it intersects $D_f$, therefore $x \in D_f$ and $f^{-1}(f(x)) = \{x\}$. As a result, $\{f(x)\} = Y \setminus f(X \setminus \{x\})$ is an open set, so $f(x)$ is isolated.

Conversely, if $f(x)$ is isolated then $f^{-1}(f(x))$ is a non-empty open set so it intersects $D_f$. Let $y$ belong to the intersection: one has $f(y) = f(x)$ and $\{y\} = f^{-1}(f(y))$ so $x = y$ and $\{x\} = f^{-1}(f(x))$ is open, i.e. $x$ is isolated. $\square$

We now show that the general case of compact Polish spaces can be reduced to the case of zero-dimensional ones. The basic intuition is quite straightforward; the compactness of a space $X$ allows us to cover each closed subset of $X$ with finitely many open sets. The closure of each of these “cells” can in turn be covered by finitely many other open sets. This process allows us to simulate the construction of a compact zero-dimensional space. Since the space itself does not have to be zero-dimensional, this association is not exact. However, if we are careful enough, we will be able to produce an almost injective map. To be precise, we prove:

**Lemma 2.3.** Let $X$ be a compact Polish space. There exists a zero-dimensional compact space $X_0$ and a continuous surjective function $f: X_0 \to X$ which is almost injective.

*Proof.* We first build, for each $n$, an almost partition of $X$: a finite disjoint family of non-empty open sets $U_0^n, \dots, U_{k_n}^n$ of diameters $< 2^{-n}$, whose closures cover $X$.

By compactness, there exists a finite covering $(B_i^n)_{i \le k_n}$ of $X$ by open sets of diameters $< 2^{-n}$. Let $U_i^n = B_i^n \setminus \text{cl}(B_0^n \cup \dots \cup B_{i-1}^n)$. By definition, for each $n$ the open sets $U_i^n$ are pairwise disjoint. Note that

$$ (1) \quad \text{cl}(B_i^n) \setminus \text{cl}(B_0^n \cup \dots \cup B_{i-1}^n) \subseteq \text{cl}(U_i^n) \subseteq \text{cl}(B_i^n) \setminus (B_0^n \cup \dots \cup B_{i-1}^n). $$

The closures $\text{cl}(U_i^n)$ cover $X$: for $x \in X$, let $i$ be minimal such that $x \in \text{cl}(B_i^n)$. One has $x \in \text{cl}(U_i^n)$ by the first inclusion in (1). We finally remove the $U_i^n$'s that are empty.

Each $U_i^n$ is called an open cell, its closure is called a closed cell. Say that a point $x \in X$ is generic if it belongs to an open cell at each level, i.e. if $x \in \bigcap_n \cup_i U_i^n$. The set of generic points is dense.

Consider the finitely-branching tree $T$ of finite sequences $(i_n)_{n<N}$, where $N \in \mathbb{N}$ and $i_n \le k_n$, such that the corresponding intersection of open cells $\bigcap_{n<N} U_i^n$ is non-empty. It is a pruned tree, because if $\bigcap_{n<N} U_i^n$ is not empty then it intersects some $U_i^n$, so the sequence $(i_n)_{n<N}$ has an extension in $T$. Let $X_0 = [T]$ be the set of infinite paths in $T$ and $f: [T] \to X$ send an infinite path to the unique point of $X$ that belongs to the intersection of the closed cells $\text{cl}(U_i^n)$. It is continuous, because the diameters of the cells converge to 0.

The function $f$ is surjective. Each generic point $x$ belongs to the image of $f$, because its unique path $p$ belongs to $T$ (every finite intersection of open cells along $p$ is a neighborhood of $x$, so it is non-empty), and $f(p) = x$. The image of $f$ is a compact set containing the dense set of generic points, so it is the whole space $X$.

Finally, $f$ is almost injective. A finite path of $T$ defines a non-empty open subset of $X$; take a generic point there, its unique path extends the given finite path. $\square$
We now have all the ingredients to prove Theorem 1.2.

## 2.3. Compact perfect Polish spaces.

**Theorem 2.1.** All the compact perfect Polish spaces share a computable presentation.

*Proof.* Let $X$ be a compact perfect Polish space. We show that there exists a continuous surjective function $f : 2^\omega \to X$ which is almost injective. By Lemma 2.3, there exists a zero-dimensional compact Polish space $X_0$ and a surjective almost injective continuous function $f : X_0 \to X$. As $X$ is perfect, so is $X_0$ by Proposition 2.4. Therefore, $X_0$ is a perfect compact zero-dimensional space, so it is homeomorphic to the Cantor space. Let $(B_i)_{i \in \mathbb{N}}$ be the computable presentation of the Cantor space, which is an effective enumeration of its non-empty clopen subsets. It is closed under finite unions and intersections, so it induces a formally identical computable presentation $(C_i)_{i \in \mathbb{N}}$ of $X$ by Corollary 2.1. □

## 2.4. Compact with finitely many isolated points.
All finite Polish spaces $F_n$ (where $|F_n| = n$) are clearly computable topological. All the infinite compact Polish spaces with $n$ isolated points share a computable presentation, $F_n \sqcup 2^\omega$, by applying Theorem 2.1.

## 2.5. Infinitely many isolated points that are dense.
We show that all the compact Polish spaces having infinitely many isolated points, and such that the isolated points are dense, share a computable presentation.

For that, consider the space $Z = 2^{<\omega}$, which is the Cantor space with a dense set of isolated points. (Each finite string is isolated, and for each finite string $u$, the set of all finite or infinite sequences extending $u$ is open.) Since $Z$ satisfies the premises of Corollary 2.1, in this case it is sufficient to prove:

**Lemma 2.4.** If $X$ is compact Polish with infinitely many isolated points which are dense in $X$, then there is a surjective almost injective continuous function $f : 2^{<\omega} \to X$.

*Proof.*

*Claim 1.* We can assume w.l.o.g. that $X$ is zero-dimensional.

*Proof.* Let $X_0$ be zero-dimensional compact and $f : X_0 \to X$ be given by Lemma 2.3. As $X$ has infinitely many isolated points, so does $X_0$ (Proposition 2.4). As the set of isolated points is dense in $X$, so is its pre-image (Proposition 2.3), which is the set of isolated points of $X_0$. It is sufficient to show the existence of a surjective almost injective continuous function $g : 2^{<\omega} \to X_0$, because the composition $f \circ g : 2^{<\omega} \to X$ is then surjective, almost injective continuous (Proposition 2.3). □

We assume that $X$ is zero-dimensional. Let $T$ be a pruned finitely-branching tree such that $[T] \cong X$. Let $f : 2^\omega \to [T]'$ be surjective continuous, where $[T]'$ is the Cantor-Bendixon derivative of $[T]$, i.e. the set of non-isolated points of $[T]$. We define a bijection $g : 2^{<\omega} \to [T] \setminus [T]'$ and will let $h : 2^{<\omega} \to [T]$ be the sought function, obtained by combining $f$ and $g$. Of course we need to make sure that $h$ is continuous.

As $[T]$ is zero-dimensional and $[T]'$ is closed, there is a continuous retraction $r : [T] \to [T]'$ [Kec95, Theorem 7.3]. We will exploit the following property: for
every $\sigma \in T$, the set $r^{-1}([\sigma]) \setminus [\sigma]$ is finite because it is compact and only contains isolated points ($[\sigma]$ is the set of infinite extensions of $\sigma$).

Let $(u_i)_{i \in \mathbb{N}}$ be a one-to-one enumeration of $2^{<\omega}$ and $(x_i)_{i \in \mathbb{N}}$ a one-to-one enumeration of the isolated points of $[T]$. Let $F: 2^{<\omega} \to T$ be monotone w.r.t. the prefix ordering and converge to $f$: if $u \le v$ then $F(u) \le F(v)$ and for $p \in 2^{\omega}$, the length of $F(p|n)$ goes to infinity as $n$ grows, and therefore $F(p|n)$ converge to $f(p)$ (we can define $F(u)$ as the longest common prefix of elements of $f([u])$).

For $i \in \mathbb{N}$, we inductively define $g(u_i)$ as the isolated point $x \in [T]$ with minimal index that does not belong to $\{g(u_0), \dots, g(u_{i-1})\}$ and such that $r(x)$ extends $F(u_i)$.

First, $g$ is well-defined: $r^{-1}([F(u)])$ is an open set intersecting $[T]'$ because it contains the non-empty set $[F(u)] \cap [T]'$, so $r^{-1}([F(u)])$ contains infinitely many isolated points, so one can always pick a "fresh" isolated point of $[T]$ in that set.

Second, $g$ is injective by construction.

Finally, $g$ is surjective because each isolated point has infinitely many chances to be chosen. Let $x$ be isolated. As $f: 2^{\omega} \to [T]'$ is surjective, there exists $p \in 2^{\omega}$ such that $f(p) = r(x)$, so for every prefix $u$ of $p$, $r(x)$ extends $F(u)$. Therefore, there exists $i$ such that $u_i$ is a prefix of $p$ and $g(u_i) = x$.

Let $h: 2^{\le \omega} \to [T]$ be obtained by joining $f$ and $g$. $h$ is surjective, almost injective (indeed, $2^{<\omega}$ is dense), we show that it is continuous. We only need to show that it is continuous at each point of $2^{\omega}$, because all the other points are isolated.

Let $f(p) = q$ and let $\sigma$ be a prefix of $q$. Let $u_0$ be a prefix of $p$ such that $F(u_0)$ extends $\sigma$. There are only finitely many $u$'s such that $g(u) \in r^{-1}([\sigma]) \setminus [\sigma]$, so there exists a prefix $u_1$ of $p$, longer than $u_0$, such that for every finite extension $u$ of $u_1$, $g(u) \notin r^{-1}([\sigma]) \setminus [\sigma]$. Let then $u$ be a string extending $u_1$ and let $x = g(u)$. As $r(x)$ extends $F(u)$ which extends $\sigma$, one has $x \in r^{-1}([\sigma])$ so $x \in [\sigma]$. We have proved that $h$ is continuous at $p$. $\square$

**2.6. Infinitely many isolated points that are not dense.** Let $X$ contain infinitely many isolated points, which are not dense. We build a surjective almost injective continuous function $f: 2^{\omega} \sqcup 2^{<\omega} \to X$.

We decompose $X$ as $K \cup U$, where $K$ is the perfect kernel and $U$ is countable and open. Note that $\text{cl}(U)$ has infinitely many isolated points, which are dense in $\text{cl}(U)$.

By the previous results, there exist surjective almost injective continuous functions $f: 2^{\omega} \to K$ and $g: 2^{\le \omega} \to \text{cl}(U)$. Their combination $h: 2^{\omega} \sqcup 2^{\le \omega} \to X$ is surjective continuous. We show that it is almost injective.

If $x \in 2^{\omega}$ and $x' \in 2^{\le \omega}$ and $f(x) = g(x') = y$ then $y \in \partial U$. The closed set $\partial U$ has empty interior, so its preimage under $f$ and $g$ also has empty interior, because $f$ and $g$ are almost injective (so the preimage of the complement of $\partial U$ is dense by Proposition 2.3). Therefore, $D_h$ contains $(D_f \setminus f^{-1}(\partial U)) \sqcup (D_g \setminus g^{-1}(\partial U))$ which is dense.

To finish the proof of Theorem 1.2, we just note that the finite spaces $F_n$ ($n \in \omega$, $n > 0$), the spaces $2^{\omega} \sqcup F_n n$, $2^{\le \omega}$, and $2^{\omega} \sqcup 2^{\le \omega}$ make up the complete list which mentions every $\sim$-class of compact Polish spaces exactly once.

*Remark 2.1.* The computable presentations build in the proof of Theorem 1.2 have additional property that the set $\{(i_1, \dots, i_n) : B_{i_1} \cap \dots \cap B_{i_n} \ne \emptyset\}$ is computable rather than merely c.e.
### 3. GENERAL SPACES. PROOF OF THEOREM 1.1

Theorem 1.2 implies in particular that every compact Polish space has a computable presentation. But this readily gives the following:

**Corollary 3.1.** Every separable metrizable space has a computable topological presentation.

*Proof.* Every separable metrizable space $X$ embeds as a dense subset of a compact Polish space $Y$ (embed the space in the Hilbert cube and take its closure). As $X$ is dense in $Y$, they share the same computable topological presentation. □

Moreover, the same classification as in Theorem 1.2, expressed in terms of number and density of isolated points, also holds for separable metrizable spaces, because these properties are preserved under compactification.

Theorem 1.1(1) states that, more generally, every countably based $T_0$-space admits a computable topological presentation. For the purpose of proving this more general fact, let us summarise what we have, adding an ingredient that will be useful in the next section.

**Proposition 3.1.** Let $X$ be a countably-based and metrizable and $\mathcal{F}$ be a countable family of clopen subsets of $X$. There exists a basis $(B_i)_{i \in \mathbb{N}}$ of $X$ that contains $C$ and such that $\{(i_1, \dots, i_n) : B_{i_1} \cap \dots \cap B_{i_n} \neq \emptyset\}$ is computable.

*Proof.* When we embed $X$ in the Hilbert cube $Q$ and take its closure $cl(X)$, a clopen subset of $X$ need not be the intersection of a clopen subset of $cl(X)$ with $X$. However, if we choose in advance a countable family of clopen subsets of $X$, we can choose an embedding which “respects” these clopen sets.

Let $X_0 \subseteq Q$ be homeomorphic to $X$. Let $\mathcal{F} = (F_j)_{j \in \mathbb{N}}$ be a countable family of clopen subsets of $X_0$. For each $F_j \in \mathcal{F}$, the characteristic function $f_j : X_0 \to \{0, 1\}$ of $F_j$ is continuous. Let $f : X_0 \to Q$ map $x$ to the sequence $(f_j(x))_{j \in \mathbb{N}}$. Let then $X_1 = \{(x, f(x)) : x \in X_0\} \subseteq Q \times Q \cong Q$. $X_1$ is homeomorphic to $X$. For each $j$, $cl(X_1) \cap \{(x, y) : y_j = 1\} = cl(X_1) \cap \{(x, y) : y_j > 0\}$ is a clopen set corresponding to $F_j$.

Applying the previous results, we obtain a surjective continuous almost injective function $f : Z \to cl(X_1)$ for some compact zero-dimensional $Z$ whose clopen sets form a computable basis $(B_i)_{i \in \mathbb{N}}$. We then define the basis of $cl(X_1)$, $C_i = cl(X_1) \setminus f(Z \setminus B_i)$. Note that this subbasis contains every clopen set $F \subseteq cl(X_1)$. Indeed, $f^{-1}(F)$ is clopen so it is some $B_i$, therefore $F = C_i$. We finally define a basis of $X_1$, $D_i = C_i \cap X_1$. Every $F_j \in \mathcal{F}$ is the intersection of a clopen set $F \subseteq cl(X_1)$ with $X_1$, $F$ is some $C_i$, so $F_j = F \cap X_1 = C_i \cap X_1 = D_i$. □

### 3.1. Every countably-based $T_0$-space has a computable presentation.
We prove Theorem 1.1(1) (stated in the title of this subsection).

The countably-based $T_0$-spaces are exactly the subspaces of $\mathcal{P}(\omega)$ with the Scott topology. It is sufficient to prove the result for closed subspaces of $\mathcal{P}(\omega)$, because a presentation of the closure of $X \subseteq \mathcal{P}(\omega)$ induces a presentation of $X$.

A basis of the Scott topology on $\mathcal{P}(\omega)$ is given by the sets $[F] = \{A \in \mathcal{P}(\omega) : F \subseteq A\}$ where $F \subseteq \mathbb{N}$ is finite.

Let $X$ be a non-empty closed subset of $\mathcal{P}(\omega)$ and $M = \max X$ be the set of elements of $X$ that are maximal w.r.t. inclusion.
First, $M$ is zero-dimensional because each $[F] \cap M$ is clopen in $M$: if $A \in M \setminus [F]$ then as $A$ is maximal in $X$, $A \cup F \notin X$ which is closed, so there exists a finite set $G$ such that $[G]$ contains $A \cup F$ and is disjoint from $X$. As a result, $[G \setminus F] \cap M$ is a neighborhood of $A$ which is disjoint from $[F] \cap M$.

As $M$ is countably-based and zero-dimensional, it is metrizable. We apply Proposition 3.1 to $M$ and the countable family of clopen sets $[F] \cap M$, so $M$ has a computable basis $(B_i)_{i \in \mathbb{N}}$ which contains each $[F] \cap M$.

As each $B_i$ is an open subset of $M$, it extends to an open subset of $X$: there exists an open set $V_i \subseteq X$ such that $V_i \cap M = B_i$. However, the $V_i$'s will not in general be rich enough to form a basis of $X$, because there are many ways to extend $B_i$ to an open set of $X$, and we only chose one. The idea is to allow more choices: for each $i$, we define a family of open sets $(U_i^n)_{n \in \mathbb{N}}$ such that $U_i^n \cap M = B_i$. As $M$ is dense in $X$, a finite intersections of $U_i^n$'s is non-empty iff the corresponding finite intersection of $B_i$'s is non-empty, which is computable. In order to make $(U_i^n)_{n,i \in \mathbb{N}}$ a basis of $X$, we use the fact that $([F_n] \cap X)_{n \in \mathbb{N}}$ is a basis of $X$, where $(F_n)_{n \in \mathbb{N}}$ is an enumeration of the finite subsets of $\mathbb{N}$, and we let $U_i^n = [F_n] \cap X$ for some $i$ such that $[F_n] \cap M = B_i$.

More precisely, let

$$ U_i^n = \begin{cases} [F_n] \cap X & \text{if } [F_n] \cap M = B_i, \\ V_i & \text{otherwise.} \end{cases} $$

By definition, we always have $U_i^n \cap M = B_i$. The family $(U_i^n)_{n,i \in \mathbb{N}}$ is a basis because it contains each $[F] \cap X$. Indeed, for each $n$, one has $[F_n] \cap M = B_i$ for some $i$, so $U_i^n = [F_n] \cap X$.

As $M$ is dense in $X$, a finite intersection of $U_i^n$'s is non-empty iff it intersects $M$ iff the corresponding intersection of $B_i$'s is non-empty, so it is a computable relation.

**Remark 3.1.** For a metrizable space $X$, there are two proofs. There is a common part: Every countably-based zero-dimensional space $Z$ has a computable basis, proved by building a surjective almost injective map $f: Z_0 \to Z$, where $Z_0$ is $2^\omega$ or $2^{\leq \omega}$ or $2^\omega \sqcup 2^{\leq \omega}$ (plus the cases with finitely many isolated points). Then the proofs diverge:

* Embed $X$ in $[0, 1]^\omega$, build an almost injective function $g: Z \to \text{cl}(X)$ for some zero-dimensional compact $Z$, then transfer the computable subbasis of $Z$ to $\text{cl}(X)$ using $g$, and then to $X$.

* Embed $X$ in $\mathcal{P}(\omega)$, consider the zero-dimensional space $Z = \max(\text{cl}(X))$, then transfer the computable subbasis of $Z$ to a $\text{cl}(X)$, and then to $X$.

The second proof applies to any space, so it might seem stronger. However, the first proof gives extra information that might be interesting (existence of almost injective function, the basis is formally the same as one of the Cantor-like spaces).

## 3.2. Every computable topological presentation presents a Polish space.
We now prove statement (2) in Theorem 1.1. It is easier to work with a slightly different but equivalent formulation of topological presentations. For a countably-based space $X$, we will call topological presentations of the first and second kind respectively, the two following data:

(1) A basis $(B_i)_{i \in \mathbb{N}}$ consisting of non-empty sets and an enumeration of a set $E \subseteq \mathbb{N}^3$ such that $B_i \cap B_j = \bigcup_{(i,j,k) \in E} B_k,$
(2) A subbasis $(B_i)_{i \in \mathbb{N}}$ and an enumeration of the (indices of) finite sets $F \subseteq \mathbb{N}$ such that $B_F := \bigcap_{i \in F} B_i \neq \emptyset$.

Note that the effective version of the first one is Definition 1.1.

**Claim 2.** These notions of presentations are equivalent in the sense that there is a computable translation between them.

*Proof.* Given a basis $(B_i)_{i \in \mathbb{N}}$ of the first kind with a set $E$, take $(B_i)_{i \in \mathbb{N}}$ as a subbasis; one can test whether $B_F$ is non-empty by expressing it as $\bigcup_{k \in G} B_k$ for some $G$ that can be enumerated using $E$, and so $B_F \neq \emptyset$ iff $G \neq \emptyset$.

Conversely, given a subbasis $(B_i)_{i \in \mathbb{N}}$ of the second kind, with an enumeration $(F_i)_{i \in \mathbb{N}}$ of the finite sets inducing non-empty open sets $B_{F_i}$, let $B'_i = B_{F_i}$ and $E = \{(i, j, k) : F_i \cup F_j = F_k\}$. $\square$

In a presentation of the second kind, note that if $F \subseteq G$ and $B_G \neq \emptyset$, then $B_F \neq \emptyset$, i.e. the set $\{F : B_F \neq \emptyset\}$ is downward closed. It is the only restriction to be a valid presentation. In other words, given any non-empty downward closed collection $S$ of finite sets, there exists a space $X$ with a subbasis $(B_i)_{i \in \mathbb{N}}$ such that $F \in S \iff \bigcap_{i \in F} B_i \neq \emptyset$. Indeed, let $\mathcal{P}(\mathbb{N})$ be the powerset of $\mathbb{N}$ with the Scott topology and

$$X = \{A \in \mathcal{P}(\mathbb{N}) : \forall F, F \subseteq A \implies F \in S\}$$

and let $B_i = \{A \in A : i \in A\}$.

We now improve this observation, by making the space zero-dimensional Polish.

**Proposition 3.2.** Every topological presentation of the second kind is a presentation of a zero-dimensional Polish space.

*Proof.* Let $X$ be a topological space with a subbasis $(B_i)_{i \in \mathbb{N}}$ and an enumeration of $\{F : B_F \neq \emptyset\}$, where $B_F = \bigcap_{i \in F} B_i$.

Let $Y \subseteq 2^\omega$ be defined as follows. Let

$$\mathcal{P} = \{A \in 2^\omega : \forall F, F \subseteq A \implies B_F \neq \emptyset\}.$$

Let $Y$ be the set of maximal elements of $\mathcal{P}$ w.r.t. inclusion. Let $C_i = \{A \in Y : i \in A\}$ and $C_F = \bigcap_{i \in F} C_i$.

First, $\mathcal{C} = (C_i)_{i \in \mathbb{N}}$ is a subbasis of the Cantor topology on $Y$. We only need to check that each set $N_j := \{A \in Y : j \notin A\}$ is open in the topology generated by $\mathcal{C}$. Let $A \in Y$ and $j \notin A$. As $A$ is maximal in $\mathcal{P}$, $A \cup \{j\} \notin \mathcal{P}$ so there exists $F \subseteq A \cup \{i\}$ such that $B_F = \emptyset$. Note that $F$ must contain $j$ because $A \in \mathcal{P}$. As $B_F = \emptyset$, every $A' \in \mathcal{P}$ containing $F \setminus \{j\}$ does not contain $j$, so $A \in \bigcap_{i \in F \setminus \{j\}} C_i \subseteq N_j$.

Next, we show that $C_F \neq \emptyset$ $\iff$ $B_F \neq \emptyset$. If $C_F \neq \emptyset$, then let $A \in C_F$. As $F \subseteq A$ and $A \in \mathcal{P}$, $B_F \neq \emptyset$. Conversely, if $B_F \neq \emptyset$ then let $x \in B_F$ and let $A = \{i \in \mathbb{N} : x \in B_i\}$. Note that $A \in \mathcal{P}$. A may not be maximal in $\mathcal{P}$, but it is contained in a maximal element $A'$ of $\mathcal{P}$ (iteratively add to A the smallest number which is not already in and results in an element of $\mathcal{P}$). Therefore, $A' \in C_F$ which is non-empty.

As a result, the presentations $(B_i)_{i \in \mathbb{N}}$ and $(C_i)_{i \in \mathbb{N}}$ are identical.

The space $Y$ is a subspace of the Cantor space, we need to show that it is Polish, i.e. $G_\delta$. Note that

$$A \in Y \iff \begin{cases} \forall F, F \subseteq A \implies B_F \neq \emptyset \text{ and} \\ \forall n, n \notin A \implies \exists F \subseteq A, B_F \cup \{n\} = \emptyset. \end{cases}$$
All this is a $\Pi_2^0$ formula (relative to the set $\{F : B_F \neq \emptyset\}$). $\square$

**Remark 3.2.** Another way to express what we are doing is: we canonically embed $X$ in $\mathcal{P}(\mathbb{N})$, the powerset of the natural numbers with the Scott topology, via $x \in X \mapsto \{i \in \mathbb{N} : x \in B_i\}$, take the closure $\mathcal{P}$ of $X$ in $\mathcal{P}(\mathbb{N})$, and consider the set $Y$ of maximal elements of $\mathcal{P}$. We show that the Scott topology coincides with the Cantor topology on $Y$.

The proof also gives an effective version.

**Corollary 3.2.** Every presentation of the second kind where the set $\{F : B_F \neq \emptyset\}$ is computable is a presentation of a zero-dimensional computable Polish space.

**Proof.** We say that a subset $S$ of computable topological space $(X, \tau, (B_i)_{i \in \mathbb{N}})$ is effectively overt if the set $\{i \in \mathbb{N} : B_i \cap S \neq \emptyset\}$ is c.e.. We say that a subset $S$ is effectively $G_\delta$ in $M$, or simply $\Pi_2^0$, if there is a uniformly c.e. sequence of open sets $U_i$ such that $S = \bigcap_i U_i$. The following effective version of Alexandrov's Theorem was proved in [Hoy17, Proposition 2.3.3].

**Lemma 3.1.** An effectively overt $\Pi_2^0$ subset of a computable Polish $M$ is itself computable Polish.

It remains to observe that the space $Y$ from the proof of Proposition 3.2 is computably overt and is a $\Pi_2^0$-subset of the Cantor space. $\square$

We are now ready to prove Theorem 1.1(2) which states that every topological presentation (of the first kind) is a presentation of a zero-dimensional Polish space.

**Proof of Theorem 1.1(2).** Start from a presentation $(B_i)$ and $E$, transform into the second kind, apply Proposition 3.2 to obtain the space $Y$ with a subbasis $(C_i)$. We have $C_i \cap C_j \supset \bigcup_{(i,j,k) \in E} C_k$: if $(i, j, k) \in E$ and $A \in Y$ contains $k$ but not $i$, then by maximality there is $F \subseteq A$ such that $B_F \cap B_i = \emptyset$. As $F \cup \{k\} \subseteq A$, $B_F \cap B_k \neq \emptyset$. It contradicts $B_k \subseteq B_i$. However, we may not have equality. Solution: remove the difference. Let

$$Z = Y \setminus \bigcup_{i,j} \left( C_i \cap C_j \setminus \bigcup_{(i,j,k) \in E} C_k \right).$$

We have removed a $\Sigma_2^0$-subset of $Y$, so $Z$ is still Polish and by construction, $C_i \cap C_j = \bigcup_{(i,j,k) \in E} C_k$ on $Z$. It remains to show that each $C_n$ is non-empty in $Z$. By Baire category, it is sufficient to show that what the complement of what we remove is dense in $Y$, i.e. that every $(C_i \cap C_j)^c \cup \bigcup_{(i,j,k) \in E} C_k$ is dense in $Y$. Let $C_F$ be a non-empty basic open subset of $Y$. If it intersects $(C_i \cap C_j)^c$ then we are done, otherwise $C_F \subseteq C_i \cap C_j$. Let $G = F \cup \{i, j\}$. One has $C_G = C_F$ which is non-empty, so $B_G \neq \emptyset$. Let $A \in B_G \subseteq B_i \cap B_j$. There exists $k$ such that $(i, j, k) \in E$ and $A \in B_k$. Let $A'$ be maximal in $\mathcal{P}$ and contain $A$. One has $A' \in C_F \cap \bigcup_{(i,j,k) \in E} C_k$. $\square$

**Question 2.** Is there an example of a computable topological presentation which does not represent a computable Polish space?
### 4. EFFECTIVE COMPACTNESS. PROOF OF THEOREM 1.3

**Definition 4.1.** A (compact) computable topological space is effectively compact if there exists an enumeration of all finite covers of the space by basic open balls.

**Definition 4.2.** A computable topological presentation is $∩$-decidable if $B_i ∩ B_j = ∅$ is a computable relation in $i, j$.

We now prove the first half of Theorem 1.3 which states that, for a compact Polish space $X$, the following are equivalent:

(1) $X$ has an effectively compact $∩$-decidable (Def. 4.2) topological presentation.

(2) $X$ admits a computably compact Polish presentation.

*Proof of (2) → (1).* It is known that a computably compact Polish space admits a system of $2^{-n}$-covers so that the property $B_i ∩ B_j = ∅$ is decidable for any pair of open balls from the system; [DM23, Thm 1.1]. These balls form an effective basis of the space with the desired property. □

*Proof of (1) → (2).* A computable topological space $X$ is effectively normal ([Sch98], after [Dym84]) if, given (names of) disjoint effectively closed sets $C_0$ and $C_1$, we can effectively produce (names of) disjoint effectively open sets $U_0$ and $U_1$ that separate $C_0$ and $C_1$, i.e., so that

$$C_0 \subseteq U_0 \text{ and } C_1 \subseteq U_1.$$

A very similar lemma has been established in [AH23].

**Lemma 4.1.** *Any effectively compact $∩$-decidable topological space $X$ is effectively normal.*

*Proof.* Fix two disjoint effectively closed sets $C_0, C_1$. Search for finite collections of basic open sets $O_0, O_1, U_0, U_1$ with the properties:

(1) $U_0 \subseteq X \setminus C_0$ and $U_1 \subseteq X \setminus C_1$,

(2) each of the open sets $U_0 \cup O_0$ and $U_1 \cup O_1$ is a cover of $X$,

(3) $O_0 \cap O_1 = \emptyset$.

It is clear that such finite collections of basic open sets exist, and that for any such collection, $C_0 \subseteq O_0$ and $C_1 \subseteq O_1$. Since the $O_0$ and $O_1$ consist of finitely many open sets, we can effectively check (3), while the first two conditions are $\Sigma_1^0$. □

**Lemma 4.2** (Effective Urysohn Lemma [Sch98]). *Let $X$ be an effectively normal computable topological space. Given disjoint effectively closed sets $A$ and $B$ we can uniformly produce a computable function*

$$f_{A,B}: X \to [0, 1]$$

so that $f_{A,B} \upharpoonright_A = 0$ and $f_{A,B} \upharpoonright_B = 1$.

*Proof.* The proof essentially follows the standard textbook argument (e.g., [Mun00, Thm 33.1]) but with one minor modification. To define the map, instead of the set of all rationals we will be using the set of the dyadic rationals. We give more details.
Define a uniformly effective list of closed sets $A_i$ and open sets $O_i$, where $i$ ranges over the dyadic rationals in $[0, 1]$, as follows. Begin with $A_0 = A$ and $O_1 = X \setminus B$. By effective normality, there we can find $A_{1/2}$ and $O_{1/2}$ so that

$$A_0 \subseteq O_{1/2} \subseteq A_{1/2} \subseteq O_1,$$

and then we can iterate this and define

$$A_0 \subseteq O_{1/4} \subseteq A_{1/4} \subseteq O_{1/2} \subseteq A_{1/2} \subseteq O_1,$$

and

$$A_0 \subseteq O_{1/4} \subseteq A_{1/4} \subseteq O_{1/2} \subseteq A_{1/2} \subseteq O_{3/4} \subseteq A_{3/4} \subseteq O_1,$$

and so on. We also set $O_d = X$ for every dyadic $d > 1$ and $A_d = \emptyset$ for each dyadic $d < 0$. The desired function is

$$f_{A,B}(x) = \inf\{i : x \in O_i\} = \sup\{j : x \notin A_j\}.$$

The function is well-defined. The former version of its definition shows that the left cut of the real $f_{A,B}(x)$ is c.e., and the latter implies that the right cut of this real is c.e. as well. $\square$

Note we never used that the closed sets were non-empty.

**Lemma 4.3.** Let $X$ be an effectively compact topological space. We can effectively uniformly list all disjoint effectively closed subsets of $X$.

*Proof.* Two effectively closed sets $C_0 = X \setminus U_0$ and $C_1 = X \setminus U_1$ are disjoint iff $U_0 \cup U_1$ covers $X$. For an effectively open set, being a cover of $X$ is a $\Sigma_1^0$ property, by effective compactness. $\square$

**Lemma 4.4.** For every $x \in X$ and every open $U \ni x$ there exist disjoint effectively closed $C \ni x$ and $D \supseteq (X \setminus U)$.

*Proof.* It is perhaps easiest to use that the compact $X$ is (classically) metrizable. Fix any compatible metric $d$ and the induced Hausdorff metric $d_H$.

*Claim 3.* For each $\epsilon > 0$ and every closed set $C \subseteq X$ there exists an effectively closed set $C_\epsilon \supseteq C$ so that $d_H(C, C_\epsilon) < \epsilon$.

*Proof of Claim 3.* Given a closed $C \subseteq X$, fix a finite cover $(V_i)_{i \le k}$ of $X$ by basic open sets whose diameters are bounded by $\epsilon/2$, where $\text{diam}(V_i) = \text{diam}(\text{cl}(V_i))$. Then the effectively closed set

$$C_\epsilon = X \setminus \bigcup \{V_i : V_i \cap C = \emptyset\}$$

satisfies

$$d_H(C, C_\epsilon) < \epsilon.$$

Clearly, $C \subseteq C_\epsilon$. Suppose $y \in C_\epsilon \setminus C$. Then necessarily $y \in V_j$ for some $V_j$ intersecting $C$, and thus $d(x, C) \le \text{diam}(V_j) \le \epsilon/2 < \epsilon$. $\square$

To complete the proof of the lemma, fix disjoint closed $C' \ni x$ and $D' \supseteq (X \setminus U)$, and let $C = C'_\epsilon \supseteq C'$ and $D = D'_\epsilon \supseteq D' \supseteq (X \setminus U)$, where $\epsilon < d_H(C'_i, D'_i)/2$. $\square$

Using Lemma 4.3, fix an effective enumeration $(C_i, D_i)_{i \in \omega}$ of all (computable indices of) disjoint effectively closed subsets in $X$, perhaps with repetition. Using Lemma 4.1 and Lemma 4.2, produce a uniformly effective list of functions

$$f_{C_i, D_i} : X \to [0, 1]$$
that map the respective $C_i$ to 1 and vanish at $D_i$. Define $g: X \to [0, 1]^\omega$ to be

$$g(x) = (f_{C_i, D_i})_{i \in \omega},$$

where the computable metric on $[0, 1]^\omega$ is given by $d((x_i)_{i \in \omega}, (y_i)_{i \in \omega}) = \sum_i 2^{-i}|x_i - y_i|$. The function is computable. Lemma 4.4 implies that $g$ is injective, and thus $g$ is a computable homeomorphic embedding of $X$ into $[0, 1]^\omega$.

We claim that we can effectively list all finite covers of $f(X)$ (that intersect $f(X)$). For that, list all finite tuples of basic open balls in $[0, 1]^\omega$ and calculate their preimages. Keep only those tuples that consist of balls having non-empty preimage, and so that these preimages cover the entire space $X$. It follows that $f(X)$ is a computable subset of the computably compact $[0, 1]^\omega$, e.g., [DM23, Prop. 3.29]. Thus, in particular, it is $\Sigma_1^0$-closed. It is also well-known that, for closed subsets of computable Polish spaces, being $\Sigma_1^0$-closed is equivalent to the existence of an effectively dense sequence; e.g., [DM23, Lemma 3.27]. Use this effective dense sequence in $f(X)$ and the metric inherited from $[0, 1]^\omega$ to produce a computably compact Polish presentation of $X$. This finishes the proof of (1) $\to$ (2) (of Theorem 1.3). □

If we drop the assumption of $\cap$-decidability, we can use $\emptyset'$ to produce a $\Delta_2^0$-Polish presentation of the space. To finish Theorem 1.3, we need to show that this is sharp, i.e., in absence of $\cap$-decidability we cannot contain a computable Polish presentation (in general). For that, we shall use some known results.

**Proposition 4.1.** For a (separable) Stone space $S$ and the dual Boolean algebra $\hat{S}$, the following are equivalent:

(1) $S$ has an effectively compact computable topological presentation;

(2) $S$ has $0'$-compact computable topological presentation;

(3) $S$ has a $\Delta_2^0$-compact Polish presentation;

(4) $S$ has a $\Delta_2^0$-Polish presentation;

(5) $S$ has a right-c.e. Polish effectively compact presentation;

(6) $\hat{S}$ has a c.e. presentation, i.e., is isomorphic to a factor of the (computable) atomless Boolean algebra by a c.e. ideal;

(7) $\hat{S}$ has a $\Delta_2^0$-presentation.

*Proof.* The implications (1) $\to$ (2) and (3) $\to$ (4) are trivial (and so is (6) $\to$ (7)).

(2) $\to$ (3): This follows from Theorem 1.3.

(5) $\to$ (1): Basic open balls in a right-c.e. Polish space induce a computable topological presentation of the space; e.g., [KK17, Thm 2.3] or [DM23, Prop. 2.4].

(4) $\to$ (7): This is [HTMN20, Thm 1.1] relativised to $\emptyset'$.

(6) $\to$ (5): This is [BHTM23, Thm 3.1].

(7) $\to$ (6): This is a well-known fact due to Feiner [Fei70a]. □

Now, to establish the final part of Theorem 1.3, we argue that there exists an effectively compact topological space with no computable Polish presentation. To see why such a space exists, fix a c.e. presented Boolean algebra without a computable presentation [Fei70a], and apply Proposition 4.1 and the aforementioned [HTMN20, Thm 1.1].

This finishes the proof of Theorem 1.3.
*Remark* 4.1. It also follows that there exists an effectively compact topological space that is not homeomorphic to any *∩*-decidable effectively compact topological space.

REFERENCES

[AH23] Djamel Eddine Amir and Mathieu Hoyrup. Strong computable type. *Computability*, 12(3):227-269, 2023.

[AK00] C. Ash and J. Knight. *Computable structures and the hyperarithmetic hierarchy*, volume 144 of *Studies in Logic and the Foundations of Mathematics*. North-Holland Publishing Co., Amsterdam, 2000.

[BHTM23] Nikolay Bazhenov, Matthew Harrison-Trainor, and Alexander Melnikov. Computable Stone spaces. *Ann. Pure Appl. Logic*, 174(9):103304, 2023.

[BMN] N. Bazhenov, A. Melnikov, and K.M. Ng. Every $\Delta_2^0$ Polish space is computable topological. To appear.

[Ceı59] G. S. Ceitin. Algorithmic operators in constructive complete separable metric spaces. *Dokl. Akad. Nauk SSSR*, 128:49–52, 1959.

[DM23] R. Downey and A. Melnikov. Computably compact metric spaces. *The Bulletin of Symbolic Logic*, 2023. To appear. doi: 10.1017/bsl.2023.16.

[Dym84] E. Z. Dyment. Recursive metrizability of enumerated topological spaces and bases of effective linear topological spaces. *Izv. Vyssh. Uchebn. Zaved. Mat.*, (8):59–61, 1984.

[EG00] Y. Ershov and S. Goncharov. *Constructive models*. Siberian School of Algebra and Logic. Consultants Bureau, New York, 2000.

[Fei70a] Lawrence Feiner. Hierarchies of Boolean algebras. *J. Symbolic Logic*, 35(3):365–374, 09 1970.

[Fei70b] Lawrence Feiner. Hierarchies of Boolean algebras. *J. Symbolic Logic*, 35:365–374, 1970.

[GK02] S. S. Goncharov and J. F. Knight. Computable structure and non-structure theorems. *Algebra and Logic*, 41(6):351–373, 2002.

[GKP17] Vassilios Gregoriades, Tamás Kispéter, and Arno Pauly. A comparison of concepts from computable analysis and effective descriptive set theory. *Math. Structures Comput. Sci.*, 27(8):1414–1436, 2017.

[GW07] Tanja Grubba and Klaus Weihrauch. On computable metrization. *Electron. Notes Theor. Comput. Sci.*, 167:345–364, 2007.

[Hig61] G. Higman. Subgroups of finitely presented groups. *Proc. Roy. Soc. Ser. A*, 262:455-475, 1961.

[HKS20] M. Hoyrup, T. Kihara, and V. Selivanov. Degree spectra of homeomorphism types of Polish spaces, 2020. Preprint.

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

[HTMN20] Matthew Harrison-Trainor, Alexander Melnikov, and Keng Meng Ng. Computability of Polish spaces up to homeomorphism. *The Journal of Symbolic Logic*, 85(4):1664-1686, 2020.

[IK21] Zvonko Iljazović and Takayuki Kihara. Computability of subsets of metric spaces. In *Handbook of computability and complexity in analysis*, Theory Appl. Comput., pages 29-69. Springer, Cham, 2021.

[Kec95] Alexander S. Kechris. *Classical Descriptive Set Theory*. Springer, January 1995.

[Khi98] N. Khisamiev. Constructive abelian groups. In *Handbook of recursive mathematics, Vol. 2*, volume 139 of *Stud. Logic Found. Math.*, pages 1177-1231. North-Holland, Amsterdam, 1998.

[KK08] Margarita Korovina and Oleg Kudinov. Towards computability over effectively enu-merable topological spaces. In *Proceedings of the Fifth International Conference on Computability and Complexity in Analysis (CCA 2008)*, volume 221 of *Electron. Notes Theor. Comput. Sci.*, pages 115-125. Elsevier Sci. B. V., Amsterdam, 2008.

[KK17] Margarita Korovina and Oleg Kudinov. The Rice-Shapiro theorem in computable topology. *Log. Methods Comput. Sci.*, 13(4):Paper No. 30, 13, 2017.

[KMN] H.T. Koh, A. Melnikov, and K.M. Ng. Counterexamples in effective topology. To appear.
[KMN23] H. T. Koh, A. Melnikov, and K. M. Ng. Computable topological groups, 2023. Submitted.

[KW85] Iraj Kalantari and Galen Weitkamp. Effective topological spaces. I. A definability theory. *Ann. Pure Appl. Logic*, 29(1):1–27, 1985.

[LMN23] M. Lupini, A. Melnikov, and A. Nies. Computable topological abelian groups. *J. Algebra*, 615:278–327, 2023.

[MN23] A. Melnikov and K. M. Ng. Separating notions in computable topology. Submitted, 2023.

[Mos64] Y. N. Moschovakis. Recursive metric spaces. *Fund. Math.*, 55:215–238, 1964.

[Mun00] James R. Munkres. *Topology*. Prentice Hall, Inc., Upper Saddle River, NJ, second edition, 2000.

[Sch98] Matthias Schröder. Effective metrization of regular spaces. *Computability and Complexity in Analysis*, Informatik Berichte 235:63–80, 1998.

[Spr90] Dieter Sreen. A characterization of effective topological spaces. In *Recursion theory week (Oberwolfach, 1989)*, volume 1432 of *Lecture Notes in Math.*, pages 363–387. Springer, Berlin, 1990.

INSTITUT NATIONAL DE RECHERCHE EN INFORMATIQUE ET EN AUTOMATIQUE, NANCY, FRANCE

VICTORIA UNIVERSITY OF WELLINGTON, WELLINGTON, NEW ZEALAND

Email address: alexander.g.melnikov@gmail.com

NANYANG TECHNOLOGICAL UNIVERSITY, SINGAPORE

Email address: kmng@ntu.edu.sg