# Strong computable type111This version is an update from July 2023, in which
Section 8.4 was added.

Djamel Eddine Amir and Mathieu Hoyrup

Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### 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
[Her05].

It turns out that for certain sets, semicomputability is actually equivalent
to computability. It was discovered by Miller [Mil02] 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 [Ilj11], manifolds [Ilj13]
and many other sets in a series of articles with several authors [Ilj09,
Ilj11, Ilj13, BI14, IS18, ČIV19, HIP20, Ilj20, ČI21b, ČI21a]. We recently
identified which finite simplicial complexes have computable type in [AH22].
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 [Mil02], Iljazović used some form of Brouwer’s
fixed-point theorem in [Ilj11, Ilj13].

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 [Ilj09, Ilj13] and then extended to computably Hausdorff spaces [ČIV19,
IS18]. 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 [Sch98] 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\mathbb{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 a pair $(X,A)$ is minimal satisfying some $\Sigma^{0}_{2}$ 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 $\Sigma^{0}_{2}$ 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
$\Sigma^{0}_{2}$ 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 $\mathbb{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 $\SS_{n}$. This analysis immediately induces
topological invariants of low descriptive complexity, which are very classical
in topology.

######  Theorem 3.

The following topological invariants are $\Sigma^{0}_{2}$ in the upper
Vietoris topology:

$\displaystyle(X,A)\in\mathsf{E}_{n}$ $\displaystyle\iff\text{there is a
continuous function }f:A\to\SS_{n}\text{ having no continuous}$
$\displaystyle\qquad\qquad\text{extension }F:X\to\SS_{n},$ $\displaystyle
X\in\mathsf{H}_{n}$ $\displaystyle\iff\text{there is a continuous function
}f:X\to\SS_{n}\text{ which is not null-homotopic}.$

We thoroughly study these topological invariants and revisit several results
of the literature, showing how they can be obtained by identifying a suitable
$\Sigma^{0}_{2}$ 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 $(\mathbb{B}_{n+1},\SS_{n})$ is $\mathsf{E}_{n}$-minimal,

  * •

Every closed $n$-manifold is $\mathsf{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 $\Sigma^{0}_{2}$) 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 [Ilj13] 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 [BI14] or [Ilj20]; 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 [Ilj11], 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\mathbb{N}$ is computably enumerable (c.e.) if there exists a
Turing machine that, on input $n\in\mathbb{N}$, halts if and only if $n\in A$.
An enumeration of $A$ is any function $f:\mathbb{N}\to\mathbb{N}$ such that
$A=\\{n\in\mathbb{N}:\exists p\in\mathbb{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\mathbb{N}$. We say that $A$ is enumeration reducible to $B$,
written $A\leq_{e}B$, if one of the following equivalent statements holds:

  1. 1.

There is an effective procedure producing an enumeration of $A$ from any
enumeration of $B$,

  2. 2.

There exists a c.e. set $W\subseteq\mathbb{N}$ such that, for all
$x\in\mathbb{N}$,

$x\in A\iff\text{there exists a finite set }D\subseteq B\text{ such that
}\langle x,D\rangle\in W,$

  3. 3.

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

In condition 2., $\langle x,D\rangle$ 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 [Sel71].

###  2.2 Computable $T_{0}$-spaces

######  Definition 2.2.

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

We will often denote a computable $T_{0}$-space by $(X,\tau)$, 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,\tau)$ is also a computable $T_{0}$-space, by taking the
subspace topology and the numbered basis $B^{Y}_{i}=Y\cap B^{X}_{i}$. The
product of two computable $T_{0}$-spaces is naturally a computable
$T_{0}$-space.

In a computable $T_{0}$-space $(X,\tau)$, 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
[KP22]. In particular, a computable reduction between points can be defined
using enumeration reducibility as follows.

######  Definition 2.3.

Let $(X,\tau_{X})$ and $(Y,\tau_{Y})$ be computable $T_{0}$-spaces. A point
$x$ in $(X,\tau_{X})$ is computable relative to a point $y$ in $(Y,\tau_{Y})$
if

$\left\\{i\in\mathbb{N}:x\in
B_{i}^{X}\right\\}\leq_{e}\left\\{i\in\mathbb{N}:y\in B_{i}^{Y}\right\\}.$

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\rightarrow 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,\tau,(B_{i})_{i\in\mathbb{N}})$
is:

  1. 1.

Effectively compact, or semicomputable, if it is compact and the set

$\left\\{(i_{1},\ldots,i_{n})\in\mathbb{N}^{\ast}:A\subseteq
B_{i_{1}}\cup\ldots\cup B_{i_{n}}\right\\}$

is c.e.,

  2. 2.

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

  3. 3.

Computable if it is effectively compact and computably overt,

  4. 4.

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

  5. 5.

Effectively closed or $\Pi^{0}_{1}$ 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 [Pau16] 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

$R^{\exists}:=\\{x\in X:\exists y\in Y,(x,y)\in R\\}$

is effectively closed as well,

  * •

If $R\subseteq X\times Y$ is effectively open, then its universal
quantification

$R^{\forall}:=\\{x\in X:\forall y\in Y,(x,y)\in R\\}$

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\mathbb{N}^{2}$
such that $R=\bigcup_{(i,j)\in E}B^{X}_{i}\times B^{Y}_{j}$. One has

$\displaystyle x\in R^{\forall}$ $\displaystyle\iff\\{x\\}\times Y\subseteq R$
(1) $\displaystyle\iff\exists\text{ finite set }L\subseteq E,\\{x\\}\times
Y\subseteq\bigcup_{(i,j)\in L}B^{X}_{i}\times B^{Y}_{j}$ (2)

because $\\{x\\}\times Y$ is compact. Let $\mathcal{F}$ be the collection of
(indices of) finite sets $L\subseteq E$ such that $Y\subseteq\bigcup_{(i,j)\in
L}B^{Y}_{j}$. As $Y$ is effectively compact, $\mathcal{F}$ is a c.e. set. For
each $L\in\mathcal{F}$, let $U_{L}=\bigcap_{(i,j)\in L}B^{X}_{i}$. The
equivalence (2) implies that $R^{\forall}=\bigcup_{L\in\mathcal{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 ([Mos09]). We have already seen the classes
$\Sigma^{0}_{1}$ and $\Pi^{0}_{1}$. In this article, we will also need another
class.

######  Definition 2.6.

A set $A$ in a computable $T_{0}$-space $(X,\tau,(B_{i})_{i\in\mathbb{N}})$ is
$\Sigma^{0}_{2}$ if it can be expressed as

$A=\bigcup_{n\in\mathbb{N}}A_{n}\setminus B_{n}$

where $A_{n},B_{n}$ are uniformly effective closed sets (i.e. $\Pi^{0}_{1}$).

Observe that one can equivalently require $A_{n},B_{n}$ to be effectively
_open_ , as $A_{n}\setminus B_{n}=(X\setminus B_{n})\setminus(X\setminus
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 [Sco76] and Selivanov [Sel06], to make sure that
the classes $\Sigma^{0}_{1}$ and $\Pi^{0}_{1}$ are contained in the class
$\Sigma^{0}_{2}$.

###  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 [Sch98] for instance.

######  Definition 2.7.

  1. 1.

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

  2. 2.

A computable $T_{0}$-space $(X,\tau,(B_{i})_{i\in\mathbb{N}})$ is computably
Hausdorff if the diagonal $\Delta=\\{(x,x):x\in X\\}$ is an effectively closed
subset of $X\times X$, i.e. if there exists some c.e. set
$\mathcal{D}\subseteq\mathbb{N}^{2}$ satisfying

$(X\times X)\setminus\Delta=\left\\{(x,y)\in X\times X:x\neq
y\right\\}=\bigcup_{(i,j)\in\mathcal{D}}B_{i}\times B_{j}.$

######  Remark 2.8.

The following facts are standard and can be found in [Pau16] for instance:

  * •

A computable metric space is a computable $T_{0}$-space, by taking the basis
of metric balls $B_{d}(\alpha_{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\rightarrow Y$ is a computable
injective function, then its inverse $f^{-1}:f(K)\rightarrow 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)\setminus
f(K\setminus B_{i})$. As $K\setminus B_{i}$ is semicomputable, its image
$f(K\setminus B_{i})$ is semicomputable as well. As $Y$ is computably
Hausdorff, $f(K\setminus 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]^{\mathbb{N}}$ endowed with the complete
metric

$d_{Q}(x,y)=\sum_{i}2^{-i}|x_{i}-y_{i}|.$

Here are some important facts about the Hilbert cube.

######  Fact 2.11.

The Hilbert cube $Q$ satisfies the following properties:

  1. 1.

Let $(\alpha_{i})_{i\in\mathbb{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},\alpha)$ a computable metric space.

  2. 2.

The Hilbert cube is effectively compact,

  3. 3.

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

  4. 4.

Every computable metric space embeds effectively into the Hilbert cube. More
precisely, for every computable metric space $(X,d,\alpha)$ there exists a
computable embedding $f:X\to Q$ such that $f^{-1}$ is computable, defined as
$f(x)=(1/(1+d(x,\alpha_{i})))_{i\in\mathbb{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
[Mil02], was studied by Iljazović et al. in [Ilj09, Ilj11, Ilj13, BI14, IS18,
ČIV19, HIP20, Ilj20, ČI21b, ČI21a] and by the authors in [AH22]. The first
formal definition as given in [IS18].

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)\subsetneq(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 [Ilj09] and [ČIV19]
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 [Ilj09, Ilj13] imply the results in
[ČIV19, IS18]).

######  Theorem 3.4.

For a pair $(X,A)$, the following statements are equivalent:

  1. 1.

$(X,A)$ has computable type (on the Hilbert cube),

  2. 2.

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

  3. 3.

$(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 [Sch98], so we
need to introduce the computable version of regular spaces.

######  Definition 3.5.

A computable $T_{0}$-space $(X,\tau)$ 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\mathbb{N}}$ and a sequence of effective
closed sets $(F_{k})_{k\in\mathbb{N}}$ such that $U_{k}\subseteq
F_{k}\subseteq B_{n}$ and $B_{n}=\bigcup_{k}U_{k}$.

######  Proposition 3.6.

Let $(X,\tau)$ be a computable $T_{0}$-space. If $(X,\tau)$ is effectively
compact and computably Hausdorff, then it is computably regular.

###### Proof.

Let $\mathcal{D}\subseteq\mathbb{N}^{2}$ witness that the space is computably
Hausdorff. Let $n\in\mathbb{N}$. The set $K=X\setminus B_{n}$ is effectively
compact, so one can compute an enumeration $(L_{k})_{k\in\mathbb{N}}$ of all
the finite sets $L\subseteq\mathcal{D}$ such that $K\subseteq\bigcup_{(i,j)\in
L}B_{j}$. To each such $L_{k}$ associate the pair $(U_{k},F_{k})$ defined by

$\displaystyle U_{k}$ $\displaystyle=\bigcap_{(i,j)\in L_{k}}B_{i}$
$\displaystyle F_{k}$ $\displaystyle=X\setminus\bigcup_{(i,j)\in L_{k}}B_{j}.$

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\mathcal{D}$. As $X\setminus
B_{n}\subseteq\bigcup_{(i,j)\in L_{k}}B_{j}$, one has
$F_{k}=X\setminus\bigcup_{(i,j)\in L_{k}}B_{j}$$\subseteq B_{n}$.

Finally, we show that $B_{n}=\bigcup_{k}U_{k}$. Let $x\in B_{n}$. As $x\notin
K$, the compact set $\\{x\\}\times K$ is contained in $\bigcup_{(i,j)\in
D}B_{i}\times B_{j}$, so there exists a finite set $L\subseteq\mathcal{D}$
such that $\\{x\\}\times K\subseteq\bigcup_{(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^{\prime}\subseteq L$ be the result of this
operation. There exists $k$ such that $L^{\prime}=L_{k}$, and $x\in U_{k}$. ∎

Schröder proved the following effective Urysohn metrization theorem (Theorem
6.1 in [Sch98]) : every computably regular space $X$ admits a computable
metric, i.e. a computable function $d:X\times X\to\mathbb{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,\tau)$ is a computably regular space, then there exists a computable
injection $h:X\rightarrow Q$.

###### Proof.

The proof of Theorem 6.1 in [Sch98] 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\mathbb{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\mathbb{N}}$. ∎

######  Corollary 3.8.

If $K$ is a semicomputable set in a computably Hausdorff space $(X,\tau)$,
then there exists a computable embedding $h:K\to Q$ whose inverse is
computable.

###### Proof.

Consider the subspace $(K,\tau_{K})$ with the induced topology
$\tau_{K}=\\{U\cap K:U\in\tau\\}$. 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,\tau_{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,\tau)$ 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 $\mathcal{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
[Mil02, Ilj09, Ilj11, Ilj13, BI14, IS18, ČIV19, HIP20, Ilj20, ČI21b, ČI21a,
AH22] 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 [AH22]. 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 $\mathcal{K}(Q)$ be the hyperspace of $Q$, i.e. the space of compact
subsets of $Q$. It can be equipped with:

  1. 1.

The upper Vietoris topology $\tau_{up\mathcal{V}}$ generated by the sets of
the form $\\{K\in\mathcal{K}(Q):K\subseteq U\\}$, where $U$ ranges over the
open subsets of $Q$,

  2. 2.

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

  3. 3.

The Vietoris topology $\tau_{\mathcal{V}}$ generated by $\tau_{up\mathcal{V}}$
and $\tau_{low\mathcal{V}}$.

These three topological spaces are computable $T_{0}$-spaces. A countable
basis of $\tau_{up\mathcal{V}}$ is obtained by taking $U$ among the finite
unions of rational balls of $Q$. A countable subbasis of
$\tau_{low\mathcal{V}}$ is obtained by taking $U$ among the rational balls of
$Q$, and adding $\mathcal{K}(Q)$ to the subbasis. The space
$(\mathcal{K}(Q),\tau_{\mathcal{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 [IK20] for instance; it is
sufficient to prove it for the stronger topology $\tau_{\mathcal{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$,

$\displaystyle K\text{ is semicomputable }\iff K\text{ is a computable element
of }(\mathcal{K}(Q),\tau_{up\mathcal{V}}),$ $\displaystyle K\text{ is
computable }\iff K\text{ is a computable element of
}(\mathcal{K}(Q),\tau_{low\mathcal{V}}).$

The topology $\tau_{low\mathcal{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 $\mathcal{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:

  1. 1.

$(X,A)$ has strong computable type,

  2. 2.

For every copy $(Y,B)$ of $(X,A)$ in $Q$, the element $Y$ of the space
$(\mathcal{K}(Q),\tau_{\mathcal{V}})$ is computable relative to the element
$(Y,B)$ of the product space $(\mathcal{K}^{2}(Q),\tau_{up\mathcal{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 $\mathcal{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 [Jea17] of the sets
$A\subseteq\mathbb{N}$ that are _total_ , i.e. whose complement
$\mathbb{N}\setminus A$ is enumeration reducible to $A$.

We first need two definitions.

######  Definition 4.5.

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

We recall that $(Y,B)$ is a proper subpair of $(X,A)$, written
$(Y,B)\subsetneq(X,A)$, if $Y\subsetneq X$ and $B\subseteq A$.

######  Definition 4.6.

Let $\mathcal{P}$ be a property of pairs. A pair $(X,A)\subseteq Q$ is
$\mathcal{P}$-minimal if $(X,A)\in\mathcal{P}$ and for every proper subpair
$(Y,B)\subsetneq(X,A)$, one has $(Y,B)\notin\mathcal{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:

  1. 1.

$(X,A)$ has strong computable type,

  2. 2.

For every copy $(Y,B)$ of $(X,A)$ in $Q$, there exists a property
$\mathcal{P}$ of pairs which is $\Pi^{0}_{1}$ in the topology
$\tau_{up\mathcal{V}}^{2}$ and such that $(Y,B)$ is $\mathcal{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
$\tau_{\mathcal{V}}$ neighborhoods of $X$ is enumeration reducible to the set
of basic $\tau_{up\mathcal{V}}^{2}$ neighborhoods of $(X,A)$ iff there exists
a $\Pi^{0}_{1}$ property $\mathcal{P}$ such that $(X,A)$ is
$\mathcal{P}$-minimal.

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

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

We first show that $\mathcal{U}$ is effectively open in
$\tau_{up\mathcal{V}}^{2}$. If $\sigma=\sigma_{0}\ldots\sigma_{k}$ is a finite
sequence of basic $\tau_{up\mathcal{V}}^{2}$-open sets and $U$ is a basic open
subset of $Q$, then let

$\mathcal{U}_{(\sigma,U)}=\\{(X^{\prime},A^{\prime}):\forall i\leq
k,(X^{\prime},A^{\prime})\in\sigma_{i}\text{ and }X^{\prime}\subseteq
Q\setminus\overline{U}\\}.$

It is an effective $\tau_{up\mathcal{V}}^{2}$-open set, and $\mathcal{U}$ is
the union of all the $\mathcal{U}_{(\sigma,U)}$ such that $M$ outputs $U$
after reading $\sigma$, so it is a c.e. union. Therefore $\mathcal{U}$ is an
effective $\tau_{up\mathcal{V}}^{2}$-open set and $\mathcal{P}$ is
$\Pi^{0}_{1}$ in $\tau_{up\mathcal{V}}^{2}$.

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

In particular, this characterization immediately implies a simple sufficient
condition for having strong computable type.

######  Theorem 4.8.

Let $\mathcal{P}$ be a topological invariant which is $\Sigma_{2}^{0}$ in
$\tau_{up\mathcal{V}}^{2}$. Every minimal element of $\mathcal{P}$ has strong
computable type.

###### Proof.

Let $\mathcal{P}=\bigcup_{n}\mathcal{P}_{n}\setminus\mathcal{Q}_{n}$ where
each $\mathcal{P}_{n},\mathcal{Q}_{n}$ is $\Pi_{1}^{0}$ in
$\tau_{up\mathcal{V}}^{2}$. Assume that $(X,A)$ is $\mathcal{P}$-minimal and
let $(Y,B)$ be a copy of $(X,A)$ in $Q$. This copy belongs to some
$\mathcal{P}_{n}\setminus\mathcal{Q}_{n}$. Let us show that $(Y,B)$ must be
$\mathcal{P}_{n}$-minimal. Let $(Y^{\prime},B^{\prime})$ be a proper subpair
of $(Y,B)$. The set $\mathcal{Q}_{n}$ is $\Pi^{0}_{1}$ in
$\tau_{up\mathcal{V}}^{2}$ so it is an upper set. As
$(Y,B)\notin\mathcal{Q}_{n}$, $(Y^{\prime},B^{\prime})\notin\mathcal{Q}_{n}$
as well. As $(Y,B)$ is $\mathcal{P}$-minimal,
$(Y^{\prime},B^{\prime})\notin\mathcal{P}$, so
$(Y^{\prime},B^{\prime})\notin\mathcal{P}_{n}$. Therefore, $(Y,B)$ is
$\mathcal{P}_{n}$-minimal.

We have shown that each copy $(Y,B)$ of $(X,A)$ is $\mathcal{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 $\Sigma^{0}_{2}$ 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
$\mathcal{P}$-minimal for some $\mathcal{P}$. The definition of minimality
involves all the proper subpairs $(Y,B)\subsetneq(X,A)$. However, because
$\mathcal{P}$ is $\Pi^{0}_{1}$ in $\tau_{up\mathcal{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 $\mathcal{P}\subseteq\mathcal{K}(Q)$ is closed in
$\tau_{up\mathcal{V}}$ or open in $\tau_{low\mathcal{V}}$, then it is an upper
set: if $K\subseteq K^{\prime}\subseteq Q$ and $K\in\mathcal{P}$, then
$K^{\prime}\in\mathcal{P}$.

  * •

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

It gives a shortcut to prove that a pair $(X,A)$ is $\mathcal{P}$-minimal,
when $\mathcal{P}$ is an upper set, for instance when $\mathcal{P}$ is
$\Pi^{0}_{1}$ or more generally closed in the topology
$\tau_{up\mathcal{V}}^{2}$.

######  Definition 4.9.

Let $(X,A)$ be a pair and $\mathcal{F}$ a family of proper subpairs of
$(X,A)$. We say that $\mathcal{F}$ is cofinal if every proper subpair of
$(X,A)$ is contained in some pair in $\mathcal{F}$.

The next result is elementary but very useful.

######  Lemma 4.10.

Let $\mathcal{P}$ be a property of pairs which is an upper set. Let
$(X,A)\in\mathcal{P}$ and $\mathcal{F}$ be cofinal. If no pair of
$\mathcal{F}$ is in $\mathcal{P}$ then $(X,A)$ is $\mathcal{P}$-minimal.

###### Proof.

If $(Y,B)\subsetneq(X,A)$, then $(Y,B)\subseteq(Z,C)\subsetneq(X,A)$ for some
$(Z,C)\in\mathcal{F}$, by cofinality. As $(Z,C)\notin\mathcal{P}$ by
assumption and $\mathcal{P}$ is an upper set, $(Y,B)\notin\mathcal{P}$. ∎

We will implicitly apply this observation, notably with the following
families:

  * •

The family $\\{(Y,Y\cap A):Y\subsetneq X\\}$ is cofinal,

  * •

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

  * •

If $A$ has empty interior in $X$, then the family $\\{(Y,A):A\subseteq
Y\subsetneq 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 $\Pi^{0}_{1}$ 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 $\Pi^{0}_{1}$ 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:

  1. 1.

$(X,A)$ has strong computable type,

  2. 2.

There exists a $\Sigma_{2}^{0}$ invariant
$\bigcup_{n\in\mathbb{N}}\mathcal{P}_{n}$, where the sets $\mathcal{P}_{n}$
are uniformly $\Pi^{0}_{1}$ in $\tau_{up\mathcal{V}}^{2}$, such that every
copy of $(X,A)$ in $Q$ is $\mathcal{P}_{n}$-minimal for some $n$.

Note that the invariant is more than a $\Sigma^{0}_{2}$ 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 $\Pi^{0}_{1}$ properties from Theorem
4.7 works for “many” copies of $(X,A)$, in the sense of Baire category. We
then transform this $\Pi^{0}_{1}$ property into a $\Sigma^{0}_{2}$ invariant.
This transformation is an instance of Vaught’s transform [Vau74]. Let us
briefly explain this transform. There are several ways of defining an
invariant out of a property $\mathcal{P}$. For instance, the set of pairs
having at least one copy in $\mathcal{P}$ is an invariant; the set of pairs
whose copies are all in $\mathcal{P}$ is another invariant. However, these two
invariants can have very high descriptive complexities (typically
$\Sigma^{1}_{1}$ and $\Pi^{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 $\mathcal{P}$, where “many” is expressed using Baire
category. We now give the details.

We endow the space $\mathcal{C}(Q)$ of continuous functions from $Q$ to itself
with the complete separable metric

$\rho(f,g)=\max_{x\in Q}d_{Q}(f(x),g(x)).$

If functions $f,g$ are defined on $X\subseteq Q$ only, then we also define
$\rho_{X}(f,g)=\max_{x\in X}d_{Q}(f(x),g(x))$.

######  Remark 4.12.

We will often use the following inequalities:

$\displaystyle\rho(f\circ h,g\circ h)$ $\displaystyle\leq\rho(f,g),$ (3)
$\displaystyle\rho(f\circ g,\mathrm{id}_{Q})$
$\displaystyle\leq\rho(f,\mathrm{id}_{Q})+\rho(g,\mathrm{id}_{Q}).$ (4)

The second inequality holds because $\rho(f\circ
g,\mathrm{id}_{Q})\leq\rho(f\circ
g,g)+\rho(g,\mathrm{id}_{Q})\leq\rho(f,\mathrm{id}_{Q})+\rho(g,\mathrm{id}_{Q})$.

We can make $(\mathcal{C}(Q),\rho)$ a computable metric space.

######  Lemma 4.13.

There exists a computable sequence of injective continuous functions
$\phi_{i}:Q\to Q$ that is dense in the metric $\rho$.

###### 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},\ldots,x_{n-1},0,0,0,\ldots)$ where
each $x_{i}$ is a multiple of $2^{-n}$. For each $n\in\mathbb{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 $\epsilon>0$. An $\epsilon$-function is a continuous function $f:Q\to Q$
such that $\rho(f,\mathrm{id}_{Q})<\epsilon$. An $\epsilon$-deformation of a
pair $(X,A)\subseteq Q$ is the image $f(X,A):=(f(X),f(A))$ of $(X,A)$ under an
$\epsilon$-function $f$.

Note that if $f$ is an $\epsilon$-function and $g$ is a $\delta$-function,
then $f\circ g$ is an $(\epsilon+\delta)$-function. Therefore, an
$\epsilon$-deformation of a $\delta$-deformation of $(X,A)$ is a
$(\epsilon+\delta)$-deformation of $(X,A)$.

######  Remark 4.15.

The notion of $\epsilon$-function can be defined for partial functions $f:X\to
Q$, where $X\subseteq Q$, by requiring $\rho_{X}(f,\mathrm{id}_{X})<\epsilon$.
The notion of $\epsilon$-deformation of $(X,A)$ does not change if we consider
$\epsilon$-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 $\epsilon$-function, then $f$ has a continuous
extension $\tilde{f}:Q\to Q$ which is an $\epsilon$-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 $\delta>0$ and
$\tilde{f}(x)=(1-\lambda_{x})f_{0}(x)+\lambda_{x}x$, where
$\lambda_{x}=\min(1,d_{Q}(x,X)/\delta)$ (note that $Q$ indeed allows convex
combinations). $\tilde{f}$ is a continuous extension of $f$ and if $\delta$ is
sufficiently small, then $\rho(\tilde{f},\mathrm{id}_{Q})<\epsilon$.

If a homeomorphism $f:X\to Y$ is an $\epsilon$-function, then its inverse
$f^{-1}:Y\to X$ is an $\epsilon$-function as well.

######  Definition 4.16.

Let $\mathcal{P}$ be a property of pairs. We define an invariant
$\mathcal{P}^{*}$ as follows: $(X,A)\in\mathcal{P}^{*}$ iff there exists a
copy $(X^{\prime},A^{\prime})$ of $(X,A)$ and an $\epsilon>0$ such that every
$\epsilon$-deformation of $(X^{\prime},A^{\prime})$ is in $\mathcal{P}$.

The key observation about $\mathcal{P}^{*}$ is that its descriptive complexity
is not too high, compared to the descriptive complexity of $\mathcal{P}$: if
$\mathcal{P}$ is $\Pi^{0}_{1}$, then $\mathcal{P}^{*}$ is $\Sigma^{0}_{2}$.

######  Remark 4.17.

When $\mathcal{P}$ is $\Pi^{0}_{1}$ (more generally closed) in
$\tau_{\mathcal{V}}^{2}$, $\mathcal{P}^{*}$ could be equivalently defined by
considering _injective_ $\epsilon$-functions only, in which case
$\epsilon$-deformations of $(X^{\prime},A^{\prime})$ would all be copies of
$(X^{\prime},A^{\prime})$. Indeed, the injective continuous functions are
dense in $\mathcal{C}(Q)$, so every $\epsilon$-deformation of
$(X^{\prime},A^{\prime})$ is a limit, in the Vietoris topology, of
$\epsilon$-deformations by injective $\epsilon$-functions; if the latter are
all in $\mathcal{P}$, then every $\epsilon$-deformation is also in
$\mathcal{P}$ as $\mathcal{P}$ is closed in $\tau_{\mathcal{V}}^{2}$.

###### Proof of Theorem 4.11.

For a rational $\epsilon>0$, we define

$\mathcal{P}_{\epsilon}=\\{(X,A)\subseteq
Q:\text{every~{}$\epsilon$-deformation of~{}$(X,A)$ is
in~{}$\mathcal{P}$}\\}.$

One has $\mathcal{P}^{*}=\\{(X,A)\subseteq Q:\exists\epsilon>0,(X,A)\text{ has
a copy in }\mathcal{P}_{\epsilon}\\}$.

######  Claim 4.18.

Let $\tau$ be either $\tau_{\mathcal{V}}^{2}$ or $\tau_{up\mathcal{V}}^{2}$.
If $\mathcal{P}$ is $\Pi^{0}_{1}$ in $\tau$ then $\mathcal{P}_{\epsilon}$ is
$\Pi^{0}_{1}$ in $\tau$.

###### Proof.

The function $f\in\mathcal{C}(Q)\mapsto f(X,A)\in(\mathcal{K}^{2}(Q),\tau)$ is
continuous, $\mathcal{P}$ is closed in $\tau$ and the functions $\phi_{k}$ are
dense in $\mathcal{C}(Q)$. Therefore, the quantification over the
$\epsilon$-functions can be replaced by a quantification over the $k$’s such
that $\phi_{k}$ is an $\epsilon$-function: $(X,A)\in\mathcal{P}_{\epsilon}$
iff $\forall k\in\mathbb{N}$, $\rho(\phi_{k},\mathrm{id}_{Q})<\epsilon$
implies $\phi_{k}(X,A)\in\mathcal{P}$. It is a $\Pi^{0}_{1}$ predicate. ∎

Say that two pairs $(X,A)$ and $(Y,B)$ in $Q$ are $\epsilon$-homeomorphic if
there exists a homeomorphism $f:(X,A)\to(Y,B)$ which is an $\epsilon$-function
(note that this relation is symmetric, because in this case $f^{-1}$ is an
$\epsilon$-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 $\epsilon>0$ there exists $i$ such that $\phi_{i}(X_{0},A_{0})$
and $(X_{1},A_{1})$ are $\epsilon$-homeomorphic.

###### Proof.

Let $f:(X_{0},A_{0})\to(X_{1},A_{1})$ be a homeomorphism and let $i$ be such
that $\rho_{X_{0}}(\phi_{i},f)<\epsilon$. Let $\psi=\phi_{i}\circ f^{-1}$. One
has $\phi_{i}(X_{0},A_{0})=\psi(X_{1},A_{1})$ and
$\rho_{X_{1}}(\psi,\mathrm{id}_{Q})=\rho_{X_{0}}(\phi_{i},f)<\epsilon$. ∎

######  Claim 4.20.

Let $\tau$ be either $\tau_{\mathcal{V}}^{2}$ or $\tau_{up\mathcal{V}}^{2}$.
If $\mathcal{P}$ is $\Pi^{0}_{1}$ in $\tau$ then $\mathcal{P}^{*}$ is
$\Sigma^{0}_{2}$ in $\tau$.

###### 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
$\phi_{i}$’s. Precisely, let

$\mathcal{P}_{i,\epsilon}=\\{(X,A)\subseteq
Q:\phi_{i}(X,A)\in\mathcal{P}_{\epsilon}\\}.$

We show that $\mathcal{P}^{*}=\bigcup_{i,\epsilon}\mathcal{P}_{i,\epsilon}$,
which is $\Sigma^{0}_{2}$.

If $(X,A)$ has a copy $(X^{\prime},A^{\prime})$ in $\mathcal{P}_{\epsilon}$,
then there exists $i$ such that $\phi_{i}(X,A)\in\mathcal{P}_{\epsilon/2}$.
Indeed, let $i$ be such that $\phi_{i}(X,A)$ is $\epsilon/2$-homeomorphic to
$(X^{\prime},A^{\prime})$ by the previous claim. Every
$\epsilon/2$-deformation of $\phi_{i}(X,A)$ is an $\epsilon$-deformation of
$(X^{\prime},A^{\prime})$, so it belongs to $\mathcal{P}$. Therefore
$\phi_{i}(X,A)\in\mathcal{P}_{\epsilon/2}$, hence
$(X,A)\in\mathcal{P}_{i,\epsilon/2}$. ∎

######  Claim 4.21.

Assume that $(X,A)$ is $\mathcal{P}$-minimal and that
$(X,A)\in\mathcal{P}_{\epsilon}$. For every copy $(X^{\prime},A^{\prime})$ of
$(X,A)$, there exists $i$ such that $(X^{\prime},A^{\prime})$ is
$\mathcal{P}_{i,\epsilon/2}$-minimal.

###### Proof.

Let $(X^{\prime},A^{\prime})$ be a copy of $(X,A)$. Let $i$ be such that
$\phi_{i}(X^{\prime},A^{\prime})$ is $\epsilon/2$-homeomorphic to $(X,A)$. As
in the previous claim, $(X^{\prime},A^{\prime})\in\mathcal{P}_{i,\epsilon/2}$,
and we show that $(X^{\prime},A^{\prime})$ is
$\mathcal{P}_{i,\epsilon/2}$-minimal.

If $(X^{\prime\prime},A^{\prime\prime})$ is a proper subpair of
$(X^{\prime},A^{\prime})$, then $\phi_{i}(X^{\prime\prime},A^{\prime\prime})$
is $\epsilon/2$-homeomorphic to a proper subpair of $(X,A)$. The latter is not
in $\mathcal{P}$ as $(X,A)$ was $\mathcal{P}$-minimal, and is an
$\epsilon/2$-deformation of $\phi_{i}(X^{\prime\prime},A^{\prime\prime})$, so
$\phi_{i}(X^{\prime\prime},A^{\prime\prime})\notin\mathcal{P}_{\epsilon/2}$.
In other words.
$(X^{\prime\prime},A^{\prime\prime})\notin\mathcal{P}_{i,\epsilon/2}$. As a
result, $(X^{\prime},A^{\prime})$ is $\mathcal{P}_{i,\epsilon/2}$-minimal. ∎

######  Claim 4.22.

If $(X,A)$ has strong computable type, then there exists a $\Pi^{0}_{1}$
property $\mathcal{P}$, a copy $(X_{0},A_{0})\subseteq Q$ and an $\epsilon>0$
such that $(X_{0},A_{0})$ is $\mathcal{P}$-minimal and
$(X_{0},A_{0})\in\mathcal{P}_{\epsilon}$.

###### Proof.

Assume that $(X,A)\subseteq Q$ has strong computable type. Let
$\mathcal{I}(Q)\subseteq\mathcal{C}(Q)$ be the subspace of _injective_
continuous functions $f:Q\to Q$. It is a $G_{\delta}$-set:
$\mathcal{I}(Q)=\bigcap_{n\in\mathbb{N}}\mathcal{I}_{n}(Q)$ where

$\mathcal{I}_{n}(Q)=\\{f\in\mathcal{C}(Q):\forall x,y\in Q,d(x,y)\geq
2^{-n}\implies f(x)\neq f(y)\\}$

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 [vM01] for a more detailed proof). Being a $G_{\delta}$-subset
of the Polish space $\mathcal{C}(Q)$, the space $\mathcal{I}(Q)$ is therefore
Polish (Theorem 3.11 in [Kec95]).

Theorem 4.7 implies that for each $f\in\mathcal{I}(Q)$ there exists a
$\Pi^{0}_{1}$ property $\mathcal{P}$ (in $\tau_{up\mathcal{V}}^{2}$) such that
$f(X,A)$ is $\mathcal{P}$-minimal. There are countably many $\Pi^{0}_{1}$
properties, so by Baire category on $\mathcal{I}(Q)$ there exists a
$\Pi^{0}_{1}$-property $\mathcal{P}$, an $f_{0}\in\mathcal{I}(Q)$ and an
$\epsilon>0$ such that for “almost every” $f\in B(f_{0},\epsilon)$, $f(X,A)$
is $\mathcal{P}$-minimal. By “almost every”, we mean for a dense set of
functions $f\in B(f_{0},\epsilon)$. It actually implies that for _every_
continuous $f\in B(f_{0},\epsilon)$ the pair $f(X,A)$ is in $\mathcal{P}$
because $\mathcal{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 $\mathcal{P}_{\epsilon}$ but may not be
$\mathcal{P}$-minimal. However, we can replace $f_{0}$ by any $f_{1}\in
B(f_{0},\epsilon/2)$ such that $f_{1}(X,A)$ is $\mathcal{P}$-minimal, and
$\epsilon$ by $\epsilon/2$. We then let $(X_{0},A_{0})=f_{1}(X,A)$. ∎

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

##  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
$\epsilon>0$ such that no sequence of $\epsilon$-deformations of $(X,A)$
converges to a proper subpair of $(X,A)$ in the topology
$\tau_{up\mathcal{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 $\mathcal{P}$ which is $\Pi^{0}_{1}$
in $\tau_{up\mathcal{V}}^{2}$, a copy $(Y,B)$ of $(X,A)$ in $Q$ which is
$\mathcal{P}$-minimal, and an $\epsilon>0$ such that every
$\epsilon$-deformation of $(Y,B)$ is in $\mathcal{P}$.

As $\mathcal{P}$ is closed in $\tau_{up\mathcal{V}}^{2}$, every limit of
$\epsilon$-deformations of $(Y,B)$ in that topology also belongs to
$\mathcal{P}$. As $(Y,B)$ is $\mathcal{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 $\phi:(X,A)\to(Y,B)$. Indeed, $\phi$ sends proper subpairs of
$(X,A)$ to proper subpairs of $(Y,B)$ and if $\delta>0$ is sufficiently small,
then $\phi$ sends $\delta$-deformations of $(X,A)$ to $\epsilon$-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 $\tau_{\mathcal{V}}$ from $(Y,B)$ as an element of
$(\mathcal{K}^{2}(Q),\tau_{up\mathcal{V}}^{2})$.

######  Corollary 5.3.

For a pair $(X,A)$, the following statements are equivalent:

  1. 1.

$(X,A)$ has strong computable type relative to some oracle,

  2. 2.

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

###### Proof.

The proof of Corollary 5.1 holds relative to any oracle, which shows (1)
$\Rightarrow$ (2). Now assume condition (2). Let $\mathcal{P}$ be the closure,
in $\tau_{up\mathcal{V}}^{2}$, of the set of $\epsilon$-deformations of
$(X,A)$. Let $O$ be an oracle relative to which $\mathcal{P}$ is $\Pi^{0}_{1}$
in $\tau_{up\mathcal{V}}^{2}$. By definition, $\mathcal{P}$ contains all the
$\epsilon$-deformations of $(X,A)$ and $(X,A)$ is $\mathcal{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 [AH23], 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 $\epsilon>0$
one can compute $\delta>0$ such that $\epsilon$-deformations of $(X,A)$
converge to a proper subpair $(Y,B)\subsetneq(X,A)$ such that
$d_{H}(Y,X)>\delta$. Then $(X,A)$ does not have computable type.

Note that neither the $\epsilon$-deformations nor the limit $Y$ are required
to be computable. The computability assumption is only about the function
sending $\epsilon$ to $\delta$.

This result therefore identifies a general situation when computable type is
equivalent to strong computable type.

###  5.2 The $\epsilon$-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
$\epsilon>0$ such that every continuous function of pairs $f:(X,A)\to(X,A)$
satisfying $\rho_{X}(f,\mathrm{id}_{X})<\epsilon$ must be surjective.

###### Proof.

Take $\epsilon$ from Corollary 5.1. If $f:(X,A)\to(X,A)$ is an
$\epsilon$-function, then $f(X,A)$ is an $\epsilon$-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 [AH22]. A pair
$(X,A)\subseteq Q$ has the $\epsilon$-surjection property if every continuous
function $f:X\to X$ satisfying $\rho_{X}(f,\mathrm{id}_{X})<\epsilon$ and
$f|_{A}=\mathrm{id}_{A}$ is surjective. One of the main results from [AH22] 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 $\epsilon$-surjection property for some $\epsilon>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:

  1. 1.

$(X,A)$ has strong computable type,

  2. 2.

$(X,A)$ has computable type,

  3. 3.

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

  4. 4.

There exists $\epsilon>0$ such that every continuous function
$f:(X,A)\to(X,A)$ satisfying $\rho_{X}(f,\mathrm{id}_{X})<\epsilon$ and
$f|_{A}=\mathrm{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 [AH22] 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
$\epsilon$-surjection property does not imply computable type in general.
Consider the pair $(X,A)$ in $\mathbb{R}^{2}$ defined as follows:
$X=\bigcup_{i\in\mathbb{N}}X_{i}$ where $X_{0}=[0,1]\times\\{0\\}$ and for
$i\geq 1$, $X_{i}=\\{2^{-i}\\}\times[0,2^{-i}]$ and
$A=\\{(2^{-i},2^{-i}):i\geq 1\\}\cup\\{(0,0)\\}$ (see Figure 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}=\mathrm{id}_{A}$ must
be surjective, so $(X,A)$ has the $\epsilon$-surjection property for every
$\epsilon$. However it does not have computable type: if
$E\subseteq\mathbb{N}$ is a non-computable c.e. set, then the pair $(Y,B)$
defined by $Y=X_{0}\cup\bigcup_{i\notin E}X_{i}$ and
$B=\\{(2^{-i},2^{-i}):i\geq 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 $\epsilon>0$ there exists a connected component of $X$ of
diameter $<\epsilon$ 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 $\epsilon>0$ a non-
surjective continuous $\epsilon$-function, implying that $X$ does not have
strong computable type by Corollary 5.5.

Let $A\subseteq X$ be a connected component of diameter $<\epsilon$, 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_{\epsilon}$ of
diameter $<\epsilon$. The function $f:X\to X$ defined as the identity on
$X\setminus C_{\epsilon}$ and sending all $C_{\epsilon}$ to some point $x\in
C_{\epsilon}$ is a continuous $\epsilon$-function, which is not surjective
because $C_{\epsilon}$ is not a singleton.

If $X$ contains infinitely many isolated points then by compactness, they have
an accumulation point $x\in X$. Given $\epsilon>0$, let $f:X\to X$ send some
isolated point $y\in B(x,\epsilon)$ to $x$ and be the identity on
$X\setminus\\{y\\}$. $f$ is a non-surjective continuous $\epsilon$-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 [AH22] or the set shown in
Figure 2(a) 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.

######  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 $\mu:\mathbb{N}\to\mathbb{N}$ such
that if $d(x,x^{\prime})<2^{-\mu(n)}$ then $d(f(x),f(x^{\prime}))\leq 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 $\mu$ a closed
subset of the space $\mathcal{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 $\mu(n)=n+\lceil\log_{2}(L)\rceil$.

######  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
$\mu:\mathbb{N}\to\mathbb{N}$ be computable. The set

$\mathcal{K}_{\mu}:=\\{f\in\mathcal{C}(X,Q):\mu\text{ is a modulus of uniform
continuity of }f\\}$

is effectively compact.

###### Proof.

Let $(x_{i})_{i\in\mathbb{N}}$ be a dense computable sequence in $X$. If $\mu$
is a computable modulus of continuity of $f$, then an access to a name of
$f\in\mathcal{K}_{\mu}$ 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 $\mathcal{K}_{\mu}$ is computably homeomorphic to the set

$\mathcal{L}_{\mu}:=\\{(z_{i})_{i\in\mathbb{N}}\in Q^{\mathbb{N}}:\forall
i,j,n\in\mathbb{N},d(x_{i},x_{j})<2^{-n}\implies d(z_{i},z_{j})\leq 2^{-n}\\}$

via the map sending $f\in\mathcal{K}_{\mu}$ to the sequence
$(f(x_{i}))_{i\in\mathbb{N}}$. The space $Q^{\mathbb{N}}$ is effectively
compact and $\mathcal{L}_{\mu}$ is a $\Pi^{0}_{1}$-subset of $Q^{\mathbb{N}}$,
therefore $\mathcal{L}_{\mu}$ is effectively compact, and so is
$\mathcal{K}_{\mu}$. ∎

We now prove the result.

###### Proof of Theorem 5.11.

Let $\mu:\mathbb{N}\to\mathbb{N}$ be a computable function. The set
$\mathcal{J}_{\mu}$ of injective continuous functions $f:X\to Q$ such that
$\mu$ is a modulus of uniform continuity for both $f$ and $f^{-1}$ is an
effectively compact subset of $\mathcal{C}(X,Q)$. Indeed, $\mathcal{J}_{\mu}$
is the intersection of $\mathcal{K}_{\mu}$ from Lemma 5.12 with the set

$\\{f\in\mathcal{C}(X,Q):\forall x,x^{\prime}\in
X,d_{Q}(f(x),f(x^{\prime}))<2^{-\mu(n)}\implies d_{Q}(x,x^{\prime})\leq
2^{-n}\\}.$

As the latter set is $\Pi^{0}_{1}$, its intersection with $K_{\mu}$ is
effectively compact.

Let $\mathcal{P}_{\mu}=\\{f(X):f\in\mathcal{J}_{\mu}\\}$. As $X$ is
computable, the function
$\phi:\mathcal{C}(X,Q)\to(\mathcal{K}(Q),\tau_{\mathcal{V}})$ sending $f$ to
$f(X)$ is computable. As $\mathcal{J}_{\mu}$ is effectively compact, its image
$\mathcal{P}_{\mu}$ by $\phi$ is effectively compact as well, so
$\mathcal{P}_{\mu}$ is a $\Pi^{0}_{1}$-subset of $\mathcal{K}(Q)$ in the
topology $\tau_{\mathcal{V}}$. As $X$ does not properly contain a copy of
itself, any copy of $X$ in $\mathcal{P}_{\mu}$ is $\mathcal{P}_{\mu}$-minimal.
Therefore, any semicomputable copy of $X$ in $\mathcal{P}_{\mu}$ is
computable, by the same argument as in the proof of Theorem 4.7. ∎

######  Example 5.13.

The set $X$ shown in Figure 2(a), consisting of a disk attached to a pinched
torus, does not have computable type.

It can be proved using the results in [AH22, AH23]. 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
$\epsilon>0$, there is a sequence of $\epsilon$-deformations of $X$ converging
to a proper subset of $X$ (see Figure 2(b)). 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 [AH22,
AH23], that such sets do not have computable type is not straightforward.

(a) The set $X$

(b) $\epsilon$-deformations converging to a proper subset of $X$

Figure 2: The set from Example 5.13 and its $\epsilon$-deformations

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 $\tau_{up\mathcal{V}}^{2}$ and
computes $Y$ in the topology $\tau_{\mathcal{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
[Pau21] in the case of the circle embedded in $\mathbb{R}^{2}$. We give here
more results about this question.

######  Definition 5.14.

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

The first result holds for every pair (which may or may not have strong
computable type).

######  Definition 5.15.

Closed choice over $\mathbb{N}$ is the problem $\mathsf{C}_{\mathbb{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
$\leq_{sW}^{t}$ (where $t$ stands for _topological_).

######  Theorem 5.16.

Let $(X,A)$ be a pair such that $X$ is not a singleton. One has
$\mathsf{C}_{\mathbb{N}}\leq^{t}_{sW}\mathsf{SCT}_{(X,A)}$. If $(X,A)$ has a
semicomputable copy then
$\mathsf{C}_{\mathbb{N}}\leq_{sW}\mathsf{SCT}_{(X,A)}$.

###### Proof.

Instead of $\mathsf{C}_{\mathbb{N}}$, we use the strongly Weihrauch equivalent
problem $\mathsf{Max}$ which sends a non-empty finite subset of $\mathbb{N}$,
represented by its characteristic function, to its maximal element (Theorem
7.13 in [BGP21]). 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<\mathrm{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\mathbb{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}<\mathrm{diam}(X_{E})<2^{-m}$. Given an access to $X_{E}$ in the
topology $\tau_{\mathcal{V}}$, one can compute its diameter so one can compute
$m$, showing that $\mathsf{Max}$ is strongly Weihrauch reducible to
$\mathsf{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 $\tau_{up\mathcal{V}}^{2}$ neighborhood of the previous copy.
It is possible because we can assume that at stage $i$, the
$\tau_{up\mathcal{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
$\mathsf{SCT}_{(X,A)}\leq_{W}\mathsf{C}_{\mathbb{N}}$ holds when $(X,A)$ has
strong computable type in a particular way. A strong Weihrauch reduction is
impossible, because $\mathsf{C}_{\mathbb{N}}$ has countably many possible
outputs while $\mathsf{SCT}_{(X,A)}$ has uncountably many.

######  Theorem 5.17.

Let $\mathcal{P}$ be a $\Sigma_{2}^{0}$ invariant. If a pair $(X,A)$ is
$\mathcal{P}$-minimal then
$\mathsf{SCT}_{(X,A)}\leq_{W}\mathsf{C}_{\mathbb{N}}$.

###### Proof.

Let $\mathcal{P}=\bigcup_{n}\mathcal{P}_{n}$ where $\mathcal{P}_{n}$ are
uniformly $\Pi^{0}_{1}$-set in $\tau_{up\mathcal{V}}^{2}$. Given a copy
$(Y,B)$, let $E=\\{n:(Y,B)\in\mathcal{P}_{n}\\}$. From $(Y,B)$ in
$\tau_{up\mathcal{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
$\mathcal{P}_{n}$-minimal as in the proof of Theorem 4.7. ∎

We do not know whether $\mathsf{SCT}_{(X,A)}$ is always Weihrauch reducible to
$\mathsf{C}_{\mathbb{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 $\tau_{\mathcal{V}}^{2}$ and upper Vietoris topology
$\tau_{up\mathcal{V}}^{2}$. As $\tau_{up\mathcal{V}}^{2}$ is weaker than
$\tau_{\mathcal{V}}^{2}$, the descriptive complexity of a property in
$\tau_{up\mathcal{V}}^{2}$ is always an upper bound on its complexity in
$\tau_{\mathcal{V}}^{2}$. Although the properties of a given complexity level
are not the same in the topologies
$\tau_{\mathcal{V}}\times\tau_{up\mathcal{V}}$ and $\tau_{up\mathcal{V}}^{2}$,
we show that they actually induce the same class of minimal elements.

######  Notation 5.18.

For a property of pairs $\mathcal{P}$ let

$\text{$\uparrow$}\mathcal{P}=\\{(X,A):\exists(X^{\prime},A^{\prime})\subseteq(X,A),(X^{\prime},A^{\prime})\in\mathcal{P}\\}.$

######  Proposition 5.19.

Let $\mathcal{P}$ be a property of pairs. The set
$\text{$\uparrow$}\mathcal{P}$ has the same minimal elements as $\mathcal{P}$
and

  1. 1.

If $\mathcal{P}$ is $\Pi_{1}^{0}$ in $\tau_{\mathcal{V}}^{2}$, then
$\text{$\uparrow$}\mathcal{P}$ is $\Pi_{1}^{0}$ in $\tau_{up\mathcal{V}}^{2}$,

  2. 2.

If $\mathcal{P}$ is $\Sigma_{2}^{0}$ in $\tau_{\mathcal{V}}^{2}$, then
$\text{$\uparrow$}\mathcal{P}$ is $\Sigma_{2}^{0}$ in
$\tau_{up\mathcal{V}}^{2}$; moreover,
$\text{$\uparrow$}\mathcal{P}=\bigcup_{n}\mathcal{P}_{n}$ where
$\mathcal{P}_{n}$ are uniformly $\Pi^{0}_{1}$ in $\tau_{up\mathcal{V}}^{2}$.

Therefore, whether a pair $(X,A)$ is minimal for some $\Pi_{1}^{0}$ or
$\Sigma_{2}^{0}$ property does not depend on the topology (among
$\tau_{\mathcal{V}}^{2}$ and $\tau_{up\mathcal{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 $\subseteq$, which is the set
$\\{(X,X^{\prime})\in\mathcal{K}^{2}(Q):X\subseteq X^{\prime}\\}$, is
$\Pi^{0}_{1}$ in the topology
$\tau_{low\mathcal{V}}\times\tau_{up\mathcal{V}}$.

###### Proof.

One has $X\nsubseteq X^{\prime}$ iff there exists a rational ball $B$
intersecting $X$ and such that $X^{\prime}$ is contained in
$Q\setminus\overline{B}$. This condition on the pair $(X,X^{\prime})$ is an
effective open set in the topology
$\tau_{low\mathcal{V}}\times\tau_{up\mathcal{V}}$. In other words, inclusion
is $\Pi^{0}_{1}$ in that topology. ∎

###### Proof of Proposition 5.19.

It is easy to see that $\mathcal{P}$ and $\text{$\uparrow$}\mathcal{P}$ have
the same minimal elements. Now assume that $\mathcal{P}$ is $\Pi_{1}^{0}$ in
$\tau_{\mathcal{V}}^{2}$ and let us show that $\text{$\uparrow$}P$ is
$\Pi_{1}^{0}$ in $\tau_{up\mathcal{V}}^{2}$. One has

$(X,A)\in\text{$\uparrow$}\mathcal{P}\iff\exists(X^{\prime},A^{\prime})\in\mathcal{K}(Q)^{2},(X^{\prime},A^{\prime})\subseteq(X,A)\text{
and }(X^{\prime},A^{\prime})\in\mathcal{P}.$

Using Lemma 5.20 and the assumption that $\mathcal{P}$ is $\Pi^{0}_{1}$ in
$\tau_{\mathcal{V}}^{2}$, the relation
$R:=\\{(X,A,X^{\prime},A^{\prime}):(X^{\prime},A^{\prime})\subseteq(X,A)\text{
and }(X^{\prime},A^{\prime})\in\mathcal{P}\\}$ is $\Pi^{0}_{1}$ in the
topology $\tau_{up\mathcal{V}}^{2}\times\tau_{\mathcal{V}}^{2}$. The space
$(\mathcal{K}^{2}(Q),\tau_{\mathcal{V}}^{2})$ is effectively compact, so the
projection of $R$ on its first two components, which is
$\text{$\uparrow$}\mathcal{P}$, is $\Pi^{0}_{1}$ in the topology
$\tau_{up\mathcal{V}}^{2}$ by Proposition 2.5.

The second item is now easy to prove. If $\mathcal{P}$ is $\Sigma_{2}^{0}$ in
$\tau_{\mathcal{V}}^{2}$, then $\mathcal{P}=\bigcup_{n}\mathcal{P}_{n}$ where
$\mathcal{P}_{n}$ are uniformly $\Pi_{1}^{0}$ in $\tau_{\mathcal{V}}^{2}$.
Therefore,
$\text{$\uparrow$}\mathcal{P}=\bigcup_{n}\text{$\uparrow$}\mathcal{P}_{n}$ and
$\text{$\uparrow$}\mathcal{P}_{n}$ are uniformly $\Pi_{1}^{0}$ in
$\tau_{up\mathcal{V}}^{2}$ by the first statement, so
$\text{$\uparrow$}\mathcal{P}$ is $\Sigma_{2}^{0}$ in
$\tau_{up\mathcal{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

$(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})).$

######  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
$\mathrm{Cone}(X)=\left(X\times[0,1]\right)/\left(X\times\\{0\\}\right)$.

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

If $X$ is embedded in $Q$, then a realization of $\mathrm{Cone}(X)$ in
$Q\cong[0,1]\times Q$ is given by

$\mathrm{Cone}(X)\cong\\{(\lambda,\lambda x):\lambda\in[0,1],x\in X\\}.$

######  Proposition 5.24.

Let $(X,A)$ be a pair. If $\mathrm{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)=\mathrm{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 $\mathrm{Cone}(X_{0},A_{0})$ in
$Q$ is semicomputable:

$\displaystyle Y_{0}$ $\displaystyle=\\{(\lambda,\lambda
x):\lambda\in[0,1],x\in X_{0}\\},$ $\displaystyle B_{0}$
$\displaystyle=\\{(\lambda,\lambda x):\lambda\in[0,1],x\in
A_{0}\\}\cup(\\{1\\}\times X_{0}).$

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 $(\lambda,y)\mapsto y/\lambda$
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 $\mathrm{Cone}(L,N)$ does not, as
shown in [AH22], 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
[AH22] that it has (strong) computable type. However, the results of [AH22]
imply that as $L$ is contractible, the pair $(\mathrm{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 $\Sigma^{0}_{2}$ topological invariant for
which $(X,A)$ is minimal. In order to apply this result, we need to find
suitable $\Sigma^{0}_{2}$ invariants. In this section, we develop results of
independent interest that will be applied to define $\Sigma^{0}_{2}$
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 $\Sigma^{0}_{2}$
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 [Bor32] 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 [Col09], although we do not use these results.

######  Definition 6.1.

Let $(X,A)$ be a pair. A retraction $r:X\rightarrow A$ is a continuous
function such that $r|_{A}=\mathrm{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.

  1. 1.

$X$ is an absolute retract (AR) if every copy of $X$ in $Q$ is a retract of
$Q$,

  2. 2.

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

######  Fact 6.3.

We recall some classical facts (see [Han51] and [vM01]).

  1. 1.

The $n$-dimensional ball is an AR,

  2. 2.

The $n$-dimensional sphere is an ANR,

  3. 3.

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$,

  4. 4.

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\mathbb{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 [vM01]).

Let $Y\subseteq Q$ be a compact ANR. There exists $\alpha>0$ such that for
every space $X$, if $f,g:X\to Y$ are continuous and $\rho_{X}(f,g)<\alpha$,
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 [vM01]).

######  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 [vKM+14],
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 [Col09], 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
$\nu_{S}:\subseteq\mathbb{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 $\nu_{[X;Y]}$ of $[X;Y]$ such that:

  1. 1.

$\mathrm{dom}(\nu_{[X;Y]})$ is c.e. relative to $X$,

  2. 2.

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

  3. 3.

For any pair $(X,A)$, the extension relation

$\\{(i,j)\in\mathrm{dom}(\nu_{[X;Y]})\times\mathrm{dom}(\nu_{[A;Y]}):\nu_{[X;Y]}(i)\text{
extends }\nu_{[A;Y]}(j)\\}$

is c.e. relative to $X$ and $A$,

  4. 4.

For any pair $(X,A)$, the extensibility predicate

$\\{i\in\mathrm{dom}(\nu_{[A;Y]}):\nu_{[A;Y]}(i)\text{ has a continuous
extension to }X\\}$

is c.e. relative to $X$ and $A$,

where $X$ and $A$ are given as elements of
$(\mathcal{K}(Q),\tau_{up\mathcal{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 $\mu,\alpha>0$ such
that:

  1. (i)

Functions to $Y$ that are $\alpha$-close are homotopic,

  2. (ii)

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

  3. (iii)

For $x,y\in U$, $d(x,y)<\mu$ implies $d(r(x),r(y))<\alpha$.

###### Proof.

The number $\alpha$ 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 $\mu>0$ satisfying (iii) for $x,y\in\overline{V}$. As
$r|_{Y}=\mathrm{id}_{Y}$ and $Y$ is compact, if $x$ is sufficiently close to
$Y$, $d(r(x),x)<\mu$. 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\mathbb{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,\alpha,\mu$
be provided by Lemma 6.8. For $X\subseteq Q$, we define a numbering
$\nu_{[X;Y]}$ of $[X;Y]$ and prove (1), (4), (2) and (3) in this order. Its
domain is

$\mathrm{dom}(\nu_{[X;Y]})=\\{i\in\mathbb{N}:f_{i}(X)\subseteq U\\},$

which is clearly c.e. relative to $X$, showing (1). For
$i\in\mathrm{dom}(\nu_{[X;Y]})$, we then define $\nu_{[X;Y]}(i)$ as the
equivalence class of $r\circ f_{i}|_{X}:X\to Y$.

We first show that $\nu_{[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\mathrm{dom}(\nu_{[X;Y]})$) and $r\circ f_{i}|_{X}$ is
$\alpha$-close to $f$. Therefore, $r\circ f_{i}|_{X}$ is homotopic to $f$ and
$\nu_{[X;Y]}(i)=[f]$.

Let now $(X,A)$ be a pair in $Q$ and let $\nu_{[X;Y]}$ and $\nu_{[A;Y]}$ be
the corresponding numberings. We show condition (4).

######  Claim 6.9.

The set

$\\{i\in\mathrm{dom}(\nu_{[X;Y]}):\nu_{[A;Y]}(i)\text{ has a continuous
extension to }X\\}$

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\mathrm{dom}(\nu_{[X;Y]})$ such that
$\rho_{A}(f_{j},f_{i})<\mu$. It will imply the result as this condition is
c.e. relative to $X$ and $A$.

If there exists such a $j$, then $\rho_{A}(r\circ f_{j},r\circ f_{i})<\alpha$
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 $\rho_{A}(f,f_{i})=\rho_{A}(r\circ f_{i},f_{i})<\mu$ by Lemma 6.8 (ii) so
if $f_{j}$ is sufficiently close to $f$ on $X$, then $f_{j}(X)\subseteq U$ and
$\rho_{A}(f_{j},f_{i})<\mu$. ∎

We now show (2), i.e. that equality is c.e. Let
$\mathrm{Cyl}(X)=X\times[0,1]\subseteq Q$ be the cylinder of $X$ and
$\partial\mathrm{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\mathrm{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
$\varphi:\mathrm{dom}(\nu_{[X;Y]})^{2}\to\mathrm{dom}(\nu_{[\partial\mathrm{Cyl}(X);Y]})$
such that if $i,j$ are indices of the homotopy classes of $f$ and $g$
respectively, then $\varphi(i,j)$ is an index of the homotopy class of $h$.
Note that $f,g$ are homotopic iff $h$ has a continuous extension to
$\mathrm{Cyl}(X)$. Therefore, for $i,j\in\mathrm{dom}(\nu_{[X;Y]})$, one has
$\nu_{[X;Y]}(i)=\nu_{[X;Y]}(j)$ iff
$\nu_{[\partial\mathrm{Cyl}(X);Y]}(\varphi(i,j))$ has an extension to
$\mathrm{Cyl}(X)$, which is c.e. relative to $X$ by Claim 6.9 applied to the
pair $(\mathrm{Cyl}(X),\partial\mathrm{Cyl}(X))$.

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

###  6.3 Families of $\Sigma^{0}_{2}$ invariants

The previous results enable us to define families of $\Sigma^{0}_{2}$
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 $\mathsf{E}(Y)$.
Ultimately, we will focus on $Y=\SS_{n}$, the $n$-dimensional sphere.

######  Definition 6.10 (The invariant $\mathsf{E}(Y)$).

Let $Y$ be a topological space. A pair $(X,A)$ belongs to $\mathsf{E}(Y)$ if
there exists a continuous function $f:A\rightarrow Y$ that cannot be extended
to a continuous function $g:X\rightarrow 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
$\mathsf{E}(Y)$ is $\underaccent{\wtilde}{{\boldsymbol{\Sigma}}}^{1}_{2}$.
However when $Y$ is a compact ANR, we show that the complexity drops down to
$\Sigma^{0}_{2}$, 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 $\mathsf{E}(Y)$ is a $\Sigma_{2}^{0}$ invariant
in $\tau_{up\mathcal{V}}^{2}$.

###### Proof.

It is a simple application of Theorem 6.7. Indeed,

$\displaystyle(X,A)\in\mathsf{E}(Y)$ $\displaystyle\iff\exists f:A\to Y\text{
having no extension to }X,$ $\displaystyle\iff\exists
i\in\mathrm{dom}(\nu_{[A;Y]}),\forall
j\in\mathrm{dom}(\nu_{[X;Y]}),\nu_{[X;Y]}(j)\text{ does not extend
}\nu_{[A;Y]}(i)$

which is a $\Sigma^{0}_{2}$ condition. ∎

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

####  6.3.2 Null-homotopy of functions

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

######  Definition 6.12 (The invariant $\mathsf{H}(Y)$).

Let $Y$ be a topological space. A space $X$ belongs to $\mathsf{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 $\mathsf{H}(Y)$ is a $\Sigma^{0}_{2}$ invariant
in $\tau_{up\mathcal{V}}^{2}$.

###### Proof.

One has $X\in\mathsf{H}(Y)$ iff $[X;Y]$ is non-trivial iff $\exists
i,j\in\mathrm{dom}(\nu_{[X;Y]}),\nu_{[X;Y]}(i)\neq\nu_{[X;Y]}(j)$, which is a
$\Sigma^{0}_{2}$ 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\mathrm{dom}(\nu_{[X;Y]})$ for any $X$), so that $[X;Y]$ is non-
trivial iff $\exists
i\in\mathrm{dom}(\nu_{[X;Y]}),\nu_{[X;Y]}(i)\neq\nu_{[X;Y]}(i_{0})$. ∎

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

The invariant $\mathsf{H}(Y)$ only applies to single sets. We will define a
version for pairs, with $Y=\SS_{n}$.

##  7 Detailed study of some $\Sigma^{0}_{2}$ invariants

Theorem 4.8 provides a template to prove that a pair has strong computable
type, by identifying a $\Sigma^{0}_{2}$ invariant for which the pair is
minimal. One of our goals is to revisit previous results by finding
corresponding $\Sigma^{0}_{2}$ 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 $\Sigma^{0}_{2}$ 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 $\mathsf{E}(Y)$

We study the invariant $\mathsf{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\mathsf{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 $\mathsf{E}(Y)$.

######  Proposition 7.1.

Let $\phi:(X^{\prime},A^{\prime})\to(X,A)$ such that
$\phi|_{A^{\prime}}:A^{\prime}\to A$ is a homeomorphism. If
$(X^{\prime},A^{\prime})\in\mathsf{E}(Y)$ then $(X,A)\in\mathsf{E}(Y)$.

###### Proof.

We assume that $(X,A)\notin\mathsf{E}(Y)$ and show that
$(X^{\prime},A^{\prime})\notin\mathsf{E}(Y)$. Let $f:A^{\prime}\to Y$. The
function $g=f\circ(\phi|_{A^{\prime}})^{-1}:A\to Y$ has a continuous extension
$G:X\to Y$. The continuous function $F=G\circ\phi:X^{\prime}\to Y$ then
extends $f$. Indeed,
$F|_{A^{\prime}}=G\circ\phi|_{A^{\prime}}=g\circ\phi|_{A^{\prime}}=f\circ(\phi|_{A^{\prime}})^{-1}\circ\phi|_{A^{\prime}}=f$.
∎

##### Converging sequences

Now we give results showing how $\mathsf{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 $\mathsf{E}(Y)$ does not imply that $(X,A)$ is (resp. is not) in
$\mathsf{E}(Y)$. In other words, $\mathsf{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 $\mathsf{E}(Y)$ by
approximating it with pairs that are not in $\mathsf{E}(Y)$ in some way. It is
taken from the definition of pseudo-cubes in [HIP20].

######  Proposition 7.2.

Let $(X,A)$ be a pair and $(X_{i},A_{i})_{i\in\mathbb{N}}$ be a sequence of
pairs contained in $X$ such that

  1. 1.

For every $i$, $X_{i}\setminus A_{i}$ is open in $X$ and is contained in
$(X\setminus A)$,

  2. 2.

For every $\epsilon>0$, there exists $i$ such that $X\setminus(X_{i}\setminus
A_{i})\subseteq\mathcal{N}_{\epsilon}(A)$.

If $(X_{i},A_{i})\notin E(Y)$ for all $i$, then $(X,A)\notin\mathsf{E}(Y)$.

###### Proof.

We assume that $(X_{i},A_{i})\notin\mathsf{E}(Y)$ for all $i$ and show that
$(X,A)\notin\mathsf{E}(Y)$.

Let $f:A\rightarrow Y$ be continuous. $Y$ is an ANR, so there exists some
continuous extension $\tilde{f}$ of $f$ to $\mathcal{N}_{\epsilon}(A)$, for
some $\epsilon>0$ by Fact 6.3 (4). Let $i$ be such that
$X\setminus(X_{i}\setminus A_{i})\subseteq\mathcal{N}_{\epsilon}(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\setminus(X_{i}\setminus A_{i})$. Note that
$X_{i}$ and $X\setminus(X_{i}\setminus 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\mathsf{E}(Y)$. ∎

The second result can be used to prove that a pair is in $\mathsf{E}(Y)$ by
approximating it with pairs that are in $\mathsf{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 $\epsilon>0$ such that their restrictions
$\tilde{f}|_{\mathcal{N}_{\epsilon}(X)}$ and $g|_{\mathcal{N}_{\epsilon}(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 $\mathcal{N}_{\epsilon}(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\mathbb{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\mathbb{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\mathbb{N}$, then $f$ has no continuous extension to $X$.

###  7.2 The invariant $\mathsf{E}_{n}$

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

######  Definition 7.7 (The invariant $\mathsf{E}_{n}$).

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

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

The simplest example of a pair which is $\mathsf{E}_{n}$-minimal is given by
the $n+1$-ball and its bounding $n$-sphere. We first explain why is it in
$\mathsf{E}_{n}$. More generally, whether a pair $(\mathbb{B}_{m+1},\SS_{m})$
satisfies $\mathsf{E}_{n}$ depends on the $m$th homotopy group of the
$n$-sphere.

######  Proposition 7.8.

The pair $(\mathbb{B}_{m+1},\SS_{m})$ is in $\mathsf{E}_{n}$ if and only if
the homotopy group $\pi_{m}(\SS_{n})$ is non-trivial.

In particular, $(\mathbb{B}_{n+1},\SS_{n})$ is in $\mathsf{E}_{n}$ and
$(\mathbb{B}_{m+1},\SS_{m})$ is not in $\mathsf{E}_{n}$ for $m<n$.

###### Proof.

As $\mathbb{B}_{m+1}$ is the cone of $\SS_{m}$, a continuous extension of
$f:\SS_{m}\to\SS_{n}$ to $\mathbb{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 $\SS_{n}$ extends continuously to
$X$.

######  Theorem 7.9 (Theorem 3.6.3 in [vM01]).

Let $n\in\mathbb{N}$. If $(X,A)$ is a pair with $\dim(X\setminus A)\leq n$,
then $(X,A)\notin\mathsf{E}_{n}$.

In particular, if $\dim(X)\leq n$ then $(X,A)\notin\mathsf{E}_{n}$.

In some cases, if a pair is not in $\mathsf{E}_{n}$ then no subpair is in
$\mathsf{E}_{n}$.

######  Lemma 7.10.

Let $(X,A)$ be a pair with $\dim(A)\leq n$. If $(X,A)\notin\mathsf{E}_{n}$,
then for every $(Y,B)\subseteq(X,A)$ one has $(Y,B)\notin\mathsf{E}_{n}$.

###### Proof.

As $\dim(A)\leq n$, one has $(A,B)\notin\mathsf{E}_{n}$. Therefore,
$(X,A)\notin\mathsf{E}_{n}$ implies $(Y,B)\notin\mathsf{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 $\mathsf{E}_{n}$-minimality in certain
circumstances.

######  Corollary 7.11.

Let $(X,A)$ be a pair in $\mathsf{E}_{n}$, where $A$ has empty interior and
$\dim(A)\leq n$. If for every $A\subseteq Y\subsetneq X$ one has
$(Y,A)\notin\mathsf{E}_{n}$, then $(X,A)$ is $\mathsf{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\mathsf{E}_{n}$ by
assumption. Therefore, $(Y,B)\notin\mathsf{E}_{n}$ by Lemma 7.10. ∎

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

We now apply this technique.

######  Proposition 7.12.

For every $n\in\mathbb{N}$, the pair $(\mathbb{B}_{n+1},\SS_{n})$ is
$\mathsf{E}_{n}$-minimal.

###### Proof.

By Proposition 7.8, $(\mathbb{B}_{n+1},\SS_{n})$ is in $\mathsf{E}_{n}$. If
$\SS_{n}\subseteq Y\subsetneq\mathbb{B}_{n+1}$, then $Y$ retracts to $\SS_{n}$
so $(Y,\SS_{n})\notin\mathsf{E}_{n}$. Therefore by Corollary 7.11, no proper
subpair $(Y,B)$ of $(\mathbb{B}_{n+1},\SS_{n})$ is in $\mathsf{E}_{n}$. As a
result, $(\mathbb{B}_{n+1},\SS_{n})$ is $\mathsf{E}_{n}$-minimal. ∎

Therefore, our results give an alternative proof that the pair
$(\mathbb{B}_{n+1},\SS_{n})$ has (strong) computable type, which was shown by
Miller [Mil02]. We will give more examples of $\mathsf{E}_{n}$-minimal pairs
in the next sections.

###  7.3 The invariant $\mathsf{H}_{n}$

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

In the $n$-sphere $\SS_{n}$, let $p$ be an arbitrary point. We recall that two
continuous functions of pairs $f,g:(X,A)\to(\SS_{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\SS_{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(\SS_{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 $\mathsf{H}_{n}$).

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

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

Now that for single spaces, $\mathsf{H}_{n}$ is precisely
$\mathsf{H}(\SS_{n})$ from Definition 6.12.

We first prove that $\mathsf{H}_{n}$ is a $\Sigma^{0}_{2}$ invariant, by
reducing it to $\mathsf{E}_{n}$. We recall from Definition 5.23 that for a
space $Y$, $\mathrm{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}:\mathrm{Cone}(Y)\to Z$, where $Y$ is embedded in $\mathrm{Cone}(Y)$
as $Y\times\\{1\\}$. A similar equivalence holds for pairs, as follows.

######  Proposition 7.14.

For a pair $(X,A)$, one has

$(X,A)\in\mathsf{H}_{n}\iff\mathrm{Cone}(X,A)\in\mathsf{E}_{n}.$

Moreover, if $\mathrm{Cone}(X,A)$ is $\mathsf{E}_{n}$-minimal, then $(X,A)$ is
$\mathsf{H}_{n}$-minimal.

###### Proof.

Let $(C,D)=\mathrm{Cone}(X,A)=(\mathrm{Cone}(X),X\cup\mathrm{Cone}(A))$. A
function $f:(X,A)\to(\SS_{n},p)$ has a canonical extension $F:D\to\SS_{n}$
with constant value $p$ on $\mathrm{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\mathsf{H}_{n}$ and let $f:(X,A)\to(\SS_{n},p)$ be a
continuous function which is not null-homotopic relative to $A$. By the
previous observation, the function $F:D\to\SS_{n}$ has no continuous extension
to $C$, therefore $\mathrm{Cone}(X,A)\in\mathsf{E}_{n}$.

Conversely, assume that $\mathrm{Cone}(X,A)\in\mathsf{E}_{n}$ and let
$G:D\to\SS_{n}$ have no continuous extension to $C$. We cannot directly apply
the preliminary observation to $G$ because it is not necessarily constant on
$\mathrm{Cone}(A)$. However, $G$ is homotopic to a function $F:D\to\SS_{n}$
which is constant on $\mathrm{Cone}(A)$. Indeed, $\mathrm{Cone}(A)$ is
contractible so the restriction of $G$ to $\mathrm{Cone}(A)$ is null-
homotopic. As $\SS_{n}$ is an ANR, the homotopy on $\mathrm{Cone}(A)$ can be
extended to a homotopy between $G:D\to\SS_{n}$ and a function $F:D\to\SS_{n}$
which is constant on $\mathrm{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\SS_{n}$ of $F$ to $X$ is not
null-homotopic relative to $A$, therefore $(X,A)\in\mathsf{H}_{n}$.

Assume that $\mathrm{Cone}(X,A)$ is $\mathsf{E}_{n}$-minimal. If
$(X^{\prime},A^{\prime})$ is a proper subpair of $(X,A)$, then
$\mathrm{Cone}(X^{\prime},A^{\prime})$ is a proper subpair of
$\mathrm{Cone}(X,A)$ so it does not satisfy $\mathsf{E}_{n}$, therefore
$(X^{\prime},A^{\prime})\notin\mathsf{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 $\mathsf{H}_{n}$ from
results about $\mathsf{E}_{n}$. We start with the descriptive complexity of
$\mathsf{H}_{n}$. We already saw in Corollary 6.13 that the invariant
$\mathsf{H}(Y)$ of _single_ spaces is $\Sigma^{0}_{2}$ in
$\tau_{up\mathcal{V}}$ when $Y$ is a compact ANR, and a similar result holds
for the invariant $\mathsf{H}_{n}$ of _pairs_.

######  Corollary 7.15.

$\mathsf{H}_{n}$ is a $\Sigma^{0}_{2}$ invariant in
$\tau_{up\mathcal{V}}^{2}$.

###### Proof.

Given a pair $(X,A)\subseteq Q$, a copy $(C,D)$ of $\mathrm{Cone}(X,A)$ can be
defined as follows:

$\displaystyle C$ $\displaystyle=\\{(t,tx):t\in[0,1],x\in X\\},$
$\displaystyle D$ $\displaystyle=\\{(1,x):x\in
X\\}\cup\\{(t,tx):t\in[0,1],x\in A\\}.$

The map $\phi$ sending $(X,A)\in(\mathcal{K}^{2}(Q),\tau_{up\mathcal{V}}^{2})$
to $(C,D)\in(\mathcal{K}^{2}(Q),\tau_{up\mathcal{V}}^{2})$ is easily
computable, and $\mathsf{H}_{n}$ is the preimage of $\mathsf{E}_{n}$ by $\phi$
by Proposition 7.14. As $\mathsf{E}_{n}$ is $\Sigma^{0}_{2}$, so is
$\mathsf{H}_{n}$. ∎

####  7.3.1 Relationship with dimension

As $\mathsf{H}_{n}$ can be expressed using $\mathsf{E}_{n}$, the relations
between $\mathsf{E}_{n}$ and the dimension of the space can be similarly
formulated for $\mathsf{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)\leq n-1$. One has
$(X,A)\notin\mathsf{H}_{n}$.

###### Proof.

One has $\dim(\mathrm{Cone}(X))\leq n$ so
$\mathrm{Cone}(X,A)\notin\mathsf{E}_{n}$ by Theorem 7.9, therefore
$(X,A)\notin\mathsf{H}_{n}$. ∎

######  Lemma 7.17.

Let $(X,A)$ be a pair satisfying $\dim(X)\leq n$ and $\dim(A)\leq n-1$. If
$(X,A)\notin\mathsf{H}_{n}$, then for every pair $(Y,B)\subseteq(X,A)$ one has
$(Y,B)\notin\mathsf{H}_{n}$.

###### Proof.

Let $(C,D)=\mathrm{Cone}(X,A)$ and $(E,F)=\mathrm{Cone}(Y,B)\subseteq(C,D)$.
Reformulating $\mathsf{H}_{n}$ in terms of $\mathsf{E}_{n}$ thanks to
Proposition 7.14, we want to prove that $(C,D)\notin\mathsf{E}_{n}$ implies
$(E,F)\notin\mathsf{E}_{n}$.

It is implied by Lemma 7.10, which can be applied because
$D=X\cup\mathrm{Cone}(A)$ so $\dim(D)\leq 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)\leq n$ and
$\dim(A)\leq n-1$. One has

$(X,A)\text{ is }\mathsf{H}_{n}\text{-minimal}\iff\mathrm{Cone}(X,A)\text{ is
}\mathsf{E}_{n}\text{-minimal}.$

Before proving this result, we need to reformulate Borsuk’s homotopy extension
theorem (Theorem 6.6). The cylinder of a space $X$ is
$\mathrm{Cyl}(X)=X\times[0,1]$. A homotopy $H:X\times[0,1]\to Y$ is nothing
else than a function from $\mathrm{Cyl}(X)$ to $Y$, and a null-homotopy is a
function from $\mathrm{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\mathrm{Cyl}(A)\to Y$ has a continuous extension to $\mathrm{Cyl}(X)$.
Every continuous function $g:\mathrm{Cone}(A)\to Y$ has a continuous extension
to $\mathrm{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,
$\mathrm{Cone}(A)$ is the quotient of $X\cup\mathrm{Cyl}(A)$ by identifying
all the points of $X$. A function $g:\mathrm{Cone}(A)\to Y$ induces a function
$f:X\cup\mathrm{Cyl}(A)\to Y$ which is constant on $X$, by composing $g$ with
the quotient map. $f$ has a continuous extension $F:\mathrm{Cyl}(X)\to Y$,
which is constant on $X$, and therefore induces a continuous function
$G:\mathrm{Cone}(X)\to Y$ extending $g$. ∎

###### Proof of Proposition 7.18.

Assume that $(X,A)$ is $\mathsf{H}_{n}$-minimal. We need to show that no
proper subpair $(Y,B)$ of $\mathrm{Cone}(X,A)$ is in $\mathsf{E}_{n}$. Using
Corollary 7.11, it is sufficient to show the result when
$B=X\cup\mathrm{Cone}(A)$. Let then $Y$ be a proper subset of
$\mathrm{Cone}(X)$ containing $X\cup\mathrm{Cone}(A)$. There exists a non-
empty open set $U\subseteq X\setminus 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 $\mathrm{Cone}(X)$ in the obvious way). Let
$f:X\cup\mathrm{Cone}(A)\to\SS_{n}$. We show how to extend $f$ to
$\mathrm{Cone}(X)\setminus(J\times U)$, giving an extension of $f$ to $Y$ by
restriction. Figure 3 may help visualize the argument.

As $(X,A)$ is $\mathsf{H}_{n}$-minimal by assumption, $(X\setminus
U,A)\notin\mathsf{H}_{n}$ so $\mathrm{Cone}(X\setminus
U,A)\notin\mathsf{E}_{n}$. Therefore, the restriction of $f$ to $(X\setminus
U)\cup\mathrm{Cone}(A)$ has a continuous extension to
$\mathrm{Cone}(X\setminus U)$. So $f$ has a continuous extension
$g:X\cup\mathrm{Cone}(X\setminus U)\to\SS_{n}$.

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

(a) $f$ is defined on $X\cup\mathrm{Cone}(A)$

(b) $g$ is defined on $X\cup\mathrm{Cone}(X\setminus U)$

(c) $h$ is defined on $\mathrm{Cone}(X)\setminus(U\times J)$

Figure 3: Consecutive extensions of $f$

∎

Finally, from the point of view of $\mathsf{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\mathsf{H}_{n}\iff X/A\in\mathsf{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\mathsf{H}_{n}\iff(X/A,p_{A})\in\mathsf{H}_{n}$. Indeed, there is a
one-to-one correspondence between continuous functions $f:(X,A)\to(\SS_{n},p)$
and continuous functions $g:(X/A,p_{A})\to(\SS_{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(\SS_{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^{\prime}$ which is constantly $p$ on $q$.

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

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

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

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

We conclude this section with two simple examples of pairs and sets that are
$\mathsf{H}_{n}$-minimal.

######  Proposition 7.21.

The pair $(\mathbb{B}_{n},\SS_{n-1})$ and the space $\SS_{n}$ are
$\mathsf{H}_{n}$-minimal.

###### Proof.

It is a direct application of Proposition 7.14: one has
$\mathrm{Cone}(\mathbb{B}_{n},\SS_{n-1})=\mathrm{Cone}(\SS_{n},\emptyset)=(\mathbb{B}_{n+1},\SS_{n})$
which is $\mathsf{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 $\mathsf{H}_{n}$-minimal.

###  7.4 Connections with homology and cohomology

We end this section with a characterization of $\mathsf{E}_{n}$ and
$\mathsf{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 [HW41, BEGH93, Hat02]. 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\mathbb{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 $\SS_{m}$, one has

$H_{n}(\SS_{m};G)\cong H^{n}(\SS_{m};G)\cong\begin{cases}G&\text{if }n=m\text{
or }n=0,\\\ 0&\text{otherwise},\end{cases}$

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