1 Introduction
Computability Theory
In computable analysis [Reference Pour-El and Ian Richards51, Reference Weihrauch65], there has for a long time been an interest in how complicated the set of codes of some element in a suitable space may be. Pour-El and Richards [Reference Pour-El and Ian Richards51] observed that any real number and, more generally, any point in a Euclidean space has a Turing degree. They subsequently raised the question of whether the same holds true for any computable metric space. Miller [Reference Miller37] later proved that various infinite-dimensional metric spaces such as the Hilbert cube and the space of continuous functions on the unit interval contain points which lack Turing degrees; that is, have no simplest code w.r.t. Turing reducibility. A similar phenomenon was also observed in algorithmic randomness theory. Day and Miller [Reference Day and Miller12] showed that no neutral measure has Turing degree by understanding each measure as a point in the infinite-dimensional space consisting of probability measures on an underlying space.
These previous works convince us of the need for a reasonable theory of degrees of unsolvability of points in an arbitrary represented space. To establish such a theory, we associate a substructure of the Medvedev degrees with a represented space, which we call its point degree spectrum. A wide variety of classical degree structures are realised in this way; for example, Turing degrees [Reference Soare61], enumeration degrees [Reference Friedberg and Rogers16], continuous degrees [Reference Miller37] and degrees of continuous functionals [Reference Hinman20]. What is more noteworthy is that the concept of a point degree spectrum is closely linked to infinite-dimensional topology. For instance, we shall see that for a Polish space all points have Turing degrees if and only if the small transfinite inductive dimension of the space exists.
In a broader context, there are various instances of smallness properties (i.e.,
$\sigma $
-ideals) of spaces and sets that start making sense for points in an effective treatment; for example, arithmetical (Cohen) genericity [Reference Downey and Hirschfeldt14, Reference Odifreddi41], Martin–Löf randomness [Reference Downey and Hirschfeldt14] and effective Hausdorff dimension [Reference Lutz35]. In all of these cases, individual points can carry some amount of complexity; for example, a Martin–Löf random point is in some sense too complicated to be included in a computable
$G_{\delta }$
set having effectively measure zero. A recent important example [Reference Pol and Zakrzewski50, Reference Zapletal66] from forcing theory is genericity with respect to the
$\sigma $
-ideal generated by finite-dimensional compact metrisable spaces. Our work provides an effective notion corresponding to topological invariants such as small inductive dimension or metrisability and, for example, allows us to say that certain points are too complicated to be (computably) a member of a (finite-dimensional) Polish space.
Additionally, the actual importance of point degree spectrum is not merely conceptual but also applicative. Indeed, unexpectedly, our notion of point degree spectrum turned out to be a powerful tool in descriptive set theory and infinite-dimensional topology, in particular in the study of restricted Borel isomorphism problems, as explained in more depth below.
Descriptive Set Theory
A Borel isomorphism problem (see [Reference Cenzer and Daniel Mauldin6, Reference Daniel Mauldin10, Reference Harrington19, Reference Steel62]) asks to find a nontrivial isomorphism type in a certain class of Borel spaces (i.e., topological spaces together with their Borel
$\sigma $
-algebras). As is well known, Kuratowski’s theorem tells us that every uncountable Polish space is Borel isomorphic to the real line
$\mathbb {R}$
. It is lesser known that what Kuratowski really showed is that an uncountable Polish space is unique up to
$\omega $
th-level Borel isomorphism (cf. [Reference Kuratowski33, Remark (ii) in p. 451]). Here, an
$\alpha $
th-level Borel/Baire isomorphism between
$\mathbf {X}$
and
$\mathbf {Y}$
is a bijection f such that
$E\subseteq \mathbf {X}$
is of additive Borel/Baire class
$\alpha $
(i.e.,
$\mathbf {\Sigma }^{0}_{1+\alpha }$
) if and only if
$f[E]\subseteq \mathbf {Y}$
is of additive Borel/Baire class
$\alpha $
. These restricted Borel isomorphisms were also considered by Jayne [Reference Jayne23] in Banach space theory, in order to obtain certain variants of the Banach–Stone theorem and the Gelfand–Kolmogorov theorem for Banach algebras of the forms
$\mathcal {B}_{\alpha }^{*}(\mathbf {X})$
for realcompact spaces
$\mathbf {X}$
. Here,
$\mathcal {B}_{\alpha }^{*}(\mathbf {X})$
is the Banach algebra of bounded real-valued Baire class
$\alpha $
functions on a space
$\mathbf {X}$
with respect to the supremum norm and the pointwise operation [Reference Bade5, Reference Dashiell11, Reference Jayne23]. The first- and second-level Borel/Baire isomorphic classifications have been studied by several authors (see [Reference Jayne and Rogers24, Reference Jayne and Rogers25]). For instance, it is proved that there are at least two second-level Borel isomorphism types of uncountable Polish spaces; that is, types of finite-dimensional Euclidean spaces
$\mathbb {R}^{n}$
and the Hilbert cube
$[0,1]^{\mathbb {N}}$
. However, it is not certain even whether more than two second-level Borel isomorphism types exist:
Problem 1.1 (The Second-Level Borel Isomorphism Problem)
Are all uncountable Polish spaces second-level Borel isomorphic either to
$\mathbb {R}$
or to
$\mathbb {R}^{\mathbb {N}}$
?
Problem 1.1 and the nth-level analogues were recently highlighted by Motto Ros [Reference Ros54, Question 8.5] and Motto Ros et al. [Reference Ros, Schlicht and Selivanov55, Question 4.29]. As already pointed out by Motto Ros [Reference Ros54], Jayne’s work [Reference Jayne23] mentioned above shows that Problem 1.1 is closely related to asking the following problem on Banach algebras.
Problem 1.2. Is the Banach space
$\mathcal {B}_{2}^{*}(\mathbf {X})$
of the Baire class
$2$
functions on an uncountable Polish space
$\mathbf {X}$
linearly isometric (or ring isomorphic) either to
$\mathcal {B}_{2}^{*}([0,1])$
or to
$\mathcal {B}_{2}^{*}([0,1]^{\mathbb {N}})$
?
The very recent successful attempts to generalise the Jayne–Rogers theorem and the Solecki dichotomy (see [Reference Ros54, Reference Pawlikowski and Sabok47] and also [Reference Gregoriades, Kihara and Ng17] for a computability theoretic proof) have revealed the close connection between second-level Borel isomorphism and
$\sigma $
-homeomorphism for Polish spaces (see Subsection 2.2.1). Here, a topological space
$\mathbf {X}$
is
$\sigma $
-homeomorphic to
$\mathbf {Y}$
(written as
$\mathbf {X}\cong _{\sigma }^{\mathfrak {T}}\mathbf {Y}$
) if there are a bijection
$f:\mathbf {X}\to \mathbf {Y}$
and countable covers
$\{\mathbf {X}_{i}\}_{i\in \omega }$
and
$\{\mathbf {Y}_{i}\}_{i\in \omega }$
of
$\mathbf {X}$
and
$\mathbf {Y}$
such that
$f\upharpoonright \mathbf {X}_{i}$
gives a homeomorphism between
$\mathbf {X}_{i}$
and
$\mathbf {Y}_{i}$
for every
$i\in \omega $
.
Therefore, the second-level Borel isomorphism problem is closely related to the following problem.
Problem 1.3 (Motto Ros et al. [Reference Ros, Schlicht and Selivanov55])
Is any Polish space
$\mathbf {X}$
either
$\sigma $
-embedded into
$\mathbb {R}$
or
$\sigma $
-homeomorphic to
$\mathbb {R}^{\mathbb {N}}$
?
Unlike the classical Borel isomorphism problem, which is reducible to the same problem on zero-dimensional Souslin spaces, the second-level Borel isomorphism problem is inescapably tied to infinite-dimensional topology [Reference van Mill64], since all transfinite-dimensional uncountable Polish spaces are mutually second-level Borel isomorphic.
The study of
$\sigma $
-homeomorphic maps in topological dimension theory dates back to a classical work by Hurewicz–Wallman [Reference Hurewicz and Wallman22] characterising transfinite dimensionality. Alexandrov [Reference Aleksandrov2] asked whether there exists a weakly infinite-dimensional compactum which is not
$\sigma $
-homeomorphic to the real line. Roman Pol [Reference Pol49] solved this problem by constructing such a compactum. Roman Pol’s compactum is known to satisfy a slightly stronger covering property, called property C [Reference Addis and Gresham1].
Our notion of degree spectrum on Polish spaces serves as an invariant under second-level Borel isomorphism. Indeed, an invariant which we call degree co-spectrum, a collection of Turing ideals realised as lower Turing cones of points of a Polish space, plays a key role in solving the second-level Borel isomorphism problem. By utilising these computability-theoretic concepts, we will construct a continuum many pairwise incomparable
$\sigma $
-homeomorphism types of compact metrisable C-spaces; that is:
There is a collection
$(\mathbf {X}_{\alpha })_{\alpha <2^{\aleph _{0}}}$
of continuum many compact metrisable C-spaces such that, whenever
$\alpha \not =\beta $
,
$\mathbf {X}_{\alpha }$
cannot be written as a countable union of homeomorphic copies of subspaces of
$\mathbf {X}_{\beta }$
.
This also shows that there are continuum many second-level Borel isomorphism types of compact metric spaces. More generally, a finite-level Borel embedding of
$\mathbf {X}$
into
$\mathbf {Y}$
is an nth-level Borel isomorphism between
$\mathbf {X}$
and a subset of
$\mathbf {Y}$
of finite Borel rank for some
$n\in \mathbb {N}$
. Then, our result entails the following as a corollary:
There is a collection
$(\mathbf {X}_{\alpha })_{\alpha <2^{\aleph _{0}}}$
of continuum many compact metrisable C-spaces such that, whenever
$\alpha \not =\beta $
,
$\mathbf {X}_{\alpha }$
cannot be finite-level Borel embedded into
$\mathbf {X}_{\beta }$
.
The key idea is measuring the quantity of all possible Scott ideals realised within the degree co-spectrum of a given space. Our spaces are completely described in the terminology of computability theory (based on Miller’s work on the continuous degrees [Reference Miller37]). Nevertheless, the first of our examples turns out to be second-level Borel isomorphic to (the sum of countably many copies of) Roman Pol’s compactum (but, of course, our remaining continuum many examples cannot be second-level Borel isomorphic to Pol’s compactum). Hence, our solution can also be viewed as a refinement of Roman Pol’s solution to Alexandrov’s problem.
Summary of Results
In Section 3, we introduce the notion of point degree spectrum and clarify the relationship with
$\sigma $
-continuity. In Section 4, we introduce the notion of an
$\omega $
-left-computably enumerable in-and-above (CEA) operator (see Section 4.2) in the Hilbert cube as an infinite-dimensional analogue of an
$\omega $
-CEA operator (in the sense of classical computability theory) and show that the graph of a universal
$\omega $
-left-CEA operator is an individual counterexample to Problems 1.1, 1.2 and 1.3. In Section 5, we describe a general procedure to construct uncountably many mutually different compacta under
$\sigma $
-homeomorphism. In Section 6, we clarify the relationship between a universal
$\omega $
-left-CEA operator and Roman Pol’s compactum.
Future work
The methods introduced in this article, in particular the notion of the point degree spectrum and the associated connection between topology and computability theory (recursion theory), have already inspired and enabled several other studies. Some additional results are found in the extended arXiv version [Reference Kihara and Pauly31]. In [Reference Gregoriades, Kihara and Ng17], Gregoriades, Kihara and Ng made significant progress on the decomposability conjecture from descriptive set theory. A core aspect of this work is whether certain degree-theoretic results like the Shore–Slaman join theorem and the cone avoidance theorem for
$\Pi ^{0}_{1}$
classes hold for the point degree spectra of Polish spaces.
Building upon our work, Andrews et al. [Reference Andrews, Igusa, Miller and Soskova3] used an effective metrisation argument to show that the point degree spectrum of the Hilbert cube coincides with the almost total enumeration degrees, which in turn is used to show the purely computability-theoretic consequence that PA above is definable in the enumeration degrees. Our idea was also utilised by Kihara [Reference Kihara29] to explain the relationship between non-total continuous degrees and PA degrees in the context of reverse mathematics.
Kihara, Ng and Pauly [Reference Kihara, Ng and Pauly30] have embarked on the systematic endeavour to classify the point degree spectra of second-countable spaces from Counterexample in Topology [Reference Steen and Seebach63]. This has already proven to be a rich source for the fine-grained study of the enumeration degrees, as both previously studied substructures as well as new ones of interest to computability theorists appear in this fashion. Kihara explored the truth-table reducibility variant of our generalised Turing degrees in [Reference Kihara28].
Based on the results both in the present article and in the extension mentioned here, we are confident that both directions of the link between topology and computability theory established here have significant potential for applications. This work can also be considered as part of a general development to study the descriptive theory of represented spaces [Reference Pauly43], together with approaches such as synthetic descriptive set theory proposed in [Reference Pauly and de Brecht45, Reference Pauly and de Brecht46].
2 Preliminaries
2.1 Computability Theory
2.1.1 Basic Notations
We use the standard notations from modern computability theory and computable analysis. We refer the reader to [Reference Odifreddi41, Reference Odifreddi42, Reference Soare61] for the basics on computability theory and to [Reference Pour-El and Ian Richards51, Reference Weihrauch65, Reference Pauly44] for the basics on computable analysis.
By
$f:\subseteq X\to Y$
, we mean a function from a subset of X into Y. Such a function is called a partial function. We fix a pairing function
$(m,n)\mapsto \langle m,n\rangle $
, which is a computable bijection from
$\mathbb {N}^{2}$
onto
$\mathbb {N}$
such that
$\langle m,n\rangle \mapsto m$
and
$\langle m,n\rangle \mapsto n$
are also computable. For
$x,y\in \mathbb {N}^{\mathbb {N}}$
, the join
$x\oplus y\in \mathbb {N}^{\mathbb {N}}$
is defined by
$(x\oplus y)(2n)=x(n)$
and
$(x\oplus y)(2n+1)=y(n)$
. An oracle is an element of
${\{0, 1\}^{\mathbb {N}}}$
or
$\mathbb {N}^{\mathbb {N}}$
. By the notation
$\Phi _{e}^{z}$
we denote the computation of the eth Turing machine with oracle z. We often view
$\Phi _{e}^{z}$
as a partial function on
${\{0, 1\}^{\mathbb {N}}}$
or
$\mathbb {N}^{\mathbb {N}}$
. More precisely,
$\Phi _{e}^{z}(x)=y$
if and only if given an input
$n\in \mathbb {N}$
with oracle
$x\oplus z$
, the eth Turing machine computation halts and outputs
$y(n)$
. The terminology ‘c.e.’ stands for ‘computably enumerable.’ For an oracle z, by ‘z-computable’ and ‘z-c.e.’, we mean ‘computable relative to z’ and ‘c.e. relative to z’. For an oracle x, we write
$x^{\prime }$
for the Turing jump of x; that is, the halting problem relative to x. Generally, for a computable ordinal
$\alpha $
, we use
$x^{(\alpha )}$
to denote the
$\alpha $
th Turing jump of x. Here, regarding the basics on computable ordinals and transfinite Turing jumps, see [Reference Chong, Yu and Sacks9, Reference Sacks58].
One of the most fundamental observations in computable analysis is that a partial function on the space
$\{0,1\}^{\mathbb {N}}$
or
$\mathbb {N}^{\mathbb {N}}$
(topologised as the product of the discrete space
$\{0,1\}$
or
$\mathbb {N}$
) is continuous if and only if it is computable relative to an oracle (cf. [Reference Weihrauch65]). This fundamental ‘relativisation argument’ will be repeatedly utilised.
We will also use the following fact, known as the Kleene recursion theorem or the Kleene fixed point theorem.
Fact 2.1 (The Kleene Recursion Theorem; see [Reference Odifreddi41, Theorem II.2.10])
Given a computable function
$f:\mathbb {N}\to \mathbb {N}$
, one can effectively find an index
$e\in \mathbb {N}$
such that for all oracles
$z \in {\{0, 1\}^{\mathbb {N}}}$
the partial functions
$\Phi _{e}^{z}$
and
$\Phi ^{z}_{f(e)}$
are identical.
2.1.2 Represented spaces
A represented space is a pair
$\mathbf {X} = (X, \delta _{X})$
of a set X and a partial surjection
$\delta _{X} : \subseteq {\mathbb {N}^{\mathbb {N}}} \to X$
. Informally speaking,
$\delta _{X}$
(called a representation) gives names of elements in X by using infinite words. It enables tracking of a function f on abstract sets by a function on infinite words (called a realiser of f). This is crucial for introducing the notion of computability on abstract sets because we already have the notion of computability on infinite words.
Formally, a
$\delta _{X}$
-name or simply a name of
$x\in \mathbf {X}$
is any
$p\in {\mathbb {N}^{\mathbb {N}}}$
such that
$\delta _{X}(p)=x$
. A function between represented spaces is a function between the underlying sets. For
$f : \mathbf {X} \to \mathbf {Y}$
and
$F : \subseteq {\mathbb {N}^{\mathbb {N}}} \to {\mathbb {N}^{\mathbb {N}}}$
, we call F a realiser of f, iff
$\delta _{Y}(F(p)) = f(\delta _{X}(p))$
for all
$p \in \operatorname {dom}(f\delta _{X})$
; that is, if the following diagram commutes:
A map between represented spaces is called computable (continuous), iff it has a computable (continuous) realiser. In other words, a function f is computable (continuous) iff there is a computable (continuous) function F on infinite words such that, given a name p of a point x,
$F(p)$
returns a name of
$f(x)$
. We also use the same notation
$\Phi _{e}^{z}$
to denote a function on represented spaces realised by the eth partial z-computable function. Similarly, we call a point
$x \in \mathbf {X}$
computable, iff there is some computable
$p \in {\mathbb {N}^{\mathbb {N}}}$
with
$\delta _{X}(p) = x$
; that is, x has a computable name. In this way, we think of a represented space as a kind of space equipped with the notion of computability.
If a set X is already topologised, the above notion of continuity (
$=$
relative computability, by the fundamental ‘relativisation argument’ mentioned in Subsection 2.1.1) can be inconsistent with topological continuity. To eliminate such an undesired situation, we shall consider a restricted class of representations which are consistent with a given topological structure, so-called admissible representations. An admissible representation is a partial continuous surjection
$\delta :\subseteq {\mathbb {N}^{\mathbb {N}}}\to X$
such that for any partial continuous function
$f:\subseteq {\mathbb {N}^{\mathbb {N}}}\to X$
there is a partial continuous function
$\theta $
on
${\mathbb {N}^{\mathbb {N}}}$
such that
$f=\delta \circ \theta $
. We will not go into the details of admissibility here but just mention that if a
$T_{0}$
-space has a countable cs-network (a.k.a. a countable sequential pseudo-base), then it always has an admissible representation (see Schröder [Reference Schröder59]). Hence, in this article, we can assume that the ‘relativisation argument’ always works.
A particularly relevant subclass of represented spaces are the computable Polish spaces, which are derived from complete computable metric spaces by forgetting the details of the metric and just retaining the representation (or, rather, the equivalence class of representations under computable translations). Forgetting the metric is relevant when it comes to compatibility with definitions in effective descriptive set theory as shown in [Reference Gregoriades, Kispéter and Pauly18].
Example 2.2. The following are examples of admissible representations:
-
1. The representation of
$\mathbb {N}$
is given by
$\delta _{\mathbb {N}}(0^{n}10^{\mathbb {N}}) = n$
. It is straightforward to verify that the computability notion for the represented space
$\mathbb {N}$
coincides with classical computability over the natural numbers. -
2. A computable metric space is a tuple
$\mathbf {M} = (M, d, (a_{n})_{n \in \mathbb {N}})$
such that
$(M,d)$
is a metric space and
$(a_{n})_{n \in \mathbb {N}}$
is a dense sequence in
$(M,d)$
such that the relation is recursively enumerable, where
$$ \begin{align*} \{(t,u,v,w) \: |\: \nu_{\mathbb{Q}}(t) < d(a_{u}, a_{v}) <\nu_{\mathbb{Q}}(w) \}\end{align*} $$
$\nu _{\mathbb {Q}}$
is the standard numbering of the rationals. The Cauchy representation
$ \delta _{\mathbf {M}} \: : \subseteq \: {\mathbb {N}^{\mathbb {N}}} \to M $
associated with the computable metric space
$ \mathbf {M} = (M, d, (a_{n})_{n \in \mathbb {N}}) $
is defined by
$$ \begin{align*} \delta_{\mathbf{M}}(p) = x \: : \: \Longleftrightarrow \begin{cases} d(a_{p(i)}, a_{p(k)}) \leq 2^{-i} \text{ for } i < k\\ \text{and } x = \lim\limits_{i\rightarrow \infty}a_{p(i)}. \end{cases} \end{align*} $$
-
3. Another, more general, subclass is the quasi-Polish spaces introduced by de Brecht [Reference de Brecht13]. A space X is quasi-Polish if it is countably based and has a total admissible representation
$\delta _{\mathbf {X}} : {\mathbb {N}^{\mathbb {N}}} \to X$
. These include the computable Polish spaces as well as
$\omega $
-continuous domains. -
4. Generally, a topological
$T_{0}$
-space
$\mathbf {X}$
with a countable base
$\mathcal {B}=\langle {B_{n}\rangle }_{n\in \mathbb {N}}$
is naturally represented by defining
$\delta _{(\mathbf {X},\mathcal {B})}(p)=x$
iff p enumerates the code of a neighbourhood basis for x; that is,
$\text{range}(p)=\{n\in \mathbb {N}:x\in B_{n}\}$
. One can also use a network to give a representation of a space as suggested above.
We always assume that
${\{0, 1\}^{\mathbb {N}}}$
,
$\mathbb {R}^{n}$
and
$[0,1]^{\mathbb {N}}$
are admissibly represented by the Cauchy representations obtained from their standard metrics.
A real
$x\in \mathbb {R}$
is left-c.e. if there is a computable sequence
$(q_{n})_{n\in \mathbb {N}}$
of rationals such that
$x=\sup _{n}q_{n}$
(cf. [Reference Downey and Hirschfeldt14]). Generally, a real
$x\in \mathbb {R}$
is left-c.e. relative to
$y\in \mathbf {X}$
if there is a partial computable function
$f:\subseteq \mathbf {X}\to \mathbb {Q}^{\mathbb {N}}$
such that
$x=\sup _{n}f(y)(n)$
. If
$(M,d,(a_{n})_{n\in \mathbb {N}})$
is a computable metric space, there is a computable list
$(B_{e})_{e\in \mathbb {N}}$
of open balls of the form
$B(a_{n};q)$
, where
$B(a_{n};q)$
is the open ball of radius q centred at
$a_{n}$
. We say that a set U is c.e. open if there is a c.e. set
$W\subseteq \mathbb {N}$
such that
$U=\bigcup _{e\in W}B_{e}$
. The complement of a c.e. open set is called
$\Pi ^{0}_{1}$
. By
$\Pi ^{0}_{1}(z)$
, we mean
$\Pi ^{0}_{1}$
relative to an oracle z, whose complement is defined using a z-c.e. set W instead of a c.e. set.
2.1.3 Degree structures
The Medvedev degrees
$\mathfrak {M}$
[Reference Medvedev36] are a cornerstone of our framework. These are obtained by taking equivalence classes from Medvedev reducibility
$\leq _{M}$
, defined on subsets A, B of Baire space
${\mathbb {N}^{\mathbb {N}}}$
via
$A \leq _{M} B$
iff there is a partial computable function
$F :\subseteq {\mathbb {N}^{\mathbb {N}}} \to {\mathbb {N}^{\mathbb {N}}}$
such that
$B\subseteq \mathrm{dom}(F)$
and
$F[B]\subseteq A$
. Important substructures of
$\mathfrak {M}$
also relevant to us are the Turing degrees
$\mathcal {D}_{T}$
, the continuous degrees
$\mathcal {D}_{r}$
and the enumeration degrees
$\mathcal {D}_{e}$
; these satisfy
$\mathcal {D}_{T} \subsetneq \mathcal {D}_{r} \subsetneq \mathcal {D}_{e} \subsetneq \mathfrak {M}$
.
Turing degrees are obtained from the usual Turing reducibility
$\leq _{\mathrm {T}} $
defined on points
$p, q \in {\mathbb {N}^{\mathbb {N}}}$
with
$p \leq _{\mathrm {T}} q$
iff there is a computable function
$F : \subseteq {\mathbb {N}^{\mathbb {N}}} \to {\mathbb {N}^{\mathbb {N}}}$
with
$F(q) = p$
. We thus see
$p \leq _{\mathrm {T}} q \Leftrightarrow \{p\} \leq _{M} \{q\}$
and can indeed understand the Turing degrees to be a subset of the Medvedev degrees. The continuous degrees were introduced by Miller in [Reference Miller37]. Enumeration degrees have received a lot of attention in computability theory and were originally introduced by Friedberg and Rogers [Reference Friedberg and Rogers16] (see also [Reference Odifreddi42, Chapter XIV]). In both cases, we can provide a simple definition directly as a substructure of the Medvedev degrees later on.
A further reducibility notion is relevant, although we are not particularly interested in its degree structure. This is Muchnik reducibility
$\leq _{w}$
[Reference Mučnik40], defined again for sets
$A, B \subseteq {\mathbb {N}^{\mathbb {N}}}$
via
$A \leq _{w} B$
iff, for any
$p \in B$
, there is
$q \in A$
such that
$q \leq _{\mathrm {T}} p$
. Clearly,
$A \leq _{M} B$
implies
$A \leq _{w} B$
, but the converse is false in general.
2.2 Topology and Dimension
2.2.1 Isomorphism and Classification
We are now interested in isomorphisms of a particular kind; this always means a bijection in that function class, such that the inverse is also in that function class. For instance, consider the following morphisms. For a function
$f:\mathbf {X}\to \mathbf {Y}$
,
-
1. f is
$\sigma $
-computable (
$\sigma $
-continuous, respectively) if there are sets
$(X_{n})_{n \in \mathbb {N}}$
such that
$\mathbf {X} = \bigcup _{n \in \mathbb {N}} X_{n}$
and each
$f|_{X_{n}}$
is computable (continuous, respectively) -
2. f is
$\mathbf {\Gamma }$
-piecewise continuous if there are
$\mathbf {\Gamma }$
-sets
$(X_{n})_{n \in \mathbb {N}}$
such that
$\mathbf {X} = \bigcup _{n \in \mathbb {N}} X_{n}$
and each
$f|_{X_{n}}$
is continuous. -
3. f is nth-level Borel measurable if
$f^{-1}[A]$
is
$\mathbf {\Sigma }^{0}_{n+1}$
for every
$\mathbf {\Sigma }^{0}_{n+1}$
set
$A\subseteq \mathbf {Y}$
.
In particular, f is second-level Borel measurable iff
$f^{-1}[A]$
is
$G_{\delta \sigma }$
for every
$G_{\delta \sigma }$
set
$A\subseteq \mathbf {Y}$
. We also say that f is finite-level Borel measurable if it is nth-level Borel measurable for some
$n\in \mathbb {N}$
. Note that
$\sigma $
-continuity is also known as countable continuity. A
$\sigma $
-homeomorphism is a bijection
$f:\mathbf {X}\to \mathbf {Y}$
such that both f and
$f^{-1}$
are
$\sigma $
-continuous. Similarly, a
$\sigma $
-embedding of
$\mathbf {X}$
into
$\mathbf {Y}$
is a
$\sigma $
-homeomorphism between
$\mathbf {X}$
and a subspace of
$\mathbf {Y}$
.
Remark 2.3. Note that if
$f:\mathbf {X}\to \mathbf {Y}$
is a
$\sigma $
-homeomorphism, then f is a countable union of partial homeomorphisms: By definition, we can write f as the union of continuous injections
$f_{i}:X_{i}\to \mathbf {Y}$
and, similarly,
$f^{-1}$
as the union of
$g_{j}\colon Y_{j}\to \mathbf {X}$
. Then, the restriction
$f_{ij}$
of
$f_{i}$
up to
$X_{i}\cap g_{j}[Y_{j}]$
is a homeomorphism between
$X_{i}\cap g_{j}[Y_{j}]$
and
$f_{i}[X_{i}]\cap Y_{j}$
. Clearly, f is the union of
$f_{ij}$
s. It is clear that the converse is also true.
By recent results from descriptive set theory (cf. [Reference Gregoriades, Kihara and Ng17, Reference Kihara27, Reference Ros54, Reference Pawlikowski and Sabok47]), we have the following implication for functions on Polish spaces:
$$ \begin{align*} \mathbf{\Sigma}^{0}_{n+1}\mbox{-piecewise continuous}&\iff\mathbf{\Pi}^{0}_{n}\mbox{-piecewise continuous}\\ &\implies\mathit{n}\mbox{th-level Borel measurable}\implies\sigma\mbox{-continuous}. \end{align*} $$
The last implication was recently proved by [Reference Ros54, Reference Pawlikowski and Sabok47] and, more recently, an alternative computability theoretic proof was given by [Reference Gregoriades, Kihara and Ng17] using our framework of point degree spectra of Polish spaces.
Observation 2.4. Let
$\mathbf {X}$
and
$\mathbf {Y}$
be Polish spaces. Then,
$\mathbb {N}\times \mathbf {X}$
and
$\mathbb {N}\times \mathbf {Y}$
are
$\sigma $
-homeomorphic if and only if
$\mathbb {N}\times \mathbf {X}$
and
$\mathbb {N}\times \mathbf {Y}$
are second-level Borel isomorphic.
Proof. For the ‘if’ direction, assume that
$\mathbf {X}$
and
$\mathbf {Y}$
are second-level Borel isomorphic; that is, there is a bijection
$f\colon \mathbf {X}\to \mathbf {Y}$
such that both f and
$f^{-1}$
are second-level Borel measurable. From the above argument, both f and
$f^{-1}$
are
$\sigma $
-continuous and, therefore, f is a
$\sigma $
-homeomorphism.
To show the ‘only if’ direction, recall (from Remark 2.3) that a
$\sigma $
-homeomorphism of
$\mathbf {X}$
into
$\mathbf {Y}$
is a countable union of partial homeomorphisms. Then, note that, by the Lavrentiev theorem (cf. [Reference Kechris26, Theorem 3.9]), every homeomorphism between subsets of Polish spaces can be extended to a homeomorphism between
$G_{\delta }$
sets. Therefore, we have homeomorphisms
$h_{n}$
between
$G_{\delta }$
sets
$X_{n}\subseteq \mathbf {X}$
and
$Y_{n}\subseteq \mathbf {Y}$
such that
$\bigcup _{n}X_{n}=\mathbf {X}$
and
$\bigcup _{n}Y_{n}=\mathbf {Y}$
. Then, by defining
$h_{n}^{\ast }:X_{n}\setminus \bigcup _{m<n}X_{m}\to \{n\}\times \mathbf {Y}$
with
$h^{\ast }_{n}(x)=(n,h_{n}(x))$
, we obtain a
$\mathbf {\Delta }^{0}_{3}$
-piecewise embedding of
$\mathbf {X}$
into
$\mathbb {N}\times \mathbf {Y}$
whose image is
$\mathbf {\Delta }^{0}_{3}$
. Hence, whenever Polish spaces
$\mathbf {X}$
and
$\mathbf {Y}$
are
$\sigma $
-homeomorphic, we get second-level Borel embeddings
$f:\mathbf {X}\to \mathbb {N}\times \mathbf {Y}$
and
$g:\mathbf {Y}\to \mathbb {N}\times \mathbf {X}$
with
$\mathbf {\Delta }^{0}_{3}$
images. Then, using a finer version (see [Reference Jayne and Rogers25, Lemma 5.2]) of the Cantor–Bernstein argument, one can construct a second-level Borel isomorphism between
$\mathbb {N}\times \mathbf {X}$
and
$\mathbb {N}\times \mathbf {Y}$
. This verifies our assertion since
$\mathbb {N}\simeq \mathbb {N}^{2}$
.
Consequently, the second-level Borel isomorphic classification and the
$\sigma $
-homeomorphic classification of Polish spaces are almost the same. Hence, three classification problems, Problems 1.1, 1.2 and 1.3 in Section 1, are almost equivalent.
Hereafter, for notation, let
$\cong $
be computable isomorphism,
$\cong ^{\mathfrak {T}}$
continuous isomorphism (i.e., homeomorphism),
$\cong _{\sigma }$
isomorphism by
$\sigma $
-computable functions and
$\cong _{\sigma }^{\mathfrak {T}} \sigma $
-continuous isomorphism (i.e.,
$\sigma $
-homeomorphism).
For any of these notions, we write
$\mathbf {X} \leq \mathbf {Y}$
with the same decorations on
$\leq $
if
$\mathbf {X}$
is isomorphic to a subspace of
$\mathbf {Y}$
(i.e.,
$\mathbf {X}$
is embedded into
$\mathbf {Y}$
) in that way. If
$\mathbf {X} \leq \mathbf {Y}$
holds, but
$\mathbf {Y}\leq \mathbf {X}$
does not, then we also write
$\mathbf {X} < \mathbf {Y}$
, again with the suitable decorations on
$<$
. If neither
$\mathbf {X} \leq \mathbf {Y}$
nor
$\mathbf {Y} \leq \mathbf {X}$
, we write
$\mathbf {X} \ | \ \mathbf {Y}$
(again, with the same decorations). Again, the Cantor–Bernstein argument shows the following.
Observation 2.5. Let
$\mathbf {X}$
and
$\mathbf {Y}$
be represented spaces. Then,
$\mathbf {X}\cong _{\sigma }\mathbf {Y}$
if and only if
$\mathbf {X}\leq _{\sigma }\mathbf {Y}$
and
$\mathbf {Y}\leq _{\sigma }\mathbf {X}$
.
2.2.2 Topological Dimension theory
As a general source for topological dimension theory, we point to Engelking [Reference Engelking15]. See also van Mill [Reference van Mill64] for infinite-dimensional topology. A topological space
$\mathbf {X}$
is countable dimensional if it can be written as a countable union of finite-dimensional subspaces. Recall that a Polish space is countable dimensional if and only if it is transfinite dimensional; that is, its transfinite small inductive dimension is less than
$\omega _{1}$
(see [Reference Hurewicz and Wallman22, pp. 50–51]). One can see that a Polish space
$\mathbf {X}$
is countable dimensional if and only if
$\mathbf {X}\leq _{\sigma }^{\mathfrak {T}}{\{0, 1\}^{\mathbb {N}}}$
.
To investigate the structure of uncountable dimensional spaces, Alexandrov introduced the notion of weakly/strongly infinite-dimensional space. We say that C is a separator (usually called a partition in dimension theory) of a pair
$(A,B)$
in a space
$\mathbf {X}$
if there are two pairwise disjoint open sets
$A^{\prime }\supseteq A$
and
$B^{\prime }\supseteq B$
such that
$A^{\prime }\sqcup B^{\prime }=\mathbf {X}\setminus C$
. A family
$\{(A_{i},B_{i})\}_{i\in \Lambda }$
of pairwise disjoint closed sets in
$\mathbf {X}$
is essential if whenever
$C_{i}$
is a separator of
$(A_{i},B_{i})$
in
$\mathbf {X}$
for every
$i\in \mathbb {N}$
,
$\bigcap _{i\in \mathbb {N}}C_{i}$
is nonempty. An infinite-dimensional space X is said to be strongly infinite-dimensional if it has an essential family of infinite length. Otherwise, X is said to be weakly infinite-dimensional.
We also consider the following covering property for topological spaces. Let
$\mathcal {O}[{\mathbf {X}}]$
be the collection of all open covers of a topological space
$\mathbf {X}$
and
$\mathcal {O}_{2}[{\mathbf {X}}]=\{\mathcal {U}\in \mathcal {O}[X] : |\mathcal {U}|=2\}$
; that is, the collection of all covers by two open sets. For
$\mathcal {A},\mathcal {B}\in \{\mathcal {O}_{2},\mathcal {O}\}$
, we write
$\mathbf {X}\in \mathcal {S}_{c}(\mathcal {A},\mathcal {B})$
if and only if for any sequence
$(\mathcal {U}_{n})_{n\in \mathbb {N}}\in \mathcal {A}[\mathbf {X}]^{\mathbb {N}}$
, there is a sequence
$(\mathcal {V}_{n})_{n\in \mathbb {N}}$
of pairwise disjoint open sets such that
$\mathcal {V}_{n}$
refines
$\mathcal {U}_{n}$
for each
$n\in \mathbb {N}$
and
$\bigcup _{n\in \mathbb {N}}\mathcal {V}_{n}\in \mathcal {B}[\mathbf {X}]$
.
Note that a topological space
$\mathbf {X}$
is weakly infinite-dimensional if and only if
$\mathbf {X}\in \mathcal {S}_{c}(\mathcal {O}_{2},\mathcal {O})$
. We say that
$\mathbf {X}$
is a C-space [Reference Addis and Gresham1] or selectively screenable [Reference Babinkostova4] if
$\mathbf {X}\in \mathcal {S}_{c}(\mathcal {O},\mathcal {O})$
. For a topological property
$\mathcal {P}$
, we say that
$\mathbf {X}$
is hereditarily
$\mathcal {P}$
if every subspace of
$\mathbf {X}$
is
$\mathcal {P}$
. We have the following implications:
$$ \begin{align*}\mbox{countable-dimensional }\Rightarrow\mbox{ }C\mbox{-space }\Rightarrow\mbox{ weakly infinite-dimensional}.\end{align*} $$
Alexandrov’s old problem was whether there exists a weakly infinite-dimensional compactum which is not countable dimensional; that is,
$\mathbf {X}>_{\sigma }^{\mathfrak {T}}{\{0, 1\}^{\mathbb {N}}}$
. This problem was solved by R. Pol [Reference Pol49] by constructing a compact metrisable space of the form
$R\cup L$
for a strongly infinite-dimensional totally disconnected subspace R and a countable dimensional subspace L. Such a compactum is a C-space but not countable dimensional. Namely, R. Pol’s theorem says that there are at least two
$\sigma $
-homeomorphism types of compact metrisable C-spaces.
There are previous studies on the structure of continuous isomorphism types (Fréchet dimension types) of various kinds of infinite-dimensional compacta; for example, strongly infinite-dimensional Cantor manifolds (see [Reference Chatyrko7, Reference Chatyrko and Pol8]). For instance, by combining the Baire category theorem and the result by Chatyrko-Pol [Reference Chatyrko and Pol8], one can show that there are continuum many first-level Borel isomorphism types of strongly infinite-dimensional Cantor manifolds. However, there is an enormous gap between first and second level and, hence, such an argument never tells us anything about second-level Borel isomorphism types. Concerning weakly infinite-dimensional Cantor manifolds, Elżbieta Pol [Reference Pol48] (see also [Reference Chatyrko7]) constructed a compact metrisable C-space in which no separator of nonempty subspaces can be hereditarily weakly infinite-dimensional. We call such a space a Pol-type Cantor manifold.
3 Point Degree Spectra
3.1 Generalised Turing Reducibility
Recall that the notion of a represented space involves the notion of computability. More precisely, every point in a represented space is coded by an infinite word, called a name. Then, we estimate how complicated a given point is by considering the degree of difficulty of calling a name of the point. Of course, it is possible for each point to have many names, and this feature yields the phenomenon that there is a point with no easiest names with respect to Turing degree.
Formally, we associate analogies of Turing reducibility and Turing degrees with an arbitrary represented space in the following manner.
Definition 3.1. Let
$\mathbf {X}$
and
$\mathbf {Y}$
be represented spaces. We say that
$y\in \mathbf {Y}$
is point-Turing reducible to
$x\in \mathbf {X}$
if there is a partial computable function
$f:\subseteq \mathbf {X}\to \mathbf {Y}$
such that
$f(x)=y$
. In other words, the set
$\delta ^{-1}_{Y}(y)$
of names of y is Medvedev reducible to the set
$\delta ^{-1}_{X}(x)$
of names of x. In this case, we write
$y^{\mathbf {Y}}\leq _{\mathrm {T}} x^{\mathbf {X}}$
, or simply
$y\leq _{\mathrm {T}} x$
.
Roughly speaking, by the condition
$y\leq _{\mathrm {T}} x$
we mean that if one knows a name of x, one can compute a name of y, in a uniform manner. This pre-ordering relation
$\leq _{\mathrm {T}}$
clearly yields an equivalence relation
$\equiv _{\mathrm {T}}$
on points
$x^{\mathbf {X}}$
of represented spaces, and we then call each equivalence class
$[x^{\mathbf {X}}]_{\equiv _{\mathrm {T}}}$
the point-Turing degree of
$x\in \mathbf {X}$
, denoted by
$\deg (x^{\mathbf {X}})$
. In other words,
$$ \begin{align*}\deg(x^{\mathbf{X}}) = [\delta_{X}^{-1}(x)]_{\equiv_{M}} = \mbox{`the Medvedev degree of the set of all }\delta_{X}\mbox{-names of }\mathit{x}\text{'}.\end{align*} $$
Then, we introduce the notion of point degree spectrum of a represented space as follows.
Definition 3.2. For a represented space
$\mathbf {X}$
, define
$$ \begin{align*}\mathrm{Spec}(\mathbf{X}) =\{ \deg(x^{\mathbf{X}}) \mid x \in \mathbf{X}\} \subseteq \mathfrak{M}.\end{align*} $$
We call
$\mathrm{Spec}(\mathbf {X})$
the point degree spectrum of
$\mathbf {X}$
. Given an oracle p, we also define the p-relativised point degree spectrum by replacing a partial computable function in Definition 3.1 with a partial p-computable function. Equivalently, define
$\deg ^{p}(x^{\mathbf {X}})=[\{p\}\times \delta ^{-1}_{\mathbf {X}}(x)]_{\equiv _{M}}$
and
$\mathrm{Spec}^{p}(\mathbf {X})=\{\deg ^{p}(x^{\mathbf {X}}):x\in \mathbf {X}\}$
.
Clearly, one can identify the Turing degrees
$\mathcal {D}_{T}$
, the continuous degrees
$\mathcal {D}_{r}$
and the enumeration degrees
$\mathcal {D}_{e}$
with degree spectra of some spaces as follows:
-
○
$\mathrm{Spec}({\{0, 1\}^{\mathbb {N}}}) = \mathrm{Spec}({\mathbb {N}^{\mathbb {N}}}) = \mathrm{Spec}(\mathbb {R}) = \mathcal {D}_{T}$
, -
○ (Miller [Reference Miller37])
$\mathrm{Spec}({[0, 1]}^{\mathbb {N}}) = \mathrm{Spec}(\mathcal {C}({[0, 1]},{[0, 1]})) = \mathcal {D}_{r}$
, -
○
$\mathrm{Spec}(\mathcal {O}(\mathbb {N})) = \mathcal {D}_{e}$
, where
$\mathcal {O}(\mathbb {N})$
is the space of all subsets of
$\mathbb {N}$
where a basic open set is the set of all supersets of a finite subset of
$\mathbb {N}$
. Note that
$\mathcal {O}(\mathbb {N})$
is (computably) homeomorphic to
$\mathbb {S}^{\mathbb {N}}$
, where
$\mathbb {S}$
is the Sierpiński space.
As any separable metric space embeds into the Hilbert cube
${[0, 1]}^{\mathbb {N}}$
, we find in particular that
$\mathrm{Spec}(\mathbf {X}) \subseteq \mathcal {D}_{r}$
for any computable metric space
$\mathbf {X}$
. As any second-countable
$T_{0}$
space embeds into the Scott domain
$\mathcal {O}(\mathbb {N})$
, we also have that
$\mathrm{Spec}(\mathbf {X}) \subseteq \mathcal {D}_{e}$
for any computable second-countable
$T_{0}$
space
$\mathbf {X}$
. In the latter case, the point degree of
$x\in \mathbf {X}$
corresponds to the enumeration degree of neighbourhood basis as in Example 2.2 (4). The Turing degrees will be characterised in Subsection 3.2 in the context of topological dimension theory.
In computable model theory, the degree spectrum of a countable structure S is defined as the collection of Turing degrees of isomorphic copies of S coded in
$\mathbb {N}$
(see [Reference Hirschfeldt, Khoussainov, Shore and Slinko21, Reference Richter53]). The notion of degree spectrum on a cone (i.e., degree spectrum relative to an oracle) also plays an important role in (computable) model theory (see [Reference Montalbán38, Reference Montalbán39]). One can define the space of countable structures as done in invariant descriptive set theory; however, from this perspective, a countable structure is a point and, therefore, the degree spectrum of a structure corresponds to the degree spectrum of a point rather than that of a space.
Given a point
$x\in \mathbf {X}$
, we define
$\mathrm{Spec}(x^{\mathbf {X}})$
as the set of all oracles
$z\in \{0,1\}^{\mathbb {N}}$
which can compute a name of x and
$\mathrm{Spec}^{p}(x^{\mathbf {X}})$
as its relativisation by an oracle
$p\in \{0,1\}^{\mathbb {N}}$
. Then, the weak point degree spectrum
$\mathrm{Spec}_{w}(\mathbf {X})$
is the collection of all degree spectra of points of
$x\in \mathbf {X}$
and
$\mathrm{Spec}^{p}_{w}(\mathbf {X})$
is its relativisation by an oracle p; that is,
$$ \begin{align*} &\text{Spec}(x^{\mathbf{X}})=\{z\in\{0,1\}^{\mathbb{N}}:x\leq_{\mathrm{T}} z\},& &\text{Spec}^{p}(x^{\mathbf{X}})=\{z\in\{0,1\}^{\mathbb{N}}:x\leq_{\mathrm{T}} (z,p)\},\\ &\text{Spec}_{w}(\mathbf{X})=\{\text{Spec}(x^{\mathbf{X}}):x\in\mathbf{X}\},& &\text{Spec}^{p}_{w}(\mathbf{X})=\{\text{Spec}^{p}(x^{\mathbf{X}}):x\in\mathbf{X}\}. \end{align*} $$
Note that this notion can be described in terms of Muchnik reducibility [Reference Mučnik40]; that is, we can think of the degree spectrum of
$x\in \mathbf {X}$
as
$$ \begin{align*}\mathrm{Spec}(x^{\mathbf{X}})\approx[\delta_{X}^{-1}(x)]_{\equiv_{w}}=\mbox{`the Muchnik degree of the set of all }\delta_{X}\mbox{-names of }\mathit{x}\text{'}.\end{align*} $$
Observation 3.3. If
$\mathbf {X}$
and
$\mathbf {Y}$
are admissibly represented second-countable
$T_{0}$
-spaces, then there is an oracle p such that for all
$q\geq _{T}p$
,
$$ \begin{align*}\mathrm{Spec}^{q}(\mathbf{X})\subseteq\mathrm{Spec}^{q}(\mathbf{Y})\iff\mathrm{Spec}^{q}_{w}(\mathbf{X})\subseteq\mathrm{Spec}^{q}_{w}(\mathbf{Y}).\end{align*} $$
Proof. It is known that enumeration reducibility coincides with its nonuniform version (see [Reference Selman60] or [Reference Miller37, Theorem 4.2]); that is, for
$A,B\subseteq \mathbb {N}$
, the condition
$A\leq _{e}B$
is equivalent to the following: For any
$Z\in {\{0, 1\}^{\mathbb {N}}}$
, if B is Z-c.e., then A is also Z-c.e. In our terminology, for
$\mathbf {C}={\{0, 1\}^{\mathbb {N}}}$
and
$\mathbf {D}=\mathcal {O}(\mathbb {N})$
, the abovementioned equivalence says that for any
$a,b\in \mathbf {D}$
,
$$ \begin{align*} a^{\mathbf{D}}\leq_{\mathrm{T}} b^{\mathbf{D}}&\iff(\forall z\in\mathbf{C})\;[b^{\mathbf{D}}\leq_{\mathrm{T}} z^{\mathbf{C}}\implies a^{\mathbf{D}}\leq_{\mathrm{T}} z^{\mathbf{C}}]\\ &\iff\text{Spec}(b^{\mathbf{D}})\subseteq\text{Spec}(a^{\mathbf{D}}). \end{align*} $$
In particular,
$a^{\mathbf {D}}\equiv _{\mathrm {T}} b^{\mathbf {D}}$
if and only if
$\mathrm{Spec}(b^{\mathbf {D}})=\mathrm{Spec}(a^{\mathbf {D}})$
. Let
$\mathbf {X}$
and
$\mathbf {Y}$
be subspaces of
$\mathbf {D}$
. Note that
$\mathrm{Spec}(\mathbf {X})\subseteq \mathrm{Spec}(\mathbf {Y})$
iff for any
$x\in \mathbf {X}$
there is
$y\in \mathbf {Y}$
such that
$x^{\mathbf {X}}\equiv _{\mathrm {T}} y^{\mathbf {Y}}$
. Since
$x^{\mathbf {X}}\equiv _{\mathrm {T}} y^{\mathbf {Y}}$
is equivalent to
$\mathrm{Spec}(x^{\mathbf {X}})=\mathrm{Spec}(y^{\mathbf {Y}})$
, we get that
$\mathrm{Spec}_{w}(\mathbf {X})\subseteq \mathrm{Spec}_{w}(\mathbf {Y})$
.
As in Example 2.2 (4), every second-countable
$T_{0}$
-space can be embedded into the Scott domain
$\mathcal {O}(\mathbb {N})$
. Use the relativisation argument to get an oracle p such that there are p-computable embeddings of
$\mathbf {X}$
and
$\mathbf {Y}$
into
$\mathcal {O}(\mathbb {N})$
. Then, the desired assertion can be verified by relativising the above argument to any oracle
$q\geq _{T}p$
.
3.2 Degree Spectra and Dimension Theory
One of the main tools in our work is the following characterisation of the point degree spectra of represented spaces.
Theorem 3.4. The following are equivalent for admissibly represented spaces
$\mathbf {X}$
and
$\mathbf {Y}$
:
-
1.
$\mathrm{Spec}^{r}(\mathbf {X})=\mathrm{Spec}^{r}(\mathbf {Y})$
for some oracle
$r\in {\{0, 1\}^{\mathbb {N}}}$
. -
2.
$\mathbb {N}\times \mathbf {X}$
is
$\sigma $
-homeomorphic to
$\mathbb {N}\times \mathbf {Y}$
; that is,
$\mathbb {N}\times \mathbf {X}\cong _{\sigma }^{\mathfrak {T}}\mathbb {N}\times \mathbf {Y}$
.
Moreover, if
$\mathbf {X}$
and
$\mathbf {Y}$
are Polish, then the following assertions (3) and (4) are also equivalent to the above assertions (1) and (2).
-
3.
$\mathbb {N}\times \mathbf {X}$
is second-level Borel isomorphic to
$\mathbb {N}\times \mathbf {Y}$
. -
4. The Banach algebra
$\mathcal {B}_{2}^{*}(\mathbb {N}\times \mathbf {X})$
is linearly isometric (ring isomorphic and so on) to
$\mathcal {B}_{2}^{*}(\mathbb {N}\times \mathbf {Y})$
.
One can also see that the following assertions are equivalent:
-
2′.
$\mathbb {N}\times \mathbf {X}$
is
$G_{\delta }$
-piecewise homeomorphic to
$\mathbb {N}\times \mathbf {Y}$
. -
3′.
$\mathbb {N}\times \mathbf {X}$
is nth-level Borel isomorphic to
$\mathbb {N}\times \mathbf {Y}$
for some
$n\geq 2$
. -
4′. The Banach algebra
$\mathcal {B}_{n}^{*}(\mathbb {N}\times \mathbf {X})$
is linearly isometric (ring isomorphic and so on) to
$\mathcal {B}_{n}^{*}(\mathbb {N}\times \mathbf {Y})$
for some
$n\geq 2$
.
By Observation 2.4 and its proof, the assertions (2), (2
$^{\prime }$
) and (3) are equivalent. Obviously, the assertions (3) and (4) imply (3
$^{\prime }$
) and (4
$^{\prime }$
), respectively. The equivalence between (3) and (4) (and the equivalence between (3
$^{\prime }$
) and (4
$^{\prime }$
)) has already been shown by Jayne [Reference Jayne23] for second-countable (or, more generally, real compact) spaces
$\mathbf {X}$
and
$\mathbf {Y}$
. Consequently, all assertions from (2) to (4
$^{\prime }$
) are equivalent.
To see the equivalence between (1) and (2), we characterise the point degree spectra of represented spaces in the context of computable
$\sigma $
-embedding.
Lemma 3.5. The following are equivalent for represented spaces
$\mathbf {X}$
and
$\mathbf {Y}$
:
-
1.
$\mathrm{Spec}(\mathbf {X}) \subseteq \mathrm{Spec}(\mathbf {Y})$
-
2.
$\mathbf {X}\leq _{\sigma }\mathbb {N}\times \mathbf {Y}$
; that is,
$\mathbf {X}$
is a countable union of subspaces that are computably isomorphic to subspaces of
$\mathbf {Y}$
.
Proof. We first show that the assertion (1) implies (2). By assumption, for any
$x \in \mathbf {X}$
we find
$x^{\mathbf {X}}\equiv _{M}y_{x}^{\mathbf {Y}}$
for some
$y_{x} \in \mathbf {Y}$
. For any
$i, j \in \mathbb {N}$
, let
$\mathbf {X}_{ij}$
be the set of all points where the reductions are witnessed by
$\Phi _{i}$
and
$\Phi _{j}$
. More precisely, put
$\mathbf {X}_{ij}=\{x\in \mathbf {X}:\Phi _{j}\Phi _{i}(x)=x\}$
, where we recall that
$\Phi _{e}$
is a partial function on represented spaces realised by the eth partial computable function. Let
$\mathbf {Y}_{ij} = \{\Phi _{i}(x) \mid x \in \mathbf {X}_{ij}\} \subseteq \mathbf {Y}$
. Then
$\Phi _{i}$
and
$\Phi _{j}$
also witness
$\mathbf {X}_{ij} \cong \mathbf {Y}_{ij}$
. Obviously,
$\mathbf {X} = \bigcup _{\langle i, j\rangle \in \mathbb {N}} \mathbf {X}_{ij}$
since
$x^{\mathbf {X}}\equiv _{M}y_{x}^{\mathbf {Y}}$
is witnessed by some
$\Phi _{i}$
and
$\Phi _{j}$
; that is,
$\Phi _{i}(x)=y_{x}$
and
$\Phi _{j}(y_{x})=x$
. Then, the union of computable homeomorphisms
$\mathbf {X}_{ij}\simeq \{\langle i,j\rangle \}\times \mathbf {Y}_{ij}$
gives a
$\sigma $
-computable embedding of
$\mathbf {X}$
into
$\mathbb {N}\times \mathbf {Y}$
.
Conversely, the point degree spectrum is preserved by computable isomorphism and, clearly,
$\mathrm{Spec}\left (\bigcup _{n \in \mathbb {N}} \mathbf {X}_{n}\right ) = \bigcup _{n \in \mathbb {N}} \mathrm{Spec}(\mathbf {X}_{n})$
, so the claim follows.
Proof of Theorem 3.4 (1)
$\Leftrightarrow $
(2)
It follows from relativisations of Lemma 3.5 and Observation 2.5. Here, it is easy to see that the assertion (2) is equivalent to
$\mathbb {N}\times \mathbf {X}\leq _{\sigma }\mathbb {N}\times \mathbf {Y}$
.
This simple argument completely solves a mystery about the occurrence of non-Turing degrees in proper infinite-dimensional spaces. Concretely speaking, by relativising Lemma 3.5, we can characterise the Turing degrees in terms of topological dimension theory as follows.Footnote 1
Corollary 3.6. The following are equivalent for a separable metrisable space
$\mathbf {X}$
endowed with an admissible representation:
-
1.
$\mathrm{Spec}^{p}(\mathbf {X}) \subseteq \mathcal {D}_{T}$
for some oracle
$p\in {\{0, 1\}^{\mathbb {N}}}$
-
2.
$\mathbf {X}$
is countable dimensional.
By a dimension-theoretic fact (see Subsection 2.2.2), if
$\mathbf {X}$
is Polish, transfinite dimensionality is also equivalent to the condition for
$\mathbf {X}$
in which any point has a Turing degree relative to some oracle.
By definition,
$\mathrm{Spec}(\mathbf {X})$
can be considered as a degree structure (i.e., a substructure of the enumeration degrees or the Medvedev degrees). Hence, by Theorem 3.4,
$\sigma $
-homeomorphic classification can be viewed as a kind of degree theory dealing with the order structure on degree structures (on a cone). Thus, from the viewpoint of degree theory, it is natural to ask whether Post’s problem (of whether there is an intermediate degree structure strictly between the bottom
${\{0, 1\}^{\mathbb {N}}}$
and the top
$[0,1]^{\mathbb {N}}$
), the Friedberg–Muchnik theorem (there is a pair of incomparable degree structures), the Sacks density theorem (given two comparable, but different, degree structures, there is an intermediate degree structure strictly between them) and so on are true for the order of degree structures of uncountable Polish spaces.
More details of the structure of degree spectra of Polish spaces will be investigated in Sections 4 and 5.
4 Intermediate Point Degree Spectra
4.1 Intermediate Polish Spaces
In this section, we investigate the structure of
$\sigma $
-homeomorphic types or, (almost) equivalently, point degree spectra (up to relativisation) of uncountable Polish spaces.
It is well-known that for every uncountable Polish space X:
$$ \begin{align*}{\{0, 1\}^{\mathbb{N}}}\leq_{c}^{\mathfrak{T}} X\leq_{c}^{\mathfrak{T}}[0,1]^{\mathbb{N}},\end{align*} $$
where, recall that
$\leq _{c}^{\mathfrak {T}}$
is the topological embeddability relation (i.e., the ordering of Fréchet dimension types). In this section, we focus on Problem 1.3 asking whether there exists a Polish space
$\mathbf {X}$
satisfying the following:
$$ \begin{align*}{\{0, 1\}^{\mathbb{N}}} <_{\sigma}^{\mathfrak{T}}\mathbf{X}<_{\sigma}^{\mathfrak{T}}[0,1]^{\mathbb{N}}.\end{align*} $$
One can see that there is no difference between the structures of
$\sigma $
-homeomorphism types of uncountable Polish spaces and uncountable compact metric spaces.
Fact 4.1. Every Polish space is
$\sigma $
-homeomorphic to a compact metrisable space.
Proof. If a pair of countable spaces has the same cardinality, then they are clearly
$\sigma $
-homeomorphic. Moreover, there are compact metrisable spaces of all countable cardinalities.
So let
$\mathbf {X}$
be an uncountable Polish space. Lelek [Reference Lelek34] showed that every Polish space
$\mathbf {X}$
has a compactification
$\gamma \mathbf {X}$
such that
$\gamma \mathbf {X}\setminus \mathbf {X}$
is countable dimensional. Clearly,
$\mathbf {X}\leq _{c}\gamma \mathbf {X}$
. Then, we have
$\gamma \mathbf {X}\setminus \mathbf {X}\leq _{\sigma }^{\mathfrak {T}}{\{0, 1\}^{\mathbb {N}}}\leq _{\sigma }^{\mathfrak {T}}\mathbf {X}$
, since
$\mathbf {X}$
is uncountable Polish and
$\gamma \mathbf {X}\setminus \mathbf {X}$
is countable dimensional. Consequently,
$\mathbf {X},\gamma \mathbf {X}\setminus \mathbf {X}\leq _{\sigma }^{\mathfrak {T}}\mathbf {X}$
, and this implies
$\gamma \mathbf {X}=\mathbf {X}\cup (\gamma \mathbf {X}\setminus \mathbf {X})\leq _{\sigma }^{\mathfrak {T}}\mathbf {X}$
.
4.2 The Graph Space of a Universal
$\omega $
-Left-CEA Operator
Now, we provide a concrete example having an intermediate degree spectrum. We say that a point
$(r_{n})_{n\in \mathbb {N}}\in [0,1]^{\mathbb {N}}$
is
$\omega $
-left-CEA in
$x\in {\mathbb {N}^{\mathbb {N}}}$
if
$r_{n+1}$
is left-c.e. in
$\langle x,r_{0},r_{1},\dots ,r_{n}\rangle $
uniformly in
$n\in \mathbb {N}$
. In other words, there is a computable function
$\Psi :{\mathbb {N}^{\mathbb {N}}}\times [0,1]^{<\omega }\times \mathbb {N}^{2}\to \mathbb {Q}_{\geq 0}$
such that
$$ \begin{align*}r_{n}=\sup_{s\in\mathbb{N}}\Psi(x,r_{0},\dots,r_{n-1},n,s)\end{align*} $$
for every
$x,n,s$
, where
$\mathbb {Q}_{\geq 0}$
denotes the set of all nonnegative rationals. If, moreover, we have
$r_{0}\geq _{M}x$
, then we say that
$(r_{n})_{n\in \mathbb {N}}$
is
$\omega $
-left-CEA over
$x\in {\mathbb {N}^{\mathbb {N}}}$
.
Whenever
$r_{n}\in [0,1]$
for all
$n\in \mathbb {N}$
, such a computable function
$\Psi $
generates an operator
$J_{\Psi }^{\omega }:{\mathbb {N}^{\mathbb {N}}}\to [0,1]^{\mathbb {N}}$
with
$J_{\Psi }^{\omega }(x)=(x,r_{0},r_{1},\dots )$
, which is called an
$\omega $
-left-CEA operator. An
$\omega $
-left-CEA operator
$J^{\omega }$
is universal if for any
$\omega $
-left-CEA operator J, there is
$e\in \mathbb {N}$
such that
$J^{\omega }(\langle e,x\rangle )=J(x)$
.
Proposition 4.2. A universal
$\omega $
-left-CEA operator exists.
Proof. We first give an effective enumeration
$(J^{\omega }_{e})_{e\in \mathbb {N}}$
of all
$\omega $
-left-CEA operators. It is not hard to see that
$y\in [0,1]$
is left-c.e. in
$x\in {\mathbb {N}^{\mathbb {N}}}\times [0,1]^{k}$
if and only if there is a c.e. set
$W\subseteq \mathbb {N}\times \mathbb {Q}$
such that
$$ \begin{align*}y=J^{k}_{W}(x):=\sup\{\min\{|p|,1\}:x\in B^{k}_{i}\mbox{ for some }(i,p)\in W\},\end{align*} $$
where
$B_{i}^{k}$
is the ith rational open ball in
${\mathbb {N}^{\mathbb {N}}}\times [0,1]^{k}$
. Thus, we have an effective enumeration of all left-c.e. operators
$J:{\mathbb {N}^{\mathbb {N}}}\times [0,1]^{k}\rightarrow [0,1]$
by putting
$J^{k}_{e}=J^{k}_{W_{e}}$
, where
$W_{e}$
is the eth c.e. subset of
$\mathbb {N}\times \mathbb {Q}$
. Then, we define
$$ \begin{align*}J^{\omega}_{e}(x)=(x,J^{0}_{\langle e,0\rangle}(x),J^{1}_{\langle e,1\rangle}(x,J^{0}_{\langle e,0\rangle}(x)),\dots);\end{align*} $$
that is,
$J^{\omega }_{e}$
is the
$\omega $
-left-CEA operator generated by the uniform sequence
$(J^{k}_{\langle e,k\rangle })_{k\in \mathbb {N}}$
of left-c.e. operators. Clearly,
$(J^{\omega }_{e})_{e\in \mathbb {N}}$
is an effective enumeration of all
$\omega $
-left-CEA operators. Then, define
$J^{\omega }(\langle e,x\rangle )=J^{\omega }_{e}(x)$
. It is not hard to check that
$J^{\omega }$
is a universal
$\omega $
-left-CEA operator.
Definition 4.3. The
$\omega $
-left-computably enumerable in-and-above space
$\omega \mathbf {CEA}$
is a subspace of
$\mathbb {N}\times {\{0, 1\}^{\mathbb {N}}}\times [0,1]^{\mathbb {N}}$
defined by
$$ \begin{align*} \mathbf{\omega CEA}&=\{(e,x,r)\in\mathbb{N}\times {\mathbb{N}^{\mathbb{N}}}\times[0,1]^{\mathbb{N}}:J^{\omega}_{e}(x)=(x,r)\}\\ &\simeq\mbox{`the graph of a universal }\omega\mbox{-left-CEA operator'}. \end{align*} $$
Note that in classical recursion theory, an operator
$\Psi $
is called a CEA-operator (also known as an REA-operator, a pseudojump, or a hop) if there is a c.e. procedure W such that
$\Psi (A)=\langle {A,W(A)\rangle }$
for any
$A\subseteq \mathbb {N}$
(see Odifreddi [Reference Odifreddi42, Chapters XII and XIII]). An
$\omega $
-CEA operator (also called an
$\omega $
-hop) is the
$\omega $
th iteration of a uniform sequence of CEA-operators. In general, computability theorists have studied
$\alpha $
-CEA operators for computable ordinals
$\alpha $
in the theory of
$\Pi ^{0}_{2}$
singletons. We will also use a generalisation of the notion of a
$\Pi ^{0}_{2}$
singleton in Section 5.
We say that a continuous degree is
$\omega $
-left-CEA if it contains a point
$r\in [0,1]^{\mathbb {N}}$
which is
$\omega $
-left-CEA over an oracle
$z\in {\{0, 1\}^{\mathbb {N}}}$
. The point degree spectrum of the space
$\mathbf {\omega CEA}$
(as a subspace of
$[0,1]^{\mathbb {N}}$
) can be described as follows:
$$ \begin{align*}\mathrm{Spec}(\mathbf{\omega CEA})=\{\mathbf{a}\in\mathcal{D}_{r}:\mathbf{a}\mbox{ is }\omega\mbox{-left-CEA}\}.\end{align*} $$
This is because
$J^{\omega }_{e}(x)$
is always
$\omega $
-left-CEA over x and, conversely, if r is
$\omega $
-left-CEA over x, then by universality of
$J^{\omega }$
(Proposition 4.2) there is e such that
$J_{e}^{\omega }(x)=(x,r)$
, which is equivalent to r as
$x\leq _{\mathrm {T}} r$
. Clearly,
$$ \begin{align*}\mathrm{Spec}({{\{0, 1\}^{\mathbb{N}}}})\subseteq\mathrm{Spec}({\mathbf{\omega CEA}})\subseteq\mathrm{Spec}({[0,1]^{\mathbb{N}}}).\end{align*} $$
The following is an analog of the well-known fact from classical computability theory that every
$\omega $
-CEA set is a
$\Pi ^{0}_{2}$
-singleton (see Odifreddi [Reference Odifreddi42, Proposition XIII.2.7]).
Lemma 4.4. The
$\omega $
-left-CEA space
$\mathbf {\omega CEA}$
is Polish.
Proof. It suffices to show that
$\mathbf {\omega CEA}$
is
$\Pi ^{0}_{2}$
(hence
$G_{\delta }$
) in
${\mathbb {N}^{\mathbb {N}}}\times [0,1]^{\mathbb {N}}$
since a
$G_{\delta }$
subset of a Polish space is Polish. The stage s approximation to
$J_{e}^{k}$
is denoted by
$J_{e,s}^{k}$
; that is,
$J_{e,s}^{k}(z)=\max \{\min \{|p|,1\}:(\exists \langle i,p\rangle \in W_{e,s})\;z\in B_{i}^{k}\}$
, where
$W_{e,s}$
is the stage s approximation to the eth computably enumerable set
$W_{e}$
. Note that the function
$(e,s,k,z)\mapsto J_{e,s}^{k}(z)$
is computable. We can easily see that
$(e,x,r)\in \mathbf {\omega CEA}$
if and only if
$$ \begin{align*}(\forall n,k\in\mathbb{N})(\exists s>n)\;d\ \left(\pi_{k}(r),J^{k}_{e,s}(x,\pi_{0}(r),\pi_{1}(r),\dots,\pi_{k-1}(r))\right)<2^{-n},\end{align*} $$
where d is the Euclidean metric on
$[0,1]$
and
$\pi _{i}$
is the ith projection (i.e.,
$\pi _{i}(r)=r_{i}$
for
$r=(r_{j})_{j\in \mathbb {N}}$
). The above formula is clearly
$\Pi ^{0}_{2}$
.
We devote the rest of this section to a proof of the following theorem.
Theorem 4.5. The space
$\mathbf {\omega CEA}$
has an intermediate
$\sigma $
-homeomorphism type; that is,
$$ \begin{align*}{\{0, 1\}^{\mathbb{N}}} <_{\sigma}^{\mathfrak{T}} \mathbf{\omega CEA} <_{\sigma}^{\mathfrak{T}} [0,1]^{\mathbb{N}}.\end{align*} $$
Consequently, the space
$\mathbf {\omega CEA}$
is a concrete counterexample to Problem 1.3.
4.3 Proof of Theorem 4.5
The key idea is to measure how similar the space
$\mathbf {X}$
is to a zero-dimensional space by approximating each point in a space
$\mathbf {X}$
by a zero-dimensional space. Recall from (the proof of) Observation 3.3 that, for points in represented spaces which computably embed into
$\mathcal {O}(\mathbb {N})$
, there is a one-to-one correspondence between the point-Turing degree
$\deg (x)=[x]_{\equiv _{M}}$
and the spectrum
$\mathrm{Spec}(x)$
. Via this correspondence, the point-Turing degree
$\deg (x)$
of a point
$x\in \mathbf {X}$
can be identified with its Turing upper cone; that is,
$$ \begin{align*}\deg(x)\approx\mathrm{Spec}(x)=\{z\in {\{0, 1\}^{\mathbb{N}}}:x\leq_{\mathrm{T}} z\}.\end{align*} $$
We think of the spectrum
$\mathrm{Spec}(x)$
as the upper approximation of
$x\in \mathbf {X}$
by the zero-dimensional space
${\{0, 1\}^{\mathbb {N}}}$
. Now, we need the notion of the lower approximation of
$x\in \mathbf {X}$
by the zero-dimensional space
${\{0, 1\}^{\mathbb {N}}}$
. We introduce the co-spectrum of a point
$x\in \mathbf {X}$
as its Turing lower cone
$$ \begin{align*}\mathrm{coSpec}(x)=\{z\in {\{0, 1\}^{\mathbb{N}}}:z\leq_{\mathrm{T}} x\},\end{align*} $$
and, moreover, we define the degree co-spectrum of a represented space
$\mathbf {X}$
as follows:
$$ \begin{align*}\mathrm{coSpec}(\mathbf{X})=\{\mathrm{coSpec}(x):x\in\mathbf{X}\}.\end{align*} $$
As we will see below, the degree spectrum of a represented space fully determines its co-spectrum, while the converse is not true. For every oracle
$p\in {\{0, 1\}^{\mathbb {N}}}$
, we may also introduce relativised co-spectra
$\mathrm{coSpec}^{p}(x)=\{z\in {\{0, 1\}^{\mathbb {N}}}:z\leq _{\mathrm {T}}(x,p)\}$
and the relativised degree co-spectra
$\mathrm{coSpec}^{p}(\mathbf {X})$
in the same manner.
Observation 4.6. Let
$\mathbf {X}$
and
$\mathbf {Y}$
be admissibly represented spaces. If
$\mathrm{Spec}^{p}(\mathbf {X})\subseteq \mathrm{Spec}^{p}(\mathbf {Y})$
, then we also have
$\mathrm{coSpec}^{p}(\mathbf {X})\subseteq \mathrm{coSpec}^{p}(\mathbf {Y})$
.
Therefore, by Theorem 3.4, the cospectrum of an admissibly represented space up to an oracle is invariant under
$\sigma $
-homeomorphism. Indeed, by relativising Lemma 3.5, one can see that
$\mathbf {X}\leq _{\sigma }^{\mathfrak {T}}\mathbf {Y}$
implies
$\mathrm{coSpec}^{p}(\mathbf {X})\subseteq \mathrm{coSpec}^{p}(\mathbf {Y})$
for some p.
Proof. Clearly,
$[x^{\mathbf {X}}]_{\equiv _{\mathrm {T}}}=[y^{\mathbf {Y}}]_{\equiv _{\mathrm {T}}}$
implies that
$\{z\in {\{0, 1\}^{\mathbb {N}}}:z\leq _{\mathrm {T}} x^{\mathbf {X}}\}=\{z\in {\{0, 1\}^{\mathbb {N}}}:z\leq _{\mathrm {T}} y^{\mathbf {Y}}\}$
. This observation can be relativised to any oracle p. This verifies the first assertion.
We say that a collection
$\mathcal {I}$
of subsets of
$\mathbb {N}$
is realised as the co-spectrum of x if
$\mathrm{coSpec}(x)=\mathcal {I}$
. A countable set
$\mathcal {I}\subseteq \mathcal {P}(\mathbb {N})$
is a Scott ideal if it is the standard system of a countable nonstandard model of Peano arithmetic or, equivalently, a countable
$\omega $
-model of the theory
${\sf WKL}_{0}$
. We will not go into the details of a Scott ideal (see Miller [Reference Miller37, Section 9] for a more explicit definition); we will only use the fact that every jump ideal is a Scott ideal. Here, a jump ideal
$\mathcal {I}$
is a collection of subsets of natural numbers which is closed under the join
$\oplus $
, downward Turing reducibility
$\leq _{\mathrm {T}}$
and the Turing jump; that is,
$p,q\in \mathcal {I}$
implies
$p\oplus q\in \mathcal {I}$
;
$p\leq _{\mathrm {T}} q\in \mathcal {I}$
implies
$p\in \mathcal {I}$
; and
$p\in \mathcal {I}$
implies
$p^{\prime }\in \mathcal {I}$
. Miller [Reference Miller37, Theorem 9.3] showed that every countable Scott ideal (hence, every countable jump ideal) is realised as a co-spectrum in
$[0,1]^{\mathbb {N}}$
.
Example 4.7. The spectra and co-spectra of Cantor space
${\{0, 1\}^{\mathbb {N}}}$
, the space
$\omega \mathrm{CEA}$
and the Hilbert cube
$[0,1]^{\mathbb {N}}$
are illustrated as follows (see also Figure 1):
-
1. The co-spectrum
$\mathrm{coSpec}(x)$
of any point
$x\in {\{0, 1\}^{\mathbb {N}}}$
is principal and meets with
$\mathrm{ Spec}(x)$
exactly at
$\deg _{T}(x)$
. The same is true up to some oracle for an arbitrary Polish spaces
$\mathbf {X}$
such that
$\mathbf {X}\cong _{\sigma }^{\mathfrak {T}}{\{0, 1\}^{\mathbb {N}}}$
. -
2. For any point
$z\in \omega \mathbf {CEA}$
, the ‘distance’ between
$\mathrm{Spec}(z)$
and
$\mathrm{coSpec}(z)$
has to be at most the
$\omega $
th Turing jump (see the proof of Theorem 4.5 below). -
3. (Miller [Reference Miller37, Theorem 9.3]) An arbitrary countable Scott ideal is realised as
$\mathrm{coSpec}(y)$
of some point
$y\in [0,1]^{\mathbb {N}}$
. Hence,
$\mathrm{Spec}(y)$
and
$\mathrm{coSpec}(y)$
can be separated by an arbitrary distance. (Consider countable Scott ideals closed under the
$\alpha $
th Turing jump, the hyperjump, the
$\Delta ^{1}_{n}$
-jump, etc.)
The upper and lower approximations of
${\{0, 1\}^{\mathbb {N}}}$
,
$\omega \mathbf {CEA}$
and
$[0,1]^{\mathbb {N}}$
This upper/lower approximation method clarifies the differences of
$\sigma $
-homeomorphism types of spaces because both relativised point-degree spectra and co-spectra are invariant under
$\sigma $
-homeomorphism by Theorem 3.4 and Observation 4.6.
Proof of Theorem 4.5
We first show that
$\omega \mathbf {CEA}<_{\sigma }^{\mathfrak {T}}[0,1]^{\mathbb {N}}$
. This follows from the following claim: For any oracle
$p\in {\{0, 1\}^{\mathbb {N}}}$
, there is a countable Scott ideal which cannot be realised as a p-co-spectrum of an
$\omega $
-left-CEA continuous degree.
To see this, let
$y=(e,x,r)\in \omega \mathbf {CEA}$
be an arbitrary point. Clearly,
$x\leq _{\mathrm {T}}(e,x,r)$
, and this means that
$x\in \mathrm{coSpec}(y)$
since
$x\in {\{0, 1\}^{\mathbb {N}}}$
. However, as
$r=(r_{n})_{n\in \mathbb {N}}$
is
$\omega $
-left-CEA in x, we know that
$r_{0}$
is c.e. in x (so computable in the Turing jump of x) and
$r_{n+1}$
is c.e. in
$(x,r_{0},\dots ,r_{n})$
. By induction, this implies that
$r_{n}$
is computable in the
$(n+1)$
th jump of x uniformly in n and, therefore, r is computable in the
$\omega $
th jump of x; hence,
$y=(e,x,r)\leq _{\mathrm {T}} x^{(\omega )}$
; that is,
$x^{(\omega )}\in \mathrm{Spec}(y)$
. In particular,
$\mathrm{coSpec}(y)$
does not contain the
$(\omega +1)$
-st Turing jump of the second entry x of given any
$y\in \omega \mathbf {CEA}$
. Thus, for any oracle p, the jump ideal
$\mathcal {A}^{p}=\{x\in {\{0, 1\}^{\mathbb {N}}}:(\exists n\in \mathbb {N})\;x\leq _{\mathrm {T}} p^{(\omega \cdot n)}\}$
cannot be realised as a co-spectrum in
$\omega \mathbf {CEA}$
. This verifies the claim.
By the above claim and Miller’s result on Scott ideals mentioned in Example 4.7 (3), we have
$\mathrm{coSpec}^{p}(\omega \mathbf {CEA})\subsetneq \mathrm{coSpec}^{p}([0,1]^{\mathbb {N}})$
for any oracle p. Therefore, by Theorem 3.4 and Observation 4.6, we conclude that the
$\omega $
-left-CEA space is not
$\sigma $
-homeomorphic to the Hilbert cube; that is,
$\omega \mathbf {CEA}<_{\sigma }^{\mathfrak {T}}[0,1]^{\mathbb {N}}$
.
We next show
${\{0, 1\}^{\mathbb {N}}}<_{\sigma }^{\mathfrak {T}}\mathbf {\omega CEA}$
. In other words, we have to show that the
$\omega $
-left-CEA space is not countable-dimensional. For a compact set
$P\subseteq [0,1]^{\mathbb {N}}$
, we inductively define
$\min P\in P$
as follows:
$$ \begin{align*}\pi_{n}(\min P)=\min\pi_{n}[\{z\in P:(\forall i<n)\;\pi_{i}(z)=\pi_{i}(\min P)\}],\end{align*} $$
where
$\pi _{n}:[0,1]^{\mathbb {N}}\to [0,1]$
is the projection onto the nth coordinate. We call the point
$\min P$
the leftmost point of P. Kreisel’s basis theorem (see [Reference Odifreddi41, Proposition V.5.31]) in classical computability theory says that the leftmost element of a
$\Pi ^{0}_{1}$
subset of
${\{0, 1\}^{\mathbb {N}}}$
or
$[0,1]$
is always left-c.e. We consider the following infinite-dimensional version of Kreisel’s basis theorem: For any oracle
$p\in {\{0, 1\}^{\mathbb {N}}}$
, the leftmost point of a
$\Pi ^{0}_{1}(p)$
subset of
$[0,1]^{\mathbb {N}}$
is
$\omega $
-left-CEA in p.
To see this, one can easily check that the Hilbert cube
$[0,1]^{\mathbb {N}}$
is computably compact in the sense that there is a computable enumeration of all finite collections
$\mathcal {D}$
of basic open sets which covers the whole space; that is,
$\bigcup \mathcal {D}=[0,1]^{\mathbb {N}}$
. In particular, given a
$\Pi ^{0}_{1}$
set
$P\subseteq [0,1]^{\mathbb {N}}$
, the predicate
$P=\emptyset $
is
$\Sigma ^{0}_{1}$
uniformly in a
$\Pi ^{0}_{1}$
code of P.
Fix a
$\Pi ^{0}_{1}(p)$
set
$P\subseteq [0,1]^{\mathbb {N}}$
. It suffices to show that
$\pi _{n+1}(\min P)$
is left-c.e. in
$\langle \pi _{i}(\min P)\rangle _{i\leq n}$
uniformly in n relative to p. Given a finite sequence
$\mathbf {a}=(a_{0},a_{1},\dots ,a_{n})$
of reals and a real q, we denote by
$C(\mathbf {a},q)$
the set of all points in P of the form
$(a_{0},a_{1},\dots ,a_{n},r,\dots )$
for some
$r\leq q$
; that is,
$$ \begin{align*}C(\mathbf{a},q)=P\cap \bigcap_{i\leq n}\pi_{i}^{-1}\{a_{i}\}\cap\pi_{n+1}^{-1}[0,q].\end{align*} $$
It is easy to check that
$C(\mathbf {a},q)$
is a
$\Pi ^{0}_{1}$
subspace of
$[0,1]$
relative to
$\mathbf {a}$
and q. By computable compactness of the Hilbert cube, one can see that
$C^{*}(\mathbf {a}):=\{q\in [0,1]:C(\mathbf {a},q)=\emptyset \}$
is p-c.e. open uniformly relative to
$\mathbf {a}$
(since
$C(\mathbf {a},q)=\emptyset $
is
$\Sigma ^{0}_{1}$
uniformly relative to
$\mathbf {a}$
and q). Therefore,
$\sup C^{*}(\mathbf {a})$
is p-left-c.e. uniformly relative to
$\mathbf {a}$
. Finally, we claim that
$\pi _{n+1}(\min P)$
is exactly
$\sup C^{*}(\langle \pi _{i}(\min P)\rangle _{i\leq n})$
. By definition,
$\pi _{n+1}(\min P)$
is the least
$q\in [0,1]$
such that there exists
$(r_{m})_{m\geq n+2}$
such that
$(\pi _{0}(\min P),\dots ,\pi _{n}(\min P),q,r_{n+2},r_{n+3},\dots )\in P$
. This is equal to the least
$q\in [0,1]$
such that
$C(\langle \pi _{i}(\min P)\rangle _{i\leq n},q)$
is nonempty. This is exactly the same as
$\sup C^{*}(\langle \pi _{i}(\min P)\rangle _{i\leq n})$
.
We use the following relativised versions of Miller’s lemmas.
Lemma 4.8 (Miller [Reference Miller37, Lemma 6.2])
For every
$p\in {\{0, 1\}^{\mathbb {N}}}$
, there is a multivalued function
$\Psi ^{p}:[0,1]^{\mathbb {N}}\rightrightarrows [0,1]^{\mathbb {N}}$
with a
$\Pi ^{0}_{1}(p)$
graph and nonempty, convex images such that, for all
$e\in \mathbb {N}$
,
$\alpha \in [0,1]^{\mathbb {N}}$
and
$\beta \in \Psi ^{p}(\alpha )$
, if for every name
$\lambda $
of
$\alpha $
,
$\varphi _{e}^{\lambda \oplus p}$
is a name of
$x\in [0,1]$
, then
$\beta (e)=x$
.
Note that Kakutani’s fixed point theorem ensures the existence of a fixed point of
$\Psi ^{p}$
. If
$\alpha $
is a fixed point of
$\Psi ^{p}$
– that is –
$\alpha \in \Psi ^{p}(\alpha )$
, then
$\mathrm{coSpec}^{p}(\alpha )=\{\alpha (n):n\in \mathbb {N}\}$
(to be more precise,
$\mathrm{coSpec}^{p}(\alpha )$
is the set of all binary expansions of reals in
$\{\alpha (n):n\in \mathbb {N}\}$
or, equivalently,
$\mathrm{coSpec}^{p}(\alpha )=\{\alpha (n):n\in \mathbb {N}\}\cap {\{0, 1\}^{\mathbb {N}}}$
when
${\{0, 1\}^{\mathbb {N}}}$
is regarded as the canonical Cantor set in
$[0,1]$
). Therefore, such an
$\alpha $
has no Turing degree relative to p (see [Reference Miller37, Proposition 5.3]).
Lemma 4.9 (Miller [Reference Miller37, Lemma 9.2])
For every
$p\in {\{0, 1\}^{\mathbb {N}}}$
, there is an index
$e\in \mathbb {N}$
such that for any
$x\in [0,1]$
, there is a fixed point
$\alpha $
of
$\Psi ^{p}$
such that
$\alpha (e)=x$
.
We show the following: For any oracle
$p\in {\{0, 1\}^{\mathbb {N}}}$
, there is an
$\omega $
-left-CEA continuous degree which is not contained in
$\mathrm{Spec}^{p}({\{0, 1\}^{\mathbb {N}}})$
.
Let
$\mathrm{Fix}(\Psi ^{p})$
be the set of all fixed points of
$\Psi ^{p}$
. Then,
$\mathrm{Fix}(\Psi ^{p})$
is
$\Pi ^{0}_{1}(p)$
since it is the intersection of the graph of
$\Psi ^{p}$
(which is a
$\Pi ^{0}_{1}(p)$
set) and the diagonal set. Let e be an index as in Lemma 4.9. Clearly,
$A=\{\alpha \in \mathrm{Fix}(\Psi ^{p}):\alpha (e)=p\}$
is again a
$\Pi ^{0}_{1}(p)$
subset of
$[0,1]^{\mathbb {N}}$
and A is nonempty by Lemma 4.9. Given
$\alpha \in [0,1]^{\mathbb {N}}$
, define
$\alpha ^{\ast }$
as the result of swapping the values of the
$0$
th and eth entries of
$\alpha $
; that is,
$\alpha ^{\ast }(0)=\alpha (e)$
,
$\alpha ^{\ast }(e)=\alpha (0)$
and
$\alpha ^{\ast }(n)=\alpha (n)$
for
$n\not \in \{0,e\}$
. It is clear that
$\alpha \mapsto \alpha ^{\ast }$
is a computable homeomorphism. Thus,
$A^{\ast }=\{\alpha \in [0,1]:\alpha ^{\ast }\in A\}$
is computably homeomorphic to A; hence,
$A^{\ast }$
is also a nonempty
$\Pi ^{0}_{1}(p)$
set. By our infinite-dimensional version of Kreisel’s basis theorem,
$A^{\ast }$
contains an element
$\alpha $
which is
$\omega $
-left-CEA in p. Indeed,
$\alpha $
is
$\omega $
-left-CEA over p since
$\alpha (0)=\alpha ^{\ast }(e)=p$
. By the property of an element of
$A\subseteq \mathrm{Fix}(\Psi ^{p})$
discussed above,
$\alpha ^{\ast }\in A$
has no Turing degree relative to p. Moreover, since moving the eth entry of
$\alpha $
to the first entry does not affect the degree, the degree of
$\alpha $
is equal to that of
$\alpha ^{\ast }$
. Hence,
$\alpha $
has a
$\omega $
-left-CEA continuous degree but has no Turing degree relative to p.
By this claim,
$\mathrm{Spec}^{p}({\{0, 1\}^{\mathbb {N}}})\subsetneq \mathrm{Spec}^{p}(\omega \mathbf {CEA})$
for any oracle p. Again by Theorem 3.5 and Observation 4.6, we conclude
${\{0, 1\}^{\mathbb {N}}}<_{\sigma }^{\mathfrak {T}}\omega \mathbf {CEA}$
.
5 Structure of
$\sigma $
-Homeomorphism Types
In this section, we will show that there are continuum many
$\sigma $
-homeomorphism types of compact metrisable spaces.
Theorem 5.1. There exists a collection
$(\mathbf {X}_{\alpha })_{\alpha <2^{\aleph _{0}}}$
of continuum many compact metric spaces such that if
$\alpha \not =\beta $
,
$\mathbf {X}_{\alpha }$
cannot be
$\sigma $
-embedded into
$\mathbf {X}_{\beta }$
.
We devote the rest of this section to prove Theorem 5.1. Actually, we will show the following:
There is an embedding of the inclusion ordering
$([\omega _{1}]^{\leq \omega },\subseteq )$
of countable subsets of the smallest uncountable ordinal
$\omega _{1}$
into the
$\sigma $
-embeddability ordering of compact metric spaces.
As a corollary, there are an uncountable chain and a continuum antichain of
$\sigma $
-homeomorphism types of compact metric spaces.
5.1 Almost Arithmetical Degrees
In Section 4, we used the co-spectrum as a
$\sigma $
-topological invariant. More explicitly, in our proof, it was essential to examine closure properties of co-spectra to obtain an intermediate
$\sigma $
-homeomorphism type of Polish spaces. In this section, we will develop a method for controlling closure properties of co-spectra. As a result, we will construct a compact metrisable space whose co-spectra realise a given well-behaved family of ‘almost’ arithmetical degrees.
First, we introduce a notion which estimates the strength of closure properties of functions up to the arithmetical equivalence.
Definition 5.2. Let g and h be total Borel measurable functions from
${\{0, 1\}^{\mathbb {N}}}$
into
${\{0, 1\}^{\mathbb {N}}}$
.
-
1. We inductively define
$g^{0}(x)=x$
and
$g^{n+1}(x)=g^{n}(x)\oplus g(g^{n}(x))$
. -
2. For every oracle
$r\in {\{0, 1\}^{\mathbb {N}}}$
, consider the following jump ideal defined as where
$$ \begin{align*}\mathcal{J}_{a}(g,r)=\{z\in {\{0, 1\}^{\mathbb{N}}}:(\exists n\in\mathbb{N})\;z\leq_{a}g^{n}(r)\},\end{align*} $$
$\leq _{a}$
denotes the arithmetical reducibility; that is,
$p\leq _{a}q$
is defined by
$p\leq _{\mathrm {T}} q^{(m)}$
for some
$m\in \mathbb {N}$
(see Odifreddi [Reference Odifreddi42, Section XII.2 and Chapter XIII]).
-
3. A function g is almost arithmetical reducible to a function h (written as
$g\leq _{aa}h$
) if for any
$r\in {\{0, 1\}^{\mathbb {N}}}$
there is
$x\in {\{0, 1\}^{\mathbb {N}}}$
with
$x\geq _{T}r$
such that
$$ \begin{align*}\mathcal{J}_{a}(g,x)\subseteq\mathcal{J}_{a}(h,x).\end{align*} $$
-
4. Let
$\mathcal {G}$
and
$\mathcal {H}$
be countable sets of total functions. We say that
$\mathcal {G}$
is
$aa$
-included in
$\mathcal {H}$
(written as
$\mathcal {G}\subseteq _{aa}\mathcal {H}$
) if for all
$g\in \mathcal {G}$
, there is
$h\in \mathcal {H}$
such that
$g\equiv _{aa}h$
(i.e.,
$g\leq _{aa}h$
and
$h\leq _{aa}g$
).
A function
$g:{\{0, 1\}^{\mathbb {N}}}\to {\{0, 1\}^{\mathbb {N}}}$
is said to be monotone if
$x\leq _{\mathrm {T}} y$
implies
$g(x)\leq _{\mathrm {T}} g(y)$
.
Remark 5.3. Although it will not be used later, one can show that
$\leq _{aa}$
is transitive on monotone Borel measurable functions using Borel determinacy: First note that the condition
$\mathcal {J}_{a}(g,x)\subseteq \mathcal {J}_{a}(h,x)$
is equivalent to saying that for any i there is j such that
$g^{i}(x)\leq _{a} h^{j}(x)$
. Thus, this is a Borel property. Given Borel measurable functions g and h, consider the following game: Player I plays r (bit by bit), Player II responds with x and Player II wins this game if
$x\geq _{T} r$
and
$\mathcal {J}_{a}(g,x)\subseteq \mathcal {J}_{a}(h,x)$
. If
$g\leq _{aa}h$
, then Player I cannot have a winning strategy, so by Borel determinacy, II has a winning strategy
$\alpha $
. This strategy yields an
$\alpha $
-computable transformation
$r\mapsto x$
, which implies
$x\leq _{\mathrm {T}} r\oplus \alpha $
. In particular, if
$r\geq _{T}\alpha $
, then there is
$x\equiv _{\mathrm {T}} r$
such that
$\mathcal {J}_{a}(g,x)\subseteq \mathcal {J}_{a}(h,x)$
. By monotonicity of g, if
$z\equiv _{\mathrm {T}} x$
, then
$\mathcal {J}_{a}(g,x)=\mathcal {J}_{a}(g,z)$
and the same property holds for h. Thus, using monotonicity of g and h, for any
$x\geq _{T}\alpha $
we get
$\mathcal {J}_{a}(g,x)\subseteq \mathcal {J}_{a}(h,x)$
. Using this characterisation, it is now easy to show that
$\leq _{aa}$
is transitive.
An oracle
$\mathbf {\Pi }^{0}_{2}$
-singleton is a total function
$g:{\{0, 1\}^{\mathbb {N}}}\to {\{0, 1\}^{\mathbb {N}}}$
whose graph is
$G_{\delta }$
. Clearly, every oracle
$\mathbf {\Pi }^{0}_{2}$
-singleton is Borel measurable, whereas there is no upper bound of Borel ranks of oracle
$\mathbf {\Pi }^{0}_{2}$
-singletons. For instance, if
$\alpha $
is a computable ordinal, then the
$\alpha $
th Turing jump
$j_{\alpha }(x)=x^{(\alpha )}$
is a monotone oracle
$\mathbf {\Pi }^{0}_{2}$
-singleton for every computable ordinal
$\alpha $
(see Odifreddi [Reference Odifreddi42, Proposition XII.2.19], Sacks [Reference Sacks58, Corollary II.4.3] and Chong-Yu [Reference Chong, Yu and Sacks9, Theorem 2.1.4]). The following is the key lemma in our proof, which will be proved in Subsection 5.2.
Lemma 5.4 (Realisation Lemma)
There is a map
$\mathbf {Rea}$
transforming each countable set of monotone oracle
$\mathbf {\Pi }^{0}_{2}$
-singletons into a Polish space such that
$$ \begin{align*}\mathbf{Rea}(\mathcal{G})\leq^{\mathfrak{T}}_{\sigma}\mathbf{Rea}(\mathcal{H})\;\Longrightarrow\;\mathcal{G}\subseteq_{aa}\mathcal{H}.\end{align*} $$
5.2 Construction
We construct a Polish space whose co-spectrum codes almost arithmetical degrees contained in a given countable set
$\mathcal {G}$
of oracle
$\mathbf {\Pi }^{0}_{2}$
-singletons. For notational simplicity, given
$x\in [0,1]^{\mathbb {N}}$
, we write
$x_{n}$
for the nth coordinate of x and, moreover,
$x_{<n}$
and
$x_{\leq n}$
for
$(x_{i})_{i<n}$
and
$(x_{i})_{i\leq n}$
, respectively. We also consider a sequence like
$(r,x_{<i},x_{\ell })$
and, in this case, for sake of simplicity, we assume that any name of
$(r,x_{<i},x_{\ell })$
codes information for i and
$\ell $
.
Our idea comes from the construction by Miller [Reference Miller37, Lemma 9.2]. Our purpose is constructing a Polish space such that given
$g\in \mathcal {G}$
and oracle r the space has a point
$x=(x_{i})_{i\in \mathbb {N}}$
whose co-spectrum is not very different from
$\mathcal {J}_{a}(g,r)$
. Then, at least, such a point should compute
$g^{i}(r)$
for all
$i\in \mathbb {N}$
. We can achieve this by requiring
$x_{i}=g^{i}(r)$
for infinitely many
$i\in \mathbb {N}$
; however, we need to control the co-spectrum simultaneously and, therefore, we have to choose such coding locations i very carefully. The actual construction is that, from r and
$x_{<v}$
, we will find a finite set
$(\ell (u))_{u\leq v}$
of candidates of safe coding locations and then we define
$x_{\ell (u)}=g^{\ell (u)}(r)$
at a genuine safe coding location
$\ell (u)$
. Then, for each i with
$v\leq i<\ell (u)$
, we define
$x_{i}$
from
$(r,x_{<i},x_{\ell (u)})$
in a left-c.e. manner. This idea yields the following definition.
Definition 5.5. Let
$\mathcal {G}=(g_{n})_{n\in \mathbb {N}}$
be a countable collection of oracle
$\mathbf {\Pi }^{0}_{2}$
-singletons. The space
$\mathbf {\omega CEA}(\mathcal {G})$
consists of
$(n,d,e,r,x)\in \mathbb {N}^{3}\times {\{0, 1\}^{\mathbb {N}}}\times [0,1]^{\mathbb {N}}$
such that for every i,
-
1. either
$x_{i}=g_{n}^{i}(r)$
or -
2. there are
$u\leq v\leq i$
such that
$x_{i}\in [0,1]$
is the eth left-c.e. real relative to
$\langle r,x_{<i},x_{\ell (u)}\rangle $
and
$x_{\ell (u)}=g_{n}^{\ell (u)}(r)$
, where
$\ell (u)=\Phi _{d}(u,r,x_{<v})\geq i$
(recall that
$\Phi _{d}$
is the dth partial computable function).
Moreover, for a set
$P\subseteq {\{0, 1\}^{\mathbb {N}}}\times [0,1]^{\mathbb {N}}$
, define
$\mathbf {\omega CEA}(\mathcal {G},P)$
to be the set of all points
$(n,d,e,r,x)\in \mathbf {\omega CEA}(\mathcal {G})$
with
$(r,x)\in P$
.
Lemma 5.6. Suppose that
$\mathcal {G}$
is a countable collection of oracle
$\mathbf {\Pi }^{0}_{2}$
-singletons and P is a
$\mathbf {\Pi }^{0}_{2}$
subset of
$\{0,1\}^{\mathbb {N}}\times [0,1]^{\mathbb {N}}$
. Then,
$\mathbf {\omega CEA}(\mathcal {G},P)$
is Polish.
Proof. It suffices to show that
$\mathbf {\omega CEA}(\mathcal {G})$
is
$\mathbf {\Pi }^{0}_{2}$
. The condition (1) in Definition 5.5 is clearly
$\mathbf {\Pi }^{0}_{2}$
. Let
$\forall a\exists b>a\;G(a,b,n,\ell ,r,x)$
be a
$\mathbf {\Pi }^{0}_{2}$
condition representing
$x=g_{n}^{\ell }(r)$
, where G is open and let
$\ell (u)[s]$
be the stage s approximation of
$\Phi _{d}(u,r,x_{<v})$
. The condition (2) is equivalent to the statement that there are
$u\leq v\leq i$
such that
$$ \begin{align*} (\forall t\in\mathbb{N})(\exists s>t)\;&\ell(u)[s]\downarrow\geq i,\;d(x_{i},J_{e,s}^{i+1}(r,x_{<i},x_{\ell(u)[s]}))<2^{-t},\\ &\mbox{ and }G(t,s,n,\ell(u)[s],r,x_{\ell(u)[s]}). \end{align*} $$
Clearly, this condition is
$\mathbf {\Pi }^{0}_{2}$
.
Remark 5.7. The space
$\mathbf {\omega CEA}(\mathcal {G})$
is totally disconnected for any countable set
$\mathcal {G}$
of oracle
$\mathbf {\Pi }^{0}_{2}$
singletons, since for any fixed
$(n,d,e,r)\in \mathbb {N}^{3}\times {\{0, 1\}^{\mathbb {N}}}$
, its extensions form a finite-branching infinite tree
$T\subseteq [0,1]^{<\omega }$
.
Recall from Lemma 4.8 that Miller [Reference Miller37, Lemma 6.2] constructed a
$\Pi ^{0}_{1}$
set
$\mathrm{Fix}(\Psi )\subseteq [0,1]^{\mathbb {N}}=[0,1]\times [0,1]^{\mathbb {N}}$
such that
$\mathrm{coSpec}(x)=\{x_{i}:i\in \mathbb {N}\}$
for every
$x=(x_{i})_{i\in \mathbb {N}}\in \mathrm{Fix}(\Psi )$
. By Lemma 4.9, without loss of generality, we may assume that
$\mathrm{Fix}(\Psi )\cap \pi _{0}^{-1}\{r\}\not =\emptyset $
for every
$r\in [0,1]$
. Define
$\mathrm{Fix}^{\ast }(\Psi )=\mathrm{Fix}(\Psi )\cap \pi _{0}^{-1}[{\{0, 1\}^{\mathbb {N}}}]=\mathrm{Fix}(\Psi )\cap ({\{0, 1\}^{\mathbb {N}}}\times [0,1]^{\mathbb {N}})$
, where
${\{0, 1\}^{\mathbb {N}}}$
is always thought of as a subset of
$[0,1]$
(as a Cantor set). Now, consider the space
$\mathbf {Rea}(\mathcal {G})=\mathbf {\omega CEA}(\mathcal {G},\mathrm{Fix}^{\ast }(\Psi ))$
. To state properties of
$\mathbf {Rea}(\mathcal {G})$
, for an oracle
$\mathbf {\Pi }^{0}_{2}$
-singleton g and an oracle
$r\in {\{0, 1\}^{\mathbb {N}}}$
, we use the following Turing ideal:
$$ \begin{align*}\mathcal{J}_{T}(g,r)=\{z\in {\{0, 1\}^{\mathbb{N}}}:(\exists n\in\mathbb{N})\;z\leq_{\mathrm{T}} g^{n}(r)\}.\end{align*} $$
The following is the key lemma, which states that any collection of jump ideals generated by countably many oracle
$\mathbf {\Pi }^{0}_{2}$
-singletons has to be the degree co-spectrum of a Polish space up to the almost arithmetical equivalence!
Lemma 5.8. Suppose that
$\mathcal {G}=(g_{n})_{n\in \mathbb {N}}$
is a countable set of oracle
$\mathbf {\Pi }^{0}_{2}$
-singletons.
-
1. For every
$x\in \mathbf {Rea}(\mathcal {G})$
, there are
$r\in {\{0, 1\}^{\mathbb {N}}}$
and
$n\in \mathbb {N}$
such that
$$ \begin{align*}\mathcal{J}_{T}(g_{n},r)\subseteq\mathrm{coSpec}(x)\subseteq\mathcal{J}_{a}(g_{n},r).\end{align*} $$
-
2. For every
$r\in {\{0, 1\}^{\mathbb {N}}}$
and
$n\in \mathbb {N}$
, there is
$x\in \mathbf {Rea}(\mathcal {G})$
such that
$$ \begin{align*}\mathcal{J}_{T}(g_{n},r)\subseteq\mathrm{coSpec}(x)\subseteq\mathcal{J}_{a}(g_{n},r).\end{align*} $$
Proof of Lemma 5.8 (1)
We have
$(r,x)\in \mathrm{Fix}(\Psi )$
for every
$y=(n,d,e,r,x)\in \mathbf {Rea}(\mathcal {G})$
. For every
$i\in \mathbb {N}$
, we inductively assume that for every
$j<i$
,
$x_{j}$
is arithmetical in
$g_{n}^{k}(r)$
for some
$k\in \mathbb {N}$
. Now, either
$x_{i}=g_{n}^{i}(r)$
or
$x_{i}$
is left-c.e. in
$(r,x_{<i},g_{n}^{\ell }(r))$
for some
$\ell $
. In both cases,
$x_{i}$
is arithmetical in
$g_{n}^{k}(r)$
for some k. Since
$(r,x)\in \mathrm{Fix}(\Psi )$
, by Lemma 4.8,
$\mathrm{coSpec}(y)=\{r\}\cup \{x_{i}:i\in \mathbb {N}\}$
. This shows that
$\mathrm{coSpec}(y)\subseteq \mathcal {J}_{a}(g_{n},r)$
. Moreover,
$x_{i}=g_{n}^{i}(r)$
for infinitely many
$i\in \mathbb {N}$
, since either
$x_{i}=g^{i}_{n}(r)$
holds or there is
$\ell \geq i$
such that
$x_{\ell }=g^{\ell }_{n}(r)$
by the condition (2) in Definition 5.5. Therefore,
$g_{n}^{k}(r)\leq _{\mathrm {T}} x$
for all
$k\in \mathbb {N}$
; that is,
$\mathcal {J}_{T}(g_{n},r)\subseteq \mathrm{coSpec}(y)$
.
To verify the assertion (2) in Lemma 5.8 – indeed, for any
$n\in \mathbb {N}$
– we will construct indices d and e such that for every
$r\in {\{0, 1\}^{\mathbb {N}}}$
, there is
$x=(x_{i})_{i\in \mathbb {N}}$
with
$(n,d,e,r,x)\in \mathbf {Rea}(\mathcal {G})$
, where
$x_{i}=g_{n}^{i}(r)$
for infinitely many
$i\in \mathbb {N}$
. Let e be an index of a left-c.e. procedure
$J^{i+1}_{e}(r,x_{<i},x_{\ell (u)})$
which is a simple procedure extending
$r,x_{<i},x_{\ell (u)}$
to the leftmost
$r,x_{\leq i},x_{\ell (u)}$
which is extendable to a fixed point of
$\Psi $
(as in Kreisel’s basis theorem in the proof of Theorem 4.5). The function
$\Phi _{d}$
searches for a safe coding location
$c(n)$
from a given name of
$x_{\leq c(n-1)}$
, where
$c(n-1)$
is the previous coding location.
To make sure the search of the next coding location is bounded, as in Definition 5.5, we have to restrict the set of names of a v-tuple
$x_{<v}$
to at most
$v+1$
candidates. It is known that a separable metrisable space is at most n-dimensional if and only if it is the union of
$n+1$
many zero-dimensional subspaces (see [Reference Engelking15, Theorem 1.5.8] or [Reference van Mill64, Corollary 3.1.7]). We say that an admissibly represented Polish space is computably at most n-dimensional if it is the union of
$n+1$
many subspaces that are computably homeomorphic to subspaces of
$\mathbb {N}^{\mathbb {N}}$
.
Lemma 5.9. Suppose that
$(\mathbf {X},\rho _{X})$
is a computably at most n-dimensional admissibly represented space. Then, there is a partial computable injection
$\nu _{X}:\subseteq (n+1)\times \mathbf {X}\to \mathbb {N}^{\mathbb {N}}$
such that for every
$x\in \mathbf {X}$
, there is
$k\leq n$
such that
$(k,x)\in \mathrm{dom}(\nu _{X})$
and
$\rho _{X}\circ \nu _{X}(k,x)=x$
.
Proof. By definition,
$\mathbf {X}$
is divided into
$n+1$
many subspaces
$S_{0},\dots ,S_{n}$
such that
$S_{k}$
is homeomorphic to
$N_{k}\subseteq \mathbb {N}^{\mathbb {N}}$
via computable maps
$\tau _{k}\colon S_{k}\to N_{k}$
and
$\tau _{k}^{-1}\colon N_{k}\to S_{k}$
. Then,
$\tau ^{-1}_{k}$
can also be viewed as a partial computable injection
$\tau _{k}^{-1}:\subseteq \mathbb {N}^{\mathbb {N}}\to \mathbf {X}$
and then it has a computable realiser
$\tau ^{*}_{k}$
; that is,
$\tau _{k}^{-1}=\rho _{X}\circ \tau ^{*}_{k}$
. Define
$\nu _{X}(k,x)=\tau ^{*}_{k}\circ \tau _{k}(x)$
for
$x\in S_{k}$
. Then, we have
$\rho _{X}\circ \nu _{X}(k,x)=\tau _{k}^{-1}\circ \tau _{k}(x)=x$
for
$x\in S_{k}$
.
The Euclidean n-space
$\mathbb {R}^{n}$
is clearly computably n-dimensional; for example, for
$k\leq n$
, let
$S_{k}$
be the set of all points
$x\in \mathbb {R}^{n}$
such that exactly k many coordinates are irrationals. Furthermore, one can effectively find an index of
$\nu _{n}:=\nu _{\mathbb {R}^{n}}$
in Lemma 5.9 uniformly in n. Hereafter, let
$\rho _{i}$
be the usual Euclidean admissible representation of
$\mathbb {R}^{i}$
(cf. [Reference Weihrauch65]). One can use Miller’s argument [Reference Miller37, Lemma 9.2] to ensure the existence of a safe coding location
$c(n)$
as a fixed point in the sense of Kleene’s recursion theorem. Therefore, as Kleene’s recursion theorem is uniform (see Fact 2.1), one can effectively find such a location in the following sense:
Lemma 5.10 (Miller [Reference Miller37, Lemma 9.2])
Suppose that
$(r,x_{<i})$
can be extended to a fixed point of
$\Psi $
and fix a partial computable function
$\nu $
which sends
$x_{<i}$
to its name; that is,
$\rho _{i}\circ \nu (x_{<i})=(x_{<i})$
. From an index t of
$\nu $
and the sequence
$x_{<i}$
, one can effectively find a location
$p=\Gamma (t,r,x_{<i})$
such that for every real y, the sequence
$(r,x_{<i})$
can be extended to a fixed point
$(r,x)$
of
$\Psi $
such that
$x_{p}=y$
.
Note that, in Lemma 5.10, we always have
$p\geq i$
since an arbitrary
$x_{p}$
is allowed. Let
$t(n,k)$
be an index of the partial computable function
$x\mapsto \nu _{n}(k,x)$
for
$k\leq n$
and let d be an index such that
$\Phi _{d}(u,r,x_{<v})$
is equal to
$\Gamma (t(v,u),r,x_{<v})$
for every
$u\leq v$
. Note that indices d and e do not depend on
$g_{n}$
(where e is an index chosen in the paragraph after the proof of Lemma 5.8 (1)).
Proof of Lemma 5.8 (2)
Now, we claim that for every
$r\in {\{0, 1\}^{\mathbb {N}}}$
and
$n\in \mathbb {N}$
, there is x with
$(n,d,e,r,x)\in \mathbf {Rea}(\mathcal {G})$
, where
$x_{i}=g_{n}^{i}(r)$
for infinitely many
$i\in \mathbb {N}$
. We follow the argument by Miller [Reference Miller37, Lemma 9.2]. Suppose that i is a coding location of
$g_{n}^{i}(r)$
and
$(r,x_{\leq i})$
is extendible to a fixed point of
$\Psi $
. Here, for the base case, consider
$i={-1}$
and
$x_{-1}$
is the empty sequence. Then, there is a genuine
$k\leq i+1$
; that is,
$\nu _{i+1}(k,x_{\leq _{i}})$
returns a name of
$x_{\leq i}$
. For such a k,
$p=\Phi _{d}(k,r,x_{\leq i})$
is defined and then we set
$x_{p}=g_{n}^{p}(r)$
, where we have
$p\geq i+1$
as mentioned in the paragraph below Lemma 5.10. By the property of
$\Phi _{d}$
(Lemma 5.10),
$(r,x_{\leq i},x_{p})$
can be extended to a fixed point of
$\Psi $
. Then, the eth left-c.e. procedure automatically produces
$x_{\leq p}$
which extends
$x_{\leq i}$
and is extendible to a fixed point of
$\Psi $
. Note that the condition (2) in Definition 5.5 is ensured via
$u=k$
,
$v=i+1$
and
$\ell (u)=p$
. Eventually, we obtain
$(r,x)\in \mathrm{Fix}(\Psi )$
such that
$z=(n,d,e,r,x)\in \mathbf {Rea}(\mathcal {G})$
.
Clearly,
$g_{n}^{k}(r)\in \mathrm{coSpec}(z)$
for every
$k\in \mathbb {N}$
, since
$\mathrm{coSpec}(z)$
is a Turing ideal and
$g_{n}^{k}(r)\leq _{\mathrm {T}} g_{n}^{k+1}(r)$
. Consequently,
$\mathcal {J}_{T}(g_{n},r)\subseteq \mathrm{coSpec}(z)$
. The inclusion
$\mathrm{coSpec}(z)\subseteq \mathcal {J}_{a}(g_{n},r)$
can be shown as in the proof of Lemma 5.8 (1).
Proof of Lemma 5.4
Suppose that
$\mathbf {Rea}(\mathcal {G})\leq ^{\mathfrak {T}}_{\sigma }\mathbf {Rea}(\mathcal {H})$
. Then,
$\mathbb {N}\times \mathbf {Rea}(\mathcal {G})\leq ^{\mathfrak {T}}_{\sigma }\mathbb {N}\times \mathbf {Rea}(\mathcal {H})$
and by Lemma 3.5 and Observation 4.6, the degree cospectrum of
$\mathbf {Rea}(\mathcal {G})$
is a sub-cospectrum of that of
$\mathbf {Rea}(\mathcal {H})$
up to an oracle p. Fix enumerations
$\mathcal {G}=(g_{n})_{n\in \mathbb {N}}$
and
$\mathcal {H}=(h_{n})_{n\in \mathbb {N}}$
.
Claim. For any n and
$u\geq _{T}p$
, there are m and v such that
$\mathcal {J}_{a}(g_{n},u)=\mathcal {J}_{a}(h_{m},v)$
.
By Lemma 5.8 (2), for any n and
$u\geq _{T}p$
, there is
$x\in \mathbf {Rea}(\mathcal {G})$
such that
$\mathcal {J}_{T}(g_{n},u)\subseteq \mathrm{coSpec}(x)\subseteq \mathcal {J}_{a}(g_{n},u)$
. Note that
$p\leq _{\mathrm {T}} u$
implies
$p\in \mathcal {J}_{T}(g_{n},u)\subseteq \mathrm{coSpec}(x)$
; that is, p is x-computable and, therefore,
$\mathrm{coSpec}(x)=\mathrm{coSpec}^{p}(x)$
. By our assumption, there is
$y\in \mathbf {Rea}(\mathcal {H})$
such that
$\mathrm{coSpec}^{p}(x)=\mathrm{coSpec}^{p}(y)$
.
We claim that
$p\leq _{\mathrm {T}} y$
: Otherwise,
$(y,p)$
has Turing degree by almost totality of continuous degrees (cf. [Reference Andrews, Igusa, Miller and Soskova3]); that is, if
$\mathbf {q}=\mathrm{deg}(q)\in \mathrm{Spec}([0,1]^{\mathbb {N}})\setminus \mathrm{Spec}({\mathbb {N}^{\mathbb {N}}})$
, then, for any
$p\in {\mathbb {N}^{\mathbb {N}}}$
, the condition
$\mathrm{deg}(p,q)\in \mathrm{Spec}({\mathbb {N}^{\mathbb {N}}})$
is equivalent to
$p\not \leq _{\mathrm {T}} q$
. However, that
$(y,p)$
has a Turing degree means that
$\mathrm{coSpec}^{p}(y)$
forms a principal ideal. Then,
$\mathrm{coSpec}^{p}(y)=\mathrm{coSpec}(x)$
implies that
$\mathrm{coSpec}(x)$
is principal, which is equivalent to saying that x has a Turing degree. However, it is impossible since
$x\in \mathbf {Rea}(\mathcal {G})\subseteq \mathbb {N}^{3}\times \mathrm{Fix}(\Psi )$
implies that x has no Turing degree by Lemma 4.8.
Thus, we have
$\mathrm{coSpec}(y)=\mathrm{coSpec}^{p}(y)$
. Then, by Lemma 5.8 (1), there exist m and v such that
$\mathcal {J}_{T}(h_{m},v)\subseteq \mathrm{coSpec}(y)\subseteq \mathcal {J}_{a}(h_{m},v)$
. Now,
$\mathrm{coSpec}(x)=\mathrm{coSpec}(y)$
holds and note that
$\mathcal {J}_{T}(h_{m},v)\subseteq \mathcal {J}_{a}(g_{n},u)$
implies
$\mathcal {J}_{a}(h_{m},v)\subseteq \mathcal {J}_{a}(g_{n},u)$
. This verifies the claim.
For a fixed n,
$\beta _{n}(u)$
chooses m fulfilling the above claim for some v. It is not hard to see that there is
$m(n)$
such that
$\beta _{n}(u)=m(n)$
for cofinally many u.
We will show that, for cofinally many u, there is v such that
$\mathcal {J}_{a}(g_{n},u\oplus v)=\mathcal {J}_{a}(h_{m(n)},u\oplus v)$
: By our proof of the above claim, such u and v involve some x and y such that
$u\in \mathrm{coSpec}(x)=\mathrm{coSpec}(y)\ni v$
. This x also has the property
$\mathrm{coSpec}(x)\subseteq \mathcal {J}_{a}(g_{n},u)$
. Thus,
$v\in \mathcal {J}_{a}(g_{n},u)$
; that is,
$v\leq _{a} g_{n}^{i}(u)$
for some i and, therefore, by monotonicity of
$g_{n}$
, we get
$g_{n}^{j}(u\oplus v)\leq _{a} g_{n}^{i+j}(u)$
. Thus,
$\mathcal {J}_{a}(g_{n},u\oplus v)=\mathcal {J}_{a}(g_{n},u)$
. Similarly, we have
$\mathcal {J}_{a}(h_{m(n)},u\oplus v)=\mathcal {J}_{a}(h_{m(n)},v)$
.
Therefore,
$g_{n}\equiv _{aa}h_{m(n)}$
. Consequently,
$\mathcal {G}\subseteq _{aa}\mathcal {H}$
.
Proof of Theorem 5.1
Let S be a countable subset of
$\omega _{1}$
. Note that
$\sup S$
is countable by regularity of
$\omega _{1}$
. Then, there is an oracle p such that
$\sup S<\omega _{1}^{\mathrm{CK},p}$
, where
$\omega _{1}^{\mathrm{CK},p}$
is the smallest noncomputable ordinal relative to p. Now, the
$\alpha $
th Turing jump operator
$j^{p}_{\alpha }$
for
$\alpha <\omega _{1}^{\mathrm{CK},p}$
is defined via a p-computable coding of
$\alpha $
. By Spector’s uniqueness theorem (see Sacks [Reference Sacks58, Corollary II.4.6] or Chong-Yu [Reference Chong, Yu and Sacks9, Section 2.3]), the Turing degree of
$j^{p}_{\alpha }(x)$
for
$x\geq _{T}p$
is independent of the choice of coding of
$\alpha $
and so is
$\mathcal {J}_{a}(j^{p}_{\alpha },x)$
. Therefore, we simply write
$j_{\alpha }$
for
$j^{p}_{\alpha }$
.
Define
$\mathcal {G}_{S}=\{j_{\omega ^{1+\alpha }}:\alpha \in S\}$
. We show that
$S\subseteq T$
if and only if
$\mathcal {G}_{S}\subseteq _{aa}\mathcal {G}_{T}$
. Suppose
$\alpha \not =\beta $
, say,
$\alpha <\beta $
. Clearly,
$j_{\omega ^{\alpha }}\leq _{aa}j_{\omega ^{\beta }}$
. Suppose for the sake of contradiction that
$j_{\omega ^{\beta }}\leq _{aa}j_{\omega ^{\alpha }}$
. Then, in particular, for every
$x\leq _{a}\emptyset ^{(\omega ^{\beta }\cdot t)}$
with
$t\in \mathbb {N}$
, we must have
$\emptyset ^{(\omega ^{\beta }\cdot (t+1))}\leq _{a}x^{(\omega ^{\alpha }\cdot m)}$
for some
$m\in \mathbb {N}$
. Thus, there is n such that
$\emptyset ^{(\omega ^{\beta }\cdot t+\omega ^{\beta })}\leq _{\mathrm {T}} \emptyset ^{(\omega ^{\beta }\cdot t+\omega ^{\alpha }\cdot m+n)}<_{T}\emptyset ^{(\omega ^{\beta }\cdot t+\omega ^{\alpha +1})}$
. This is a contradiction.
Now, given countable sets
$S,T\subseteq \omega _{1}$
, if
$S\subseteq T$
, then
$\mathbf {Rea}(\mathcal {G}_{S})$
clearly embeds into
$\mathbf {Rea}(\mathcal {G}_{T})$
. If
$S\not \subseteq T$
, then the above argument shows that
$\mathcal {G}_{S}\not \subseteq _{aa}\mathcal {G}_{T}$
and, therefore, by Lemma 5.4, we have
$\mathbf {Rea}(\mathcal {G}_{S})\not \leq _{\sigma }^{\mathfrak {T}}\mathbf {Rea}(\mathcal {G}_{T})$
. Consequently,
$S\mapsto \gamma \mathbf {Rea}(\mathcal {G}_{S})$
is an order-preserving embedding of
$([\omega _{1}]^{\leq \omega },\subseteq )$
into the
$\sigma $
-embeddability order
$\leq _{\sigma }^{\mathfrak {T}}$
on compact metrisable spaces, where
$\gamma \mathbf {X}$
is Lelek’s compactification of
$\mathbf {X}$
in Fact 4.1.
Corollary 5.11. There exists a collection
$(\mathbf {X}_{\alpha })_{\alpha <2^{\aleph _{0}}}$
of continuum many compact metrisable spaces satisfying the following conditions:
-
1. If
$\alpha \not =\beta $
, then
$\mathbf {X}_{\alpha }$
does not finite-level Borel embed into
$\mathbf {X}_{\beta }$
. -
2. If
$\alpha \not =\beta $
, then the Banach algebra
$\mathcal {B}^{*}_{n}(\mathbf {X}_{\alpha })$
is not linearly isometric (not ring isomorphic etc.) to
$\mathcal {B}^{*}_{n}(\mathbf {X}_{\beta })$
for all
$n\in \mathbb {N}$
.
6 Infinite-Dimensional Topology
6.1 Pol’s Compactum
In this section, we will shed light on dimension-theoretic perspectives of the
$\omega $
-left-CEA space. Note that
$\mathbf {\omega CEA}$
is a totally disconnected infinite-dimensional space. We first compare our space
$\mathbf {\omega CEA}$
and a totally disconnected infinite-dimensional space
$\mathbf {RSW}$
which is constructed by Rubin, Schori and Walsh [Reference Rubin, Schori and Walsh57]. A continuum is a connected compact metric space and a continuum is nondegenerated if it contains at least two points.
It is known that the hyperspace
${\sf CK}(\mathbf {X})$
of continua in a compact metrisable space
$\mathbf {X}$
equipped with the Vietoris topology forms a Polish space. Hence, we may think of
${\sf CK}(\mathbf {X})$
as a represented space, which corresponds to a positive and negative representation of the hyperspace in computable analysis. We consider the closed subspace S of
${\sf CK}([0,1]^{\mathbb {N}})$
consisting of all continua connecting opposite faces
$\pi _{0}^{-1}\{0\}$
and
$\pi _{0}^{-1}\{1\}$
. Then, fix a total Cantor representation of S; that is, a continuous surjection
$\delta _{\sf CK}$
from the Cantor set
$C\subseteq [0,1]$
onto S.
Remark 6.1. If we are interested in effectivity, we can give a more explicit construction of
$\delta _{\sf CK}$
: Let
$\delta $
be the standard positive-and-negative representation of the hyperspace
$\mathcal {A}([0,1]^{\mathbb {N}})$
of all closed subsets of the Hilbert cube. Then, one can see that S is a
$\Pi ^{0}_{1}$
subspace of
$\mathcal {A}([0,1]^{\mathbb {N}})$
as follows.
A
$\delta $
-name of
$A\in \mathcal {A}([0,1]^{\mathbb {N}})$
can be thought of as an enumeration of all finite open covers
$\mathcal {U}=\{U_{i}\}_{i<n}$
of A such that
$A\cap U_{i}\not =\emptyset $
for each
$i<n$
. If A is disconnected, then there are disjoint open sets
$U,V$
in
$[0,1]^{\mathbb {N}}$
such that
$A\subseteq U\cup V$
. Thus, by compactness of A, such disjoint open sets U and V can be replaced with finite unions
$U_{s},V_{s}$
of basic open sets. Note that, if U and V are finite unions of basic open sets, one can effectively decide whether U and V are disjoint. This means that, if p is a name of a disconnected set, then some
$p(s)$
witnesses this fact.
Next, assume that A does not connect
$\pi _{0}^{-1}\{0\}$
and
$\pi _{0}^{-1}\{1\}$
. First consider the case that
$A\cap \pi _{0}^{-1}\{y\}$
is empty for some
$y\in \{0,1\}$
. By compactness,
$A\cap \pi _{0}^{-1}\{y\}=\emptyset $
is a
$\Sigma ^{0}_{1}$
property relative to a name of A. Thus, this fact is witnessed after reading a finite amount of information of the name. Now, assume that
$A\cap \pi _{0}^{-1}\{y\}$
is nonempty for each
$y\in \{0,1\}$
. Then, that A does not connect
$\pi _{0}^{-1}\{0\}$
and
$\pi _{0}^{-1}\{1\}$
means that there are disjoint open sets U and V such that
$A\cap \pi _{0}^{-1}\{0\}\subseteq U$
and
$A\cap \pi _{0}^{-1}\{1\}\subseteq V$
. As in the previous argument, this fact is also witnessed by some
$p(s)$
.
Consequently, S is
$\Pi ^{0}_{1}$
– that is, if p is a name of some
$A\not \in S$
– then one can obtain this information from p by some finite stage. As usual, one can consider a partial name
$(p(0),p(1),\dots ,p(s-1))$
as a closed set
$A^{p}_{s}$
and it converges to
$A^{p}:=\delta (p)$
. By the above argument, if
$A^{p}\not \in S$
, then
$A^{p}_{s}\not \in S$
for some s. If s is the least such number, then
$A^{p}_{s-1}\in S$
and we define
$\delta _{\sf CK}(p)=A^{p}_{s-1}$
. If it does not happen, then
$\delta _{\sf CK}(p)=\delta (p)$
. Then,
$\delta _{\sf CK}$
is a total representation of S.
We define the Rubin–Schori–Walsh space
$\mathbf {RSW}$
[Reference Rubin, Schori and Walsh57] (see also [Reference van Mill64, Theorem 3.9.3]) as follows:
$$ \begin{align*} \mathbf{RSW}&=\{\min (\delta_{\sf CK}(p)^{[p]}):p\in C\},\\ &=\{\min A^{[p]}:A\mbox{ is the }\mathit{p}\mbox{th continuum of }[0,1]^{\mathbb{N}}\mbox{ with }[0,1]\subseteq\pi_{0}[A]\}, \end{align*} $$
where
$A^{[p]}=A\cap \pi _{0}^{-1}\{p\}=\{z\in A:\pi _{0}(z)=p\}$
and recall that
$\min P$
is the leftmost point of P defined in the proof of Theorem 4.5. For notational convenience, without loss of generality, we may assume that the eth z-computable continuum is equal to the
$\langle e,z\rangle $
th continuum, where recall that
$\langle \cdot ,\cdot \rangle $
is a pairing function.
A compactification of
$\mathbf {RSW}$
is well-known in the context of Alexandrov’s old problem in dimension theory. Pol’s compactum
$\mathbf {RP}$
is given as a compactification in the sense of Lelek of the space
$\mathbf {RSW}$
. Hence, we can see that
$\mathbf {RP}$
and
$\mathbf {RSW}$
have the same point degree spectra (modulo an oracle) as in the proof of Fact 4.1. Surprisingly, these spaces have the same degree spectra as the space
$\omega \mathbf {CEA}$
up to an oracle.Footnote
2
Theorem 6.2. All of the following spaces have the same point degree spectra relative to some oracle:
-
1. The
$\omega $
-left-CEA space
$\mathbf {\omega CEA}$
. -
2. Rubin–Schori–Walsh’s totally disconnected strongly infinite-dimensional space
$\mathbf {RSW}$
. -
3. Roman Pol’s counterexample
$\mathbf {RP}$
to Alexandrov’s problem.
Indeed, we will show that
$\mathbf {RP}\simeq _{\sigma }^{\mathfrak {T}}\mathbf {RSW}\leq _{c}\omega \mathbf {CEA}\leq _{\sigma \mathbf {RSW}}$
. As a corollary,
$\mathbb {N}\times \mathbf {\omega CEA}$
,
$\mathbb {N}\times \mathbf {RSW}$
and
$\mathbb {N}\times \mathbf {RP}$
are all
$\sigma $
-homeomorphic (hence second-level Borel isomorphic) to each other. To prove Theorem 6.2, we show two lemmata.
Lemma 6.3. Every point of
$\mathbf {RSW}$
is
$\omega $
-left-CEA.
Proof. As we have seen in the proof of Theorem 4.5,
$\min A^{[p]}$
is
$\omega $
-left-CEA in p, since
$A^{[p]}$
is
$\Pi ^{0}_{1}(p)$
(see also Remark 6.1 on
$\delta _{\sf CK}$
). Moreover, clearly,
$p\leq _{\mathrm {T}} \min A^{[p]}$
. Thus,
$\min A^{[p]}$
is
$\omega $
-left-CEA.
For
$\omega \mathbf {CEA}\leq _{\sigma }^{\mathfrak {T}}\mathbf {RSW}$
, we need to show that every
$\omega $
-left-CEA point is realised as a leftmost point of a computable continuum in a uniform manner. Indeed, we will show the following.
Lemma 6.4. Suppose that
$x\in [0,1]^{\mathbb {N}}$
is
$\omega $
-left-CEA in a point
$z\in {\{0, 1\}^{\mathbb {N}}}$
. Then, there is a nondegenerated z-computable continuum
$A\subseteq [0,1]^{\mathbb {N}}$
such that
$[0,1]\subseteq \pi _{0}[A]$
and
$\min A^{[p]}=(p,x)$
for a name p of A.
Proof. Given
$p=\langle e,z\rangle $
, we will effectively construct a name
$\Psi (p)$
of a continuum A. We can view this construction as defining a computable function
$f : \mathbb {N} \to \mathbb {N}$
such that
$\Phi _{f(e)}^{z} = \Psi (p)$
. By Kleene’s recursion theorem (Fact 2.1), we may fix e such that, for
$p=\langle e,z\rangle $
, the pth continuum is equal to the
$\Psi (p)$
th continuum.
We first describe how to obtain the negative information about
$\Psi (p)$
. Fix an
$\omega $
-left-CEA operator J generated by
$\langle W_{n}\rangle _{n\in \mathbb {N}}$
such that
$J(z)=x$
. Here, as in the proof of Proposition 4.2, each
$W_{n}$
is a c.e. list of pairs
$(i,q)$
, which indicates that ‘if a given n-tuple
$(z_{0},\dots ,z_{n-1})$
is in the ith ball
$B_{i}^{n}\subseteq [0,1]^{n}$
, then
$J^{n}_{W_{n}}(z_{0},\dots ,z_{n-1})\geq q$
’. Since
$p=\langle e,z\rangle $
for some
$e\in \mathbb {N}$
, we have a computable function
$\pi $
with
$\pi (p)=z$
and then redefine
$W_{0}$
to be
$W_{0}\circ \pi $
. In this way, we may assume that
$J(p)=x$
.
At stage
$0$
,
$\Psi $
constructs
$A_{0}=[0,1]\times [0,1]^{\mathbb {N}}$
. At stage
$s+1$
, if we find some rational open ball
$B_{i}^{n}\subseteq [0,1]^{n}$
and a rational
$q\in \mathbb {Q}$
such that
$W_{n,s}$
declares that ‘if a given n-tuple
$(z_{0},\dots ,z_{n-1})$
is in the ith ball
$B_{i}^{n}$
, then
$J^{n}_{W_{n}}(z_{0},\dots ,z_{n-1})\geq q$
’, by enumerating
$(i,q)$
, then
$\Psi $
removes
$\pi _{0}^{-1}[B(p;2^{-s})]\cap (B_{i}^{n}\times [0,q)\times [0,1]^{\mathbb {N}})$
from the previous continuum
$A_{s-1}$
, where
$B(p;2^{-s})$
is the rational open ball with centre p and radius
$2^{-s}$
.
Now, we show
$\min A^{[p]}=x:=(x_{0},x_{1},\dots )$
. Assume that
$x_{0},\dots ,x_{n-1}$
is an initial segment of
$\min A^{[p]}$
. We will show that
$x_{n}=\pi _{n}(\min A^{[p]})=\min \pi _{n}[\{z\in A^{[p]}:(\forall i<n)\;\pi _{i}(z)=x_{i}\}]$
. Since
$J^{n}_{W_{n}}(p,x_{0},\dots ,x_{n-1})=x_{n}$
,
$W_{n}$
declares this fact at some point; that is, for any rational
$q<x_{n}$
, there is i such that
$(i,q)\in W_{n}$
and
$(p,x_{0},\dots ,x_{n-1})\in B^{n}_{i}$
. Therefore,
$A\cap (\pi _{0}^{-1}[B(p;2^{-s})]\cap (B^{n}_{i}\times [0,q)\times [0,1]^{\mathbb {N}}))=\emptyset $
. Hence, if
$y<x_{n}$
, then no extension of
$(p,x_{0},\dots ,x_{n-1},y)$
is contained in A. Moreover, if
$(p,x_{0},\dots ,x_{n-1})\in B^{n}_{i}$
and
$q<x_{n}$
, then
$(i,q)\not \in W_{n}$
. Hence,
$x_{n}=\pi _{n}(\min A^{[p]})$
as desired.
Now, clearly,
$\min A^{[p]}=(p,x)$
. Note that
$\Psi $
defines a z-computable continuum A in a uniform manner. We can obtain the positive information, too, as we remove only subsets of
$\pi _{0}^{-1}[B(p;2^{-s})]$
after stage s. Thus, to ascertain that a ball of radius greater than
$2^{-s}$
intersects A, we only need to perform the construction up to stage s. For the connectivity, assume that
$A\subseteq U\cup V$
for some open sets
$U,V\subseteq [0,1]^{\mathbb {N}}$
. By compactness, one can assume that U and V mention only finitely many coordinates; that is, there is
$n_{0}$
such that if
$y=(y_{n})_{n\in \mathbb {N}}\in U$
(V, respectively) then
$(y_{0},\dots ,y_{n_{0}},z_{n_{0}+1},z_{n_{0}+2},\dots )\in U$
(V, respectively) for any
$(z_{n_{0}+m})_{m\in \mathbb {N}}$
. Given
$y=(y_{n})_{n\in \mathbb {N}}$
, define
$y^{\ast }=(y_{0},\dots ,y_{n_{0}},\vec {1})$
. By our choice of
$n_{0}$
and our definition of A,
$y\in A\cap U$
implies
$y^{\ast }\in A\cap U$
. By our construction of A, if
$k\leq n_{0}$
, then any
$(y_{0},\dots ,y_{k},\vec {1})\in A\cap U$
is connected to
$(y_{0},\dots ,y_{k-1},1,\vec {1})\in A\cap U$
by a line segment inside
$A\cap U$
. Therefore, for any point
$y\in A\cap U$
,
$y^{\ast }$
is connected to
$\vec {1}$
by a polygonal line inside
$A\cap U$
. The same holds true for V. Hence, if
$A\cap U$
and
$A\cap V$
are nonempty,
$y\in A\cap U$
and
$z\in A\cap V$
say,
$y^{\ast }\in A\cap U$
and
$z^{\ast }\in A\cap V$
and they are connected to
$\overline {1}$
and, therefore, there is a path from
$y^{\ast }$
to
$z^{\ast }$
in
$A\cap (U\cup V)$
. By connectivity of the path,
$A\cap U$
and
$A\cap V$
have an intersection in the path. This shows that A cannot be written as a union of disjoint open subsets. Consequently, A is connected.
The properness of
$\mathbf {RSW} <_{\sigma }^{\mathfrak {T}} [0,1]^{\mathbb {N}}$
can also be obtained by some relatively recent work on infinite-dimensional topology: the Hilbert cube (indeed, any strongly infinite-dimensional compactum) is not
$\sigma $
-hereditary-disconnected (see [Reference Radul52]). However, such an argument does not go any further for constructing second-level Borel isomorphism types and, indeed, to the best of our knowledge, no known topological technique provides us four or more second-level Borel isomorphism types.
On a side note, one can also define the graph
$n\mathbf {CEA}\subseteq \mathbb {N}\times {\{0, 1\}^{\mathbb {N}}}\times [0,1]^{n}$
of a universal n-left-CEA operator (as an analogy of an n-REA operator) in a straightforward manner. The space
$n\mathbf {CEA}$
is an example of a finite-dimensional Polish space whose infinite product has again the same dimension. The first such examples were constructed by Kulesza in [Reference Kulesza32].
Proposition 6.5. The space
$n\mathbf {CEA}$
is a totally disconnected n-dimensional Polish space. Moreover, the countable product
$n\mathbf {CEA}^{\mathbb {N}}$
is again n-dimensional.
Proof. Clearly,
$n\mathbf {CEA}$
is totally disconnected and Polish. To check the n-dimensionality, we think of
$n\mathbf {CEA}$
as a subspace of
$[0,1]^{n+1}$
by identifying
$(e,x)\in \mathbb {N}\times {\{0, 1\}^{\mathbb {N}}}$
with
$\iota (0^{e}1x)\in [0,1]$
, where
$\iota $
is a computable embedding of
${\{0, 1\}^{\mathbb {N}}}$
into
$[0,1]$
. We claim that
$n\mathbf {CEA}$
intersects with all continua
$A\subseteq [0,1]^{n+1}$
such that
$[0,1]\subseteq \pi _{0}[A]$
. We have a computable function d such that the
$d(e)$
th n-left-CEA procedure
$J^{n}_{d(e)}(x)$
for a given input
$x\in {\{0, 1\}^{\mathbb {N}}}$
outputs the value
$y\in [0,1]^{n}$
such that
$(\iota (0^{e}1x),y)=\min A_{e,x}^{[\iota (0^{e}1x)]}$
, where
$A_{e,x}$
is the eth x-computable continuum in
$[0,1]^{n+1}$
such that
$[0,1]\subseteq \pi _{0}[A_{e,x}]$
. By Kleene’s recursion theorem (Fact 2.1), there is r such that
$J^{n}_{d(r)}=J^{n}_{r}$
. Hence,
$(\iota (0^{r}1x),J^{n}_{r}(x))\in n\mathbf {CEA}\cap A_{e,x}$
, which verifies the claim. The claim implies that
$n\mathbf {CEA}$
is n-dimensional (see van Mill [Reference van Mill64, Corollary 3.7.5]).
To verify the second assertion, consider the (computably) continuous map g from the square
$n\mathbf {CEA}^{2}$
into
${\{0, 1\}^{\mathbb {N}}}\times [0,1]^{n}$
such that for two points
$\mathbf {x}=(e,r,x_{0},\dots ,x_{n-1})$
and
$\mathbf {y}=(d,s,y_{0},\dots ,y_{n-1})$
in
$n\mathbf {CEA}$
,
$$ \begin{align*}g(\mathbf{x},\mathbf{y})=(\langle e,d\rangle,r\oplus s,(x_{0}+y_{0})/2,\dots,(x_{n-1}+y_{n-1})/2).\end{align*} $$
To verify that
$g^{-1}$
is also (computably) continuous, using given left r- and s-computable approximations of
$x_{0}$
and
$y_{0}$
, one can compute
$x_{0}$
and
$y_{0}$
from
$(x_{0}+y_{0})/2$
. By induction, one can computably recover
$\mathbf {x}$
and
$\mathbf {y}$
from
$g(\mathbf {x},\mathbf {y})$
. Hence,
$n\mathbf {CEA}^{2}$
is computably embedded into
${\{0, 1\}^{\mathbb {N}}}\times [0,1]^{n}$
. In particular, it is n-dimensional. The same argument shows that
$n\mathbf {CEA}^{k}$
is n-dimensional for any
$k\in \mathbb {N}$
. Then, we can conclude that
$n\mathbf {CEA}^{\mathbb {N}}$
is also n-dimensional (by the same argument as in van Mill [Reference van Mill64, Theorem 3.9.5]).
6.2 Nondegenerated Continua and
$\omega \mathbf {CEA}$
Degrees
We may extract computability-theoretic contents from the construction of Rubin–Schori–Walsh’s strongly infinite-dimensional totally disconnected space
$\mathbf {RSW}$
. The standard proof of noncountable dimensionality of
$\mathbf {RSW}$
(hence, the existence of a non-Turing degree in
$\mathbf {RSW}$
) indeed implies the following computability theoretic result.
Proposition 6.6. There exists a nondegenerated continuum
$A\subseteq [0,1]^{\mathbb {N}}$
in which no point has Turing degree.
Proof. Define
$\mathbf {H}_{\langle {i,j\rangle }}\subseteq [0,1]^{\mathbb {N}}$
to be the set of all points which can be identified with an element in
${\{0, 1\}^{\mathbb {N}}}$
via the witnesses
$\Phi _{i}$
and
$\Phi _{j}$
(as in the proof of Lemma 3.5). Then,
$\bigcup _{n}\mathbf {H}_{n}$
is the set of all points in
$[0,1]^{\mathbb {N}}$
having Turing degrees. Note that each
$\mathbf {H}_{n}$
is zero-dimensional since it is homeomorphic to a subspace of
${\{0, 1\}^{\mathbb {N}}}$
.
Consider the hyperplane
$P_{n}^{i}=[0,1]^{n}\times \{i\}\times [0,1]^{\mathbb {N}}$
for each
$n\in \mathbb {N}$
and
$i\in \{0,1\}$
. It is well known that
$\{(P_{n}^{0},P_{n}^{1})\}_{n\in \mathbb {N}}$
is essential in
$[0,1]^{\mathbb {N}}$
. Then, by using the dimension-theoretic fact (see van Mill [Reference van Mill64, Corollary 3.1.6]), we can find a separator
$L_{n}$
of
$(P_{n+1}^{0},P_{n+1}^{1})$
in
$[0,1]^{\mathbb {N}}$
such that
$L_{n}\cap \mathbf {H}_{n}=\emptyset $
since
$\mathbf {H}_{n}$
is zero-dimensional.
Put
$L=\bigcap _{n}L_{n}$
. Then, L contains no point having Turing degree, since
$L\cap \mathbf {H}_{n}=\emptyset $
for every
$n\in \mathbb {N}$
. Moreover, L contains a continuum A from
$P_{0}^{0}$
to
$P_{0}^{1}$
(see van Mill [Reference van Mill64, Proposition 3.7.4]).
Recall that our infinite-dimensional version of Kreisel’s basis theorem (shown in the proof of Theorem 4.5) says that every
$\Pi ^{0}_{1}$
subset P of the Hilbert cube has a point of an
$\omega $
-left-CEA continuous degree. Surprisingly, we do not need any effectivity assumption on P to prove this if P is a nontrivial connected compact set.
Proposition 6.7. Every nondegenerated continuum
$A\subseteq [0,1]^{\mathbb {N}}$
contains a point of an
$\omega $
-left-CEA continuous degree.
Proof. Note that there is
$n\in \omega $
such that
$P_{n}^{[0,p]}$
and
$P_{n}^{[q,1]}$
with some rationals
$p<q\in \mathbb {Q}$
intersect with A, since A is nondegenerated, where
$P_{n}^{[a,b]}=[0,1]^{n}\times [a,b]\times [0,1]^{\mathbb {N}}$
. Clearly, there is no separator C of
$P_{n}^{[0,p]}$
and
$P_{n}^{[q,1]}$
with
$C\cap A=\emptyset $
(i.e., the pair
$(P_{n}^{[0,p]},P_{n}^{[q,1]})$
is essential in A), since A is not zero-dimensional. Therefore, the pair
$(P_{n}^{p},P_{n}^{q})$
is essential in the compact subspace
$A\cap P_{n}^{[p,q]}$
. Hence,
$A\cap P_{n}^{[p,q]}$
contains a continuum B intersecting with
$P_{n}^{p}$
and
$P_{n}^{q}$
(see van Mill [Reference van Mill64, Proposition 3.7.4]). Consider a computable homeomorphism
$h:P_{n}^{[p,q]}\cong [0,1]^{\mathbb {N}}$
mapping
$P_{n}^{p}$
and
$P_{n}^{q}$
to
$P_{0}^{0}=\pi _{0}^{-1}(0)$
and
$P_{0}^{1}=\pi _{1}^{-1}(1)$
, respectively. Then
$h[B]$
is a continuum intersecting with
$\pi _{0}^{-1}(0)$
and
$\pi _{0}^{-1}(0)$
and therefore
$[0,1]\subseteq \pi _{0}[h[B]]$
. Let s be a name of
$h[B]$
. Then, by definition,
$\min h[B]^{[s]}\in \mathbf {RSW}$
, which has an
$\omega $
-left-CEA continuous degree by Lemma 6.3. In particular,
$h[B]$
contains a point of an
$\omega $
-left-CEA continuous degree and so does A since h is a computable homeomorphism and
$B\subseteq A$
.
As a corollary, we can see that every compactum
$A\subseteq [0,1]^{\mathbb {N}}$
of positive dimension contains a point of an
$\omega $
-left-CEA continuous degree. Our proof of Theorem 6.6 is essentially based on the fact that for any sequence of zero-dimensional spaces
$\{X_{i}\}_{i\in \mathbb {N}}$
, there exists a continuum avoiding all
$X_{i}$
s. Contrary to this fact, Theorem 6.7 says that
$\{X_{i}\}_{i\in \mathbb {N}}$
cannot be replaced with a sequence of totally disconnected spaces. We say that a space is
$\sigma $
-totally disconnected if it is a countable union of totally disconnected subspaces. Note that the complement of a
$\sigma $
-totally-disconnected subset of the Hilbert cube is infinite-dimensional.
Corollary 6.8. There exists a
$\sigma $
-totally-disconnected set
$X\subseteq [0,1]^{\mathbb {N}}$
such that any compact subspace of the complement
$Y=[0,1]^{\mathbb {N}}\setminus X$
is zero-dimensional.
Proof. Define
$X_{\langle i,j\rangle }$
to be the set of all points which can be identified with an element in
$\omega \mathbf {CEA}$
via the witnesses
$\Phi _{i}$
and
$\Phi _{j}$
. Then,
$X_{\langle i,j\rangle }$
is totally disconnected since it is homeomorphic to a subspace of
$\omega \mathbf {CEA}$
. Clearly, no point
$Y=[0,1]^{\mathbb {N}}\setminus \bigcup _{i,j\in \mathbb {N}}X_{\langle i,j\rangle }$
has an
$\omega $
-left-CEA continuous degree. Assume that Z is a compact subspace of Y of positive dimension. Then Z has a nondegenerated subcontinuum A. However, by Theorem 6.7, A contains a point of an
$\omega $
-left-CEA continuous degree.
6.3 Weakly Infinite-Dimensional Cantor Manifolds
Recall that a Pol-type Cantor manifold is a compact metrisable C-space which cannot be disconnected by a hereditarily weakly infinite-dimensional compact subspaces. By combining a known construction in infinite-dimensional topology, we can slightly extend Theorem 5.1 as follows.
Proposition 6.9. There exists a collection
$(\mathbf {X}_{\alpha })_{\alpha <2^{\aleph _{0}}}$
of continuum many Pol-type Cantor manifolds satisfying the following conditions:
-
1. if
$\alpha \not =\beta $
,
$\mathbf {X}_{\alpha }$
does not
$\sigma $
-embed into
$\mathbf {X}_{\beta }$
. -
2. If
$\alpha \not =\beta $
, then
$\mathbf {X}_{\alpha }$
does not finite-level Borel embed into
$\mathbf {X}_{\beta }$
. -
3. If
$\alpha \not =\beta $
, then the Banach algebra
$\mathcal {B}^{*}_{n}(\mathbf {X}_{\alpha })$
is not linearly isometric (not ring isomorphic etc.) to
$\mathcal {B}^{*}_{n}(\mathbf {X}_{\beta })$
for all
$n\in \mathbb {N}$
.
Lemma 6.10. For any
$\mathcal {G}$
, there exists a Pol-type Cantor manifold
$\mathbf {Z}(\mathcal {G})$
such that
$\omega \mathbf {CEA}\oplus \mathbf {Rea}(\mathcal {G})\equiv _{\sigma }^{\mathfrak {T}}\mathbf {Z}(\mathcal {G})$
.
Proof. Recall from Theorem 6.2 that
$\omega \mathbf {REA}$
is
$\sigma $
-homeomorphic to a strongly infinite-dimensional space
$\mathbf {RSW}$
. Let
$\mathbf {R}_{0}$
and
$\mathbf {R}_{1}$
be homeomorphic copies of
$\mathbf {RSW}$
and let
$\mathbf {X}$
be a compactification of
$\mathbf {R}_{0}\oplus \mathbf {R}_{1}\oplus \mathbf {Rea}(\mathcal {G})$
in the sense of Lelek (recall from Fact 4.1). Then,
$\mathbf {X}$
is
$\sigma $
-homeomorphic to
$\omega \mathbf {CEA}\oplus \mathbf {Rea}(\mathcal {G})$
.
We follow the construction of Elżbieta Pol [Reference Pol48, Example 4.1]. Now,
$\mathbf {R}_{0}$
has a hereditarily strongly infinite-dimensional subspace
$\mathbf {Y}$
[Reference Rubin56]. Choose a point
$p\in \mathbf {Y}$
and a closed set
$F\subseteq \mathbf {Y}$
containing p such that every separator between p and
$\mathrm{cl}_{\mathbf {X}}F$
is strongly infinite-dimensional as in [Reference Pol48, Example 4.1 (A)].
Define
$\mathbf {K}=\mathbf {X}/\mathrm{cl}_{\mathbf {X}}F$
as in [Reference Pol48, Example 4.1 (A)]. To see that
$\mathbf {K}$
is
$\sigma $
-homeomorphic to
$\mathbf {X}$
, we note that
$\mathrm{cl}_{\mathbf {X}}F\cap (\mathbf {R}_{1}\cup \mathbf {Rea}(\mathcal {G}))=\emptyset $
since
$\mathbf {R}_{0}$
,
$\mathbf {R}_{1}$
and
$\mathbf {Rea}(\mathcal {G})$
are separated in
$\mathbf {X}$
. Therefore,
$\mathrm{cl}_{\mathbf {X}}F$
is covered by the union of
$\mathbf {R}_{0}$
(which is homeomorphic to
$\mathbf {R}_{1}$
) and a countable dimensional space. Define
$\mathbf {Z}$
as a Pol-type Cantor manifold in [Reference Pol48, Example 4.1 (C)]. Then,
$\mathbf {Z}(\mathcal {G}):=\mathbf {Z}$
is the union of a finite-dimensional space and countably many copies of
$\mathbf {K}$
. Consequently,
$\mathbf {Z}(\mathcal {G})$
is
$\sigma $
-homeomorphic to
$\mathbf {Rea}(\mathcal {G})$
.
Acknowledgements
The authors are grateful to Masahiro Kumabe, Joseph Miller, Luca Motto Ros, Philipp Schlicht and Takamitsu Yamauchi for their insightful comments and discussions. The work has benefitted from the Marie Curie International Research Staff Exchange Scheme Computable Analysis, PIRSES-GA-2011-294962. For the duration of this research, the first author was partially supported by a Grant-in-Aid for JSPS fellows (FY2012–2014) and for JSPS overseas research fellows (FY2015–2016; Host: University of California, Berkeley).
Conflicts of Interest
None.
Open access
