Strong computable type

Abstract

A compact set has computable type if any homeomorphic copy of the set which is semicomputable is actually computable. Miller proved that finite-dimensional spheres have computable type, Iljazović and other authors established the property for many other sets, such as manifolds. In this article we propose a theoretical study of the notion of computable type, in order to improve our general understanding of this notion and to provide tools to prove or disprove this property.

We first show that the definitions of computable type that were distinguished in the literature, involving metric spaces and Hausdorff spaces respectively, are actually equivalent. We argue that the stronger, relativized version of computable type, is better behaved and prone to topological analysis. We obtain characterizations of strong computable type, related to the descriptive complexity of topological invariants, as well as purely topological criteria. We study two families of topological invariants of low descriptive complexity, expressing the extensibility and the null-homotopy of continuous functions. We apply the theory to revisit previous results and obtain new ones.

Keywords

Computable type descriptive complexity topological invariant

1. Introduction

Computable analysis provides several notions of computability for compact subsets of Euclidean spaces and more general topological spaces. The most important ones are the notions of computable and semicomputable set. Intuitively, a subset of the Euclidean plane is computable if there exists a program that can draw the set on a screen with arbitrary resolution; it is semicomputable if there exists a program that can reject points that are outside the set. A famous example is given by the Mandelbrot set, which can easily be seen to be semicomputable from its very definition, but whose computability is an open problem, related to a conjecture in complex dynamics [17].

It turns out that for certain sets, semicomputability is actually equivalent to computability. It was discovered by Miller [32] that finite-dimensional spheres embedded in Euclidean spaces enjoy this property. This result later led Iljazović to systematically study this computabilty-theoretic property, for spheres embedded in computable metric spaces [22], manifolds [23] and many other sets in a series of articles with several authors [7,9–11,18,21–24,26]. We recently identified which finite simplicial complexes have computable type in [2]. Most of the results in the literature are not only about sets, but about pairs. A pair should be informally thought as a set together with its “boundary”, the typical example being the $(n + 1)$ -dimensional ball and its bounding n-dimensional sphere. A pair has computable type if for any copy $(X, A)$ , if X and A are semicomputable then X is computable.

The purpose of the present article is not to provide new examples, but to develop a structural understanding of the notion of computable type, with several goals in mind. The first goal is practical. Establishing that a space has computable type can be difficult and very technical, so there is a need to provide unifying and simplifying arguments for previous results as well as general tools that can be applied to establish new results with less effort.

Our general goal is to highlight the interaction between topology and computability underlying the notion of computable type. The definition of this notion combines topology and computability theory, and the arguments always gather ideas from these two fields. It would be clarifying to split the arguments into two parts, a purely topological one and a computability-theoretic one.

Having computable type is by definition a topological invariant, and its precise relationship with other topological invariants should be explored. A more explicit relationship with topology would enable one to leverage the venerable field of topology, notably algebraic topology, in the study of a computability-theoretic problem. Indeed, the main results about computable type rely on classical topological results: Miller used the homology of the complement of the sphere in [32], Iljazović used some form of Brouwer’s fixed-point theorem in [22,23].

Finally, a better theoretical understanding also has many consequences: it can give more information on previous results, give new results with little effort, clarify the role of certain assumptions in the results.

1.1. Summary of the main results

Let us present the main results of the article, stated informally.

Mainly two notions of computable type have been introduced in the literature, that consider copies of the set embedded in different classes of topological spaces, namely computable metric spaces and computably Hausdorff spaces respectively. Several results have been established on computable metric spaces [21,23] and then extended to computably Hausdorff spaces [11,26]. We first show that these two notions are actually equivalent.

Theorem 1 (Theorem 3.4).

Computable type can be equivalently defined on the Hilbert cube, on computable metric spaces and on computably Hausdorff spaces.

The proof is based on Schröder’s effective metrization theorem [36] which implies that compact Hausdorff spaces are metrizable in an effective way.

One cannot expect interesting general characterizations of the computable type property: most spaces have computable type simply because they do not have any semicomputable copy. This issue can be fixed by introducing the notion of strong computable type: a compact space X has strong computable type if for every oracle $O \subseteq N$ and every copy Y of X, if Y is semicomputable relative to O then Y is computable relative to O (and similarly for pairs). We carry out a thorough analysis of strong computable type. We show that it is equivalent to being minimal for some property of low descriptive complexity (Theorems 4.7 and 4.11). In particular, the next result gives a relatively simple recipe to prove that a space (or pair) has strong computable type.

Theorem 2 (Theorem 4.8).

If $(X, A)$ is minimal satisfying some $Σ_{2}^{0}$ topological invariant, then $(X, A)$ has strong computable type.

The descriptive complexity is measured in the hyperspace of compact sets with the Vietoris or upper Vietoris topology. It is an open question whether Theorem 2 is an equivalence, although we do not expect so. As far as we know, being minimal for some $Σ_{2}^{0}$ invariant is therefore a distinguished way of having strong computable type, from which particular consequences can be derived, for instance about the level of uniformity of the computation that is involved in strong computable type. If the pair is minimal for some $Σ_{2}^{0}$ invariant, then the non-uniformity level of the computation is precisely what is called non-deterministic computability, captured by the Weihrauch degree of choice over $N$ (Theorem 5.17).

These structural results have many interesting consequences. We give a purely topological necessary condition, which is sufficient up to some oracle (Corollaries 5.1 and 5.3). We show that for finite simplicial complexes, computable type is equivalent to strong computable type (Corollary 5.6). We explain why for some spaces it is difficult to produce a semicomputable copy which is not computable (Theorem 5.11), contrasting with obvious examples such as the line segment or the n-dimensional ball.

When Y is a fixed compact ANR and X is a varying compact space, we show how the set $[X; Y]$ of continuous functions from X to Y quotiented by homotopy can be computed from X, with no computability assumptions about Y (Theorem 6.7). A particularly interesting case is when Y is the n-dimensional sphere $S_{n}$ . This analysis immediately induces topological invariants of low descriptive complexity, which are very classical in topology.

Theorem 3.
The following topological invariants are $Σ_{2}^{0}$ in the upper Vietoris topology: $\begin{array}{l} (X, A) \in E_{n} ⟺ there is a continuous function f : A \to S_{n} having no continuous extension F : X \to S_{n}, \\ X \in H_{n} ⟺ there is a continuous function f : X \to S_{n} which is not null-homotopic . \end{array}$

We thoroughly study these topological invariants and revisit several results of the literature, showing how they can be obtained by identifying a suitable $Σ_{2}^{0}$ invariant for which the space or pair is minimal. These results show that the theory indeed applies, and they strengthen the previous results because they give more information and can be used to derive new results. For instance,
The pair $(B_{n + 1}, S_{n})$ is $E_{n}$ -minimal,

Every closed n-manifold is $H_{n}$ -minimal.
We also consider other examples from the literature such as chainable and circularly chainable sets, pseudo-cubes, and as a side result give a few new examples.

Our framework often provides simpler proofs of the results, separating the argument into a computability-theoretic part (showing that a topological invariant is $Σ_{2}^{0}$ ) and a purely topological one (showing that a space is minimal for that invariant), both parts relying heavily on classical topological theorems. It is informative to compare the original proof of a previous result with the argument obtained by unfolding the proof using our framework. It turns out that sometimes the underlying arguments are essentially the same – it is the case for chainable sets and pseudo-cubes. However in other cases, the underlying argument is very different, e.g. for manifolds. In this case the new argument gives more information, providing for instance a precise measure of the non-uniformity of the computation, and also implying a new result for free, namely that cones of manifolds have (strong) computable type. Note that there is a price to pay: the proof heavily relies on results in algebraic topology about homology and cohomology of manifolds, while the proof given in [23] is locally and only uses the properties of balls and spheres, notably some form of Brouwer’s fixed point theorem.

Let us finally discuss the scope of our approach. Several results in the literature establish a computable type property for non-compact spaces, for instance in [7] or [24]; in this article, we consider compact spaces only. The compactness assumption is central and it is not clear how the theory would extend beyond compact spaces. Some of the previous results used slight variations on the notion of computable type, e.g. in [22], notably defining semicomputability as effective closedness rather than effective compactness, at the price of requiring extra assumptions on the ambient space, such as effective local compactness. In this article, we use the notion of effective compactness which behaves more smoothly.

The article is organized as follows. In Section 2, we present the standard concepts of computability over topological spaces. In Section 3 we recall the definition of computable type and prove that some of the variations of this introduced in the literature are actually equivalent. In Section 4 we introduce the notion of strong computable type and develop the theory. We obtain characterizations using descriptive set theory on the hyperspace of compact subsets of the Hilbert cube. In Section 5 we exploit these characterizations and obtain several results that improve our understanding of strong computable type. In Section 6, we show how the classical notion of Absolute Neighborhood Retract (ANR) behaves well in terms of computability, and allows to define topological invariants of low descriptive complexity, expressing extensibility and null-homotopy of continuous functions to ANRs. In Section 7 we study these invariants in more details. We finally apply the whole theory in Section 8 to revisit many previous results about computable type.
2. Background on computable topology

We give some background about computable aspects of topological spaces: computable $T_{0}$ -spaces, computable separation axioms, computability of subsets, the Hilbert cube.

First of all, let us recall enumeration reducibility, which enables one to define a notion of computable reduction between points of countably-based topological spaces.

2.1. Enumeration reducibility

We will mainly use the following notion from computability theory: a set $A \subseteq N$ is computably enumerable (c.e.) if there exists a Turing machine that, on input $n \in N$ , halts if and only if $n \in A$ . An enumeration of A is any function $f : N \to N$ such that $A = {n \in N : \exists p \in N, f (p) = n + 1}$ . A set is c.e. if and only if it has a computable enumeration. These notion immediately extends to subsets of countable sets, whose elements can be encoded by natural numbers.

As we will see soon, a point of a countably-based topological space can be identified with a set of natural numbers, namely the set indices of its basic neighborhoods. Therefore, relative computability between points will be conveniently expressed using enumeration reducibility, which we recall now.

Definition 2.1.
Let $A, B \subseteq N$ . We say that A is enumeration reducible to B, written $A ⩽_{e} B$ , if one of the following equivalent statements holds:
There is an effective procedure producing an enumeration of A from any enumeration of B.

There exists a c.e. set $W \subseteq N$ such that, for all $x \in N$ , $\begin{matrix} x \in A ⟺ there exists a finite set D \subseteq B such that ⟨ x, D ⟩ \in W . \end{matrix}$

For every oracle $O \subseteq N$ , if B is c.e. relative to O then A is c.e. relative to O.

In condition (2), $⟨ x, D ⟩$ denotes the encoding of the pair of finite objects x and D into a natural number. Equivalence between (2) and (3) is due to Selman [39].
2.2. Computable $T_{0}$ -spaces

Definition 2.2.
A computable $T_{0}$ -space is a tuple $(X, τ, {(B_{i})}_{i \in N})$ where $(X, τ)$ is a countably-based $T_{0}$ topological space and ${(B_{i})}_{i \in N}$ is a numbered basis of τ such that there exists a c.e. set $E \subseteq N^{3}$ satisfying $B_{i} \cap B_{j} = ⋃_{k : (i, j, k) \in E} B_{k}$ .

We will often denote a computable $T_{0}$ -space by $(X, τ)$ , the numbered basis being implicit. When several topological spaces are involved, we write $B_{i}^{X}$ for the basis of the space X. A subset Y of a computable $T_{0}$ -space $(X, τ)$ is also a computable $T_{0}$ -space, by taking the subspace topology and the numbered basis $B_{i}^{Y} = Y \cap B_{i}^{X}$ . The product of two computable $T_{0}$ -spaces is naturally a computable $T_{0}$ -space.

In a computable $T_{0}$ -space $(X, τ)$ , a point can be identified with the set of its basic neighborhoods, therefore the computability properties of a point of such a space is entirely captured by the enumeration degree of its neighborhood basis. This idea is explored in depth by Kihara and Pauly in [29]. In particular, a computable reduction between points can be defined using enumeration reducibility as follows.
Definition 2.3.
Let $(X, τ_{X})$ and $(Y, τ_{Y})$ be computable $T_{0}$ -spaces. A point x in $(X, τ_{X})$ is computable relative to a point y in $(Y, τ_{Y})$ if $\begin{matrix} {i \in N : x \in B_{i}^{X}} ⩽_{e} {i \in N : y \in B_{i}^{Y}} . \end{matrix}$

A function $f : X \to Y$ between computable $T_{0}$ -spaces is computable if and only if for every $x \in X$ , $f (x)$ is computable relative to x in a uniform way, i.e. using the same machine in the reduction. Equivalently, $f : X \to Y$ is computable if the sets $f^{- 1} (B_{i}^{Y})$ are effectively open, uniformly in i.

Let us recall some notions of computability of sets.
Definition 2.4.
A set A in a computable $T_{0}$ -space $(X, τ, {(B_{i})}_{i \in N})$ is:
Effectively compact, or semicomputable, if it is compact and the set $\begin{matrix} {(i_{1}, \dots, i_{n}) \in N^{} : A \subseteq B_{i_{1}} \cup \dots \cup B_{i_{n}}} \end{matrix}$ is c.e.

Computably overt if the set ${i \in N : A \cap B_{i} \neq \emptyset}$ is c.e.

Computable if it is effectively compact and computably overt.

Effectively open or $Σ_{1}^{0}$ if there exists a c.e. set $E \subseteq N$ such that $A = ⋃_{i \in E} B_{i}$ .

Effectively closed or $Π_{1}^{0}$ if its complement is effectively open.
A pair $(A, L)$ is semicomputable if A and L are semicomputable.

We will use the word semicomputable* when talking about a subset of a space, and effectively compact when talking about the space itself.

The image of a (semi)computable set under a computable function is a (semi)computable set.

The next result is simple but very powerful and central in many arguments: closed sets are preserved by taking existential quantification over a compact set, and it holds effectively. Equivalently, open sets are preserved by taking universal quantification over a compact set, effectively so. It is a standard folklore result in computable analysis that can drastically simplify many arguments. It can be found in [34] for instance, but we include a proof for completeness.
Proposition 2.5 (Quantifying over a compact space).

Let X, Y be computable $T_{0}$ -spaces such that Y is effectively compact.

If $R \subseteq X \times Y$ is effectively closed, then its existential quantification $\begin{matrix} R^{\exists} : = {x \in X : \exists y \in Y, (x, y) \in R} \end{matrix}$ is effectively closed as well.

If $R \subseteq X \times Y$ is effectively open, then its universal quantification $\begin{matrix} R^{\forall} : = {x \in X : \forall y \in Y, (x, y) \in R} \end{matrix}$ is effectively open as well.

Of course the two items are equivalent by taking complements, but we make both of them explicit as they are equally useful.

Proof.
We prove the second item, the first one is obtained by taking complements. As R is effectively open, there exists a c.e. set $E \subseteq N^{2}$ such that $R = ⋃_{(i, j) \in E} B_{i}^{X} \times B_{j}^{Y}$ . One has $\begin{array}{l} (1) & x \in R^{\forall} & ⟺ {x} \times Y \subseteq R \\ (2) & ⟺ \exists finite set L \subseteq E, {x} \times Y \subseteq ⋃_{(i, j) \in L} B_{i}^{X} \times B_{j}^{Y} \end{array}$ because ${x} \times Y$ is compact. Let $F$ be the collection of (indices of) finite sets $L \subseteq E$ such that $Y \subseteq ⋃_{(i, j) \in L} B_{j}^{Y}$ . As Y is effectively compact, $F$ is a c.e. set. For each $L \in F$ , let $U_{L} = ⋂_{(i, j) \in L} B_{i}^{X}$ . The equivalence (2) implies that $R^{\forall} = ⋃_{L \in F} U_{L}$ , which is an effective open set. □

Descriptive set theory and its effective version provide notions of complexity for subsets of topological spaces ([33]). We have already seen the classes $Σ_{1}^{0}$ and $Π_{1}^{0}$ . In this article, we will also need another class.
Definition 2.6.
A set A in a computable $T_{0}$ -space $(X, τ, {(B_{i})}_{i \in N})$ is $Σ_{2}^{0}$ if it can be expressed as $\begin{matrix} A = ⋃_{n \in N} A_{n} ∖ B_{n} \end{matrix}$ where $A_{n}$ , $B_{n}$ are uniformly effective closed sets (i.e. $Π_{1}^{0}$ ).

Observe that one can equivalently require $A_{n}$ , $B_{n}$ to be effectively open, as $A_{n} ∖ B_{n} = (X ∖ B_{n}) ∖ (X ∖ A_{n})$ . This class is traditionally defined on computable metric spaces (those spaces are defined in Section 2.3 below), where it is equivalently defined without the sets $B_{n}$ . The definition given here was proposed for non-Hausdorff spaces by Scott [37] and Selivanov [38], to make sure that the classes $Σ_{1}^{0}$ and $Π_{1}^{0}$ are contained in the class $Σ_{2}^{0}$ .
2.3. Classes of computable $T_{0}$ spaces

Each topological separation axiom has a computable version, we recall some of them. These definitions can be found in [36] for instance.

Definition 2.7.

A computable metric space is a tuple $(X, d, α)$ , where $(X, d)$ is a metric space and $α : N \to X$ is a dense sequence in $(X, d)$ such that the real numbers $d (α_{i}, α_{j})$ are uniformly computable.

A computable $T_{0}$ -space $(X, τ, {(B_{i})}_{i \in N})$ is computably Hausdorff if the diagonal $Δ = {(x, x) : x \in X}$ is an effectively closed subset of $X \times X$ , i.e. if there exists some c.e. set $D \subseteq N^{2}$ satisfying $\begin{matrix} (X \times X) ∖ Δ = {(x, y) \in X \times X : x \neq y} = ⋃_{(i, j) \in D} B_{i} \times B_{j} . \end{matrix}$

Remark 2.8.
The following facts are standard and can be found in [34] for instance:
A computable metric space is a computable $T_{0}$ -space, by taking the basis of metric balls $B_{d} (α_{i}, q)$ with $q > 0$ rational; these balls are called the rational balls.

A computable metric space is computably Hausdorff.

In a computably Hausdorff space which is effectively compact, a set is semicomputable (i.e., effectively compact) if and only if it is effectively closed.

The next fact is another powerful feature of effective compactness: in certain situations, if a computable function is injective, then its inverse is automatically computable. Proposition 2.9.
Let X be a computable $T_{0}$ -space, Y a computably Hausdorff space and $K \subseteq X$ a semicomputable set. If $f : K \to Y$ is a computable injective function, then its inverse $f^{- 1} : f (K) \to K$ is computable.
Proof.
It is a folklore result but we include a proof for completeness. We need to show that for a basic open set $B_{i}$ of X, its preimage under $f^{- 1}$ is effectively open in $f (K)$ , uniformly in i. The preimage is precisely $f (B_{i} \cap K)$ . As f is injective, $f (B_{i} \cap K) = f (K) ∖ f (K ∖ B_{i})$ . As $K ∖ B_{i}$ is semicomputable, its image $f (K ∖ B_{i})$ is semicomputable as well. As Y is computably Hausdorff, $f (K ∖ B_{i})$ is effectively closed, so its complement is effectively open, as wanted. □

2.3.1. The Hilbert cube

The Hilbert cube will play a central role in this article, because every computable metric space computably embeds into it, so one can work in this space without loss of generality.

Definition 2.10.
The Hilbert cube is the space $Q = {[0, 1]}^{N}$ endowed with the complete metric $\begin{matrix} d_{Q} (x, y) = \sum_{i} 2^{- i} | x_{i} - y_{i} | . \end{matrix}$

Here are some important facts about the Hilbert cube.
Fact 2.11.
The Hilbert cube Q satisfies the following properties:
Let ${(α_{i})}_{i \in N}$ be a computable enumeration of the points of Q having rational coordinates, finitely many of them being non-zero. It makes $(Q, d_{Q}, α)$ a computable metric space.

The Hilbert cube is effectively compact.

Therefore, a set $X \subseteq Q$ is semicomputable if and only if its complement is an effective open set.

Every computable metric space embeds effectively into the Hilbert cube. More precisely, for every computable metric space $(X, d, α)$ there exists a computable embedding $f : X \to Q$ such that $f^{- 1}$ is computable, defined as $f (x) = {(1 / (1 + d (x, α_{i})))}_{i \in N}$ .

In particular, the fourth item implies that the semicomputable subsets of arbitrary computable metric spaces are no more general than the semicomputable subsets of Q.
3. Computable type and the Hilbert cube

The notion of computable type takes its origins in an article by Miller [32], was studied by Iljazović et al. in [7,9–11,18,21–24,26] and by the authors in [2]. The first formal definition as given in [26].

Let us present the language needed to formulate definition of computable type.

Definition 3.1.
A pair $(X, A)$ consists of a compact metrizable space X and a compact subset $A \subseteq X$ . A copy of a pair $(X, A)$ in a topological space Z is a pair $(Y, B)$ such that $Y \subseteq Z$ is homeomorphic to X and A is sent to B by the homeomorphism.

