Ideal presentations and numberings of some classes of effective quasi-Polish spaces

Abstract

The well known ideal presentations of countably based domains were recently extended to (effective) quasi-Polish spaces. Continuing these investigations, we explore some classes of effective quasi-Polish spaces. In particular, we prove an effective version of the domain-characterization of quasi-Polish spaces, describe effective extensions of quasi-Polish topologies, discover natural numberings of classes of effective quasi-Polish spaces, estimate the complexity of the (effective) homeomorphism relation and of some classes of spaces with respect to these numberings, and investigate degree spectra of continuous domains.

Keywords

Effective quasi-Polish space effective domain numbering index set degree spectrum

1. Introduction

The investigation of computability in topological structures, which is currently a hot topic in computability theory, is less straightforward than the investigation of computability in countable algebraic structures [2,10]. A reason is that it is not clear how to capture the computability issues for a topological space by a single countable algebraic structure, even when the space is Polish. Nevertheless, people often look for analogues of well-developed notions and methods of the computable structure theory in the topological context. For instance, analogues of computable categoricity turned out fruitful also in the study of computable metric spaces and Banach spaces [22,23], and analogues of degree spectra turned out interesting also for topological spaces [16,17,27].

In this paper, which is an extended version of the conference paper [6],1

¹
Sections 3, 4, 5.1, 6.2, 9 are entirely new, Section 8 is extended by new facts, other sections remain essentially the same as in [6].

we explore several classes of effective quasi-Polish (EQP-) spaces. Quasi-Polish (QP-) spaces [4] are a class of well-behaved countably based spaces that has many interesting characterizations and includes many spaces of interest in analysis and theoretical computer science, such as Polish spaces, ω-continuous domains, and countably based spectral spaces. The study of effective versions of QP-spaces was initiated in [21,26] and recently continued in [5,7,18]. In particular, it was shown that some equivalent characterizations of QP-spaces become non-equivalent in the effective setting, and it is not obvious which of the resulted notions are the “right” ones.

Theorem 11 in [7] characterizes the EQP-spaces (called there precomputable QP-spaces) as the spaces of ideals of c.e. transitive relations on ω; see also Theorem 3 in [5] for a more direct proof. This characterization is very much in the spirit of domain theory where similar characterizations of computable domains are important. It is a basic technical tool of our paper because it enables, in particular, to discover natural numberings of classes of EQP-spaces and to estimate the complexity of the (effective) homeomorphism relation and of some classes of spaces w.r.t. these numberings. Our investigation of numberings of classes of EQP-spaces is analogous to the investigation of numberings of classes of algebraic structures popular in computable structure theory; see e.g. [11–13,15,25] and references therein.

Along with the mentioned results on numberings of classes of EQP-spaces, we obtain several other results. In particular, we prove an effective version of the domain-characterization of quasi-Polish spaces [4, Theorem 53], describe effective extensions of quasi-Polish topologies which is a partial effectivisation of some results in [4, Section 14], and investigate degree spectra of continuous domains which is a continuation of the investigation of degree spectra of algebraic domains in [27] and of Polish spaces in [16,17].

After recalling some preliminaries in the next section, we discuss in Section 3 some variations of the ideal characterization of EQP-spaces. In Section 4 we apply this to the problem of extending EQP topologies.

In Section 5.1 we study ideal characterizations for classes of effective domains partly identified in [27]. This study turns out closely related to the study of computable and c.e. partial orders and some other binary relations of interest to computability theory (see e.g. [3] and references therein). In particular, our discussion leads to an effective version of a domain-characterization of quasi-Polish spaces ([4], Theorem 53) and to identifying and separating new natural classes of effective domains in Theorem 3: There is a strongly c.e. algebraic domain which is not homeomorphic to any computable algebraic domain; there is a c.e. algebraic domain which is not homeomorphic to any strongly c.e. algebraic domain; there is a c.e. domain which is not homeomorphic to any computable domain. In Section 5.2 we describe representations of computable functions between some classes of effective domains which are again based on the ideal characterizations.

In Section 6.1 we discuss natural numberings of some classes of c.e. binary relations on ω and of the corresponding classes of EQP-spaces; some of these were considered in [27]. In Section 6.2 we construct a computable numbering of all c.e. continuous domains (Theorem 6). This computable numbering gives, in a sense, a partial answer to the question of the enumerability of c.e. interpolable relations posed in the conference paper [6], and the existence of such a numbering is much less straightforward than of those in Section 6.1.

In Section 7 we characterize the complexity of (effective) homeomorphism in the introduced numberings in parallel to the similar question for algebraic structures. Theorem 7 provides precise complexity estimates for several natural classes of algebraic domains, with a heavy use of the ideal characterizations and non-trivial estimates for linear and partial orderings known in computability theory [11,12,15]). Not surprisingly, the effective homeomorphism relation (which is often arithmetical) is simpler than the homeomorphism relation (typically, complete in a level of the analytical hierarchy).

In Section 8 we establish precise estimates of index sets of some popular classes of topological spaces related to separation axioms. In particular, the results of this section imply that the properties of being a $T_{1}$ -, $T_{2}$ -, regular, and metrisable space are all $Π_{1}^{1}$ -complete with respect to the natural numbering of EQP-spaces.

We conclude in Section 9 by presenting several non-trivial facts about degree spectra of continuous domains which complement some results in [16,17,27] and some earlier facts for the discrete algebraic structures. In particular, the results of this section imply that: the class of high degrees is the degree spectrum of an irreflexive interpolable relation (Corollary 6); there exists a c.e. irreflexive interpolable relation which is not isomorphic to any X-computable relation whenever X is not high (Corollary 7); there exists a ${low}_{3}$ -c.e. irreflexive interpolable relation which is not isomorphic to any c.e. relation (Corollary 8). Similar results can be obtained for the degree spectra of ω-continuous domains instead of interpolable relations.

2. Preliminaries

Here we introduce some notation, notions and facts used throughout the paper. More special information is recalled in the corresponding sections below.

We use the standard set-theoretical notation, in particular, $Y^{X}$ is the set of functions from X to Y, and $P (X)$ is the class of subsets of a set X. All (topological) spaces in this paper are countably based $T_{0}$ ( ${cb}_{0}$ -spaces, for short). We denote the homeomorphism relation by ≃. An effective space is a pair $(X, β)$ where X is a ${cb}_{0}$ -space, and $β : ω \to P (X)$ is a numbering of a base in X such that there is a uniformly c.e. sequence ${A_{i j}}$ of c.e. sets with $β (i) \cap β (j) = \cup β (A_{i j})$ where $β (A_{i j})$ is the image of $A_{i j}$ under β. We simplify $(X, β)$ to X if β is clear from the context. Any subspace Y of an effective space $(X, β)$ is effective with the induced numbering $β_{Y} (n) = β (n) \cap Y$ of the base sets.

The effective space $(X, β)$ is c.e. (or overt) if the set ${n | β (n) \neq \emptyset}$ is c.e. A subspace of a c.e. space is not necessarily c.e. Among the effective spaces are: the discrete space $N$ of natural numbers, the Euclidean spaces $R^{n}$ , the Scott domain $P ω$ (the powerset of the natural numbers with the Scott-topology; see [1] for information about domains), the Baire space $N = N^{N}$ , the Hilbert cube ${[0, 1]}^{ω}$ ; all these spaces come with natural numberings of bases.

A function $f : (X, β) \to (Y, γ)$ is computable if it is effectively continuous; that is, given a γ-index of basic open set, one can effectively find a β-c.e. index of its preimage under f. Computability of a partial function can also be introduced via relative topology ${β (n) \cap D : n \in ω}$ on a subspace $D \subseteq X$ .

A computable function may be understood as an enumeration operator via the canonical embedding: With any effective space $(X, β)$ we associate the canonical embedding $e : X \to P ω$ defined by $e (x) = {n | x \in β (n)}$ . The canonical embedding is an effective homeomorphism between X and the subspace $e (X)$ of $P ω$ .

Here, effective spaces $(X, β)$ and $(Y, γ)$ are effectively homeomorphic if there is a computable (i.e., effectively continuous) bijection $f : X \to Y$ such that $f^{- 1}$ is also computable. The relation of effective homeomorphism of effective spaces will be denoted by $≃_{e}$ . Note that if $(X, β) ≃_{e} (Y, γ)$ then $X ≃ Y$ . All classes of effective spaces considered below will be closed under $≃_{e}$ .

In any effective space X, one can define effective versions of classical hierarchies (see e.g. [26]), in particular the effective Borel hierarchy ${Σ_{1 + n}^{0} (X)}_{n < ω}$ and the effective Luzin hierarchy ${Σ_{n}^{1} (X)}_{n < ω}$ . For $X = ω$ , these coincide with the arithmetical and analytical hierarchies, respectively.

An effective space is effective Polish (resp. effective quasi-Polish, abbreviated as EQP) if it is effectively homeomorphic to a $Π_{2}^{0}$ -subspace of the Hilbert cube (resp. the Scott domain). Note that EQP-spaces are called in [7] precomputable QP-spaces, while c.e. EQP-spaces are called computable QP-spaces. All the aforementioned examples of spaces are c.e. EQP-spaces. Moreover, all computable Polish spaces and all computable ω-continuous domains (see e.g. [26]) are c.e. EQP-spaces. However, an effective Polish space is not necessarily computable Polish (nor even $Δ_{1}^{1}$ -computable Polish; for example, consider a $Π_{1}^{0}$ subspace P of $N^{N}$ with no $Δ_{1}^{1}$ elements. If P were $Δ_{1}^{1}$ -overt, P would have a $Δ_{1}^{1}$ element).

We use the standard terminology about binary relations and about domains (see e.g. [1,27]). Given a transitive relation ρ on a set S, a subset $D \subseteq S$ is lower (with respect to ρ) if $x ρ y \in D$ implies $x \in D$ . A set $D \subseteq S$ is directed if it is nonempty and satisfies $\forall x, y \in D \exists z \in D (x ρ z \land y ρ z)$ . An ideal of $(S; ρ)$ is a directed lower subset of S. By interpolable relations we mean transitive relations ≺ on S such that any initial segment ${x | x ≺ y}$ , $y \in S$ , is directed.

We briefly recall some terminology of domain theory (see e.g. [1,9,14] for details). Let X be a $T_{0}$ -space. The specialization order $⩽_{X}$ on X is defined by: $x ⩽_{X} y$ , if $x \in U$ implies $y \in U$ , for each open set $U \subseteq X$ . Any continuous function $f : X \to Y$ is monotone w.r.t. $⩽_{X}$ , $⩽_{Y}$ . Let $K (X)$ be the set of compact elements of X, i.e. elements x such that $↑ x = {y | x ⩽_{X} y}$ is open. The approximation relation $≪_{X}$ on X is defined by: $x ≪_{X} y$ , if y is in the interior of $↑ x$ . Clearly, $≪_{X} \subseteq ⩽_{X}$ . One can see that if $x \in X$ is a compact element, then $x ≪_{X} y$ if and only if $x ⩽_{X} y$ . Note also that $x \in X$ is a compact element if and only if $x ≪_{X} x$ .

The space X is a continuous domain, if $(X; ⩽_{X})$ is directed complete and there is a set $B \subseteq X$ (called a domain basis of X) such that the sets ${x | b ≪_{X} x}$ , $b \in B$ , form a base of the topology in X, and every $x \in X$ is the directed supremum of ${b \in B | b ≪_{X} x}$ . An ω-continuous domain is a continuous domain which possesses a countable domain base. The space X is an algebraic domain, if $(X; ⩽_{X})$ is directed complete and the sets $↑ c$ , $c \in K (X)$ , form a base of the topology in X. Every algebraic domain is also a continuous domain because $K (X)$ is a domain basis. An ω-algebraic domain is an algebraic domain with countably many compact elements.

The study of some classes of EQP-spaces is closely related to the mentioned types of binary relations on ω with some effectivity conditions. Correspondingly, we assume the reader to be familiar with the basics of computability theory (see e.g. [24]), including the notions of computable, c.e., and co-c.e. binary relations. There are many interesting results about computable relations (as well as about computable and c.e. structures in general). Below we will use the following nice fact (Theorem 2.1 in [3]) about effective partial orders: There is a co-c.e. partial order on ω which is not isomorphic to any c.e. partial order, and similarly with c.e. and co-c.e. interchanged.

We conclude this section with recalling the basic fact established in Theorem 11 [7] (see also Theorem 3 in [5] for additional details).

Definition 1.
Let ≺ be a transitive relation on ω. A subset $I \subseteq ω$ is an ideal (with respect to ≺) if and only if:
$I \neq \emptyset$ , (I is non-empty)

$(\forall a \in I) (\forall b \in ω) (b ≺ a \Rightarrow b \in I)$ , (I is a lower set)

$(\forall a, b \in I) (\exists c \in I) (a ≺ c & b ≺ c)$ . (I is directed)
The collection $I (≺)$ of all ideals has the topology generated by basic open sets of the form ${[n]}_{≺} = {I \in I (≺) | n \in I}$ for $n \in ω$ . □

As shown in [7, Theorem 11], such spaces of ideals are closely related to QP-spaces, namely: a space X is quasi-Polish iff it is homeomorphic to $I (≺)$ for some transitive relation ≺ on ω. Moreover, an effective space $(X, ξ)$ is EQP iff it is computably homeomorphic to $I (≺)$ for some transitive c.e. relation ≺ on ω.
3. On ideal presentations of EQP-spaces

In this section we prove some variations of Theorem 11 in [7]. A natural related question is: which class of EQP spaces is obtained if we restrict c.e. transitive relations above to, say, computable strict partial orders. It turns out that nothing new appears (although, as we show in Section 5.1, similar variations for effective domains lead to new interesting notions).

Proposition 1.
For every c.e. transitive relation ≺ on ω, there is a computable strict partial order ⊏ on ω such that $I (≺)$ and $I (⊏)$ are computably homeomorphic.
Proof.
Let $≺^{(k)}$ be a computable relation such that $x ≺^{(k)} y$ holds if and only if $x ≺ y$ is accepted by some fixed Turing machine within k steps. Let $P_{fin} ω$ be the set of finite subsets of ω, and for $F, G \in P_{fin} ω$ and $m, n \in ω$ define $⟨ F, m ⟩ ⊏ ⟨ G, n ⟩$ if and only if the following all hold:
$F \subseteq G$ ,

$m < n$ ,

$(\forall y \in F) (\forall x ⩽ n) [x ≺^{(n)} y \Rightarrow x \in G]$ ,

$(\exists y \in G) (\forall x \in F) x ≺^{(n)} y$ .
It is easy to verify that ⊏ is computable, irreflexive, and transitive, hence it is a computable strict partial order. Define $f : I (≺) \to I (⊏)$ as $\begin{matrix} f (I) = {⟨ F, m ⟩ | F \subseteq I is finite & m \in ω}, \end{matrix}$ and define $g : I (⊏) \to I (≺)$ as $\begin{matrix} g (I) = ⋃_{⟨ F, m ⟩ \in I} F . \end{matrix}$

