Separating notions in effective topology

1. Introduction

In the past decade or two there has been an increasing interest in the computability-theoretic aspects of abstract topological spaces. The central questions in such investigations include:

—	What does it mean for a space to be computably presented?
—	When does a space admit a computable presentation?
—	Can we compute the standard topological invariants of a computable space?
—	Can we classify computably presentable spaces in a given class?

To attack these and other similar questions we will have to move away from classical computable analysis which typically deals with fixed “natural” computable presentations of Polish and separable Banach spaces as presented in, e.g. [1, 7, 24, 46, 53]. Investigations of computable presentability in abstract topology contribute to the fast developing subject in computable mathematics, namely computable topology. There had been many early investigations into the effective aspects of abstract topological spaces, and we refer the reader to [20, 41, 51]. Following these early work, there have been a lot of more recent work in computable topology such as [13, 18, 21, 27, 28, 52, 54]. Some of this work has been motivated by the recently revived systematic research in computable topological groups. Such studies restricted to profinite groups began with Metakides and Nerode [38], La Roche [29, 30] and Smith [49, 50]. After several decades of dormancy, computable topological groups (not necessarily restricted to profinite ones) have found new unexpected applications in computable structure theory [15, 35] and, remarkably, in computable topology [31, 33] where they were used to solve problems that seemed unrelated to topological groups.

Computable topology is notorious for having a “zoo” of various notions of computability for a topological space, and for a topological group alike. In contrast with effective algebra [2, 11] where all standard notions of computable presentability in common classes had been separated several decades ago (e.g. Novikov [42], Boone [5], Feiner [12], Khisamiev [22], Odintsov and Selivanov [43]), some of the key notions of computable presentability in topology have only very recently been shown to be different [3, 16, 18, 31]; these results will be discussed in detail later in the paper. In fact, some of the other key notions, such as left-c.e. Polish and computable Polish presentations, have not yet been separated up to homeomorphism. The first main goal of this paper is to fill this gap in the literature by constructing counterexamples.

The second main goal is to apply the techniques used to separate notions in computability to obtain a positive result about topological groups. In the related work [31, 36], several notions of computable presentability for a totally disconnected locally compact (tdlc) group have been proposed. Remarkably, it has been illustrated in [31, 36] that several natural definitions are indeed equivalent, and that the approach in  [31, 36] is also equivalent to the well-established notions of computable presentability in the important discrete [32, 47] and profinite [30, 38, 50] cases. In this paper, we connect these investigations to the study of computable Polish groups that are not necessarily tdlc (initiated in [35]). More specifically, we obtain a characterization of computable presentability for a tdlc group in terms of an arbitrary (compatible) computable metric. We believe that our result is unexpected since it uses a seemingly weak hypothesis about the metric.

To state the results formally we need a few well-known definitions. The notion of a computable Polish space is the most well-established notion of computable presentability for a Polish(-able) space. It can be traced back to Ceitin [9] and Moschovakis [39]. A Polish space is computable or computably metrized if there is a complete, compatible metric d and a dense subset of special or ideal points ${(x_i)}_{i\in \omega }$ of the space such that $d(x_i,x_j)$ are computable reals uniformly in i and j. This means that given i, j, n we can compute $d(x_i,x_j)$ to within a precision of $2^{-n}$. This definition can be relativized to an oracle; for instance, a ${\mathrm{\Delta }}_2^0$-presented space can also be defined using algorithms that have access to an oracle for the halting problem.

The following two refinements of ${\mathrm{\Delta }}_2^0$-presentability for spaces are of special importance. If $d(x_i,x_j)$ is right-c.e. (left-c.e.), meaning that we can uniformly in $i,j$ list the rationals in the right (respectively, left) cut of the real $d(x_i,x_j)$, then we say that the space is right-c.e. (respectively, left-c.e.) presented. In the literature, left- and right-c.e. spaces are also known, respectively, under the names of lower- and upper-semicomputable spaces. The intuition is that right-c.e. and left-c.e. spaces roughly correspond to ${\mathrm{\Sigma }}_1^0$- and ${\mathrm{\Pi }}_1^0$-presentations, respectively, in computable structure theory. In the context of topological groups this intuition is formally clarified in [25] where it is noted that, e.g. right-c.e. and ${\mathrm{\Sigma }}_1^0$-presentability are equivalent for discrete groups. For a Stone space, right-c.e. presentability with a mild additional assumption is equivalent to ${\mathrm{\Sigma }}_1^0$-presentability of the dual Boolean algebra [3].

As we mentioned above, ${\mathrm{\Delta }}_n^0$-, ${\mathrm{\Pi }}_n^0$- and ${\mathrm{\Sigma }}_n^0$-presentability in effective algebra had been separated (up to isomorphism) several decades ago. In contrast, the examples of ${\mathrm{\Delta }}_2^0$-presented Polish spaces with no computable presentations up to homeomorphism have been found only very recently; see [16, 18]. The notions of a right-c.e. space, computable Polish space, and a “computably compact” space (to be defined later) have been separated in [3, 16, 18, 31].

One possible reason for this delay is that producing such examples typically requires significant effort and new ideas, especially if we want to keep our examples within some natural class of spaces, e.g. compact connected spaces. The above-cited results rely on (co)homological methods, the theory of computably compact spaces, results from effective algebra, and priority techniques; for a detailed exposition of the methods and the cited results see the recent technical survey [10].

We note that it was not known whether every left-c.e. Polish space must be homeomorphic to a computable one. We will see in Proposition 3.8 that every left-c.e. Stone space has a computable Polish presentation, up to homeomorphism (indeed, a computably compact one by [16]). The first main result of the paper is.

Theorem 1.1. There exists a left-c.e. Polish space not homeomorphic to any computable Polish space.

The techniques that we developed to prove the result have another peculiar and important implication. We will later define the weaker notion of a computable topological presentation of a space. In this notion, we only assume that there is an effective list of a countable base of the topology, and that we can effectively enumerate the finite intersections of basic open sets. A standard example of such a presentation is any right-c.e. presented space. It follows from one of the aforementioned separation results ([3]) that there is a right-c.e. Stone space with no computable Polish presentation; therefore there is a Polish space with a computable topological presentation but with no computable Polish presentation.

However, it seems that the following result is new, improving on the previous result: There is a locally compact Polish space with a computable topological presentation but with no right-c.e. Polish presentation (see Theorem 4.4). We point out that Theorem 4.4 contrasts greatly with a main result in the companion paper [25]. In that paper it was shown that every locally compact Polish group with a computable topological presentation is topologically isomorphic to a right-c.e. Polish group. The proof of Theorem 4.4 will in fact show something stronger: there is no a priori upper bound on the complexity of the simplest completely metrized presentation of a locally compact computable topological Polish(able) space.

