{'fraction_non_alphanumeric': 0.0624098597089288, 'fraction_numerical': 0.016894865983629586, 'mean_word_length': 3.530335171828596, 'pattern_counts': {'":': 0, '<': 64, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 17, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Borel and Hausdorff Hierarchies in Topological Spaces of Choquet Games and Their Effectivization

What parts of classical descriptive set theory done in Polish spaces still hold for more general topological spaces, possibly T0 or T1, but not T2 (i.e. not Hausdorff)? This question has been addressed by Victor Selivanov in a series of papers centered on algebraic domains. And recently it has been considered by Matthew de Brecht for quasi-Polish spaces, a framework that contains both countably based continuous domains and Polish spaces. In this paper we present alternative unifying topological spaces, that we call approximation spaces. They are exactly the spaces for which player Nonempty has a stationary strategy in the Choquet game. A natural proper subclass of approximation spaces coincides with the class of quasi-Polish spaces. We study the Borel and Hausdorff difference hierarchies in approximation spaces, revisiting the work done for the other topological spaces. We also consider the problem of effectivization of these results.


Introduction
The primary setting of descriptive set theory, including the study of Borel and Hausdorff hierarchies, is that of Polish spaces. These are spaces homeomorphic to complete metric spaces that have a countable dense subset, for example the Cantor space, the Baire space, the real line and its intervals. The question of what parts of classical descriptive set theory still hold for non-Polish spaces, specifically for general T 0 topological spaces, has not been yet systematically studied. Major progress has been done by Victor Selivanov in his investigations centered mainly in algebraic domains (directed complete partial orders with a countable base of compact elements) in an ongoing series of papers on this topic that started in 1978. Recently, Matthew de Brecht (2011) presented the theory of quasi-Polish spaces, a unifying framework for Polish spaces and countably based domains (i.e., ω-continuous domains, or directed complete partial orders with a countable basis).
De Brecht characterized quasi-Polish spaces in terms of the Choquet topological games, and he proved that descriptive set theory can be nicely developed in such spaces.
In this paper we consider alternative unifying topological spaces, that we call approximation spaces. Not only they contain all Polish spaces and all continuous domains, but a natural subclass of approximation spaces coincides with the class of quasi-Polish spaces. Approximation spaces can be viewed as the "à la domain" version of the "à la Polish" unifying framework of de Brecht. These spaces can also be characterized in terms of Choquet games. We study the Borel and Hausdorff difference hierarchies in approximation spaces, revisiting the work done for the other topological spaces. We also consider the problem of effectivization of these results.
The paper is organized as follows. §2 presents the preliminary material. We recall the needed notions about the Borel and Hausdorff hierarchies in a T 0 (possibly not T 2 ) topological context. We give an overview of the needed material on domains with the Scott topology and quasi-Polish spaces. We also present some prerequisites on the Banach-Mazur and Choquet topological games.
§3 is devoted to the class of approximation spaces. We prove that both, Polish spaces and continuous domains, are approximation spaces. Indeed, we show that all quasi-Polish spaces are approximation spaces. Theorem 3.10 characterizes approximation spaces in terms of Choquet games. Theorem 3.12 proves that quasi-Polish spaces and convergent approximation spaces are the same class.
In the context of Polish spaces, the Baire property asserts that any countable intersection of dense open sets is dense. Thus, countable intersections of open sets, the G δ sets, constitute the Π 0 2 level of the Borel hierarchy. In the context of T 0 but not T 2 spaces this is not true any more: the Π 0 2 level consists of countable intersections of Boolean combinations of open sets. Then it is natural to consider the Π 0 2 Baire property which asserts that any countable intersection of dense differences of open sets is dense. As shown by de Brecht (2011), the usual G δ Baire property and Hausdorff-Kuratowski's theorem both hold for quasi-Polish spaces. Consequently, these two results are ensured for convergent approximation spaces. Theorem 3.14 proves that, in fact, all approximation spaces satisfy the Π 0 2 Baire property. Theorem 3.16 extends Hausdorff's theorem to spaces having a countable basis and such that every closed subspace is an approximation space: the ∆ 0 2 class coincides with the difference hierarchy. This result was previously obtained by Selivanov for ω-algebraic domains and then for ω-continuous domains (Selivanov 2005(Selivanov , 2008. De Brecht (2011) proved that the full Hausdorff-Kuratowski Theorem holds for quasi-Polish spaces; hence, it holds for convergent approximation spaces. We do not know whether it holds for all approximation spaces.
In §4 we revisit a part of Selivanov's work (2005,2008) on domains that does not apply to Polish spaces: his characterization of the classes of the Hausdorff hierarchy in terms of alternating trees, and his proof of non existence of ambiguous sets in this hierarchy. We check that the assumption of ω-algebraicity or ω-continuity can be replaced, mutatis mutandis, by that of continuity.
§5 is devoted to effectivization. The definition of approximation spaces admits a straightforward definition of an effective version. We make the first steps in developing the effective theory. We first recall the notions of effective topological space and effective domains.
We also include the known machinery of effective Borel codes. Thorem 5.17 proves a weak effective version of Hausdorff's theorem in effective approximation spaces. We obtain this proof as an adaptation of Selivanov's work (2003) for the Baire space. A general effective version of Hausdorff's theorem is still an open question.
Acknowledgement. We thank Martín Escardó for pointing out the work of Matthew de Brecht on quasi-Polish spaces and for giving us very helpful references. Also we are indebted to an anonymous reviewer for his/her insights on approximation spaces; specifically, we owe this reviewer the indication to consider Choquet games and the convergence condition on approximation spaces that yields the equivalence with quasi-Polish spaces.

Preliminary Definitions and Results
We write N for the set of natural numbers, P(N) for the set of all subsets of N and P <ω (N) for the set of all finite subsets of N. Finite sequences of elements of a set X are denoted by (x 1 , x 2 , . . . , x n ). Concatenation of sequences u, v and element x are written simply as uv, ux. We use Greek letters to denote ordinals. We write ω for the first infinite ordinal, ω 1 for the first uncountable ordinal, and ω CK 1 for the least not computable ordinal (the Church-Kleene ordinal). For any two ordinals α, β, α ∼ β means that they have the same parity.

Borel and Hausdorff Hierarchies in General Topological Spaces
All the material of this subsection on the Borel and Hausdorff hierarchies in general topological spaces has first appeared in (Selivanov 2005). To make the presentation self contained, we reproduce here some of the proofs.
2.1.1. The Borel Hierarchy. In general topological spaces, an open set may possibly not be a countable union of closed sets, cf. Remark 2.13 infra. In order to get the expected inclusion Σ 0 1 (E) ⊆ Σ 0 2 (E), one has to distort the usual definition of Borel spaces given in metric spaces. This leads to define the hierarchy of Borel sets in a general setting as follows.
Definition 2.1 (Borel sets). Let E be a topological space.
where α ≥ 1 varies over countable ordinals, are inductively defined as follows: The class G δ (E) (respectively F σ (E)) is the family of countable intersections of open sets (respectively unions of closed sets). In general, it is a proper subclass of Π 0 2 (E) (respectively Σ 0 2 (E)). The following result follows from elementary set theory.
is closed under finite unions and intersections and continuous inverse images. The Σ 0 α (E) (respectively Π 0 α (E)) classes are closed under countable unions (respectively intersections).
As expected, the above definition is equivalent to the usual one for metric spaces. Also, in the general case, the distortion can be done solely for Σ 0 2 (E). Proposition 2.3.
1 Σ 0 2 (E) coincides with the family of countable unions of differences of sets in Σ 0 1 (E), i.e. sets of the form ⋃ n∈N U n ∖ V n where the U n , V n 's are open. Moreover, if B is a countable topological basis then one can take the U n 's in B.
. If E is metrizable then this also holds for α = 2.
Proof. 1. Observe that a Boolean combination of open sets is a finite union of differences of two open sets. For the last assertion, use that U n is a union of sets in B.
2. It suffices to prove that the difference X ∖Y of two sets in Σ 0 β (E), with β < α, is equal to a countable union of sets in Π 0 γ (E) with γ < α. In case β+1 < α then, as the intersection of a Σ 0 β (E) and a Π 0 β (E) set, X ∖ Y is Π 0 β+1 (E) and we are done. In case α = β + 1, since α ≥ 3, we have β ≥ 2 and X is of the form . Therefore, X ∖ Y is a countable union of sets in Π 0 β (E). Finally, in a metric space, the topological closure X of any set X is G δ since X = ⋂ n∈N {z ∃x ∈ X d(z, x) < 2 −n }. Going to complements, any open set is F σ . Then, any difference of two open sets hence also any Σ 0 2 (E) set is also F σ , i.e. a countable union of Π 0 1 (E) sets.  (Kuratowski 1966;Kechris 1995).
one can restrict to monotone increasing α-sequences.
Definition 2.7. For any 0 < β < ω 1 , the α-th level of the difference hierarchy over The difference hierarchy over Σ 0 1 (E) is simply called the difference hierarchy and denoted by D α (E).
1 Using item 2 of Proposition 2.6, we can graphically represent sets in the first levels of the difference hierarchy as in Figure 1. 2 This graphical representation makes it clear that D α (E) is not closed under finite union nor finite intersection: Proof. If the A γ 's, γ < α are in Σ 0 β (E) then so are the ⋃ δ<γ A δ 's. Thus, D α ((A γ ) γ<α ) is a countable union of differences of sets in Σ 0 β (E) hence is in Σ 0 β+1 (E). By Proposition 2.6, we see that Proposition 2.10. Let D, E be topological spaces and 2.1.3. The Borel and Hausdorff Hierarchies May Collapse. As it is well-known, the Borel and Hausdorff hierarchies are proper in uncountable Polish spaces: The same for the effective hierarchies (with α, β < ω CK 1 ) relative to some fixed enumeration of a countable basis of open sets. However, this is not true in general topological spaces. For instance, if the space is T 2 and countable then Σ 0 2 (E) = P(E). However, (de Brecht 2011) proves the non collapse of the Borel and Hausdorff difference hierarchies in uncountable quasi-Polish spaces, a class containing Polish spaces and ω-continuous domains.

Domains
Domain theory refers to the field initiated by Dana Scott in the late 1960s to specify denotational semantics for functional programming languages. The theory formalizes the ideas of approximation and convergence via some partially ordered sets called domains.
Example 2.11. Some examples of Scott topologies on partially ordered sets.
X ⊇ A}. The Scott topology on P(N) is has the O A 's, for A ∈ P <ω (N), as a topological basis. This is the topology of "positive information"; in contrast, the Cantor topology on 2 ω gives positive and negative information. 2 Scott topology on (P ∞ (N), ⊆) : consider the family P ∞ (N) of infinite subsets of N as a topological subspace of P(N). 3 Scott topology on the family (X ≤ω , ≤ pref ) of finite or infinite X-sequences.
We suppose X is any set with at least two elementss. For any s ∈ X <ω , let B s = {u ∈ X ≤ω u extends s}. The Scott topology on the space X ≤ω is that which admits the B s 's, s ∈ X <ω , as a topological basis.
4 Scott topology on the right extended real line ( The open sets of the topology on → R are → R and the semi-intervals ]x, +∞], for x ∈ R. 5 Extended real line (R, ≤) with duplicated rationals. LetR = R∪(Q×{+})∪{+∞} and ≤ be the following total order: +∞ is a maximum element, and for all x, y ∈ R and q ∈ Q, q <R (q, +); x <R y if and only if x < y; and x <R (q, +) <R y if and only if x < q < y. The Scott topology onR is that for which the [(q, +), +∞]'s, q ∈ Q, are a topological basis.
The following properties are straightforward.
Proposition 2.12. The Scott topologies of spaces in Examples 2.11 are not T 2 but are T 0 , i.e. they satisfy Kolmogorov's axiom: given two distinct points, one of them has a neighborhood which does not contain the other one (but this may not be symmetric).
1 As noticed in (Selivanov 2005), the finite levels of the Scott Borel hierarchy on P(N) do not coincide with the corresponding ones on the Cantor space 2 ω : Σ 0 n (P(N)) ⊊ Σ 0 n (2 ω ) ⊊ Σ 0 n+1 (P(N)) for all n ∈ N. The same is true with the effective Borel hierarchy (cf. § 5.3). For instance, X = P(N) ∖ {N}, defined by the formula ∃x (x ∉ X), is Σ 0 1 (2 ω ) and Σ 0 2 (P(N)) but neither Scott open nor Scott closed. However, the infinite levels of the Borel hierarchy on P(N) and 2 ω coincide. O is open and X is F σ and O, X are different from ∅, P(N). Then there exist non empty finite subsets X, 2.2.1. The Scott Topology on dcpo's. We briefly recall the main definitions and notions and refer the reader to classical papers and books, for instance (Abramsky & Jung 1994;Edalat 1997;Gierz & al. 2003).
1 A directed complete partial order (dcpo) is a partially ordered set (D, ⊑) such that every non empty directed subset S has a least upper bound (denoted by ⊔S). A dcpo is pointed if it has a least element . 2 The Scott topology on a dcpo is the topology that admits as closed sets all sets X satisfying conditions -X is a downset: x ∈ X ∧ y ⊑ x ⇒ y ∈ X.
-X is closed under suprema of directed subsets of D.
Then, O ⊆ D is open in the Scott topology if it satisfies the following conditions.
-O is an upset: -Every directed set with supremum in O has an element in O.

The Scott Topology on Domains.
Definition 2.17.
follows: let x, y ∈ D, x ≪ y if, for all directed subset S, y ⊑ ⊔S implies x ⊑ s for some s ∈ S. We say x approximates, or is way-below, y. 2 An element x ∈ D is compact (or finite) if x ≪ x. The set of compact elements is denoted by K(D). 3 ↟x = {y x ≪ y} and ↡ x = {y y ≪ x} Proposition 2.18. Let (D, ⊑) be a dcpo and x, x ′ , y, y ′ ∈ D.
Proposition 2.19. Let (D, ⊑) be a dcpo. The following conditions are equivalent.
D is a continuous domain if these conditions hold. Any set B satisfying condition (ii) is called a basis. D is an ω-continuous domain if (ii) holds for some countable set B. D is an algebraic (respectively ω-algebraic) domain if K(D) is a basis (and is countable).
Example 2.20. All spaces in Example 2.11 are dcpo's with the Scott topology. The spaces P(N), X ≤ω ,R are ω-algebraic domains. Their sets of compact elements are respectively P <ω (N), X <ω and Q×{+}. The way-below relation on any of these three spaces is the restriction of the partial order ≤ to K(D) × D. The space → R is an ω-continuous domain but is not algebraic: there is no compact element and its way-below relation is the strict order <. The space P ∞ (N) is not continuous: its way-below relation is empty.
Let us recall classical results in continuous domains.
Proposition 2.21. Let (D, ⊑) be a continuous domain with basis B.
the family of sets ↟z, where z varies in B, is a basis of the Scott topology on D.

Quasi-Polish Spaces
Quasi-Polish spaces, developed by de Brecht (2011), are a unifying framework of Polish spaces and ω-continuous domains. We recall here the definition and main results.
1 Giving up the symmetry axiom of metrics, a quasi-metric on a space E is defined as The topology associated to d is the one generated by the open balls.
is complete if every Cauchy sequence is convergent relative to the metricd such thatd(x, y) = max{d(x, y), d(y, x)}. 4 Topological spaces associated to complete quasi-metrics with a countable topological basis are called quasi-Polish.
Example 2.23. The Scott topology on P(N) is quasi-Polish for the quasi-metric such that d(X, Y ) = ∑ n∈X∖Y 2 −n .
Theorem 2.24. (Künzi 1983) A quasi-metric space (E, d) has a countable topological basis if and only if the metric space (E,d) is separable (i.e. has a countable dense subset).
The following theorem sums up some of the main results in (de Brecht 2011).
1 A space is quasi-Polish if and only if it is homeomorphic to some Π 0 2 subspace of P(N) endowed with the Scott topology.
2 Polish spaces and ω-continuous domains are quasi-Polish. 3 Every quasi-Polish space E satisfies the following properties: -(Baire property) The intersection of a sequence of dense open sets is a dense set.
Two examples of subspaces of P(N) illustrate the above theorem.
and is homeomorphic to the Cantor space 2 ω (and is therefore Polish).
It has a countable basis but is not Polish since it is T 0 and not T 2 . Although (P ∞ (N), ⊆) is a dcpo, it is not a continuous domain since its way-below relation is empty.

Topological Games
The Choquet topological games have been used to characterize Polish spaces (Choquet 1969) and quasi-Polish spaces (de Brecht 2011). We shall use them to characterize approximation spaces (cf. Definition §3.1 infra). Choquet games are a variant of Banach-Mazur games. The subtlety of this variant is best understood by confronting definitions and properties of both classes of games. Also, the interest of de Brecht's Theorem 2.36 and our Corollary 3.12 about convergent Markov/stationary strategies in the Choquet game is highlighted by the counterpart (and more powerful) results by Galvin  Definition 2.27. (Choquet 1969;Galvin & Telgárky 1986) Let X be a topological space.
1 In the Banach-Mazur game BM(X) two players, Empty and Nonempty, alternate turns for ω rounds. On round 0 (respectively i + 1), Empty moves first, choosing a non empty open subset U 0 ⊆ X (respectively U i+1 ⊆ V i ). Then, Nonempty responds A winning strategy for a player (in any of the above games) is a function that takes a partial play of the game ending with a move by its opponent and returns a move to play, such that the player wins any play of the game that follows the strategy. 4 A winning strategy for Nonempty is convergent if, when he follows it, the V i 's are a basis of neighborhoods of some x ∈ ⋂ i∈N V i .
Remark 2.29. Every winning strategy for Nonempty in the Choquet game Ch(X) yields one in the Banach-Mazur game BM(X).
The following theorem sums up some known results around these topological games.
Theorem 2.30. Let X be a topological space.
1 (Oxtoby 1957, cf. Kechris 1995) X has the Baire property (i.e. the intersection of countably many dense open sets is dense) if and only if player Empty has no winning strategy in the Banach-Mazur game BM(X). 2 (Choquet 1969, cf. Kechris 1995) X is Polish if and only if X has a countable basis, is T 1 and regular and player Nonempty has a winning strategy in the Choquet game Ch(X). 3 (de Brecht 2011, Theorem 51) X is quasi-Polish if and only if X has a countable basis, and player Nonempty has a convergent winning strategy in the Choquet game Ch(X).

2.4.2.
Markov and Stationary Strategies. The pioneer work of Schmidt (1966) and Choquet (1969) considered strategies of a very simple form. Then Galvin & Telgárky (1986) obtained deep results for other strategies.
Definition 2.31. A winning strategy is stationary (respectively Markov) if it depends only on the last move of the opponent (respectively and on the ordinal rank of the round).
Theorem 2.32. (Galvin & Telgárky 1986, Theorems 5 and 7) Let (S, ≤) be a non empty partially ordered set. Let R be a family of monotone (non strictly) decreasing sequences in S. In the game G(S, ≤, R), player I starts and plays elements a 0 , a 1 , . . . of S, player II plays elements b 0 , b 1 , . . . of S in such a way that a i+1 ≤ b i and b i ≤ a i for all i. Player II wins if and only if (a 0 , a 1 , . . .) ∈ R. Suppose R is such that for all monotone (non strictly) decreasing sequences (x i ) i∈N , (y i ) i∈N in S, 1 If player II has a winning strategy in G(S, ≤, R) then he has one that depends only on the last move of I and the last move of II. 2 If player II has a Markov winning strategy in G(S, ≤, R) then he has a stationary one.
Corollary 2.33. (Galvin & Telgárky 1986, Corollaries 9 and 14) 1 If player Nonempty has a winning (respectively and convergent) strategy in the Banach-Mazur game BM(X) then he has one which depends only on the last move of Empty and the last move of Nonempty (respectively and is convergent). 2 If player Nonempty has a Markov (respectively and convergent) winning strategy in BM(X) then he has a stationary (respectively and convergent) one. 3 (Debs 1984(Debs , 1985 There exists a T 2 (even completely regular) space X such that player Nonempty has no stationary winning strategy in BM(X) but has a winning strategy which depends only on the last two moves of Empty. We shall improve this last result (replacing Markov by stationary), cf. Corollary 3.13.

Approximation Spaces
We introduce another class of topological spaces: approximation spaces. They include all continuous domains, all Polish spaces and, in fact, all quasi-Polish spaces. The definition is based on an approximation relation which formalizes a containment relation between basic open sets. This containment relation ensures that inclusion-decreasing chains have a non empty intersection; however, this intersection may not be reduced to a singleton set. An example of an approximation relation is obtained by lifting to basic open sets the way-below relation in a dcpo. We borrowed the notation ≪ from this particular example. Theorem 3.12 proves that a subclass of second-countable approximation spaces coincides with the class of quasi-Polish spaces. This gives an "à la domain" characterization of quasi-Polish spaces. Whether the notion of approximation space captures a substantial part of the rich theory developed by de Brecht for quasi-Polish spaces is a question still to be investigated. In the next sections, we just show two pleasant properties: a Π 0 2 Baire property and Hausdorff's characterization of ∆ 0 2 . Definition 3.1. Let E be a topological space.
-An approximation relation for E is a binary relation ≪ on some topological basis B such that, for all U, V, T ∈ B, -Convergent approximation relations are obtained by strengthening condition (4) to each open set containing x also contains some U i ).
-An approximation relation is hereditary if, for every closed subset C of E, is an approximation relation for the subspace C. -A space E is an approximation space (respectively convergent approximation space, respectively hereditary approximation space) if it admits an approximation (respectively convergent approximation, respectively hereditary approximation) relation.
is an approximation space which is neither Polish nor a continuous domain. In P(N), inclusion is a convergent approximation relation since ⋃ i∈N A i ∈ ⋂ i∈N O Ai and the O Ai 's converge to ⋃ i∈N A i .
Approximation relations exist on all topological basis or on none.
Lemma 3.3. Let B and C be topological basis of a space E. If there exists an (respectively convergent; respectively hereditary) approximation relation on B then there exists one on C.
Proof. Let ≪ be an approximation relation on B. Consider the relation ⋘ on C such that, for any C, D ∈ C, Let us check that ⋘ satisfies conditions (1) to (4) of Definition 3.1. Conditions (1) and (2) are straightforward. We now look at Condition (3). (2) for ≪. Applying condition (4) for ≪, we see that ⋂ i∈N C i = ⋂ i∈N V i ≠ ∅ so that condition (4) holds for ⋘.
In case ≪ is convergent then the V i 's are a neighborhood basis of some x ∈ ⋂ i∈N V i . Hence so are the C i+1 's and ⋘ is convergent. Suppose ≪ is hereditary. To see that ⋘ is also hereditary, observe that, for any closed subset F of E, the relation ⋘ F is obtained from ≪ F via condition ( * ). Proof. Suppose (U i ) i∈N is ≪-increasing and C meets each U i . Since ≪ is a convergent approximation relation, the U i 's are a neighborhood basis of some x ∈ ⋂ i∈N U i . Since the U i 's meet C, x is adherent to C, hence it is in C. Also, the U i ∩ C's are a neighborhood basis of x in the subspace C.  (1)

Approximation Spaces versus quasi-Polish Spaces
Using the interpolation property, let c be such that b ≪ c ≪ x and set W =↟c. Then x ∈ W and c ∈↟b = U , so that U ≪ W . Finally, for condition (4 + ), suppose Let x be the supremum of the b j 's for j ≥ 1. Then x ∈ ⋂ j≥1 ↟b j = ⋂ i∈N U i which is therefore a non empty set. Also, the ↟b j = U j 's, j ≥ 1, are a basis of neighborhoods of x.
Using de Brecht's Theorem 2.25 for second-countable spaces, the above Proposition is partly subsumed by the next theorem.
Proof. By de Brecht's result stated in item 1 of Theorem 2.25, it suffices to show that any Π 0 2 subspace A of P(N) (with the Scott topology) is a convergent approximation space. In this proof we use Greek letters to denote finite sets. For α ∈ P <ω (N), let O α = {X α ⊆ X}. As a basis B of the subspace A, we consider those B α = O α ∩ A, α ∈ P <ω (N), which are non empty. Observe that if U ∈ B, there may be infinitely many α's such that and F n is closed in P(N). Since F n is a countable intersection of closed sets of the form P(N) ∖ O α , by merging this intersection with the global one, we can reduce to the case where F n = P(N) ∖ O αn with α n ∈ P <ω (N). Then, X ∈ A ⇔ ∀n (α n ⊆ X ∨ ∃γ ∈ I n γ ⊆ X) ⇔ ∀n (α n ⊆ X ⇒ ∃γ ∈ I n γ ⊆ X) .
Let us call clause n the clause α n ⊆ X ⇒ ∃γ ∈ I n γ ⊆ X. Thus, a set X ⊆ N is in A if and only if it satisfies clause n for all n. We introduce two notions: (i.e. the conclusion ∃γ ∈ I n γ ⊆ X of clause n is satisfied by all X ∈ U with the same witness γ).
Observe that if W ⊇ U then any W -clause is a U -clause and any W -solved W -clause is a U -solved U -clause. We denote by n U the least n such that clause n is a U -unsolved U -clause or +∞ if there is no such clause. We now define the relation ≪ on B : for U, V ∈ B, ii) or n U < +∞ and clause n U is V -solved (iii) or n U < +∞ and, for some m < n U , clause m is not a U -clause and is a V -solved V -clause.
. We now assume n U ≤ n W < +∞. Since n U is finite, U ≪ V cannot hold by condition (i). If U ≪ V holds by condition (iii) then the witnessing clause m is not a U -clause hence is not a W -clause, so that W ≪ V holds by condition (iii). Suppose now that U ≪ V holds by condition (ii). If n W = n U then W ≪ V also holds by condition (ii). Suppose n W > n U . If clause n U were a W -clause then it would be W -solved (by definition of n W and inequality n U < n W ) hence it would be a U -solved U -clause, contradicting the definition of n U . Thus, clause n U is not a W -clause and W ≪ V holds by condition (iii).
Condition (3). Let X be in U ∈ B. If n U = +∞ then it suffices to set V = U . Suppose now that n U < +∞. Since clause n U is a U -clause and X ∈ U , we have α n U ⊆ X so that X satisfies the premiss of clause n U . Then, X being in A, satisfies all clauses, in particular clause n U . So, there exists some γ ∈ I n U such that γ ⊆ X. Now, To finish the proof, we show that the set X = ⋃ i∈N δ i is in the family ⋂ i∈N U i = A∩⋂ i∈N O δi (which is therefore non empty). Clearly, X ∈ ⋂ i∈N O δi . To show that X ∈ A, i.e. X satisfies clause n for all n, we argue by contradiction. Suppose clause n is the first clause not satisfied by X. Then, X satisfies clause m for all m < n. This means that if α m ⊆ X then there is γ X,m ∈ I m such that γ X,m ⊆ X. Also, X satisfies the premiss of clause n (but not its conclusion), i.e. α n ⊆ X. Since α n and those α m 's, γ X,m 's included in X (for m < n) are finite, they are all included in δ i for some i. Thus, -for each m < n, clause m is a U i -clause if and only if it is a U i+1 -clause (if and only if α m ⊆ X), -for each m < n, if clause m is a U i -clause then it is U i -solved, -clause n is a U i -clause and is not U j -solved for any j ≥ i.
Then, clause n is the first U i -unsolved U i -clause and no clause m, m < n, can be a U i+1solved U i+1 -clause without being a U i -clause. As a consequence, the assumed property U i ≪ U i+1 necessarily comes from condition (ii) in the definition of ≪, i.e. clause n is U i+1 -solved. Since X ∈ U i+1 , clause n is satisfied by X. This is a contradiction. Condition (4 + ). To show that the U i 's are a basis of neighborhoods of X in A, it suffices to prove that, for all β ∈ P <ω (N) such that X ∈ O β , there exists i such that Example 3.7. Applied to the quasi-Polish space P ∞ (N) and its basis {O A ∩ P ∞ (N) A ∈ P <ω (N)} (cf. Examples 2.11, and 2.20), the previous proof gives an approximation relation which is not the containment relation (cf. Example 3.2). Clause n is ∃j ≥ n j ∈ X (i.e. A n is empty). It is an where θ is the usual homeomorphism (given by continued fractions) between R ∖ Q and the Baire space N ω and ≪ Baire is any approximation relation on the family of images by θ of bounded open real intervals (cf. Propositions 3.5 infra and 3.3 supra). It is easy to check that ≪ makes (R, τ ) an approximation space. However, Theorem 3.14 infra ensures that (R, τ ) is not a hereditary approximation space since Q is closed in (R, τ ) and, as a subspace, has the usual topology induced by R hence fails the Baire property.
Open Problem 3.9. Suppose a space is (T 0 or T 1 ) hereditary approximation space and has a countable topological basis. Is it convergent (hence quasi-Polish)?

Characterization as Spaces of Choquet Games
The next theorem asserts that approximation relations on a topological basis of X are essentially normalized strategies for player Nonempty in the Choquet game Ch(X).
Theorem 3.10. If X is a topological space with a well-orderable topological basis (in particular, if X has a countable basis) then X is an approximation (respectively convergent approximation) space if and only if player Nonempty has a stationary (respectively and convergent) winning strategy in the Choquet game Ch(X).
Proof. Suppose ≪ is an approximation relation on some topological basis B of X. Fix some well-ordering of B. Define a stationary strategy σ for player Nonempty in the Choquet game Ch(X) as follows. If U is a non empty set and x ∈ U then define σ(x, U ) = B where, letting C be least in B such that x ∈ C ⊆ U , applying condition (3) of Definition 3.1, B is least in B such that C ≪ B and x ∈ B. If is a play where Nonempty follows this strategy σ, there are open sets C 0 , C 1 , . . . in B such that

Applying condition (2), we see that
Thus, σ is a winning strategy for player Nonempty. In case ≪ is convergent, condition (4 + ) ensures that σ is convergent.
Conversely, suppose that τ is a winning stationary strategy for Nonempty in the Choquet game Ch(X). In particular, x ∈ τ (x, U ) ⊆ U for all open set U and x ∈ U . Fix some basis B of X and define a relation ≪ on this basis as follows: for B, C ∈ B B ≪ C ⇐⇒ ∃D ∈ B ∃x ∈ D (B ⊇ D ∧ x ∈ C ⊆ τ (x, D)) . (2) is obvious from the definition of ≪. As for condition (3), if x ∈ B then x ∈ τ (x, B) so that, for any C ∈ B such that x ∈ C ⊆ τ (x, B), we have B ≪ C. We now show condition (4). Suppose that B n ≪ B n+1 for all n. Let D n ∈ B, x n ∈ D n be such that B n ⊇ D n and x n ∈ B n+1 ⊆ τ (x n , D n ). Observe that the infinite sequence

Let us check the four conditions of Definition 3.1. Condition (1) is trivial since
is a legal play of the Choquet game Ch(X) in which Nonempty follows his winning strat- In case τ is a convergent stationary strategy, it is clear that ≪ is a convergent approximation relation.
Remark 3.11. The above proof fails if we consider the Banach-Mazur game in place of the Choquet game: we fail to obtain condition (3) for the relation ≪ associated to τ .

Quasi-Polish and Second Countable Convergent Approximation Spaces Coincide
Theorem 3.12. Quasi-Polish spaces coincide with T 0 convergent approximation spaces with a countable basis.
Proof. By Theorem 3.6, quasi-Polish spaces are convergent approximation spaces. If X is a convergent approximation space then, using Theorem 3.10, Nonempty has a con-vergent winning strategy in the Choquet game Ch(X). By de Brecht's result (cf. item 3 of Theorem 2.30), if X is also T 0 and has a countable basis then it is quasi-Polish.
Corollary 3.13. Let X be a T 0 space with a countable basis. The following conditions are equivalent: 1 Nonempty has a convergent wining strategy in the Choquet game Ch(X), 2 Nonempty has a stationary convergent wining strategy in the Choquet game Ch(X), 3 X is a quasi-Polish space.
3.5. The Π 0 2 Baire Property in Approximation Spaces The Baire property holds in Polish spaces and in compact T 2 (i.e. Hausdorff) spaces, and it is also true in quasi-Polish spaces (de Brecht 2011): the intersection of countably many dense open sets is dense. It trivially implies that the intersection of countably many dense G δ sets is dense. The next result is a formulation of the Baire property for spaces where the Π 0 2 and G δ classes do not coincide. As a corollary, we see that the classical Baire property on ω-continuous domains and also that on quasi-Polish spaces (cf. Theorem 2.25) can be strengthened from G δ to Π 0 2 .
Theorem 3.14. If X is an approximation space with a well-orderable topological basis (in particular, if X has a countable basis) then it satisfies the Baire property for Π 0 2 (E) sets: the intersection of countably many dense Π 0 2 (E) sets is dense.
Proof. Using Lemma 3.3, consider a well-orderable basis B and an approximation relation ≪ on B. We fix some well-order on B and we will speak freely of the least U in B satisfying a given property. Since Π 0 2 (E) sets are intersections of countably many sets in co-D 2 (E) (i.e. unions of an open and a closed sets), and any superset of a dense set is dense, it suffices to prove the Baire property for co-D 2 sets. Suppose X = ⋂ n∈N U n ∪ F n where, for each n, U n is open, F n is closed and U n ∪ F n is dense. We prove that X is dense, i.e. X meets O for each O ∈ B. Fix some π ∶ N → N such that π −1 (j) is infinite for each j ∈ N. (b) Suppose n ≥ 1, O n−1 is defined and let W ∈ B be least such that O n−1 ≪ W (as above there exists such a W ). If U π(n) contains some W * such that W ≪ W * then set O n = W * . Otherwise, set O n = W . The following Claim finishes the proof of the Theorem.
Claim. The set ⋂ n∈N O n is non empty and is included in holds for all n's and the non emptiness of ⋂ n∈N O n is ensured by condition (4) of Definition 3.1. Let x ∈ ⋂ n∈N O n . By clause (a) we have O ≪ O 0 . Thus, O 0 ⊆ O and x ∈ O. Let j ∈ N. Suppose x ∉ U j , we show that x ∈ F j . Since x ∉ U j we have O n ⊆ U j for all n ∈ N. Let n be such that π(n) = j, clause (b) ensures that O n = W (instead of W * ) and (*) U j contains no V ∈ B such that O n ≪ V . Since F j is closed, to show that x ∈ F j , it suffices to prove that x is adherent to F j . Consider T ∈ B such that x ∈ T , we have to prove that T meets F j . Let n be such that π(n) = j. Since U j ∪ F j is dense and T ∩ O n is non empty (it contains x), there exists x n ∈ (U j ∪ F j ) ∩ T ∩ O n . By way of contradiction, suppose x n is in U j . Then let S ∈ B be such that x n ∈ S ⊆ U j ∩ T ∩ O n . Condition (3) yields some V ∈ B such that x n ∈ V and S ≪ V . Using condition (2) and inclusion S ⊆ O n we have O n ≪ V . Now, we also have V ⊆ S ⊆ U j , contradicting (*). Thus, x n ∈ F j ; hence, T meets F j .
Remark 3.15. The fact that every continuous domain D satisfies the Π 0 2 (D) Baire property questions on a possible relation with the Lawson topology. Recall that the Lawson topology on a continuous domain is the refinement of the Scott topology such that the complement of the uppercone set ↑ x is open, for each x in D. The Lawson topology is T 2 and compact, so it satisfies the usual Baire property with G δ sets. Also, the Scott Π 0 2 class is included in the Lawson class G δ . However, the Π 0 2 Baire property for the Scott topology differs from the usual G δ Baire property for the Lawson topology because the notion of dense set is not the same in the two topologies.
3.6. Hausdorff 's Theorem and the Π 0 2 Baire Property Hausdorff-Kuratowski's theorem establishes that for Polish spaces the inclusion in Proposition 2.9 is an equality: ⋃ α<ω1 D α (Σ 0 β (E)) = ∆ 0 β+1 (E). One of the properties of Polish spaces used in the proof of this result is the classical Baire property. Matthew de Brecht (2011) has proved that Hausdorff-Kuratowski's theorem holds for quasi-Polish spaces. Our next theorem gives conditions of approximaton spaces to establish the case β = 1 i.e., Hausdorff's theorem ∆ 0 2 (E) = ⋃ α<ω1 D α (E). The theorem pinpoints some topological properties that suffice to prove this equality. These properties are true in second countable hereditary approximation spaces. A similar result was obtained in (Tang 1981) for the Scott domain P(N). Using a different proof Selivanov (2005) proved it for ω-algebraic domains.
Theorem 3.16. Let E be a topological space satisfying the following properties.
(i) There exists a countable basis of open sets. (ii) Every closed subspace F of E satisfies the Π 0 2 (E)-Baire property: the intersection of countably many Π 0 2 (E) subsets of F which are dense in F is also dense in F . Then, ⋃ α<ω1 D α (E) = ∆ 0 2 (E). Proof. The ⊆ inclusion is Proposition 2.9. For the ⊇ inclusion, we follow, mutatis mutandis, Hausdorff's original proof with residues and adjoins, as exposed in (Kechris 1995), Theorem 22.27 pages 176-177. For any subset A ⊆ E, we define by transfinite recursion a family (F α ) α<ω1 : Applying property (i), let (O n ) n∈N be a countable basis of open sets of E. The F α 's are a decreasing sequence of closed sets. If F ξ+1 = F ξ then F α = F ξ for all α ≥ ξ. If F α+1 is a strict subset of F α then there is some O n which meets F α but not F α+1 . Since there are countably many O n 's, this implies that there is some countable θ such that F θ = F α for all α ≥ θ. We shall consider the least even such θ. Claim Thus, arguing in the subspace F θ , the sets A ∩ F θ and (E ∖ A) ∩ F θ are Π 0 2 (F θ ) dense subsets of F θ . Since they are disjoint, this contradicts property (ii) in F θ .
Open Problem 3.18. What topological conditions ensure higher levels of Hausdorff-Kuratowski theorem ?

The Hausdorff Hierarchy in Continuous Domains
Selivanov made a fine analysis of the Hausdorff difference hierarchy in ω-algebraic domains and he proved Hausdorff's theorem for these spaces (Selivanov 2005). He also showed the non existence of ambiguous sets in the Hausdorff hierarchy, provided there is a least element in the ω-algebraic domain. As stated in (Selivanov 2008, Theorem 3.4), the methods in his paper of 2005 can be pushed from ω-algebraic to ω-continuous domains.
In this section we reconsider the question of the non existence of ambiguous sets in the Hausdorff hierarchy for continuous domains (possibly not ω-continuous). We prove that the hypothesis of a least element considered by Selivanov can be removed for successor levels of the Hausdorff hierarchy, but not for limit levels. Although this improvement is a modest addition to Selivanov's result (proofs being, mutatis mutandis, the same), it requires to use the machinery of well-founded alternating trees developed in (Selivanov 2005). The extension from ω-continuous domains to continuous domains led us to consider possibly non countable alternating trees. In fact, the countability of the domain basis is useful only to ensure that the tree is countable, hence the rank of an alternating tree is countable. But this hypothesis appears directly as an assumption on the ordinal α in Theorems 4.7 and 4.8.

Alternating Trees
First, we recall some simple notions about possibly uncountable trees.
1 A tree is any non empty set of finite sequences closed under prefix. The root of a tree is the empty sequence nil. If σ is in a tree T we let T σ be the tree {τ στ ∈ T }. 2 A tree T is well-founded if it has no infinite branch. The ranks of the elements in a well-founded tree T are defined inductively: rank T (σ) = sup{rank T (σn) + 1 σn ∈ T } (convention for leaves of T : sup ∅ = 0). The rank of T is that of its root. 3 An alternating tree is a map f ∶ T → {0, 1} such that T is a tree and f (τ ) ≠ f (σ) whenever σ is a son of τ (i.e. τ is a prefix of σ and the length of σ is the successor of that of τ ). We say f is ε-alternating if f (nil) = ε. 4 An embedding of an alternating tree g ∶ S → {0, 1} into an alternating tree f ∶ T → {0, 1} is a monotone increasing (with respect to the prefix ordering on finite sequences) injective map θ ∶ S → T such that g(σ) = f (θ(σ)). We write g ≤ f .
The next basic result is taken from (Selivanov 2005), Lemma 3.6 page 48.
Proof. We reproduce Selivanov's proof. Argue by induction on α. If α is finite then take a branch of length α and remove an appropriate tail and/or the root. If α is limit then, for some x, T (x) (cf. Definition 4.1) has rank γ such that β < γ < α. Use the induction hypothesis with . Finally, suppose α = λ + m + 1 with λ limit and m ∈ N. If β < λ + m then let x such that T (x) has rank λ + m and use the induction hypothesis. Suppose now β = λ + m. Let s with length m + 1 such that T s has rank λ. Let η be the cofinality of λ and let (λ ξ ) ξ<η be strictly increasing with supremum λ and x ξ be such that T sx ξ has rank λ ξ . Let g ξ,δ ≤ f sx ξ+1 for δ ∈ {0, 1} be δ-alternating with rank λ ξ . Set g ε (0 p ) = f (s↾ p) for p ≤ m and g ε (0 m ξσ) = g ξ,δ (σ) where δ is chosen so as to get alternation from 0 m to 0 m ξ.

Alternating Trees and the Hausdorff Hierarchy
The following notion plays the role of intervals [p, x] in (Selivanov 2005).  If (x i ) i∈I is a directed system with supremum in A then x i ∈ A for all i large enough. In particular, if D is a continuous domain with basis B ⊆ D and x ∈ A then there exists b ∈ B such that b ≪ x and b, x] ⊆ A.
Proof. Let A = ⋃ n∈N U n ∖ V n where U n , V n are open. Let x = ⊔ i x i . Since x ∈ U n and U n is Scott open, the x i 's are in U n for i large enough. Since x ∉ V n and V n is an upset, no x i is in V n . Thus, the x i 's are in U n ∖ V n hence in A for i large enough.
To keep the presentation self-contained, we prove the extensions to continuous domains of Theorems 3.10 and 3.14 in (Selivanov 2005). Proofs are almost the same: compact elements are replaced by elements of some fixed basis B and the countability of the basis (which ensures the countability of the rank of alternating B-trees, cf. Definition 4.5) is replaced by the assumed countability of the considered ordinal α.
Definition 4.5. Let (D, ⊑) be a dcpo and B ⊆ D. If A is any subset of D we let χ A ∶ A → {0, 1} be the characteristic function of A (which takes value 1 on A). Theorem 4.7. Let (D, ⊑) be a dcpo, B ⊆ D, A ∈ ∆ 0 2 (D) and 0 < α < ω 1 . 1 If A ∈ D α (D) then there is no ≤-increasing (A, 1)-alternating B-tree with rank α. 2 If D is a continuous domain with basis B, the following conditions are equivalent.
Proof. 1. We argue by induction on α. Let A = D α ((A β ) β<α ) where the A β 's are a monotone increasing α-sequence of open sets. By way of contradiction, suppose there exists an increasing (A, 1)-alternating B-tree f ∶ T → B with rank α. Since f (nil) ∈ A we have f (nil) ∈ A β ∖ ⋃ γ<β A γ for some β < α, β ∼ α. Since f (nil) ≤ f (σ) for all σ ∈ T and A β is open (hence, an upset), we see that the range of f is included in Then f is an (A − , 0)-alternating B-tree. Now, f has rank α and Lemma 4.2 implies that there exists g ≤ f which is an (A − , 1)-alternating B-tree with rank β. Since A − is in D β , the inductive hypothesis is contradicted.
2. Since i ⇒ ii is item 1 and ii ⇒ iii is trivial, it remains to prove iii ⇒ i. For each b ∈ B, let S b be the family of finite sequences (b, b 1 , . . . , b k ) of elements of B satisfying the following conditions: Fix some bijection θ between B and an initial segment of N. Applying θ, transform S b into an A-alternating B-tree f b ∶ T b → B such that θ(b 1 ), . . . , θ(b k ))) = b k . Since A is assumed to be ∆ 0 2 (D), Proposition 4.6 ensures that f b is well-founded. Suppose there is no (A, 1)-alternating B-tree

