A counterexample regarding C.E. closed subsets of [0,1] under homeomorphisms

Abstract

We give an example of a computably enumerable closed subset of |$[0,1]$| that is not homeomorphic to any computably compact Polish space. This answers a question of Koh, Melnikov and Ng (2025, J. Symb. Log.).

1 Introduction

Turing machines originally operate on words or sequences over a finite alphabet. Turing computability is extended to other mathematical objects by means of naming systems or representations [18]. Different representations of the same set can give rise to different notions of computability. If the set is equipped with additional structure, it is natural to focus on representations that make the structure accessible in a computable way, e.g. make the operations of a group or the distance function of a metric space computable [9].¹ But even with this constraint, there may be different non-equivalent representations of the same structure, and some representations may make additional properties of the structure exploitable in a computable way while others do not. It is then natural to ask whether this is only a question of choosing the ‘right’ representation, or whether there are structures that intrinsically do not allow computable access to certain properties of interest (even though these properties are present).

In the concrete case, the structures we consider are compact metric spaces. If a compact metric space can be represented with computable access to the metric and to a dense sequence witnessing separability, can it also be represented in a way that, in addition, allows computable access to a witness of its compactness? To make this question rigorous, we will recall the notions of a computable Polish space and a computably compact metric space in Section 2. Both are widely studied in computable analysis; see [8] (and also [9]) for an extensive survey, further references and historical remarks. The question can be restated as: Is there a compact computable Polish space that is not homeomorphic to any computably compact metric space? Such spaces in fact exist; examples were constructed in [8, 13, 15] with proofs based on methods from algebraic topology and topological group theory. These works contribute to a recent program of separating various notions of effectivity on topological spaces; see also [3–5, 9, 12, 14, 16].

In view of the rather advanced topological methods applied in the cited works, [8; Question 4.56] asks for a more elementary construction. It is most desirable to have an example of a computably enumerable (c.e.) closed subset² of |$[0,1]^{n}$| (w.r.t. the standard representation of |$\mathbb{R}^{n}$|⁠) that is not homeomorphic to any computably compact metric space.

For every |$n \geq 1$|⁠, the article [6] gives examples of c.e. closed and co-c.e. closed subsets of |$[0,1]^{n}$| the image of which under any homeomorphism of |$\mathbb{R}^{n}$| is not computable (and hence not computably compact). For the argument in [6], it is essential that the map is a homeomorphism of all of |$\mathbb{R}^{n}$|⁠, so the argument is not suitable to construct an example as desired above.

A suitable example |$K \subseteq [0, 1]^{2}$| has recently been constructed by Koh, Melnikov and Ng [14]. The proof technique of [14], however, is not applicable in |$\mathbb{R}$|⁠. The authors thus ask for a corresponding example |$K \subseteq [0, 1]$|⁠. The purpose of the present note is to show that in fact:

Theorem 1.1.

There exists a perfect³ c.e. closed |$K \subseteq [0,1]$| that is not homeomorphic to any computably compact Polish space.

The proof uses the Feiner complexity classes, which we will review in Section 3. Apart from that, we use only elementary methods from topology and computability theory. Section 4 outlines the proof and reduces it to two propositions, which are then proved in the remaining two sections, respectively.

An alternative construction of a set as in Theorem 1.1⁴ has independently been found by Badaev et al. [2]. That article also contains a proof that the index set of the computable Polish spaces that allow a computably compact representation is not arithmetical.

2 Computable spaces and subsets

A computable Polish space is a Polish space |$X$| with a compatible metric |$d$| and a dense sequence |$(x_{i})_{i}$| such that |$(i,j) \mapsto d(x_{i}, x_{j})$| is a computable real function. The |$x_{i}$| are called the special points of |$X$|⁠. For |$x \in X$| and |$r \in \mathbb{R}^{>0}$| let |$B(x,r)$| be the open ball with centre |$x$| and radius |$r$|⁠. Call an open ball basic if the centre is a special point and the radius is a rational number. If there is a computable function |$f: \mathbb{N} \to \mathbb{N}^{<\omega }$| such that for every |$n$|

$$\begin{align*} & f(n) = (i_{1}, \ldots, i_{k}) \ \Rightarrow \ X = B(x_{i_{1}}, 2^{-n}) \cup \cdots \cup B(x_{i_{k}}, 2^{-n}), \end{align*}$$

the computable Polish space |$X$| is called computably compact.

A closed subset |$K$| of |$X$| is computably enumerable (c.e.) closed if the set of basic balls that intersect |$K$| is computably enumerable (w.r.t. some standard encoding). For non-empty |$K$|⁠, this is equivalent to the existence of a computable sequence that is dense in |$K$|⁠. Note that a c.e. closed subset can itself be seen as a computable Polish space. |$K$| is called computably co-enumerable (co-c.e.) closed if there is a computable sequence of basic balls that exhausts |$X\setminus K$|⁠. Call |$K$| computably closed if it is both c.e. closed and co-c.e. closed. Call |$K$| computably compact if it is compact, c.e. closed and the set of all finite open covers by basic balls is computably enumerable. This is equivalent to |$K$| being compact and the set of all finite open covers by basic balls that intersect |$K$| being computably enumerable. In Euclidean space, it is equivalent to |$K$| being bounded and computably closed. See [7] for a comparison of these and further notions of effectivity of subsets of computable metric spaces.

3 The Feiner classes

Let |$c: \mathbb{N} \to \mathbb{N} \setminus \{0\}$| be a total computable function. We say that a set |$A\subseteq \mathbb{N}$| is in |$\varSigma _{c}^{0}$| if there is a computably enumerable operator |$W_{e}$| such that

$$\begin{align*} & n \in A \ \Leftrightarrow \ n \in W_{e}^{\emptyset^{(c(n)-1)}}, \end{align*}$$