We have already discussed that modern computable topology is motivated by its consequences in the study of the effective aspects of Polish groups. In fact, the two subjects are so interconnected that no firm line can be drawn between them. For instance, in the recent papers [31, 33, 34] Pontryagin duality between compact and discrete Polish abelian groups has been applied to derive corollaries about connected compact spaces. In this paper, we also give an application of our methods to groups. More specifically, we apply our machinery to derive the following positive result about tdlc groups, which is the second main result of the paper.

A separable group is tdlc if it is either discrete or its domain is homeomorphic to the disjoint union of clopen sets, each homeomorphic to $2^{\omega }$. If it is compact, then the group is profinite. Classically, tdlc groups have been studied in much detail; we cite the recent papers [8, 14, 17, 57, 56].

As we already mentioned above, the notion of a computable tdlc presentation [31, 36] generalizes the notions of computability that are well-established in the discrete and profinite cases. Essentially it requires that we fix the nicest possible presentation of the domain as a locally compact subset of ${\omega }^{\omega }$ and assume that the group operations are given by computable functionals acting on strings. It has also been shown in [31, 36] that this is actually equivalent to several other definitions, one involving a Stone-type duality between such a group and the (countable, discrete) groupoid of its cosets, and the other that uses subgroups of the infinite symmetric group $S_{\infty }$. As shown in [36, 31], the notion enjoys a large number of closure properties. Nonetheless, it may seem that this approach to computability for tdlc groups is a bit too strong since it assumes too much about a presentation. For instance, it assumes the metric is the standard ultra-metric induced by ${\omega }^{\omega }$. It is natural to wonder how this is related to the general theory of computably metrized Polish groups studied in [16, 33, 35, 45]. In the general theory we merely require that the group has a computable Polish presentation (compatible with the topology) which makes the group operations computable. In particular the metric, while required to be computable, could still be “unnatural” or might not be an ultra-metric. We believe that our second main result stated below answers this question in a strong way.

Recall the notion of locally compact space: given a point x there is a basic open set B and a compact K such that $x\in B\subseteq K$. We will use the most straightforward computable version of this notion (cf. [44, 55, 58]) that involves the robust notion of a computably compact (sub)space. We say that a group is computably locally compact if it is computable Polish in the sense of [35] and is additionally computably locally compact, as defined in Subsec. 2.5.

Theorem 1.2. Suppose G is a separable tdlc group. The following are equivalent:

(1)	G has a computable locally compact presentation.
(2)	G has a computable tdlc presentation.

Combined with other results from the literature, Theorem 1.2 provides us with the last missing implication between various (seemingly) most important notions of effective presentability for Polish groups; see Fig. 2.

The two main results of the paper are related technically and share a similar motivation (comparing various notions of computable presentability in topology). As far as we can tell, there is no explicit way to apply one to prove the other. The proofs of our main results are not very long, and not very typical for a recursion-theory paper. Nonetheless, much preliminary analysis is needed to make them work. Our proofs exploit the machinery of effective compactness explained in detail in [10]. We shall make our paper as self-contained as possible. The readers should however prepare themselves for an extended preliminary section consisting of a number of lemmas and propositions.

The structure of the paper is as follows. Section 2 is a preliminaries section. In Sec. 3, we prove several technical lemmas and facts that will be used in the proofs of both Theorems 1.1 and 1.2. Section 3 also contains the proof of the above-mentioned Proposition 3.8 stating that every left-c.e. Stone space admits a computable Polish presentation. In Sec. 4, we develop our techniques further, and we establish that, for any fixed oracle X, there is a computable topological space not homeomorphic to any X-computable Polish space. In Subsec. 4.1, we also explain how Proposition 3.8 can be used to show that “right-c.e Polish presentability” does not imply “left-c.e. Polish presentability”, up to homeomorphism. Section 5 contains the proof of Theorem 1.1, and Sec. 6 is completely devoted to the proof of Theorem 1.2.

2. Definitions from Computable Metric Space Theory

2.1. Computable Polish spaces and groups

The notions below are standard and can be found in, e.g. [10, 19].

Definition 2.1. A Polish space M is computable Polish or computably (completely) metrized if there is a compatible, complete metric d and a countable sequence of special points ${(x_i)}_{i\in \omega }$ dense in M such that, on input $i,j,n$, we can compute a rational number r such that $|r-d(x_i,x_j)|<2^{-n}$.

Remark 2.2. We allow the possibility that $d(x_i,x_j)=0$. However, it is not difficult to exclude repetitions from the dense set, if necessary.

A basic open ball is an open ball having a rational radius and centered in a special point. Let X be a computable Polish space, and $(B_i)$ is the effective list of all its basic open balls, perhaps with repetition. (We also sometimes write $B_r(x)$ for the open ball having radius r and centered in x: $B_r(x)=\{y:d(x,y)<r\}$.)

Definition 2.3. We call

the name of x (in X).

We can also use basic open balls to produce names of open sets, as follows. A name of an open set U in a computable topological space X is a set $W\subseteq \mathbb{N}$ such that $U={\bigcup }_{i\in W}{B}_i$, where $B_i$ stands for the ith basic open set in the basis of X. If an open U has a c.e. name, then we say that U is effectively open or c.e. open.

Definition 2.4. A function $f:X\to Y$ between two computably metrized Polish spaces is effectively continuous if there is a c.e. family $F\subseteq {𝒫}(X)\times {𝒫}(Y)$ of pairs of (indices of) basic open sets in such that:

(C1):	for every $(U,V)\in F$, $f(U)\subseteq V$;
(C2):	for every $x\in X$ and basic open $E\ni f(x)$ in Y there exists a basic open $D\ni x$ in X such that $(D,E)\in F$.

Note that a function is continuous if and only if it is effectively continuous relative to some oracle. The lemma below is well known.

Lemma 2.5. Let $f:X\to Y$be a function between computable Polish spaces. The following are equivalent:

(1)	f is effectively continuous.
(2)	There is an enumeration operator $\mathrm{\Phi }$that on input a name of an open set Y (in Y), lists a name of $f^{-1}(Y)$ (in X).
(3)	There is an enumeration operator $\mathrm{\Psi }$, that given the name of $x\in X$, enumerates the name of $f(x)$in Y.
(4)	There exists a uniformly effective procedure that on input a fast Cauchy name of $x\in M$lists a fast Cauchy name of $f(x)$ (note that the Cauchy names need not be computable).

We say that a map between computable Polish spaces is computable if it satisfies the conditions in the lemma above. Clearly, computable maps are closed under composition, when it is well defined.

