Proof Assume that X has a ${\mathbf {d}}$ -computable Polish presentation $(X,d,S)$ . By compactness of X, one can observe that E is a code of a finite rational open cover of X if and only if there exists $s\in {\mathbb {N}}$ such that for all $x\in X$ we have $d(x,s_i)\leq r-2^{-s}$ for some $(i,r)\in E$ . The latter is equivalent to the existence of $s\in {\mathbb {N}}$ such that for all $j\in {\mathbb {N}}$ we have $d(s_j,s_i)\leq r-2^{-s}$ for some $(i,r)\in E$ . As E is finite, this is a $\Sigma ^0_2$ condition relative to ${\mathbf {d}}$ , so it is ${\mathbf {d}}'$ -c.e. In other words, X has a $\mathbf {d}'$ -computable compact presentation.

Proof The result is straightforward for finite disjoint unions and wedge sums, because the sets $\{0\}\times X$ , $\{1\}\times Y$ , $X\times \{\overline {0}\}$ and $\{\overline {0}\}\times Y$ easily inherit the computability properties of X and Y, and so do their unions.

Let us consider the one-point compactification of the disjoint union. The function $f_n:Q\to Q$ sending $x=(x_0,x_1,\ldots )$ to $(0,\ldots ,0,1,x_0,x_1,\ldots )$ , starting with n occurrences of $0$ , is computable uniformly in n. Equivalently, the preimages of rational balls by $f_n$ are effectively open, uniformly in n.

Assume that $X_n$ are uniformly ${\mathbf {d}}$ -computably overt. A rational open ball B intersects the set $\alpha _0(\coprod _n X_n)$ iff $f_n^{-1}(B)$ intersects $X_n$ for some n, which is ${\mathbf {d}}$ -c.e.

Now assume that $X_n$ are uniformly ${\mathbf {d}}$ -computably compact. A rational open set U contains $\alpha _0(\coprod _nX_n)$ iff there exists n such that $\{0\}^n\times Q\subseteq U$ and $X_i\subseteq f_i^{-1}(U)$ for all $i<n$ , which is ${\mathbf {d}}$ -c.e.

Proof For $s\in \mathbb {N}$ let $X_A[s]=X_s$ if $A\cap [0,s]$ is empty, and $X_A[s]=X_n$ where $n=\min (A\cap [0,s])$ otherwise. The sequence $(X_A[s])_{s\in \mathbb {N}}$ can be computed from A and satisfies $d_H(X_A[s],X_A)<2^{-s+1}$ , so $X_A$ is computably compact relative to A.

We show that a rational ball B intersects $X_A$ if and only if there exists $n\in \mathbb {N}$ such that $[0,n-1]\cap A=\emptyset $ and B intersects $X_n$ . This condition is c.e. relative to any enumeration of $\mathbb {N}\setminus A$ . If $[0,n-1]\cap A=\emptyset $ and B intersects $X_n$ , then $X_A$ contains $X_n$ , so B intersects $X_A$ . Conversely, if B intersects $X_A$ , then either $A=\emptyset $ and any sufficiently large n satisfies the conditions, or $A\neq \emptyset $ and $n=\min A$ satisfies the conditions.

Proof The mesh of a finite open cover $\kern1pt\mathcal {U}=(U_i)_{i\in I}$ is the maximal diameter of the $U_i$ ’s. We first show that there are good open covers of arbitrarily small meshes, and that if $\kern1pt\mathcal {U}$ is a finite open cover of X then there exists $\epsilon>0$ such that every finite cover of mesh $<\epsilon $ strongly refines $\kern1pt\mathcal {U}$ .

Let $\epsilon>0$ and $(B(s,\epsilon ))_{s\in I}$ be a rational open cover of X, where I is finite. By compactness, let $\delta <\epsilon $ be such that $(B(s,\delta ))_{s\in I}$ is still a cover of X. There are only finitely many values of $r\in [\delta ,\epsilon ]$ such that $(B(s,r))_{r\in I}$ is not a good cover; indeed, these values are $\min _{x\in X}\max _{s\in J}d(x,s)$ , for $J\subseteq I$ ; indeed, when the cover is not good there exists $J\subseteq I$ and a point x at distance $\leq r$ from every $s\in J$ , but no point y at distance $<r$ from every $s\in J$ , so $\max _{s\in J}d(x,s)=r$ and x minimizes this quantity. Therefore, there exists a rational number $r\in [\delta ,\epsilon ]$ avoiding this finite set of values, providing a good open cover of mesh $<2\epsilon $ .