It is straightforward to show that f is well-defined and computable. We verify that g is well-defined, and then computability will be obvious. Fix any $I \in I (⊏)$ . It is clear that $g (I) \neq \emptyset$ . To show $g (I)$ is a lower set, assume $x ≺ y \in g (I)$ . Choose k large enough that $x ⩽ k$ and $x ≺^{(k)} y$ , and fix $⟨ F, m ⟩ \in I$ with $y \in F$ . Using the directedness of I and $(2)$ , there is $⟨ G, n ⟩ \in I$ with $⟨ F, m ⟩ ⊏ ⟨ G, n ⟩$ and $k ⩽ n$ . It follows from $(3)$ that $x \in G$ , hence $x \in g (I)$ . To prove that $g (I)$ is directed, note that for any $⟨ F, m ⟩, ⟨ G, n ⟩ \in I$ , there is $⟨ H, p ⟩ \in I$ with $⟨ F, m ⟩ ⊏ ⟨ H, p ⟩$ and $⟨ G, n ⟩ ⊏ ⟨ H, p ⟩$ , so by $(4)$ there are $x, y \in H$ satisfying $(\forall w \in F) w ≺ x$ and $(\forall w \in G) w ≺ y$ . Then again using directedness of I, there is $⟨ H^{'}, p^{'} ⟩ \in I$ with $⟨ H, p ⟩ ⊏ ⟨ H^{'}, p^{'} ⟩$ , hence $(4)$ and the transitivity of ≺ implies every pair of elements in $F \cup G$ has a ≺-upper bound in $H^{'}$ which is contained in $g (I)$ .

It only remains to show that f and g are inverses of each other. It is clear that $g (f (I)) = I$ for each $I \in I (≺)$ . It is also clear that $I \subseteq f (g (I))$ for each $I \in I (⊏)$ . To see that $f (g (I)) \subseteq I$ , fix $⟨ F, m ⟩ \in f (g (I))$ . For each $x \in F$ there is $⟨ F_{x}, m_{x} ⟩ \in I$ with $x \in F_{x}$ . Let $⟨ G, n ⟩$ be a ⊏-upper bound of ${⟨ F_{x}, m_{x} ⟩ | x \in F}$ in I, and let $⟨ H, p ⟩ \in I$ be a ⊏-upper bound of $⟨ G, n ⟩$ . Then there exists $y \in H$ such that $x ≺^{(p)} y$ for each $x \in F$ . Furthermore, from the directedness of I and $(2)$ , we can assume without loss of generality that $m < p$ . It then follows that $⟨ F, m ⟩ ⊏ ⟨ H, p ⟩ \in I$ , hence $⟨ F, m ⟩ \in I$ because I is a lower set. This completes the proof that $I (≺)$ and $I (⊏)$ are computably homeomorphic. □

Now we relate the spaces of ideals $I (≺)$ where ≺ is transitive, to the spaces $I (⊑)$ where ⊑ is a partial order on ω. Recall that an ideal of ⊑ is principal if it has a largest element w.r.t. ⊑. Proposition 2.
For any c.e. transitive relation ≺ on ω there exists a computable partial order ⊑ on ω such that $I (≺)$ is computably homeomorphic to the subspace of non-principal ideals in $I (⊑)$ .
Proof.
From Proposition 1 there is a computable strict partial order ⊏ on ω such that $I (≺)$ and $I (⊏)$ are computably homeomorphic. Define ⊑ to be the reflexive closure of ⊏. It suffices to show that any $I \subseteq ω$ is an ideal of ⊏ if and only if I is a non-principal ideal of ⊑.

Assume $I \in I (⊏)$ . Clearly $I \neq \emptyset$ . If $a ⊑ b \in I$ then since I is ⊏-directed there is $c \in I$ with $b ⊏ c$ , hence $a ⊏ c$ which implies $a \in I$ because I is a ⊏-lower set. Therefore, I is a ⊑-lower set. Since I is ⊏-directed it is clear that I is ⊑-directed and also non-principal with respect to ⊑.

Conversely, assume $I \in I (⊑)$ is non-principal. It is immediate that I is non-empty and a ⊏-lower set. Every $a, b \in I$ has a ⊑-upper bound $c \in I$ , and since I is non-principal there is $c^{'} \in I$ with $c ⊏ c^{'}$ . Therefore, $c^{'}$ is a ⊏-upper bound of a and b, which proves I is ⊏-directed. □

4. Extending EQP topologies

It is known that if countably many $Δ_{2}^{0}$ -sets are added to the topology of a quasi-Polish space then the resulting space is again quasi-Polish [4]. The following result is an effective version of this observation, but restricted to closed sets.

Theorem 1.
Given a c.e. transitive relation ≺ on ω and a c.e. set $U \subseteq ω$ , one can effectively obtain a c.e. transitive relation ⊏ on ω such that $I (⊏)$ is computably homeomorphic to the space obtained by adding $A = {I \in I (≺) | (\forall x \in U) x \notin I}$ as a c.e. open set to the topology of $I (≺)$ .
Proof.
From Proposition 1, we can assume without loss of generality that ≺ is computable. We write $U^{(n)}$ for the subset of U enumerated within n steps by some fixed Turing machine. Let $ω_{} = ω \cup {}$ , where ${}$ is a symbol not in ω. Define a c.e. transitive relation ⊏ on $(P_{fin} ω_{}) \times n$ as $⟨ F, m ⟩ ⊏ ⟨ G, n ⟩$ if and only if the following all hold:
$m < n$ ,

$* \in F \Rightarrow * \in G$ ,

$(\exists y \in G ∖ {}) (\forall x \in F ∖ {}) x ≺ y$ ,

$* \in G$ or $(\exists x \in U) x \in G$ ,

$[* \in F & y \in F ∖ {}] \Rightarrow (\forall x ⩽ n) [x \in U^{(n)} \Rightarrow x ⊀ y]$ .
It is clear that ⊏ is c.e. The only non-trivial part of proving that ⊏ is transitive is verifying that $(5)$ holds, so we will show that here. Assume $⟨ F, m ⟩ ⊏ ⟨ G, n ⟩ ⊏ ⟨ H, p ⟩$ . Assume $ \in F$ and $y \in F ∖ {}$ and that $x ⩽ p$ is in $U^{(p)}$ . Then $(2)$ implies $ \in G$ , and by $(3)$ there is $z \in G ∖ {}$ with $y ≺ z$ , and by $(5)$ we have $x ⊀ z$ . So if $x ≺ y$ then transitivity would yield $x ≺ z$ , a contradiction. Therefore, $(5)$ holds, and we obtain $⟨ F, m ⟩ ⊏ ⟨ H, p ⟩$ .

Define $g : I (⊏) \to I (≺)$ as $\begin{matrix} g (I) = ⋃_{⟨ F, m ⟩ \in I} F ∖ {} . \end{matrix}$ We first show that $g (I)$ is well-defined. $g (I)$ is non-empty because $(3)$ implies there is $⟨ G, n ⟩ \in I$ with some $y \in G ∖ {}$ . To show $g (I)$ is a lower set, assume $x ≺ y \in g (I)$ , and let $⟨ F, m ⟩ \in I$ be such that $y \in F ∖ {}$ . Since I is directed, there is $⟨ G, n ⟩ \in I$ with $⟨ F, m ⟩ ⊏ ⟨ G, n ⟩$ . By $(3)$ , there is $z \in G ∖ {}$ with $y ≺ z$ , hence $x ≺ z$ by transitivity of ≺. It follows that $⟨ {x}, m ⟩ ⊏ ⟨ G, n ⟩$ , which implies $⟨ {x}, m ⟩ \in I$ and therefore $x \in g (I)$ . The proof that $g (I)$ is directed is identical to the proof that $g (I)$ is directed in Proposition 1.

It is clear that g is computable. To see that g is injective, assume $g (I) = g (J)$ and fix any $⟨ F, m ⟩ \in I$ . This implies $F ∖ {} \subseteq g (I) = g (J)$ , hence there is a ≺-upper bound y of $F ∖ {}$ in $g (J)$ . Then there is $⟨ G, n ⟩ \in J$ with $y \in G$ , and by directedness we can assume $m < n$ and that G satisfies $(4)$ . We show $⟨ F, m ⟩ ⊏ ⟨ G, n ⟩$ . The criteria $(1)$ , $(3)$ , and $(4)$ are satisfied by the choice of G. To see that $(2)$ is satisfied, assume for a contradiction that $ \in F$ and $* \notin G$ . Since G satisfies $(4)$ , there must be $x \in U$ with $x \in G$ , and by the directedness of J there is $⟨ H, p ⟩ \in J$ with $⟨ G, n ⟩ ⊏ ⟨ H, p ⟩$ and $x ⩽ p$ and $x \in U^{(p)}$ . Then $(3)$ implies there is $z \in H$ with $x ≺ z$ , but then $(5)$ implies $⟨ H, p ⟩$ can have no ⊏-upper bound in J, which contradicts the directedness of J. Therefore, $* \in F \Rightarrow * \in G$ , hence $(2)$ is satisfied. Finally, if $* \in F$ and $F ∖ {} \neq \emptyset$ , then by directedness of I we can find some $⟨ H, p ⟩ \in I$ with $⟨ F, m ⟩ ⊏ ⟨ H, p ⟩$ and $n < p$ , and it easily follows that $(5)$ holds. Therefore, $⟨ F, m ⟩ ⊏ ⟨ G, n ⟩$ , hence $⟨ F, m ⟩ \in J$ because J is a lower set. The proof that $J \subseteq I$ is identical, hence g is injective.

To prove that g is bijective, we construct its inverse $h : I (≺) \to I (⊏)$ as $\begin{matrix} h (J) = {⟨ F, m ⟩ | F \subseteq J \cup {} is finite & m \in ω} \end{matrix}$ if $J \in A$ , and $\begin{matrix} h (J) = {⟨ F, m ⟩ | F \subseteq J is finite & m \in ω} \end{matrix}$ if $J \notin A$ . To show that $h (J)$ is well-defined, first consider the case $J \in A$ . Then $h (J)$ is clearly non-empty, and it is a lower set because if $⟨ F, m ⟩ ⊏ ⟨ G, n ⟩ \in h (J)$ , then $(3)$ implies G contains a ≺-upper bound of F, hence $F \subseteq J$ because J is a lower set. To see that $h (J)$ is directed, assume $⟨ F, m ⟩, ⟨ G, n ⟩ \in h (J)$ , and let $y \in J$ be a ≺-upper bound of $(F \cup G) ∖ {}$ . Set $H = {y, }$ and $p = m + n + 1$ . Then $⟨ H, p ⟩ \in h (J)$ is a ⊏-upper bound of $⟨ F, m ⟩$ and $⟨ G, n ⟩$ , which proves $h (J) \in I (⊏)$ . The case when $J \notin A$ is similar, except when proving that $h (J)$ is directed, we use the fact that there exists $x \in U \cap J$ when constructing a ⊏-upper bound of a pair of elements of $h (J)$ so that it satisfies $(4)$ . In either case, we clearly have $g (h (J)) = J$ , hence g is a computable bijection and h is its inverse.

Finally, it is clear that $g^{- 1} (A)$ is a c.e. open subset of $I (⊏)$ , and although h is not computable on its whole domain $I (≺)$ in general, the additional information needed to compute h is precisely whether or not the input J is in A. More precisely, h can be viewed as a computable homeomorphism from the disjoint union of A and $I (≺) ∖ A$ to $I (⊏)$ . Therefore, $I (⊏)$ is computably homeomorphic to the space obtained by adding A as a c.e. open set to the topology of $I (≺)$ . □

Using the construction of countable products and equalizers described in [4], we can easily generalize the above theorem to handle c.e. sequences of co-c.e. closed sets. Corollary 1.
Given a c.e. transitive relation ≺ on ω and a c.e. sequence ${(A_{i})}_{i \in ω}$ of co-c.e. closed subsets of $I (≺)$ , one can compute a c.e. transitive relation ⊏ on ω such that $I (⊏)$ is computably homeomorphic to the space obtained by adding each $A_{i}$ ( $i \in ω$ ) as a c.e. open set to the topology of $I (≺)$ .
Proof.
Let $⊏_{i}$ be the c.e. transitive relation obtained from the previous theorem for the space with $A_{i}$ joined to the topology of $I (≺)$ , let $⊏^{'}$ be a c.e. encoding for the product of these spaces, and let ⊏ be a c.e. encoding for the diagonal of $I (⊏^{'})$ , obtained as the equalizer of the computable functions ${(x_{i})}_{i \in ω} \mapsto {(g_{i} (x_{i}))}_{i \in ω}$ and ${(x_{i})}_{i \in ω} \mapsto {(g_{0} (x_{0}))}^{ω}$ , where $g_{i}$ is the bijection from $I (⊏_{i})$ to $I (≺)$ used in the proof of the above theorem. Then ⊏ satisfies the corollary. □

5. Representing effective domains and computable functions

5.1. Ideal presentations of effective domains

Here we establish ideal characterizations of some effective versions of domains. Let us first recall definitions of two classes of effective domains (one of which is known while the other recently introduced in [27]). We warn the reader that the adjectives “computable” and “c.e.” are sometimes used in the literature inconsistently.

Definition 2.
By a computable domain we mean a pair $(X, b)$ where X is an ω-continuous domain and $b : ω \to X$ is a numbering of a domain base in X such that the relation $b_{i} ≪_{X} b_{j}$ is computable, where $≪_{X}$ is the approximation relation on X. The notion of c.e. domain is obtained by using “c.e.” instead of “computable”.

For algebraic domains, we have at least three natural versions of effectiveness.
Definition 3.

By a computable algebraic domain we mean a pair $(X, c)$ where X is an ω-algebraic domain and $c : ω \to X$ is a numbering of the compact elements in X such that the relation $c_{i} ⩽_{X} c_{j}$ is computable, where $⩽_{X}$ is the specialization order on X.

By a strongly c.e. algebraic domain we mean either a finite domain or a pair $(X, c)$ where X is an ω-algebraic domain and $c : ω \to X$ is a bijective numbering of the compact elements in X such that the relation $c_{i} ⩽_{X} c_{j}$ is c.e.

By a c.e. algebraic domain we mean a pair $(X, c)$ where X is an ω-algebraic domain and $c : ω \to X$ is a numbering of the compact elements in X such that the relation $c_{i} ⩽_{X} c_{j}$ is c.e.

Notions (1) and (2) were introduced in [27] while notion (3) is sometimes met in the literature under the name “computable ω-algebraic domain”. It is easy to see that any computable algebraic domain is strongly c.e. and any strongly c.e. algebraic domain is c.e. The next result is a reformulation of some well known facts of domain theory [1]. It was announced without a proof in [27] as Proposition 2; here we provide a proof, for the sake of completeness.
Proposition 3.

A topological space is an ω-continuous domain iff it is homeomorphic to $I (≺)$ for some transitive interpolable relation ≺ on ω.

A topological space is an ω-algebraic domain iff it is homeomorphic to $I (⊑)$ for some preorder ⊑ on ω.

An infinite topological space is an ω-algebraic domain iff it is homeomorphic to $I (⊑)$ for some partial order ⊑ on ω.

Proof.
(1) Let ≺ be a transitive interpolable relation on ω. It is well known (see e.g. Proposition 2.2.22 in [1]) that $I (≺)$ is an ω-continuous domain. Conversely, let X be an ω-continuous domain and $b : ω \to X$ be a numbering of a domain basis. Define the relation ≺ on ω by: $i ≺ j$ , if $b_{i} ≪_{X} b_{j}$ . Then ≺ is a transitive interpolable relation on ω, and X is homeomorphic to $I (≺)$ via $f (x) = {i | b_{i} ≪_{X} x}$ .

(2) Let ⊑ be a preorder on ω. It is well known that $I (⊑)$ is an ω-algebraic domain the compact elements of which are the principal ideals (note also that $I (⊑)$ is homeomorphic to $I (ω^{}; ⊑^{})$ , where $(ω^{}; ⊑^{})$ is the quotient-order of $(ω, ⊑)$ ). Conversely, let X be an ω-algebraic domain and $c : ω \to X$ be a numbering of the compact elements. Define the preorder ⊑ on ω by: $i ⊑ j$ , if $c_{i} ⩽_{X} c_{j}$ . Then X is homeomorphic to $I (⊑)$ via $f (x) = {i | c_{i} ⩽_{X} x}$ .

(3) Similarly to (2). □

We proceed with effective versions of the above proposition for algebraic domains (for continuous domains such a direct effectivization is probably not known); see also Section 4. The next fact was stated in [27] without proof.
Proposition 4.

An effective space is a computable (resp. c.e.) algebraic domain iff it is effectively homeomorphic to $I (⊑)$ for some computable (resp. c.e.) preorder ⊑ on ω.

An infinite effective space is a computable (resp. strongly c.e.) algebraic domain iff it is effectively homeomorphic to $I (⊑)$ for some computable (resp. c.e.) partial order ⊑ on ω.

Proof.
(1) Let ⊑ be a computable preorder on ω. Then $(I (⊑); c)$ , where $c_{i} = ↓ i = {j | j ⊑ i}$ , is a computable domain because $c_{i} \subseteq c_{j}$ iff $i ⊑ j$ . Conversely, let $(X, c)$ be a computable algebraic domain. Define the computable preorder ⊑ on ω by: $i ⊑ j$ , if $c_{i} ⩽_{X} c_{j}$ . Then ⊑ has the desired properties. The same argument works for the c.e. case.

(2) Let ⊑ be a computable partial order on ω. Then $(I (⊑), c)$ , where c is as in item (1), is an infinite computable domain. Conversely, let $(X, c^{'})$ be an infinite computable algebraic domain. Since $K (X)$ is infinite, it is straightforward to modify $c^{'}$ and obtain an injective numbering $c : ω \to X$ of the compact elements, preserving the computability of the relation $c_{i} ⩽_{X} c_{j}$ . Then proceed as above. A similar argument works for the strong c.e. case. □

Although we assume the Scott topology on ω-algebraic domains in this paper, the Lawson topology also has useful applications (see [14]). The Lawson topology on a domain X refines the Scott topology on X by adding all sets of the form $X ∖ ↑ x$ as open sets. For algebraic domains, it suffices to only add sets of the form $X ∖ ↑ x$ for $x \in K (X)$ to obtain the Lawson topology (see the hint after Exercise III-1.14 in [14]). Using Corollary 1 and Proposition 4, we obtain the following partial effectivization of the known fact that an ω-algebraic domain with the Lawson topology is a (zero-dimensional) Polish space.
Corollary 2.
If X is a computable (or c.e.) algebraic domain, then X with the Lawson topology is an effective quasi-Polish space. □

Next we prove an effective version of the following domain-characterization of quasi-Polish spaces established in [4]: a space is quasi-Polish iff it is homeomorphic to the space of non-compact elements of an ω-algebraic (equivalently, of an ω-continuous) domain.
Theorem 2.
For an effective space $(X, ξ)$ the following are equivalent:
$(X, ξ)$ is an effective quasi-Polish space.

$(X, ξ)$ is computably homeomorphic to the space of non-compact elements of a computable algebraic domain.

$(X, ξ)$ is computably homeomorphic to the space of non-compact elements of a computable domain.

Proof.
(1) → (2). By Proposition 1, X is computably homeomorphic to $I (≺)$ for some computable strict partial order ≺ on ω. By Proposition 2, X is computably homeomorphic to the subspace of non-principal ideals in $I (⊑)$ , for some computable partial order ⊑ on ω. By Proposition 4(1), $I (⊑)$ is a computable algebraic domain.

The implication (2) → (3) is obvious since every computable algebraic domain is a computable domain.

(3) → (1). Let $(Y, b)$ be a computable domain and let X be computably homeomorphic to $Y ∖ K (Y)$ . Since Y is EQP, it suffices to show that $K (Y) \in Σ_{2}^{0} (Y)$ [7,18]. The set $C = {i | b_{i} ≪_{Y} b_{i}}$ is computable and $K (Y) = {b_{i} | i \in C}$ , hence it suffices to check that ${b_{i}} \in Σ_{2}^{0} (Y)$ uniformly on $i \in C$ . We have $\begin{matrix} {b_{i}} = {y | b_{i} ⩽_{Y} y} ∖ {y | y ≰_{Y} b_{i}} = {y | b_{i} ⩽_{Y} y} ∖ ⋃_{b_{j} ⊀_{Y} b_{i}} {y | b_{j} ≺_{Y} y} . \end{matrix}$ This is because $y ⩽_{Y} b_{i}$ iff, for any j, $b_{j} ≪_{Y} y$ implies $b_{j} ≪_{Y} b_{i}$ . Since the relation $b_{j} {≪̸}_{Y} b_{i}$ is computable, the desired estimate follows. □

Next we show that the effective versions of algebraic domains introduced above are non-equivalent. For this we use Theorem 2.1 in [3] cited in Section 2, and Theorem 1 in [27] equivalent to following fact about c.e. preorders on ω.
Proposition 5.
There is a c.e. preorder ⊑ on ω whose quotient-order $(ω^{}; ⊑^{})$ is infinite and not isomorphic to any c.e. partial order on ω.

We use this proposition to obtain the following fact which was also announced in [27] without proof: Theorem 3.

There is a strongly c.e. algebraic domain which is not homeomorphic to any computable algebraic domain.

There is a c.e. algebraic domain which is not homeomorphic to any strongly c.e. algebraic domain.

There is a c.e. domain which is not homeomorphic to any computable domain.

Proof.
(1) By Theorem 2.1 in [3], there is a c.e. partial order ⊑ on ω which is not isomorphic to any computable partial order on ω. We claim that the space $X = I (⊑)$ has the desired properties. Indeed, by Proposition 4(2) X (with a natural numbering of the compact elements) is a strongly c.e. algebraic domain. Suppose, for a contradiction, that X is homeomorphic to a computable algebraic domain $(Y, c)$ , and let $f : X \to Y$ be a homeomorphism. As noticed in the proof of Theorem 2 in [27], the restriction of f to $K (X)$ is an isomorphism between $(K (X); ⩽_{X})$ and $(K (Y); ⩽_{Y})$ . By Proposition 4, $(K (X); ⩽_{X})$ and $(K (Y); ⩽_{Y})$ are isomorphic respectively to $(ω, ⊑)$ and to $(ω, ⊑_{Y})$ , for some computable partial order $⊑_{Y}$ on ω. Thus, the latter two partial orders are isomorphic. A contradiction.

(2) Let ⊑ be the preorder on ω from Proposition 5. The same argument as in item (1) shows that the space $X = I (⊑)$ has the desired properties because $(K (X); ⩽_{X})$ is isomorphic to $(ω^{}; ⊑^{})$ by Proposition 4.

(3) Let $(X, c)$ be the space from the proof of item (1), then $(X, c)$ is an infinite c.e. domain. Suppose for a contradiction that X is homeomorphic to Y for some computable domain $(Y, b)$ . Let $C = {i | b_{i} ≪_{Y} b_{i}}$ , then, as a base must contain all compact elements, $C = {i_{0} < i_{1} < \dots}$ is an infinite computable set and $(Y, {b_{i_{j}}}_{j})$ is a computable algebraic domain. This contradicts item (1). □

5.2. Representing computable functions

Here we describe useful representations of computable functions between EQP spaces and effective domains.

First we briefly recall some notions and facts from Section 2.2.6 of [1]. Let $A = (A; ≺_{1})$ and $B = (B; ≺_{2})$ be interpolable relations on arbitrary sets A, B; we denote the elements of A as $a, a^{'}, \dots$ , and similarly for B. We say that a set $R \subseteq A \times B$ is a morphism from $A$ to $B$ (in symbols, $R : A \to B$ ) if it satisfies the following conditions: if $a R b$ and $a ≺_{1} a^{'}$ then $a^{'} R b$ ; if $a R b$ and $b^{'} ≺_{2} b$ then $a R b^{'}$ ; for any a there is b with $a R b$ ; for all a, b, $b^{'}$ with $a R b$ , $a R b^{'}$ there is $b^{″}$ with $b ≺_{2} b^{″}$ , $b^{'} ≺_{2} b^{″}$ , and $a R b^{″}$ ; if $a R b$ then $a^{'} R b$ for some $a^{'} ≺_{1} a$ (cf. Definition 2.2.27 in [1]).

By Theorem 2.2.28 in [1], the category $INT$ of the interpolable relations $A$ and the just defined morphisms is equivalent to the category $CONT$ of continuous domains as objects and continuous functions as morphisms. The equivalence is given by the functors $I : INT \to CONT$ and $B : CONT \to INT$ defined as follows. Let $I (A)$ be the space of ideals of $A$ , and, for $R : A \to B$ , $I (R) : I (A) \to I (B)$ be the image map $⌜ R ⌝ (J) = {b | \exists a \in J (a R b)}$ , $J \in I (A)$ . For an object X of $CONT$ let $B (X) = (X; ≪_{X})$ , and for a morphism $f : X \to Y$ of $CONT$ let $B (f) = {(x, y) | y ≪_{Y} f (x)}$ .

By Theorem 2.2.29 in [1], the full subcategory $PRE$ of $INT$ formed by the arbitrary preorders $A = (A; ⊑)$ as objects, is equivalent to the full subcategory $ALG$ of $CONT$ formed by the algebraic domains as objects. The equivalence is given by the functors $I_{PRE} : PRE \to ALG$ and $K : ALG \to PRE$ where $I_{PRE}$ is the restriction of I to $PRE$ , $K (X)$ is the restriction of $⩽_{X}$ to the set of compact elements in X, and, for a morphism $f : X \to Y$ of $ALG$ , let $K (f) = {(x, y) | x \in K (X) \land y \in K (Y) \land y ⩽_{Y} f (x)}$ .

Now we describe effective versions of the cited results for the classes of effective algebraic domains from Proposition 4. The effectivization of Theorem 2.2.28 in [1] is currently not clear. The problem is that the functor I increases the algorithmic complexity (while the effective version of the functor B, $B_{e} (X, b) = (ω; ≺)$ where $m ≺ n \leftrightarrow b (m) ≪_{X} b (n)$ , preserves the algorithmic complexity).

Let ${ALG}_{e}$ (resp. ${ALG}_{s}$ , resp. ${ALG}_{c}$ ) be the category of c.e. (resp. infinite strongly c.e., resp. computable) algebraic domains as objects and the computable functions as morphisms. Let ${PRE}_{e}$ (resp. ${PRE}_{s}$ , resp. ${PRE}_{c}$ ) be the category of c.e. preorders (resp. c.e. partial orders, resp. computable preorders) on ω; the morphisms in all three categories are c.e. morphisms of $PRE$ restricted to the objects of these categories. Let ≃ denote the equivalence of categories.

Theorem 4.
We have: ${PRE}_{e} ≃ {ALG}_{e}$ , ${PRE}_{s} ≃ {ALG}_{s}$ , ${PRE}_{c} ≃ {ALG}_{c}$ .
Proof.
We only define the functors witnessing the equivalences, leaving the straightforward checking of their properties to the reader. Define $I_{e} : {PRE}_{e} \to {ALG}_{e}$ as follows: $I_{e} (ω; ⊑) = (I (⊑), b)$ where $b (n) = {m | m ⊑ n}$ , and for a morphism $R : (ω; ⊑_{1}) \to (ω; ⊑_{2})$ let $I_{e} (R)$ be the image map $⌜ R ⌝$ restricted to $I (⊑_{1})$ . Define $B_{e} : {ALG}_{e} \to {PRE}_{e}$ as follows: if $(X, b)$ is a c.e. algebraic domain then let $B_{e} (X, b) = (ω; ⊑)$ where $m ⊑ n \leftrightarrow b (m) ⩽_{X} b (n)$ , and if $f : (X, b) \to (Y, c)$ is a computable function then let $B_{e} (f) = {(m, n) | c (n) ⩽_{Y} f (b (m))}$ . Then $I_{e}$ , $B_{e}$ are witnesses for ${INT}_{e} ≃ {ALG}_{e}$ The witnesses for the remaining two equivalences are obvious restrictions of $I_{e}$ , $B_{e}$ . □

We conclude this section with remarks on representing functions between QP-spaces represented as spaces of ideals $I (≺_{1})$ and $I (≺_{2})$ . We define a code for a partial function to be any subset $R \subseteq ω \times ω$ . Each code R encodes the partial function $⌜ R ⌝ : \subseteq I (≺_{1}) \to I (≺_{2})$ defined as $\begin{aligned} ⌜ R ⌝ (I) = {n \in ω | (\exists m \in I) ⟨ m, n ⟩ \in R}, \\ dom (⌜ R ⌝) = {I \in I (≺_{1}) | ⌜ R ⌝ (I) \in I (≺_{2})} . \end{aligned}$

The following fact is Theorem 2 from [5].2
²
In the original paper, the statement of the theorem incorrectly omitted the requirement that $≺_{1}$ be a c.e. relation. We are grateful to Ivan Georgiev for pointing out this mistake and providing a counter example.

Theorem 5.
Let $≺_{1}$ and $≺_{2}$ be c.e. transitive relations on ω. A total function $f : I (≺_{1}) \to I (≺_{2})$ is computable if and only if there is a c.e. code $R \subseteq ω \times ω$ such that $f = ⌜ R ⌝$ . □

6. Enumerating classes of spaces

6.1. Some natural numberings

Here we introduce and study natural numberings of some classes of relations on ω and of EQP-spaces. Some of these may be defined directly from the definitions of Section 2. For any effective space X, let $π_{X}$ be the standard numbering of $Π_{2}^{0}$ -subspaces of X. In the particular case $X = P ω$ we obtain the numbering $π = π_{X}$ of all (up to $≃_{e}$ ) EQP-spaces. In the particular case $X = {[0, 1]}^{ω}$ , $π_{X}$ is a numbering of all effective Polish spaces (because, up to homeomorphism, Polish spaces are precisely the $Π_{2}^{0}$ -subspaces of the Hilbert cube, see e.g. Theorem 4.14 in [19]); setting $μ (n) = e (π_{X} (n))$ , where e is the canonical embedding of ${[0, 1]}^{ω}$ into $P ω$ , we obtain a numbering μ of effective Polish spaces realised as $Π_{2}^{0}$ -subspaces of $P ω$ .

Other natural numberings of spaces are defined using the ideal representations. We first define some numberings of classes of relations on ω. Setting $V_{n} = {(i, j) | ⟨ i, j ⟩ \in W_{n}}$ , we obtain a standard computable numbering ${V_{n}}$ of the class E of all c.e. binary relations on ω. Let T, I, P, O be the classes of all transitive c.e. relations, all interpolable c.e. relations, all c.e. preorders, and all c.e. partial orders on ω, respectively.

Proposition 6.

There is a computable function t such that: $V_{t (n)} \in T$ , $V_{n} \in T$ implies $V_{n} = V_{t (n)}$ , and $V_{m} = V_{n}$ implies $V_{t (m)} = V_{t (n)}$ .

There is a computable function p such that: $V_{p (n)} \in P$ , $V_{n} \in P$ implies $V_{n} = V_{p (n)}$ , and $V_{m} = V_{n}$ implies $V_{p (m)} = V_{p (n)}$ .

There is a computable function o such that: $V_{o (n)} \in O$ , and $V_{n} \in O$ implies $V_{n} = V_{o (n)}$ .

Proof.
(1) As t we can take arbitrary computable function such that $V_{t (n)}$ is the transitive closure of $V_{n}$ (such a function obviously exists).

(2) As p we can take arbitrary computable function such that $V_{p (n)}$ is the reflexive transitive closure of $V_{n}$ (such a function obviously exists).

(3) Given a computable step-wise enumeration of ${V_{p (n)}}$ , it is straightforward to construct a computable sequence ${A_{n}}$ of c.e. partial orders on ω such that: $A_{n} \subseteq V_{p (n)}$ ; if $V_{p (n)}$ is a partial order then $A_{n} = V_{p (n)}$ ; if $V_{p (n)}$ is not a partial order then almost all elements of $A_{n}$ are pairwise incomparable. As o we can take arbitrary computable function such that $V_{o (n)} = A_{n}$ . □

We thank an anonymous referee of the conference version of this paper for showing that there is no function o as in item (3) with the additional property that $V_{m} = V_{n}$ implies $V_{o (m)} = V_{o (n)}$ .
Corollary 3.
The classes T , P , O have computable numberings, namely the numberings ${V_{t (n)}}$ , ${V_{p (n)}}$ , ${V_{o (n)}}$ , respectively.

Compared to other classes, the method of enumerating the class I of interporable c.e. relations is not at all clear. The complexity of interpolability is one of the reasons why it is difficult to enumerate I in a simple way.
Proposition 7.
Deciding whether a given c.e. transitive relation is interpolable is $Π_{2}^{0}$ -complete.
Proof.
It is clear that this decision is $Π_{2}^{0}$ . For completeness, consider the standard strict ordering $<_{Q}$ of the rational numbers $Q = {q_{i} : i \in N}$ , which is clearly interpolable. For any $Π_{2}^{0}$ formula $φ (n) \equiv \forall a \exists b θ (n, a, b)$ , consider the restriction of $<_{Q}$ to $Q_{n} = {q_{i} : \forall a < i \exists b θ (n, a, b)}$ , which is c.e. If $φ (n)$ is true, then $Q_{n} = Q$ ; otherwise $Q_{n}$ is finite. Note that the strict order $<_{Q}$ restricted to a finite set cannot be interpolable. □

We do not know whether the class I has a computable numbering but by Proposition 7 we can define a natural non-computable one ${V_{i (n)}}$ where i is the $\emptyset^{″}$ -computable function which enumerates the $Π_{2}^{0}$ -set ${m | V_{t (m)} \in I}$ in the increasing order. For the moment, let j, c be $\emptyset^{″}$ -computable functions which enumerate the $Σ_{3}^{0}$ -sets ${m | V_{t (m)} is computable}$ and ${m | V_{p (m)} is computable}$ , respectively. We return to this issue again in Section 6.2 to show that a subclass of I large enough to represent all homeomorphism types of effective ω-continuous domains has a computable numbering.

Theorem 11 in [7], Corollary 3, and Propositions 3,4 in [27] imply that ${I (V_{t (n)})}$ , ${I (V_{p (n)})}$ , ${I (V_{o (n)})}$ , ${I (V_{c (n)})}$ are numberings of all (up to $≃_{e}$ ) EQP-spaces, positive algebraic domains, c.e. algebraic domains, and computable algebraic domains, respectively (see [27] for precise definitions and a discussion of these classes of domains); we sometimes denote these numberings by ι, α, β, γ, respectively. Sequences ${I (V_{i (n)})}$ and ${I (V_{j (n)})}$ are numberings of natural classes of ω-continuous domains, which we also denote by δ and ε, respectively. Below is a summary of the introduced numberings.

μ: Standard numbering of $Π_{2}^{0}$ -subspaces of ${[0, 1]}^{ω}$ .

π: Standard numbering of $Π_{2}^{0}$ -subspaces of $P ω$ .

ι: Numbering of EQP-spaces derived from the computable numbering ${V_{t (n)}}$ of c.e. transitive relations (T).

α: Numbering of positive algebraic domains derived from the computable numbering ${V_{p (n)}}$ of c.e. preorders (P).

β: Numbering of c.e. algebraic domains derived from the computable numbering ${V_{o (n)}}$ of c.e. partial orders (O).

γ: Numbering of computable algebraic domains derived from the $\emptyset^{″}$ -computable numbering of computable partial orders.

δ: Numbering of ω-continuous domains derived from the $\emptyset^{″}$ -computable numbering ${I (V_{i (n)})}$ of interpolable c.e. relations (I).

ε: Numbering of ω-continuous domains derived from the $\emptyset^{″}$ -computable numbering ${I (V_{j (n)})}$ of interpolable computable relations.

The next proposition compares the introduced numberings under the following preorder on the numberings of effective spaces: $ν ⩽_{e} ν^{'}$ , if $ν (n) ≃_{e} ν^{'} (f (n))$ for some computable function f; let $\equiv_{e}$ be the equivalence relation induced by $⩽_{e}$ . For an oracle h, let $⩽_{e}^{h}$ and $\equiv_{e}^{h}$ be the h-relativizations of $⩽_{e}$ and $\equiv_{e}$ , respectively. The presence of oracles in some of the reductions below is explained by the fact that numberings γ, δ, ε are defined in a less constructive way than the other numberings.
Proposition 8.
We have: $μ ⩽_{e} π \equiv_{e} ι$ , $β ⩽_{e} α ⩽_{e} ι$ , $ε ⩽_{e}^{\emptyset^{″}} δ ⩽_{e}^{\emptyset^{″}} ι$ , and $γ ⩽_{e}^{\emptyset^{″}} α$ . The binary operations of product and coproduct are represented by computable functions in any of the numberings μ, π, ι, α, γ (again, up to $\equiv_{e}$ ).
Proof.
The relation $π \equiv_{e} ι$ follows from the effectivity of proofs of Theorem 11 in [7] and Theorem 3 in [5]. The relation $μ ⩽_{e} π$ follows from Theorem 1 in [18] because the Hilbert cube is a computable Polish space. The remaining relations follow from the definition of the numbering and of functions i, j, c, and from Proposition 6. The assertion about product and coproduct is checked in a straightforward way, similar to Sections 3.1 and 3.2 in [5]. □

May the non-computable numberings γ, δ, ϵ be improved to computable numberings of the corresponding classes of EQP-spaces? In Section 6.2 we give a positive answer for the case of δ.
6.2. Enumerating continuous domains

As shown in Proposition 3, ω-continuous domains can be represented by interpolable transitive relations. However, as described in Section 6.1 (also in [6]), it is not at all clear how to provide a computable numbering for all c.e. interpolable relations. In this section, we address this issue. Although it is still unknown whether there exists a computable enumeration of all c.e. interpolable transitive relations on $N$ , we will show in this section that there exists a computable enumeration of the corresponding ω-continuous domains (up to computable homeomorphism). This was unknown at the time of [6], and we present the result here for the first time.

Lemma 1.
Let $(X, ≺_{X})$ and $(Y, ≺_{Y})$ be sets equipped with (c.e.) transitive relations. Assume $f : X \to Y$ is a (computable) function satisfying
f is surjective, and

$x ≺_{X} x^{'} ⟺ f (x) ≺_{Y} f (x^{'})$ .
Let $G_{f} = {⟨ x, f (x) ⟩ | x \in X}$ be the graph of f. Then $⌜ G_{f} ⌝ : I (≺_{X}) \to I (≺_{Y})$ is a (computable) homeomorphism.
Proof.
First we show that $x \in I$ if and only if $f (x) \in ⌜ G_{f} ⌝ (I)$ . If $x \in I$ then $f (x) \in ⌜ G_{f} ⌝ (I)$ by definition of $⌜ G_{f} ⌝$ . Conversely, if $f (x) \in ⌜ G_{f} ⌝ (I)$ , then there must be some $x^{'} \in I$ with $f (x^{'}) = f (x)$ . By directedness of I there is $x^{″} \in I$ with $x^{'} ≺_{X} x^{″}$ . Then $f (x) = f (x^{'}) ≺_{Y} f (x^{″})$ hence our assumption on f implies $x ≺_{X} x^{″}$ , and it follows from I being a lower set that $x \in I$ .