Definition 2.6 ([33, 35]). A computable Polish group is a computable Polish space together with computable group operations ⋅ and ${}^{-1}$.

2.2. Effectively open maps

Fix computable Polish spaces X and Y.

Definition 2.7. A function $f:X\to Y$ is effectively open if there is a c.e. family F of pairs of basic open sets such that

(O1):	for every $(U,V)\in F$, $f(U)\supseteq V$;
(O2):	for every $x\in X$ and any basic open $E\ni x$ there exists a basic open $D\ni f(x)$ such that $(E,D)\in F$.

The lemma below is elementary.

Lemma 2.8 ([35]). Let $f:X\to Y$be a function between computable Polish spaces. The following are equivalent:

(1)	f is effectively open.
(2)	There is an enumeration operator that given a name of an open set A in X, outputs a name of the open set f(A) in Y.

In particular, if f is computable and is a homeomorphism, then it is effectively open if, and only if, $f^{-1}$ is computable. In this case we say that f is a computable homeomorphism. We say that two computable metrizations on the same Polish space are effectively compatible if the identity map on the space is a computable homeomorphism when viewed as a map from the first metrization to the second metrization under consideration.

A special kind of self-homeomorphisms is the (left or right) translations of a Polish group by its elements, and also the group inverse map $g\mapsto g^{-1}$.

Fact 2.9. Multiplication and inverse operators are both effectively open in a computable Polish group.

Proof. Given some name for an effectively open set U, in order to enumerate the name for $U^{-1}$, simply enumerate the preimage of U under ${}^{-1}$. This must be the name for $U^{-1}$ since ${(U^{-1})}^{-1}=U$. Thus ${}^{-1}$ is effectively open.

Now given names for open $U,V$, we produce a name for $U\cdot V$. The map $(x,y)\to x^{-1}y$ is computable. Enumerate all basic open B such that there is some basic open set A such that

Since U is c.e. open and A is basic open, $A\cap U\ne \varnothing$ will always be witnessed by a special point, thus $A\cap U\ne \varnothing$ is a ${\mathrm{\Sigma }}_1^0$ property. Also, $A^{-1}\cdot B\subseteq V$ is c.e. by Lemma 2.5.

We claim that the union of all such B is equal to $U\cdot V$. First, assume B is enumerated by the procedure above. Fix $a\in A\cap U$. For each $b\in B$ we have $b=a\cdot a^{-1}b\in U\cdot A^{-1}\cdot B\subseteq U\cdot V$, and so $B\subseteq U\cdot V$. Conversely let $a\in U$ and $b\in V$. Since $a^{-1}\cdot ab=b\in V$, we can let $A,B$ be basic open sets containing a and $ab$, respectively, such that $A^{-1}\cdot B\subseteq V$. Then B will be enumerated by the procedure above, and $ab\in B$. □

2.3. Computable topological spaces

We will use the following approach that seems rather standard throughout the literature (e.g. [26, Definition 2.1; 54, Definition 4]). A computable topological space is given by a computable, countable basis of its topology for which the intersection of any two basic open sets (“basic balls”) can be uniformly computably listed.

Definition 2.10. A computable topological presentation of a topological space X is given by a sequence ${(B_i)}_{i\in \omega }$ of non-empty open sets of X (that are called “basic”) and a computably enumerable set W such that for any $i,j\in \omega$,

Perhaps, the most natural examples of computable topological Polish spaces are right-c.e. Polish spaces; see, e.g. [26, Theorem 2.3]; we also cite [3, 10] for a detailed proof. For instance, every computably metrized Polish space is a computable topological space. We will apply the notion above only when the space is Polish, but it can be used for a much more broad class of topological spaces in a meaningful way (e.g. for $T_0$ spaces). For $i\in \omega$, we identify the basic open set $B_i$ with its index i.

Remark 2.11. Some of the basic results from the previous subsection (e.g. Fact 2.2) can be proven for computable topological spaces perhaps with some mild additional assumptions. For instance, they should certainly work for right-c.e. spaces as well. For Fact 2.2, we do not need any extra assumptions since $A\cap U\ne \varnothing$ is c.e. (recall we assume our basic open sets are non-empty). We will not need this degree of generality.

We do not require the map $i\to B_i\subseteq X$ to be “effective” in any sense. This notion of presentation is so weak that, in fact, two non-homeomorphic spaces X and Y can share the exact same computable topological presentation, i.e. they share the same c.e. set W. The only difference will be in the interpretation of the basic sets $B_i$. There is indeed no contradiction here, because the notion of a homomorphism refers to individual points of the homeomorphic space (the map has to be a bijection in the first place), but computable topological presentations are point-free. This strange and unnatural feature of computable topological presentations will be explained (and exploited) in the proof of Theorem 4.4.

2.4. Effective compactness

The following definition is equivalent to many other definitions of effective (computable) compactness that can be found in the literature.

Definition 2.12. A compact computable Polish space is effectively (computably) compact if there is a (partial) Turing functional that given a countable cover of the space outputs its finite subcover (and is undefined otherwise).

This is equivalent to saying that, for every n, we can uniformly produce at least one finite open $2^{-n}$-cover of the space by basic open balls. For several equivalent definitions of effective compactness, see [10, 19]. It is also well known that, given a computable Polish space C that is compact (but not necessarily computably compact) using $0^{\prime }$ one can produce a sequence of basic open $2^{-n}$-covers of the space, thus making it computably compact relative to $0^{\prime }$. The following elementary fact is well known (e.g. [10]).

Lemma 2.13. A computable image of a computably compact space is itself computably compact.

To see why the lemma is true, list basic open balls in the image until their preimages finally cover the domain of the computable map. We will also use that the inverse of a bijective computable map $f:X\to Y$, where X and Y are computably compact, is also computable. Also, it is well known that both the supremum and the infimum of a computable function $f:X\to ℝ$ are computable provided that X is computably compact, and this is uniform. We cite [10] for further background on computably compact spaces.

2.5. Effective local compactness

Theorem 1.1 uses notions that need to be formally clarified. The usual definition of a locally compact space M says that for every $x\in M$ there is an open B and a compact $K\subseteq M$ such that $x\in B\subseteq K$. In the context of computable Polish spaces, it makes sense to adopt the following notion of effective local compactness which is essentially the approach taken in [44, 55, 58], up to notation change.^a

Definition 2.14. A computable Polish space M is computably locally compact if there is a uniform procedure which, given (the name $N^x$ of) any point x outputs a basic open B and a computable compact $K\subseteq M$ such that $x\in B\subseteq K$, where K is given by a sequence of finite open $2^{-n}$-covers so that each ball in the cover is centered in a (computable) point in K and has a rational radius.