Ambiguous Sets in the Hausdorff Hierarchy
We now come to the question of whether there are ambiguous sets in the Hausdorff hierarchy. Item 1 of the next Theorem was obtained by Selivanov (2005) for ω-algebraic domains.
Proof. 1. Inclusion right to left comes from Proposition 2.6. Inclusion left to right is proved by induction on α. Case α = 0 is trivial since both members are empty.
Suppose now α is a limit ordinal and (α n ) n∈N is increasing with α as supremum. Towards a contradiction, suppose A ∉ ⋃ β<α D β (D) ∪ co-D β (D). Then, for every n and ε = 0, 1, there is a monotone increasing (A, ε)-alternating B-tree f n,ε ∶ T n,ε → B with rank α n . Let τ ∈ {0, 1} be as above. Set S = {nσ σ ∈ T n,ε } and g ∶ S → B be such that g(nil) = and g(nσ) = f n,ε (σ). Then g is a monotone increasing (A, τ )-alternating B-tree with rank α. As above, this gives a contradiction. 2 where the A β , E β 's are α + 1 increasing sequences of open sets. Set D + = D ∪{ α } and extend the order of D by setting Observe that the A * β 's and E β 's are open in D + . Thus, A + is ambiguous at level α + 1 in D + . Though α is not a least element in D + , it is smaller than A α hence smaller than all elements labeling an (A, 1)-alternating B-tree with rank α. Arguing as in item 1, we see that A + must have level at most α in D + . If D + ∖ A + = D ∖ A has level α in D + then D ∖ A is obtained via open sets not containing α hence D ∖ A has level α in D. Suppose now that A + has level α in D + . Then So, A has level β in D. Finally, observe that the argument breaks down if α = 0.
3. In 2 ≤ω , the set 02 ≤ω is in D 1 (D) ∩ co-D 1 (D) but not in D 0 (D) ∩ co-D 0 (D). Let α be a countable limit ordinal. Let (a β ) β<α be a strictly decreasing α-sequence of reals with no lower bound and which is continuous: a λ = inf δ<λ a δ for all limit λ < α. In → R (cf. Example 2.11), consider the set Thus, A is ambiguous at level α. It is easy to check that A is not in a lesser level.