where |$\emptyset ^{(n)}$| is the |$n$|th Turing jump. Also define |$\varPi _{c}^{0}:= \{ A : \mathbb{N} \setminus A \in \varSigma _{c}^{0} \}$| and |$\varDelta _{c}^{0}:= \varSigma _{c}^{0} \cap \varPi _{c}^{0}$|⁠. For constant |$c$|⁠, we recover the usual |$\varSigma$|-, |$\varPi$|- and |$\varDelta$|-classes of the artithmetical hierarchy [17]. Feiner [11] introduced the classes |$\varDelta _{c}^{0}$| for |$c$| of the form |$n \mapsto an + b$| and used it to construct a c.e. Boolean algebra not isomorphic to any computable Boolean algebra. See also the expositions and further references in e.g. [1, 9].

The Feiner classes have been used indirectly in computable topological structure theory before, when certain results were obtained by reduction to results in computable algebraic structure theory. In [3] e.g. Feiner’s example was used to construct a computable topological compact Polish space not homeomorphic to any computably metrized Polish space. Another example is in fact the alternative construction of a set as in Theorem 1.1 by Badaev et al. [2], which is based on an ‘encoding’ of a Boolean algebra into a subset of |$[0,1]$|⁠.

The classical characterizations of the arithmetical |$\varSigma$|- and |$\varPi$|-classes in terms of quantified computable predicates generalize to the Feiner classes as the classical constructions (see e.g. [17; Theorem 14.VIII]) are uniform in the number of quantifiers. So if |$\langle \cdots \rangle : \mathbb{N}^{<\omega } \to \mathbb{N}$| is a standard bi-computable tupling function (see e.g. [17; p. 71]) and