If $B=B(c,r)$ is an open ball, then we write $B^c$ to denote the respective closed ball $\{x:d(c,x)\le r\}$ which does not have to be equal to the closure of B in general. Recall that we say that $B=B(c,r)$ is basic if c is special and r is a rational (given as a fraction). If c and r are merely computable, we say that the ball is computable. The following proposition will be rather useful.

Proposition 2.15. In the notation of the previous definition, we can assume K is equal to $B^c$, where $B\ni x$is a computable open ball.

Proof. Proposition 3.30 of [10] establishes that we can uniformly produce a system of $2^{-n}$-covers of K that consists of closed computable balls each of which is uniformly computably compact. If we have $x\in B\subseteq K$, then wait for such a small enough closed ball D from one of these covers such that $x\in D$ and $D^c\subseteq B$; where the latter is witnessed by formal inclusion, i.e. is deduced from the triangle inequality: $B_r(x){\subseteq }_{\mathrm{\text{form}}}{B}_q(y)$ if $d(x,y)+q<r$. This process is uniformly effective. However, the potential danger here is that the proof of Proposition 3.30 will have to be restricted to the topology of K.

The proof of Proposition 3.30 never mentions compactness of the ambient space M, but it uses [10, Lemma 3.20] that claims that we can list basic open U such that $D^c\cap U\ne \varnothing$. In our context U should be replaced by $U\cap K$. However, since D is formally contained in some $B\subseteq K$, checking whether a basic open U intersects the closed ball $D^c$ can be restricted to K which is computably compact, by assumption. (For that, in the notation of [10, Lemma 3.20], we should additionally require that a small enough ball C from the cover that we are searching for is formally contained in B.) □

Definition 2.16. A computable Polish group is computably locally compact if its domain is computably locally compact (and the operations are computable).

We now discuss trees. Our (rooted) trees are viewed as sets of strings in ${\omega }^{<\omega }$ closed under prefixes. A tree has no dead ends if every finite string is extendible to an infinite path through the tree. The space of paths through a tree T is denoted $[T]$. The space T is a metric space under the shortest common initial segment ultrametric. A computable tree with no dead ends evidently induces a computable Polish presentation on $[T]$.

Definition 2.17. We say that a computable tree is nicely locally compact if it has no dead ends, only its root is possibly $\omega$-branching, and for every node we can uniformly compute the number of its successors.

Although we will not use the fact below, it is important to know that the two definitions given above are actually equivalent for trees that we care about.

Fact 2.18. For a computable locally compact tree T that is infinitely branching only perhaps at the root, the following are equivalent:

(1)	T is nicely locally compact.
(2)	$[T]$ is computably locally compact.

Proof. The implication $(1)\to (2)$ is obvious. For $(2)\to (1)$, observe that in the metric induced by the tree, $B=B^c$ for any basic open ball B. In Proposition 2.15, the radii of balls are merely computable. However, the radius of any basic open ball is of the form $2^{-n}$, and also any computable open ball in $[T]$ is actually equal to some basic clopen ball. We therefore can compute the radius of the ball from Proposition 2.15 to a sufficient precision and be sure that it represents a certain basic clopen ball extending some fixed string. Clearly, computable compactness of the ball is equivalent to the tree being computably branching. Since such balls/subtrees cover the whole space, we conclude that $(1)$ holds. □

Definition 2.19 ([31, 36]). Let G be a Polish t.d.l.c. group. A computable tdlc presentation of G is a topological group $Ĝ\cong G$ of the form $Ĝ=([T],\cdot {,}^{-1})$ such that

(1)	T is a nicely locally compact tree;
(2)	$\cdot :[T]\times [T]\to [T]$ and ${}^{-1}:[T]\to [T]$ are computable (as operators).

Remark 2.20. We usually omit “nicely” throughout the rest of the paper. In fact, it is known ([36]) that the assumption of niceness can be omitted from the definition above. The resulting notion (without the “niceness” assumption) will be equivalent to the seemingly stronger notion above, up to computable topological group isomorphism. This observation will also follow from the proof of our second main result (Theorem 1.2) that will be presented below.

3. Effective Stone Spaces

In this section we accumulate techniques related to splitting a space into clopen components. The techniques are not restricted to only Stone spaces. This machinery will be crucial in the proofs of both main results of the paper. Some of the elementary technical facts established in this section seem to be new as stated, but most of the rest were included to make the paper self-contained. We refer to [10] for a detailed exposition of the general theory. We also prove Proposition 3.8 mentioned in the preliminaries; this simple (but perhaps unexpected) result is new.

The fact below (though not as stated) is due to Hoyrup, Kihara and Selivanov [48]. It can also be recovered from Brattka et al. [6] and Harrison-Trainor, Melnikov and Ng [16].

Theorem 3.1. Given a computably compact Stone space M, we can uniformly produce a computable computably branching tree T without dead ends and a computable homeomorphism $f:M\to [T]$.

Proof. We say that clopen X and Y form a clopen split of a Polish space M if $X\cap Y=\varnothing$ and $X\cup Y=M$. The key step is the following. □

Lemma 3.2. Suppose M is computably compact. Then there is a computable enumeration of all clopen splits of M (perhaps, with repetition). In this enumeration each clopen set X is represented by (a finite tuple of parameters coding) a finite collection of basic open balls whose union is X.

Proof. Suppose $M=X\bigsqcup Y$ is a clopen split, and let $\delta$ be the infimum-distance between these compact open sets

(Since $X\times Y$ is compact and d is continuous, it attains its infimum at some pair $(x_0,y_0)$. In particular, $\delta >0$.)

Suppose $0<𝜖<\delta /4$. Then every finite $𝜖$-cover will consist of two formally disjoint subsets of basic open balls, in the following sense. Every ball covering a point in X cannot contain a point in Y, and every ball covering a point in Y cannot contain a point in X. If a basic open B has its center in X and D has its center in Y, then the distance between their centers is at least $\delta$, while the sum of their radii is at most $\delta /2<\delta$, making them formally disjoint (this is ${\mathrm{\Sigma }}_1^0$).

On the other hand, if a finite open cover of M consists of two formally disjoint subcovers, then these subcovers induce a split of M into clopen components. Since the property of being formally disjoint is a c.e. property, we can effectively list all such clopen splits. □

Suppose X and $\neg X=M\setminus X$ are clopen components represented as finite unions of formally disjoint basic open balls, as in the proof of the lemma above. Given a special point x in M, we can use these finite open names to wait and see whether x in X or x in $\neg X$. This makes both X and $\neg X$ computable closed subsets of the computably compact M, and thus they can be viewed as computably compact spaces. In particular, their diameters are computable reals. (Note this is uniform.)