Next we show that $⌜ G_{f} ⌝ (I) \in I (≺_{Y})$ for each $I \in I (≺_{X})$ . We use the assumption that f is surjective in the following.
( $⌜ G_{f} ⌝ (I)$ is non-empty): There is $x \in I$ , hence there is $f (x) \in ⌜ G_{f} ⌝ (I)$ .

( $⌜ G_{f} ⌝ (I)$ is a lower set): Assume $f (x) ≺_{Y} f (x^{'}) \in ⌜ G_{f} ⌝ (I)$ . Then $x ≺_{X} x^{'} \in I$ , hence $x \in I$ . Therefore, $f (x) \in ⌜ G_{f} ⌝ (I)$ .

( $⌜ G_{f} ⌝ (I)$ is directed): Assume $f (x_{0}), f (x_{1}) \in ⌜ G_{f} ⌝ (I)$ . Then $x_{0}, x_{1} \in I$ so there is $x \in I$ with $x_{0} ≺_{X} x$ and $x_{1} ≺_{X} x$ . Therefore, $f (x) \in ⌜ G_{f} ⌝ (I)$ and $f (x_{0}) ≺_{Y} f (x)$ and $f (x_{1}) ≺_{Y} f (x)$ .
It follows from Theorem 5 that $⌜ G_{f} ⌝ : I (≺_{X}) \to I (≺_{Y})$ is a total computable function.

Next we show that $⌜ G_{f} ⌝$ is surjective. Given $J \in I (≺_{Y})$ , set $I = f^{- 1} (J)$ . Then
$I \neq \emptyset$ because $J \neq \emptyset$ and f is surjective.

I is a lower set, because if $x ≺_{X} x^{'} \in I$ then $f (x) ≺_{Y} f (x^{'}) \in J$ , hence $f (x) \in J$ , which implies $x \in I$ .