If $(X, A)$ and $(Y, B)$ are two pairs embedded in a topological space Z, then we say that $(X, A)$ is a subpair of $(Y, B)$ , or is contained in $(Y, B)$ if $X \subseteq Y$ and $A \subseteq B$ . We then write $(X, A) \subseteq (Y, B)$ . We say that $(X, A)$ is strictly contained in $(Y, B)$ , or is a proper subpair of $(Y, B)$ , if in addition $X \neq Y$ (note that A may equal B), and we write $(X, A) ⊊ (Y, B)$ .
Definition 3.2.
If $(X, A)$ and $(Y, B)$ are two pairs, then a function between pairs $f : (X, A) \to (Y, B)$ is a function $f : X \to Y$ such that $f (A) \subseteq B$ .
Definition 3.3.
A compact metrizable space X has computable type if for every copy Y in the Hilbert cube, if Y is semicomputable then Y is computable.

A compact pair $(X, A)$ has computable type if for every copy $(Y, B)$ of $(X, A)$ in the Hilbert cube, if $(Y, B)$ is semicomputable then Y is computable.

Note that the notion for pairs subsumes the notion for single sets, by considering the pair $(X, \emptyset)$ .

Originally, two notions of computable type were studied in [21] and [11] respectively, using other spaces than the Hilbert cube. Precisely,

A pair $(X, A)$ has computable type on computable metric spaces if for every copy $(Y, B)$ of the pair in any computable metric space Z, if $(Y, B)$ is semicomputable then Y is computable.

A pair $(X, A)$ has computable type on computably Hausdorff spaces if for every copy $(Y, B)$ of the pair in any computably Hausdorff space Z, if $(Y, B)$ is semicomputable then Y is computable.

In this section, we prove that the distinction between computable type on computable metric spaces and computably Hausdorff spaces is unnecessary, because they are actually equivalent. Moreover, it is sufficient to consider the Hilbert cube only, as in Definition 3.3. Therefore there is no more need to distinguish between these definitions, and the results about computable type on computable metric spaces immediately extend to computably Hausdorff spaces (for instance, the results in [21,23] imply the results in [11,26]).
Theorem 3.4.
For a pair $(X, A)$ , the following statements are equivalent:
$(X, A)$ has computable type (on the Hilbert cube).

$(X, A)$ has computable type on computable metric spaces.

$(X, A)$ has computable type on computably Hausdorff spaces.

We now proceed with the proof of Theorem 3.4. The implications $(3) \Rightarrow 2 \Rightarrow (1)$ are straightforward, we only need to prove $(1) \Rightarrow (3)$ . The idea is that a compact subspace of a Hausdorff space is metrizable, so embedding a compact set in a Hausdorff space implicitly induces an embedding in a metric space. We need to make this argument effective. We will use Schröder’s effective version of Urysohn metrization theorem [36], so we need to introduce the computable version of regular spaces.
Definition 3.5.
A computable $T_{0}$ -space $(X, τ)$ is computably regular if there is a computable procedure associating to each basic open set $B_{n}$ a sequence of effective open sets ${(U_{k})}_{k \in N}$ and a sequence of effective closed sets ${(F_{k})}_{k \in N}$ such that $U_{k} \subseteq F_{k} \subseteq B_{n}$ and $B_{n} = ⋃_{k} U_{k}$ .
Proposition 3.6.
Let $(X, τ)$ be a computable $T_{0}$ -space. If $(X, τ)$ is effectively compact and computably Hausdorff, then it is computably regular.
Proof.
Let $D \subseteq N^{2}$ witness that the space is computably Hausdorff. Let $n \in N$ . The set $K = X ∖ B_{n}$ is effectively compact, so one can compute an enumeration ${(L_{k})}_{k \in N}$ of all the finite sets $L \subseteq D$ such that $K \subseteq ⋃_{(i, j) \in L} B_{j}$ . To each such $L_{k}$ associate the pair $(U_{k}, F_{k})$ defined by $\begin{array}{l} U_{k} = ⋂_{(i, j) \in L_{k}} B_{i} \\ F_{k} = X ∖ ⋃_{(i, j) \in L_{k}} B_{j} . \end{array}$ By construction, $U_{k}$ and $F_{k}$ are uniformly effectively open and closed respectively.

Next, $U_{k}$ is contained in $F_{k}$ because $B_{i}$ is disjoint from $B_{j}$ for all $(i, j) \in L_{k} \subseteq D$ . As $X ∖ B_{n} \subseteq ⋃_{(i, j) \in L_{k}} B_{j}$ , one has $F_{k} = X ∖ ⋃_{(i, j) \in L_{k}} B_{j} \subseteq B_{n}$ .

Finally, we show that $B_{n} = ⋃_{k} U_{k}$ . Let $x \in B_{n}$ . As $x \notin K$ , the compact set ${x} \times K$ is contained in $⋃_{(i, j) \in D} B_{i} \times B_{j}$ , so there exists a finite set $L \subseteq D$ such that ${x} \times K \subseteq ⋃_{(i, j) \in L} B_{i} \times B_{j}$ . This inclusion is still satisfied if one removes from L the pairs $(i, j)$ such that $x \notin B_{i}$ . Let $L^{'} \subseteq L$ be the result of this operation. There exists k such that $L^{'} = L_{k}$ , and $x \in U_{k}$ . □

Schröder proved the following effective Urysohn metrization theorem (Theorem 6.1 in [36]): every computably regular space X admits a computable metric, i.e. a computable function $d : X \times X \to R$ which is a metric that induces the topology of the space (note that it does not mean that X is a computable metric space, because it may not contain a dense computable sequence). The proof of that result implies the next lemma.
Lemma 3.7.
If $(X, τ)$ is a computably regular space, then there exists a computable injection $h : X \to Q$ .
Proof.
The proof of Theorem 6.1 in [36] consists in building a computable sequence of functions $g_{i} : X \to [0, 1]$ that separates points, i.e. such that for all $x, y \in X$ with $x \neq y$ , $g_{i} (x) \neq g_{i} (y)$ for some $i \in N$ . The metric d is then defined as $d (x, y) = \sum_{i} 2^{- i} | g_{i} (x) - g_{i} (y) |$ . In our case, we simply define $h (x) = {(g_{i} (x))}_{i \in N}$ . □
Corollary 3.8.
If K is a semicomputable set in a computably Hausdorff space $(X, τ)$ , then there exists a computable embedding $h : K \to Q$ whose inverse is computable.
Proof.
Consider the subspace $(K, τ_{K})$ with the induced topology $τ_{K} = {U \cap K : U \in τ}$ . Because it is a subspace of a computably Hausdorff space, it is computably Hausdorff as well. As K is semicomputable, as a set, it is effectively compact as a space. Therefore, Proposition 3.6 implies that $(K, τ_{K})$ is computably regular. By Lemma 3.7, there exists a computable injection $h : K \to Q$ . By Proposition 2.9, its inverse is computable. □

Now, we prove our theorem. Proof of Theorem 3.4.
We prove $(1) \Rightarrow (3)$ . If $(K, L)$ is a pair that has computable type (on the Hilbert cube), $(X, τ)$ is a computably Hausdorff space and $f : K \to X$ is an embedding such that $f (K)$ and $f (L)$ are semicomputable, then by Corollary 3.8, there exists a computable embedding $h : f (K) \to Q$ such that $h^{- 1}$ is computable. Hence, $h \circ f : K \to Q$ is an embedding such that $h \circ f (K)$ and $h \circ f (L)$ are semicomputable. As $(K, L)$ has computable type, the set $h \circ f (K)$ is computable. The set $f (K)$ is the image of the computable set $h \circ f (K)$ by the computable function $h^{- 1}$ , so $f (K)$ is a computable set. As a result, $(K, L)$ has computable type on computably Hausdorff spaces. □

4. Strong computable type

The notion of computable type suffers from a severe drawback: if a compact metrizable space has no semicomputable copy in the Hilbert cube, then it vacuously has computable type. As there are only countably many semicomputable sets, most compact metrizable spaces have computable type for no good reason. In particular, there is no hope to obtain interesting characterizations of this notion.

This observation leads us to define a stronger and more robust notion: having computable type relative to any oracle. This definition solves the previous issue and has the advantage of lending itself to topological analysis, notably in terms of the topologies on the hyperspace $K (Q)$ of compact subsets of Q, which enables us to obtain topological characterizations.

4.1. Definition

We first define the notion of strong computable type, which is a simple relativization of Definition 3.3.

Definition 4.1.
A compact metrizable space X has strong computable type if for every oracle O and every copy Y of X in the Hilbert cube, if Y is semicomputable relative to O, then Y is computable relative to O.

A pair $(X, A)$ has strong computable type if for every oracle O and every copy $(Y, B)$ of $(X, A)$ in Q, if $(Y, B)$ is semicomputable relative to O, then Y is computable relative to O.
Remark 4.2.
All the spaces which were proved to have computable type in the literature [2,7,9–11,18,21–24,26,32] actually have strong computable type because the proofs hold relative to any oracle.

Note that the proof that the definition of computable type reduces to the Hilbert cube (Theorem 3.4) also extends to strong computable type, so defining strong computable type on computable metric spaces or computably Hausdorff spaces would yield equivalent notions.

We will see in Section 5.2 that for finite simplicial complexes, strong computable type is equivalent to computable type (Corollary 5.6), refining the results in [2]. More generally, we expect that for natural spaces, the notion of strong computable type is actually no stronger than the notion of computable type.

Intuitively, a pair has strong computable type iff for every copy $(Y, B)$ in the Hilbert cube, the set Y can be fully computed if we are only given the compact information about Y and B. We make it precise by seeing Y and B as points of the hyperspace of compact subsets of the Hilbert cube with suitable topologies, as follows.
Definition 4.3.
Let $K (Q)$ be the hyperspace of Q, i.e. the space of compact subsets of Q. It can be equipped with:
The upper Vietoris topologyn $τ_{up V}$ generated by the sets of the form ${K \in K (Q) : K \subseteq U}$ , where U ranges over the open subsets of Q.

The lower Vietoris topology $τ_{low V}$ generated by the sets of the form ${K \in K (Q) : K \cap U \neq \emptyset}$ , where U ranges over the open subsets of Q.

The Vietoris topology $τ_{V}$ generated by $τ_{up V}$ and $τ_{low V}$ .

These three topological spaces are computable $T_{0}$ -spaces. A countable basis of $τ_{up V}$ is obtained by taking U among the finite unions of rational balls of Q. A countable subbasis of $τ_{low V}$ is obtained by taking U among the rational balls of Q, and adding $K (Q)$ to the subbasis. The space $(K (Q), τ_{V})$ is also a computable metric space, by taking the Hausdorff metric, and the dense sequence of finite sets of rational points of Q with finitely many non-zero coordinates. Moreover, these three spaces are effectively compact (see Section 5 in [25] for instance; it is sufficient to prove it for the stronger topology $τ_{V}$ ).

Each computability notion of compact set can then be seen as the notion of computable point in one of these topologies. In particular, for a compact set $K \subseteq Q$ , $\begin{array}{l} K is semicomputable ⟺ K is a computable element of (K (Q), τ_{up V}), \\ K is computable ⟺ K is a computable element of (K (Q), τ_{low V}) . \end{array}$ The topology $τ_{low V}$ induces the notion of computably overt set, which will not be discussed in this article. It is easy to get confused with the many different uses of the word “computable”, but we will always make it clear what meaning is used.

The property of having strong computable type can then be rephrased as relative computability between elements of $K (Q)$ with various topologies, using the notion of relative computability given by Definition 2.3. As relative computability is expressed in terms of enumeration reducibility, Definition 2.1 then provides equivalent formulations of this notion, which we will implicitly use in the rest of the article. Let us state such a formulation for clarity.
Proposition 4.4.
For a pair $(X, A)$ , the following statements are equivalent:
$(X, A)$ has strong computable type.

For every copy $(Y, B)$ of $(X, A)$ in Q, the element Y of the space $(K (Q), τ_{V})$ is computable relative to the element $(Y, B)$ of the product space $(K^{2} (Q), τ_{up V}^{2})$ .

Proof.
The second statement is about relative computability, which is defined as enumeration reducibility between neighborhood bases of Y and $(Y, B)$ . The definition of strong computable type is precisely formulation (3) of enumeration reducibility (Definition 2.1). □

It will have interesting consequences, because it enables one to use topology and descriptive set theory on $K (Q)$ to analyze a computability-theoretic property.
4.2. A first characterization

We give a first characterization of strong computable type. This result is related to the characterization obtained by Jeandel in [27] of the sets $A \subseteq N$ that are total, i.e. whose complement $N ∖ A$ is enumeration reducible to A.

We first need two definitions.

Definition 4.5.
A property of pairs is a subset $P$ of $K (Q) \times K (Q)$ . It is a topological invariant, or shortly an invariant, if for every $(X, A) \in P$ , every copy $(Y, B)$ of $(X, A)$ is in $P$ .

We recall that $(Y, B)$ is a proper subpair of $(X, A)$ , written $(Y, B) ⊊ (X, A)$ , if $Y ⊊ X$ and $B \subseteq A$ .
Definition 4.6.
Let $P$ be a property of pairs. A pair $(X, A) \subseteq Q$ is $P$ -minimal if $(X, A) \in P$ and for every proper subpair $(Y, B) ⊊ (X, A)$ , one has $(Y, B) \notin P$ .

We can now state our first characterization of strong computable type.
Theorem 4.7.
For a pair $(X, A)$ , the following statements are equivalent:
$(X, A)$ has strong computable type.

For every copy $(Y, B)$ of $(X, A)$ in Q, there exists a property $P$ of pairs which is $Π_{1}^{0}$ in the topology $τ_{up V}^{2}$ and such that $(Y, B)$ is $P$ -minimal.

Proof.
We fix an arbitrary copy of $(X, A)$ in Q (that we still call $(X, A)$ ) and prove that the following equivalence holds for that copy: the set of basic $τ_{V}$ neighborhoods of X is enumeration reducible to the set of basic $τ_{up V}^{2}$ neighborhoods of $(X, A)$ iff there exists a $Π_{1}^{0}$ property $P$ such that $(X, A)$ is $P$ -minimal.

$(2) \Rightarrow (1)$ . Assume that $P$ is $Π_{1}^{0}$ in $τ_{up V}^{2}$ and that $(X, A)$ is $P$ -minimal. Given the $τ_{up V}^{2}$ neighborhoods of $(X, A)$ , we need to enumerate the rational balls U intersecting X. Note that U intersects X iff $X ∖ U$ is a proper subset of X; as $(X, A)$ is $P$ -minimal, it is equivalent to $(X ∖ U, A ∖ U) \notin P$ . Given $(X, A)$ in the topology $τ_{up V}^{2}$ , one can compute $(X ∖ U, A ∖ U)$ in the topology $τ_{up V}^{2}$ (indeed, $X ∖ U \subseteq V ⟺ X \subseteq U \cup V$ , and similarly for $A ∖ U$ ) so one can semi-decide whether $(X ∖ U, A ∖ U) \notin P$ , i.e. whether U intersects X.