Lemma 3.3. Given two clopen sets X and Y, as well as their complements $\neg X$and $\neg Y$ (represented by the strong indices of their finite open names), we can additionally decide whether $X\cap Y$is empty, and if it is not empty, then output a finite open name of it and its complement.

Proof. For that, recall that a basic open ball $B_r(x)$ is formally contained in a basic open ball $B_q(y)$ if $d(x,y)+q<r$; this is ${\mathrm{\Sigma }}_1^0$. Search for an $𝜖$-cover of the space M, where $𝜖$ is so small that every ball in the new cover is formally contained in some ball of each of the two covers that we fixed above (the first for X and $\neg X$, and the second for Y and $\neg Y$). Such a cover must exist; the standard proof of Lebesgue’s Number Lemma guarantees formal inclusion. Then $X\cap Y$ is composed of those balls in the cover that are formally contained in balls corresponding to names of X and of Y. If there are no such balls, then declare the intersection $X\cap Y$ empty. □

To build the tree T, associate the empty string with M. Suppose $\sigma \in T$ of length i has been defined, and suppose $\sigma$ has been associated with a clopen X. Let $X_i\bigsqcup \neg X_i$ be the ith clopen split of M in the effective list of all such splits produced above. If both $X\cap X_i$ and $X\cap \neg X_i$ are non-empty, then create two children of $\sigma$, $\sigma ˆ0$ and $\sigma ˆ1$, and associate $X\cap X_i$ with $\sigma ˆ0$ and $X\cap \neg X_i$ with $\sigma ˆ1$. If only one of the $X\cap X_i$ and $X\cap \neg X_i$ is non-empty, say $X\cap X_i\ne \varnothing$, then create only $\sigma ˆ0$ and associate it with $X\cap X_i$.

It should be clear that $[T]$ is homeomorphic to M. We claim that it is computably homeomorphic to M. Given a (not necessarily computable) point $x\in M$ and n, search for $\sigma \in T$ such that the component of M associated with $\sigma$ has diameter at most $2^{-n}$ and $x\in [\sigma ]$. Output (any point in) $[\sigma ]$. This gives a computable name of a surjective computable f (that can be viewed as the identity map) between the computably compact spaces M and $[T]$. Since both spaces are computably compact, $f^{-1}$ is also computable.

Remark 3.4. We see that, under a careful choice of notation at the end of the proof above, f can be chosen equal to the identity map on M. In other words, the metric induced by T is effectively compatible with the original metric on M. In particular, any operation defined on M that is computable with respect to the old metric will also be computable with respect to the new ultrametric induced by T.

We shall use the following observation. Write $A{\cong }_{\mathrm{\text{comp}}}B$ if A is computably homeomorphic to B.

Remark 3.5. Suppose $M=C\bigsqcup D$ is computably compact, where C and D are clopen and (thus) computably compact. Let $T_0$ and $T_1$ be computably finitely branching trees with no dead ends such that $C{\cong }_{\mathrm{\text{comp}}}[T_0]$ and $D{\cong }_{\mathrm{\text{comp}}}[T_1]$. Define a new tree T by adjoining the successors of the root of $T_1$ to the root of $T_0$. Then $M{\cong }_{\mathrm{\text{comp}}}[T]$, and this is uniform.

The lemma below extends the techniques described above to spaces that are not necessarily compact, but at the cost of a few Turing jumps. The lemma will be used later in the proof of Theorem 1.1.

Lemma 3.6. There is an arithmetical procedure that enumerates all connected components of a given computable Polish space that are both compact and open.

Proof. Let C be a compact open component of a computable Polish M upon a computable dense set X. Since C is open, it is the union of finitely many basic open balls, say $B_0,\dots ,B_k$. These balls cannot intersect the complement of C. If $\delta$ is the Lebesgue number of this cover, then any ball in any $\delta$-subcover is contained in one for the $B_i$ that does not intersect the complement, which implies ${inf}_{x\in C,y\notin C}d(x,y)\ge \delta$. We can arithmetically search for basic open $B_0,\dots ,B_n$ and a $\delta >0$ such that

where x and y range over special points only.

Once such balls are fixed, we can define the computable subspace C of M equal to the closure of the set of the special points that are contained in $B_0\cup \cdots \cup B_n$. Since a Polish space is compact if, and only if, it is totally bounded, it is arithmetical to tell whether this subspace C is compact [37]. Because the subspace C is separated from the rest by $\delta$, it is also open. It is also arithmetical to tell whether a compact space is connected; this follows from, e.g. Lemma 3.2. □

Remark 3.7. A more detailed analysis of the argument shows that $0^{\prime \prime \prime }$ can list compact connected components of a computable space, and we suspect this is sharp. The upper bound can be improved to $0^{\prime \prime }$ if the whole space is itself compact; this follows from Lemma 3.2 relativized to $0^{\prime }$.

3.1. A byproduct of our technique

It is known that there exists a right-c.e. Stone space not homeomorphic to any computable Polish space [3]. It is also known that any computable Polish Stone space is homeomorphic to a computably compact one [16]; this is explained in detail in [10]. Interestingly, we can push this positive result to also include left-c.e. Stone spaces. The result contrasts with a counter-example (Theorem 1.1) that will be established later using homological techniques. In Subsec. 4.1, we will use this result to separate two more notions in Fig. 1.

Proposition 3.8. Every left-c.e. Stone space is homeomorphic to a computably compact computable Polish space.

Proof. It is sufficient to argue that the dual Boolean algebra admits a computable copy. Note that a finite collection of basic closed balls does not cover the space if, and only if, there is a special point x whose distance to the centers of the balls is greater than the radii of the respective balls. This is naturally a c.e. property, and therefore $0^{\prime }$ can list all finite closed covers of a compact left-c.e. space. The metric is also evidently $0^{\prime }$-computable. It follows from the aforementioned result from [16] relativized to $0^{\prime }$ that we can $0^{\prime }$-effectively reconstruct the dual Boolean algebra. We claim that this Boolean algebra in fact has a computable presentation.