Let $\kern1pt\mathcal {U}$ be a finite open cover of X. By compactness, $\kern1pt\mathcal {U}$ has a Lebesgue number $\delta>0$ , which means that any set of diameter ${\leq} \delta $ is contained in some member of U. If $\mathcal {V}=(V_i)_{i\in J}$ is a good cover of mesh ${\leq} \delta $ , then each $\overline {V_i}$ has diameter ${\leq} \delta $ , so $\mathcal {V}$ strongly refines $\kern1pt\mathcal {U}$ .

Now we are given a compact presentation of X as oracle. Whether a finite rational cover is good is $\Sigma ^0_1$ , and whether it strongly refines another rational cover is $\Sigma ^0_1$ , and whether its mesh is ${<}q$ is $\Sigma ^0_1$ . Therefore, we start with searching for some good open cover $\kern1pt\mathcal {U}_0$ of mesh ${<}1$ and inductively look for a good open cover $\kern1pt\mathcal {U}_{s+1}$ of mesh ${<}2^{-s}$ strongly refining $\kern1pt\mathcal {U}_s$ . These objects exist as proved above, and can be effectively found by exhaustive search.

Proof Assume that a compact presentation is given as oracle. One can compute an enumeration $(U_i,V_i)_{i\in \mathbb {N}}$ of all the pairs of rational open sets satisfying $X=U_i\cup V_i=X$ and $\overline {U}_i\cap \overline {V}_i=\emptyset $ , because these conditions are c.e. relative to a compact presentation of X. Let then $C_i=U_i$ for each i. One can then easily compute the Boolean operations: given i, one can compute j such that $(U_j,V_j)=(V_i,U_i)$ , so $C_j=X\setminus C_i$ ; given $i,j$ , one can compute k such that $(U_k,V_k)=(U_i\cap U_j,V_i\cup V_j)$ , so that $C_k=C_i\cap C_j$ , and symmetrically for the union. The set $\{i\in \mathbb {N}:C_i=\emptyset \}$ can be computed, because $C_i=\emptyset \iff X\subseteq V_i\iff U_i=\emptyset $ , which is both c.e. and co-c.e. relative to a compact presentation. Therefore, equality and inclusion are decidable because they reduce to emptiness of some Boolean combination.

Proof We are given a compact presentation of X as oracle. As X is compact, it is routine to check that in the definition of dimension, one can assume that $\kern1pt\mathcal {U}$ and $\mathcal {V}$ are good covers and that $\mathcal {V}$ strictly refines $\kern1pt\mathcal {U}$ . Therefore, $\dim X\leq n$ iff for every good cover $\kern1pt\mathcal {U}$ , there exists a good cover $\mathcal {V}$ that strongly refines $\kern1pt\mathcal {U}$ , and such that for all $V_0,\ldots ,V_n\in \mathcal {V}$ , one has $\overline {V}_0\cap \cdots \cap \overline {V}_n=\emptyset $ . This is a $\Pi ^0_2$ predicate, because one can computable enumerate the good covers of X, and the strong refinements of a given good cover.

Proof We proceed as in the proof of Lemma 2.5, but when searching for a good cover $\kern1pt\mathcal {U}_{s+1}$ that strongly refines $\kern1pt\mathcal {U}_s$ , we additionally test whether $\kern1pt\mathcal {U}_{s+1}$ has order $n+1$ , which is also a $\Sigma ^0_1$ predicate. As $\dim (X)\leq n$ , it always exists so it can be effectively found.

Proof As X is zero-dimensional, one can compute by Proposition 2.8 a strongly refining sequence of good open covers $(\mathcal {U}_s)_{s\in \mathbb {N}}$ of order $1$ . Each $\kern1pt\mathcal {U}_s$ is therefore made of clopen sets. All these clopen sets ordered by inclusion form a finitely branching pruned tree, in which the number of nodes at each level can be computed. By standard arguments, it can be effectively converted into a binary tree.