$(1) \Rightarrow (2)$ . Consider a machine M which takes any enumeration of the basic $τ_{up V}^{2}$ -neighborhoods of $(X, A)$ and enumerates the open balls intersecting X. Let $U$ be the set of pairs $(X^{'}, A^{'})$ on which M fails in the following sense: after reading a finite sequence of $τ_{up V}^{2}$ neighborhoods of the pair $(X^{'}, A^{'})$ , the machine enumerates an open ball U such that $X^{'} \cap \overline{U} = \emptyset$ , where $\overline{U}$ is the corresponding closed ball. Let $P$ be the complement of $U$ . Note that $(X, A) \in P$ because the machine does not fail on $(X, A)$ .

We first show that $U$ is effectively open in $τ_{up V}^{2}$ . If $σ = σ_{0} \dots σ_{k}$ is a finite sequence of basic $τ_{up V}^{2}$ -open sets and U is a basic open subset of Q, then let $\begin{matrix} U_{(σ, U)} = {(X^{'}, A^{'}) : \forall i ⩽ k, (X^{'}, A^{'}) \in σ_{i} and X^{'} \subseteq Q ∖ \overline{U}} . \end{matrix}$ It is an effective $τ_{up V}^{2}$ -open set, and $U$ is the union of all the $U_{(σ, U)}$ such that M outputs U after reading σ, so it is a c.e. union. Therefore $U$ is an effective $τ_{up V}^{2}$ -open set and $P$ is $Π_{1}^{0}$ in $τ_{up V}^{2}$ .

We now show that $(X, A)$ is $P$ -minimal. If $(X^{'}, A^{'})$ is a proper subpair of $(X, A)$ , then there exists a ball U intersecting X such that $\overline{U}$ is disjoint from $X^{'}$ . On an arbitrary enumeration of the $τ_{up V}^{2}$ -neighborhoods of $(X, A)$ , the machine eventually outputs U after reading a finite sequence σ. As $(X^{'}, A^{'}) \subseteq (X, A)$ , the $τ_{up V}^{2}$ -neighborhoods of $(X, A)$ are also $τ_{up V}^{2}$ -neighborhoods of $(X^{'}, A^{'})$ so the machine fails on $(X^{'}, A^{'})$ . Therefore, $(X^{'}, A^{'}) \in U$ , i.e. $(X^{'}, A^{'}) \notin P$ . We have shown that $(X, A)$ is $P$ -minimal. □

In particular, this characterization immediately implies a simple sufficient condition for having strong computable type.
Theorem 4.8.
Let $P$ be a topological invariant which is $Σ_{2}^{0}$ in $τ_{up V}^{2}$ . Every minimal element of $P$ has strong computable type.
Proof.
Let $P = ⋃_{n} P_{n} ∖ Q_{n}$ where each $P_{n}$ , $Q_{n}$ is $Π_{1}^{0}$ in $τ_{up V}^{2}$ . Assume that $(X, A)$ is $P$ -minimal and let $(Y, B)$ be a copy of $(X, A)$ in Q. This copy belongs to some $P_{n} ∖ Q_{n}$ . Let us show that $(Y, B)$ must be $P_{n}$ -minimal. Let $(Y^{'}, B^{'})$ be a proper subpair of $(Y, B)$ . The set $Q_{n}$ is $Π_{1}^{0}$ in $τ_{up V}^{2}$ so it is an upper set. As $(Y, B) \notin Q_{n}$ , $(Y^{'}, B^{'}) \notin Q_{n}$ as well. As $(Y, B)$ is $P$ -minimal, $(Y^{'}, B^{'}) \notin P$ , so $(Y^{'}, B^{'}) \notin P_{n}$ . Therefore, $(Y, B)$ is $P_{n}$ -minimal.

We have shown that each copy $(Y, B)$ of $(X, A)$ is $P_{n}$ -minimal for some n, so we can apply Theorem 4.7, implying that $(X, A)$ has strong computable type. □

We will see applications of this result in the sequel. Theorem 4.8 is only an implication and we will see later that the converse implication does not hold in general. However, in the next section we obtain a characterization of strong computable type using $Σ_{2}^{0}$ invariants and a weak form of minimality.

Discussion about minimality. When applying Theorem 4.7 and Theorem 4.8 to prove that a pair has strong computable type, one needs to show that a pair $(X, A)$ is $P$ -minimal for some $P$ . The definition of minimality involves all the proper subpairs $(Y, B) ⊊ (X, A)$ . However, because $P$ is $Π_{1}^{0}$ in $τ_{up V}^{2}$ , it is not necessary to consider all of them.

The reason is that the lower and upper Vietoris topologies interact nicely with the inclusion ordering on compact sets:

If a set $P \subseteq K (Q)$ is closed in $τ_{up V}$ or open in $τ_{low V}$ , then it is an upper set: if $K \subseteq K^{'} \subseteq Q$ and $K \in P$ , then $K^{'} \in P$ .

Dually, if $P$ is open in the topology $τ_{up V}$ or closed in the topology $τ_{low V}$ , then it is a lower set: if $K \subseteq K^{'} \subseteq Q$ and $K^{'} \in P$ , then $K \in P$ .

It gives a shortcut to prove that a pair $(X, A)$ is $P$ -minimal, when $P$ is an upper set, for instance when $P$ is $Π_{1}^{0}$ or more generally closed in the topology $τ_{up V}^{2}$ .
Definition 4.9.
Let $(X, A)$ be a pair and $F$ a family of proper subpairs of $(X, A)$ . We say that $F$ is cofinal if every proper subpair of $(X, A)$ is contained in some pair in $F$ .

The next result is elementary but very useful.
Lemma 4.10.
Let $P$ be a property of pairs which is an upper set. Let $(X, A) \in P$ and $F$ be cofinal. If no pair of $F$ is in $P$ then $(X, A)$ is $P$ -minimal.
Proof.
If $(Y, B) ⊊ (X, A)$ , then $(Y, B) \subseteq (Z, C) ⊊ (X, A)$ for some $(Z, C) \in F$ , by cofinality. As $(Z, C) \notin P$ by assumption and $P$ is an upper set, $(Y, B) \notin P$ . □

We will implicitly apply this observation, notably with the following families:
The family ${(Y, Y \cap A) : Y ⊊ X}$ is cofinal.

If $B$ is a basis of the topology of X consisting of non-empty open sets, then the family ${(X ∖ B, A ∖ B) : B \in B}$ is cofinal.

If A has empty interior in X, then the family ${(Y, A) : A \subseteq Y ⊊ X}$ is cofinal.

4.3. A characterization using invariants

In order to prove that a pair has strong computable type using Theorem 4.7, one needs to find a $Π_{1}^{0}$ property for each copy. In this section we improve the result by making the property less dependent on the copy. It is possible because there are countably many $Π_{1}^{0}$ properties, but uncountably many copies of a pair, so some property must work for “many” copies. The word “many” can be made precise by using Baire category on the space of continuous functions of the Hilbert cube to itself.

Theorem 4.11.
For a pair $(X, A)$ , the following statements are equivalent:
$(X, A)$ has strong computable type.

There exists a $Σ_{2}^{0}$ invariant $⋃_{n \in N} P_{n}$ , where the sets $P_{n}$ are uniformly $Π_{1}^{0}$ in $τ_{up V}^{2}$ , such that every copy of $(X, A)$ in Q is $P_{n}$ -minimal for some n.

Note that the invariant is more than a $Σ_{2}^{0}$ property, because it is a union of closed sets rather than a union of differences of closed sets. The rest of the section is devoted to the proof of this result.

The idea of the proof is that one of the $Π_{1}^{0}$ properties from Theorem 4.7 works for “many” copies of $(X, A)$ , in the sense of Baire category. We then transform this $Π_{1}^{0}$ property into a $Σ_{2}^{0}$ invariant. This transformation is an instance of Vaught’s transform [41]. Let us briefly explain this transform. There are several ways of defining an invariant out of a property $P$ . For instance, the set of pairs having at least one copy in $P$ is an invariant; the set of pairs whose copies are all in $P$ is another invariant. However, these two invariants can have very high descriptive complexities (typically $Σ_{1}^{1}$ and $Π_{1}^{1}$ respectively). Vaught’s transform is an intermediate way of converting a property into an invariant which almost preserves the descriptive complexity: the invariant is the set of pairs having “many” copies in $P$ , where “many” is expressed using Baire category. We now give the details.

We endow the space $C (Q)$ of continuous functions from Q to itself with the complete separable metric $\begin{matrix} ρ (f, g) = max_{x \in Q} d_{Q} (f (x), g (x)) . \end{matrix}$

If functions f, g are defined on $X \subseteq Q$ only, then we also define $ρ_{X} (f, g) = {max}_{x \in X} d_{Q} (f (x), g (x))$ .
Remark 4.12.
We will often use the following inequalities: $\begin{array}{l} (3) & ρ (f \circ h, g \circ h) ⩽ ρ (f, g), \\ (4) & ρ (f \circ g, {id}_{Q}) ⩽ ρ (f, {id}_{Q}) + ρ (g, {id}_{Q}) . \end{array}$ The second inequality holds because $ρ (f \circ g, {id}_{Q}) ⩽ ρ (f \circ g, g) + ρ (g, {id}_{Q}) ⩽ ρ (f, {id}_{Q}) + ρ (g, {id}_{Q})$ .

We can make $(C (Q), ρ)$ a computable metric space.
Lemma 4.13.
There exists a computable sequence of injective continuous functions $ϕ_{i} : Q \to Q$ that is dense in the metric ρ.
Proof.
We first build a dense computable sequence of functions $f_{i} : Q \to Q$ that are not necessarily injective. Say that an element $x \in Q$ is dyadic of order n if it has the form $x = (x_{0}, \dots, x_{n - 1}, 0, 0, 0, \dots)$ where each $x_{i}$ is a multiple of $2^{- n}$ . For each $n \in N$ , the finite set of dyadic elements of order n forms a regular grid. One can then define a piecewise affine map by assigning a dyadic element to each dyadic element of order n and interpolating affinely in between. All the possible such assignments provide a dense computable sequence of functions from Q to itself.

Every continuous function $f : Q \to Q$ can be approximated by injective continuous functions $g_{n} : Q \to Q$ defined as follows: let $g_{n} (x)$ be the sequence starting with the first n terms of $f (x)$ , appended with x. If f is computable then the functions $g_{n}$ are computable, uniformly. Therefore injective approximations of the functions $f_{i}$ give a computable dense sequence of injective functions. □
Definition 4.14.
Let $ϵ > 0$ . An ϵ-function is a continuous function $f : Q \to Q$ such that $ρ (f, {id}_{Q}) < ϵ$ . An ϵ-deformation of a pair $(X, A) \subseteq Q$ is the image $f (X, A) : = (f (X), f (A))$ of $(X, A)$ under an ϵ-function f.

Note that if f is an ϵ-function and g is a δ-function, then $f \circ g$ is an $(ϵ + δ)$ -function. Therefore, an ϵ-deformation of a δ-deformation of $(X, A)$ is a $(ϵ + δ)$ -deformation of $(X, A)$ .
Remark 4.15.
The notion of ϵ-function can be defined for partial functions $f : X \to Q$ , where $X \subseteq Q$ , by requiring $ρ_{X} (f, {id}_{X}) < ϵ$ . The notion of ϵ-deformation of $(X, A)$ does not change if we consider ϵ-functions define on Q or on X only, so we will freely use this flexibility in the sequel.

Indeed, if $f : X \to Q$ is an ϵ-function, then f has a continuous extension $\tilde{f} : Q \to Q$ which is an ϵ-function. The function $\tilde{f}$ can be defined as follows: let $f_{0} : Q \to Q$ be a continuous extension of f obtained by the Tietze extension theorem; let $δ > 0$ and $\tilde{f} (x) = (1 - λ_{x}) f_{0} (x) + λ_{x} x$ , where $λ_{x} = min (1, d_{Q} (x, X) / δ)$ (note that Q indeed allows convex combinations). $\tilde{f}$ is a continuous extension of f and if δ is sufficiently small, then $ρ (\tilde{f}, {id}_{Q}) < ϵ$ .

If a homeomorphism $f : X \to Y$ is an ϵ-function, then its inverse $f^{- 1} : Y \to X$ is an ϵ-function as well.
Definition 4.16.
Let $P$ be a property of pairs. We define an invariant $P^{}$ as follows: $(X, A) \in P^{}$ iff there exists a copy $(X^{'}, A^{'})$ of $(X, A)$ and an $ϵ > 0$ such that every ϵ-deformation of $(X^{'}, A^{'})$ is in $P$ .

The key observation about $P^{}$ is that its descriptive complexity is not too high, compared to the descriptive complexity of $P$ : if $P$ is $Π_{1}^{0}$ , then $P^{}$ is $Σ_{2}^{0}$ . Remark 4.17.
When $P$ is $Π_{1}^{0}$ (more generally closed) in $τ_{V}^{2}$ , $P^{}$ could be equivalently defined by considering injective ϵ-functions only, in which case ϵ-deformations of $(X^{'}, A^{'})$ would all be copies of $(X^{'}, A^{'})$ . Indeed, the injective continuous functions are dense in $C (Q)$ , so every ϵ-deformation of $(X^{'}, A^{'})$ is a limit, in the Vietoris topology, of ϵ-deformations by injective ϵ-functions; if the latter are all in $P$ , then every ϵ-deformation is also in $P$ as $P$ is closed in $τ_{V}^{2}$ .
Proof of Theorem 4.11.
For a rational $ϵ > 0$ , we define $P_{ϵ} = {(X, A) \subseteq Q : every ϵ -deformation of (X, A) is in P}$ . One has $P^{} = {(X, A) \subseteq Q : \exists ϵ > 0, (X, A) has a copy in P_{ϵ}}$ . Claim 4.18.
Let τ be either $τ_{V}^{2}$ or $τ_{up V}^{2}$ . If $P$ is $Π_{1}^{0}$ in τ then $P_{ϵ}$ is $Π_{1}^{0}$ in τ.
Proof.
The function $f \in C (Q) \mapsto f (X, A) \in (K^{2} (Q), τ)$ is continuous, $P$ is closed in τ and the functions $ϕ_{k}$ are dense in $C (Q)$ . Therefore, the quantification over the ϵ-functions can be replaced by a quantification over the k’s such that $ϕ_{k}$ is an ϵ-function: $(X, A) \in P_{ϵ}$ iff $\forall k \in N$ , $ρ (ϕ_{k}, {id}_{Q}) < ϵ$ implies $ϕ_{k} (X, A) \in P$ . It is a $Π_{1}^{0}$ predicate. □

Say that two pairs $(X, A)$ and $(Y, B)$ in Q are ϵ-homeomorphic if there exists a homeomorphism $f : (X, A) \to (Y, B)$ which is an ϵ-function (note that this relation is symmetric, because in this case $f^{- 1}$ is an ϵ-function as well). Claim 4.19.
If $(X_{0}, A_{0}) \subseteq Q$ and $(X_{1}, A_{1}) \subseteq Q$ are homeomorphic, then for every $ϵ > 0$ there exists i such that $ϕ_{i} (X_{0}, A_{0})$ and $(X_{1}, A_{1})$ are ϵ-homeomorphic.
Proof.
Let $f : (X_{0}, A_{0}) \to (X_{1}, A_{1})$ be a homeomorphism and let i be such that $ρ_{X_{0}} (ϕ_{i}, f) < ϵ$ . Let $ψ = ϕ_{i} \circ f^{- 1}$ . One has $ϕ_{i} (X_{0}, A_{0}) = ψ (X_{1}, A_{1})$ and $ρ_{X_{1}} (ψ, {id}_{Q}) = ρ_{X_{0}} (ϕ_{i}, f) < ϵ$ . □
Claim 4.20.
Let τ be either $τ_{V}^{2}$ or $τ_{up V}^{2}$ . If $P$ is $Π_{1}^{0}$ in τ then $P^{}$ is $Σ_{2}^{0}$ in τ.*
Proof.
Again, the idea is that we can replace the quantification over the copies, i.e. over the injective continuous functions, by a quantification over the $ϕ_{i}$ ’s. Precisely, let $\begin{matrix} P_{i, ϵ} = {(X, A) \subseteq Q : ϕ_{i} (X, A) \in P_{ϵ}} . \end{matrix}$ We show that $P^{} = ⋃_{i, ϵ} P_{i, ϵ}$ , which is $Σ_{2}^{0}$ .

If $(X, A)$ has a copy $(X^{'}, A^{'})$ in $P_{ϵ}$ , then there exists i such that $ϕ_{i} (X, A) \in P_{ϵ / 2}$ . Indeed, let i be such that $ϕ_{i} (X, A)$ is $ϵ / 2$ -homeomorphic to $(X^{'}, A^{'})$ by the previous claim. Every $ϵ / 2$ -deformation of $ϕ_{i} (X, A)$ is an ϵ-deformation of $(X^{'}, A^{'})$ , so it belongs to $P$ . Therefore $ϕ_{i} (X, A) \in P_{ϵ / 2}$ , hence $(X, A) \in P_{i, ϵ / 2}$ . □
Claim 4.21.
Assume that* $(X, A)$ is $P$ -minimal and that $(X, A) \in P_{ϵ}$ . For every copy $(X^{'}, A^{'})$ of $(X, A)$ , there exists i such that $(X^{'}, A^{'})$ is $P_{i, ϵ / 2}$ -minimal.
Proof.
Let $(X^{'}, A^{'})$ be a copy of $(X, A)$ . Let i be such that $ϕ_{i} (X^{'}, A^{'})$ is $ϵ / 2$ -homeomorphic to $(X, A)$ . As in the previous claim, $(X^{'}, A^{'}) \in P_{i, ϵ / 2}$ , and we show that $(X^{'}, A^{'})$ is $P_{i, ϵ / 2}$ -minimal.

If $(X^{″}, A^{″})$ is a proper subpair of $(X^{'}, A^{'})$ , then $ϕ_{i} (X^{″}, A^{″})$ is $ϵ / 2$ -homeomorphic to a proper subpair of $(X, A)$ . The latter is not in $P$ as $(X, A)$ was $P$ -minimal, and is an $ϵ / 2$ -deformation of $ϕ_{i} (X^{″}, A^{″})$ , so $ϕ_{i} (X^{″}, A^{″}) \notin P_{ϵ / 2}$ . In other words. $(X^{″}, A^{″}) \notin P_{i, ϵ / 2}$ . As a result, $(X^{'}, A^{'})$ is $P_{i, ϵ / 2}$ -minimal. □
Claim 4.22.
If $(X, A)$ has strong computable type, then there exists a $Π_{1}^{0}$ property $P$ , a copy $(X_{0}, A_{0}) \subseteq Q$ and an $ϵ > 0$ such that $(X_{0}, A_{0})$ is $P$ -minimal and $(X_{0}, A_{0}) \in P_{ϵ}$ .
Proof.
Assume that $(X, A) \subseteq Q$ has strong computable type. Let $I (Q) \subseteq C (Q)$ be the subspace of injective continuous functions $f : Q \to Q$ . It is a $G_{δ}$ -set: $I (Q) = ⋂_{n \in N} I_{n} (Q)$ where $\begin{matrix} I_{n} (Q) = {f \in C (Q) : \forall x, y \in Q, d (x, y) ⩾ 2^{- n} ⟹ f (x) \neq f (y)} \end{matrix}$ is open by Proposition 2.5, because it is obtained as a universal quantification of an open predicate over the compact space $Q \times Q$ (see Lemma 1.3.10 in [40] for a more detailed proof). Being a $G_{δ}$ -subset of the Polish space $C (Q)$ , the space $I (Q)$ is therefore Polish (Theorem 3.11 in [28]).

Theorem 4.7 implies that for each $f \in I (Q)$ there exists a $Π_{1}^{0}$ property $P$ (in $τ_{up V}^{2}$ ) such that $f (X, A)$ is $P$ -minimal. There are countably many $Π_{1}^{0}$ properties, so by Baire category on $I (Q)$ there exists a $Π_{1}^{0}$ -property $P$ , an $f_{0} \in I (Q)$ and an $ϵ > 0$ such that for “almost every” $f \in B (f_{0}, ϵ)$ , $f (X, A)$ is $P$ -minimal. By “almost every”, we mean for a dense set of functions $f \in B (f_{0}, ϵ)$ . It actually implies that for every continuous $f \in B (f_{0}, ϵ)$ the pair $f (X, A)$ is in $P$ because $P$ is closed and the injective functions are dense in the continuous ones by Lemma 4.13.

The copy $f_{0} (X, A)$ belongs to $P_{ϵ}$ but may not be $P$ -minimal. However, we can replace $f_{0}$ by any $f_{1} \in B (f_{0}, ϵ / 2)$ such that $f_{1} (X, A)$ is $P$ -minimal, and ϵ by $ϵ / 2$ . We then let $(X_{0}, A_{0}) = f_{1} (X, A)$ . □

Finally, we put everything together. Let $(X_{0}, A_{0})$ , $P$ and ϵ be begin by Claim 4.22. The $Σ_{2}^{0}$ invariant we are looking for is $P^{*} = ⋃_{i, ϵ} P_{i, ϵ}$ . Claim 4.21 implies that every copy of $(X, A)$ is $P_{i, ϵ}$ -minimal for some i, ϵ. □

5. Strong computable type: Further properties

In this section, we exploit the analysis developed so far to obtain a better structural understanding of strong computable type.

5.1. A topological necessary condition

We start with a purely topological understanding of the notion of strong computable type by identifying a topological necessary condition.

Corollary 5.1 (Necessary condition).

If a pair $(X, A) \subseteq Q$ has strong computable type, then there exists $ϵ > 0$ such that no sequence of ϵ-deformations of $(X, A)$ converges to a proper subpair of $(X, A)$ in the topology $τ_{up V}^{2}$ .

Proof.
From Theorem 4.7 and the proof of Theorem 4.11, $(X, A)$ has strong computable type iff there exist a property of pairs $P$ which is $Π_{1}^{0}$ in $τ_{up V}^{2}$ , a copy $(Y, B)$ of $(X, A)$ in Q which is $P$ -minimal, and an $ϵ > 0$ such that every ϵ-deformation of $(Y, B)$ is in $P$ .

As $P$ is closed in $τ_{up V}^{2}$ , every limit of ϵ-deformations of $(Y, B)$ in that topology also belongs to $P$ . As $(Y, B)$ is $P$ -minimal, no such limit is a proper subpair of $(Y, B)$ . The same result can be transferred to $(X, A)$ by using a homeomorphism $ϕ : (X, A) \to (Y, B)$ . Indeed, ϕ sends proper subpairs of $(X, A)$ to proper subpairs of $(Y, B)$ and if $δ > 0$ is sufficiently small, then ϕ sends δ-deformations of $(X, A)$ to ϵ-deformations of $(Y, B)$ . □

This necessary condition is almost sufficient and captures the purely topological aspects of strong computable type, in the sense that it is equivalent to the following relativization of strong computable type.
Definition 5.2.
A pair $(X, A)$ has strong computable type relative to an oracle O if for every copy $(Y, B)$ of $(X, A)$ in Q, there exists a machine with oracle O computing Y in $τ_{V}$ from $(Y, B)$ as an element of $(K^{2} (Q), τ_{up V}^{2})$ .
Corollary 5.3.
For a pair $(X, A)$ , the following statements are equivalent:
$(X, A)$ has strong computable type relative to some oracle.

There exists $ϵ > 0$ such that no sequence of ϵ-deformations of $(X, A)$ converges to a proper subpair of $(X, A)$ in the topology $τ_{up V}^{2}$ .

Proof.
The proof of Corollary 5.1 holds relative to any oracle, which shows $(1) \Rightarrow (2)$ . Now assume condition (2). Let $P$ be the closure, in $τ_{up V}^{2}$ , of the set of ϵ-deformations of $(X, A)$ . Let O be an oracle relative to which $P$ is $Π_{1}^{0}$ in $τ_{up V}^{2}$ . By definition, $P$ contains all the ϵ-deformations of $(X, A)$ and $(X, A)$ is $P$ -minimal by assumption. Therefore, we can apply the argument in the proof of Theorem 4.7, showing that $(X, A)$ has strong computable type relative to O. □

The countrapositive of Corollary 5.1 gives a sufficient condition implying that a pair does not have strong computable type. In [3], we prove an effective version which even shows that the pair does not have computable type, as follows.
Theorem 5.4.
Assume that $(X, A) \subseteq Q$ is semicomputable and that given $ϵ > 0$ one can compute $δ > 0$ such that ϵ-deformations of $(X, A)$ converge to a proper subpair $(Y, B) ⊊ (X, A)$ such that $d_{H} (Y, X) > δ$ . Then $(X, A)$ does not have computable type.

Note that neither the ϵ-deformations nor the limit Y are required to be computable. The computability assumption is only about the function sending ϵ to δ.

This result therefore identifies a general situation when computable type is equivalent to strong computable type.
5.2. The ϵ-surjection property

The following special case of Corollary 5.1 has a particularly simple formulation.

Corollary 5.5.
If $(X, A) \subseteq Q$ has strong computable type, then there exists $ϵ > 0$ such that every continuous function of pairs $f : (X, A) \to (X, A)$ satisfying $ρ_{X} (f, {id}_{X}) < ϵ$ must be surjective.
Proof.
Take ϵ from Corollary 5.1. If $f : (X, A) \to (X, A)$ is an ϵ-function, then $f (X, A)$ is an ϵ-deformation of $(X, A)$ which is a subpair of $(X, A)$ . By Corollary 5.1 it cannot be a proper subpair, which means that f must be surjective. □

We do not know whether converse of Corollary 5.5 holds, although we do not expect so. As we discuss now, it holds for particular pairs.

The property from Corollary 5.5 is a slight variation, actually a strengthening, of the following property introduced in [2]. A pair $(X, A) \subseteq Q$ has the ϵ-surjection property if every continuous function $f : X \to X$ satisfying $ρ_{X} (f, {id}_{X}) < ϵ$ and $f |_{A} = {id}_{A}$ is surjective. One of the main results from [2] is that for a simplicial pair, i.e. a pair $(X, A)$ consisting of a finite simplicial complex X and a subcomplex A, $(X, A)$ has computable type if and only if it has the ϵ-surjection property for some $ϵ > 0$ .

Putting all the results together, we obtain the following characterization for simplicial pairs.
Corollary 5.6.
For a simplicial pair $(X, A)$ , the following statements are equivalent:
$(X, A)$ has strong computable type.

$(X, A)$ has computable type.

There exists $ϵ > 0$ such that every continuous function $f : (X, A) \to (X, A)$ satisfying $ρ_{X} (f, {id}_{X}) < ϵ$ is surjective.

There exists $ϵ > 0$ such that every continuous function $f : (X, A) \to (X, A)$ satisfying $ρ_{X} (f, {id}_{X}) < ϵ$ and $f |_{A} = {id}_{A}$ is surjective.

Proof.
The following implications hold for any pair: $(1) \Rightarrow (2)$ and $(3) \Rightarrow (4)$ are straightforward, and $(1) \Rightarrow (3)$ is Corollary 5.5. The main result from [2] is $(2) \Leftrightarrow (4)$ . As usual, the proof of the implication $(4) \Rightarrow (2)$ holds relative to any oracle so it actually shows $(4) \Rightarrow (1)$ . Therefore we have all the implications. □
Example 5.7.
As already mentioned, we do not know whether the converse of Corollary 5.5 holds. However, there is a simple example showing that the ϵ-surjection property does not imply computable type in general. Consider the pair $(X, A)$ in $R^{2}$ defined as follows: $X = ⋃_{i \in N} X_{i}$ where $X_{0} = [0, 1] \times {0}$ and for $i ⩾ 1$ , $X_{i} = {2^{- i}} \times [0, 2^{- i}]$ and $A = {(2^{- i}, 2^{- i}) : i ⩾ 1} \cup {(0, 0)}$ (see Fig. 1).

Figure 1.
The pair $(X, A)$ in Example 5.7: it has the surjection property but does not have computable type.

Every continuous function $f : X \to X$ such that $f |_{A} = {id}_{A}$ must be surjective, so $(X, A)$ has the ϵ-surjection property for every ϵ. However it does not have computable type: if $E \subseteq N$ is a non-computable c.e. set, then the pair $(Y, B)$ defined by $Y = X_{0} \cup ⋃_{i \notin E} X_{i}$ and $B = {(2^{- i}, 2^{- i}) : i ⩾ 1, i \notin E} \cup {(0, 0)}$ is a semicomputable copy of $(X, A)$ but Y is not computable.

It is an open question whether there is a compact space with infinitely many connected components having strong computable type. The previous results give partial answers to this question. Essentially, such a space cannot have arbitrarily small connected components. Proposition 5.8.
Let X be a compact metric space.

If for every $ϵ > 0$ there exists a connected component of X of diameter $< ϵ$ which is not a singleton, then X does not have strong computable type.

If X contains infinitely many isolated points, then X does not have strong computable type.
Proof.
We show that in both situations one can build for each $ϵ > 0$ a non-surjective continuous ϵ-function, implying that X does not have strong computable type by Corollary 5.5.

Let $A \subseteq X$ be a connected component of diameter $< ϵ$ , which is not a singleton. A is the intersection of a decreasing sequence of clopen sets, so by compactness it is contained in a clopen set $C_{ϵ}$ of diameter $< ϵ$ . The function $f : X \to X$ defined as the identity on $X ∖ C_{ϵ}$ and sending all $C_{ϵ}$ to some point $x \in C_{ϵ}$ is a continuous ϵ-function, which is not surjective because $C_{ϵ}$ is not a singleton.

If X contains infinitely many isolated points then by compactness, they have an accumulation point $x \in X$ . Given $ϵ > 0$ , let $f : X \to X$ send some isolated point $y \in B (x, ϵ)$ to x and be the identity on $X ∖ {y}$ . f is a non-surjective continuous ϵ-function. □

5.3. Failing to have computable type in a non-trivial way

When a set or a pair does not have computable type, it may or may not be easy to build a semicomputable copy which is not computable. For instance, it is straightforward to show that the line segment I does not have computable type (as a single set, i.e. without its boundary): if $r > 0$ is a non-computable right-c.e. real number, then $[0, r]$ is a semicomputable copy of I which is not computable.

However, for other sets such as the dunce hat [2] or the set shown in Fig. 2a below, there is no such obvious construction. We can formulate a precise statement expressing this idea, by using the results obtained so far, notably Theorem 4.7.

Figure 2.

The set from Example 5.13 and its ϵ-deformations.

Definition 5.9.

Let X, Y be compact metric spaces and $f : X \to Y$ be continuous. A modulus of uniform continuity for f is a function $μ : N \to N$ such that if $d (x, x^{'}) < 2^{- μ (n)}$ then $d (f (x), f (x^{'})) ⩽ 2^{- n}$ .

The choice of strict and non-strict inequalities is not important, but is convenient as it makes the set of functions having modulus μ a closed subset of the space $C (X, Y)$ of continuous functions from X to Y.

For instance, a Lipschitz function with Lipschitz constant L has a modulus of uniform continuity $μ (n) = n + ⌈ {log}_{2} (L) ⌉$ .

Definition 5.10.

Let $X \subseteq Q$ . A copy of X in Q is a simple copy of X if there exists a homeomorphism $f : X \to Y$ such that both f and $f^{- 1}$ have a computable modulus of uniform continuity.

Theorem 5.11 (Computability of simple copies).

Let $X \subseteq Q$ be a computable set that does not properly contain a copy of itself. Let Y be a simple copy of X. If Y is semicomputable then Y is computable.

In particular, if X does not properly contain a copy of itself, then there is no geometrical transformation (scaling, rotation, translation) yielding a semicomputable copy of X which is not computable, and more generally there is no bilipschitz transformation yielding such a copy.

We need the following result which is folklore, but does not seem to appear in the literature.

Lemma 5.12.
Let $X \subseteq Q$ be a computable compact set and let $μ : N \to N$ be computable. The set $\begin{matrix} K_{μ} : = {f \in C (X, Q) : μ is a modulus of uniform continuity of f} \end{matrix}$ is effectively compact.
Proof.
Let ${(x_{i})}_{i \in N}$ be a dense computable sequence in X. If μ is a computable modulus of continuity of f, then an access to a name of $f \in K_{μ}$ is computably equivalent to an access to the values of f on this dense sequence, because using those values and the modulus of continuity, one can computably evaluate f at any point. In other words, the set $K_{μ}$ is computably homeomorphic to the set $\begin{matrix} L_{μ} : = {{(z_{i})}_{i \in N} \in Q^{N} : \forall i, j, n \in N, d (x_{i}, x_{j}) < 2^{- n} ⟹ d (z_{i}, z_{j}) ⩽ 2^{- n}} \end{matrix}$ via the map sending $f \in K_{μ}$ to the sequence ${(f (x_{i}))}_{i \in N}$ . The space $Q^{N}$ is effectively compact and $L_{μ}$ is a $Π_{1}^{0}$ -subset of $Q^{N}$ , therefore $L_{μ}$ is effectively compact, and so is $K_{μ}$ . □

We now prove the result.
Proof of Theorem 5.11.
Let $μ : N \to N$ be a computable function. The set $J_{μ}$ of injective continuous functions $f : X \to Q$ such that μ is a modulus of uniform continuity for both f and $f^{- 1}$ is an effectively compact subset of $C (X, Q)$ . Indeed, $J_{μ}$ is the intersection of $K_{μ}$ from Lemma 5.12 with the set $\begin{matrix} {f \in C (X, Q) : \forall x, x^{'} \in X, d_{Q} (f (x), f (x^{'})) < 2^{- μ (n)} ⟹ d_{Q} (x, x^{'}) ⩽ 2^{- n}} . \end{matrix}$ As the latter set is $Π_{1}^{0}$ , its intersection with $K_{μ}$ is effectively compact.

Let $P_{μ} = {f (X) : f \in J_{μ}}$ . As X is computable, the function $ϕ : C (X, Q) \to (K (Q), τ_{V})$ sending f to $f (X)$ is computable. As $J_{μ}$ is effectively compact, its image $P_{μ}$ by ϕ is effectively compact as well, so $P_{μ}$ is a $Π_{1}^{0}$ -subset of $K (Q)$ in the topology $τ_{V}$ . As X does not properly contain a copy of itself, any copy of X in $P_{μ}$ is $P_{μ}$ -minimal. Therefore, any semicomputable copy of X in $P_{μ}$ is computable, by the same argument as in the proof of Theorem 4.7. □
Example 5.13.
The set X shown in Fig. 2a, consisting of a disk attached to a pinched torus, does not have computable type.

It can be proved using the results in [2,3]. Indeed, the neighborhood of the pinched point is the cone of a graph consisting of two circles attached by a line segment; the line segment is not part of a cycle in the graph, implying that the set does not have computable type. Another way to prove that it does not have computable type is to use the fact that for every $ϵ > 0$ , there is a sequence of ϵ-deformations of X converging to a proper subset of X (see Fig. 2b). Therefore, it does not have strong computable type by Corollary 5.1, hence it does not have computable type as it is a finite simplicial complex (Corollary 5.6).

As X does not contain a copy of itself, it has no simple copy which is semicomputable but not computable. It explains why the proof, given in [2,3], that such sets do not have computable type is not straightforward.

A similar analysis can be carried out for pairs.
5.4. Uniformity

Given a pair $(X, A)$ which has strong computable type, a natural question one may ask is whether it is possible to have a single effective procedure that takes any copy $(Y, B)$ given in the topology $τ_{up V}^{2}$ and computes Y in the topology $τ_{V}$ . It turns out that the answer is almost always negative: uniformity is only possible when X is a singleton. Therefore, the natural problem is to measure the degree of non-uniformity of this problem, using Weihrauch degrees. It was studied by Pauly [35] in the case of the circle embedded in $R^{2}$ . We give here more results about this question.

Definition 5.14.
For a pair $(X, A)$ , let ${SCT}_{(X, A)}$ be the function taking a copy $(Y, B)$ of $(X, A)$ in $τ_{up V}^{2}$ and outputting Y in $τ_{V}^{2}$ .

The first result holds for every pair (which may or may not have strong computable type).
Definition 5.15.
Closed choice over $N$ is the problem $C_{N}$ of finding an element in a non-empty set A of natural numbers, given any enumeration of the complement of A.

Strong Weihrauch reducibility relative to some oracle is usually denoted by $⩽_{s W}^{t}$ (where t stands for topological).
Theorem 5.16.
Let $(X, A)$ be a pair such that X is not a singleton. One has $C_{N} ⩽_{s W}^{t} {SCT}_{(X, A)}$ . If $(X, A)$ has a semicomputable copy then $C_{N} ⩽_{s W} {SCT}_{(X, A)}$ .
Proof.
Instead of $C_{N}$ , we use the strongly Weihrauch equivalent problem $Max$ which sends a non-empty finite subset of $N$ , represented by its characteristic function, to its maximal element (Theorem 7.13 in [5]). We prove the result when $(X, A)$ has a semicomputable copy, the general case is obtained by relativizing the argument to an oracle which semicomputes some copy.

Assume that $(X, A)$ is already embedded as a semicomputable pair in Q. We can assume that $1 / 2 < diam (X) < 1$ , rescaling X if needed (and using the assumption that X is not a singleton).

Given a non-empty finite set $E \subseteq N$ , let $m = max E$ . We show how to produce a semicomputable copy $(X_{E}, A_{E})$ of $(X, A)$ such that $2^{- m - 1} < diam (X_{E}) < 2^{- m}$ . Given an access to $X_{E}$ in the topology $τ_{V}$ , one can compute its diameter so one can compute m, showing that $Max$ is strongly Weihrauch reducible to ${SCT}_{(X, A)}$ .

We now define $(X_{E}, A_{E})$ . It is obtained from $(X, A)$ by a translation and a scaling by a factor $2^{- m}$ . Given E, one can compute the sequence $m_{i} = max (E \cap [0, i])$ converging to m. The idea is that at stage i, we produce a copy of $(X, A)$ that is translated and scaled by $2^{- m_{i}}$ . If at stage $i + 1$ , one has $m_{i + 1} = m_{i}$ then we keep that copy. If $m_{i + 1} > m_{i}$ , then we move to another copy. The new scaling factor is $2^{- m_{i + 1}}$ and we choose the translation so that the new copy is contained in the current $τ_{up V}^{2}$ neighborhood of the previous copy. It is possible because we can assume that at stage i, the $τ_{up V}^{2}$ neighborhood contains a ball of diameter $2^{- i}$ , and $2^{m_{i + 1}} = 2^{- i - 1}$ . □

In the other direction, we can prove that ${SCT}_{(X, A)} ⩽_{W} C_{N}$ holds when $(X, A)$ has strong computable type in a particular way. A strong Weihrauch reduction is impossible, because $C_{N}$ has countably many possible outputs while ${SCT}_{(X, A)}$ has uncountably many.
Theorem 5.17.
Let $P$ be a $Σ_{2}^{0}$ invariant. If a pair $(X, A)$ is $P$ -minimal then ${SCT}_{(X, A)} ⩽_{W} C_{N}$ .
Proof.
Let $P = ⋃_{n} P_{n}$ where $P_{n}$ are uniformly $Π_{1}^{0}$ -set in $τ_{up V}^{2}$ . Given a copy $(Y, B)$ , let $E = {n : (Y, B) \in P_{n}}$ . From $(Y, B)$ in $τ_{up V}^{2}$ one can enumerate the complement of E, and given any $n \in E$ , one can compute Y by using the fact that $(Y, B)$ is $P_{n}$ -minimal as in the proof of Theorem 4.7. □

We do not know whether ${SCT}_{(X, A)}$ is always Weihrauch reducible to $C_{N}$ when $(X, A)$ has strong computable type. It is left as an open question (Question 3).
5.5. Vietoris vs upper Vietoris topology

We now relate the descriptive complexity of properties of pairs in the Vietoris topology $τ_{V}^{2}$ and upper Vietoris topology $τ_{up V}^{2}$ . As $τ_{up V}^{2}$ is weaker than $τ_{V}^{2}$ , the descriptive complexity of a property in $τ_{up V}^{2}$ is always an upper bound on its complexity in $τ_{V}^{2}$ . Although the properties of a given complexity level are not the same in the topologies $τ_{V} \times τ_{up V}$ and $τ_{up V}^{2}$ , we show that they actually induce the same class of minimal elements.

Notation 5.18.
For a property of pairs $P$ let $\begin{matrix} ↑ P = {(X, A) : \exists (X^{'}, A^{'}) \subseteq (X, A), (X^{'}, A^{'}) \in P} . \end{matrix}$
Proposition 5.19.
Let $P$ be a property of pairs. The set $↑ P$ has the same minimal elements as $P$ and
If $P$ is $Π_{1}^{0}$ in $τ_{V}^{2}$ , then $↑ P$ is $Π_{1}^{0}$ in $τ_{up V}^{2}$ .

If $P$ is $Σ_{2}^{0}$ in $τ_{V}^{2}$ , then $↑ P$ is $Σ_{2}^{0}$ in $τ_{up V}^{2}$ ; moreover, $↑ P = ⋃_{n} P_{n}$ where $P_{n}$ are uniformly $Π_{1}^{0}$ in $τ_{up V}^{2}$ .

Therefore, whether a pair $(X, A)$ is minimal for some $Π_{1}^{0}$ or $Σ_{2}^{0}$ property does not depend on the topology (among $τ_{V}^{2}$ and $τ_{up V}^{2}$ ) in which the complexity is measured.

In order to prove Proposition 5.19, we need the next result. Lemma 5.20.
The relation ⊆, which is the set ${(X, X^{'}) \in K^{2} (Q) : X \subseteq X^{'}}$ , is $Π_{1}^{0}$ in the topology $τ_{low V} \times τ_{up V}$ .
Proof.
One has $X ⊈ X^{'}$ iff there exists a rational ball B intersecting X and such that $X^{'}$ is contained in $Q ∖ \overline{B}$ . This condition on the pair $(X, X^{'})$ is an effective open set in the topology $τ_{low V} \times τ_{up V}$ . In other words, inclusion is $Π_{1}^{0}$ in that topology. □
Proof of Proposition 5.19.
It is easy to see that $P$ and $↑ P$ have the same minimal elements. Now assume that $P$ is $Π_{1}^{0}$ in $τ_{V}^{2}$ and let us show that $↑ P$ is $Π_{1}^{0}$ in $τ_{up V}^{2}$ . One has $\begin{matrix} (X, A) \in ↑ P ⟺ \exists (X^{'}, A^{'}) \in K {(Q)}^{2}, (X^{'}, A^{'}) \subseteq (X, A) and (X^{'}, A^{'}) \in P . \end{matrix}$ Using Lemma 5.20 and the assumption that $P$ is $Π_{1}^{0}$ in $τ_{V}^{2}$ , the relation $R : = {(X, A, X^{'}, A^{'}) : (X^{'}, A^{'}) \subseteq (X, A) and (X^{'}, A^{'}) \in P}$ is $Π_{1}^{0}$ in the topology $τ_{up V}^{2} \times τ_{V}^{2}$ . The space $(K^{2} (Q), τ_{V}^{2})$ is effectively compact, so the projection of R on its first two components, which is $↑ P$ , is $Π_{1}^{0}$ in the topology $τ_{up V}^{2}$ by Proposition 2.5.

The second item is now easy to prove. If $P$ is $Σ_{2}^{0}$ in $τ_{V}^{2}$ , then $P = ⋃_{n} P_{n}$ where $P_{n}$ are uniformly $Π_{1}^{0}$ in $τ_{V}^{2}$ . Therefore, $↑ P = ⋃_{n} ↑ P_{n}$ and $↑ P_{n}$ are uniformly $Π_{1}^{0}$ in $τ_{up V}^{2}$ by the first statement, so $↑ P$ is $Σ_{2}^{0}$ in $τ_{up V}^{2}$ . □

5.6. The product and cone spaces

We give a simple relationship between pairs, their products and their cones, w.r.t. strong computable type.

5.6.1. The product of two pairs

Definition 5.21.
The product of two pairs $(X_{1}, A_{1})$ and $(X_{2}, A_{2})$ is the pair $\begin{matrix} (X_{1}, A_{1}) \times (X_{2}, A_{2}) = (X_{1} \times X_{2}, (X_{1} \times A_{2}) \cup (A_{1} \times X_{2})) . \end{matrix}$
Proposition 5.22.
If $(X_{1}, A_{1}) \times (X_{2}, A_{2})$ has (strong) computable type and $(X_{2}, A_{2})$ has a semicomputable copy in Q, then $(X_{1}, A_{1})$ has (strong) computable type.
Proof.
Assume that $(X_{1}, A_{1})$ and $(X_{2}, A_{2})$ are embedded in Q as semicomputable pairs, let us prove that $X_{1}$ is computable.

The product $(X, A) = (X_{1}, A_{1}) \times (X_{2}, A_{2}) \subset Q \times Q$ is semicomputable because each pair is. Therefore X is computable by assumption, so its first projection $X_{1}$ is computable. It shows that $(X_{1}, A_{1})$ has computable type. The proof relativizes, so $(X_{1}, A_{1})$ has strong computable type. □

If two pairs have strong computable type, it is an open problem whether their product has strong computable type as well.
5.6.2. The cone of a pair

Definition 5.23 (Cone).

Let X be a topological space. The cone of X is the quotient space $Cone (X) = (X \times [0, 1]) / (X \times {0})$ .

Let $(X, A)$ be a pair. The cone pair $(Y, B) = Cone (X, A)$ is defined by $Y = Cone (X)$ and $B = X \cup Cone (A)$ , where we consider X as $X \times {1}$ .

If X is embedded in Q, then a realization of $Cone (X)$ in $Q ≅ [0, 1] \times Q$ is given by $\begin{matrix} Cone (X) ≅ {(λ, λ x) : λ \in [0, 1], x \in X} . \end{matrix}$

Proposition 5.24.
Let $(X, A)$ be a pair. If $Cone (X, A)$ has (strong) computable type, then $(X, A)$ has (strong) computable type.
Proof.
We prove it for computable type and the proof relativizes. Suppose $(Y, B) = Cone (X, A)$ has computable type and that $(X_{0}, A_{0})$ is a semicomputable copy of $(X, A)$ in Q. Let us prove that $X_{0}$ is computable.

The following realization $(Y_{0}, B_{0})$ of $Cone (X_{0}, A_{0})$ in Q is semicomputable: $\begin{array}{l} Y_{0} = {(λ, λ x) : λ \in [0, 1], x \in X_{0}}, \\ B_{0} = {(λ, λ x) : λ \in [0, 1], x \in A_{0}} \cup ({1} \times X_{0}) . \end{array}$ The pair $(Y_{0}, B_{0})$ is easily semicomputable so $Y_{0}$ is computable by assumption. The intersection $Z_{0}$ of $Y_{0}$ with $[1 / 2, 1] \times Q$ is computable as well (an open set B intersects $Z_{0}$ iff the open set $B \cap ((1 / 2, 1] \times Q)$ intersects $Y_{0}$ , which is semidecidable). The image of $Z_{0}$ under the computable function $(λ, y) \mapsto y / λ$ is $X_{0}$ , which is therefore computable. □
Remark 5.25.
The other implication of the previous theorem is false. Let L be the graph consisting of two circles joined by a line segment, and $N = \emptyset$ . The pair $(L, N)$ has strong computable type but $Cone (L, N)$ does not, as shown in [2], because the graph L has an edge which belongs to no cycle.

Here is another example. Let L be the so-called house with two rooms, or Bing’s house, and $N = \emptyset$ . L is contractible and it is proved in [2] that it has (strong) computable type. However, the results of [2] imply that as L is contractible, the pair $(Cone (L), L)$ does not have strong computable type.

6. Computability-theoretic properties of ANRs

Theorem 4.8 gives a simple way to prove that a pair $(X, A)$ has strong computable type by identifying a $Σ_{2}^{0}$ topological invariant for which $(X, A)$ is minimal. In order to apply this result, we need to find suitable $Σ_{2}^{0}$ invariants. In this section, we develop results of independent interest that will be applied to define $Σ_{2}^{0}$ invariants, expressed in terms of extensions of continuous functions.

The core concept is the notion of Absolute Neighborhood Retract (ANR). It is central in topology and it turns out that it has interesting computability-theoretic properties that we will exploit in order to define $Σ_{2}^{0}$ invariants. The general idea is that the space of functions from a space X to a space Y cannot be handled in a computable way if Y is arbitrary; it can if Y is an ANR.

We recall the definition of Absolute Neighborhood Retracts (ANRs) and explore their computable aspects. The results will be applied in the next section.

6.1. Absolute neighborhood retracts (ANRs)

This important notion was introduced by Borsuk [4] and plays an eminent role in algebraic topology. Moreover, it has very useful computability-theoretic consequences, which we will take advantage of. We point out that computability-theoretic aspects of compact ANRs have been studied by Collins in [12], although we do not use these results.

Definition 6.1.
Let $(X, A)$ be a pair. A retraction $r : X \to A$ is a continuous function such that $r |_{A} = {id}_{A}$ . If a retraction exists, then we say that A is a retract of X.
Definition 6.2.
Let X be a compact space.
X is an absolute retract (AR) if every copy of X in Q is a retract of Q.

X is an absolute neighborhood retract (ANR) if every copy $X^{'}$ of X in Q is retract of a neighborhood of $X^{'}$ .

Fact 6.3.
We recall some classical facts (see [ 15 ] and [ 40 ]).
The n-dimensional ball is an AR.

The n-dimensional sphere is an ANR.

If Y is an AR and $(X, A)$ is a pair, then every continuous function $f : A \to Y$ has a continuous extension $F : X \to Y$ .

If Y is an ANR and $(X, A)$ is a pair, then every continuous function $f : A \to Y$ has a continuous extension $F : U \to Y$ where $U \subseteq X$ is a neighborhood of A.

The topologist’s sine curve, or the set ${0} \cup {1 / n : n \in N}$ are examples of spaces that are not ANRs.

ANRs interact nicely with the notion of homotopy, that we recall now.
Definition 6.4.
A homotopy between two continuous functions $f, g : X \to Y$ is a continuous function $H : X \times [0, 1] \to Y$ such that $H (x, 0) = f (x)$ and $H (x, 1) = g (x)$ for all $x \in X$ . Two functions are homotopic if there exist a homotopy between them. A function is null-homotopic if it is homotopic to a constant function.

Homotopy between functions is an equivalence relation, whose equivalence classes are called homotopy classes. If two functions to a compact ANR are close to each other, then they are homotopic.
Lemma 6.5 (Theorem 4.1.1 in [40]).

Let $Y \subseteq Q$ be a compact ANR. There exists $α > 0$ such that for every space X, if $f, g : X \to Y$ are continuous and $ρ_{X} (f, g) < α$ , then f, g are homotopic.

Whether a function to an ANR has a continuous extension only depends on the homotopy class of the function. This is Borsuk’s homotopy extension theorem (Theorem 1.4.2 in [40]).

Theorem 6.6 (Borsuk’s homotopy extension theorem).

Let Y be an ANR and $(X, A)$ be a pair. If $f, g : A \to Y$ are continuous and f has a continuous extension $F : X \to Y$ , then every homotopy between f and g can be extended to a homotopy between F and some continuous extension $G : X \to Y$ of g.

These results have important computability-theoretic consequences, because arbitrary functions can be replaced by computable functions that are close enough to the original ones so that they are homotopic.

6.2. Homotopy classes

If X, Y are topological spaces and $f : X \to Y$ is continuous, then we denote by $[f]$ the homotopy class of f. Let $[X; Y]$ be the set of homotopy classes of continuous functions from X to Y.

Let Y be a fixed compact ANR. Given a compact set $X \subseteq Q$ in the upper Vietoris topology, we show how the set $[X; Y]$ can be computed in some way. Note that this question has been addressed, for instance in [8], when X and Y are simplicial complexes presented as combinatorial objects. In our case, the information available about X and Y is much more elusive, therefore one might expect that very little can be computed. Note that computable aspects of ANRs have been investigated by Collins [12], where a compact ANR Y is presented together with a neighrborhood and a computable retraction. In our case, we do not have access to a retraction.

In order to state the results, let us discuss the consequences of Borsuk’s homotopy extension theorem (Theorem 6.6). Let $(X, A)$ be a pair. Whether a continuous function $f : A \to Y$ has a continuous extension $F : X \to Y$ does not depend on f, but on its equivalence class in $[A; Y]$ . We denote this class by ${[f]}_{A}$ to make it clear that f is defined on A and that we consider homotopies defined on A (rather than X). If $f : A \to Y$ and $F : X \to Y$ are continuous functions, then we say that ${[F]}_{X}$ extends ${[f]}_{A}$ if F is homotopic to an extension of f. This relation is well-defined, i.e. does not depend on the representatives of the equivalence classes, because if F extends f, ${[g]}_{A} = {[f]}_{A}$ and ${[G]}_{X} = {[F]}_{X}$ , then G is homotopic to an extension of g by Borsuk’s homotopy extension theorem. In particular, ${[F]}_{X}$ extends ${[f]}_{A}$ if and only if ${[F |_{A}]}_{A} = {[f]}_{A}$ .

A numbering of a set S is a surjective partial function $ν_{S} : \subseteq N \to S$ .

Theorem 6.7.
Let Y be a fixed compact ANR. To any compact set $X \subseteq Q$ we can associate a numbering $ν_{[X; Y]}$ of $[X; Y]$ such that:
$dom (ν_{[X; Y]})$ is c.e. relative to X.

Equality ${(i, j) \in dom {(ν_{[X; Y]})}^{2} : ν_{[X; Y]} (i) = ν_{[X; Y]} (j)}$ is c.e. relative to X.

For any pair $(X, A)$ , the extension relation ${(i, j) \in dom (ν_{[X; Y]}) \times dom (ν_{[A; Y]}) : ν_{[X; Y]} (i) extends ν_{[A; Y]} (j)}$ is c.e. relative to X and A.

For any pair $(X, A)$ , the extensibility predicate ${i \in dom (ν_{[A; Y]}) : ν_{[A; Y]} (i) has a continuous extension to X}$ is c.e. relative to X and A,
where X and A are given as elements of $(K (Q), τ_{up V})$ .

Note that the result holds with no computability assumption about Y. We now proceed with the proof of this result. Lemma 6.8.
If $Y \subseteq Q$ is a compact ANR, then there exist an effective open set U containing Y, a continuous retraction $r : U \to Y$ and $μ, α > 0$ such that:
Functions to Y that are α-close are homotopic.

For $x \in U$ , $d (r (x), x) < μ$ .

For $x, y \in U$ , $d (x, y) < μ$ implies $d (r (x), r (y)) < α$ .

Proof.
The number α exists by Lemma 6.5. As Y is an ANR, there exists an open set W containing Y and a retraction $r : W \to Y$ . Let V be an open set such that $Y \subseteq V \subseteq \overline{V} \subseteq W$ . As $\overline{V}$ is compact, r is uniformly continuous on $\overline{V}$ so there exists $μ > 0$ satisfying (iii) for $x, y \in \overline{V}$ . As $r |_{Y} = {id}_{Y}$ and Y is compact, if x is sufficiently close to Y, $d (r (x), x) < μ$ . Therefore we can choose $U \subseteq V$ satisfying (ii). By compactness of Y, U can be replaced by a finite union of rational balls. □
Proof of Theorem 6.7.
Let ${(f_{i})}_{i \in N}$ be a dense computable sequence of functions $f_{i} : Q \to Q$ . Let $Y \subseteq Q$ be a compact ANR and let U, r, α, μ be provided by Lemma 6.8. For $X \subseteq Q$ , we define a numbering $ν_{[X; Y]}$ of $[X; Y]$ and prove (1), (4), (2) and (3) in this order. Its domain is $\begin{matrix} dom (ν_{[X; Y]}) = {i \in N : f_{i} (X) \subseteq U}, \end{matrix}$ which is clearly c.e. relative to X, showing (1). For $i \in dom (ν_{[X; Y]})$ , we then define $ν_{[X; Y]} (i)$ as the equivalence class of $r \circ f_{i} |_{X} : X \to Y$ .

We first show that $ν_{[X; Y]}$ is surjective. For a continuous function $f : X \to Y$ , let $\tilde{f} : Q \to Q$ be a continuous extension of f. If $f_{i}$ is sufficiently close to $\tilde{f}$ , then $f_{i} (X) \subseteq U$ (hence $i \in dom (ν_{[X; Y]})$ ) and $r \circ f_{i} |_{X}$ is α-close to f. Therefore, $r \circ f_{i} |_{X}$ is homotopic to f and $ν_{[X; Y]} (i) = [f]$ .

Let now $(X, A)$ be a pair in Q and let $ν_{[X; Y]}$ and $ν_{[A; Y]}$ be the corresponding numberings. We show condition (4). Claim 6.9.
The set $\begin{matrix} {i \in dom (ν_{[X; Y]}) : ν_{[A; Y]} (i) has a continuous extension to X} \end{matrix}$ is c.e. relative to X and A.
Proof of the claim.
We show that $r \circ f_{i} |_{A} : A \to Y$ has a continuous extension to X iff there exists $j \in dom (ν_{[X; Y]})$ such that $ρ_{A} (f_{j}, f_{i}) < μ$ . It will imply the result as this condition is c.e. relative to X and A.

If there exists such a j, then $ρ_{A} (r \circ f_{j}, r \circ f_{i}) < α$ by Lemma 6.8(iii) so $r \circ f_{j} |_{A}$ and $r \circ f_{i} |_{A}$ are homotopic by Lemma 6.8(i). As $r \circ f_{j} |_{A}$ obviously has an extension $r \circ f_{j} |_{X}$ , so does $r \circ f_{i} |_{A}$ by Borsuk’s homotopy extension theorem (Theorem 6.6).

Conversely, assume that $r \circ f_{i} |_{A}$ has an extension $f : X \to Y$ . One has $ρ_{A} (f, f_{i}) = ρ_{A} (r \circ f_{i}, f_{i}) < μ$ by Lemma 6.8(ii) so if $f_{j}$ is sufficiently close to f on X, then $f_{j} (X) \subseteq U$ and $ρ_{A} (f_{j}, f_{i}) < μ$ . □

We now show (2), i.e. that equality is c.e. Let $Cyl (X) = X \times [0, 1] \subseteq Q$ be the cylinder of X and $\partial Cyl (X) = X \times {0, 1}$ its boundary. These sets are semicomputable relative to X. A pair $(f, g)$ of functions from X to Y is nothing else than a function $h : \partial Cyl (X) \to Y$ , defined as $h (x, 0) = f (x)$ and $h (x, 1) = g (x)$ . This correspondence is moreover effective, in the sense that there exists a computable function $φ : dom {(ν_{[X; Y]})}^{2} \to dom (ν_{[\partial Cyl (X); Y]})$ such that if i, j are indices of the homotopy classes of f and g respectively, then $φ (i, j)$ is an index of the homotopy class of h. Note that f, g are homotopic iff h has a continuous extension to $Cyl (X)$ . Therefore, for $i, j \in dom (ν_{[X; Y]})$ , one has $ν_{[X; Y]} (i) = ν_{[X; Y]} (j)$ iff $ν_{[\partial Cyl (X); Y]} (φ (i, j))$ has an extension to $Cyl (X)$ , which is c.e. relative to X by Claim 6.9 applied to the pair $(Cyl (X), \partial Cyl (X))$ .

We finally show (3), i.e. the extension relation is c.e. Note that $dom (ν_{[X; Y]}) \subseteq dom (ν_{[A; Y]})$ and for $i \in dom (ν_{[X; Y]})$ , $ν_{[A; Y]} (i)$ is the equivalence class of the restrictions to A of functions in $ν_{[X; Y]} (i)$ . For $i \in dom (ν_{[X; Y]})$ and $j \in dom (ν_{[A; Y]})$ , $ν_{[X; Y]} (i)$ extends $ν_{[A; Y]} (j)$ iff $ν_{[A; Y]} (i) = ν_{[A; Y]} (j)$ , which is c.e. □

6.3. Families of $Σ_{2}^{0}$ invariants

The previous results enable us to define families of $Σ_{2}^{0}$ invariants. We will study their properties and use particular instances in the next sections.

6.3.1. Extension of functions

To each compact ANR Y we associate a topological invariant $E (Y)$ . Ultimately, we will focus on $Y = S_{n}$ , the n-dimensional sphere.

Definition 6.10 (The invariant $E (Y)$ ).

Let Y be a topological space. A pair $(X, A)$ belongs to $E (Y)$ if there exists a continuous function $f : A \to Y$ that cannot be extended to a continuous function $g : X \to Y$ .

Note that this definition is only interesting when A is non-empty, otherwise it is never satisfied.

From this definition, the obvious upper bound on the descriptive complexity of $E (Y)$ is ${\underset{~}{Σ}}_{2}^{1}$ . However when Y is a compact ANR, we show that the complexity drops down to $Σ_{2}^{0}$ , which is much lower and is an effective class, even if there is no computability assumption on Y.

Corollary 6.11.
If Y is a compact ANR, then $E (Y)$ is a $Σ_{2}^{0}$ invariant in $τ_{up V}^{2}$ .
Proof.
It is a simple application of Theorem 6.7. Indeed, $\begin{array}{l} (X, A) \in E (Y) & ⟺ \exists f : A \to Y having no extension to X \\ ⟺ \exists i \in dom (ν_{[A; Y]}), \forall j \in dom (ν_{[X; Y]}), ν_{[X; Y]} (j) does not extend ν_{[A; Y]} (i) \end{array}$ which is a $Σ_{2}^{0}$ condition. □

Note that although $E (Y)$ is a countable union of differences of closed sets, it is never a countable union of closed sets in $τ_{up V}^{2}$ unless it is empty. Indeed, if $E (Y)$ is non-empty then it is not an upper set: take $(X, A) \in E (Y)$ , and observe that $(X, X) \notin E (Y)$ .
6.3.2. Null-homotopy of functions

The previous results provide another family of $Σ_{2}^{0}$ invariants.

Definition 6.12 (The invariant $H (Y)$ ).

Let Y be a topological space. A space X belongs to $H (Y)$ if there exists a continuous function $f : X \to Y$ which is not null-homotopic, i.e. not homotopic to a constant function.

Corollary 6.13.
If Y is a compact ANR, then $H (Y)$ is a $Σ_{2}^{0}$ invariant in $τ_{up V}^{2}$ .
Proof.
One has $X \in H (Y)$ iff $[X; Y]$ is non-trivial iff $\exists i, j \in dom (ν_{[X; Y]})$ , $ν_{[X; Y]} (i) \neq ν_{[X; Y]} (j)$ , which is a $Σ_{2}^{0}$ condition. Slightly differently, we fix some $i_{0}$ such that $f_{i_{0}} : Q \to Q$ is constant with value in U (implying $i_{0} \in dom (ν_{[X; Y]})$ for any X), so that $[X; Y]$ is non-trivial iff $\exists i \in dom (ν_{[X; Y]})$ , $ν_{[X; Y]} (i) \neq ν_{[X; Y]} (i_{0})$ . □

Again, $H (Y)$ is not a countable union of closed sets in $τ_{up V}$ unless it is empty, because it is not an upper set in that case: the maximal set Q is not in $H (Y)$ because it is contractible.

The invariant $H (Y)$ only applies to single sets. We will define a version for pairs, with $Y = S_{n}$ .
7. Detailed study of some $Σ_{2}^{0}$ invariants

Theorem 4.8 provides a template to prove that a pair has strong computable type, by identifying a $Σ_{2}^{0}$ invariant for which the pair is minimal. One of our goals is to revisit previous results by finding corresponding $Σ_{2}^{0}$ invariants when possible, hopefully giving more insight on the problem, providing unifying arguments and sometimes giving new examples for free. We now study in details the $Σ_{2}^{0}$ invariants defined in the previous section.

The study of the descriptive complexity of topological invariants is particularly interesting because it lies at the interaction between two branches of topology, namely point-set topology and algebraic topology. Descriptive complexity belongs to point-set topology, because it is about expressing sets of points in terms of open sets; algebraic topology provides topological invariants having low descriptive complexity.

7.1. Properties of $E (Y)$

We study the invariant $E (Y)$ from Definition 6.10, and develop a few techniques to establish whether a pair satisfies this invariant.

First, if A is a retract of X, then $(X, A) \notin E (Y)$ . Indeed, every $f : A \to Y$ has an extension $f \circ r : X \to Y$ , where $r : X \to A$ is a retraction.

The next result identifies a relation between pairs that preserves the invariant $E (Y)$ .

Proposition 7.1.
Let $ϕ : (X^{'}, A^{'}) \to (X, A)$ such that $ϕ |_{A^{'}} : A^{'} \to A$ is a homeomorphism. If $(X^{'}, A^{'}) \in E (Y)$ then $(X, A) \in E (Y)$ .
Proof.
We assume that $(X, A) \notin E (Y)$ and show that $(X^{'}, A^{'}) \notin E (Y)$ . Let $f : A^{'} \to Y$ . The function $g = f \circ {(ϕ |_{A^{'}})}^{- 1} : A \to Y$ has a continuous extension $G : X \to Y$ . The continuous function $F = G \circ ϕ : X^{'} \to Y$ then extends f. Indeed, $F |_{A^{'}} = G \circ ϕ |_{A^{'}} = g \circ ϕ |_{A^{'}} = f \circ {(ϕ |_{A^{'}})}^{- 1} \circ ϕ |_{A^{'}} = f$ . □

Converging sequences. Now we give results showing how $E (Y)$ behaves w.r.t. converging sequences. First, if a sequence of pairs $(X_{i}, A_{i})$ converges to a pair $(X, A)$ in the Vietoris topology (i.e., if $X_{i}$ converges to X and $A_{i}$ converges to A), then whether all $(X_{i}, A_{i})$ are (resp. are not) in $E (Y)$ does not imply that $(X, A)$ is (resp. is not) in $E (Y)$ . In other words, $E (Y)$ is neither closed nor open in the Vietoris topology.

Therefore in order to obtain results, we need more complicated assumptions on the way a sequence of pairs converges to a pair.

The first result can be used to prove that a pair is not in $E (Y)$ by approximating it with pairs that are not in $E (Y)$ in some way. It is taken from the definition of pseudo-cubes in [18].
Proposition 7.2.
Let $(X, A)$ be a pair and ${(X_{i}, A_{i})}_{i \in N}$ be a sequence of pairs contained in X such that
For every i, $X_{i} ∖ A_{i}$ is open in X and is contained in $(X ∖ A)$ .

For every $ϵ > 0$ , there exists i such that $X ∖ (X_{i} ∖ A_{i}) \subseteq N_{ϵ} (A)$ .
If $(X_{i}, A_{i}) \notin E (Y)$ for all i, then $(X, A) \notin E (Y)$ .
Proof.
We assume that $(X_{i}, A_{i}) \notin E (Y)$ for all i and show that $(X, A) \notin E (Y)$ .

Let $f : A \to Y$ be continuous. Y is an ANR, so there exists some continuous extension $\tilde{f}$ of f to $N_{ϵ} (A)$ , for some $ϵ > 0$ by Fact 6.3 (4). Let i be such that $X ∖ (X_{i} ∖ A_{i}) \subseteq N_{ϵ} (A)$ by (2), so $\tilde{f} |_{A_{i}}$ can be defined and has a continuous extension $F_{i} : X_{i} \to Y$ by assumption.

We define a continuous extension $F : X \to Y$ of f, by defining $F = F_{i}$ on $X_{i}$ and $F = \tilde{f}$ on $X ∖ (X_{i} ∖ A_{i})$ . Note that $X_{i}$ and $X ∖ (X_{i} ∖ A_{i})$ are closed and their intersection is $A_{i}$ , where these two functions agree. Therefore, F is well-defined and continuous and extends f. As f was arbitrary, we have proved that $(X, A) \notin E (Y)$ . □

The second result can be used to prove that a pair is in $E (Y)$ by approximating it with pairs that are in $E (Y)$ , in a particular way.
Definition 7.3.
Let Y be an ANR and $X_{i}$ converge to X in the upper Vietoris topology. We say that functions $f_{i} : X_{i} \to Y$ are asymptotically homotopic to $f : X \to Y$ if for some extension $\tilde{f} : U \to Y$ of f to a neighborhood U of X, $f_{i}$ is homotopic to $\tilde{f} |_{X_{i}}$ for sufficiently large i.

There are usually many ways of extending f to a neighborhood of X. However, any two of them are homotopic on a smaller neighborhood, which implies that the definition does not depend on the choice of an extension of f, and is intrinsic to the functions $f_{i}$ , f.
Proposition 7.4.
Whether $f_{i} : X_{i} \to Y$ are asymptotically homotopic to $f : X \to Y$ does not depend on the choice of a neighborhood U of X and an extension $\tilde{f} : U \to Y$ .
Proof.
Assume that for some U and $\tilde{f} : U \to Y$ and sufficiently large i, $f_{i}$ is homotopic to $\tilde{f} |_{X_{i}}$ . Let V be a neighborhood of X and $g : V \to Y$ a continuous extension of f. As $\tilde{f}$ and g coincide on X, there exists $ϵ > 0$ such that their restrictions $\tilde{f} |_{N_{ϵ} (X)}$ and $g |_{N_{ϵ} (X)}$ are as close as needed so that they are homotopic. For sufficiently large i, $f_{i}$ is homotopic to $\tilde{f} |_{X_{i}}$ by assumption and $X_{i}$ is contained in $N_{ϵ} (X)$ , so $\tilde{f} |_{X_{i}}$ is homotopic to $g |_{X_{i}}$ . Therefore, $f_{i}$ is homotopic to $g |_{X_{i}}$ . □
Proposition 7.5 (Asymptotic homotopy preserves continuous extensibility).

Let Y be an ANR, ${(X_{i}, A_{i})}_{i \in N}$ and $(X, A)$ be pairs in Q such that $(X_{i}, A_{i})$ converge to $(X, A)$ in the upper Vietoris topology. Assume that $f_{i} : A_{i} \to Y$ are asymptotically homotopic to $f : A \to Y$ . If f has a continuous extension on X, then for sufficiently large i, $f_{i}$ has a continuous extension on $X_{i}$ .

Proof.
Let $F : X \to Y$ be a continuous extension of f. It has a continuous extension $\tilde{F} : U \to Y$ for some neighborhood U of X. Note that U is a neighborhood of A and $\tilde{F}$ is an extension of f. As $f_{i}$ is asymptotically homotopic to f, $f_{i}$ is homotopic to $\tilde{F} |_{A_{i}}$ for large i. The function $\tilde{F} |_{A_{i}}$ has a continuous extension to $X_{i}$ , namely $\tilde{F} |_{X_{i}}$ , so $f_{i}$ also has a continuous extension as well. □

In particular, when all the involved pairs have the same second component, we obtain the following simple result. Corollary 7.6.
Let Y be an ANR. Let ${(X_{i}, A_{i})}_{i \in N}$ and $(X, A)$ be pairs in Q such that $A_{i} = A$ for all i and $X_{i}$ converge to X in the upper Vietoris topology. If $f : A \to Y$ has no continuous extension to $X_{i}$ for any $i \in N$ , then f has no continuous extension to X.

7.2. The invariant $E_{n}$

For $n \in N$ , the n-dimensional sphere $S_{n}$ is an ANR. We define $E_{n} = E (S_{n})$ . This invariant will be used to cover several examples.

Definition 7.7 (The invariant $E_{n}$ ).

For $n \in N$ , a pair $(X, A)$ is in $E_{n}$ if there exists a continuous function $f : A \to S_{n}$ that has no continuous extension $F : X \to S_{n}$ .

Corollary 6.11 implies that $E_{n}$ is a $Σ_{2}^{0}$ invariant, therefore every $E_{n}$ -minimal pair has strong computable type, by applying Theorem 4.8.

The simplest example of a pair which is $E_{n}$ -minimal is given by the $n + 1$ -ball and its bounding n-sphere. We first explain why is it in $E_{n}$ . More generally, whether a pair $(B_{m + 1}, S_{m})$ satisfies $E_{n}$ depends on the mth homotopy group of the n-sphere.

Proposition 7.8.
The pair $(B_{m + 1}, S_{m})$ is in $E_{n}$ if and only if the homotopy group $π_{m} (S_{n})$ is non-trivial.

In particular, $(B_{n + 1}, S_{n})$ is in $E_{n}$ and $(B_{m + 1}, S_{m})$ is not in $E_{n}$ for $m < n$ .
Proof.
As $B_{m + 1}$ is the cone of $S_{m}$ , a continuous extension of $f : S_{m} \to S_{n}$ to $B_{m + 1}$ is nothing else than a null-homotopy of f. □

7.2.1. Relationship with dimension

The dimension of a space has a strong impact on the possibility of extending functions to a sphere. First, if X has dimension at most n, then any continuous function from a closed subset to $S_{n}$ extends continuously to X.

Theorem 7.9 (Theorem 3.6.3 in [40]).

Let $n \in N$ . If $(X, A)$ is a pair with $dim (X ∖ A) ⩽ n$ , then $(X, A) \notin E_{n}$ .

In particular, if $dim (X) ⩽ n$ then $(X, A) \notin E_{n}$ .

In some cases, if a pair is not in $E_{n}$ then no subpair is in $E_{n}$ .

Lemma 7.10.
Let $(X, A)$ be a pair with $dim (A) ⩽ n$ . If $(X, A) \notin E_{n}$ , then for every $(Y, B) \subseteq (X, A)$ one has $(Y, B) \notin E_{n}$ .
Proof.
As $dim (A) ⩽ n$ , one has $(A, B) \notin E_{n}$ . Therefore, $(X, A) \notin E_{n}$ implies $(Y, B) \notin E_{n}$ : every function f on B has an extension to A and then to X, whose restriction to Y is an extension of f. □

This result gives a simple way to prove $E_{n}$ -minimality in certain circumstances.
Corollary 7.11.
Let $(X, A)$ be a pair in $E_{n}$ , where A has empty interior and $dim (A) ⩽ n$ . If for every $A \subseteq Y ⊊ X$ one has $(Y, A) \notin E_{n}$ , then $(X, A)$ is $E_{n}$ -minimal.
Proof.
Let $(Y, B)$ be a proper subpair of $(X, A)$ . As A has empty interior, $Y \cup A$ is a proper subset of X, so $(Y \cup A, A) \notin E_{n}$ by assumption. Therefore, $(Y, B) \notin E_{n}$ by Lemma 7.10. □

The statement is reminiscent of the discussion about minimality at the end of Section 4.2. However, $E_{n}$ is not an upper set (indeed, $(B_{n + 1}, S_{n}) \in E_{n}$ but $(B_{n + 1}, B_{n + 1}) \notin E_{n}$ ) so Lemma 4.10 does not apply. Indeed, the dimension assumption cannot be dropped in general. The pair $(B_{4}, S_{3})$ is in $E_{2}$ as witnessed by the Hopf map, but it is not $E_{2}$ -minimal, as $(B_{3}, S_{2}) ⊊ (B_{4}, S_{3})$ is also in $E_{2}$ . However, if $S_{3} \subseteq Y ⊊ B_{4}$ then $S_{3}$ is a retract of Y so $(Y, S_{3}) \notin E_{2}$ .

We now apply this technique.
Proposition 7.12.
For every $n \in N$ , the pair $(B_{n + 1}, S_{n})$ is $E_{n}$ -minimal.
Proof.
By Proposition 7.8, $(B_{n + 1}, S_{n})$ is in $E_{n}$ . If $S_{n} \subseteq Y ⊊ B_{n + 1}$ , then Y retracts to $S_{n}$ so $(Y, S_{n}) \notin E_{n}$ . Therefore by Corollary 7.11, no proper subpair $(Y, B)$ of $(B_{n + 1}, S_{n})$ is in $E_{n}$ . As a result, $(B_{n + 1}, S_{n})$ is $E_{n}$ -minimal. □

Therefore, our results give an alternative proof that the pair $(B_{n + 1}, S_{n})$ has (strong) computable type, which was shown by Miller [32]. We will give more examples of $E_{n}$ -minimal pairs in the next sections.
7.3. The invariant $H_{n}$

It was shown in [23,26] that closed manifolds and compact manifolds with boundary have computable type. In this section, we identify a $Σ_{2}^{0}$ invariant for which manifolds are minimal.

In the n-sphere $S_{n}$ , let p be an arbitrary point. We recall that two continuous functions of pairs $f, g : (X, A) \to (S_{n}, p)$ are homotopic relative to A if there exists a homotopy between f and g that is constant on A, i.e. a continuous function $H : X \times [0, 1] \to S_{n}$ such that $H (x, 0) = f (x)$ , $H (x, 1) = g (x)$ for all $x \in X$ , and $H (a, t) = p$ for all $t \in [0, 1]$ and $a \in A$ . A continuous function $f : (X, A) \to (S_{n}, p)$ is null-homotopic relative to A if f is homotopic, relative to A, to the constant function p.

Definition 7.13 (The invariant $H_{n}$ ).

A pair $(X, A)$ is in $H_{n}$ if there exists a continuous function of pairs $f : (X, A) \to (S_{n}, p)$ which is not null-homotopic relative to A.

A space X is in $H_{n}$ if the pair $(X, \emptyset)$ is in $H_{n}$ , i.e. if there exists a continuous function $f : X \to S_{n}$ which is not null-homotopic.

Now that for single spaces, $H_{n}$ is precisely $H (S_{n})$ from Definition 6.12.

We first prove that $H_{n}$ is a $Σ_{2}^{0}$ invariant, by reducing it to $E_{n}$ . We recall from Definition 5.23 that for a space Y, $Cone (Y)$ is the quotient of $Y \times [0, 1]$ obtained by identifying all the pairs $(y, 0)$ . A function $f : Y \to Z$ is null-homotopic if and only if it can be extended to a continuous function $\tilde{f} : Cone (Y) \to Z$ , where Y is embedded in $Cone (Y)$ as $Y \times {1}$ . A similar equivalence holds for pairs, as follows.

Proposition 7.14.
For a pair $(X, A)$ , one has $\begin{matrix} (X, A) \in H_{n} ⟺ Cone (X, A) \in E_{n} . \end{matrix}$

Moreover, if $Cone (X, A)$ is $E_{n}$ -minimal, then $(X, A)$ is $H_{n}$ -minimal.
Proof.
Let $(C, D) = Cone (X, A) = (Cone (X), X \cup Cone (A))$ . A function $f : (X, A) \to (S_{n}, p)$ has a canonical extension $F : D \to S_{n}$ with constant value p on $Cone (A)$ . Moreover, a null-homotopy of f relative to A is nothing else than a continuous extension of F to C.

Assume that $(X, A) \in H_{n}$ and let $f : (X, A) \to (S_{n}, p)$ be a continuous function which is not null-homotopic relative to A. By the previous observation, the function $F : D \to S_{n}$ has no continuous extension to C, therefore $Cone (X, A) \in E_{n}$ .

Conversely, assume that $Cone (X, A) \in E_{n}$ and let $G : D \to S_{n}$ have no continuous extension to C. We cannot directly apply the preliminary observation to G because it is not necessarily constant on $Cone (A)$ . However, G is homotopic to a function $F : D \to S_{n}$ which is constant on $Cone (A)$ . Indeed, $Cone (A)$ is contractible so the restriction of G to $Cone (A)$ is null-homotopic. As $S_{n}$ is an ANR, the homotopy on $Cone (A)$ can be extended to a homotopy between $G : D \to S_{n}$ and a function $F : D \to S_{n}$ which is constant on $Cone (A)$ (Theorem 6.6). Let p be the constant value. As G has no extension to C, neither does F. We can now apply the preliminary observation: the restriction $f : X \to S_{n}$ of F to X is not null-homotopic relative to A, therefore $(X, A) \in H_{n}$ .

Assume that $Cone (X, A)$ is $E_{n}$ -minimal. If $(X^{'}, A^{'})$ is a proper subpair of $(X, A)$ , then $Cone (X^{'}, A^{'})$ is a proper subpair of $Cone (X, A)$ so it does not satisfy $E_{n}$ , therefore $(X^{'}, A^{'}) \notin H_{n}$ . □

We will see below (Proposition 7.18) that under additional assumptions, the implication about minimality can be turned into an equivalence.

This characterization allows one to derive results about $H_{n}$ from results about $E_{n}$ . We start with the descriptive complexity of $H_{n}$ . We already saw in Corollary 6.13 that the invariant $H (Y)$ of single spaces is $Σ_{2}^{0}$ in $τ_{up V}$ when Y is a compact ANR, and a similar result holds for the invariant $H_{n}$ of pairs. Corollary 7.15.
$H_{n}$ is a $Σ_{2}^{0}$ invariant in $τ_{up V}^{2}$ .
Proof.
Given a pair $(X, A) \subseteq Q$ , a copy $(C, D)$ of $Cone (X, A)$ can be defined as follows: $\begin{array}{l} C = {(t, t x) : t \in [0, 1], x \in X}, \\ D = {(1, x) : x \in X} \cup {(t, t x) : t \in [0, 1], x \in A} . \end{array}$ The map ϕ sending $(X, A) \in (K^{2} (Q), τ_{up V}^{2})$ to $(C, D) \in (K^{2} (Q), τ_{up V}^{2})$ is easily computable, and $H_{n}$ is the preimage of $E_{n}$ by ϕ by Proposition 7.14. As $E_{n}$ is $Σ_{2}^{0}$ , so is $H_{n}$ . □

7.3.1. Relationship with dimension

As $H_{n}$ can be expressed using $E_{n}$ , the relations between $E_{n}$ and the dimension of the space can be similarly formulated for $H_{n}$ . Theorem 7.9 and Lemma 7.10 have the following consequences.

Proposition 7.16.
Let $(X, A)$ be a pair with $dim (X) ⩽ n - 1$ . One has $(X, A) \notin H_{n}$ .
Proof.
One has $dim (Cone (X)) ⩽ n$ so $Cone (X, A) \notin E_{n}$ by Theorem 7.9, therefore $(X, A) \notin H_{n}$ . □
Lemma 7.17.
Let $(X, A)$ be a pair satisfying $dim (X) ⩽ n$ and $dim (A) ⩽ n - 1$ . If $(X, A) \notin H_{n}$ , then for every pair $(Y, B) \subseteq (X, A)$ one has $(Y, B) \notin H_{n}$ .
Proof.
Let $(C, D) = Cone (X, A)$ and $(E, F) = Cone (Y, B) \subseteq (C, D)$ . Reformulating $H_{n}$ in terms of $E_{n}$ thanks to Proposition 7.14, we want to prove that $(C, D) \notin E_{n}$ implies $(E, F) \notin E_{n}$ .

It is implied by Lemma 7.10, which can be applied because $D = X \cup Cone (A)$ so $dim (D) ⩽ n$ . □

Under the same assumptions, we can improve Proposition 7.14 to obtain an equivalence.
Proposition 7.18.
Let $(X, A)$ be a pair where A has empty interior, $dim (X) ⩽ n$ and $dim (A) ⩽ n - 1$ . One has $\begin{matrix} (X, A) is H_{n} -minimal ⟺ Cone (X, A) is E_{n} -minimal . \end{matrix}$

Before proving this result, we need to reformulate Borsuk’s homotopy extension theorem (Theorem 6.6). The cylinder of a space X is $Cyl (X) = X \times [0, 1]$ . A homotopy $H : X \times [0, 1] \to Y$ is nothing else than a function from $Cyl (X)$ to Y, and a null-homotopy is a function from $Cone (X)$ to Y. Therefore, Borsuk’s homotopy extension theorem can be reformulated as follows.
Lemma 7.19.
Let $(X, A)$ be a pair and Y an ANR. Every continuous function $f : X \cup Cyl (A) \to Y$ has a continuous extension to $Cyl (X)$ . Every continuous function $g : Cone (A) \to Y$ has a continuous extension to $Cone (X)$ .
Proof.
The first statement is Borsuk’s homotopy extension theorem. The second one is a particular case for functions that are constant on X. More precisely, $Cone (A)$ is the quotient of $X \cup Cyl (A)$ by identifying all the points of X. A function $g : Cone (A) \to Y$ induces a function $f : X \cup Cyl (A) \to Y$ which is constant on X, by composing g with the quotient map. f has a continuous extension $F : Cyl (X) \to Y$ , which is constant on X, and therefore induces a continuous function $G : Cone (X) \to Y$ extending g. □
Proof of Proposition 7.18.
Assume that $(X, A)$ is $H_{n}$ -minimal. We need to show that no proper subpair $(Y, B)$ of $Cone (X, A)$ is in $E_{n}$ . Using Corollary 7.11, it is sufficient to show the result when $B = X \cup Cone (A)$ . Let then Y be a proper subset of $Cone (X)$ containing $X \cup Cone (A)$ . There exists a non-empty open set $U \subseteq X ∖ A$ and an interval $J = (a, b) \subseteq [0, 1]$ such that $U \times J$ is disjoint from Y (we think of $U \times J$ as embedded in $Cone (X)$ in the obvious way). Let $f : X \cup Cone (A) \to S_{n}$ . We show how to extend f to $Cone (X) ∖ (J \times U)$ , giving an extension of f to Y by restriction. Figure 3 may help visualize the argument.

Figure 3.
Consecutive extensions of f.

As $(X, A)$ is $H_{n}$ -minimal by assumption, $(X ∖ U, A) \notin H_{n}$ so $Cone (X ∖ U, A) \notin E_{n}$ . Therefore, the restriction of f to $(X ∖ U) \cup Cone (A)$ has a continuous extension to $Cone (X ∖ U)$ . So f has a continuous extension $g : X \cup Cone (X ∖ U) \to S_{n}$ .

Applying Lemma 7.19, we can extend g to the quotient of $X \times [0, a]$ which is homeomorphic to $Cone (X)$ and to $Cyl (X) : = X \times [b, 1]$ . So we obtain a continuous extension h of f to the union of $Cone (X ∖ U)$ with the quotient of $X \times ([0, a] \cup [b, 1])$ . That union is precisely $Cone (X) ∖ (J \times U)$ . □

Finally, from the point of view of $H_{n}$ , a pair $(X, A)$ can be replaced by the single space $X / A$ , which is the quotient of X by A.
Proposition 7.20.
For every pair $(X, A)$ , $(X, A) \in H_{n} ⟺ X / A \in H_{n}$
Proof.
Let $p_{A} \in X / A$ be the equivalence class of A. First observe that $(X, A)$ can equivalently be replaced by $(X / A, p_{A})$ , i.e. $(X, A) \in H_{n} ⟺ (X / A, p_{A}) \in H_{n}$ . Indeed, there is a one-to-one correspondence between continuous functions $f : (X, A) \to (S_{n}, p)$ and continuous functions $g : (X / A, p_{A}) \to (S_{n}, p)$ , and a one-to-one correspondence between null-homotopies of f relative to A and null-homotopies of g relative to $p_{A}$ .

Now, for a pair $(Y, q)$ , where q is a point of Y, we show that a function $g : (Y, q) \to (S_{n}, p)$ is null-homotopic if and only if it is null-homotopic relative to q. Assume that g is null-homotopic, i.e. homotopic to a constant function. We can assume w.l.o.g. that the constant function is p, because all constant functions are homotopic (indeed, the sphere is path-connected). Let $H_{t}$ be a homotopy from $H_{0} = g$ to $H_{1} = p$ . Our goal is to define another such homotopy $H^{'}$ which is constantly p on q.

We give a different argument for $n = 1$ and $n ⩾ 2$ .

Let $n = 1$ . There exists a continuous function $ϕ : S_{1} \times S_{1} \to S_{1}$ such that $ϕ (x, p) = x$ and $ϕ (x, x) = p$ for all $x \in S_{1}$ . Indeed, identifying $S_{1}$ with $R / Z$ and p with the equivalence class of 0, let $ϕ (x, y) = x - y mod 1$ . We can then define $H_{t}^{'} (y) = ϕ (H_{t} (y), H_{t} (q))$ , it is easy to check that it satisfies the required assumptions.

Let now $n ⩾ 2$ (we do not know whether a similar map $ϕ : S_{n} \times S_{n} \to S_{n}$ can be defined but we provide another argument, which cannot be applied to $n = 1$ ). We want to define a continuous function $H^{'} : Y \times [0, 1] \to S_{n}$ extending a certain function $h^{'} : ({q} \times [0, 1]) \cup (Y \times {0, 1}) \to S_{n}$ . Let h be the restriction of H to that set. We show that $h^{'}$ is homotopic to h. As h has a continuous extension, it will imply that $h^{'}$ has a continuous extension, because $S_{n}$ is an ANR.

On ${q} \times [0, 1]$ , h and $h^{'}$ define two loops on $S_{n}$ ( $h^{'}$ defines the constant loop). As $S_{n}$ is simply-connected (indeed, $n ⩾ 2$ ), these two loops are homotopic relative to ${q} \times {0, 1}$ . As h and $h^{'}$ coincide on $Y \times {0, 1}$ , they are homotopic. □

We conclude this section with two simple examples of pairs and sets that are $H_{n}$ -minimal.
Proposition 7.21.
The pair $(B_{n}, S_{n - 1})$ and the space $S_{n}$ are $H_{n}$ -minimal.
Proof.
It is a direct application of Proposition 7.14: one has $Cone (B_{n}, S_{n - 1}) = Cone (S_{n}, \emptyset) = (B_{n + 1}, S_{n})$ which is $E_{n}$ -minimal by Proposition 7.12. □

We will see in the Section 8.2 that, more generally, compact n-dimensional manifolds with or without boundary are all $H_{n}$ -minimal.
7.4. Connections with homology and cohomology

We end this section with a characterization of $E_{n}$ and $H_{n}$ in terms of homology and cohomology groups for certain spaces. Our goal here is not to give a complete presentation, but to mention intimate connections with algebraic topology, that can be used to study strong computable type. It will be applied to manifolds.

We do not define homology and cohomology groups, but just recall the notations and some classical results. We refer to standard textbooks on algebraic topology for complete expositions of the concepts [6,16,20]. This section is not essential and may be skipped by the reader who is unfamiliar with algebraic topology.

If X is a topological space, G an abelian group and $n \in N$ , one can define the homology groups $H_{n} (X; G)$ and the cohomology groups $H^{n} (X; G)$ , which are abelian groups. They are topological invariants that, informally, detect the n-dimensional holes of the space X. For instance, when X is the m-dimensional sphere $S_{m}$ , one has $\begin{matrix} H_{n} (S_{m}; G) ≅ H^{n} (S_{m}; G) ≅ \{\begin{matrix} G & if n = m or n = 0, \\ 0 & otherwise, \end{matrix} \end{matrix}$ where 0 is the trivial group with one element.

These groups are also called the singular homology and cohomology groups, to distinguish them from the groups from other homology and cohomology theories, such as the Čech homology and cohomology groups, denoted by ${\overset{ˇ}{H}}_{n} (X; G)$ and ${\overset{ˇ}{H}}^{n} (X; G)$ respectively. However, these different theories are equivalent for ANRs.

Theorem 7.22 (Theorem 1 in [31]).

If X is an ANR, then for all G and n, $\begin{array}{l} H_{n} (X; G) ≅ {\overset{ˇ}{H}}_{n} (X; G), \\ H^{n} (X; G) ≅ {\overset{ˇ}{H}}^{n} (X; G) . \end{array}$

The result applies to compact manifolds with and without boundary, which are ANRs (Corollary A.9 in [16]).

Partial characterization of $E_{n}$ . For compact spaces of dimension at most $n + 1$ , $E_{n}$ can be characterized in terms of Čech homology and cohomology. For a pair $(X, A)$ , let $i : A \to X$ be the inclusion map. Like any continuous map, it induces natural homomorphisms on the homology and cohomology groups, written $i_{*} : {\overset{ˇ}{H}}_{n} (A; G) \to {\overset{ˇ}{H}}_{n} (X; G)$ and $i^{*} : {\overset{ˇ}{H}}^{n} (X; G) \to {\overset{ˇ}{H}}^{n} (A; G)$ . It uses the abelian groups $(Z, +)$ and $(R / Z, +)$ .

Theorem 7.23 (Corollaries VIII.2 and VIII.3 (p. 149) in [20]).

Let $(X, A)$ be a compact pair with $dim (X) ⩽ n + 1$ . One has $\begin{array}{l} (X, A) \in E_{n} & ⟺ i_{*} : {\overset{ˇ}{H}}_{n} (A; R / Z) \to {\overset{ˇ}{H}}_{n} (X; R / Z) is not injective \\ ⟺ i^{*} : {\overset{ˇ}{H}}^{n} (X; Z) \to {\overset{ˇ}{H}}^{n} (A; Z) is not surjective . \end{array}$

The equivalence does not hold in general. For instance, Hopf’s fibration is a continuous function $f : S_{3} \to S_{2}$ which is not null-homotopic, hence does not extend to $B_{4}$ , implying that $(B_{4}, S_{3}) \in E_{2}$ . However, the second homology and cohomology groups of both $B_{4}$ and $S_{3}$ are trivial, so the only homomorphism between them is bijective.

Partial characterization of $H_{n}$ . The invariant $H_{n}$ also admits a characterization in terms of Čech homology and cohomology, for compact spaces of dimension at most n.

Theorem 7.24 (Corollary 4 (p. 150) in [20]).

Let X be a compact space with $dim (X) ⩽ n$ . One has $\begin{array}{l} X \in H_{n} & ⟺ {\overset{ˇ}{H}}_{n} (X; R / Z) \neq 0 \\ ⟺ {\overset{ˇ}{H}}^{n} (X; Z) \neq 0 . \end{array}$

Again, the equivalence does not hold in general. Hopf’s fibration implies that $S_{3} \in H_{2}$ , but ${\overset{ˇ}{H}}_{2} (S_{3}; R / Z) ≅ {\overset{ˇ}{H}}^{2} (S_{3}; Z) ≅ 0$ .

Lupini, Melnikov and Nies [30], and Melnikov and Downey [13] with a different proof, proved that if $X \subseteq Q$ is given in the Vietoris topology $τ_{V}$ , then its Čech cohomology groups ${\overset{ˇ}{H}}^{n} (X; Z)$ can be computably presented (relative to X and uniformly): one can enumerate a list of generators and the words, i.e. finite combinations of generators and their inverses, that are equal to the 0 element of the group. Their result implies that the non-triviality of a group ${\overset{ˇ}{H}}^{n} (X; Z)$ is a $Σ_{2}^{0}$ invariant in the topology $τ_{V}$ : the group is non-trivial iff there exists a word which does not equal 0, which is a $Σ_{2}^{0}$ formula. It seems that their proof even shows that it is a $Σ_{2}^{0}$ invariant in the topology $τ_{up V}$ . However Proposition 5.19 implies that being $Σ_{2}^{0}$ in $τ_{V}$ is enough for the purpose of proving strong computable type. More precisely,

Corollary 7.25.
Let X be a compact space. If X is minimal such that ${\overset{ˇ}{H}}^{n} (X; Z) ≇ 0$ , then X has strong computable type.
Proof.
The invariant $I_{n} = {X \in K (Q) : {\overset{ˇ}{H}}^{n} (X; Z) ≇ 0}$ is $Σ_{2}^{0}$ in the topology $τ_{V}$ by [30] and [13]. Therefore, $↑ I_{n}$ is $Σ_{2}^{0}$ in the topology $τ_{up V}$ and has the same minimal elements as $I_{n}$ (Proposition 5.19), so we can apply Theorem 4.8. □

We also mention a stronger connection between maps to the sphere and cohomology. Theorem 7.24 is actually a particular case of Hopf’s classification theorem, which states that for a compact space of dimension at most n, there is a one-to-one correspondence between homotopy classes of maps to the n-sphere and elements of the nth Čech cohomology group. It can be found as Theorem 2.2 (p. 17) in [1], reformulated in [19]. Theorem 7.26 (Hopf classification theorem).

Let X be a compact space of dimension $⩽ n$ . There is a bijection between $[X; S_{n}]$ and ${\overset{ˇ}{H}}^{n} (K; Z)$ .

8. Examples

In this section, we illustrate our framework by revisiting previous results stating that a pair has computable type, and showing that it can be explained by their minimality w.r.t. some suitable $Σ_{2}^{0}$ invariant. The advantages of this approach are multiple. A single $Σ_{2}^{0}$ invariant can be used for many different sets or pairs, therefore capturing in a unified way the computability-theoretic part of the argument, leaving a purely topological analysis to each specific set or pair, which can often leverage the well-developed field of topology. It makes the study of (strong) computable type more explicitly related to topology.

In particular, most of the arguments in this section are purely topological.

8.1. Examples of $E_{n}$ -minimal pairs

In this section we show how $E_{n}$ -minimality covers many of the known examples of pairs having computable type. We also give a new example to illustrate its scope.

8.1.1. Chainable continuum between two points

We revisit a result due to Iljazović in [21]. Let us first recall the definitions. A continuum is a connected compact metric space.

Definition 8.1.
Let X be a metric space. A finite sequence $C$ of nonempty open subsets $C_{0}, \dots, C_{m}$ of X is said to be a chain if $C_{i} \cap C_{j} \neq \emptyset \Leftrightarrow | i - j | ⩽ 1$ , $\forall i, j \in {0, \dots, m}$ . A chain $C = {C_{0}, \dots, C_{m}}$ covers X if $X \subseteq ⋃_{i} C_{i}$ ; for $ϵ > 0$ , it is an ϵ-chain if ${max}_{i} (diam (C_{i})) < ϵ$ .

For $a, b \in X$ , X is chainable from a to b if for every $ϵ > 0$ , there exists an ϵ-chain $C = {C_{0}, \dots, C_{m}}$ in X which covers X and such that $a \in C_{0}$ and $b \in C_{m}$ .

Iljazović proved in [21] that if X is chainable from a to b, then the pair $(X, {a, b})$ has computable type. This result and its proof can be reformulated as the $E_{0}$ -minimality of the pair.
Proposition 8.2.
If X is compact connected and is chainable from a to b, then the pair $(X, {a, b})$ is $E_{0}$ -minimal.
Proof.
Take $S_{0} = {a, b}$ and $f = {id}_{S_{0}} : S_{0} \to S_{0}$ . As X is connected, the function f has no continuous extension $g : X \to S_{0}$ , because $g^{- 1} (a)$ and $g^{- 1} (b)$ would disconnect X. Hence, $(X, {a, b})$ is in $E_{0}$ .

Let $x \in X ∖ {a, b}$ and $ϵ > 0$ be such that $B (x, ϵ) \subseteq X ∖ {a, b}$ . Let $f : {a, b} \to S_{0}$ . The points a, b must be disconnected in $X ∖ B (x, ϵ)$ . Indeed, let $C = {C_{0}, \dots, C_{m}}$ be an ϵ-chain covering X with $a \in C_{0}$ and $b \in C_{m}$ . Let k be such that $x \in C_{k}$ . As $diam (C_{k}) < ϵ$ , $a \notin C_{k}$ , $b \notin C_{k}$ and $C_{k} \subseteq B (x, ϵ)$ . Therefore $X ∖ B (x, ϵ)$ is covered by the two disjoint open sets $U_{a} : = ⋃_{i < k} C_{i}$ and $U_{b} : = ⋃_{i > k} C_{i}$ , containing a and b respectively.

The disconnection can be turned into a continuous extension $g : X ∖ B (x, ϵ) \to S_{0}$ , sending $U_{a}$ to $f (a)$ and $U_{b}$ to $f (b)$ . Therefore, $(X ∖ B (x, ϵ), {a, b}) \notin E_{0}$ . It implies that $(X, {a, b})$ is $E_{0}$ -minimal because any proper subset of X is contained in such a $X ∖ B (x, ϵ)$ . □

We will cover other examples from [21] in Section 8.3, using another $Σ_{2}^{0}$ invariant.
8.1.2. Pseudo n-cubes

In [18], the authors introduce the notion of a pseudo-n-cube, which is a pair $(X, A)$ which can somehow be approximated by n-dimensional cubes and their boundaries. They prove that pseudo-n-cubes have computable type.

We show how the result can be proved using the invariant $E_{n - 1}$ , by showing how the $E_{n - 1}$ -minimality of the n-dimensional cube implies the $E_{n - 1}$ -minimality of pseudo-n-cubes.

We first recall the definition of pseudo-n-cubes from [18]. Fix some $n \in N^{*}$ and let $S_{1}^{0}, \dots, S_{n}^{0}, S_{1}^{1}, \dots, S_{n}^{1}$ be the faces of the n-cube $I^{n}$ defined by $\begin{array}{l} S_{i}^{0} = {(x_{1}, \dots, x_{n}) \in I^{n} : x_{i} = 0}, \\ S_{i}^{1} = {(x_{1}, \dots, x_{n}) \in I^{n} : x_{i} = 1}, \end{array}$ where $i \in {1, \dots, n}$ . Let $S = ⋃_{i} S_{i}^{0} \cup S_{i}^{1}$ be the boundary of $I^{n}$ .

The Hausdorff distance between two non-empty compact subsets A, B of a metric space $(X, d)$ is $\begin{matrix} d_{H} (A, B) = max (max_{x \in A} min_{y \in B} d (x, y), max_{y \in B} min_{x \in A} d (x, y)) . \end{matrix}$

Definition 8.3.
A compact pair $(X, A)$ in $R^{n}$ is called a pseudo-n-cube with respect to some finite sequence of compact subsets $A_{i}^{0}$ and $A_{i}^{1}$ , $1 ⩽ i ⩽ n$ , if $A = ⋃_{i} A_{i}^{0} \cup A_{i}^{1}$ , $A_{i}^{0} \cap A_{i}^{1} = \emptyset$ and for each $ϵ > 0$ there exists a continuous injection $f : I^{n} \to R^{n}$ such that
$f (I^{n}) \subseteq X$ .

$f ({int}_{R^{n}} (I^{n})) \cap A = \emptyset$ .

$X ∖ f ({int}_{R^{n}} (I^{n})) \subseteq N_{ϵ} (f (S))$ .

$d_{H} (f (S_{i}^{0}), A_{i}^{0}) < ϵ$ and $d_{H} (f (S_{i}^{1}), A_{i}^{1}) < ϵ$ .

We now show how the proof that pseudo-n-cubes have computable type can be simplified by showing that they are $E_{n - 1}$ -minimal. Proposition 8.4.
Every pseudo-n-cube is $E_{n - 1}$ -minimal.
Proof.
A pseudo-cube is approximated by cubes. We use Propositions 7.5 and 7.2 to derive $E_{n - 1}$ -minimality of pseudo-n-cubes from $E_{n - 1}$ -minimality of n-cubes (Proposition 7.12).

We recall that the pair $(I^{n}, S) ≅ (B_{n}, S_{n - 1})$ is in $E_{n - 1}$ because the identity on S has no continuous extension to $I^{n}$ . A similar function $h : A \to S$ can be defined that has no extension to X. The function h satisfies $h (A_{i}^{0}) \subseteq S_{i}^{0}$ and $h (A_{i}^{1}) \subseteq S_{i}^{1}$ and is built as follows. On an intersection $A_{1}^{b_{1}} \cap \dots \cap A_{n}^{b_{n}}$ (where $b_{i} \in {0, 1}$ ), h sends every point to the vertex $(b_{1}, \dots, b_{n})$ of $I^{n}$ . We then progressively extend h, sending intersections of $n - 1$ sets to segments, intersections of $n - 2$ sets to squares, then cubes, etc. and finally sending single sets $A_{i}^{0}$ and $A_{i}^{1}$ to the $n - 1$ -cubes which are the faces $S_{i}^{0}$ and $S_{i}^{1}$ of $I^{n}$ . All the extensions can be done using the Tietze extension theorem.

Once $h : A \to S$ is defined, it has a continuous extension $\tilde{h}$ to a neighborhood of A because S is an ANR. For sufficiently small ϵ and a cube $(I^{n}, S)$ embedded in X as in the definition, $\tilde{h}$ is defined on S and sends $S_{i}^{b}$ close to $S_{i}^{b}$ , in particular disjoint from $S_{i}^{1 - b}$ . Thus, $\tilde{h} |_{S} : S \to S$ is homotopic to ${id}_{S}$ . In other words, the functions ${id}_{S}$ on the copies of $(I^{n}, S)$ are asymptotically homotopic to $h : A \to S$ . As ${id}_{S}$ has no continuous extension to $I^{n}$ , h has no continuous extension to X by Proposition 7.5. As a result, $(X, A) \in E_{n - 1}$ .

We now prove minimality. By definition of pseudo-n-cubes, for each ϵ there exists a copy $(X_{i}, A_{i})$ of the n-cube in X satisfying the conditions of Proposition 7.2:
$X_{i} ∖ A_{i}$ is open in X (indeed, it is the image by a continuous injection map of an open subset of $R^{n}$ in $X \subseteq R^{n}$ , so it is open by invariance of domain) and contained in $X ∖ A$ .

$X ∖ (X_{i} ∖ A_{i}) \subseteq N_{ϵ} (A)$ .
If $U \subseteq X ∖ A$ is an open set intersecting X, then the same conditions are satisfied by the pairs $(X_{i} ∖ U, A_{i} ∖ U)$ and $(X ∖ U, A)$ . For sufficiently large i, U intersects $X_{i}$ so $(X_{i} ∖ U, A_{i} ∖ U) \notin E_{n - 1}$ by $E_{n - 1}$ -minimality of $(X_{i}, A_{i})$ . We can apply Proposition 7.2, which implies that $(X ∖ U, A) \notin E_{n - 1}$ . Therefore, $(X, A)$ is $E_{n - 1}$ -minimal (we again use Corollary 7.11 which can be applied, as $A \subseteq R^{n}$ has empty interior, therefore has dimension at most $n - 1$ by Theorem 3.7.1 in [40]). □

8.1.3. A new example

In this section we illustrate how $E_{n}$ -minimality can be used to obtain new examples of spaces having computable type property, with little effort. We present an example, but many variations are possible.

Definition 8.5.
The topologist’s sine curve T, or Warsaw sine curve, is defined by $\begin{matrix} T = {(x, sin \frac{1}{x}) : 0 < x ⩽ 1} \cup {(0, y) : - 1 ⩽ y ⩽ 1} . \end{matrix}$

We define the Warsaw saucer S by $\begin{matrix} S = {(x, y, z) \in R^{3} : 0 < x^{2} + y^{2} ⩽ 1 and z = sin \frac{1}{\sqrt{x^{2} + y^{2}}}} \cup {(0, 0, z) : - 1 ⩽ z ⩽ 1} . \end{matrix}$

We define its boundary $\partial S$ as its bounding circle $\begin{matrix} \partial S = {(x, y, sin (1)) \in R^{3} : x^{2} + y^{2} = 1} ≅ S_{1} . \end{matrix}$

It is obtained from the closed topologist’s sine curve, making it rotate around the vertical segment, see Fig. 4.

Figure 4.
The Warsaw saucer.

The set S is compact and connected but neither locally connected nor path-connected. It is neither a manifold, nor a simplicial complex, nor a pseudo-n-cube so none of the previous results applies to $(S, \partial S)$ . However, it can easily be proved to have strong computable type, because it is closely related to the pair $(B_{2}, S_{1})$ and is therefore $E_{1}$ -minimal.
Proposition 8.6.
The pair $(S, \partial S)$ is $E_{1}$ -minimal and hence has strong computable type.
Proof.
We show the $E_{1}$ -minimality of $(B_{2}, S_{1})$ implies the $E_{1}$ -minimality of $(S, \partial S)$ .

The surface S can be approximated by copies of the disk $B_{2}$ that share the same boundary $S_{1}$ . Indeed, let $\begin{matrix} X_{i} = {(x, y, z) : \frac{1}{i π} ⩽ \sqrt{x^{2} + y^{2}} ⩽ 1 and z = sin \frac{1}{\sqrt{x^{2} + y^{2}}}} \cup {(x, y, 0) : \sqrt{x^{2} + y^{2}} ⩽ \frac{1}{i π}} . \end{matrix}$

The sets $X_{i}$ converge to S, and they all have the same boundary $S_{1}$ . We know that $(X_{i}, S_{1}) = (B_{2}, S_{1}) \in E_{1}$ , moreover the same function, which is the identity $id : S_{1} \to S_{1}$ , has no continuous extension to $X_{i}$ . Therefore, this function has no continuous extension to S by Corollary 7.6.

We now prove $E_{1}$ -minimality. The projection π on the horizontal plane sends S to $B_{2}$ and is the identity on $\partial S = S_{1}$ . If X is a proper compact subset of S containing $\partial S$ , then $π (X)$ is a proper compact subset of $B_{2}$ . As $(B_{2}, S_{1})$ is $E_{1}$ -minimal, $(π (X), S_{1}) \notin E_{1}$ so $(X, \partial S) \notin E_{1}$ by Proposition 7.1 (more directly, every $f : S_{1} \to S_{1}$ has a continuous extension $F : π (X) \to S_{1}$ , inducing a continuous extension $F^{'} = F \circ π : X \to \partial S$ of f to X). As a result, $(S, \partial S)$ is $E_{1}$ -minimal. □
8.2. Compact n-manifolds are $H_{n}$ -minimal

It was proved in [23] and [26] that compact manifolds with or without boundary have computable type, as pairs and single spaces respectively. In this section, we show how this result can be derived from classical results in algebraic topology implying that n-dimensional manifolds are $H_{n}$ -minimal, and applying Theorem 4.8. We first recall the definition of a manifold.

Definition 8.7.
A manifold of dimension n, or more concisely an n-manifold, is a Hausdorff space M in which each point has an open neighborhood homeomorphic to $R^{n}$ .

An n-manifold with boundary is a Hausdorff space M in which each point has an open neighborhood homeomorphic either to $R^{n}$ or to the half-space $R_{+}^{n} = {(x_{1}, \dots, x_{n}) \in R^{n} : x_{n} ⩾ 0}$ by a homeomorphism which maps x to a point $(x_{1}, \dots, x_{n - 1}, 0)$ . The set of points which have an open neighborhood homeomorphic to the half-space is called the boundary of M and is denoted by $\partial M$ .

The next result seems to be folklore but is not stated in any standard textbook on algebraic topology. However, it can be derived from classical results about homology of manifolds.
Theorem 8.8.
Every connected compact n-manifold M is $H_{n}$ -minimal. Every connected compact n-manifold with boundary $(M, \partial M)$ is $H_{n}$ -minimal.

We give here the proof for manifolds without boundary, and put the proof for manifolds with boundary in the Appendix (it is similar but requires more technical results about pairs).
Proof.
The result is a consequence of Theorem 7.24, which reduces $H_{n}$ to homology groups, and of classical results about homology groups of manifolds.

Let us use the abelian group $G = R / Z$ . As it contains an element of order 2, namely $1 / 2$ , Corollary 7.12 in [6] implies that if M is a connected n-manifold, then $H_{n} (M; G) \neq 0$ if and only if M is compact. Therefore, if M is a compact connected n-manifold and $x \in M$ , then $\begin{array}{l} H_{n} (M; G) ≇ 0, \\ H_{n} (M ∖ {x}; G) ≅ 0, \end{array}$ because $M ∖ {x}$ is a non-compact connected manifold.

If $x \in M$ and B is an open Euclidean ball around x, then $M ∖ {x}$ deformation retracts to $M ∖ B$ , which means that there is a retraction $r : M ∖ {x} \to M ∖ B$ such that if $i : M ∖ B \to M ∖ {x}$ is the inclusion map, then $i \circ r$ is homotopic to ${id}_{M ∖ {x}}$ . It is a classical result that deformation retractions preserve homology groups, so $H_{n} (M ∖ B) ≅ H_{n} (M ∖ {x}) ≅ 0$ .

Therefore, Theorem 7.24 implies that $M \in H_{n}$ and $M ∖ B \notin H_{n}$ . It implies that M is $H_{n}$ -minimal by Lemma 7.17: if X is a proper subset of M, then $X \subseteq M ∖ B$ for some B, so $X \notin H_{n}$ . □

Theorem 8.8 implies the result in [23] that connected compact manifold with or without boundary have (strong) computable type. However the proof is inherently different and has new implications. For instance, it implies that ${SCT}_{M, \partial M} ⩽_{W} C_{N}$ by Theorem 5.17. Note that a disconnected compact manifold also has strong computable type because it is a finite union of connected compact manifolds, but it is not $H_{n}$ -minimal because every connected component is in $H_{n}$ .

Moreover, Theorem 8.8 immediately implies that other pairs have strong computable type, as follows.
Corollary 8.9.
If M is a compact connected n-manifold with possibly empty boundary $\partial M$ , then the pair $\begin{matrix} Cone (M, \partial M) = (Cone (M), M \cup Cone (\partial M)) \end{matrix}$ is $E_{n}$ -minimal hence has strong computable type.
Proof.
All the assumptions of Proposition 7.18 are met: $\partial M$ has empty interior in M, $dim (M) = n$ and $dim (\partial M) = n - 1$ . As $(M, \partial M)$ is $H_{n}$ -minimal by Theorem 8.8, $Cone (M, \partial M)$ is $E_{n}$ -minimal. □

The cone of a manifold M is a manifold only when M is a sphere of a ball, so this result is indeed new.
8.3. Circularly chainable continuum which are not chainable

In [21], it is proved that every compact metrizable space which is circularly chainable but not chainable has computable type. The simplest examples of such sets are given by the circle and the Warsaw circle. We briefly show how the proof of this result can be reformulated in our framework by finding a suitable $Σ_{2}^{0}$ invariant.

We already saw the notion of chain in Definition 8.1. We recall other related notions, taken from [21]. Let $(X, d)$ be a metric space. A finite sequence $C = (C_{0}, \dots, C_{n})$ of non-empty open subsets of X is called:

A chain if for all $i, j \in {0, \dots, n}$ , $C_{i} \cap C_{j} \neq \emptyset ⟺ | i - j | ⩽ 1$ .

A circular chain if for all $i, j \in {0, \dots, n}$ , $C_{i} \cap C_{j} \neq \emptyset ⟺ (| i - j | ⩽ 1 or {i, j} = {0, n})$ .

A quasi-chain if for all $i, j \in {0, \dots, n}$ , $| i - j | > 1 ⟹ C_{i} \cap C_{j} = \emptyset$ .

Its mesh is defined by

mesh (C) = {max}_{0 ⩽ i ⩽ n} (diam (C_{i}))

. It covers a set

S \subseteq X

S \subseteq ⋃_{i} C_{i}

A set $S \subseteq X$ is chainable (resp. circularly chainable, quasi-chainable) if for every $ϵ > 0$ there exists a chain (resp. circular chain, quasi-chain) of mesh $< ϵ$ covering S.

If S is connected, then S is chainable if and only if S is quasi-chainable (Lemma 30 in [21]).

Proposition 8.10.
Not being quasi-chainable is a $Σ_{2}^{0}$ invariant in $τ_{up V}$ . If a compact space is circularly chainable but not chainable, then it is minimal satisfying this invariant and hence it has strong computable type.
Proof.
If $U \subseteq Q$ is a finite union of rational open balls, then we write $\overline{U}$ for the corresponding union of closed balls. By a standard compactness argument, a compact set $S \subseteq Q$ is quasi-chainable if for every rational $ϵ > 0$ there exists a quasi-chain $C = (C_{0}, \dots, C_{n})$ of mesh $< ϵ$ covering S, with the following additional properties: $\overline{C_{i}} \cap \overline{C_{j}} = \emptyset$ for $| i - j | > 1$ , and $diam (\overline{C_{i}}) < ϵ$ . Finite unions of rational closed balls are effectively compact, so these additional properties are c.e., and whether C covers S is effectively open in the upper Vietoris topology. Therefore, being quasi-chainable is a $Π_{2}^{0}$ invariant.

If S is not chainable then S is not quasi-chainable. If in addition S is circularly chainable, then every proper compact subset of S is quasi-chainable. Indeed, let $T ⊊ S$ be compact, $x \in S ∖ T$ and $ϵ < d_{Q} (x, T)$ , and let $C = (C_{0}, \dots, C_{n})$ be a circular chain of mesh $< ϵ$ covering S. We can assume that $x \in C_{n}$ , applying a circular permutation if needed. As $diam (C_{n}) < ϵ < d_{Q} (x, T)$ , the set $C_{n}$ is disjoint from T. As a result, $(C_{0}, \dots, C_{n - 1})$ is a quasi-chain covering T. □

It can be shown that if a compact space is in $H_{1}$ , then it is not quasi-chainable. We do not know whether the converse implication holds, in particular whether spaces that are circularly chainable but not chainable are $H_{1}$ -minimal.
8.4. A space that properly contains copies of itself

Theorem 4.8 states in particular that if a compact space X is minimal for some $Σ_{2}^{0}$ topological invariant then X has strong computable type. We show here that the converse implication does not hold. We actually prove more: we build a compact space X that has strong computable type and contains a proper subset $X^{'}$ that is homeomorphic to X. It implies that X cannot be minimal for any topological invariant, because any invariant satisfied by X is also satisfied by $X^{'}$ . Moreover, the space X is to our knowledge the first example of an infinite-dimensional space having strong computable type.

The space X is built as follows. Let $f : S_{1} \to Q$ be a so-called “space-filling curve”, i.e. a surjective continuous function (such a function from $[0, 1]$ to Q exists by the Hahn-Mazurkiewicz theorem, see Theorem 6.3.14 in [14], and can be extended to the circle by joining the two endpoints). Let $X = Q \cup_{f} B_{2}$ be the adjunction space, which is the quotient of the disjoint union $Q ⊔ B_{2}$ by the equivalence relation generated by $x \sim f (x)$ for $x \in S_{1} = \partial B_{2}$ .

Note that X contains a proper subset which is homeomorphic to X: indeed, X properly contains Q, which contains a copy of X.

Proposition 8.11.
If $f : S_{1} \to Q$ is surjective continuous, then the space $Q \cup_{f} B_{2}$ has strong computable type.
Proof.
Although X cannot be $H_{2}$ -minimal, we show that there is a continuous function $q : X \to S_{2}$ which is not null-homotopic (i.e. $X \in H_{2}$ ) and such that for any compact subset $Y ⊊ X$ , the restriction $q |_{Y} : Y \to S_{2}$ is null-homotopic.

The condition that f is surjective implies that Q has empty interior in X: every $y \in Q$ is the image by f of some $x \in \partial B_{2}$ , which is a limit of a sequence $x_{n} \in B_{2} ∖ \partial B_{2}$ ; therefore in X, y is the limit of $x_{n} \in X ∖ Q$ .

The quotient space $X / Q$ is homeomorphic to $B_{2} / \partial S_{2}$ , which is homeomorphic to $S_{2}$ , so we can type the quotient map $q : X \to X / Q$ as $q : X \to S_{2}$ . We claim that q is not null-homotopic.

Proposition 0.17 in [16] states that if a pair $(X, A)$ satisfies the homotopy extension property and A is contractible, then the quotient map $q : X \to X / A$ is a homotopy equivalence. The pair $(X, Q)$ satisfies the homotopy extension property because X is obtained by attaching a disk to Q along its boundary (see the proof of Proposition 0.16 in [16]). The space Q is contractible, so the quotient map $q : X \to X / Q ≅ S_{2}$ is a homotopy equivalence, i.e. there exists a function $p : S_{2} \to X$ such that $p \circ q$ is homotopic to ${id}_{X}$ and $q \circ p$ is homotopic to ${id}_{S_{2}}$ . It implies that q is not null-homotopic: otherwise the function ${id}_{S_{2}}$ , which is homotopic to $q \circ p$ , would be null-homotopic as well, i.e. $S_{2}$ would be contractible.

We now show that if Y is a compact proper subset of X, then the restriction $q |_{Y} : Y \to S_{2}$ is null-homotopic. As Q has empty interior in X, the interior of $B_{2}$ is dense in X so it contains a point $x \in X ∖ Y$ . The space $X ∖ {x}$ is contractible, because it deformation retracts to Q which is contractible. Therefore, the restriction of q to $X ∖ {x}$ is null-homotopic, so its restriction to $Y \subseteq X ∖ {x}$ is null-homotopic, by restriction of the homotopy.

As a result, for a compact set $Y \subseteq X$ , one has $Y \neq X$ if and only if the restriction of q to Y is null-homotopic.

We now prove that X has computable type. Let $X_{0} \subseteq Q$ be a semicomputable copy of X, and $ϕ : X_{0} \to X$ a homeomorphism. The previous discussion implies that for an open set $U \subseteq Q$ , U intersects $X_{0}$ if and only if the restriction of $q \circ ϕ$ to $X_{0} ∖ U$ is null-homotopic.

We now use the properties of the numberings $ν_{[X; Y]}$ from Theorem 6.7. Let $i_{0}$ be an index of a constant computable function $f_{i_{0}} : Q \to S_{2}$ . Note that $i_{0} \in dom (ν_{[Z; S_{2}]})$ for all $Z \subseteq Q$ . Let $i_{1}$ be such that $ν_{[X_{0}; S_{2}]} (i_{1})$ is the homotopy class of $q \circ ϕ$ . The definition of $ν_{[X; Y]}$ implies that for any open set $U \subseteq Q$ , $i_{1} \in dom (ν_{[X_{0} ∖ U; S_{2}]})$ and $ν_{[X_{0} ∖ U; S_{2}]} (i_{1})$ is the homotopy class of the restriction of q to $X_{0} ∖ U$ .

We saw that a basic open set $U \subseteq Q$ intersects $X_{0}$ if and only if $q |_{X_{0} ∖ U}$ is null-homotopic, which is equivalent to $ν_{[X_{0} ∖ U; S_{2}]} (i_{1}) = ν_{[X_{0} ∖ U; S_{2}]} (i_{0})$ . As $X_{0}$ is semicomputable, so is $X_{0} ∖ U$ , therefore this predicate is c.e. and $X_{0}$ is computable, which shows that $X_{0}$ has computable type.

The argument holds relative to any oracle, i.e. if $X_{0}$ is semicomputable relative to an oracle O, then $X_{0}$ is computable relative to O. Therefore, X has strong computable type. □

9. Open questions

Our study leaves several questions open.

We have revisited several results from the literature on computable type, identifying a $Σ_{2}^{0}$ invariant for which the space or the pair is minimal. We do not know whether the results in [2] on finite simplicial complexes can be revisited in a similar way.

Question 1.

If a finite simplicial pair $(X, A)$ has strong computable type, is it minimal satisfying some $Σ_{2}^{0}$ invariant?

The example from Section 8.4 is a space that has strong computable type and properly contains copies of itself. The argument strongly relies on the fact that it contains the Hilbert cube, which is infinite-dimensional.

Question 2.

Is there a finite-dimensional space that has strong computable type and properly contains copies of itself?

Theorem 5.17 assumes that the pair is minimal for some $Σ_{2}^{0}$ invariant. Can this assumption be dropped?

Question 3.

Is it always true that if $(X, A)$ has strong computable type, then ${SCT}_{(X, A)} ⩽_{W}^{t} C_{N}$ ?

Question 4.

Is there a compact space having (strong) computable type and infinitely many connected components?

We also mention a surprisingly difficult question, already raised in [9].

Question 5.

If two pairs $(X_{1}, A_{1})$ and $(X_{2}, A_{2})$ have (strong) computable type, does $(X_{1}, A_{1}) \times (X_{2}, A_{2}) = (X_{1} \times X_{2}, X_{1} \times A_{2} \cup A_{1} \times X_{2})$ have (strong) computable type?

Footnotes

Acknowledgements

We thank Emmanuel Jeandel for interesting discussions on the topic, as well as the anonymous referees for their careful reading and helpful comments.

Compact n -manifolds are H n -minimal

References

Alexandroff, On the dimension of normal spaces, Proceedings of the Royal Society of London. Series A. Mathematical an d Physical Sciences 189(1016) (1947), 11–39. doi:10.1098/rspa.1947.0027.

D.E.

Amir and

Hoyrup, Computability of finite simplicial complexes, in: 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, Paris, France, July 4–8, 2022,

Bojanczyk,

Merelli and

D.P.

Woodruff, eds, LIPIcs, Vol. 229, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, pp. 111:1–111:16. doi:10.4230/LIPIcs.ICALP.2022.111.

D.E.

Amir and

Hoyrup, Comparing computability in two topologies, The Journal of Symbolic Logic (2023), 1–19. doi:10.1017/jsl.2023.17.

Borsuk, Über eine Klasse von lokal zusammenhangende Räumen, Fundamenta Mathematicae 19 (1932), 220–242. doi:10.4064/fm-19-1-220-242.

Brattka,

Gherardi and

Pauly, Weihrauch complexity in computable analysis, in: Handbook of Computability and Complexity in Analysis,

Brattka and

Hertling, eds, Theory and Applications of Computability, Springer, Cham, 2021, pp. 367–417. doi:10.1007/978-3-030-59234-9_11.

G.E.

Bredon,

J.H.

Ewing,

F.W.

Gehring and

P.R.

Halmos, Topology and Geometry, Graduate Texts in Mathematics, Springer, 1993. ISBN 9780387979267.

Burnik and

Iljazović, Computability of 1-manifolds, Log. Methods Comput. Sci. 10(2) (2014).

Čadek,

Krčál,

Matoušek,

Sergeraert,

Vokřínek and

Wagner, Computing all maps into a sphere, Journal of the ACM 61(3) (2014). doi:10.1145/2597629.

Čelar and

Iljazović, Computability of products of chainable continua, Theory Comput. Syst. 65(2) (2021), 410–427. doi:10.1007/s00224-020-10017-6.

10.

Čelar and

Iljazović, Computability of glued manifolds, Journal of Logic and Computation 32(1) (2021), 65–97. doi:10.1093/logcom/exab063.

11.

Čičković,

Iljazović and

Validžić, Chainable and circularly chainable semicomputable sets in computable topological spaces, Arch. Math. Log. 58(7–8) (2019), 885–897. doi:10.1007/s00153-019-00667-w.

12.

Collins, Computability of homology for compact absolute neighbourhood retracts, in: Sixth International Conference on Computability and Complexity in Analysis, CCA 2009, Ljubljana, Slovenia, August 18–22, 2009,

Bauer,

Hertling and

Ko, eds, OASICS, Vol. 11, Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, Germany, 2009.

13.

R.G.

Downey and

A.G.

Melnikov, Computably compact metric spaces, Bulletin of Symbolic Logic (2023), 1–59. doi:10.1017/bsl.2023.16.

14.

Engelking, General Topology. Rev. and Compl. ed., Vol. 6, Rev. and compl. ed. edn, Heldermann Verlag, Berlin, 1989, viii + 529. ISBN 3-88538-006-4.

15.

Hanner, Some theorems on absolute neighborhood retracts, Arkiv for Matematik 1(5) (1951), 389–408. doi:10.1007/BF02591376.

16.

Hatcher, Algebraic Topology, Algebraic Topology, Cambridge University Press, 2002. ISBN 9780521795401.

17.

Hertling, Is the Mandelbrot set computable?, Math. Log. Q. 51(1) (2005), 5–18. doi:10.1002/malq.200310124.

18.

Horvat,

Iljazović and

Pažek, Computability of pseudo-cubes, Annals of Pure and Applied Logic 171(8) (2020), 102823. doi:10.1016/j.apal.2020.102823.

19.

S.-T.

Hu, Mappings of a normal space into an absolute neighborhood retract, Transactions of the American Mathematical Society 64(2) (1948), 336–358. https://www-jstor-org.web.bisu.edu.cn/stable/1990506 . doi:10.1090/S0002-9947-1948-0026325-3.

20.

Hurewicz and

Wallman, Dimension Theory (PMS-4), Princeton University Press, 1941. https://www-jstor-org.web.bisu.edu.cn/stable/j.ctt183pk8v . ISBN 9780691627748.

21.

Iljazović, Chainable and circularly chainable co-r.e. sets in computable metric spaces, Journal of Universal Computer Science 15(6) (2009), 1206–1235.

22.

Iljazović, Co-c.e. spheres and cells in computable metric spaces, Logical Methods in Computer Science 7(3) (2011).

23.

Iljazovic, Compact manifolds with computable boundaries, Log. Methods Comput. Sci. 9(4) (2013).

24.

Iljazović, Computability of graphs, Mathematical Logic Quarterly 66(1) (2020), 51–64. doi:10.1002/malq.201900025.

25.

Iljazović and

Kihara, Computability of subsets of metric spaces, in: Handbook of Computability and Complexity in Analysis,

Brattka and

Hertling, eds, Springer, 2020.

26.

Iljazović and

Sušić, Semicomputable manifolds in computable topological spaces, Journal of Complexity 45 (2018), 83–114. doi:10.1016/j.jco.2017.11.004.

27.

Jeandel, Enumeration reducibility in closure spaces with applications to logic and algebra, in: 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20–23, 2017, IEEE Computer Society, 2017, pp. 1–11. doi:10.1109/LICS.2017.8005086.

28.

A.S.

Kechris, Classical Descriptive Set Theory, Springer, 1995. ISBN 0387943749.

29.

Kihara and

Pauly, Point degree spectra of represented spaces, Forum of Mathematics, Sigma 10 (2022), e31. doi:10.1017/fms.2022.7.

30.

Lupini,

Melnikov and

Nies, Computable topological Abelian groups, Journal of Algebra 615 (2023), 278–327. https://www-sciencedirect-com-443.web.bisu.edu.cn/science/article/pii/S0021869322004719 . doi:10.1016/j.jalgebra.2022.10.003.

31.

Mardešić, Equivalence of singular and Čech homology for ANR-s. Application to unicoherence, Fundamenta Mathematicae 46 (1958), 29–45. doi:10.4064/fm-46-1-29-45.

32.

J.S.

Miller, Effectiveness for embedded spheres and balls, Electronic Notes in Theoretical Computer Science 66(1) (2002), 127–138, CCA 2002, Computability and Complexity in Analysis.

33.

Y.N.

Moschovakis, Descriptive Set Theory, 2nd edn, Mathematical Surveys and Monographs, American Mathematical Society, 2009. ISBN 9780821848135.

34.

Pauly, On the topological aspects of the theory of represented spaces, Computability 5(2) (2016), 159–180. doi:10.3233/COM-150049.

35.

Pauly, Weihrauch degrees of problems related to topological circles, 2021, Continuity, Computability, Constructivity (CCC).

36.

Schröder, Effective metrization of regular spaces, in: Computability and Complexity in Analysis, Vol. 235,

K.-I.

Ko,

Nerode,

M.B.

Pour-El,

Weihrauch and

Wiedermann, eds, Informatik Berichte, FernUniversität Hagen, 1998, pp. 63–80.

37.

Scott, Data types as lattices, SIAM Journal on Computing 5(3) (1976), 522–587. doi:10.1137/0205037.

38.

V.L.

Selivanov, Towards a descriptive set theory for domain-like structures, Theoretical Computer Science 365(3) (2006), 258–282. https://www-sciencedirect-com-443.web.bisu.edu.cn/science/article/pii/S0304397506005032 . doi:10.1016/j.tcs.2006.07.053.

39.

A.L.

Selman, Arithmetical reducibilities I, Mathematical Logic Quarterly 17(1) (1971), 335–350. doi:10.1002/malq.19710170139.

40.

van Mill, The Infinite-Dimensional Topology of Function Spaces, North-Holland Mathematical Library, Elsevier Science, 2001. ISBN 9780444505576.

41.

Vaught, Invariant sets in topology and logic, Fundamenta Mathematicae 82(3) (1974), 269–294. http://eudml.org/doc/214667 . doi:10.4064/fm-82-3-269-294.

Strong computable type

Abstract

Keywords

1. Introduction

1.1. Summary of the main results

Theorem 1 (Theorem 3.4).

Theorem 2 (Theorem 4.8).

2.1. Enumeration reducibility

4.1. Definition

5.1. A topological necessary condition

Corollary 5.1 (Necessary condition).

5.6.1. The product of two pairs

Definition 5.23 (Cone).

6.1. Absolute neighborhood retracts (ANRs)

Theorem 6.6 (Borsuk’s homotopy extension theorem).

6.2. Homotopy classes

6.3.1. Extension of functions

Definition 6.10 (The invariant E ( Y ) ).

Definition 6.12 (The invariant H ( Y ) ).

7.1. Properties of E ( Y )

Definition 7.7 (The invariant E n ).

Theorem 7.9 (Theorem 3.6.3 in [40]).

Definition 7.13 (The invariant H n ).

Theorem 7.22 (Theorem 1 in [31]).

Theorem 7.23 (Corollaries VIII.2 and VIII.3 (p. 149) in [20]).

Theorem 7.24 (Corollary 4 (p. 150) in [20]).

8. Examples

8.1. Examples of E n -minimal pairs

8.1.1. Chainable continuum between two points

Footnotes

Acknowledgements

Compact n -manifolds are H n -minimal

References

Definition 6.10 (The invariant $E (Y)$ ).

Definition 6.12 (The invariant $H (Y)$ ).

7.1. Properties of $E (Y)$

Definition 7.7 (The invariant $E_{n}$ ).

Definition 7.13 (The invariant $H_{n}$ ).

8.1. Examples of $E_{n}$ -minimal pairs