It is well known that a ${\mathrm{\Delta }}_2^0$-Boolean algebra with a ${\mathrm{\Delta }}_2^0$ set of atoms has a computable presentation [23]. The elements of the Boolean algebra associated with the given Stone space S are represented by clopen sets. Each clopen set (and its complement) is in turn represented by finitely many basic open (or basic closed if necessary) balls. In other words, each such clopen set is given by its finite (open or closed) name. To see whether a clopen component C is an isolated point, we use $0^{\prime }$ to calculate the finite name of its clopen complement $S\setminus C$. If $S\setminus C$ is the union of $B_0,\dots ,B_k$, then let $x_0,\dots ,x_k$ be the centers of these balls, and $r_0,\dots ,r_k$ be their rational radii. There is also a rational $\delta >0$ such that a point y is at distance $>\delta$ from all $x_0,\dots ,x_k$ if, and only if, $y\in C$. These finitely many parameters and such a $\delta$ can be computed using $0^{\prime }$ (relative to which the space becomes computably compact).

If C has more than one point then it does not correspond to an atom. In this case it must also contain more than one special point. We therefore need to check whether there exist special points $z_0$ and $z_1$ such that

where the parameters $x_i$, $i=0,\dots ,k$ and the rational $\delta$ are already given to us by $0^{\prime }$ as a finite parameter. Since the metric is left-c.e., the property above is uniformly ${\mathrm{\Sigma }}_1^0$ in these parameters, making the atom relation ${\mathrm{\Delta }}_2^0$ in the ${\mathrm{\Delta }}_2^0$ Boolean algebra of clopen sets. □

4. Cohomology, Spheres, and a Bad Computable Topological Space

In this section, we describe the basic definability techniques which, combined with the methods described in the previous section, will be used in the proofs of our first main result.

Our definability methods rely on Čech cohomology of a compact space that is defined using nerves of covers. We cite [40] for the formal details and the lengthy definitions. Since we will not actually compute any cohomology directly, we shall omit these tedious details. It is well known that the Čech cohomology of a space homeomorphic to a finite simplicial complex is actually the same as the usual simplical cohomology calculated for the complex. For instance, for the n-sphere we have:

Recall that a (discrete, countable) group is c.e. presented if it is isomorphic to the factor of a computable free group by its c.e. normal subgroup. The following result is quite recent and is due to Lupini, Melnikov and Nies [31]; see also [10] for an alternate proof.

Theorem 4.1. Suppose C is a computably compact Polish space. Then the Čech cohomology groups of the space are uniformly c.e. presented.

Corollary 4.2 (Essentially [10]). Suppose a computable Polish space C is homeomorphic to $S^n$for some n. Then $0^{\prime \prime }$can uniformly compute the parameter n.

Proof. Since the Čech cohomology groups are uniformly ${\mathrm{\Sigma }}_2^0$-presentable (by Theorem 4.1 relativized to $0^{\prime }$), in this case $M\cong S^k$ is equivalent to saying that ${Ȟ}^k(M)$ contains at least one non-zero element, which is a ${\mathrm{\Sigma }}_3^0$ property since the equality in the group is ${\mathrm{\Sigma }}_2^0$. It follows that $0^{\prime \prime }$ can list k such that the kth cohomology group of the space is non-trivial. □

Fact 4.3. Suppose M is a right-c.e. presented Polish space. Then $0^{(4)}$ can list n such that M has a clopen component homeomorphic to $S^n$.

Proof. If M was computable Polish then the upper bound would be given by Corollary 4.2, Lemma 3.6, and Remark 3.7; specifically, ${\mathrm{\Sigma }}_4^0$. Since a right-c.e. space is naturally ${\mathrm{\Delta }}_2^0$, we obtain the bound ${\mathrm{\Sigma }}_5^0$ (which we suspect is sharp). □

We can use a relatively simple construction based on n-spheres to establish the following result stated in the introduction. Recall the definition of a computable topological space (Definition 2.10).

Theorem 4.4. There is a Polish space S such that S admits a computable topological presentation but does not have a right-c.e. Polish presentation. Furthermore, S has a $0^{\prime \prime \prime }$-computable Polish presentation.

As noted in the introduction, the elementary construction of S entails that there is no upper bound on X that would guarantee that S has an X-computable Polish presentation. Indeed, more work is needed to establish the $0^{\prime \prime \prime }$lower bound which we suspect is not sharp. We leave the following open.

Question 4.5. Is there a computable topological space that does not have a right-c.e. Polish presentation, but admits a $0^{\prime }$-computable Polish presentation?

Proof of Theorem 4.4. We encode an arbitrary set $X\subseteq \mathbb{N}$ into a Polish space $S_X$ so that $S_X$ admits a computable topological presentation ${𝒯}$ that is independent of the choice of X. Fix a set $X\subseteq \mathbb{N}$. As before, $S^n$ denotes the Euclidean n-sphere. For every n, define

Let $S_X$ be the disjoint union of its clopen components $C_n$. The space is evidently locally compact Polish. Furthermore, every connected compact open component of the space has the form $S^n$ for some n.

We assume $n>0$ throughout. Recall that ${ℝ}^n{\cong }_{hom}{S}^n\setminus \{p\}$, where p is any point on the sphere. The idea behind the lemma below is that point-free topological presentation cannot possibly know whether p is in or out. □

Lemma 4.6. For every $n>0$, ${ℝ}^n$and $S^n$share the same computable topological presentation ${{𝒯}}_n$that can be produced uniformly in n.

Proof. Uniformly in n, fix a computable Polish presentation of $S^n$. Fix the associated computable topological presentation ${{𝒯}}_n$ given by the balls with rational radii and centered in computable points. Note that this remains a computable topological presentation if we extract one of the special points from the space. □

Let ${𝒯}$ be the union of the ${{𝒯}}_n$ over $n\in \mathbb{N}$. When two open sets come from different ${{𝒯}}_n$ and ${{𝒯}}_m$, $m\ne n$, we declare their intersection to be empty. This gives a computable topological presentation of the space $S_X$, and this presentation does not depend on X. If we do not care about the lower $0^{\prime \prime \prime }$-bound, it remains to note that $X\ne Y$ implies $S_X{\ncong }_{\mathrm{\text{hom}}}{S}_Y$. Since there are uncountably many subsets of $\mathbb{N}$ and only countably many right-c.e. presentations, the theorem follows.

To produce an example that is $0^{\prime \prime \prime }$-computably completely metrizable, we also adjoin infinitely many isolated points to the space, and we also duplicate every n-sphere infinitely many times. The claim below is obvious.

Claim 4.7. Suppose Y is ${\mathrm{\Pi }}_2^0$. There is a uniform procedure which outputs a computable Polish copy of $S^n$if $y\in Y$, and outputs finitely many isolated points, otherwise.