I is directed, because if $x_{0}, x_{1} \in I$ , then there is $y \in J$ with $f (x_{0}) ≺_{Y} y$ and $f (x_{1}) ≺_{Y} y$ , so from the surjectivity of f there is $x \in I$ with $f (x) = y$ and satisfying $x_{0} ≺_{X} x$ and $x_{1} ≺_{X} x$ .

Finally, since $I \in {[x]}_{≺_{X}}$ if and only if $⌜ G_{f} ⌝ (I) \in {[f (x)]}_{≺_{Y}}$ , it follows that $⌜ G_{f} ⌝$ is a computable homeomorphism. □
Theorem 6.
There exists a computable enumeration of all EQP ω-continuous domains.
Proof.
Let $(Y, ≺_{Y})$ be a set equipped with a c.e. transitive relation. We will define a c.e. subset $X \subseteq N$ and c.e. interpolable transitive relation $≺_{X}$ on X and a computable function $f : X \to Y$ . We think of $2 n \in N$ as corresponding to $n \in Y$ , and view $2 n + 1 \in N$ as being a dummy symbol $w_{n}$ .

Let $≺_{Y}^{(s)}$ be a finite approximation of $≺_{Y}$ at stage s. Let ${(F_{n}, y_{n})}_{n \in N}$ be an enumeration of $P_{fin} (N) \times N$ , such that $x \in F_{n}$ implies $x < n$ . Define the partial function $f^{(0)} : \subseteq N \to Y$ as having only even numbers in its domain, and set $f^{(0)} (2 n) = n$ . Let $≺_{X}^{(0)}$ be the empty binary relation on $N$ .

At each stage s, each dummy symbol $w_{k}$ is inactive at stage 0, but may become active at a later stage. An active dummy symbol $w_{k}$ may later become replaced. A pair $(F_{n}, y_{n})$ requires attention at stage s if each element of $F_{n} \cup {y_{n}}$ is active (and/or replaced) at stage s and furthermore $x ≺_{X}^{(s)} y_{n}$ holds for each $x \in F_{n}$ . Then we say that z solves such $(F_{n}, y_{n})$ if $x ≺_{X}^{(s)} z ≺_{X}^{(s)} y_{n}$ holds for each $x \in F_{n}$ .

Do each of the following substages for each stage $s ⩾ 0$ .
Substage 1: Let $n < s$ be least unsolved pair $(F_{n}, y_{n})$ requiring attention (if such a pair does not exist then go to the next substage). Let $w_{k}$ be the least inactive dummy, and set $x ≺_{X}^{(s + 1)} w_{k} ≺_{X}^{(s + 1)} y_{n}$ for each $x \in F_{n}$ . Declare $w_{k}$ active and $(F_{n}, y_{n})$ solved.

Substage 2: If $w_{k}$ is the least dummy symbol that is active but not replaced, and $w_{k}$ solves $(F_{n}, y_{n})$ , then we can assume $f^{(s)}$ is already defined for all elements in $F_{n} \cup {y_{n}}$ , so we search for $z \in Y$ with $f (x) ≺_{Y}^{(s + 1)} z ≺_{Y}^{(s + 1)} f (y_{n})$ for each $x \in F_{n}$ . If such z is found, then declare $w_{k}$ to be replaced and extend $f^{(s)}$ to $f^{(s + 1)}$ by adding $2 k + 1$ to its domain and defining $f^{(s + 1)} (2 k + 1) = z$ . If no such z is found then set $f^{(s + 1)} = f^{(s)}$ .

Substage 3: Further extend $≺_{X}^{(s + 1)}$ so that $x ≺_{X}^{(s + 1)} x^{'}$ whenever $f (x)$ and $f (x^{'})$ are defined and $f (x) ≺_{Y}^{(s + 1)} f (x^{'})$ .

Substage 4: Complete $≺_{X}^{(s + 1)}$ by adding $≺_{X}^{(s)}$ and taking the transitive closure. Then go to stage $s + 1$ .
Set $\begin{matrix} X = {2 n | n \in N} \cup {2 n + 1 | w_{n} becomes active at some stage} . \end{matrix}$ Define $≺_{X} = ⋃_{s \in N} ≺_{X}^{(s)}$ and $f = ⋃_{s \in N} f^{(s)}$ . It is clear that X and $≺_{X}$ are c.e. Furthermore, Substage 4 guarantees that $≺_{X}$ is transitive, and Substage 1 guarantees that it is interpolable.

Next, consider the case that $≺_{Y}$ is interpolable. Then $f : X \to Y$ is a total function because each activated dummy symbol is eventually replaced in Substage 2. It is also clear that f is computable, and that it is a surjection because $f (2 n) = n$ . Furthermore, Substage 3 guarantees that $f (x) ≺_{Y} f (x^{'})$ implies $x ≺_{X} x^{'}$ . We show that conversely, if $x ≺_{X} x^{'}$ then $f (x) ≺_{Y} f (x^{'})$ . We consider the different cases that $x ≺_{X} x^{'}$ was added to the relation $≺_{X}$ at some stage:
If $x ≺_{X} x^{'}$ was added in Substage 1, then x (or $x^{'}$ ) is a dummy symbol $w_{k}$ and $x^{'}$ (or x) is from some pair $(F_{n}, y_{n})$ . Then by assumption $w_{k}$ is replaced in some later stage in Substage 2, and the replacement is done in such a way that $f (x) ≺_{Y} f (x^{'})$ holds.

If $x ≺_{X} x^{'}$ was added in Substage 3 then trivially $f (x) ≺_{Y} f (x^{'})$ .