Fact 3.2.

1. (1) A Boolean algebra has a ${\mathbf {d}}$ -c.e. $($ resp. ${\mathbf {d}}$ -co-c.e., ${\mathbf {d}}$ -computable $)$ copy if and only if it is isomorphic to the Boolean algebra of clopen subsets of $[T]$ for some ${\mathbf {d}}$ -co-c.e. $($ resp. ${\mathbf {d}}$ -c.e., ${\mathbf {d}}$ -computable $)$ pruned tree T.

2. (2) Every ${\mathbf {d}}$ -co-c.e. Boolean algebra is isomorphic to a ${\mathbf {d}}$ -computable Boolean algebra.

3. (3) There is a ${\mathbf {d}}$ -c.e. Boolean algebra which is not isomorphic to a ${\mathbf {d}}$ -computable Boolean algebra.

Proof The first item follows from [Reference Odintsov and Selivanov36, Lemma 3]; see also [Reference Selivanov41]. The second item follows from [Reference Odintsov and Selivanov36]. The third item follows from [Reference Feiner13].

Fact 3.3 (see [Reference Harrison-Trainor, Melnikov and Ng18]).

1. (1) There exists $X\in \mathbf {CP}_0$ which has a $\mathbf {0}'$ -computable Polish presentation, but no computable Polish presentation,

2. (2) If $X\in \mathbf {CP}_0$ has a low $_4$ Polish presentation, then it has a computable Polish presentation.

Proof We first show that if $\alpha $ is $\mathbf {x}$ -computable, then $\omega ^\alpha +1$ has an $\mathbf {x}$ -computable compact presentation.

Given an $\mathbf {x}$ -computable well-ordering $\preceq $ of $\mathbb {N}$ of order type $\omega ^\alpha +1$ , we build a copy X of $\omega ^\alpha +1$ in $[0,1]$ as follows. We can assume w.l.o.g. that $0$ is minimal and $1$ is maximal for $\preceq $ . We embed $(\mathbb {N},\preceq )$ in $([0,1],\leq )$ by inductively defining a rational number $x_n\in [0,1]$ for each $n\in \mathbb {N}$ . We need some care to make sure that we will obtain a topological embedding, and that the copy X will be $\mathbf {x}$ -computably compact. We start with $x_0=0$ and $x_1=1$ . Let $n\geq 2$ and assume that $x_0,\ldots ,x_{n-1}$ have been defined. Let i and j be, respectively, the predecessor and the successor of n in $(\{0,\ldots ,n\},\preceq )$ , and define $x_{n}=2^{-n}x_i+(1-2^{-n})x_j$ . Note that $x_j-x_n\leq 2^{-n}$ . Let $X=\{x_n:n\in \mathbb {N}\}$ with the topology inherited from $\mathbb {R}$ .

The function $n\mapsto x_n$ is by construction an order embedding of $(\mathbb {N},\preceq )$ in $([0,1], \leq)$ . We need to show that it is a topological embedding, i.e., that it is continuous. It is sufficient to check that if $n=\sup _\preceq \{m:m\prec n\}$ , then $x_n=\sup _\leq \{x_m:m\prec n\}$ . There exist infinitely many m’s such that $m\geq n$ , $m\prec n$ and m is the predecessor of n in $(\{0,\ldots ,m\},\preceq )$ . When defining $x_m$ for any such m, the successor of m is $j=n$ , so $x_n-x_m\leq 2^{-m}$ , which is arbitrarily small, so $x_n=\sup _\leq \{m:m\prec n\}$ as wanted.

Therefore, the set $X=\{x_n:n\in \mathbb {N}\}$ is a copy of $\omega ^\alpha +1$ . The sequence $(x_n)_{n\in \mathbb {N}}$ is an $\mathbf {x}$ -computable sequence of rational numbers. Let $X_n=\{x_0,\ldots ,x_n\}\subseteq X$ and observe by construction that $d_H(X_n,X_{n-1})\leq 2^{-n}$ , so $d_H(X_n,X)\leq 2^{-n}$ . As the compact sets $X_n$ are uniformly $\mathbf {x}$ -computable and converge fast to X, X is $\mathbf {x}$ -computable as well.