We now fix some X that is in ${\mathrm{\Sigma }}_6^0\setminus {\mathrm{\Sigma }}_5^0$ and view it as a ${\mathrm{\Sigma }}_3^{0^{\prime \prime \prime }}$ set. We further split the ${\mathrm{\Sigma }}_3^{0^{\prime \prime \prime }}$-predicate into infinitely many ${\mathrm{\Pi }}_2^{0^{\prime \prime \prime }}$-predicates, one for each potential existential witness, and relativize the claim above to $0^{\prime \prime \prime }$. This way we obtain a $0^{\prime \prime \prime }$-computable copy of the space $S_X$ which, by Fact 4, cannot have a right-c.e. presentation.

4.1. Separating more notions in Fig. 1

It follows from the proof of Theorem 4.4 that up to homeomorphism, “computable topological” does not imply “left-c.e. Polish” (nor even “arithmetical Polish” and beyond). In Proposition 3.8 we also proved that “left-c.e. Polish” $\leftrightarrow$ “computable Polish” for Stone spaces, and thus “right-c.e. Polish” does not imply “left-c.e. Polish” by a result from [3] which establishes that “computable Polish” is stronger than “right-c.e. Polish” among Stone spaces. We do not know whether “left-c.e. Polish” implies “right-c.e. Polish”. However, it seems highly unlikely that this potential implication holds true even for compact spaces.

5. A Left-c.e. Space not Homeomorphic to a Computable One

It is known that there exist a right-c.e.  Stone space not homeomorphic to any computable Polish space, but we have seen in Proposition 3.8 that every left-c.e. Stone space has a computable presentation (indeed, a computably compact one). We prove Theorem 1.1 that states that there exists a left-c.e. Polish space not homeomorphic to any computable Polish space.

Proof of Theorem 1.1. For a set $X\subseteq \omega$, let $C(X)$ be the one-point compactification of the disjoint union of n-spheres $S^n$ and n-discs $D_n\cong {[0,1]}^n$, with infinitely many copies for each $n\in X$. The proposition below is reminiscent of the similar coding results from [10, 48]. We will need only the ‘if’ part of it, but we state it in full generality. □

Proposition 5.1. X is ${\mathrm{\Sigma }}_3^0$if, and only if, $C(X)$is homeomorphic to a computable Polish space.

Proof. The “if” part is based on calculating the cohomology of connected compact open components. Note that the cohomologies $H^i(D_n,\mathbb{Z})$ of $D_n$ are trivial when $i>0$ (folklore). Thus, Corollary 4.2 combined with the proof of Lemma 3.6 which (as noted in Remark 3.7) gives the upper bound ${\mathrm{\Sigma }}_3^0$.

For the other implication (that we only sketch since we do not really need it) note that the spaces $D_n$ are evidently uniformly computable. The construction from the proof of [10, Proposition 4.42] can be easily extended to incorporate these spaces into $C(X)$ while running the construction of $CP(X)$ (in the notation of [10]) on the other components. □

Define $L_X$ to be the space consisting of infinitely many compact open components, one of which is $C(X)$ (see Proposition 5.1), and the rest are isolated points. We will need only the “if” part of the lemma below, but we state it in full.

Lemma 5.2. X is ${\mathrm{\Sigma }}_3^0$if, and only if, $L_X$has a computable Polish copy.

Proof. Suppose $L_X$ has a computable Polish presentation. Fix finitely many open basic balls isolating the component $C(X)$ from the rest of the space. Define the subspace of $L_X$ by listing the special points contained in these finitely many balls. This gives a computable Polish presentation of $C(X)$; it remains to apply Proposition 5.1.

On the other hand, by Proposition 5.1 if X is ${\mathrm{\Sigma }}_3^0$ then we can produce a computable Polish presentation of $C(X)$. It is easy to extend it to a computable presentation of $L_X$ by adjoining infinitely many points and declaring them to be at distance (say) 1 between each other and the component homeomorphic to $C(X)$. □

Fix a ${\mathrm{\Pi }}_3^0$-complete X. By the lemma above, to prove the theorem it is sufficient to argue that $L_X$ has a left-c.e. presentation.

Lemma 5.3. There is a uniform procedure which, given $n>0$, produces a left-c.e. space U(n) of the form:

where ${\tilde{S}}^n$is the disjoint union of the n-sphere $S^n$and infinitely many isolated points (with no limit point), and ${\tilde{D}}^n$is the disjoint union of the n-disc $D_n\cong {[0,1]}^n$and infinitely many isolated points (with no limit point).

Proof. We begin our construction with the standard computable and computably compact presentation of $S^n$. We also begin with a sequence of isolated points disjoint from $S^n$ so that they have no accumulation point.

Fix a special $p\in S^n$. We represent $S^n\setminus \{p\}$ as the union of a nested uniformly computable sequence of subspaces

where each $D(i)$ is homeomorphic to $D^n$, and the boundaries of $D(i)$ approach the point p in the limit.

We also fix a ${\mathrm{\Pi }}_3^0$ predicate $P(n)$ for X. We represent it via $\forall x{\exists }^{<\infty }yR(x,y,n)$, where R is a computable predicate. We say that the predicate “toggles” on x at stage s if at the stage we discover one more $y_0$ such that $R(x,y_0,n)$ holds.

The construction of $U(n)$ proceeds as follows. We shall begin with approximating $S^n$ naturally, but we exclude the special point (the “pole”) p from its presentation. This is done by putting more and more special points into more and more of the nested discs $D(i)$. If the predicate never toggles for any x then we will end up with $S^n$ in which p is put as a limit point. We also will gradually add more and more isolated points outside $S^n$. We can use an ultra-metric between all clopen components to ensure that the triangle inequality holds, or we can opt to work within a copy of ${ℝ}^{n+1}$ and during the construction “move” the points by redefining their interpretation in ${ℝ}^{n+1}$; the exact set-up does not matter since we are working with spaces up to homeomorphism.

If at some stage the predicate toggles on some x, then assume x is least such. Without loss of generality, we can assume $x>0$. We then take the finitely many points that have been introduced so far into $D(k)\setminus D(x)$, $k>x$, and we “move these points away” from the component, as follows. Recall that the metric has to be merely left-c.e. Declare that the distance from these points to any other point in the construction is much larger than any number seen so far in the construction. We then return to the natural approximation of the nested discs and wait for the predicate to toggle again (if ever), etc.

If the ${\mathrm{\Pi }}_3^0$ predicate holds on n, then we eventually end up with a stable disc $D(k)$ for every k, and thus will end up with a sphere. Otherwise, for some x all discs $D(k)$ for $k>x$ will be “blown away” infinitely many times. Since we assumed that $x>0$, we will end up with $D(x)\cong D^n$. In both cases, we will also have infinitely many isolated points with no accumulation point.