$$\begin{align*} & Q_{n}:= \begin{cases} `\forall\text{'} & \text{if} \ n \ \text{is even,} \\ `\exists\text{'} & \text{if} \ n \ \text{is odd,} \\ \end{cases} \end{align*}$$

then |$A \in \varSigma _{c}^{0}$| if and only if there exists a computable predicate |$p$| such that

$$\begin{align*} & x \in A \ \Leftrightarrow \ (\exists y_{1}) (\forall y_{2}) \cdots (Q_{c(x)} y_{c(x)}) \ p(\langle x, y_{1}, \ldots y_{c(x)} \rangle). \end{align*}$$

A corresponding characterization holds for the |$\varPi$|-classes.

It will be convenient later to also work with the following characterization in terms of the quantifier ‘|$\exists ^\infty$|’ (meaning ‘there exist infinitely many’): |$A \in \varPi _{n \mapsto 2n+1}^{0}$| if and only if there is a computable predicate |$p$| such that

$$\begin{align*} & n \in A \ \Leftrightarrow \ (\exists^\infty y_{n}) \cdots (\exists^\infty y_{1})(\forall x)\ p(\langle n, y_{n}, \ldots, y_{1}, x \rangle). \end{align*}$$

(For the standard arithmetical class |$\varPi _{2n+1}^{0}$| the corresponding statement is [17; Theorem 14.XVIII]. The constructions are uniform in |$n$|⁠.)

The Feiner classes in fact form a hierarchy. We will only need the following special case:

Lemma 3.1.

There exists an |$A \in \varSigma _{n \mapsto 2n + 3}^{0} \setminus \varSigma _{n \mapsto 2n + 2}^{0}$| with |$\{2n : n\in \mathbb{N}\} \subseteq A$|⁠.

Proof.

Choose

$$\begin{align*} & A:= \{ 2n+1 : n \in \mathbb{N},\, 2n+1 \notin W_{n}^{\emptyset^{(4n+3)}} \} \cup \{2n : n\in \mathbb{N}\}. \end{align*}$$

4 Outline of the proof of Theorem 1.1

We start with an informal description: let |$X$| be a compact Polish space. The idea is to encode a given subset of |$\mathbb{N}$| as the set of numbers appearing as Cantor–Bendixson ranks of points in the space (which naturally leads to the appearance of the Feiner classes). The usual Cantor–Bendixson rank, however, is not suitable, basically because identifying isolated points in computably compact spaces is not easier than in merely computable spaces. Computable compactness does, however, help when it comes to identifying disjoint clopen subsets, in the sense that one quantifier change can be saved (compare Lemmas 5.4 and 6.1). So we use a variant of the Cantor–Bendixson rank where a point has positive rank if it is a ‘limit’ of clopen sets instead of isolated points. If we want to encode a set of natural numbers in these ranks, we have the problem that obviously the existence of a point of rank |$n$| implies the existence of points of ranks |$1, 2, \ldots , n-1$|⁠. So we need to ‘mark’ the points the rank of which we actually want to include. We do this by placing them at the endpoints of closed intervals, or more generally by making them elements of connected components with non-empty interiors.

For the formal treatment, call a point |$x \in X$| proper or |$1$|-proper if every neighbourhood of |$x$| is intersected by infinitely many pairwise disjoint clopen subsets of |$X$|⁠. For |$n> 1$|⁠, call a point |$n$|-proper if every neighbourhood contains infinitely many |$(n-1)$|-proper points. If there is an |$n \in \mathbb{N}$| such that |$x$| is |$n$|-proper but not |$(n+1)$|-proper, call |$n$| the proper rank of |$x$|⁠.

Consider a subset |$Y \subseteq X$|⁠. If there is an |$n$| such that |$Y$| contains an |$n$|-proper point, but no |$(n+1)$|-proper point, call |$n$| the proper rank of |$Y$|⁠. The proper rank of |$Y$| shall be |$0$| if |$Y$| does not contain any proper points.

Call a connected component of |$X$| |$n$|-distinguished if its proper rank is |$n$| and its interior in non-empty. Define

$$\begin{align*} & \rho(X):= \left\{ n \in \mathbb{N} : X \ \text{has an} \ n\text{-distinguished component} \right\}\!. \end{align*}$$

Clearly, |$\rho$| is a topological invariant, i.e. |$\rho (X_{1}) = \rho (X_{2})$| if |$X_{1}$| and |$X_{2}$| are homeomorphic.

Our proof will proceed by showing the following two propositions:

Proposition 4.1.

If |$X$| is a computably compact Polish space then |$\rho (X) \in \varSigma _{m \mapsto 2m + 2}^{0}$|⁠.

Proposition 4.2.

For every |$A \in \varSigma _{m \mapsto 2m + 3}^{0}$| with |$\{2n : n\in \mathbb{N}\} \subseteq A$|⁠, there is a perfect c.e. closed subset |$K$| of |$[0,1]$| such that |$\rho (K) = A$|⁠.

For the proof of Theorem 1.1 it is then sufficient to choose |$A$| as in Lemma 3.1 and then |$K$| as in Proposition 4.2.

5 Proof of Proposition 4.1

Throughout this section, we assume that |$(X, d)$| is a computable Polish space with special points |$(x_{i})_{i}$|⁠.

Call balls |$B(x,r)$|⁠, |$B(y,s)$| formally disjoint if |$d(x,y)> r+s$|⁠. Similarly, call |$B(x,r)$| formally enclosed in |$B(y,s)$| if |$y \in B(x,r)$| and |$d(x,y) + r < s$|⁠.⁵

We will repeatedly use the following

Fact 5.1.

If |$X$| is computably compact, there is a computable enumeration of all decompositions of |$X$| into finitely many disjoint clopen subsets. The clopen sets in this enumeration are given as (encodings of) finite unions of basic balls. We furthermore have:

(i) In each of the enumerated decompositions, the encoded balls contributing to different clopen sets are pairwise formally disjoint.
(ii) For every |$\varepsilon> 0$| every clopen decomposition appears in the enumeration in a representation with the radii of all encoded balls smaller than |$\varepsilon$|⁠. (This means every decomposition will appear again and again with higher and higher resolution.)

Fact 5.1 is proved in [8; Lemma 4.21, Theorem 1.1(ii)] for splits of |$X$| into two clopen subsets, but the argument easily extends to finite decompositions and also yields the additional features (i) and (ii).

Lemma 5.2.

Consider the following statements for a ball |$B(x,r)$|⁠:

(i) |$B(x,r)$| contains a proper point.
(ii) |$B(x,r)$| is intersected by infinitely many disjoint clopen subsets of |$X$|⁠.
(iii) For every |$k \geq 1$| there are |$k$| pairwise disjoint clopen subsets of |$X$| that intersect |$B(x,r)$|⁠.
(iv) |$\overline{B(x,r)}$| contains a proper point.

Then (i) |$\Rightarrow$| (ii) |$\Leftrightarrow$| (iii) |$\Rightarrow$| (iv).

Proof.

‘(i) |$\Rightarrow$| (ii)’: by definition.

‘(ii) |$\Rightarrow$| (iii)’: obvious.

‘(ii) |$\Rightarrow$| (iv)’: let |$\{ C_{i} \}_{i \in I}$| by an infinite family of pairwise disjoint clopen sets that intersect |$B(x,r)$|⁠: Choosing one point |$y_{i}$| from each |$C_{i} \cap B(x,r)$|⁠, the family |$(y_{i})_{i \in I}$| must, by compactness, have a limit point |$z \in \overline{B(x,r)}$|⁠. Then |$z$| is proper by construction.

‘(iii) |$\Rightarrow$| (ii)’: by assumption, there is a double sequence |$(C_{k,i} : k \geq 1,\ 1\leq i \leq k)$| of clopen sets intersecting |$B(x,r)$| and having |$C_{k,i} \cap C_{k,j} = \emptyset$| for any |$1\leq i < j \leq k$|⁠. For every |$k$|⁠, define

$$\begin{align*} & C_{k}:= \{ C_{j,i} : 1 \leq j \leq k,\, 1 \leq i \leq j \}. \end{align*}$$

Recall that the clopen subsets form a Boolean algebra under the set operations. Let |$\langle C_{k} \rangle$| be the Boolean subalgebra generated by |$C_{k}$|⁠. Define |$\tilde{C}_{k}$| as the set of all atoms of |$\langle C_{k} \rangle$| that are subsets of |$\bigcup C_{k}$| and intersect |$B(x,r)$|⁠. Note that |$|\tilde{C}_{k}| \geq k$|⁠. Furthermore, each |$\tilde{C}_{k+1}$| is obtained from |$\tilde{C}_{k}$| by adding some sets that are disjoint from |$\bigcup \tilde{C}_{k}$| and by splitting some elements of |$\tilde{C}_{k}$|⁠. So if we consider the infinite set |$\tilde{C}:= \bigcup _{k} \tilde{C}_{k}$| under the partial order |$\supseteq$|⁠, every element is either maximal or has at least two incomparable successors. This easily implies that |$\tilde{C}$| contains an infinite antichain. As any two incomparable sets are even disjoint, the elements of this antichain are the desired infinitely many disjoint clopen sets intersecting |$B(x,r)$|⁠.

Lemma 5.3.

Suppose |$X$| is computably compact. Then

$$\begin{align*}& \left\{ (n, r, k) \in \mathbb{N} \times \mathbb{Q}^{>0} \times \mathbb{N} : B(x_{n}, r) \text{ intersects at least} \ k \ \text{disjoint clopen sets} \right\} \in \varSigma_{1}^{0}. \end{align*}$$

Proof.

A basic ball |$B(x_{n}, r)$| intersects |$k$| disjoint clopen sets iff there is a decomposition of |$X$| into |$k$| clopen sets each of which intersects |$B(x_{n}, r)$|⁠. (In fact, if |$C_{1}, \ldots , C_{k}$| are disjoint clopen sets intersecting |$B(x_{n}, r)$| and |$C:= C_{1} \cup \cdots \cup C_{k}$|⁠, consider |$C_{1}, \ldots , C_{k} \cup (X \setminus C)$|⁠.) The intersection of |$B(x_{n}, r)$| with any clopen set is open; it is thus non-empty iff it contains a special point. So |$B(x_{n}, r)$| intersects |$k$| disjoint clopen sets iff there is a decomposition of |$X$| into clopen |$C_{1}, \ldots , C_{k}$| along with sepcial points |$x_{n_{1}}, \ldots , x_{n_{k}}$| with |$x_{n_{i}} \in C_{i} \cap B(x_{n}, r)$|⁠. The lemma follows because we can enumerate all decompositions of |$X$| into |$k$| clopen sets by Fact 5.1, and for each of these decompositions, we can enumerate the |$k$|-tuples of special points where each point is in a different element of the decomposition and all points are in |$B(x_{n}, r)$|⁠.

Lemma 5.4.

Suppose |$X$| is computably compact. There is a set |$A \in \varPi _{2}^{0}$| such that for all |$n \in \mathbb{N}$|⁠, |$r \in \mathbb{Q}^{>0}$|

$$\begin{align*} & B(x_{n}, r)\ \text{contains a proper point} \ \Rightarrow \ \langle n, r \rangle \in A \ \Rightarrow \ \overline{B(x_{n}, r)}\ \text{contains a proper point.} \end{align*}$$

Proof.

Combine Lemma 5.2, implications (i) |$\Rightarrow$| (iii) |$\Rightarrow$| (iv) and Lemma 5.3.

Lemma 5.5.

Consider the following statements for a ball |$B(x,r)$| and |$n>1$|⁠:

(i) |$B(x,r)$| contains an |$n$|-proper point.
(ii) |$B(x,r)$| contains infinitely many |$(n-1)$|-proper points.
(iii) For every |$k$| there are |$k$| formally disjoint basic open balls formally enclosed in |$B(x,r)$| each of which contains an |$(n-1)$|-proper point.
(iv) For every |$k$| there are |$k$| formally disjoint basic closed balls formally enclosed in |$B(x,r)$| each of which contains an |$(n-1)$|-proper point.
(v) |$\overline{B(x,r)}$| contains an |$n$|-proper point.

Then (i) |$\Rightarrow$| (ii) |$\Leftrightarrow$| (iii) |$\Leftrightarrow$| (iv) |$\Rightarrow$| (v).

Proof.

‘(i) |$\Rightarrow$| (ii)’: by definition.

‘(ii) |$\Rightarrow$| (iii)’ and ‘(ii) |$\Rightarrow$| (iv)’: obvious.

‘(ii) |$\Rightarrow$| (v)’: by compactness, the |$(n-1)$|-proper points must have a limit point |$z$| in |$\overline{B(x,r)}$|⁠. Then |$z$| is |$n$|-proper.

‘(iii) |$\Rightarrow$| (ii)’ and ‘(iv) |$\Rightarrow$| (ii)’: Easily proved by contradiction.

Lemma 5.6.

Suppose |$X$| is computably compact. There exists a set |$A \in \varPi _{\langle m, r, n \rangle \mapsto 2n}^{0}$| such that for |$m \in \mathbb{N}$|⁠, |$n\geq 1$|⁠, |$r \in \mathbb{Q}^{>0}$|⁠:

$$\begin{align*} & B(x_{m}, r)\ \text{contains an} \ n\text{-proper point} \ \Rightarrow \ \langle m, r, n \rangle \in A \ \Rightarrow \ \overline{B(x_{m}, r)}\ \text{contains an} \ n\text{-proper point}. \end{align*}$$

Proof.

We need to describe how to compute a predicate |$p_{3}$| such that the set |$A$| with

$$\begin{align*} & \langle m, r, n \rangle \in A \ \Leftrightarrow \ (\forall k_{n})(\exists \ell_{n}) \cdots (\forall k_{1})(\exists \ell_{1}) \ p_{3}(\langle m, r, n, k_{n}, \ell_{n}, \ldots, k_{1}, \ell_{1} \rangle) \end{align*}$$

has the desired properties. By Lemma 5.4 there is a computable predicate |$p_{2}$| such that

$$\begin{eqnarray}& B(x_{m}, r)\ \text{contains a proper point} \ \Rightarrow \ (\forall k)(\exists \ell)\ p_{2}(\langle m, r, k, \ell \rangle) \ \Rightarrow \ \overline{B(x_{m}, r)}\ \text{contains a proper point}\end{eqnarray}$$

(1)

for any |$m \in \mathbb{N}$|⁠, |$r \in \mathbb{Q}^{>0}$|⁠. We obtain |$p_{3}$| by a straightforward recursive construction over |$p_{2}$| using the characterization from Lemma 5.5: let some input |$\langle m, r, n, k_{n}, \ell _{n}, \ldots , k_{1}, \ell _{1} \rangle$| be given. In case |$n=1$|⁠, return |$p_{2}(\langle m, r, k_{1}, \ell _{1} \rangle )$|⁠. In case |$n>1$|⁠, we make use of a computable function |$g$| such that |$(g(m, r, k,\ell ))_\ell$| is an enumeration of (encodings of) all |$k$|-tuples of formally disjoint basic balls formally enclosed in |$B(x_{m},r)$|⁠. Compute

$$\begin{align*} & g(m, r, k_{n},\ell_{n}) =: \left( B(x_{i_{j}}, t_{j}) \right)_{1\leq j \leq k_{n}} \end{align*}$$

and return the conjunction

$$\begin{align*} & \bigwedge_{1\leq j \leq k_{n}} p_{3}(\langle i_{j}, t_{j}, n-1, k_{n-1}, \ell_{n-1,j}, \ldots, k_{1}, \ell_{1,j} \rangle), \end{align*}$$

where we have split |$\ell _{v}$| into |$k_{n}$| variables via the decoding |$\langle \ell _{v,1}, \ldots , \ell _{v,k_{n}} \rangle _{k_{n}} = \ell _{v}$| for |$v = n-1, \ldots , 1$|⁠.

The verification is by induction on |$n$|⁠. The base case |$n=1$| is yielded directly by (1). For |$n>1$|⁠:

$$\begin{align*}& \begin{array}{rl} & B(x_{m}, r)\ \text{contains an} \ n\hbox{-}\text{proper point} \\ & \Rightarrow \ (\forall k_{n})(\exists \ell_{n}) [ g(m, r, k_{n}, \ell_{n}) = \left( B(x_{i_{j}}, t_{j}) \right)_{1\leq j \leq k_{n}} \\ & \qquad\qquad\qquad\qquad \Rightarrow \, \bigwedge_{1\leq j \leq k_{n}} (B(x_{i_{j}}, t_{j}) \ \text{contains an} \ (n-1)\hbox{-}\text{proper point}) ] \\ & \Rightarrow \ (\forall k_{n})(\exists \ell_{n}) [ g(m, r, k_{n}, \ell_{n}) = \left( B(x_{i_{j}}, t_{j}) \right)_{1\leq j \leq k_{n}} \\ & \qquad\qquad\qquad\qquad \Rightarrow \, \bigwedge_{1\leq j \leq k_{n}} (\forall k_{n-1})(\exists \ell_{n-1}) \cdots (\forall k_{1})(\exists \ell_{1}) \ p_{3}(\langle i_{j}, t_{j}, n-1, k_{n-1}, \\ & \qquad\qquad\qquad\qquad\quad\ell_{n-1}, \ldots, k_{1}, \ell_{1} \rangle) ] \\ & \Rightarrow \ (\forall k_{n})(\exists \ell_{n}) [ g(m, r, k_{n}, \ell_{n}) = \left( B(x_{i_{j}}, t_{j}) \right)_{1\leq j \leq k_{n}} \\ & \qquad\qquad\qquad\qquad \Rightarrow \, \bigwedge_{1\leq j \leq k_{n}} (\overline{B(x_{i_{j}}, t_{j})} \ \text{contains an} \ (n-1)\hbox{-}\text{proper point}) ] \\ & \Rightarrow \ \overline{B(x_{m}, r)}\ \text{contains an} \ n\hbox{-}\text{proper point} \end{array} \end{align*}$$

The first implication is Lemma 5.5(i)|$\Rightarrow$|(iii), the second and third are the induction hypothesis, the fourth is Lemma 5.5(iv)|$\Rightarrow$|(v). To see that the third statement is in fact equivalent to

$$\begin{align*} & (\forall k_{n})(\exists \ell_{n}) \cdots (\forall k_{1})(\exists \ell_{1}) \ p_{3}(\langle m, r, n, k_{n}, \ell_{n}, \ldots, k_{1}, \ell_{1} \rangle), \end{align*}$$

and hence to |$\langle m, r, n \rangle \in A$|⁠, move all quantifiers to the left using the Tarski–Kuratowski algorithm [17] and compare to the recursive definition of |$p_{3}$|⁠.

Recall that the quasi-component of a point is the intersection of all clopen sets that contain the point. The next lemmas make use of the following fact about compact spaces (see e.g. [10; Theorem 6.1.23]):

Fact 5.7.

The quasi-component of any |$x \in X$| is equal to its connected component.

Lemma 5.8.

Proof.

The ‘only if’ direction follows directly from Fact 5.7. For the ‘if’ direction, let |$C$| be the connected component of |$x$| and let |$A$| be the set of |$n$|-proper points in |$X$|⁠. The claim is trivial for |$A = \emptyset$|⁠, so assume |$A \neq \emptyset$|⁠. Note the |$A$| is closed. Let |$\{C_{i}\}_{i\in I}$| be the family of all clopen sets containing |$x$|⁠. For any |$i_{1}, \ldots i_{n}$|⁠, we have that |$C_{i_{1}} \cap \cdots \cap C_{i_{n}}$| is clopen and contains |$x$|⁠, so |$C_{i_{1}} \cap \cdots \cap C_{i_{n}} \cap A \neq \emptyset$| by assumption. Thus the family |$\{ C_{i} \cap A \}$| has the Finite Intersection Property (see [10; Theorem 3.1.1]), which implies

$$\begin{align*} & \emptyset \neq \bigcap_{i\in I} (C_{i} \cap A) = A \cap \bigcap_{i\in I} C_{i} = A \cap C. \end{align*}$$

Lemma 5.9.

Assume that |$X$| is computably compact. Then

$$\begin{align*} & \text{Prop}(n,m):= \left\{ \langle n, m \rangle: \text{the connected component of} \ x_{n} \ \text{contains an} \ m\text{-proper point} \right\} \in \varPi_{\langle n,m \rangle \mapsto 2m}^{0} \end{align*}$$

Proof.

As a consequence of Fact 5.1, there is an enumeration |$(C_{n,k})_{n,k}$| such that |$(C_{n,k})_{k}$| lists all clopen sets containing |$x_{n}$|⁠, each as a finite union of basic balls. |$C_{n,k}$| contains an |$m$|-proper point iff one of the open balls contains an |$m$|-proper point, or, equivalently, if the closure of one of the balls contains an |$m$|-proper point (because |$C_{n,k}$| as a closed set is also equal to the union of the closures of the balls). Lemma 5.6 thus yields

$$\begin{align*} & \left\{ \langle n, m, k \rangle : C_{n,k}\ \text{contains an} \ m\text{-proper point} \right\} \in \varPi_{\langle n,m,k \rangle \mapsto 2m}^{0}. \end{align*}$$

By Lemma 5.8, the intersection of these sets over |$k$| is equal to |$\text{Prop}(n,m)$|⁠. The intersection does not change the quantifier complexity.

Lemma 5.10.

Assume that |$X$| is computably compact. Then

$$\begin{align*} & \text{PropRank}:= \left\{ \langle n, m \rangle : \text{the connected component of} \ x_{n} \ \text{has proper rank} \ m \right\} \in \varSigma_{\langle n,m \rangle \mapsto 2m + 2}^{0}. \end{align*}$$

Proof.

Follows from Lemma 5.9 because

$$\begin{align*} & \langle n, m \rangle \in \text{PropRank} \ \Leftrightarrow \ \langle n, m \rangle \in \text{Prop} \ \wedge \ \langle n, m + 1 \rangle \notin \text{Prop}. \end{align*}$$

Lemma 5.11.

Assume that |$X$| is computably compact.

(i) The distance |$D(n)$| between a special point |$x_{n}$| and the complement of its connected component is right-c.e. uniformly in |$n$|⁠.
(ii) |$\text{Inner}:= \left \{ n : x_{n} \text{ is in the interior of its connected component} \right \} \in \varSigma _{2}^{0}$|⁠.

Proof.

(i): As a consequence of Fact 5.1 we can enumerate a sequence |$(C_{m})_{m}$| that contains (with repetition) all clopen sets |$C_{m}$| with |$x_{n} \in X \setminus C_{m}$|⁠, each as a finite union of basic balls, say

$$\begin{align*} & C_{m}:= \bigcup_{i = 1}^{k_{m}} B(x_{n_{m,i}}, r_{m,i}), \end{align*}$$

and such that |$r_{m,i} < 2^{-m}$|⁠. By Fact 5.7, we have |$D(n) = d\left (x_{n}, \bigcup _{m} C_{m}\right )$|⁠. Define

$$\begin{align*} & \tilde{D}(n) = \inf \left\{ d(x_{n_{m,i}}, x_{n}) : m \in \mathbb{N},\ 1 \leq i \leq k_{m} \right\}\!. \end{align*}$$

We claim |$\tilde{D}(n) = D(n)$|⁠, which implies that |$D(n)$| is right-c.e. In fact, for all |$m \in \mathbb{N}$|⁠, |$1 \leq i \leq k_{m}$|⁠, we have

$$\begin{align*} & D(n) = d\left(x_{n}, \bigcup_\ell C_\ell \right) \leq d(x_{n}, C_{m}) \leq d(x_{n_{m,i}}, x_{n}), \end{align*}$$

so |$D(n) \leq \tilde{D}(n)$|⁠. On the other hand, for every |$\varepsilon> 0$|⁠, there is an |$x \in \bigcup _\ell C_\ell$| such that |$d(x, x_{n}) - D(n) < \varepsilon$|⁠. Choose |$m$| such that |$x \in C_{m}$| and |$2^{-m} < \varepsilon$|⁠, then choose |$i$| such that |$x \in B(x_{n_{m,i}}, r_{m,i})$|⁠. Then

$$\begin{align*} & d(x_{n_{m,i}}, x_{n}) - D(n) \leq d(x_{n_{m,i}}, x) + d(x, x_{n}) - D(n) < d(x_{n_{m,i}}, x) + \varepsilon < r_{m,i} + \varepsilon < 2^{-m} + \varepsilon < 2\varepsilon. \end{align*}$$

As |$\varepsilon> 0$| was arbitrary, this yields |$\tilde{D}(n) \leq D(n)$|⁠.

(ii): By (i) there is a computable |$g: \mathbb{N} \times \mathbb{N} \to \mathbb{Q}$| such that |$(g(n, \ell ))_\ell$| converges to |$D(n)$| from above. |$x_{n}$| is in the interior of its connected component iff |$D(n)> 0$| iff |$(\exists m)(\forall \ell )\ g(n,\ell )> 2^{-m}$|⁠.

A component of |$X$| has non-empty interior iff its interior contains a special point, so

$$\begin{align*} & m \in \rho(X) \ \Leftrightarrow \ (\exists n)\left[ n \in \text{Inner}\ \wedge\ \langle n, m \rangle \in \text{PropRank} \right]\!. \end{align*}$$

Proposition 4.1 then follows from Lemmas 5.11(ii) and 5.10.

6 Proof of Proposition 4.2

Lemma 6.1.

Uniformly relative to any oracle |$Y \subseteq \mathbb{N}$|⁠, there is a perfect |$Y$|-c.e. closed set |$G \subseteq [0,1]$| such that |$1 \in G$| and, considering the condition

$$\begin{eqnarray}& (\exists^\infty k)(\forall \ell)\ \langle k, \ell \rangle \in Y,\end{eqnarray}$$

(2)

we have:

(i) If (2) is true:
- (a) |$G$| is a countably infinite union of disjoint closed intervals and |$\{1\}$|⁠.
- (b) The point |$1$| is proper in |$G$| with rank |$1$|⁠.
- (c) There are no other points that are proper in |$G$|⁠.
- (d) The connected component of |$1$| is |$\{1\}$| and has empty interior in |$G$|⁠.
(ii) If (2) is false, |$G$| is a finite union of closed intervals (and thus does not have any proper points).

Proof.

Define

$$\begin{align*} & G_{k} = \begin{cases} \left[ 1 - 2^{-k}, 1 - 2^{-k} + 2^{-(k+2)} \right] & \text{if}\ (\forall \ell)\ \langle k, \ell \rangle \in Y, \\ \left[ 1 - 2^{-k}, 1 - 2^{-(k+1)} \right] & \text{otherwise,} \end{cases} \end{align*}$$

and |$G:= \bigcup _{k} G_{k} \cup \{1\}$|⁠. The |$G_{k}$| are constructed as a sequence of closed intervals, closer and closer to |$1$|⁠, such that the gap between |$G_{k}$| and |$G_{k+1}$| is |$2^{-(k+2)}$| if |$(\forall \ell )\ \langle k, \ell \rangle \in Y$|⁠; the intervals intersect in |$1 - 2^{-(k+1)}$| otherwise. This clearly implies (i)(a) and (ii). Also, |$G$| is c.e. because the potential part of |$G_{k}$| closing the gap to |$G_{k+1}$| is added on the enumerable condition |$(\exists \ell )\ \langle k, \ell \rangle \notin Y$|⁠.

Assume (2) is true and let |$(\tilde{G}_{j})_{j}$| be the maximal closed intervals contained in |$G$|⁠, in ascending order. (So each |$\tilde{G}_{j}$| is a union of certain finitely many |$G_{k}$|⁠.) Each |$\tilde{G}_{j}$| is clopen in |$G$|⁠. Every neighbourhood of |$1$| contains infinitely many |$\tilde{G}_{j}$|⁠, so |$1$| is proper. The component of |$1$| is |$\{1\}$|⁠, because every |$x \in G \setminus \{1\}$| is contained in one of the |$\tilde{G}_{j}$|⁠, which is separated from |$1$| by the gap between |$\tilde{G}_{j}$| and |$\tilde{G}_{j+1}$|⁠. |$\{1\}$| has empty interior because every neighbourhood of |$1$| also intersects some |$\tilde{G}_{j}$| and thus exceeds |$\{1\}$|⁠. So all properties listed under (i) hold.

In the following text we write |$x + H:= \{ x + y : y \in H \}$| and |$xH:= \{ xy : y \in H \}$| for |$x \in \mathbb{R}$|⁠, |$H \subseteq \mathbb{R}$|⁠.

Lemma 6.2.

Uniformly relative to any oracle |$Y \subseteq \mathbb{N}$|⁠, there is a |$Y$|-computable sequence |$(H_{m})_{m \geq 1}$| of perfect |$Y$|-c.e. closed sets |$H_{m} \subseteq [0,1]$| such that for every |$m \geq 1$|

(i) all components of |$H_{m}$| with non-empty interior have proper rank |$0$| in |$H_{m}$|⁠,
(ii) if |$1$| is proper in |$H_{m}$|⁠, its proper rank is at most |$m$|⁠,
(iii) |$1$| is |$m$|-proper in |$H_{m}$| iff
$$\begin{align*} & (\exists^\infty k_{m}) \cdots (\exists^\infty k_{1})(\forall \ell)\ \langle k_{m}, \ldots k_{1}, \ell \rangle \in Y^{[m]}, \end{align*}$$
where
$$\begin{align*} & Y^{[m]}:= \left\{ \langle k_{m}, \ldots, k_{1}, \ell \rangle : \langle m, k_{m}, \ldots, k_{1}, \ell \rangle \in Y \right\}\!. \end{align*}$$

Proof.

For fixed |$m$|⁠, we use a recursive construction in |$i = 1, \ldots , m$|⁠. In each stage we compute a sequence of c.e. closed sets, each as a countable union of certain scaled and shifted sets from the previous stage. In preparation, for every |$i = 1, \ldots , m$| and |$(k_{m}, \ldots , k_{i+1}) \in \mathbb{N}^{m-i}$|⁠, generalize the definition of |$Y^{[m]}$| to

$$\begin{align*} & Y^{[m, k_{m}, \ldots, k_{i+1}]}:= \left\{ \langle k_{i}, \ldots, k_{1}, \ell \rangle : \langle m, k_{m}, \ldots, k_{1}, \ell \rangle \in Y \right\}\!. \end{align*}$$

For |$i=1$| compute sets |$H^{[m, k_{m}, \ldots , k_{2}]}$| with the construction from Lemma 6.1, applied relative to |$Y^{[m, k_{m}, \ldots , k_{2}]}$|⁠, for each combination |$(k_{m}, \ldots , k_{2}) \in \mathbb{N}^{m-1}$|⁠.

For |$i> 1$|⁠, assume |$H^{[m, k_{m}, \ldots , k_{i}]}$| have already been constructed for all |$(k_{m}, \ldots , k_{i}) \in \mathbb{N}^{m-(i-1)}$|⁠. Define

$$\begin{align*} & H^{[m, k_{m}, \ldots, k_{i+1}]}:= \bigcup_{k_{i} \in \mathbb{N}} \left(1 - 2^{k_{i}} + 2^{-(k_{i}+2)} H^{[m, k_{m}, \ldots, k_{i}]} \right) \ \cup \ \{1\}. \end{align*}$$

After the last stage of the construction, i.e. |$i=m$|⁠, the set |$H^{[m]}$| has been constructed. Put |$H_{m} = H^{[m]}$|⁠. It is easy to show by induction on |$i=1, \ldots , m$| that every set |$H^{[m, k_{m}, \ldots , k_{i+1}]}$| appearing in the construction fulfils properties (i)–(iii) with |$i$| in place of |$m$| and |$Y^{[m, k_{m}, \ldots , k_{i+1}]}$| in place of |$Y^{[m]}$|⁠, where the base case is yielded by Lemma 6.1. So (i)–(iii) hold for |$H_{m}$| and |$Y^{[m]}$| in particular. Also, |$H_{m}$| is |$Y$|-c.e. as the union of a |$Y$|-computable sequence of |$Y$|-c.e. sets.

For the proof of Proposition 4.2, we need to construct a c.e. closed subset |$K$| of |$[0,1]$| such that |$\rho (K) = A$| for given |$A \in \varSigma _{m \mapsto 2m + 3}^{0}$| with |$\{2n : n\in \mathbb{N}\} \subseteq A$|⁠.

By the characterization of |$\varPi _{m \mapsto 2m + 3}^{0}$| mentioned in Section 3, there is a computable predicate |$p$| such that

$$\begin{align*} & m \notin A \ \Leftrightarrow \ (\exists^\infty k_{m+1}) \cdots (\exists^\infty k_{1})(\forall \ell)\ p(\langle m, k_{m+1}, \ldots k_{1}, \ell \rangle). \end{align*}$$

Choose

$$\begin{align*} & Y:= \{ \langle m+1, k_{m+1}, \ldots k_{1}, \ell \rangle : p(\langle m, k_{m+1}, \ldots k_{1}, \ell \rangle) \} \end{align*}$$

and note that |$Y$| is computable. Construct |$(H_{m})_{m}$| as in Lemma 6.2 relative to this |$Y$|⁠. Then |$(H_{m})_{m}$| is a computable sequence of c.e. closed sets such that

$$\begin{align*}& \begin{array}{rl} m \notin A & \ \Leftrightarrow \ (\exists^\infty k_{m+1}) \cdots (\exists^\infty k_{1})(\forall \ell)\ p(\langle m, k_{m+1}, \ldots k_{1}, \ell \rangle) \\ & \ \Leftrightarrow \ (\exists^\infty k_{m+1}) \cdots (\exists^\infty k_{1})(\forall \ell)\ \langle m + 1, k_{m+1}, \ldots k_{1}, \ell \rangle \in Y \\ & \ \Leftrightarrow \ 1 \text{ is } (m+1) \text{-proper in}\ H_{m+1}. \end{array} \end{align*}$$

Construct another sequence |$(\tilde{H}_{m})_{m}$| as in Lemma 6.2, but this time relative to |$\mathbb{N}$|⁠, i.e. |$(\tilde{H}_{m})_{m}$| is a generic sequence of c.e. closed sets such that |$1$| is |$m$|-proper in each |$\tilde{H}_{m}$|⁠. For every |$m$|⁠, define

$$\begin{align*} & K_{m}:= \begin{cases} \tilde{H}_{m} \cup [1, 2] & \text{if} \ m \ \text{is even}, \\ \tilde{H}_{m} \cup [1, 2] \cup (3 - H_{m+1}) & \text{if} \ m \ \text{is odd.} \end{cases} \end{align*}$$

Each |$K_{m}$| has |$[1,2]$| as a connected component with non-empty interior and the |$m$|-proper point |$1$|⁠. If |$m$| is odd and |$m \notin A$|⁠, the component |$[1,2]$| also has the |$(m+1)$|-proper point |$2$|⁠, so the proper rank of |$[1,2]$| is |$m+1$|⁠. If |$m$| is odd and |$m \in A$|⁠, the proper rank of |$2$| is at most |$m$|⁠, so the proper rank of |$[1,2]$| is |$m$|⁠. All other components of |$K_{m}$| with non-empty interior are the closed intervals from the constructions of |$\tilde{H}_{m}$| and |$H_{m}$|⁠; they all have proper rank |$0$|⁠. To summarize:

$$\begin{align*} & \rho(K_{m}):= \begin{cases} \{0, m+1\} & \text{if} \ m \ \text{is odd and} \ m \notin A, \\ \{0, m\} & \text{otherwise.} \end{cases} \end{align*}$$

For the construction of |$K$| it is sufficient to line up scaled down separated copies of the |$K_{m}$| in |$[0,1]$| and add the closing point at |$1$|⁠:

$$\begin{align*} & K = \bigcup_{m} \left(1 - 2^{-m} + 2^{-(m+3)} + 2^{-(m+4)}K_{m} \right) \cup \{ 1 \}. \end{align*}$$

Then

$$\begin{align*} & \begin{array}{rl} \rho(K) & = \bigcup_{m} \rho(K_{2m}) \cup \bigcup_{m} \rho(K_{2m+1}) \\ & = \{ 2m : m \in \mathbb{N} \} \cup \left( \{ 2m+1 : m\in \mathbb{N},\, 2m+1 \in A \} \right.\\ &\left.\quad\cup \{ 2m+2 : m\in \mathbb{N},\, 2m+1 \notin A \} \cup \{ 0 \} \right) \\ & = \{ 2m : m \in \mathbb{N} \} \cup \{ 2m+1 : m\in \mathbb{N},\, 2m+1 \in A \} \\ & = A \end{array}\!\!, \end{align*}$$

where the last equality follows from the assumption |$\{ 2m : m \in \mathbb{N} \} \subseteq A$|⁠.

Footnotes

In the latter case, it is also important which representation of |$\mathbb{R}$| we use for the values of the distance function.

See Section 2. C.e. closed subsets of a computable Polish space can always themselves be interpreted as computable Polish spaces.

Recall that a perfect subset of a topological space is a closed subset that does not have any isolated points.

The alternative construction, however, does not yield a perfect set.

Be aware that both being formally disjoint and being formally enclosed are properties of |$(y, s, x, r)$|⁠, not of the sets |$B(x,r)$|⁠, |$B(y,s)$|⁠.

References

[1]

C. J.

Ash

and

Knight

Computable Structure Theory and the Hyperarithmetical Hierarchy

North Holland Publishing Co.

2000

Month:	Total Views:
August 2026	174
September 2026	50
October 2026	31

Article Contents

A counterexample regarding C.E. closed subsets of [0,1] under homeomorphisms

Abstract

1 Introduction

2 Computable spaces and subsets

3 The Feiner classes

4 Outline of the proof of Theorem 1.1

5 Proof of Proposition 4.1

6 Proof of Proposition 4.2

Footnotes

References

Citations

Views

Altmetric

Email alerts

Citing articles via

New and popular articles

More from Oxford Academic

This Feature Is Available To Subscribers Only

Gift article access

Gift article access

Gift article access

Gift article access