The last possibility is that $x ≺_{X} x^{'}$ was added in Substage 4 when completing under transitive closure. Then there is some z such that $x ≺_{X} z$ and $z ≺_{X} x^{'}$ were already included in $≺_{X}$ before $x ≺_{X} x^{'}$ was added. By induction, we can assume that $f (x) ≺_{Y} f (z)$ and $f (z) ≺_{Y} f (x^{'})$ . Therefore, $f (x) ≺_{Y} f (x^{'})$ by the transitivity of $≺_{Y}$ .
It follows from Lemma 1 that if $≺_{Y}$ is interpolable then $I (≺_{X})$ and $I (≺_{Y})$ are computably homeomorphic.

From the above construction, we can enumerate a sequence of c.e. interpolable transitive relations ${(≺_{X_{i}})}_{i \in N}$ in such a way that for every c.e. interpolable transitive relation $≺_{Y}$ there is some $i \in N$ with $I (≺_{X_{i}})$ computably homeomorphic to $I (≺_{Y})$ . □

7. Complexity of (effective) homeomorphism

Here we estimate the complexity of (effective) homeomorphism relations $≃_{e}$ and ≃ in the introduced numberings and deduce some corollaries. Similar questions for algebraic structures were studied in detail (see e.g. [11,12,15]). In the next theorem we collect some estimates which for the classes of domains resemble the corresponding estimates for algebraic structures,3

³
We thank Nikolay Bazhenov for the related bibliographical references.

while for Polish and quasi-Polish spaces are apparently higher.

To obtain the estimate for ι, we employ the representation of computable functions $f : I (≺_{1}) \to I (≺_{2})$ between spaces of ideals, where $≺_{1}, ≺_{2} \in T$ , established in [5], Theorem 2 (see the end of Section 5.2).

For the case $≺_{1}, ≺_{2} \in I$ of domains, the above representation may be simplified using the effective version of results in Section 2.2.6 of [1] (see Theorem 4 above). Namely, the computable functions $f : I (≺_{1}) \to I (≺_{2})$ coincide with the functions $⌜ R ⌝$ where R is a binary c.e. relation on ω satisfying the following conditions: if $a R b$ and $a ≺_{1} a^{'}$ then $a^{'} R b$ ; if $a R b$ and $b^{'} ≺_{2} b$ then $a R b^{'}$ ; for any a there is b with $a R b$ ; for all a, b, $b^{'}$ with $a R b$ , $a R b^{'}$ there is $b^{″}$ with $b ≺_{2} b^{″}$ , $b^{'} ≺_{2} b^{″}$ , and $a R b^{″}$ ; if $a R b$ then $a^{'} R b$ for some $a^{'} ≺_{1} a$ . Conjunction of these conditions is denoted as $mor (R, ≺_{1}, ≺_{2})$ (meaning “R is a morphism from $≺_{1}$ to $≺_{2}$ ”). We note that $⌜ R ⌝ = {id}_{I (≺_{1})}$ iff $a R b \leftrightarrow b ≺_{1} a$ . Recall that α, β, γ, δ, ε, ι, μ are the numberings that were introduced in Section 6.1.

Theorem 7.

Let $ν \in {α, β, γ, δ, ε}$ . Then the relations $ν (m) ≃_{e} ν (n)$ and $ν (m) ≃ ν (n)$ are $Σ_{3}^{0}$ -complete and $Σ_{1}^{1}$ -complete sets, respectively. Moreover, they are resp. $Σ_{3}^{0}$ - and $Σ_{1}^{1}$ -complete equivalence relations under the computable reducibility of equivalence relations.

Let $ν \in {ι, μ}$ . The relations $ν (m) ≃_{e} ν (n)$ and $ν (m) ≃ ν (n)$ are $Π_{1}^{1}$ and $Σ_{2}^{1}$ , respectively.

Proof.

1. First we prove the upper bounds. For $ν = α$ , it is easy to see (cf. proof of Theorem 2 in [27]) that $α (m) ≃_{e} α (n)$ iff $(ω; V_{p (m)}) ≃_{e} (ω; V_{p (n)})$ iff $\begin{aligned} \exists k, l \forall x, y (φ_{k} (x) ↓ \land φ_{l} (x) ↓ \land (x V_{p (m)} y \leftrightarrow φ_{k} (x) V_{p (n)} φ_{k} (y)) \land (x V_{p (n)} y \\ \leftrightarrow φ_{l} (x) V_{p (m)} φ_{l} (y)) \land x V_{p (m)} φ_{l} (φ_{k} (x)) V_{p (m)} x \land y V_{p (n)} φ_{k} (φ_{l} (y) V_{p (n)} y)), \end{aligned}$ hence the relation is $Σ_{3}^{0}$ . For the relation ≃ we only have to add the functional quantifier $\exists h$ in the beginning of the above formula and relativize φ to the oracle h; this yields the desired estimate $Σ_{1}^{1}$ .

The above argument works for $ν = β$ if we just replace p by o. For $ν = γ$ , we also replace p by c; it is easy to see that the $\emptyset^{″}$ -computability of c does not damage the estimate $Σ_{3}^{0}$ and (trivially) the estimate $Σ_{1}^{1}$ .

For $ν = δ$ , we use the representation of computable functions between ideal spaces described before the formulation of the theorem: $δ (m) ≃_{e} δ (n)$ iff $\begin{aligned} \exists k, l, x, y (x = i (m) \land y = i (n) \land mor (V_{k}, V_{x}, V_{y}) \land mor (V_{l}, V_{y}, V_{x}) \\ \land \forall a, b (a (V_{l} \circ V_{k}) b \leftrightarrow b V_{x} a) \forall a, b (a (V_{k} \circ V_{l}) b \leftrightarrow b V_{y} a) . \end{aligned}$ Since i is $\emptyset^{″}$ -computable, the first two conjuncts in the main parenthesis are $Σ_{3}^{0}$ . Since $V_{x}$ is c.e., the same holds for the third and fourth conjuncts, while the fifth and sixth conjuncts are $Π_{2}^{0}$ . This concludes the estimate for $≃_{e}$ . For the relation ≃ we only have to add the functional quantifier $\exists h$ in the beginning of the above formula and replace $V_{k}$ , $V_{l}$ by $V_{k}^{h}$ , $V_{l}^{h}$ ; this yields the desired estimate $Σ_{1}^{1}$ . The above argument (with j in place of i) works for $ν = ε$ .

Now we prove the lower bounds. By Theorem 4.7(a) in [15], for any $Σ_{3}^{0}$ set A there are computable sequences ${L_{k}}$ , ${M_{k}}$ of computable linear orders on ω such that $k \in A$ iff $L_{k} ≃_{e} M_{k}$ . By the definition of ideal spaces, $L_{k} ≃_{e} M_{k}$ iff $I (L_{k}) ≃_{e} I (M_{k})$ iff $A ⩽_{m} {⟨ k, l ⟩ | ν (k) ≃_{e} ν (l)}$ for every $ν \in {α, β, γ, δ, ε}$ , concluding the proof for $Σ_{3}^{0}$ .

By Theorem 4.4(d) in [15], for any $Σ_{1}^{1}$ set A there are computable sequences ${L_{k}}$ , ${M_{k}}$ of computable linear orders on ω such that $k \in A$ iff $L_{k} ≃ M_{k}$ . Repeating the argument of the previous paragraph, we obtain the proof for $Σ_{1}^{1}$ .

It remains to show that $≃_{e}$ and ≃ are also complete as equivalence relations. As follows from Proposition 4 in [11], for any $Σ_{3}^{0}$ equivalence relation A on ω there is a computable sequence ${L_{k}}$ of computable partial orders on ω such that $k A l$ iff $L_{k} ≃_{e} L_{l}$ which proves the $Σ_{3}^{0}$ completeness for every $ν \in {α, β, γ, δ, ε}$ . By Theorem 5 in [12], for any $Σ_{1}^{1}$ equivalence relation A on ω there is a computable sequence ${L_{k}}$ of computable linear orders on ω such that $k A l$ iff $L_{k} ≃ L_{l}$ . This proves the $Σ_{1}^{1}$ completeness for every $ν \in {α, β, γ, δ, ε}$ .

2. By Proposition 8, we can use ι instead of π. Denoting the relation $V_{t (n)}$ in Proposition 6 by $≺_{n}$ , we obtain: $ι (m) ≃_{e} ι (n)$ iff $I (≺_{m}) ≃_{e} I (≺_{n})$ iff $\begin{aligned} \exists k, l (⌜ V_{k} ⌝ : I (≺_{m}) \to I (≺_{n}) \land ⌜ V_{l} ⌝ : I (≺_{n}) \to I (≺_{m}) \\ \land ⌜ V_{l} ⌝ \circ ⌜ V_{k} ⌝ = {id}_{I (≺_{m})} \land ⌜ V_{k} ⌝ \circ ⌜ V_{l} ⌝ = {id}_{I (≺_{n})}), \end{aligned}$ hence it suffices to check that the relation $⌜ V_{l} ⌝ \circ ⌜ V_{k} ⌝ = {id}_{I (≺_{m})}$ is $Π_{1}^{1}$ . Since it is equivalent to $\forall I \in I (≺_{m}) (⌜ V_{j} ⌝ (⌜ V_{i} ⌝ (I)) = I)$ , this follows from the definition of $⌜ R ⌝ (I)$ .

The second assertion is a straightforward relativization of the first one. Indeed, $ι (m) ≃ ι (n)$ iff $I (≺_{m}) ≃ I (≺_{n})$ iff $\begin{aligned} \exists R, S \subseteq N^{2} (⌜ R ⌝ : I (≺_{m}) \to I (≺_{n}) \land ⌜ S ⌝ : I (≺_{n}) \to I (≺_{m}) \\ \land ⌜ S ⌝ \circ ⌜ R ⌝ = {id}_{I (≺_{m})} \land ⌜ R ⌝ \circ ⌜ S ⌝ = {id}_{I (≺_{n})}), \end{aligned}$ hence the relation is $Σ_{2}^{1}$ . □

We do not currently know whether the estimates in item 2 of the above theorem are precise. From the effective Stone duality developed in [16,17] it follows that the homeomorphism relation between computable compact Polish spaces is $Σ_{1}^{1}$ -complete, as it was noticed in a recent communication of the third author with Alexander Melnikov (see Corollary 4.28 in [8]). But for computable Polish spaces the question remains open.

As a corollary of Theorem 7 and Proposition 8, we obtain upper bounds for ι-index sets of some natural classes of spaces.

Corollary 4.

Let $ν \in {μ, α, β, γ, δ, ε}$ . Then ${n | \exists m (ι (n) ≃_{e} ν (m))}$ is $Π_{1}^{1}$ and ${n | \exists m (ι (n) ≃ ν (m))}$ is $Σ_{2}^{1}$ .

In particular, the problem of deciding whether a given effective quasi-Polish space is effectively homeomorphic to a metrizable space (a c.e. domain, c.e. algebraic domain, etc.) is $Π_{1}^{1}$ . For the homeomorphism problem, it is $Σ_{2}^{1}$ . In the next section we show that the estimate for metrizable spaces can be improved.

8. Complexity of separation axioms

Here we discuss some classes of spaces related to separation axioms. Let $T_{1}$ , $T_{2}$ , $R$ , $M$ be the classes of $T_{1}$ -, $T_{2}$ -, regular, and metrisable spaces, respectively. Let ${D_{n}}$ be the standard numbering of finite subsets of ω, then the sets ${\overset{ˇ}{D}}_{n} = {A \subseteq ω | D_{n} \subseteq A}$ form the standard basis of the Scott topology on $P ω$ .

Proposition 9.
The π-index set of any of the classes $T_{1}$ , $T_{2}$ , $R$ , $M$ is $Π_{1}^{1}$ .
Proof.
By the definition of a $T_{1}$ -space, $π (m) \in T_{1}$ iff $\forall x, y \in π (m) (x \neq y \to \exists n (x \in {\overset{ˇ}{D}}_{n} ∌ y))$ . Since $π (m) \in Π_{2}^{0} (P ω)$ , we get $π^{- 1} (T_{1}) \in Π_{1}^{1}$ .

By the definition of a $T_{2}$ -space, $π (m) \in T_{2}$ iff $\begin{matrix} \forall x, y \in π (m) (x \neq y \to \exists i, j (x \in {\overset{ˇ}{D}}_{i} \land y \in {\overset{ˇ}{D}}_{j} \land \overset{ˇ}{D_{i}} \cap {\overset{ˇ}{D}}_{j} \cap π (m) = \emptyset)) . \end{matrix}$ Since ${\overset{ˇ}{D}}_{i} \cap {\overset{ˇ}{D}}_{j} \cap π (m) = \emptyset$ iff $\forall z \in π (m) (z \notin {\overset{ˇ}{D}}_{i} \lor z \notin {\overset{ˇ}{D}}_{j})$ , we have $π^{- 1} (T_{2}) \in Π_{1}^{1}$ .

Recall that X is regular iff for every $x \in X$ and every basic neighborhood U of x there is a basic neighborhood V of x such that the closure $Cl (V)$ of V in X is contained in U. For $X = π (m)$ this reads: $π (m) \in R$ iff $\forall x \in π (m) \forall i (x \in {\overset{ˇ}{D}}_{i} \to \exists j (x \in {\overset{ˇ}{D}}_{j} \land Cl ({\overset{ˇ}{D}}_{j} \cap π (m)) \subseteq {\overset{ˇ}{D}}_{i}))$ . Thus, it suffices to check that the relation $\forall y (y \in Cl ({\overset{ˇ}{D}}_{j} \cap π (m)) \to y \in {\overset{ˇ}{D}}_{i})$ is $Π_{1}^{1}$ , and for this it suffices to check that the relation $y \in Cl ({\overset{ˇ}{D}}_{j} \cap π (m))$ is $Σ_{1}^{1}$ . The relation is equivalent to $\forall k (y \in {\overset{ˇ}{D}}_{k} \cap π (m) \to \exists z \in {\overset{ˇ}{D}}_{j} \cap π (m) (z \in {\overset{ˇ}{D}}_{k}))$ , hence it is indeed $Σ_{1}^{1}$ .

By the Urysohn metrisation theorem we have $M = T_{1} \cap R$ , hence the estimate $Π_{1}^{1}$ for $π^{- 1} (M)$ follows from the previous ones. Note that the upper bound $Σ_{2}^{1}$ of $π^{- 1} (M)$ in Corollary 4 (without using the Urysohn theorem) is much worse. □

Next we show that the upper bounds of Proposition 9 are optimal. Our proofs below demonstrate that the ideal characterizations provide useful tools for such kind of results. Recall that the following implications hold for ${cb}_{0}$ -spaces: $\begin{matrix} metrizable ⟺ regular ⟹ Hausdorff ⟹ T_{1} . \end{matrix}$

For the equivalence of metrizability and regularity, as mentioned in [28, Page 12], every regular $T_{0}$ space is Hausdorff: For two distinct points x, y, by $T_{0}$ -ness, there exists an open set U containing either x or y, but not the other. Assuming that U contains x, the complement of U is closed, so from regularity they are separated, which in particular separates x and y. Thus, it follows from the Urysohn metrization theorem that regular ${cb}_{0}$ space is metrizable.

We start with the following $Π_{1}^{1}$ -completeness result with respect to the numbering ι (i.e., the numbering of all effective quasi-Polish spaces induced from the standard numbering of c.e. transitive relations), where recall $ι \equiv_{e} π$ from Proposition 8.
Theorem 8.
Let $F \subseteq ω$ be a $Π_{1}^{1}$ set. Then, there exists a computable function which, given $p \in ω$ , returns an ι-index of a c.e. EQP-space X such that $\begin{matrix} \{\begin{array}{ll} X is metrizable & if p \in F, \\ X is not T_{1} & if p \notin F . \end{array} \end{matrix}$
Proof.
Recall that the set of indices of well-founded computable trees is $Π_{1}^{1}$ complete. Hence, instead of a $Π_{1}^{1}$ set, we consider computable trees. Let $T \subseteq ω^{< ω}$ be a computable tree. Our space X will be ${I_{x} : x \in ω^{ω}} \cup {J_{x} : x \in [T]}$ equipped with the specialization order $J_{x} ⩽ I_{x}$ , where $[T]$ is the set of all infinite paths through T. The discussion from here on is to write down this space X as an ideal space.

For each $σ \in ω^{< ω}$ , we prepare for a new symbol $\underline{σ}$ . Let $| σ |$ be the length of σ, and put $| \underline{σ} | = | σ |$ . If σ is nonempty, i.e., $| σ | > 0$ , we denote by $σ^{-}$ the immediate predecessor of σ. We define a computable binary relation ≺ on the set $| ≺ | : = {σ, \underline{σ} : σ \in ω^{< ω}}$ as follows: If $σ \in ω^{ω}$ is nonempty, enumerate $σ^{-} ≺ σ$ , $\underline{σ^{-}} ≺ \underline{σ}$ , and $σ ≺ \underline{σ}$ . If $σ \notin T$ then we also enumerate $\underline{σ^{-}} ≺ σ$ . Then consider its transitive closure and define $X = I (≺)$ .

Note that if $a ≺ b$ then either $| a | < | b |$ or $a = σ$ and $b = \underline{σ}$ for some $σ \in ω^{< ω}$ . If I is an ideal of ≺, then for any $a \in I$ one can use directedness of I twice to obtain $b, c \in I$ such that $a ≺ b ≺ c$ . Then, by the property of ≺ mentioned above, we have $| a | < | c |$ . Therefore, any ideal contains arbitrarily long strings. Moreover, as no pair of incomparable strings has an upper bound, in order for a set to be directed, all of its members must be comparable. This means that for any ideal I of ≺ there exists an infinite string $x \in ω^{ω}$ such that I consists only of the initial segments of x or those underlined in them. In other words, I is the ≺-downward closure of ${σ : σ \subset x}$ or ${\underline{σ} : σ \subset x}$ , where we mean by $σ \subset x$ that σ is an initial segment of x.

If x is an infinite path through T, then the downward closure of ${σ : σ \subset x}$ is $J_{x} = {σ : σ \subset x}$ , and the downward closure of ${\underline{σ} : σ \subset x}$ is $I_{x} = {σ, \underline{σ} : σ \subset x}$ . Both $I_{x}$ and $J_{x}$ are ideals, and since $J_{x} \subseteq I_{x}$ , obviously $J_{x} \in {[τ]}_{≺}$ implies $I_{x} \in {[τ]}_{≺}$ , so $J_{x} ⩽_{X} I_{x}$ , where recall that ${[n]}_{≺} = {I \in I (≺) : n \in I}$ is a basic open set, and $⩽_{X}$ is the specialization order. Hence, if T is not well-founded, then X is not $T_{1}$ . If T is well-founded, then any $x \in ω^{ω}$ has an initial segment $σ \notin T$ , and for any such σ we have $σ^{-} ≺ \underline{σ^{-}} ≺ σ ≺ \underline{σ} ≺ \dots$ . Hence, ${σ : σ \subset x}$ and ${\underline{σ} : σ \subset x}$ have the same downward closure $I_{x} = {σ, \underline{σ} : σ \subset x}$ . Therefore, any ideal is of the form $I_{x}$ for some $x \in ω^{ω}$ . Thus, we have $X = {I_{x} : x \in ω^{ω}}$ , which is homeomorphic to Baire space $ω^{ω}$ . This is because, as $| ≺ | = {σ, \underline{σ} : σ \in ω^{< ω}}$ is the underlying set of the binary relation ≺, the set ${{[σ]}_{≺}, {[\underline{σ}]}_{≺} : σ \in ω^{< ω}}$ yields the topology on X by definition, and the above argument shows $X \cap {[σ]}_{≺} = X \cap {[\underline{σ}]}_{≺} = {I_{x} : σ \subset x}$ . In particular, X is metrizable.

For overtness, given $σ \in ω^{< ω}$ , if x extends σ then $I_{x} = {σ, \underline{σ} : σ \subset x}$ is an ideal of ≺ as seen above, and contains both σ and $\underline{σ}$ ; hence $I_{x} \in {[σ]}_{≺}$ and $I_{x} \in {[\underline{σ}]}_{≺}$ . This means that $X \cap {[τ]}_{≺} \neq \emptyset$ for any $τ \in | ≺ |$ . In particular, X is overt. □

Theorem 8 shows that, for any $i \in {1, 2, 3}$ , the ι-index set of all c.e. EQP $T_{i}$ -spaces is $Π_{1}^{1}$ -complete, where a second countable $T_{0}$ space is $T_{3}$ if and only if it is metrizable. This result can be further extended as follows.
Theorem 9.
Let $M \subseteq H \subseteq F \subseteq ω$ be $Π_{1}^{1}$ sets. Then, there exists a computable function which, given $p \in ω$ , returns an ι-index of a c.e. EQP-space X such that $\begin{matrix} \{\begin{array}{ll} X is metrizable & if p \in M, \\ X is Hausdorff, but not metrizable & if p \in H ∖ M, \\ X is T_{1}, but not Hausdorff & if p \in F ∖ H, \\ X is not T_{1} & if p \notin F . \end{array} \end{matrix}$

This means that every tuple $(M, H, F)$ of $Π_{1}^{1}$ -sets such that $M \subseteq H \subseteq F$ uniformly m-reduces to $(ι^{- 1} (M), ι^{- 1} (T_{2}), ι^{- 1} (T_{1}))$ . Let us decompose the proof of Theorem 9 into a few lemmas. Lemma 2.
Let $H \subseteq ω$ be a $Π_{1}^{1}$ set. Then, there exists a computable function which, given $p \in ω$ , returns an ι-index of a c.e. EQP-space X such that $\begin{matrix} \{\begin{array}{ll} X is metrizable & if p \in H, \\ X is T_{1}, but not Hausdorff & if p \notin H . \end{array} \end{matrix}$
Proof.
First, one specific example of a second countable $T_{1}$ topology which is not Hausdorff is called a telophase topology [28, II.73]. Here, our construction is closer to the one in [20], which adds an inseparable pair of points at infinity to ω than the one in [28, II.73], which adds a new point $1^{⋆}$ to $[0, 1]$ where $(1, 1^{⋆})$ forms an inseparable pair. In our construction, a tree $T \subseteq ω^{< ω}$ is first given. For $x \in ω^{ω}$ , if x is an infinite path through T then we add an inseparable pair $(I_{x}, I_{x}^{⋆})$ of points at infinity to the discrete space $ω^{< ω}$ . If x is not an infinite path through T then we add a single point $J_{x}$ at infinity to $ω^{< ω}$ .

Formally, given a tree $T \subseteq ω^{< ω}$ , we consider the following specific presentation ≺ of a telophase topology: For each $σ \in ω^{< ω}$ , we prepare for symbols $\underline{σ}$ , $[σ, \infty]$ , and $[σ, \infty^{⋆}]$ . We define a computable binary relation ≺ on the set $| ≺ | : = {\underline{σ}, [σ, \infty], [σ, \infty^{⋆}] : σ \in ω^{< ω}}$ . If σ is nonempty, we denote by $σ^{-}$ the immediate predecessor of σ, and enumerate $[σ^{-}, o] ≺ [σ, o] ≺ \underline{σ} ≺ \underline{σ}$ for each $o \in {\infty, \infty^{⋆}}$ . If $σ \notin T$ , we also enumerate $[σ^{-}, \infty^{⋆}] ≺ [σ, \infty] ≺ [σ, \infty^{⋆}]$ . Then consider its transitive closure and define $X = I (≺)$ .

First, since $\underline{σ} ≺ \underline{σ}$ , the ≺-downward closure of ${\underline{σ}}$ forms an ideal. This is $I_{σ} = {\underline{σ}} \cup {[τ, \infty], [τ, \infty^{⋆}] : τ \subseteq σ}$ , where we mean by $τ \subseteq σ$ that τ is an initial segment of σ. Note that the subspace $Y = {I_{σ} : σ \in ω^{< ω}}$ of X is discrete since $Y \cap {[\underline{σ}]}_{≺} = {I_{σ}}$ . For any $a \notin I_{σ}$ , a and $\underline{σ}$ have no common upper bound, so $I_{σ}$ is the unique ideal containing $\underline{σ}$ . If an ideal I does not contain $\underline{σ}$ for any $σ \in ω^{< ω}$ , then as in the proof of Theorem 8, one can see that I contains $[σ, \infty]$ or $[σ, \infty^{}]$ for an arbitrarily long string σ. Moreover, as no pair of incomparable strings has an upper bound, in order for a set to be directed, all of its members must be comparable. This means that for any such ideal I of ≺ there exists an infinite string $x \in ω^{ω}$ such that I consists only of $[σ, \infty]$ or $[σ, \infty^{⋆}]$ for initial segments σ of x. In other words, such an I is the ≺-downward closure of ${[σ, \infty] : σ \subset x}$ or ${[σ, \infty^{⋆}] : σ \subset x}$ .

If x is an infinite path through T, then both $I_{x} = {[σ, \infty] : σ \subset x}$ and $I_{x}^{⋆} = {[σ, \infty^{⋆}] : σ \subset x}$ are downward closed. Hence, any ideal is of the form $I_{σ}$ , $I_{x}$ or $I_{x}^{⋆}$ . We claim that the latter two ideals as points cannot be separated by disjoint open sets. This is because any basic open sets containing $I_{x}$ and $I_{x}^{⋆}$ are of the form ${[[σ, \infty]]}_{≺}$ for some $σ \subset x$ and ${[[τ, \infty^{⋆}]]}_{≺}$ for some $τ \subset x$ respectively. However, ${[[σ, \infty]]}_{≺}$ and ${[[τ, \infty^{⋆}]]}_{≺}$ always have an intersection $I_{ρ}$ , where ρ is a common extension of σ and τ. Hence, X is not Hausdorff. If x is not an infinite path through T, then as in the proof of Theorem 9, one can see that both ${[σ, \infty] : σ \subset x}$ and ${[σ, \infty^{⋆}] : σ \subset x}$ have the same downward closure $J_{x} = {[σ, \infty], [σ, \infty^{⋆}] : σ \subset x}$ . In any case, no two ideals are comparable by ⊆, so X is $T_{1}$ . Hence, if T is ill-founded, then X is $T_{1}$ , but not Hausdorff.

If T is well-founded, then as seen above, any ideal is of the form $I_{σ}$ or $J_{x}$ ; that is, $X = {I_{σ} : σ \in ω^{< ω}} \cup {J_{x} : x \in ω^{ω}}$ . We claim that X is homeomorphic to the Polish space $ω^{⩽ ω} : = ω^{< ω} \cup ω^{ω}$ whose topology is generated from ${σ : σ \in ω^{< ω}}$ and $[σ] = {x \in ω^{⩽ ω} : x extends σ}$ . This is because, as $| ≺ | = {\underline{σ}, [σ, \infty], [σ, \infty^{⋆}] : σ \in ω^{< ω}}$ is the underlying set of the binary relation ≺, the set ${{[\underline{σ}]}_{≺}, {[[σ, \infty]]}_{≺}, {[[σ, \infty^{⋆}]]}_{≺} : σ \in ω^{< ω}}$ yields the topology on X by definition, and the above argument shows $X \cap {[[σ, \infty]]}_{≺} = X \cap {[[σ, \infty^{⋆}]]}_{≺} = {I_{τ} : τ \subseteq σ} \cup {J_{x} : σ \subset x}$ . Hence, the union of the map $σ \mapsto I_{σ}$ and the map $x \mapsto J_{x}$ gives a homeomorphism between $ω^{⩽ ω}$ and X. In particular, X is metrizable.

For overtness, given $σ \in ω^{< ω}$ , we have $I_{σ} \in {[σ]}_{≺}$ , and if x extends σ then $I_{x}, J_{x} \in {[[σ, \infty]]}_{≺}$ and $I_{x}^{⋆}, J_{x} \in {[[σ, \infty^{⋆}]]}_{≺}$ . This means that $X \cap {[τ]}_{≺} \neq \emptyset$ for any $τ \in | ≺ |$ . In particular, X is overt. □
Lemma 3.
Let* $M \subseteq ω$ be a $Π_{1}^{1}$ set. Then, there exists a computable function which, given $p \in ω$ , returns an ι-index of a c.e. EQP-space X such that $\begin{matrix} \{\begin{array}{ll} X is metrizable & if p \in M, \\ X is Hausdorff, but not metrizable & if p \notin M . \end{array} \end{matrix}$
Proof.
First, one specific example of a second countable Hausdorff topology which is not metrizable is called the double origin topology [28, II.74]. It is like a Euclidean plane with two origins that cannot be separated by closed neighborhoods (which causes non-metrizability). Here, our construction is closer to the one in [20], which yields a quasi-Polish space, while the example in [28, II.74] is not quasi-Polish. In our construction, a tree $T \subseteq ω^{< ω}$ is first given. The base plane of our space is the discrete space $ω \times (ω^{< ω} ⊔ ω^{< ω})$ . For each $x \in ω^{ω}$ , the points $I_{n, x} = (n, x)$ and $(\infty, x)$ may be added. Here, if x is an infinite path through T then two points $J_{x}^{+}$ and $J_{x}^{-}$ corresponding to $(\infty, x)$ are added, and these cannot be separated by closed neighborhoods. Indeed, the intersection of any two closed neighborhoods containing $J_{x}^{+}$ and $J_{x}^{-}$ respectively contains $I_{n, x}$ for an arbitrary large n. If x is not an infinite path through T then the plane is folded in half with the abscissa ${I_{n, x} : n \in ω}$ as the fold line, and then $J_{x}^{+}$ is identified with $J_{x}^{-}$ .

Formally, given a tree $T \subseteq ω^{< ω}$ , we consider the following specific presentation ≺ of a telophase topology: For each $n \in ω$ and $σ \in ω^{< ω}$ , we prepare for symbols $(n, σ)$ , $(n, \underline{σ})$ , $(n, σ^{\pm})$ , $[n, σ]$ and $[n, \underline{σ}]$ . We define a computable binary relation ≺ on the set $\begin{matrix} | ≺ | : = {(n, σ), (n, \underline{σ}), (n, σ^{\pm}), [n, σ], [n, \underline{σ}] : n \in ω and σ \in ω^{< ω}} . \end{matrix}$

For any $m < n$ , put the following: $\begin{array}{c} [m, σ] ≺ [n, σ] ≺ (n, σ) ≺ (n, σ), \\ [m, \underline{σ}] ≺ [n, \underline{σ}] ≺ (n, \underline{σ}) ≺ (n, \underline{σ}) . \end{array}$

If τ is a proper initial segment of σ, put the following: $\begin{matrix} (n, τ^{\pm}) ≺ (n, σ^{\pm}), (n, σ^{\pm}) ≺ (n, σ), (n, σ^{\pm}) ≺ (n, \underline{σ}) . \end{matrix}$

If $m < n$ and τ is a proper initial segment of σ, put the following: $\begin{matrix} [m, τ] ≺ [n, σ], [m, \underline{τ}] ≺ [n, \underline{σ}] . \end{matrix}$

If $σ \notin T$ , $m < n$ , and τ is a proper initial segment of σ, then we also put the following: $\begin{matrix} [m, τ] ≺ [n, \underline{σ}] ≺ [n, σ], (n, σ) ≺ (n, \underline{σ}) ≺ (n, σ) . \end{matrix}$

Then consider its transitive closure and define $X = I (≺)$ . For a directed set D, let $↓ D$ denote the ≺-downward closure of D. As in the previous proofs, one can see that any ideal of ≺ is one of the following forms: $\begin{array}{c} I_{n, σ} = ↓ {(n, σ)}, I_{n, \underline{σ}} = ↓ {(n, \underline{σ})}, I_{n, x} = ↓ {(n, σ^{\pm}) : σ \subset x}, \\ J_{x}^{+} = ↓ {[n, σ] : n \in ω and σ \subset x}, J_{x}^{-} = ↓ {[n, \underline{σ}] : n \in ω and σ \subset x} \end{array}$

If x is not an infinite path through T, then it is easy to see that $I_{n, σ} = I_{n, \underline{σ}}$ and $J_{x}^{+} = J_{x}^{-}$ . We claim that X is Hausdorff. First, to see $I_{n, σ}$ and $I_{m, τ}$ are separated for $n \neq m$ or $σ \neq τ$ where $σ, τ \in ω^{< ω}$ , note that $(n, σ)$ and $(m, τ)$ have no common upper bound, so ${[(n, σ)]}_{≺}$ and ${[(m, τ)]}_{≺}$ have no intersection. Thus, the points $I_{n, σ}$ and $I_{m, τ}$ are separated by ${[(n, σ)]}_{≺}$ and ${[(m, τ)]}_{≺}$ . Similarly, one can see that $I_{n, \underline{σ}}$ and $I_{n, \underline{τ}}$ are separated. If $σ \in T$ then $I_{n, σ}$ and $I_{n, \underline{σ}}$ are separated, and if $σ \notin T$ then $I_{n, σ} = I_{n, \underline{σ}}$ . If $m > n$ then $(n, σ^{\pm})$ and $[m, σ]$ have no common upper bound, so ${[(n, σ^{\pm})]}_{≺}$ and ${[(m, σ)]}_{≺}$ have no intersection. Thus, $I_{n, x}$ and $J_{x}^{+}$ are separated by them. In a similar manner, one can easily separate pairs $(I_{n, x}, J_{y}^{-})$ , $(I_{n, σ}, J_{x}^{+})$ , $(I_{n, σ}, I_{n, x})$ , etc. If x is an infinite path through T, then $[n, σ]$ and $[n, \underline{σ}]$ have no common upper bound, so ${[[n, σ]]}_{≺}$ and ${[[n, \underline{σ}]]}_{≺}$ have no intersection. Thus, $J_{x}^{+}$ and $J_{x}^{-}$ are separated by them. If x is not an infinite path through T, then $J_{x}^{+} = J_{x}^{-}$ . This concludes that X is Hausdorff.

If x is an infinite path through T, we claim that $J_{x}^{+}$ and $J_{x}^{-}$ cannot be separated by closed neighborhoods. Indeed, we show that any closed neighborhood of $J_{x}^{+}$ or $J_{x}^{-}$ contains $I_{n, x}$ for some $n \in ω$ . To see this, consider an open neighborhood ${[[n, σ]]}_{≺}$ of $J_{x}^{+}$ . Then, for any $m ⩾ n$ , ${[(m, σ^{\pm})]}_{≺}$ is an open neighborhood of $I_{m, x}$ . Since $m ⩾ n$ , $(m, σ)$ is a common upper bound of $[n, σ]$ and $(m, σ^{\pm})$ , so we have $I_{m, σ} \in {[(m, σ)]}_{≺} \subseteq {[[n, σ]]}_{≺} \cap {[(m, σ^{\pm})]}_{≺}$ . Hence, any open neighborhood of $I_{m, x}$ intersects with ${[[n, σ]]}_{≺}$ , and this means that the closure of ${[[n, σ]]}_{≺}$ contains $I_{m, x}$ for any $m ⩾ n$ . Similarly, the closure of ${[[n, \underline{σ}]]}_{≺}$ contains $I_{m, x}$ for any $m ⩾ n$ . This verifies the claim. In particular, if T is ill-founded, then such an x exists, so X is not metrizable.

If T is well-founded, then $I_{n, σ} = I_{n, \underline{σ}}$ and $J_{x}^{+} = J_{x}^{-}$ . Hence, $\begin{matrix} X = {I_{n, σ} : n \in ω and σ \in ω^{< ω}} \cup {I_{n, x} : n \in ω and x \in ω^{ω}} \cup {J_{x}^{+} : x \in ω^{ω}} . \end{matrix}$

We claim that X is embedded into the Polish space $Z = (ω + 1) \times ω^{⩽ ω}$ , where $ω + 1$ is the one point compactification of ω, and $ω^{⩽ ω}$ endowed with the Polish topology as in the proof of Lemma 2. Indeed, the union of the maps $⟨ n, σ ⟩ \mapsto I_{n, σ}$ , $⟨ n, x ⟩ \mapsto I_{n, x}$ , and $⟨ ω, x ⟩ \mapsto J_{x}^{+}$ gives a homeomorphism between $(ω \times ω^{⩽ ω}) \cup ({ω} \times ω^{ω}) \subseteq Z$ and X. This is because we have ${[(n, σ)]}_{≺} = {I_{n, σ}}$ , and if T has no infinite path extending σ, then we have ${[(n, σ^{\pm})]}_{≺} = {I_{n, τ} : σ \subseteq τ} \cup {I_{n, x} : σ \subset x}$ , and ${[[n, σ]]}_{≺} = {I_{m, τ} : n ⩽ m, σ \subseteq τ} \cup {I_{n, x} : n ⩽ m, σ \subset x} \cup {J_{x}^{+} : σ \subset x}$ . This means that the basic open set ${[(n, σ)]}_{≺}$ in X corresponds to the basic open set ${⟨ n, σ ⟩}$ in Z, the basic open set ${[(n, σ^{\pm})]}_{≺}$ in X corresponds to the basic open set ${n} \times {x \in ω^{⩽ ω} : σ \subset x}$ in Z, and the basic open set ${[[n, σ]]}_{≺}$ in X corresponds to the basic open set ${m \in ω + 1 : m ⩾ n} \times {x \in ω^{⩽ ω} : σ \subset x}$ in Z. Hence, if T is well-founded, then X is metrizable. Overtness of X is obvious as before. □
Proof of Theorem 9.
Let $M \subseteq H \subseteq F \subseteq ω$ be $Π_{1}^{1}$ sets. Let $X_{F}$ , $X_{H}$ and $X_{M}$ be c.e. EQP-spaces obtained by Theorem 8, Lemma 2 and Lemma 3. Then, consider the disjoint union of these spaces, i.e., $X = ({0} \times X_{F}) \cup ({1} \times X_{H}) \cup ({2} \times X_{M})$ . If $p \in M$ then all of these spaces are metrizable, so X is metrizable. If $p \in H ∖ M$ , then $X_{F}$ and $X_{H}$ are metrizable, and $X_{M}$ is Hausdorff, but not metrizable. Therefore, X is Hausdorff, but not metrizable. If $p \in F ∖ H$ , then $X_{F}$ is metrizable, $X_{H}$ is $T_{1}$ , but not Hausdorff, and $X_{M}$ is Hausdorff. Therefore, X is $T_{1}$ , but not Hausdorff. If $p \notin F$ , then $X_{F}$ is not $T_{1}$ . Thus, X is not $T_{1}$ . □
Remark.
Our proof of Lemma 3 actually gives a metrizable space if $p \in M$ , and a Hausdorff but not $T_{2.5}$ space if $p \notin M$ . On the other hand, an anonymous referee suggested an alternative proof of Lemma 3, which gives a metrizable space if $p \in M$ , and a $T_{2.5}$ (indeed, submetrizable) but not metrizable space if $p \notin M$ : It is the product space $ω^{ω} \times {[0, 1]}^{2}$ with $C = [T] \times {(x, y) : x = 0 and y > 0}$ added to the topology as a closed set. Taken together, Theorem 9 is more complete: Every tuple $(M, U, H, F)$ of $Π_{1}^{1}$ -sets such that $M \subseteq U \subseteq H \subseteq F$ uniformly m-reduces to $(ι^{- 1} (M), ι^{- 1} (T_{2.5}), ι^{- 1} (T_{2}), ι^{- 1} (T_{1}))$ .

9. Degree spectra of continuous domains

An interpolable relation ≺ differs from a preorder in that it does not satisfy $x ≺ x$ in general; interpreted in terms of domain, an element x satisfying $x ≺ x$ corresponds to a compact element. Since the degree-spectra of algebraic domains have been studied to some extent [27], let us investigate the degree spectra of non-algebraic ω-continuous domains. We say that a binary relation ≺ is irreflexive if $x ≺ x$ fails for any x. We first show that, for any Turing degree a, there exists an irreflexive interpolable relation whose degree spectrum is ${x : a ⩽ x^{'}}$ .

Theorem 10.

For any $A \subseteq N$ , there exists an irreflexive interpolable relation $≺_{A}$ on $N$ such that for any $X \subseteq N$ : $\begin{matrix} A ⩽_{T} X^{'} ⟺ there exists an X -computable isomorphic copy of ≺_{A} . \end{matrix}$

Proof.

For $ℓ \in ω + 1$ , let $≺_{ℓ}$ be a binary relation on $ℓ \times Q$ defined as follows: $\begin{matrix} (m, p) ≺_{ℓ} (n, q) ⟺ m ⩽ n and p < q . \end{matrix}$

Clearly, $≺_{ℓ}$ is irreflexive and transitive. We claim that $≺_{ℓ}$ is interpolable. To see this, let $F = {(m_{i}, p_{i})}_{i < j}$ be a finite subset of $ℓ \times Q$ , and $(n, q)$ be an $≺_{ℓ}$ -upper bound of F. Then we have ${max}_{i < j} m_{i} ⩽ n$ and ${max}_{i < j} p_{i} < q$ . By density of $Q$ we have ${max}_{i < j} p_{i} < r < q$ , and so $(n, r) < (n, q)$ is also an $≺_{ℓ}$ -upper bound of F.

For any set $A \subseteq N$ we will define a binary relation $≺_{A}$ on $ω^{2} \times Q$ . In the following we fix a bijective coding $⟨ \cdot, \cdot ⟩ : ω \times 2 \to ω$ , say $⟨ a, b ⟩ = 2 a + b$ . Then we define a binary relation $≺_{A}$ as the disjoint union of ${≺_{⟨ n, A (n) ⟩} : n \in N}$ and countably many copies of $≺_{ω}$ . To be more precise, for each $a \in ω$ , if a is even, say $a = 2 a^{'}$ , put $ℓ (a) = ⟨ a^{'}, A (a^{'}) ⟩$ ; if a is odd, put $ℓ (a) = ω$ . Then $≺_{A}$ is defined as follows: $\begin{matrix} (a, m, p) ≺_{A} (b, n, q) ⟺ a = b and (m, p) ≺_{ℓ (a)} (n, q) . \end{matrix}$

Assume that there exists an X-computable relation ≺ on $N$ which is isomorphic to $≺_{A}$ . We say that ${x_{1}, \dots, x_{n}}$ is compatible if ${x_{1}, \dots, x_{n}}$ has a ≺-lower bound. We claim that for any $a \in N$ , $A (a) = b$ if and only if there exists a maximal compatible antichain of size $⟨ a, b ⟩$ . To see this, note that if h is an isomorphism between ≺ and $≺_{A}$ , then compatibility of ${x_{1}, \dots, x_{n}}$ ensures that ${h (x_{i}) : i ⩽ n}$ belongs to a single component; that is, ${h (x_{i}) : i ⩽ n} \subseteq {a} \times ℓ (a) \times Q$ for some $a \in N$ . So one may assume that $h (x_{i})$ is of the form $(a, m_{i}, p_{i})$ . By rearranging the indices, one may also assume that $i ⩽ j$ implies $m_{i} ⩽ m_{j}$ . If such ${x_{1}, \dots, x_{n}}$ is an antichain, then $i \neq j$ implies $m_{i} \neq m_{j}$ , so we get $n ⩽ ℓ (a)$ . If $n < ℓ (a)$ , we have $k < ℓ (a)$ such that $k \neq m_{i}$ for any nonzero $i ⩽ n$ . Since ${x_{1}, \dots, x_{n}}$ is an antichain, $i < j$ implies $q_{j} ⩽ q_{i}$ , so one can choose $q \in Q$ such that ${max}_{m_{j} > k} q_{j} ⩽ q ⩽ {min}_{m_{i} < k} q_{i}$ , and put $x^{'} = h^{- 1} (a, k, q)$ . One can see that ${x_{1}, \dots, x_{n}, x^{'}}$ is still an antichain. Hence, if ${x_{1}, \dots, x_{n}}$ is a maximal compatible antichain then $n = ℓ (a)$ . Conversely, for a fixed $p \in Q$ , since ${(a, i, p) : i < ℓ (a)}$ is a maximal compatible antichain, so is ${h^{- 1} (a, i, p) : i < ℓ (a)}$ . This verifies the claim.

We next claim that there exists an $X^{'}$ -computable sequence of all finite maximal compatible antichains. One can easily see that the condition of being a compatible antichain for a finite sequence is c.e. relative to X. Note that a compatible antichain $⟨ x_{1}, \dots, x_{n} ⟩$ is maximal if and only if any y in the same component as $x_{i}$ is comparable with $x_{j}$ (i.e., $y ≺ x_{j}$ or $x_{j} ≺ y$ ) for some $j ⩽ n$ . This is because $h (x_{i})$ is of the form $(a, m_{i}, p_{i})$ , and $h (y)$ is of the form $(a, k, q)$ for some $k < ℓ (a)$ . Note that y being in the same component as $x_{i}$ is equivalent to ${x_{i}, y}$ being compatible, so this property is X-c.e. Thus, maximality of a compatible antichain is co-c.e. relative to X. This proves the claim.

Finally, for any $a \in N$ , using $X^{'}$ search for a maximal compatible antichain whose size is of the form $⟨ a, b ⟩$ . Then, we calculate $A (a) = b$ . Hence, $A ⩽_{T} X^{'}$ .

Conversely, assume that $A ⩽_{T} X^{'}$ . Let ${(A_{s})}_{s \in ω}$ be an X-computable approximation of A. At stage s, we assume that we have already enumerated (a finite fragment of) a copy of $≺_{⟨ a, A_{s} (a) ⟩}$ , and infinitely many copies of $≺_{ω}$ . At stage $s + 1$ , if $A_{s} (a) < A_{s + 1} (a)$ for some $a < s$ , the original copy of $≺_{⟨ a, A_{s} (a) ⟩}$ can be modified to a copy $≺_{⟨ a, A_{s + 1} (a) ⟩}$ by enumerating the rationals at the top. If $A_{s + 1} (a) < A_{s} (a)$ , the original copy of $≺_{⟨ a, A_{s} (a) ⟩}$ can be modified to a copy of $≺_{ω}$ by enumerating infinitely many copies of $Q$ at the top. Then, start making a new copy of $≺_{⟨ a, A_{s + 1} (a) ⟩}$ using fresh elements. In any case, we also start making a copy of $≺_{⟨ s, A_{s + 1} (s) ⟩}$ . One can easily see that this construction gives an X-computable copy of $≺_{A}$ . □

Let us mention a few conclusions of Theorem 10. Recall that X is high if $\emptyset^{″} ⩽_{T} X^{'}$ , and that X is ${low}_{n}$ if $X^{(n)} ⩽_{T} \emptyset^{(n)}$ . The degree spectrum of a relation ≺ is the collection of all Turing degrees of isomorphic copies of ≺ on ω

Corollary 5.

The class of high degrees is the degree spectrum of an irreflexive interpolable relation.

Proof.

Let A in Theorem 10 be $\emptyset^{″}$ . □

Corollary 6.

There exists a ${low}_{2}$ irreflexive interpolable relation which is not isomorphic to any computable relation.

Proof.

If $A ≰_{T} \emptyset^{'}$ then $≺_{A}$ has no computable isomorphic copy by Theorem 10. Thus, if X is not low, then $≺_{X^{'}}$ has no computable isomorphic copy, while it has an X-computable copy, again by Theorem 10. Now, consider a ${low}_{2}$ set $X ⩽_{T} \emptyset^{'}$ which is not low. □

However, let us recall that effective quasi-Polish spaces directly correspond to c.e. transitive relations. Therefore, when focusing on the topological aspect, it seems more natural to consider a c.e. relation rather than a computable relation.

Theorem 11.

For any $A \subseteq N$ , there exists an irreflexive interpolable relation $≺_{A}^{*}$ on $N$ such that for any $X \subseteq N$ : $\begin{aligned} A ⩽_{T} X^{'} & ⟺ there exists an X -computable isomorphic copy of ≺_{A}^{*} . \\ A ⩽_{T} X^{″} & ⟺ there exists an X -c.e. isomorphic copy of ≺_{A}^{*} . \end{aligned}$

Proof.

In the following we fix a bijective coding $⟨ \cdot, \cdot, \cdot ⟩ : ω \times 2 \times 2 \to ω$ , say $⟨ a, b, c ⟩ = 4 a + 2 b + c$ . Let $≺_{A}^{*}$ be the disjoint sum of infinitely many copies of $≺_{⟨ a, i, 1 ⟩}$ for each $i < 2$ , and $≺_{⟨ a, A (a), 0 ⟩}$ . Clearly, $≺_{A}^{*}$ is irreflexive and interpolable.

The first statement can be shown in a similar way to Theorem 10. To see this, use $≺_{⟨ a, i, 1 ⟩}$ as a junk component instead of $≺_{ω}$ . A copy of $≺_{⟨ a, A_{s} (a), 0 ⟩}$ can always be changed to a junk, i.e., a copy of $≺_{⟨ a, A_{s} (a), 1 ⟩}$ .

For the second statement, assume that there exists an X-c.e. relation ≺ on $N$ which is isomorphic to $≺_{A}^{*}$ . In this case, for a finite sequence, compatibility is c.e., being an antichain is co-c.e., and maximality is $Π_{2}^{0}$ , relative to X. Hence there exists an $X^{″}$ -computable sequence of all finite maximal compatible antichains. As in the proof of Theorem 10, one can see that for any $a \in N$ , $A (a) = b$ if and only if there exists a maximal compatible antichain of size $⟨ a, b, 0 ⟩$ . Thus, one can show that $A ⩽_{T} X^{″}$ as before.

Conversely, if $A ⩽_{T} X^{″}$ then, using their $Σ_{3}^{0} (X)$ -definitions, A and its complement can be presented as follows: $\begin{array}{r} a \in A ⟺ (\exists b \in N) \underset{t \to \infty}{lim inf} A_{t}^{b} (a) = 0, \\ a \notin A ⟺ (\exists b \in N) \underset{t \to \infty}{lim inf} {\bar{A}}_{t}^{b} (a) = 0, \end{array}$ where $(a, b, t) \mapsto A_{t}^{b} (a)$ and $(a, b, t) \mapsto {\bar{A}}_{t}^{b} (a)$ are two-valued X-computable functions.

In the following, when we refer to a layer in an isomorphic copy of $≺_{ℓ}$ , we mean the isomorphic image of ${m} \times Q$ for some $m < ℓ$ . Before starting the construction, let us prepare infinitely many regions separated from each other. At each stage s, we construct (finite approximations of) infinitely many copies of $≺_{⟨ a, 1, A_{s}^{b} (a) ⟩}$ at the $⟨ a, b, 1 ⟩$ -th region, and infinitely many copies of $≺_{⟨ a, 0, {\bar{A}}_{s}^{b} (a) ⟩}$ at the $⟨ a, b, 0 ⟩$ -th region. We also make junk components, which are infinitely many copies of $≺_{⟨ a, i, 1 ⟩}$ . At stage $s + 1$ , if $A_{s}^{b} (a) < A_{s + 1}^{b} (a)$ then each copy of $≺_{⟨ a, 1, A_{s}^{b} (a) ⟩}$ can be modified to a copy $≺_{⟨ a, 1, A_{s + 1}^{b} (a) ⟩}$ by enumerating fresh rationals at the top. Even if $A_{s}^{b} (a) > A_{s + 1}^{b} (a)$ , the height of each copy of $≺_{⟨ a, 1, A_{s}^{b} (a) ⟩}$ can be lowered by adding a relation that moves upper layers of rationals to the right of lower layers of rationals (see the next paragraph for a more formal explanation), which is an X-c.e. process. In this way, each copy of $≺_{⟨ a, 1, A_{s}^{b} (a) ⟩}$ can be modified to a copy $≺_{⟨ a, 1, A_{s + 1}^{b} (a) ⟩}$ . Do the same for ${\bar{A}}_{s}^{b}$ .

Let us give a more detailed explanation of the lowering construction in the case $A_{s}^{b} (a) > A_{s + 1}^{b} (a)$ . Each element x in the copy of $≺_{⟨ a, 1, A_{s}^{b} (a) ⟩}$ in this region is assigned a role $(a, 1, i, p)$ for some $i ⩽ 1$ and $p \in Q$ . This role changes at most once in the construction. At stage s, at most s elements are enumerated in the copy. The relationship between each pair of these elements follows directly the $≺_{⟨ a, 1, A_{s}^{b} (a) ⟩}$ -relation between the assigned roles. Only at the stage where $A_{s}^{b} (a) > A_{s + 1}^{b} (a)$ happens, the role of each element x of the $⟨ a, 1, 1 ⟩$ -th layer changes to play $(a, 1, 0, p)$ for sufficiently large p. If p is chosen to be larger than all the rationals mentioned so far, this role-change corresponds to placing this element x above all the elements in the lower layers. Here, only a finite number of elements are already there, and furthermore, an element of a lower layer never comes above an element of a higher layer, so the role-change can be performed consistently. These are all the possibilities for a role-change to occur, only an element in the $⟨ a, 1, 1 ⟩$ -th layer can cause a role-change, and such an element drops to the $⟨ a, 1, 0 ⟩$ -th layer after the role change; hence the role change can occur only once at most. Finally, at each stage s, for each $n < s$ and $i ⩽ A_{s}^{b} (a)$ , if there is no element with role $(a, 1, i, p_{n})$ where $p_{n}$ is the nth rational, we arrange a fresh element to give the role of $(a, 1, i, p_{n})$ .

If $A_{s}^{b} (a) = i$ for almost all s, then each component at the $⟨ a, b, 1 ⟩$ -th region stabilizes to $≺_{⟨ a, 1, i ⟩}$ . Otherwise, we have $A_{s}^{b} (a) > A_{s + 1}^{b} (a)$ for infinitely many s. Then, if an element u in a component at the $⟨ a, b, 1 ⟩$ -th region belongs to a higher layer at some stage s, then at a stage $s^{'} ⩾ s$ such that $A_{s^{'}}^{b} (a) > A_{s^{'} + 1}^{b} (a)$ , adding a relation moves u to a lower layer, after which it never moves from that layer (since the role-change occurs only once at most). Hence, every element eventually belongs to a lower layer, which means that such a component is isomorphic to $≺_{⟨ a, 1, 0 ⟩}$ . Hence $a \in A$ if and only if there exists a copy of $≺_{⟨ a, 1, 0 ⟩}$ . Indeed, if this is the case, there are infinite such copies. The same holds for $\bar{A}$ . Hence, we have infinitely many copies of $≺_{⟨ a, A (a), 0 ⟩}$ , and no copies of $≺_{⟨ a, 1 - A (a), 0 ⟩}$ . This process may also make an extra copy of $≺_{⟨ a, i, 1 ⟩}$ , but in any case, at the junk components, we also make infinitely many copies of $≺_{⟨ a, i, 1 ⟩}$ . Consequently, this construction gives an X-c.e. copy of $≺_{A}^{*}$ . □

By using this, one can see that there exists a c.e. irreflexive interpolable relation which is not isomorphic to any computable relation. Indeed, one can prove a bit stronger.

Corollary 7.

There exists a c.e. irreflexive interpolable relation which is not isomorphic to any X-computable relation whenever X is not high.

Proof.

For $A \subseteq N$ , let $≺_{A}^{*}$ be an irreflexive interpolable relation as in Theorem 11. If $A ⩽_{T} \emptyset^{″}$ then $≺_{A}^{*}$ has a c.e. copy. Moreover, $A ⩽_{T} X^{'}$ if and only if there exists an X-computable isomorphic copy of $≺_{A}^{*}$ . Hence, for $A = \emptyset^{″}$ , if X is not high, i.e., $\emptyset^{″} ≰_{T} X^{'}$ , then $≺_{A}^{*}$ has no X-computable copy. □

Corollary 8.

There exists a ${low}_{3}$ -c.e. irreflexive interpolable relation which is not isomorphic to any c.e. relation.

Proof.

If $A ≰_{T} \emptyset^{″}$ then $≺_{A}^{*}$ has no c.e. isomorphic copy by Theorem 11. Thus, if X is not ${low}_{2}$ , then $≺_{X^{″}}^{*}$ has no c.e. isomorphic copy, while it has an X-c.e. copy, again by Theorem 11. Now, consider a ${low}_{3}$ set $X ⩽_{T} \emptyset^{'}$ which is not ${low}_{2}$ . □

The same result can be obtained for the degree spectra of ω-continuous domains instead of interpolable relations.

Footnotes

Acknowledgements

De Brecht’s research was supported by JSPS KAKENHI Grant Number 18K11166. Kihara’s research was partially supported by JSPS KAKENHI Grant Numbers 19K03602 and 21H03392, and the JSPS-RFBR Bilateral Joint Research Project JPJSBP120204809. Selivanov’s research, especially his work on some results in Sections 5, 6.1 and , was supported by the Russian Science Foundation, project 19-71-30002

References

Abramsky and

Jung, Domain theory, in: Handbook of Logic in Computer Science, Vol. 3, Oxford Univ. Press, New York, 1994, pp. 1–168.

C.J.

Ash and

Knight, Computable Structures and the Hyperarithmetical Hierarchy, Studies in Logic and the Foundations of Mathematics, Vol. 144, North-Holland Publishing Co., Amsterdam, 2000.

P.A.

Cholak,

D.D.

Dzhafarov,

Schweber and

R.A.

Shore, Computably enumerable partial orders, Computability1(2) (2012), 99–107. doi:10.3233/COM-12013.

de Brecht, Quasi-Polish spaces, Ann. Pure Appl. Logic164(3) (2013), 356–381. doi:10.1016/j.apal.2012.11.001.

de Brecht, Some notes on spaces of ideals and computable topology, in: Beyond the Horizon of Computability, Lecture Notes in Comput. Sci., Vol. 12098, Springer, Cham, 2020, pp. 26–37.

de Brecht,

Kihara and

Selivanov, Enumerating classes of effective quasi-Polish spaces, in: Revolutions and Revelations in Computability, Lecture Notes in Comput. Sci., Vol. 13359, Springer, Cham, 2022, pp. 88–102.

de Brecht,

Pauly and

Schröder, Overt choice, Computability9(3–4) (2020), 169–191. doi:10.3233/COM-190253.

R.G.

Downey and

A.G.

Melnikov, Computably compact metric spaces, Bull. Symb. Log.29(2) (2023), 170–263. doi:10.1017/bsl.2023.16.

Y.L.

Ershov, Theory of domains and nearby, in: Formal Methods in Programming and Their Applications (Academgorodok, 1993), Lecture Notes in Comput. Sci., Vol. 735, Springer, Berlin, 1993, pp. 1–7. doi:10.1007/BFb0039696.

10.

Y.L.

Ershov and

S.S.

Goncharov, Constructive Models, Siberian School of Algebra and Logic, Consultants Bureau, New York, 2000.

11.

Fokina,

Friedman and

Nies, Equivalence relations that are

Σ_{3}^{0}

complete for computable reducibility, in: Logic, Language, Information and Computation,

Ong and

de Queiroz, eds, Lecture Notes in Comput. Sci., Vol. 7456, Springer, Berlin, Heidelberg, 2012, pp. 26–33. doi:10.1007/978-3-642-32621-9_2.

12.

E.B.

Fokina,

S.-D.

Friedman,

Harizanov,

J.F.

Knight,

McCoy and

Montalbán, Isomorphism relations on computable structures, J. Symbolic Logic77(1) (2012), 122–132. doi:10.2178/jsl/1327068695.

13.

E.B.

Fokina,

Harizanov and

Melnikov, Computable model theory, in: Turing’s Legacy: Developments from Turing’s Ideas in Logic, Lect. Notes Log., Vol. 42, Assoc. Symbol. Logic, La Jolla, CA, 2014, pp. 124–194. doi:10.1017/CBO9781107338579.006.

14.

Gierz,

K.H.

Hofmann,

Keimel,

J.D.

Lawson,

M.W.

Mislove and

D.S.

Scott, A Compendium of Continuous Lattices, Springer-Verlag, Berlin–New York, 1980.

15.

S.S.

Goncharov and

Knight, Computable structure and antistructure theorems, Algebra Logika41(6) (2002), 639–681, 757. doi:10.1023/A:1021758312697.

16.

Harrison-Trainor,

Melnikov and

K.M.

Ng, Computability of Polish spaces up to homeomorphism, J. Symb. Log.85(4) (2020), 1664–1686. doi:10.1017/jsl.2020.67.

17.

Hoyrup,

Kihara and

Selivanov, Degree spectra of homeomorphism type of compact Polish spaces, The Journal of Symbolic Logic (2023), 1–32, to appear, first view. doi:10.1017/jsl.2023.93.

18.

Hoyrup,

Rojas,

Selivanov and

D.M.

Stull, Computability on quasi-Polish spaces, in: Descriptional Complexity of Formal Systems, Lecture Notes in Comput. Sci., Vol. 11612, Springer, Cham, 2019, pp. 171–183. doi:10.1007/978-3-030-23247-4_13.

19.

A.S.

Kechris, Classical Descriptive Set Theory, Graduate Texts in Mathematics, Vol. 156, Springer-Verlag, New York, 1995.

20.

Kihara,

K.M.

Ng and

Pauly, Enumeration degrees and nonmetrizable topology, submitted. arXiv:1904.04107.

21.

Korovina and

Kudinov, On higher effective descriptive set theory, in: Unveiling Dynamics and Complexity, Lecture Notes in Comput. Sci., Vol. 10307, Springer, Cham, 2017, pp. 282–291. doi:10.1007/978-3-319-58741-7_27.

22.

T.H.

McNicholl and

D.M.

Stull, The isometry degree of a computable copy of

ℓ^{p 1}

, Computability8(2) (2019), 179–189. doi:10.3233/COM-180214.

23.

A.G.

Melnikov, Computably isometric spaces, J. Symbolic Logic78(4) (2013), 1055–1085. doi:10.2178/jsl.7804030.

24.

RogersJr., Theory of Recursive Functions and Effective Computability, McGraw-Hill Book Co., New York–Toronto–London, 1967.

25.

Selivanov, Positive structures, in: Computability and Models, Univ. Ser. Math., Kluwer/Plenum, New York, 2003, pp. 321–350. doi:10.1007/978-1-4615-0755-0_14.

26.

Selivanov, Towards the effective descriptive set theory, in: Evolving Computability, Lecture Notes in Comput. Sci., Vol. 9136, Springer, Cham, 2015, pp. 324–333. doi:10.1007/978-3-319-20028-6_33.

27.

V.L.

Selivanov, On degree spectra of topological spaces, Lobachevskii J. Math.41(2) (2020), 252–259. doi:10.1134/S1995080220020146.

28.

L.A.

Steen and

J.A.

SeebachJr., Counterexamples in Topology, Holt, Rinehart and Winston, Inc., New York–Montreal, Que.–London, 1970.

Ideal presentations and numberings of some classes of effective quasi-Polish spaces

Abstract

Keywords

1. Introduction

1 Sections 3, 4, 5.1, 6.2, 9 are entirely new, Section 8 is extended by new facts, other sections remain essentially the same as in [6].

5.1. Ideal presentations of effective domains

6.1. Some natural numberings

3 We thank Nikolay Bazhenov for the related bibliographical references.

Footnotes

Acknowledgements

References

¹
Sections 3, 4, 5.1, 6.2, 9 are entirely new, Section 8 is extended by new facts, other sections remain essentially the same as in [6].

³
We thank Nikolay Bazhenov for the related bibliographical references.