The space is evidently left-c.e., by construction. This is because the distances between points can only potentially increase, making the left cut of $d(\alpha ,\beta )$ c.e. for any special points $\alpha$ and $\beta$ of the space. □

We return to the proof of the theorem. Recall the definition of $L_X$, and recall that X is ${\mathrm{\Pi }}_3^0$.

Lemma 5.4. The space $L_X$has a left-c.e. presentation.

Proof. We iterate (the proof of) Lemma 5.3. We combine the constructions described in the proof of Lemma 5.3 inside a copy of $C(X)$. We associate one compact open component of the space with each n, and we also initially have infinitely many compact open components, infinitely many for each n-disc $D^n$. When we move points away according to the instructions of the main diagonalization module in the proof of Lemma 5.3, we also move it away from all points in the whole construction introduced so far, not only from the points that are listed in our specific component working with n. The rest is repeated verbatim. In particular, we will end up with infinitely many isolated points with no limit point, the resulting space is left-c.e., and it is homeomorphic to $L_X$. □

Theorem 1.1 now follows from Lemmas 5.4 and 5.2.

6. Totally Disconnected Locally Compact Groups

Recall that Theorem 1.2 states that, for a separable tdlc group, Definitions 2.16 and 2.19 are equivalent, up to topological group-isomorphism. Our result implies the earlier result [10, Theorem 4.35] that works only in the special case of a profinite group.

Proof of Theorem 1.2. We will need the following auxiliary definition. □

Definition 6.1. A separable tdlc group G computably splits if the underlying space can be represented as a disjoint union of uniformly computably compact and uniformly c.e. open sets $G={\bigcup }_i{C}_i$, such that, for every n and i, we can uniformly compute a $2^{-n}$ cover whose union is equal to $C_i$.

Suppose G is computable tdlc, so $G=[T]$ for a computably compact T. The desired $C_i$ are induced by the compact open sets associated by the compact subtrees of T. Recall that the latter can be computably listed. It follows that any computable tdlc group computably splits, and thus it is computably locally compact.

Now suppose G is computably locally compact.

Lemma 6.2. G computably splits.

Proof. By the well-known van Dantzig’s theorem, there is a compact open subgroup H of G (which is however not necessarily normal). Every point in H is contained in a basic open B which is itself included in a compact $K\subseteq G$.

By Proposition 2.15, every point of the compact open H is contained in an open B so that the respective closed basic ball $B^c$ is computably compact. Since H is open, there are finitely many such B that cover the whole H. Since H is also closed, and since we can (non-uniformly) assume the radii of the balls are smaller than the distance from H to $G\setminus H$, we can assume that H is also equal to the union of finitely many closed balls $B^c$, each of which is computable compact. By slightly increasing the radii of the balls (using the distance to the complement again), we can also produce the finite open name of H.

In summary, we have produced both a finite open and a finite computable compact name of H. The latter evidently implies that H is computably compact.

For any special point $\xi$, the left translation operation $x\to \xi x$ is both computable and effectively open. (The latter holds because ${\xi }^{-1}$ is evidently a computable point, and the left-translation by ${\xi }^{-1}$ is the inverse of the left translation by $\xi$.)

Since the left cosets of H are open, each such coset contains a special point. In other words, all H-cosets have the form $\xi H$ for some special $\xi$. Since the computable image of a computably compact set is computably compact, all these cosets are computably compact with all possible uniformity. Further, the image of any finite cover of H under the effectively open map $x\to \xi x$ gives an open cover of $\xi H$. Since $\xi H$ is (uniformly) computably compact, we can get a finite subcover of this cover. Fixing one such finite cover (uniformly), we can conclude that $\xi H$ is equal to the union of this cover. Since $\xi H$ is (uniformly) computably compact, we can search for covers that (formally) refine this cover. The union of any such cover will also be equal to the whole coset $\xi H$.

It remains to remove repetitions from the sequence of cosets defined above. This is done as follows. Non-uniformly fix a rational $\delta$ that bounds the distance between H and $G\setminus H$ from below. To see whether $\xi H\cap \zeta H=\varnothing$, calculate the distance from the computably compact H to the computable point ${\zeta }^{-1}\xi$ to precision $\delta /4$. If this approximation is $>\delta /2$ then $\xi H\cap \zeta H=\varnothing$, and if $<\delta /2$ then $\xi H=\zeta H$; note these are exclusive cases.

In summary, we can list the compact open cosets without repetition in the nicest possible way. In particular, the group computably splits into these cosets. This gives us the lemma. □

Suppose our tdlc G computably splits into uniformly compact open $(D_i)$. For instance, these $D_i$ could be the cosets by a compact open subgroup; but this assumption is not really necessary below. Let $C_i={\bigcup }_{j<i}{D}_i$.

Observe that each $C_i$ is a computably compact Stone space. By Theorem 3.1, there is a uniformly computable procedure that, given a computably compact Stone space $C_i$, outputs a computably branching, computable tree $T_i$ with no dead ends such that $C_i{\cong }_{\mathrm{\text{comp}}}[T_i]$.

Observe also that, for every i, $C_i$ is computable clopen subset of $C_{i+1}$. Its complement in $C_{i+1}$ is also computable compact open; this follows from the proof of Lemma 3.2 with all possible uniformity. (List open finite covers of $C_i$ and search for a cover of the whole $C_{i+1}$ that is composed of the cover of $C_i$ and finitely many balls formally disjoint from it.) We are therefore in the position to apply Remark 3.5.

We see that the tree $T_i$ that can be uniformly produced for $C_i$ (by Theorem 3.1) can be viewed as a subtree of $T_{i+1}$ corresponding to $C_{i+1}$; this is Remark 3.5. It follows that we can define T to be ${\bigcup }_{i\in \omega }{T}_i$. By Remark 3.4 the original metric on $C_i$ is uniformly effectively compatible with the new ultrametric induced by the tree $T_i$. It follows that the group operations remain computable and effectively open on $[T]$. Since $T_i$ were (uniformly) computably branching, T satisfies the conditions of computable tdlc presentation.

Acknowledgments

K. M. Ng was supported by the Ministry of Education, Singapore, under its Academic Research Fund Tier 1 (RG23/19). This work was also partially supported by Rutherford Discovery Fellowship (Wellington) RDF-MAU1905, Royal Society Te Aparangi.

ORCID

Alexander G. Melnikov  https://orcid.org/0000-0001-8781-7432

Keng Meng Ng  https://orcid.org/0000-0002-7113-0596

Notes

^a It appears that the notions in the cited papers, though very similar to each other and to our Definition 2.14, could potentially be non-equivalent (up to homeomorphism) for computable Polish spaces. The differences are subtle, so we leave this as an open problem.