Conversely, if $\omega ^\alpha +1$ has an $\mathbf {x}$ -computable Polish presentation, then by Lemma 2.1, it has an $\mathbf {x}'$ -computable compact presentation. In particular, there is a countable $\Pi ^0_1(\mathbf {x}')$ class $P\subseteq 2^\omega $ which is homeomorphic to $\omega ^\alpha +1$ . Since the Cantor–Bendixson rank of $\omega ^\alpha +1$ is $\alpha $ , and the Cantor–Bendixson rank is a topological invariant, the rank of P is also $\alpha $ . However, as noted by Kreisel, the Spector boundedness principle implies that the rank of a countable $\Pi ^0_1(\mathbf {x}')$ class must be $\mathbf {x}'$ -computable; see also [Reference Cenzer7, Section 4]. As an $\mathbf {x}$ -hyperarithmetic ordinal is always $\mathbf {x}$ -computable, this implies that $\alpha <\omega _1^{\mathbf {x}}$ .

Proof Let G be the inverse limit. We claim that G is non-trivial if and only if there exist $n\in {\mathbb {N}}$ and $g\in G_n$ such that $g\neq 0$ and $g\in {\mathrm {im}}(f_n\circ \ldots \circ f_p)$ for all $p\geq n$ . This predicate is $\Sigma ^0_2$ , because the groups are finite. In particular, the predicate $g\in {\mathrm {im}}(f_n\circ \ldots \circ f_p)$ can be decided in finite time, by testing $f_n\circ \ldots \circ f_p(g')=g$ for each $g'$ in the finite set $G_{p+1}$ .

If G is non-trivial, then let $(g_n)_{n\in {\mathbb {N}}}$ be a non-zero element of G. As it is non-zero, there exists n such that $g_n\neq 0$ . Moreover, for every $p\geq n$ , $g_n=f_n\circ \ldots \circ f_p(g_{p+1})$ belongs to ${\mathrm {im}}(f_n\circ \ldots \circ f_p)$ .

Conversely, assume the existence of n and g satisfying the conditions. As the groups are finite, by König’s lemma, there exists a sequence $(g_p)_{p\geq n}$ such that $g_n=g$ and $g_p=f_p(g_{p+1})$ for all $p\geq n$ . For $m<n$ , let $g_m=f_m\circ \ldots \circ f_{n-1}(g)$ . The sequence $(g_n)_{n\in {\mathbb {N}}}$ is an element of G, and is non-zero as its nth coordinate is $g\neq 0$ .

Proof Given a compact presentation of X and a good open cover ${\mathcal {U}}=(U_0,\ldots ,U_k)$ of X, its nerve $K_{\mathcal {U}}$ on the vertices $V=\{0,\ldots ,k\}$ can be computed, in the sense that one can decide whether a set $J\subseteq V$ belongs to $K_{\mathcal {U}}$ . Indeed, $J\in K_{\mathcal {U}}$ iff $\bigcap _{j\in J}U_j\neq \emptyset $ iff $\bigcap _{j\in J}\overline {U}_j\neq \emptyset $ . The first inequality is $\Sigma ^0_1$ and the second inequality is $\Pi ^0_1$ , so it is decidable.

If ${\mathcal {U}}=(U_0,\ldots ,U_k)$ and ${\mathcal {V}}=(V_0,\ldots ,V_l)$ are good open covers of X and ${\mathcal {U}}$ strongly refines ${\mathcal {V}}$ , then one can compute a simplicial map $f:K_{\mathcal {U}}\to K_{\mathcal {V}}$ sending each vertex $u_i$ for $K_{\mathcal {U}}$ to a vertex $v_j$ of $K_{\mathcal {V}}$ such that $\overline {U}_i\subseteq V_j$ . Indeed, the latter inclusion is $\Sigma ^0_1$ , so for each i one can effectively find a suitable j.

Now, from a compact presentation of X, one can compute a strong refining sequence of good open covers $({\mathcal {U}}_s)_{s\in {\mathbb {N}}}$ by Lemma 2.5. One can then compute the nerves $K_s$ of ${\mathcal {U}}_s$ as well as simplicial maps $f_s:K_{s+1}\to K_s$ . One can compute the simplicial homology groups $H_n(K_s)$ and the homomorphisms $f_{s,*}:H_n(K_{s+1};{{\mathbb {Z}}_2})\to H_n(K_s;{{\mathbb {Z}}_2})$ . Their inverse limit is $\check {H}_n(X;{{\mathbb {Z}}_2})$ , and whether it is non-trivial is $\Sigma ^0_2$ by Proposition 4.6.

Proof The arguments in [Reference Melnikov32, Reference McNicholl and Stull29, Reference Downey and Melnikov9] imply the computability of the inverse system of simplicial groups $(H_n(K_s;{\mathbb {Z}}),f_{s,*})$ : these groups are strongly completely decomposable (strictly speaking, their results are about cohomology groups $H^n(K_s)$ but apply equally to the homology groups $H_n(K_s;{\mathbb {Z}})$ ). Therefore, their inverse limit is non-trivial if and only if there exists a sequence $(x_s)_{s\in {\mathbb {N}}}$ with $x_s\in H_n(K_s;{\mathbb {Z}})$ , $x_{s}=f_{s,*}(x_{s+1})$ for all s and $x_s\neq 0$ for some s. This condition is $\Sigma ^1_1$ . We now show the completeness of the problem.

The set of trees $T\subseteq 2^{<\omega }$ containing an infinite path with infinitely many $1$ ’s is $\Sigma ^1_1$ -complete [Reference Kechris26, Proposition 25.2]. We will reduce this problem to the non-triviliaty of $\check {H}_1(X;{\mathbb {Z}})$ , and explain the changes to be made for higher-dimensional homology groups. We will build an inverse system of groups and then build an inverse limit of compact spaces whose Čech homology group isthe inverse limit of the groups. Note the similarity of this strategy with [Reference Melnikov32] which builds an inverse limit of compact spaces whose first Čech cohomology group is a given direct limit ofgroups.

We first define an inverse system of groups $(G_n,f_n)$ , i.e. a sequence $(G_n)_{n\in {\mathbb {N}}}$ of groups together with homomorphisms $f_n:G_{n+1}\to G_n$ . We will then associate to each tree T a subsystem $(L_n,f_n)$ , i.e. a sequence of subgroups $L_n\subseteq G_n$ satisfying $f_n(L_{n+1})\subseteq L_n$ .

Let $\epsilon \in 2^{<\omega }$ be the empty string, $S=\{\epsilon \}\cup \{1w:w\in 2^{<\omega }\}$ be the set of strings that do not start with $0$ and $S_n=\{w\in S:|w|=n\}$ . For each $w\in S$ , let $k(w)=2^{|w|_1}$ where $|w|_1$ is the number of occurrences of $1$ in w. Note that $k(\epsilon )=1$ .

For $n\in {\mathbb {N}}$ , we define

$$ \begin{align*} G_n=\bigoplus_{w\in S_n}{\mathbb{Z}}^{k(w)}. \end{align*} $$

Note that $G_0={\mathbb {Z}}$ and $G_1={\mathbb {Z}}^2$ . We call each ${\mathbb {Z}}^{k(w)}$ a component of $G_n$ . If $n\geq 1$ and $w\in S_n$ , then $|w|_1\geq 1$ so $k(w)$ is even: we will implicitly split each component ${\mathbb {Z}}^{k(w)}$ into ${\mathbb {Z}}^{k(w)/2}\oplus {\mathbb {Z}}^{k(w)/2}$ , expressing an element of ${\mathbb {Z}}^{k(w)}$ as a pair.

We define $f_n:G_{n+1}\to G_n$ on each component of $G_{n+1}$ . For each $w\in S_n$ , one has $k(w0)=k(w)$ and $k(w1)=2k(w)$ and we let

$$ \begin{align*} f_n:{\mathbb{Z}}^{k(w0)}&\to {\mathbb{Z}}^{k(w)}\\ (x,y)&\mapsto (2x,3y) \end{align*} $$

and

$$ \begin{align*} f_n:{\mathbb{Z}}^{k(w1)}&\to{\mathbb{Z}}^{k(w)}\\ (x,y)&\mapsto x+y. \end{align*} $$

An element $x\in \varprojlim (G_n,f_n)$ is described as a family $(x(w))_{w\in S}$ where $x(w)\in {\mathbb {Z}}^{k(w)}$ for each $w\in S$ , such that $x(w)=f_{|w|}(x(w0))+f_{|w|}(x(w1))$ . We define the support of x as $\mathrm {supp}(x)=\{w\in S:x(w)\neq 0\}$ . Note that $x=0$ if and only if $\mathrm {supp}(x)=S$ .

We relate the supports of non-zero elements with the infinite binary sequences containing infinitely many $1$ ’s. For an infinite sequence $q\in 2^\omega $ , let $q\upharpoonright_{n}$ be the prefix of q of length n.

Conversely,

Let $T\subseteq 2^{<\omega }$ be a tree. We can assume w.l.o.g. that $T\subseteq S$ , replacing T with $\{\epsilon \}\cup \{1w:x\in T\}$ if necessary. We define an inverse subsystem $(L_n,f_n)$ of $(G_n,f_n)$ . Let $T_n=\{w\in T:|w|=n\}$ and $L_n=\bigoplus _{w\in T_n}{\mathbb {Z}}^{k(w)}$ . As T is a tree, one has $f_n(L_{n+1})\subseteq L_n$ so $(L_n,f_n)$ is an inverse system which is a subsystem of $(G_n,f_n)$ . Its inverse limit consists of the elements of the inverse limit of $(G_n,f_n)$ whose support is contained in T.

Therefore, $\varprojlim (L_n,f_n)$ contains a non-zero element iff $\varprojlim (G_n,f_n)$ contains a non-zero element whose support is contained in T iff T contains an infinite path with infinitely many $1$ ’s by Claims 4 and 5.

We now define a compact space $X_T$ such that $\check {H}_1(X_T;{\mathbb {Z}})$ is isomorphic to $\varprojlim (L_n,f_n)$ . Let ${\mathbb {T}}_n={\mathbf {S}}_1^n$ be the n-dimensional torus, which is the product of n circles.

Observe that $L_n={\mathbb {Z}}^{l_n}$ for some $l_n$ . We then define a space $X_T$ as the inverse limit of $X_n={\mathbb {T}}_{l_n}$ , with continuous surjective functions $F_n:X_{n+1}\to X_n$ defined as follows. Each homomorphism $f_n:{\mathbb {Z}}^{l_{n+1}}\to {\mathbb {Z}}^{l_n}$ can be decomposed as a direct sum of the homomorphisms

$$ \begin{align*} g_2:{\mathbb{Z}}&\to {\mathbb{Z}}&g_3:{\mathbb{Z}}&\to{\mathbb{Z}}&g_+:{\mathbb{Z}}^2&\to{\mathbb{Z}}\\ x&\mapsto 2x&x&\mapsto 3x&(x,y)&\mapsto x+y. \end{align*} $$

We define $F_n$ as the corresponding product of

$$ \begin{align*} G_2:{\mathbf{S}}_1&\to{\mathbf{S}}_1&G_3:{\mathbf{S}}_1&\to{\mathbf{S}}_1&G_+:{\mathbf{S}}_1\times{\mathbf{S}}_1&\to{\mathbf{S}}_1\\ x&\mapsto 2x&x&\mapsto3x&(x,y)&\mapsto x+y, \end{align*} $$

where the circle ${\mathbf {S}}_1$ is seen as an additive group. Let then $X_T=\varprojlim (X_n,F_n)$ .

The homology group of $X_n={\mathbb {T}}_{l_n}$ is $H_1(X_n;{\mathbb {Z}})={\mathbb {Z}}^{l_n}=L_n$ and the homomorphism $F_{n,*}:H_1(X_{n+1};{\mathbb {Z}})\to H_1(X_n;{\mathbb {Z}})$ induced by $F_n$ is $f_n$ . It is a classical result that the construction of Čech homology groups of compact spaces with coefficients in ${\mathbb {Z}}$ is continuous, i.e. commutes with inverse limits:

$$ \begin{align*} \check{H}_1(\varprojlim(X_n,F_n);{\mathbb{Z}})=\varprojlim (H_1(X_n;{\mathbb{Z}}),f_n)=\varprojlim (L_n,f_n). \end{align*} $$

This result can be found in [Reference Eilenberg and Steenrod10, Theorem X.3.1, p.261], where the statement holds for coefficient groups in the class $\mathcal {G}_R$ of modules over a ring R, and ${\mathbb {Z}}$ is indeed a module over the ring ${\mathbb {Z}}$ . Therefore, $\check {H}_1(X_T;{\mathbb {Z}})=\varprojlim (L_n,f_n)$ is non-trivial if and only if T contains a path with infinitely many $1$ ’s.

We finally need to check that the construction of $X_T$ is effective in T.

Therefore, we have proved that the non-triviality of $\check {H}_1(X;{\mathbb {Z}})$ is $\Sigma ^1_1$ -complete. We can achieve the same result for $\check {H}_k(X;{\mathbb {Z}})$ for any $k\geq 1$ . Given a binary tree T, we build the same inverse system of groups $(L_n,f_n)$ , with $L_n={\mathbb {Z}}^{l_n}$ . Let ${\mathbf {S}}_k$ be the k-dimensional sphere and note that $H_k({\mathbf {S}}_k;{\mathbb {Z}})\cong {\mathbb {Z}}$ . In the previous construction, we replace the circle by ${\mathbf {S}}_k$ . However, the equality $H_k({\mathbf {S}}_k^{l_n};{\mathbb {Z}})\cong {\mathbb {Z}}^{l_n}$ only holds for $k=1$ , so we need to replace the product by the wedge sum (the previous argument would also work with the wedge sum). Let $s\in {\mathbf {S}}_k$ be a distinguished point, making $({\mathbf {S}}_k,s)$ a pointed space, and let $X_n=\bigvee _{i<l_n} ({\mathbf {S}}_k,s)$ . One has $H_k(X_n;{\mathbb {Z}})={\mathbb {Z}}^{l_n}$ [Reference Hatcher19, Corollary 2.25].

We define continuous surjective functions $F_n:X_{n+1}\to X_n$ in a similar way, by combining the following functions. Let $G_2,G_3:({\mathbf {S}}_k,s)\to ({\mathbf {S}}_k,s)$ be continuous functions of degrees $2$ and $3$ respectively, i.e. inducing the maps $g_2,g_3:H_k({\mathbf {S}}_k;{\mathbb {Z}})\to H_k({\mathbf {S}}_k;{\mathbb {Z}})$ respectively. Let $G_+:({\mathbf {S}}_k,s)\vee ({\mathbf {S}}_k,s)\to ({\mathbf {S}}_k,s)$ be defined as the identity on each copy of ${\mathbf {S}}_k$ . One has $H_k({\mathbf {S}}_k\vee {\mathbf {S}}_k)\cong H_k({\mathbf {S}}_k)\oplus H_k({\mathbf {S}}_k)\cong {\mathbb {Z}}^2$ and $G_+$ induces $g_+:{\mathbb {Z}}^2\to {\mathbb {Z}}$ . We finally define $X=\varprojlim (X_n,F_n)$ . Again by continuity of Čech homology groups, one has $\check {H}_k(X;{\mathbb {Z}})=\varprojlim (H_k(X_n;{\mathbb {Z}}),f_n)=\varprojlim (L_n,f_n)$ , which is non-trivial iff T contains a path with infinitely many $1$ ’s.

Proof We show that relative to a compact presentation of $X\cong \mathbf {S}^d$ , the predicate $X\cong \mathbf {S}^n$ is $\Sigma ^0_2$ . It implies that it is $\Delta ^0_2$ , because $X\cong \mathbf {S}^n\iff \forall m\neq n,X\ncong \mathbf {S}^m$ is $\Pi ^0_2$ , therefore $\{d\}$ is $\Delta ^0_2$ , and d can be computed in the limit.

The Čech homology groups of $\mathbf {S}^d$ (with coefficients in $\mathbb {Z}_2$ ) are

$$ \begin{align*} \check{H}_n(\mathbf{S}^d)=\begin{cases} \mathbb{Z}_2,&\text{ if}~n=d \text{or}~n=0,\\ 0,&\text{otherwise.} \end{cases} \end{align*} $$

Therefore, for $n\geq 1$ , X is homeomorphic to $\mathbf {S}^n$ iff $\check {H}_n(X)$ is non-trivial, which is $\Sigma ^0_2$ by Corollary 4.7.

Proof of Theorem 5.1

Assume that ${\mathbf {d}}$ computes a compact presentation of $\mathcal {X}_A$ . Relative to ${\mathbf {d}}$ , we compute an enumeration $(C_i)_{i\in \mathbb {N}}$ of the clopen subsets of $\mathcal {X}_A$ , by Proposition 2.6. One has $n\in A\iff \exists i,C_i$ is connected, is not a singleton, and is homeomorphic to $\mathbf {S}_{n+1}$ . When $C_i$ is connected and is not a singleton, $C_i$ is a sphere, so by Lemma 5.6 its dimension is limit-computable relative to ${\mathbf {d}}$ . Therefore, A is $\Sigma ^0_2$ relative to ${\mathbf {d}}$ . If ${\mathbf {d}}$ computes a Polish presentation of $\mathcal {X}_A$ , then ${\mathbf {d}}'$ computes a compact presentation of $\mathcal {X}_A$ , so A is $\Sigma ^0_2$ relative to ${\mathbf {d}}'$ , hence $\Sigma ^0_3$ relative to ${\mathbf {d}}$ .

We now prove the other direction. If A is $\Sigma ^0_2$ relative to ${\mathbf {d}}$ , then there is a ${\mathbf {d}}$ -computable set $B\subseteq \mathbb {N}^3$ such that $n\in A\iff \exists i\forall j,(n,i,j)\in B$ , and such that when $n\in A$ , there exists a unique i satisfying $(n,i,j)\in B$ for all j.

For each n, let $X^n_\infty $ be a canonical $(n+1)$ -sphere in Q and $X^n_j\subseteq X^n_\infty $ be an increasing sequence of finite sets at Hausdorff distance $<2^{-j}$ from $X^n_\infty $ . We can take all these sets uniformly computably compact. Let

$$ \begin{align*} Y^n_i=\begin{cases} X^n_\infty,&\text{if}~\forall j,(n,i,j)\in B,\\ X^n_j,&\text{if}~j\ \text{is minimal such that}~(n,i,j)\notin B. \end{cases} \end{align*} $$

We apply Proposition 2.4, implying that the sets $Y^n_i$ are uniformly ${\mathbf {d}}$ -computably compact. Therefore, the set $\alpha _0(\coprod _{n,i}Y^n_i\amalg \omega )$ is ${\mathbf {d}}$ -computably compact by Proposition 2.3. This set is homeomorphic to $\mathcal {X}_A$ , because all the finite sets $X^n_j$ can be seen as subsets of $\omega $ .

If A is $\Sigma ^0_3$ relative to ${\mathbf {d}}$ , then A can be presented in the same way for some ${\mathbf {d}}$ -c.e. set B, and we consider the same realization of $\mathcal {X}_A$ . Again by Proposition 2.4, the sets $Y^n_i$ are uniformly ${\mathbf {d}}$ -computably overt, and so is $\alpha _0(\coprod _{n,i}Y^n_i\amalg \omega )$ .

Proof Given the Turing degree ${\mathbf {d}}$ of a set $D\subseteq \mathbb {N}$ , let $A=\{2n:n\in D\}\cup \{2n+1:n\notin D\}$ and $\mathcal {X}_{{\mathbf {d}},k}=\mathcal {X}_{A,k+1}$ , and note that for $j\in \{k,k+1\}$ , A is $\Sigma ^0_{j+1}$ relative to $\mathbf {x}$ iff ${\mathbf {d}}\leq \mathbf {x}^{(j)}$ .