Effective Topological Spaces
The first step to deal with the effective Borel hierarchy is the definition of effective topological space. We follow Weihrauch's book (2000), Definition 3.2.1, page 63.
Definition 5.1. An effective topological space is a pair (E, (O n ) n∈N ) where E is a topological space admitting a countable basis and (O n ) n∈N is an enumeration (not necessarily injective) of some topological basis of E.
Remark 5.2. For the notion of computable topological space, one also requires that the equivalence relation {(m, n) O m = O n } be computably enumerable. For instance, this is the case if n ↦ O n is injective, which is usually true. We shall not need this notion.
Definition 5.3. An effective approximation space is a triple (E, (O n ) n∈N , ≪) such that (O n ) n∈N enumerates a topological basis B, the relation {(i, j) O i ≪ O j } is computably enumerable and ≪ is an approximation relation on B (cf. Definition 3.1).

Effective ω-Continuous Domains
Definition 5.4. An ω-continuous domain is effective if it admits a basis B = {b n n ∈ N} such that {(i, j) b j ≪ b i } is computably enumerable.
(vi) α is the order type of some linear order on N which is computable in real time and logarithmic space (Dehornoy 1986;Grigorieff 1990).
Moreover, in (iv-vi), one can suppose that, for each n ∈ N, the set of elements with rank exactly n and that with ranks in {ωα + n α < ω CK 1 } are computable. Remark 5.10. The last assertion in Proposition 5.9 is a simple trick in (Ershov 1968). If (N, R) has type α then the lexicographic product of (N, R) and (N, <) has type ωα and the (computable) set N × {n} consists of all elements of rank ≡ n mod ω.
The definition of the effective version of Borel hierarchy for countably based spaces, and the basic properties appeared previously in (Selivanov 2008).
Definition 5.11 (Effective Borel hierarchy). Let (E, (O n ) n∈N ) be an effective topological space and α an ordinal such that 1 ] Π ) for some well-founded tree T with rank at most α such that both T and the rank order relation on if there exists a computable sequence of well-founded trees (T n ) n∈N with ranks at most α such that X n = [ [ T n ] ] Σ . Idem with uniformly Π 0 α (E). 3 G δ and F σ are the classes of intersections of uniformly Σ 0 1 (E) sequences (respectively unions of uniformly Π 0 1 (E) sequences). Remark 5.12.
1 If ⪯ is an order on N isomorphic to the ordinal α then the set of sequences (n 1 , . . . , n k ) such that n 1 ⪰ n 2 . . . ⪰ n k is a well-founded tree with rank α and computable rank order relation (i.e. it satisfies the above condition (a)). 2 The requirement that the rank order relation on T is computable (in condition 1) allows to get the usual definition of Σ 0 α (E) for finite α's. For instance, a subset X of E is Σ 0 2 (E) (respectively Σ 0 3 (E)) if and only if there exists computably enumerable sets Proposition 5.13. All assertions in Proposition 2.2 hold for the effective Borel classes with the proviso that 1 ≤ α < ω CK 1 and countable unions (respectively intersections) are relative to uniformly Σ 0 α (E) (respectively Π 0 α (E)) sequences of sets.

