{'fraction_non_alphanumeric': 0.06451253233431452, 'fraction_numerical': 0.01552047096601552, 'mean_word_length': 3.552329712719521, 'pattern_counts': {'":': 0, '<': 60, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Wadge Hardness in Scott Spaces and Its Effectivization

We prove some results on the Wadge order on the space of sets of natural numbers endowed with Scott topology, and more generally, on omega-continuous domains. Using alternating decreasing chains we characterize the property of Wadge hardness for the classes of the Hausdorff difference hierarchy (iterated differences of open sets). A similar characterization holds for Wadge one-to-one and finite-to-one completeness. We consider the same questions for the effectivization of the Wadge relation. We also show that for the space of sets of natural numbers endowed with the Scott topology, in each class of the Hausdorff difference hierarchy there are two strictly increasing chains of Wadge degrees of sets properly in that class. The length of these chains is the rank of the considered class, and each element in one chain is incomparable with all the elements in the other chain.


Introduction
Wadge reducibility between subsets of possibly uncountable topological spaces is the topological version of the classical many-one reducibility between subsets of discrete countable spaces like words or integers. Since Wadge reducibility defines a preorder on subsets of the topological space, one can consider the associated equivalence relation, whose classes are called Wadge degrees. The theory of Wadge degrees is remarkable in the case of Polish (i.e. completely metrizable with some countable dense subset) zerodimensional (i.e. admitting some basis of clopen sets) topological spaces, for instance the Cantor space 2 ω and the Baire space N ω with the product of discrete topologies. William W. Wadge (1972) developed such theory by looking at reductions between subsets of N ω as winning strategies in adequate infinite games, the now so-called Wadge games. The strength of Wadge's theory comes from Martin's result (1975) about determinacy of Borel games. The Wadge order on Borel subsets of N ω is well-founded and almost total: every antichain has only two elements, and it is constituted by the Wadge † Members of the Laboratoire Internationale Associé INFINIS, Universidad de Buenos Aires-Université Paris Diderot-Paris 7. This research was partially done whilst the first author was a visiting fellow at the Isaac Newton Institute for Mathematical Sciences in the programme 'Semantics & Syntax'. degree of a set and that of its complement. In spaces that are not totally disconnected this beauty breaks down. For instance, in the real line R, the Wadge order is not well founded (Hertling 1996a(Hertling ,1996b, for each 2 ≤ ξ < ω 1 there are chains of proper Σ 0 ξ sets indexed by any countable ordinal (Ikegami 2010) and, letting ⊆ * denote inclusion up to a finite set, the preorder (PN, ⊆ * ) (hence also any partial order of cardinality ℵ 1 ) can be embedded in the Wadge preorder of Borel subsets of R (Ikegami, Schlicht & Tanaka 2012). Also in every metric space which is positive-dimensional (i.e. at some point there is no clopen local base), there are 2 ℵ0 Wadge incomparable sets in the Hausdorff class D 2 of differences of two open sets (Schlicht 2012).
Outside zero-dimensional Polish spaces, Wadge theory has been first considered in the space PN of sets of natural numbers endowed with the Scott topology (which is T 0 but not T 2 , i.e., not Hausdorff), by A. Tang (1979Tang ( ,1981. Then it has been extensively studied by V. Selivanov in a series of papers (Selivanov 2004(Selivanov , 2005a(Selivanov , 2005b(Selivanov , 2006(Selivanov , 2008 in the context of ω-continuous domains. Although much of Wadge theory fails in spaces with Scott topology, a non trivial part remains. For instance, Selivanov showed the non existence of self-dual degrees in the Hausdorff difference hierarchy.
Another problem is to understand what part of Wadge theory remains in effective topological spaces by considering effective reductions. Since Borel determinacy gives highly non computable game strategies, the main tool used in classical Wadge theory is not available. As pointed out to us by an anonymous referee, it follows from Fokina, Friedman and Tornquist 2010 that the structure of effective Wadge degrees is very different, even for the Baire space: the ordered structure of inclusion on computably enumerable subsets of N can be embedded into the effective Wadge hierarchy of Σ 0 2 subsets of the Baire space; cf. Proposition 3.8 infra.
In this paper we concentrate on Wadge theory on the classes the Hausdorff difference hierarchy, i.e. on ∆ 0 2 Borel sets. We also consider the same problems but using only effective reductions. With this study we provide the general framework for the particular cases of effective Wadge hardness we used to define highly random reals in Grigorieff 2005, 2009). The paper is organized as follows. §2 recalls the basic definitions of the Borel and Hausdorff hierarchies and some material on domains and effective versions of various notions. In §3 we present Wadge reductions in general topological spaces, and their effective versions. We make explicit the relation between Wadge completeness and universality, and we recall what is already known about Wadge theory outside zero-dimensional spaces. In §4 we prove the main results of the paper. Theorem 4.8 characterizes Wadge hardness for the classes of the Hausdorff difference hierarchy in terms of alternating decreasing chains. Theorem 4.14 gives a similar characterization for Wadge one-to-one and finite-to-one completeness. We prove effective versions of these results.
Theorem 4.23 shows that, for the space of sets of natural numbers endowed with the Scott topology, in each class of the Hausdorff hierarchy there are two strictly increasing chains of Wadge degrees of sets properly in that class. The length of these chains is the rank of the considered class, and each element in one chain is incomparable with all the elements in the other chain. This result builds on the construction done by Selivanov (2005b) of two incomparable Wadge degrees which properly belong to an arbitrarily given Hausdorff class. Finally in §5 we prove results on Wadge theory for the Borel class Σ 0 2 .

Preliminaries
For any set A, PA denotes the powerset of A and P <ω A denotes the family of all finite subsets of A. We write N for the set of natural numbers. When X is a subset of N, and i ∈ N, X + i = {n + i n ∈ X} and iX = {i n n ∈ X}. Subsets of N are simply called sets, subsets of PN are called families, and collections of subsets of PN are called classes. As usual, N ω is the set of infinite sequences of natural numbers (the Baire space), and Z, Q, R denote the sets of integer, rational and real numbers, respectively. Greek letters α, β, γ, δ are used to denote ordinals. We write ω for the first infinite ordinal, ω 1 for the first uncountable ordinal, and ω CK 1 for the least non computable ordinal (the Church-Kleene ordinal). For any two ordinals α, β, α ∼ β means that they have the same parity.

Borel and Hausdorff Hierarchies
Following (Selivanov 2005b(Selivanov , 2008, we consider the Borel hierarchy and the Hausdorff-Kuratowski difference hierarchy in a general topological space P . The Borel hierarchy consists of classes of subsets of P , namely Σ 0 α , Π 0 α , ∆ 0 α , where 1 ≤ α < ω 1 . They are defined by induction on α : Σ 0 1 is the class of open subsets of P , Σ 0 2 is the class of countable unions of differences of open subsets of P , and, for α > 2, Σ 0 α is the class of countable unions of sets in ⋃ β<α Π 0 β . The class Π 0 α is the class of complements of sets in Σ 0 α and is the family of countable intersections of open sets (respectively countable unions of closed sets). In general, it is a proper subclass of Π 0 2 (respectively Σ 0 2 ). For an ordinal 1 ≤ α < ω 1 , the operation D α sends an α-sequence of sets (A β ) β<α to the set D α ((A β ) β<α ) = ⋃{Aβ ∖ ∪ γ<β A γ β < α, β ∼ α} (recall that β ∼ α means that α, β have different parities). The Hausdorff hierarchy is constituted by the Hausdorff classes D α , co-D α where 1 ≤ α < ω 1 . The class D α consists of all subsets of P of the form D α ((A β ) β<α ), where (A β ) β<α is an α-sequence of open subsets of P (with no loss of generality, this α-sequence can be supposed increasing with respect to the inclusion relation). The class co-D α is the class of complements of sets in D α . The Hausdorff-Kuratowski hierarchy is obtained by replacing open sets by sets in a Σ 0 ξ class, ξ < ω 1 : its classes are denoted by D α (Σ 0 ξ ) and co-D α (Σ 0 ξ ). Hausdorff-Kuratowski theorem ensures that ⋃ 1≤α<ω1 D α (Σ 0 ξ ) = ∆ 0 ξ+1 for any 1 ≤ ξ < ω 1 . When the space P is not obvious from the context, or when we want to make it explicit, we will add a parenthesized reference to the space P , writing Σ 0 ). Let us mention the following classical result.
Fact 2.1. If f ∶ P → Q is continuous then the inverse image of a subset of Q in some Borel or Hausdorff-Kuratowski class of Q is in the corresponding class of subsets of P .

Domains
We briefly recall the main definitions and refer the reader to classical papers and books, for instance (Abramsky & Jung 1994;Edalat 1997;Gierz & al. 2003). A directed com-plete partial order (dcpo) is a partially ordered set (P, ⊑) such that every non empty directed subset S has a least upper bound (denoted by ⊔S). A subset X of P is an upset (respectively downset) if, for all x, y ∈ P , if x ∈ X and x ⊑ y (respectively y ⊑ x) then y ∈ X. The Scott topology on a dcpo P admits as closed sets all downsets closed under suprema of directed subsets of P . Thus, open subsets are upsets O such that every directed set with supremum in O has an element in O. The Scott topology is T 0 (if x ≠ y then there exists an open set which contains only one of the two points x, y). The order relation ⊑ can be recovered from the Scott topology as the specialization order: x ⊑ y if and only if every open set which contains x also contains y. A function f ∶ P → Q between two dcpo's is continuous with respect to the Scott topologies if and only if it is increasing and preserves suprema of directed subsets: if S ⊆ P is directed then f (⊔S) = ⊔f (S).
The approximation (or way-below) relation in a dcpo (P, ⊑) is defined as follows: The set of compact elements is denoted K(P ). A continuous domain is a dcpo such that, for every x ∈ P , the set ↡x = {z ∈ P z ≪ x} is directed and x = ⊔ ↡x. A basis of a continuous domain is any set B such that, for all x, B∩ ↡ x is directed and x = ⊔(B∩ ↡ x). An ω-continuous domain is a dcpo admitting a countable basis. An ω-algebraic domain is a dcpo for which K(P ) is a countable basis. If B is a basis of a continuous domain then the sets ↟b, for b ∈ B, form a topological basis, where ↟x = {y x ≪ y}. Let us mention the classical interpolation property.
Fact 2.2. Let B be a basis of the continuous domain P . Suppose y ∈ P and X ⊆ P is finite such that for each x ∈ X, x ≪ y. Then, there exists b ∈ B such that for each x ∈ X x ≪ b and b ≪ y.

The Scott Domain PN
The ordered set (PN, ⊆) is an ω-algebraic domain, its compact elements are the finite sets and X ≪ Y if and only if X is finite and included in Y . A topological basis of the Scott topology is the class {B A A ∈ P <ω N} where B A = {X ∈ PN A ⊆ X}. The Scott topology gives "positive information" about sets, and contrasts with the Cantor topology on 2 ω which gives positive and negative information about sets via their characteristic functions. As recalled before, the Scott topology on PN is As observed by Selivanov (2005b) the classes of finite rank of the Scott Borel hierarchy in PN do not coincide with the corresponding ones in the Cantor space 2 ω : for all n ∈ N, In particular, f −1 is also continuous. Indeed, the inclusion order is a topological notion (namely, the specialization order) hence f is an automorphism of (PN, ⊆) and as such, respects unions and maps singleton sets into singleton sets. Let us mention a classical result which shows that PN is "universal" for ω-continuous domains. 1 The map ϕ is a dcpo embedding (i.e. an isomorphism between (P, ⊑) and (ϕ(P ), ⊆) such that {x ∈ P ϕ(x) ⊆ Z} is directed for any Z ∈ PN). 2 The map ϕ is is a topological embedding of P into PN (i.e. an homeomorphism from P to the subspace ϕ(P ) of PN). Then, for any Borel or Hausdorff-Kuratowski class Proof. We just prove items 2 and 3. Since ϕ is injective, it suffices to consider the case of basic open sets ↟b n 's of P . Observe that ϕ(↟b n ) = {ϕ(x) x ∈ P, b n ≪ x} = B {n} ∩ ϕ(P ). This proves item 2. For item 3 observe that X ∈ ϕ(P ) if and only if, relative to the approximation relation ≪ of P , Remark 2.4. Fact 2.3 allows us to transfer properties from PN to ω-continuous domains.
Definition 2.5. Let P, Q be T 0 second-countable topological spaces.
1 A presentation of the topology of P is an enumeration (not necessarily injective) (U n ) n∈N of some topological basis of P . For convenience, we shall sometimes consider enumerations indexed by N 2 or P <ω N.
An effective topological space consists of a T 0 second-countable topological space P together with an effective presentation of P . 3 Relative to a presentation (U n ) n∈N of the topology of P , an element x of P is effective (respectively computable) if the set {i ∈ N x ∈ U i } is computably enumerable (respectively computable). Let α < ω CK 1 be an infinite computable ordinal. A sequence (x β ) β<α of elements of P is effective (respectively computable) if there exists a computable relation R ⊆ N 2 , isomorphic to the ordering of α, such that, letting ρ ∶ N → α be the isomorphism between (N, R) and (α, <), the relation {(n, i) x ρ(n) ∈ U i } is computably enumerable (respectively computable). In that case, each element of the α-sequence is effective (respectively computable). 4 Relative to presentations (U n ) n∈N , (V n ) n∈N of the topologies of P and Q, a continuous Effective α-sequences of maps are defined as above.
Fact 2.6. Effective maps are closed under composition. They send effective elements onto effective elements, idem with α-sequences for α < ω CK 1 . Remark 2.7. If (U n ) n∈N , (V n ) n∈N are presentations of the topological spaces P and Q, then (U i × V j ) i,j∈N is a presentation of the product topological space P × Q.   1 A presentation of an ω-continuous domain P is an enumeration of some basis of P .
effective ω-continuous domain consists of an ω-continuous domain P together with an effective presentation of P .
Fix some presentations (p n ) n∈N , (q n ) n∈N of the (not necessarily effective) ω-continuous domains P and Q.
, domain-effective α-sequences of maps are defined as above.
It is an effective presentation of PN, (called the canonical presentation). An element X ∈ PN is domain-effective (respectively domain-computable) relative to this presentation if and only if it is a computably enumerable (respectively computable) subset of N.
where W e denotes the computably enumerable subset of N with code e.
Remark 2.11. If (p n ) n∈N , (q n ) n∈N are presentations of the ω-continuous domains P and Q then (p i , q j ) i,j∈N is a presentation of the product ω-continuous domain P × Q.
Fact 2.12. Let (p n ) n∈N , (q n ) n∈N be presentations of the ω-continuous domains P, Q.
A domain-effective map f ∶ P → Q between ω-continuous domains sends any domaineffective element of P to a domain-effective element of Q. Idem with domain-effective α-sequences for α < ω CK 1 .

2.4.4.
Topological effectiveness versus domain effectiveness. While Definition 2.5 gives the notions of element, sequence and map that are topology-effective, Definition 2.9 does it for the domain-effective notions. Since x ∈↟p i ⇔ p i ≪ x, for elements and sequences the two definitions of effectivity coincide.
Fact 2.13. Let (p n ) n∈N be a presentation of the ω-continuous domain P . An element x ∈ P is domain-effective (respectively domain-computable) if and only if it is topologyeffective (respectively topology-computable). Idem with α-sequences, for 1 ≤ α < ω CK 1 . In the case of ω-algebraic domains, Definition 2.5 and 2.9 the notion of effectivity coincides not only for elements and sequences but also for space presentations and maps.
Fact 2.14. Let (p n ) n∈N be a presentation of the ω-algebraic domain P consisting of compact elements. Let (q n ) n∈N be a presentation of the ω-continuous domain Q.
1 The presentation (p n ) n∈N of the ω-continuous domain is effective if and only if so is the presentation (↟p n ) n∈N of the Scott topology of P .
Finally, topological effective maps are also domain-effective.
be the two computably enumerable sets ensuring the domain-effectiveness and the topology-effectiveness of f . Inclusion S ⊆ T is straightforward. Though, in general, S and T are distinct, we 2.4.5. Effective embedding in PN. We give a version of Fact 2.3 that effectivizes the embedding of an ω-continuous domain P in PN.
Fact 2.16. Let (p n ) n∈N be a presentation of the ω-continuous domain (P, ⊑).
1 An element x ∈ P is effective (respectively computable) if and only if the set ϕ(x) = {n ∈ N p n ≪ x} is effective (respectively computable) relative to the canonical presentation of PN. Idem with α-sequences for α < ω CK 1 . 2 If the presentation (↟p n ) n∈N is effective then ϕ is a topology-effective embedding of (P, ⊑) in (PN, ⊆) (relative to the canonical presentation of PN). As a consequence, for every effective Borel or Hausdorff-Kuratowski class Γ, The universal quantification is bounded by the finite set A, so this last formula gives the computable enumerability of the set 3. Observe that in the proof of Fact 2.3 item 3, the sets R and {(i, j, k) k ∈ Z i,j } are computably enumerable.
Note 2.17. Item 1 in Fact 2.16 does not need that the presentation (p n ) n∈N be effective.

Wadge Hardness and Completeness
Definition 3.1. (Wadge 1972) Let P, Q be two topological spaces and C ⊆ P(P ).
it belongs to C. 4 Wadge reducibility, Wadge hardness and Wadge completeness are finite-to-one or oneto-one when the associated reductions are, respectively, finite-to-one or one-to-one. 5 The preordering ≤ W on subsets of P induces an equivalence relation. Its equivalence classes are called Wadge degrees.
Definition 3.2. Relative to fixed presentations (U n ) n∈N and (V n ) n∈N of the topological spaces P, Q, effective Wadge reducibility, hardness and completeness are obtained by requiring that only effective maps be considered in Definition 3.1.
One-to-one and finite-to-one Wadge reducibilities are not equivalent.
Proposition 3.3. In the Scott domain PN, Wadge reducibility, finite-to-one and oneto-one reducibilities are not equivalent. Idem with effective reducibilities.
The complements of these families respectively contain one set (namely ∅), two sets (namely ∅ and {0}), and infinitely many sets (namely ∅, {0} and all subsets of PN ∖ {0}). Thus, there can be no injective reduction of O 2 to O 1 , and no finite-to-one reduction of O 3 to both O 1 and O 2 . However, there is a finite-to-one effective reduction of Also, there is an effective reduction g of O 3 to both O 1 and O 2 : g(X) = X, if 0 ∈ X and there is n > 0 such that n ∈ X; otherwise g(X) = ∅.
Remark 3.4. Related to the above proposition, cf. Theorem 4.17 and Corollary 4.16.
For zero-dimensional Polish spaces, Wadge theory has beautiful properties.

(Duality theorem). Let
2 (Hardness theorem) For all ξ < ω 1 , the following conditions are equivalent: Remark 3.6. The zero-dimensional hypothesis is necessary in Theorem 3.5 (cf. Hertling 1996aHertling ,1996bIkegami 2010;Schlicht 2011). For instance, consider the closed interval But this is a contradiction since, being continuous, reductions are increasing with respect to subset inclusion.
Theorem 3.5 does not have an effective version because determinacy is not guaranteed in the effective world. As pointed to us by an anonymous referee, the arguments given by Fokina, Friedman and Tornquist (2010) yield the following result.
Proposition 3.8. The ordered structure of inclusion on computable (respectively computably enumerable) subsets of N can be embedded into the ordered structure of effective Wadge degrees (i.e. degrees relative to computable reductions) of Π 0 1 (respectively Σ 0 2 ) subsets of the Baire space.
Proof. We follow the arguments in the proof of Theorem 9 in Fokina, Friedman and Tornquist (2010). Their Theorem 6 establishes that there is a uniform sequence (A n ) n∈N of nonempty Π 0 1 subsets of N ω such that, for each n, there is no hyperarithmetical function F ∶ N ω → N ω such that F (A n ) ⊆ ⋃ m≠n A m . We also use that the computable sequence 0 ω is in no A n , stated as a Remark after their Theorem 5.
Case of computable subsets of N. For f ∈ N ω and k ∈ N, let kf ∈ N ω be such that Since k ∉ Y , the assumed property of the A n 's ensures that G hence also the reduction F cannot be hyperarithmetical. Thus, there is no computable reduction of A * X to A * Y . Case of computably enumerable subsets of N. For X ⊆ N computably enumerable, let A † X be the Σ 0 2 set 0 <ω 1A * X . Let (n i ) i∈N be a computable enumeration of X and consider the map F ∶ N ω → N ω such that F (0 p 1n i f ) = 0 p+i 1n i f for all p, i ∈ N, f ∈ N ω , and F takes value 0 ω elsewhere. Then F is computable and reduces A † X to A † Y for any X ⊆ Y . As before, A † X cannot be effectively reduced to A † Y in case X ⊆ Y .
Definition 3.9. Let P, Q be topological spaces, Γ a Borel or Hausdorff-Kuratowski class.
. If Φ is oneto-one in its second argument then S is said to be one-to-one strongly P -universal. 3 Fix some presentations of P, Q. If Γ is an effective class, we get corresponding effective notions by requiring equality Γ(Q) = {U p p ∈ P, p effective} in item 1 and equality Γ(Q) = {Φ −1 p (S) p ∈ P, p effective} with Φ an effective map in item 2.
1 If there is some strongly P -universal set S for Γ(Q) then there is some P -universal set U for Γ(Q) : let U = Φ −1 (S), for a witness Φ of the strong P -universality of S.
2 Effective strong universality is a variant of the notion of universal partial computable function in Blum's isomorphism theorem (recall that a partial computable ψ x)), cf. Rogers 1967, pages 54, 191).
Wadge completeness lies between universality and strong universality.
Proposition 3.11. Let Γ be a Borel or Hausdorff-Kuratowski class. Let P, Q be topological spaces.
1 If S is (one-to-one) strongly P -universal for Γ(Q) then S is (one-to-one) Wadge complete for Γ(Q). An effective version holds relative to fixed presentations of P, Q. 2 Let C(Q, Q) be the set of continuous maps Q → Q endowed with any topology at least as fine as the topology of pointwise convergence. If S is Wadge complete for An effective version holds relative to presentations of Q and of a topology on C(Q, Q) finer than that of pointwise convergence.
Proof. 1. Let X be in Γ(Q). Since S is strongly universal, there exists p ∈ P such that so a −1 preserves Borel and Hausdorff-Kuratowski classes. Thus, U = a −1 (S) ∈ Γ(C(Q, Q) × Q). Since S ∈ Γ(Q), the set U f is in Γ(Q) for all f ∈ C(Q, Q). Since S is Wadge hard for Γ(Q), every X ∈ Γ(Q) is of the form X = f −1 (S) for some f ∈ C(Q, Q). Hence, f −1 (S) = U f . If Q is not a countable set, the pointwise topology on C(Q, Q) has no countable basis. For the effective version we need a finer topology: If (V i ) i∈N is a presentation of Q, a convenient topology on C(Q, Q) has a presentation ( Wadge completeness coincides with strong universality when this last condition is not void. Fact 3.12. If there is a strongly P -universal set for Γ(Q) then every Wadge complete set for Γ(Q) is strongly P -universal for Γ(Q). One-to-one and effective versions also hold.
Proof. Suppose U is a strongly P -universal set for Γ(Q) and V is a Wadge complete set for Γ(Q). Any continuous reduction from V to U composed with a witness of the strongly P -universality of U yields a witness of the strongly P -universality of V .
There are also cases in which universality grants Wadge completeness.
Fact 3.13. Suppose h ∶ P × Q → Q is a homeomorphism. If U is P -universal for Γ(Q) then h(U ) is one-to-one Wadge complete for Γ(Q).
By classical arguments (Kechris, 1995) Wadge hardness and P -universality can be lifted with set-theoretical operations of complements, (countable) unions, intersections and differences. When P , P 2 and P ω (endowed with the product topologies) are all homeomorphic (for example N ω , 2 ω or PN), one can lift Wadge completeness (respectively, P -universality) for a class D α (Σ ξ (Q)) to that for a class D β (Σ µ (Q)) as long as either ξ < µ or else ξ = µ and α is less or equal to β.

Known Outside the Baire Space
The following simple result shows that PN is for ω-continuous domains what the Baire space N ω is for Polish spaces. It can be seen as an extension of Facts 2.3 and 2.16.
Proposition 3.14. For every Polish space (respectively ω-continuous domain) Q there is a N ω -universal (respectively PN-universal) set for Σ 0 1 (Q). Given presentations of the topological spaces N ω and Q (respectively the ω-continuous domains PN and Q), this universal set is in the effective class relative to the associated presentation of N ω × Q (respectively PN × Q), cf. Remarks 2.7, 2.11.
Proof. We argue for the case of ω-continuous domains.
Applying Fact 3.13 and Proposition 3.14, one obtains the existence of Wadge complete sets for domains such as PN, a result proved in (Selivanov 2005b). Proposition 3.16. (Selivanov 2005b, Proposition 6.4 i) Let P be an ω-continuous domain and n ∈ N. Every set in ∆ 0 2 (P ) but not in co-D n (P ) is Wadge hard for D n (P ).
Polish spaces and ω-continuous domains have been put in an elegant unifying framework: the quasi-Polish spaces (de Brecht 2011). Up to homeomorphism, quasi-Polish spaces coincide with the Π 0 2 subspaces of PN. Wadge hardness results transfer from PN to quasi-Polish spaces as follows.
Let P be a topological space. Any set H ⊆ P that is Wadge hard for Γ(PN) is also Wadge hard for Γ(Q) for every quasi-Polish space Q.
Proof. Since every quasi-Polish space is homeomorphic to a Π 0 2 subspace of PN, we can suppose Q is a Π 0 2 subspace of PN. The hypothesis on Γ ensures that Q is in Γ(PN). If A ∈ Γ(Q) then A = A ′ ∩ Q for some A ′ ∈ Γ(PN) hence A ∈ Γ(PN). The restriction to Q of any continuous reduction of A ′ to H is a reduction of A to H.

Alternating Chains
Recall that we write α ∼ β to indicate that α and β have the same parity.
Definition 4.1. Let (P, ⊑) be a dcpo, A a subset of P and α an ordinal.
2 An A-special (α + 1)-chain is an A-alternating decreasing chain (x β ) β≤α such that Remark 4.3. As proved by Selivanov (2005bSelivanov ( , 2008, when α is infinite and A is ∆ 0 2 A-alternating increasing chains do not exist. In fact, if A is in the difference of two open sets and the supremum of an increasing chain (x n ) n∈N is in A then the x n 's are in A for all n large enough. By considering countable unions, it follows that the same is true if A is Σ 0 2 . This property forbids A-alternation of increasing infinite chains if A is ∆ 0 2 .

Wadge Hardness and Alternating Decreasing (α + 1)-Chains
If A is in ∆ 0 2 then long A-alternating decreasing infinite chains do exist in PN.
1 There exists a family A ∈ D α (PN) and an A-special chain (X β ) β≤α such that X α and X β ∖ X β+1 , for all β < α, are infinite subsets of N. 2 If α < ω CK 1 then A can be taken in the effective class D α (PN) and the chain can be taken computable (cf. Definition 2.9).
Proof. Let β ↦ a β be a bijection α → 3N. Let (A β ) β≤α be a family of pairwise disjoint infinite subsets of 3N Observe that a set X is in A if and only if it meets {a β β < α} and the least β < α such that a β ∈ X has parity different from that of α.
In particular, if X β ⊇ X ⊃ X β+1 then X ∈ A if and only if β ∼ α. Thus (X β ) β≤α is an A-special chain. Effectivization is straightforward.
In general in continuous domains, long decreasing chains may not exist. For instance in the ω-algebraic domain (2 ≤ω , ⊑) of finite and infinite binary words with the prefix ordering, every decreasing chain is finite. However, in case a long decreasing chain exists then it can always be viewed as an A-alternating chain for some A ∈ ∆ 0 2 .
Proposition 4.5. Let P be a continuous domain and α < ω 1 be an ordinal.
1 Every strictly decreasing chain (x β ) β≤α in P is A-special for some A ∈ D α (P ). 2 Suppose P is ω-continuous and fix some presentation of P . If α < ω CK 1 and the chain is computable then we can take A ∈ D α (P ).
Proof. Let B be a basis of P . In the vein of Fact 2.3, we use the isomorphism ψ between (P, ⊑) and a subspace of (P(B), ⊆) such that ψ( For the effective version, using a presentation (b i ) i∈N , replace ψ with ϕ of Facts 2.3 and 2.16 such that ϕ(x) = {i ∈ N b i ≪ x}. The computability of the chain (x β ) β≤α ensures that of (ϕ(x 0 ) ∖ ϕ(x β+1 )) β≤α .
Note 4.6. An effective chain is not enough for the above proof: being differences of computably enumerable sets, the sets ϕ(x 0 ) ∖ ϕ(x β+1 ) might not be computably enumerable.
Remark 4.7. The proof of Proposition 4.5 amounts to a proof for the case P = P(κ), where κ is cardinal, and a transfer to all continuous domains having a basis of cardinality ≤ κ via an obvious extension of Fact 2.3. Idem for effectivization with κ = ω and Fact 2.16.
We present now one of the main theorems of the paper. For the effective part of the result we use the following convention: effective reductions P → Q are relative to the presentations (↟p n ) n∈N and (↟q n ) n∈N of the Scott topologies on P, Q associated to presentations (p n ) n∈N and (q n ) n∈N of the ω-continuous domains P, Q.
Theorem 4.8. Let Q be a continuous domain, H ⊆ Q and α < ω 1 be an ordinal.
1 The following conditions are equivalent.
(i) H is Wadge hard for D α (P ) for every continuous domain P .
(iii) H is Wadge hard for D α (P ) for some continuous domain P admitting a strictly decreasing chain of length α + 1. (iv) There exists a decreasing H-alternating chain in Q of length α + 1.
2 Suppose Q is an ω-continuous domain and fix some presentation (q n ) n∈N of Q. If α < ω CK 1 the following conditions are equivalent. (i e ) H is Wadge hard for D α (P ) and effectively Wadge hard for D α (P ) for every effective ω-continuous domain P (cf. Definition 2.9).
(ii e ) H is effectively Wadge hard for D α (PN).
(iii e )H is effectively Wadge hard for D α (P ) for some effective ω-algebraic domain P admitting a computable strictly decreasing chain of length α + 1.
(iv e ) There exists an effective decreasing H-alternating chain in Q of length α + 1.
Proof. (i) ⇒ (ii). Particularize item (i) with P = PN. (ii) ⇒ (iii). Let P = PN and use Proposition 4.4. (iii) ⇒ (iv). By Proposition 4.5, the strictly decreasing chain in P of length α+1 given by (iii) is A-alternating for some A ∈ D α (P ). A continuous reduction of A to H maps this A-alternating chain onto a decreasing H-alternating chain in Q.
(iv) ⇒ (i). Let (y β ) β≤α be a decreasing H-alternating chain of length α + 1. Suppose X is a set in D α (P ). Then X = ⋃ β<α,β ∼α V β ∖ ⋃ γ<β V γ for some increasing chain (V β ) β≤α of open sets. Define τ ∶ P → α + 1 and f ∶ P → Q as follows: for z ∈ P , Since the V β 's are increasing and are open hence are upsets in P , τ is decreasing and f is increasing. Letting B be a basis of P , we have V β = ⋃ c∈I β ↟c for some I β ⊆ B. Thus, The last equality shows that f is continuous. Finally, observe that z ∈ X if and only if τ (z) < α and τ (z) ∼ α if and only if f (z) = y τ (z) ∈ H. Thus, f reduces X to H.
(iii e ) ⇒ (iv e ). By Proposition 4.5, the chain in P of length α + 1 given by (iii) is A-alternating for some A ∈ D α (P ). Observe that an effective reduction from A to H maps this computable chain onto an effective decreasing H-alternating chain.
(iv e ) ⇒ (i e ). Suppose X ∈ D α (P ). Keeping the notation as in the proof of (iv) ⇒ (i), we first show that the reduction f ∶ P → Q of X to H is domain-effective. Let (p i ) i∈N and (q ℓ ) ℓ∈N be presentations of P and Q such that (p i ) i∈N is effective, i.e. {(i, j) p i ≪ p j } is computably enumerable. Since α < ω CK 1 and the chain (y β ) β≤α is effective, there exists an initial segment S of N, a set R ⊂ S 2 and a map ρ ∶ S → α + 1 such that ρ is an isomorphism (necessarily unique) between (S, R) and (α + 1, ≤), -the relation {(n, ℓ) q ℓ ≪ y ρ(n) } is computably enumerable.
Thus, the set {(i, ℓ) q ℓ ≪ f (p i )} is obtained via conjunction, disjunction and projection of computably enumerable sets. As such, it is computably enumerable. This proves f is a domain-effective map.
If P is ω-algebraic and the p n 's are compact elements then Fact 2.14 ensures that the reduction f is also topology-effective. In the general case where P is only ω-continuous, we argue as follows. Consider the map ϕ ∶ P → PN such that ϕ(x) = {n ∈ N p n ≪ x}. Since the presentation (p n ) n∈N of P is effective, Fact 2.16 ensures that ϕ is a topological embedding which is topology-effective (relatively to the canonical presentation of PN) and that ϕ(X) = Y ∩ ϕ(P ) for some Y ∈ D α (PN). Since PN is an effective ω-algebraic domain, the above argument applied to the subset Y of PN, yields a reduction g ∶ PN → Q of Y to H which is topology-effective. The composition g ○ ϕ ∶ P → Q is then a reduction of X to H which is also topology-effective.  1 If Q admits some strictly decreasing chain of length α + 1 then there exists a Wadge complete set for D α (Q). In particular, this applies if Q = PN. 2 Suppose Q is an effective ω-continuous domain. If Q admits some computable strictly decreasing chain of length α + 1 then there exists a Wadge complete set for D α (Q) which is also effectively Wadge complete for D α (Q). In particular, this applies if Q = PN.
Proof. By Proposition 4.5, the assumed strictly decreasing chain of length α + 1 is H-special, hence H-alternating for some H ∈ D α (Q). Thus item (iv) of Theorem 4.8 is satisfied; then, item (i) of Theorem 4.8 also holds, hence H is as desired. The possible instantiation Q = PN comes from Proposition 4.4. Effectivization is straightforward.

One-to-one Wadge Completeness and Alternating Decreasing Chains
Universal properties as those in part 1 (i) of Theorem 4.8 cannot hold with one-to-one Wadge reductions f ∶ P → Q since such reductions can only exist if Q has cardinality at least that of P . Therefore, we shall restrict to ω-continuous domains. The version of Theorem 4.8 for one-to-one hardness relies on the following notion.
Definition 4.11. Let (P, ⊑) be an ordered set and α an ordinal.
1 The following conditions are equivalent.
In case the chain is A-special, (b) ⇒ (c) and (c) ⇒ (a) are straightforward.
Corollary 4.13. Let α < ω 1 be an ordinal. There exists A ∈ D α (PN) and an A-scattered chain of length α + 1. If α < ω CK 1 then we can take A ∈ D α (PN) and get a computable A-scattered chain of length α + 1.
To characterize effective Wadge one-to-one hardness we use the same convention as in Theorem 4.8: effective reductions P → Q are relative to the presentations (↟p n ) n∈N and (↟q n ) n∈N of the Scott topologies on P, Q for presentations (p n ) n∈N and (q n ) n∈N of the ω-continuous domains P, Q.
Theorem 4.14. Let Q be an ω-continuous domain, H ⊆ Q and α < ω 1 be an ordinal.
1 The following conditions are equivalent.
(i) H is one-to-one Wadge hard for D α (P ) for every ω-continuous domain P .
(ii) H is one-to-one Wadge hard for D α (PN).
(iii)H is one-to-one Wadge hard for D α (P ) for some continuous domain P admitting a scattered chain of length α + 1. (iv) There exists an H-scattered chain in Q of length α + 1.
2 Fix some presentation (q n ) n∈N of Q. If α < ω CK 1 the following conditions are equivalent.
(i e ) H is one-to-one Wadge hard for D α (P ) and effectively one-to-one Wadge hard for D α (P ) for every effective ω-continuous domain P (cf. Definition 2.9).
(ii e ) H is effectively one-to-one Wadge hard for D α (PN).
(iii e )H is effectively one-to-one Wadge hard for D α (P ) for some effective ω-algebraic domain P admitting a computable scattered chain of length α + 1.
(iv e ) There exists an effective H-scattered chain in Q of length α + 1.
Proof. (i) ⇒ (ii). Particularize item (i) with P = PN. (ii) ⇒ (iii). Let P = PN and use Corollary 4.13. (iii) ⇒ (iv). By Proposition 4.5, the strictly decreasing chain in P of length α + 1 given by (i) is A-special for some A ∈ D α (P ). Being scattered and A-special, this chain is A-scattered. A one-to-one continuous reduction of A to H maps this A-scattered chain onto an H-scattered chain in Q.
(iv) ⇒ (i). Fix some presentation (b i ) i∈N of P . Let (y β ) β≤α be the H-scattered chain and θ β 's, β ≤ α, the one-to-one continuous maps PN → P as in Definition 4.11. We keep the notations in the proof of the same implication in Theorem 4.8. Let f ∶ P → Q be the continuous reduction of X to H constructed in this proof: Since θ β is one-to-one we have g(z) ≠ g(t). Let us now see that g ∶ P → Q is continuous. It is clear that g is increasing. Suppose z = ⊔ n∈N z n where (z n ) n∈N is an increasing sequence of elements of P . Since z ∈ V τ (z) and V τ (z) is open, for n large enough, z n is also in V τ (z) hence τ (z n ) ≤ τ (z). Now, τ ∶ P → {β β ≤ α} is decreasing so that τ (z n ) ≥ τ (z). Thus, we get equality τ (z n ) = τ (z). Consequently, g(z) and the g(z n )'s, for n large enough, are of the form θ β (z) and θ β (z n ) for the same β = τ (z). Since θ β is continuous we get g(z) = θ β (z) = ⊔ n∈N θ β (z n ) = ⊔ n∈N g(z n ). This proves continuity of g.
The next Corollary was known for the domain PN, (Selivanov 2005b), cf. Corollary 3.15.
Corollary 4.15. Let Q be an ω-continuous domain and α < ω 1 be a countable ordinal.
1 If Q admits some scattered chain of length α + 1 then there exists a one-to-one Wadge complete set for D α (Q). In particular, this applies if Q = PN. 2 Suppose Q is ω-continuous and admits an effective presentation. Fix such an effective presentation. If Q admits some computable scattered chain of length α + 1 then there exists a one-to-one Wadge complete set for D α (Q) which is also effectively Wadge complete for D α (Q). In particular, this applies if Q = PN.
Proof. Using Corollary 4.13 the proof is similar to that of Corollary 4.10.
Wadge completeness does not coincide with one-to-one Wadge completeness in PN.
Corollary 4.16. There are Wadge complete families for D α (PN) which are not Wadge one-to-one complete.
Proof. Consider a partition (A β ) β<α of N in infinite sets and let A α = ∅. Let X β = ⋃ β≤δ≤α A δ and U β be the sets that meet ⋃ γ≤β A γ . Let H = D α ((U β ) β<α ). Since (X β ) β<α is a decreasing H-alternating chain, Theorem 4.8 ensures that H is Wadge complete for D α (PN). Observe that ⋃ β<α U β = PN ∖ {∅}. Thus, every decreasing H-alternating chain of lenghth α + 1 has the empty set as last element hence it cannot be scattered. This shows that H cannot be Wadge one-to-one complete.

Finite-to-one Wadge Completeness and Alternating Decreasing Chains
In the case of the ω-continuous domain (PN, ⊆) finite-to-one and one-to-one Wadge hardness concide. 1 The following conditions are equivalent.
(i) H is finite-to-one Wadge hard for D α (PN).
(ii) H is one-to-one Wadge hard for D α (P ) for every ω-continuous domain P .
2 Fix some presentation of Q. If α < ω CK 1 the following conditions are equivalent. (i e ) H is effectively finite-to-one Wadge hard for D α (PN).
(ii e ) H is one-to-one Wadge hard for D α (P ) and effectively one-to-one Wadge hard for D α (P ) for every effective ω-continuous domain (cf. Definition 2.9).
(i e ) ⇒ (ii e ). Routine variation of the above argument.

Increasing Chains of Wadge Degrees
Combining a construction given by Selivanov (2005b) with decreasing chains of sets, we get increasing chains of proper D α (PN) Wadge degrees. We write N <ω for the set of finite sequences of natural numbers, and N ≤ω for N <ω ∪ N ω . nil denotes the empty sequence.
And, for each ordinal α, let Y α = {e(σ) σ ∈ T has odd length } and Z α = Y α ∪ B(T ). Before entering the construction of the chains of Wadge degrees, a simple lemma.
Lemma 4.20. Let E be a topological space.
, L is open and C ⊆ L and L and D are disjoint then C ∪ D ∈ D α (E).
Hence, either f (N) ∉ B(T ) or 0 ∉ f (N). Suppose f (N) ∉ B(T ). Then f (N) ⊆ e(σ) for some σ ∈ T . In particular, f (N) is finite hence has finitely many subsets. This contradicts the fact that the infinite decreasing Y α,β -alternating chains are mapped by f to infinite decreasing Z α,δ -alternating chains below f (N). If, instead, 0 ∉ f (N ), then 0 ∉ f (X) (for all X) hence f reduces Y α,β to Y α,δ = A δ ∪ Y α hence to A δ (since all sets in Y α contain 0 whereas no f (X) does). This is already a contradiction since δ < α, Y α,β is a proper D α (PN) set by item 1, and A δ is a D δ (PN) set by the proof of item 1. Finally, we check that Z α,δ ≤ W Y α,β . Since N ∈ Z α,δ (it is in B(T )) we have f (N) ∈ Y α,β . If f (N) ∈ Y α then f (N) is finite. This contradicts the existence of infinite alternating decreasing chains. Thus, f (N) ∈ A β hence f (N) is included in 2N + 1. Since f is increasing, f takes values in P (2N + 1). Thus, f reduces Z α,δ to A β . But β < α, Z α,δ is a proper D α (PN) set by item 1, and A β is a D β (PN) set by the proof of item 1, the same contradiction as before. 4. Since α < ω CK 1 , the tree T in Definition 4.18 can be taken computable. Then Y α is a computable subfamily of P <ω N and B(T ) is an effective open family. We can take a computable enumeration (a δ ) δ<α as in Definition 4.21. Thus, the Y α,β 's and Z α,γ 's are in D α (PN). To see that for β < γ, Y α,β is effectively reducible to Y α,γ , and Z α,β is effectively reducible to Z α,γ , observe that the map f defined in the proof of item 2 is effective.

Wadge Hardness in PN Versus Wadge Hardness in Other Spaces
Due to the universality property of PN (cf. Proposition 3.14), Wadge hardness relative to a Borel class of PN is stronger than Wadge hardness relative to the same Borel class of many other spaces. 5.1. Simple Wadge Complete Sets in PN for Σ 0 2 Definition 5.1. Let S 2 = {X ∈ PN ∃n (2n ∈ X ∧ 2n + 1 ∉ X)}.
Proof. From its definition it is clear that S 2 is Σ 0 2 (PN). Consider a Σ 0 2 (PN) family X = ⋃ n∈N {Z ∃A ∈ A n Z ⊇ A} ∖ {Z ∃B ∈ B n Z ⊇ B}, where the A n 's and B n 's are families of finite sets. Define f ∶ PN → PN as Then, X ∈ X ⇔ ∃n (2n ∈ f (X) ∧ 2n + 1 ∉ f (X)) ⇔ f (X) ∈ S 2 . Observe that f is continuous hence it is a reduction of X to S 2 . In case X is Σ 0 2 (PN) then the A n , B n are uniformly computably enumerable so that f is effective.
5.2. Alternating Increasing Chains for Σ 0 2 (PN) Families As stated in Remark 4.3, in ω-continuous domains there are no increasing A-alternating chains of length ω when A is ∆ 0 2 . This is not true anymore for A in Σ 0 2 .
Proposition 5.3. For every ordinal α < ω 1 , there exists in PN an S 2 -alternating increasing chain with length α. If α < ω CK 1 then the sequence can be taken computable.
Remark 5.4. As a corollary, we see that the space 2 ≤ω , where all increasing chains have length at most ω + 1, contains no Wadge hard set for Σ 0 2 (PN). The above proposition can be improved. We first define a notion of alternating chain.
Definition 5.5. Let (E, ≤) be a linear ordering and A ⊆ E. Let (P, ⊑) be a partially ordered set and H ⊆ P .
1 A is an alternation on E if, for all a, b ∈ E, the following conditions are satisfied.
-If b is successor to a then a ∈ A if and only if b ∉ A.
-If a has no predecessor nor successor then a ∉ A. 2 An (H, A)-alternating E-chain in P is an E-sequence (x a ) a∈E of elements of P that satisfies the following conditions: for all a, b ∈ E, We now define a very rich linear order with respect to alternation.
Remark 5.7. The above linear order is very rich in the following sense. In a linear order (E, ≤) let ∼ E be the equivalence relation such that x ∼ E y if and only if there are finitely many elements between x and y (i.e. we identify an element with its successor if there is one). If (E, ≤) has countably many successor pairs and its quotient is embedded in R then (E, ≤) is embedded in R.
Proposition 5.8. Le P be an ω-continuous domain and H ⊆ P . 1 If H is Wadge hard for Σ 0 2 (PN) then P contains an (H, A)-alternating R-chain for every alternation A on R (cf. Definition 5.6). In particular, the set P ∖ H has cardinality 2 ℵ0 . 2 Suppose P is an ω-continuous domain and fix some presentation (p i ) i∈N of P . If H ⊆ P is effectively Wadge hard for Σ 0 2 (PN) then, for every alternation A on R which is computable as a subset of Q × Z, P contains an (H, A)-alternating R-chain (u ξ ) ξ∈R such that the sets {(q, n, i) q ∈ Q, n ∈ Z, p i ≪ u (q,n) } and {(q, i) q ∈ Q, ∀x ∈ R ∖ Q (q < x ⇒ p i ≪ u x )} are both computably enumerable. In particular, the set P ∖ H has cardinality 2 ℵ0 .