Hausdorff Codes and the Effective Hausdorff Hierarchy
The definition of the effective difference hierarchy for countably based spaces and their basic properties appeared previously in (Selivanov 2008).
Definition 5.14. Let (E, (O n ) n∈N ) be an effective topological space.
1 A Hausdorff α-code for a set X in D α (Σ 0 β (E)) is a triple (⪯, P, (T n ) n∈N ) such that -⪯ is a well-order of type α on N or on a finite initial segment of N, -P = {n ∈ dom(⪯) ϕ(n) ∼ α} where ϕ is the unique isomorphism from (dom(⪯), ⪯) onto the ordinal α, -(T n ) n∈N is a family of well-founded trees with ranks at most β, 2 The effective Hausdorff classes D α (Σ 0 β (E)) are defined as follows: for 1 ≤ α < ω CK 1 , a set X is in D α (Σ 0 β (E)) if and only if it admits an α-code (⪯, P, (T n ) n∈N ) such that ⪯ and P are computable and the T n 's and the rank relations on the T n 's are uniformly computable, (i.e. {(n, s) s ∈ T n } and {(n, s, t) s, t ∈ T n , rank Tn (s) ≤ rank Tn (t)} are computable).
The effective class D α (Σ 0 1 (E)) is also denoted by D α (E). Contrary to what was the case with the other results, the proof of Theorem 3.16 does not effectivize. The reason is that although the topological closure of a ∆ 0 2 set is closed, hence Π 0 1 , it may not be Π 0 1 . For instance, let X be any countable ∆ 0 2 (N) subset of N. In the real line, X is ∆ 0 2 (R) and closed hence Π 0 1 (R), but X is not Π 0 1 (R). Idem in the Baire space with the set {f ∈ N ω f (0) ∈ X}. This difficulty is mentioned in (Selivanov 2005), page 53, lines 6-7, with open sets: in the proof of his Theorem 3.10 page 50, open sets A β 's are defined using some ∆ 0 2 set A: this is a stumbling block to get Σ 0 1 sets. For the Baire space N ω , Selivanov (2003) uses a proof different from Hausdorff's original one. We adapt it to get the following weak effective version of Hausdorff's theorem.
It is clear that, as a family of finite sequences, T is a tree and is computable. Claim 1. The tree T is well-founded (i.e. it has no infinite branch).
Proof of Claim 1. Else consider an infinite branch (m ℓ , t ℓ ) ℓ∈N . Condition (3) of the Definition 5.11 and condition (b) of the definition of T imply that the set ⋂ ℓ∈N O m ℓ contains at least one element x. Observe that condition (c) implies that F ε (m ℓ , t) ≥ ⌊ℓ 2⌋. Using ( †) for even and odd n's, we see that x ∈ ⋂ q<⌊ℓ 2⌋ ⋃ i∈I ε q O i for all ℓ and for ε = 0, 1. Thus, x is in both A and E ∖ A, a contradiction. Let us say that a pair (m, t) ∈ X has type ε if F ε (m, t) > F 1−ε (m, t).
Claim 2. Suppose x ∈ A and (m, t) ∈ X has type 0 and x ∈ O m . Then there exists (p, u) ∈ X such that (p, u) has type 1 and x ∈ O p and (p, m) ∈ R, m < p and t ≤ u. Switching types 0 and 1, the same is true with x ∉ A.
Proof of Claim 2. We treat the sole case x ∈ A, the other one being trivial modification. Since x ∉ E ∖ A, condition ( * ) insures that there exists n such that x ∉ ⋃ i∈I 0 n O i . Since x ∈ A, using again ( * ), we see that x ∈ ⋂ r≤n ⋃ i∈I 1 r O i . Choose i 1 , . . . , i n , p such that x ∈ O ir and (i r , p) ∈ R for all r ≤ n. Let u > t, n, i 1 , . . . , i n . Then F 0 (p, u) < n whereas F 1 (p, u) ≥ n hence (p, u) has type 1 and satisfies Claim 2. We extendà la Kleene-Brouwer the computable well-founded reverse prefix partial ordering on T into a computable total well-ordering ⪯ on T : let σ, τ ∈ T , -If the sequences σ and τ are prefix comparable, then we ⪯-compare them relative to the reverse prefix partial order. -If the sequences σ and τ are not prefix comparable, then we compare the first elements on which they differ relative to the usual order on N.
In other words, S is obtained from T by replacing each element of T by a chain of ω + 2 copies of that element. We also denote by ⪯ the well-ordering on S. The following Claim is straightforward.