Olivier Finkel
email: finkel@logique.jussieu.fr

Dominique Lecomte
email: dominique.lecomte@upmc.fr

Classical and Effective Descriptive Complexities of ω-Powers

Keywords: ω-power, Borel class, complete, effective descriptive set theory, hyperarithmetical hierarchy. 2000 Mathematics Subject Classification. Primary: 03E15, 03B70, Secondary: 54H05, 68Q15, 68Q45, 68R15

We prove that, for each countable ordinal ξ ≥ 1, there exist some Σ 0 ξ -complete ω-powers, and some Π 0 ξ -complete ω-powers, extending previous works on the topological complexity of ω-powers [Fin01, Fin03, Fin04, Lec01, Lec05, DF06]. We prove effective versions of these results; in particular, for each recursive ordinal ξ < ω CK

1

there exist some recursive sets A ⊆ 2 <ω such that A ∞ ∈ Π 0 ξ \ Σ 0 ξ (respectively, A ∞ ∈ Σ 0 ξ \Π 0 ξ ), where Π 0 ξ and Σ 0 ξ denote classes of the hyperarithmetical hierarchy. To do this, we prove effective versions of a result by Kuratowski, describing a Π 0 ξ set as the range of a closed subset of the Baire space ω ω by a continuous bijection. This leads us to prove closure properties for the pointclasses Σ 0 ξ in arbitrary recursively presented Polish spaces. We apply our existence results to get better computations of the topological complexity of some sets of dictionaries considered in [START_REF] Lecomte | Omega-Powers and Descriptive Set Theory[END_REF].

Introduction.

We consider the finite alphabet Σ = {0, . . . , Σ -1}, where Σ ≥ 2 is an integer, and a language over this alphabet, i.e., a subset A of the set Σ <ω of finite words with letters in Σ. Notice that a language of finite words will be also sometimes called a dictionary, as in [START_REF] Lecomte | Omega-Powers and Descriptive Set Theory[END_REF]. The set of infinite words over the alphabet Σ, i.e., of sequences of length ω of letters of Σ, is denoted Σ ω . Definition 1.1 The ω-power associated with A is the set A ∞ of the infinite sentences constructible with A by concatenation. So we have A ∞ := { a 0 a 1 . . . ∈ Σ ω | ∀i ∈ ω a i ∈ A }.

Notice that we denote here A ∞ the ω-power associated with A, as in [START_REF] Lecomte | Omega-Powers and Descriptive Set Theory[END_REF], while it is often denoted A ω in Theoretical Computer Science papers, as in [START_REF] Staiger | ω-Languages[END_REF][START_REF] Finkel | Topological Properties of Omega Context Free Languages[END_REF][START_REF] Finkel | Borel Hierarchy and Omega Context Free Languages[END_REF][START_REF] Finkel | There Exist some ω-Powers of Any Borel Rank[END_REF]. Here we reserved the notation A ω to denote the cartesian product of countably many copies of A since this will be often used in this paper.

In the theory of formal languages of infinite words, accepted by various kinds of automata, the ω-powers appear very naturally in the characterization of the class REG ω of ω-regular languages (respectively, of the class CF ω of context free ω-languages) as the ω-Kleene closure of the family REG of regular finitary languages (respectively, of the family CF of context free finitary languages), see [START_REF] Thomas | Automata on Infinite Objects[END_REF][START_REF] Lescow | Logical Specifications of Infinite Computations[END_REF][START_REF] Perrin | Infinite Words, Automata, Semigroups, Logic and Games[END_REF][START_REF] Staiger | Hierarchies of Recursive ω-Languages[END_REF][START_REF] Staiger | ω-Languages[END_REF][START_REF] Finkel | Borel Ranks and Wadge Degrees of Omega Context Free Languages[END_REF][START_REF] Kechris | 1 1 Borel Sets[END_REF] for some references on this topic.

Since the set Σ ω of infinite words over a finite alphabet Σ can be equipped with the usual Cantor topology, the question of the topological complexity of ω-powers of finitary languages naturally arises and has been posted by Niwinski [Niw90], Simonnet [START_REF] Simonnet | Automates et Théorie Descriptive[END_REF], and Staiger [START_REF] Staiger | ω-Languages[END_REF].

What are the possible levels of topological complexity for the ω-powers?

As the concatenation map, from A ω onto A ∞ , which associates a 0 a 1 . . . to (a i ) i∈ω , is continuous, an ω-power is always an analytic set.

It has been recently proved, that for each integer n ≥ 1, there exist some ω-powers of (context-free) languages which are Π 0 n -complete Borel sets, [START_REF] Finkel | Topological Properties of Omega Context Free Languages[END_REF], and that there exists a (context-free) language L such that L ω is analytic but not Borel, [START_REF] Finkel | Borel Hierarchy and Omega Context Free Languages[END_REF]. Amazingly, the language L is very simple to describe and it is accepted by a simple 1-counter automaton. Notice that Louveau has proved independently that analytic-complete ω-powers exist, but the existence was proved in a non effective way. We refer the reader to [START_REF] Hopcroft | Formal Languages and their Relation to Automata[END_REF][START_REF] Autebert | Context Free Languages and Pushdown Automata[END_REF] for basic notions about context-free languages.

The first author proved in [START_REF] Finkel | An omega-Power of a Finitary Language Which is a Borel Set of Infinite Rank[END_REF] that there exists a finitary language V such that V ω is a Borel set of infinite rank. However the only known fact on their complexity is that there is a (context-free) language W such that W ω is Borel above ∆ 0 ω , [START_REF] Duparc | An ω-Power of a Context-Free Language Which Is Borel Above ∆ 0 ω[END_REF]. In particular, it was still unknown which could be the possible infinite Borel ranks of ω-powers.

The basic notions of descriptive set theory used in this paper will be recalled in the next section. We now state our results which extend the previous ones.

Theorem 1.2 (a) Let 3 ≤ ξ < ω 1 , and Γ = Γ be a Wadge class closed under finite unions satisfying the inclusions ∆ 0 ξ (Γ) ⊆ Γ = ∆ 0 3 -PU(Γ) ⊆ Π 0 ξ+1 . Then there is A ⊆ 2 <ω such that A ∞ is Γ-complete. (b) Let 1 ≤ ξ < ω 1 . Then there is A ⊆ 2 <ω such that A ∞ is Σ 0 ξ -complete. (c) Let 1 ≤ ξ < ω 1 . Then there is A ⊆ 2 <ω such that A ∞ is Π 0 ξ -complete. (d) Let 1 ≤ ξ < ω 1 . Then there is A ⊆ 2 <ω such that A ∞ is Ď2 (Σ 0 ξ )-complete. (e) Let 3 ≤ ξ < ω 1 and ω ≤ η < ω 1 be an indecomposable ordinal. Then there is A ⊆ 2 <ω such that A ∞ is Ďη (Σ 0 ξ )-complete.

So we get a complete knowledge of the Borel classes Γ for which there is A ⊆ 2 <ω such that A ∞ is Γcomplete. Indeed, the only class ∆ 0 ξ admitting a complete set is ∆ 0 1 . And A := {s ∈ 2 <ω | 0 ≺ s or 1 2 ≺ s} implies that A ∞ = 2 ω \N 10 is a ∆ 0 1 -complete set.

In this context coming from theoretical computer science, it is natural to wonder whether these examples are effective. We answer positively. The reader should see [START_REF] Moschovakis | Descriptive Set Theory[END_REF] for basic notions of effective descriptive set theory. It is known that B ⊆ 2 ω is Σ 0 ξ -complete if and only if B ∈ Σ 0 ξ \Π 0 ξ (see 22.10 in [START_REF] Kechris | Classical Descriptive Set Theory[END_REF]). The effective version of Theorem 1.2 is the following:

Theorem 1.3 (1) Let 1 ≤ ξ < ω CK 1 . (a) There is A ⊆ 2 <ω such that A ∞ ∈ Σ 0 ξ \Π 0 ξ . (b) There is A ⊆ 2 <ω such that A ∞ ∈ Π 0
ξ \Σ 0 ξ . Moreover, A can be coded by a ∆ 0 1 subset of ω.

(2) Similarly, let β ∈ 2 ω and 1 ≤ ξ < ω β 1 . (a) There is A ⊆ 2 <ω such that A ∞ ∈ Σ 0 ξ (β)\Π 0 ξ . (b) There is A ⊆ 2 <ω such that A ∞ ∈ Π 0 ξ (β)\Σ 0 ξ . Moreover, A can be coded by a ∆ 0 1 (β) subset of ω.

To prove Theorem 1.2, we use a theorem of Kuratowski which is a level by level version of a theorem of Lusin and Souslin stating that every Borel set B ⊆ 2 ω is the image of a closed subset of the Baire space ω ω by a continuous bijection. This theorem of Lusin and Souslin had already been used by Arnold in [START_REF] Arnold | Topological Characterizations of Infinite Behaviours of Transition Systems, Automata, Languages and Programming[END_REF] to prove that every Borel subset of Σ ω , for a finite alphabet Σ, is accepted by a non-ambiguous finitely branching transition system with Büchi acceptance condition and our first idea was to code the behaviour of such a transition system. This way, in the general case, we can manage to construct an ω-power of the same complexity as B. We now state Kuratowski's Theorem [START_REF] Kuratowski | Topology[END_REF] (see Corollary 33.II.1):

Theorem 1.4 Let ξ ≥ 1 be a countable ordinal, X a zero-dimensional Polish space, and B ∈ Π 0 ξ+1 (X). Then there is C ∈ Π 0 1 (ω ω ) and a continuous bijection f :

C → B such that f -1 is Σ 0 ξ -measurable (i.e., f [U ] is Σ 0 ξ (B)
for each open subset U of C).

To prove Theorem 1.3, we first prove an effective version of Theorem 1.4. It has the following consequence.

In [START_REF] Lecomte | Omega-Powers and Descriptive Set Theory[END_REF], the following question is asked. What is the topological complexity of the set of dictionaries whose associated ω-power is of a given level of complexity? More specifically, let 1 ≤ ξ < ω 1 . The following Σ 1 2 (2 2 <ω )\D 2 (Σ 0 1 ) sets are introduced:

Σ ξ := {A ⊆ 2 <ω | A ∞ ∈ Σ 0 ξ }, Π ξ := {A ⊆ 2 <ω | A ∞ ∈ Π 0 ξ }, ∆ := {A ⊆ 2 <ω | A ∞ ∈ ∆ 1 1 } = {A ⊆ 2 <ω | A ∞ ∈ Π 1 1 }.
The proof of Theorem 1.3 gives some more informations about the complexity of these sets. We will prove, using a result by J. Saint Raymond, that Σ ξ and Π ξ are Π 1 1 -hard if ξ ≥ 3, which is a much better approximation of their complexity than the one in [START_REF] Lecomte | Omega-Powers and Descriptive Set Theory[END_REF]. The proof of this fact has the following consequence. Theorem 1.2 shows that the ω-powers are quite general objects. On the other hand, we will prove another result showing that they are not arbitrary.

Notation.

Let Γ be a class having a universal set U 2 ω Γ ⊆ (2 ω ) 2 , and Γ ′ another class. We set

U(Γ, Γ ′ ) := {α ∈ 2 ω | (U 2 ω Γ ) α ∈ Γ ′ }.
Let X, Y be zero-dimensional Polish spaces and A ⊆ X, B ⊆ Y . We will use the following notation to denote the Wadge quasi-order:

(X, A) ≤ W (Y, B) ⇔ ∃f : X → Y continuous with A = f -1 (B). We write (X, A) < W (Y, B) if (X, A) ≤ W (Y, B) and (Y, B) ≤ W (X, A).
The consequence we mentioned is the following. If we choose suitable universal sets, then the following inequalities hold:

U(Π 0 ξ , Σ 0 ξ ) ≤ W Σ ξ < W U(Σ 1 1 , Σ 0 ξ ) U(Σ 0 ξ , Π 0 ξ ) ≤ W Π ξ < W U(Σ 1 1 , Π 0 ξ ) U(Σ 1 1 , Π 1 1 ) ≤ W ∆ < W U(Σ 1 1 , ∆ 1 1 ) = U(Σ 1 1 , Π 1 1
). This means that the ω-powers are analytic sets that do not behave like arbitrary analytic sets. This also means that there is a strong difference between the Borel levels on one side, and the level of analytic sets on the other side. Actually, our method to prove Theorem 1.3 is a method that works for the Borel levels, and it cannot be extended to the level of analytic sets, even if Theorem 1.3 can be extended to the level of analytic sets (see [START_REF] Finkel | Borel Hierarchy and Omega Context Free Languages[END_REF]). Note that we will prove that

U(Σ 1 1 , ∆ 1 1 ) is Π 1 2 -complete.
This paper is organized as follows:

• In section 2 we prove Theorem 1.2.

• In section 3 we recall a few basic facts of effective descriptive set theory, and fix some notation. Then we prove the results of effective descriptive set theory that we need for the sequel. This is where the closure properties for the pointclasses Σ 0 ξ are proved.

• In section 4 we prove Theorem 1.5.

• In section 5 we prove Theorem 1.3.

• In section 6 we study the complexity of some sets of dictionaries.

2 Proof of Theorem 1.2.

Basic facts and notation.

In descriptive set theory, we study the topological complexity of definable subsets of Polish spaces, i.e., of separable and completely metrizable topological spaces.

• The notation for the Borel classes in metrizable spaces is as follows: Σ 0 1 is the class of open sets, and if ξ ≥ 1 is a countable ordinal, then Π 0 ξ is the class of complements of Σ 0 ξ sets, Σ 0 ξ is the class of countable unions of sets in 1≤η<ξ Π 0 η , and

∆ 0 ξ is the class Σ 0 ξ ∩ Π 0 ξ . The class of Borel sets is ∆ 1 1 := 1≤ξ<ω 1 Σ 0 ξ = 1≤ξ<ω 1 Π 0 ξ .
• The class of analytic sets is the class Σ 1 1 of subsets of Polish spaces that are continuous images of Polish spaces. One can prove that if X is a Polish space, then A ⊆ X is analytic if and only if A is the projection on X of a closed subset of X × ω ω (see 14.3 in [START_REF] Kechris | Classical Descriptive Set Theory[END_REF]). Then we can define the projective classes in Polish spaces as follows; if n ≥ 1 is an integer, then Π 1 n is the class of complements of Σ 1 n sets, Σ 1 n+1 (X) is the class of projections on X of sets in Π 1 n (X ×ω ω ), and

∆ 1 n is the class Σ 1 n ∩ Π 1 n .
• If Γ is a class of sets in Polish spaces and X is a Polish space, then a set

U X Γ ∈ Γ(2 ω ×X) is universal for Γ(X) if Γ(X) = {(U X Γ ) α | α ∈ 2 ω } (where (U X Γ ) α := {x ∈ X | (α, x) ∈ U X Γ }).
For example, there are universal sets for Σ 0 ξ (X), Π 0 ξ (X), Σ 1 1 (X), Π 1 1 (X) for any Polish space X (see 22.3 and 26.1 in [START_REF] Kechris | Classical Descriptive Set Theory[END_REF]).

• Recall that a Polish space is zero-dimensional if it has a basis consisting of ∆ 0 1 sets. Typically, let K be a countable set. If K is equipped with the discrete topology and s ∈ K <ω , then

N s := {α ∈ K ω | s ≺ α} is a basic ∆ 0 1 set of K ω (s ≺ α means that s is a beginning of α). The length of γ ∈ K ≤ω is denoted |γ|. If γ ∈ K ≤ω and k ∈ ω, then γ ↾ k is the beginning of length k of γ. If s ≺ α = α(0)α(1)..., then α-s is the sequence α(|s|)α(|s|+1)... • If Γ is a class of sets in zero-dimensional Polish spaces, closed under continuous preimages, then a subset A of X is Γ-hard if for each A ′ ∈ Γ(X ′ ) there is a continuous map f : X ′ → X with A ′ = f -1 (A). If A ∈ Γ(X) is Γ-hard, then we say that A is Γ-complete. We say that Γ is a Wadge class if there is a Γ-complete set. We denote Γ := {¬A | A ∈ Γ}. If Γ = Γ ⊆ ∆ 1 1 is a Wadge class, then A is Γ-complete if and only if A ∈ Γ\ Γ. • If Γ is a Wadge class, then ∆ 0 ξ (Γ) ⊆ Γ means that E ∈ Γ(X) if E ∈ ∆ 0 ξ (A) and A ∈ Γ(X).
• If I is a set and Γ is a class or a set, then (x i ) i∈I ⊆ Γ means that x i ∈ Γ for each i ∈ I. [START_REF] Louveau | Les Propriétés de Réduction et de Norme pour les Classes de Boréliens[END_REF]).

• We set ∆ 0 ξ -PU(Γ) := { n∈ω A n ∩ P n | (A n ) n∈ω ⊆ Γ and (P n ) n∈ω ⊆ ∆ 0 ξ partition} if 1 ≤ ξ < ω 1 . One can prove that if ∆ 0 1 ⊆ Γ = Γ ⊆ ∆ 1 1 is a Wadge class, then there is a bigger 1 ≤ ξ < ω 1 (the level of Γ) such that Γ = ∆ 0 ξ -PU(Γ) (see
If η < ω 1 and (A θ ) θ<η is an increasing sequence of subsets of some space X, then we set

D η [(A θ ) θ<η ] := {x ∈ X | ∃θ < η x ∈ A θ \ θ ′ <θ
A θ ′ and the parity of θ is opposite to that of η}.

If moreover 1 ≤ ξ < ω 1 , then we set D η (Σ 0 ξ ) := {D η [(A θ ) θ<η ] | (A θ ) θ<η ⊆ Σ 0 ξ }. One can prove that D η (Σ 0 ξ ) has level ξ if η ≥ 1 (see [LStR88]
).

• We say that ω ≤ η < ω 1 is indecomposable if η cannot be represented as η 1 + η 2 with η 1 , η 2 < η. It is known that the indecomposable ordinals are the ω θ with 1 ≤ θ < ω 1 (see IV.2.16 in [START_REF] Levy | Basic Set Theory[END_REF]).

Proof of Theorem 1.2.

• We have already said that the existence of the continuous bijection f : C → B given by Lusin and Souslin's Theorem had already been used by Arnold in [START_REF] Arnold | Topological Characterizations of Infinite Behaviours of Transition Systems, Automata, Languages and Programming[END_REF] to prove that every Borel subset of Σ ω , for a finite alphabet Σ, is accepted by a non-ambiguous finitely branching transition system with Büchi acceptance condition. We now recall the definition of these transition systems.

A B üchi transition system is a tuple T = (Σ, Q, δ, q 0 , Q f ), where Σ is a finite input alphabet, Q is a countable set of states, δ ⊆ Q × Σ × Q is the transition relation, q 0 ∈ Q is the initial state, and Q f ⊆ Q is the set of final states. A run of T over an infinite word σ ∈ Σ ω is an infinite sequence of states (t i ) i≥0 , such that t 0 = q 0 , and for each i ≥ 0, (t i , σ(i), t i+1 ) ∈ δ. The run is said to be accepting iff there are infinitely many integers i such that t i is in Q f . The transition system is said to be non-ambiguous if each infinite word σ ∈ Σ ω has at most one accepting run by T .

The transition system is said to be f initely branching if for each state q ∈ Q and each a ∈ Σ, there are only finitely many states q ′ such that (q, a, q ′ ) ∈ δ.

Our first idea was to code the behaviour of such a transition system. In fact this can be done on a part of infinite words of a special compact set K 0,0 . However we shall have also to consider more general sets K N,j and then we shall need the hypothesis of the Σ 0 ξ -measurability of the function f , which is given by Kuratowski's Theorem.

• We now come to the proof of Theorem 1.2.

(a) We may assume that ∆ 0 1 ⊆ Γ, otherwise Γ = {∅} since ∆ 0 ξ (Γ) ⊆ Γ, in which case A := ∅ is suitable. This implies that ∆ 0 ξ ⊆ Γ since ∆ 0 ξ (Γ) ⊆ Γ.

• Let B ∈ Γ(2 ω )\ Γ, and

P ∞ := {α ∈ 2 ω | ∀m ∈ ω ∃n ≥ m α(n) = 1}
, which is homeomorphic to ω ω (we associate 0 β(0) 10 β(1) 1... to β ∈ ω ω ). As B ∈ Π 0 ξ+1 , Theorem 1.4 gives C ∈ Π 0 1 (P ∞ ) and f . By Proposition 11 in [START_REF] Lecomte | Omega-Powers and Descriptive Set Theory[END_REF], it is enough to find A ⊆ 4 <ω . The dictionary A will be made of two pieces: we will have A = µ ∪ π. The set π will code f , and π ∞ will look like B on some nice compact sets K N,j . Outside a countable family of compact sets, we will hide f , so that A ∞ will be the simple set µ ∞ .

• We set Q := {(s, t) ∈ 2 <ω × 2 <ω | |s| = |t|}. We enumerate Q as follows. We start with q 0 := (∅, ∅). Then we put the sequences of length 1 of elements of 2× 2, in the lexicographical ordering: q 1 := (0, 0), q 2 := (0, 1), q 3 := (1, 0), q 4 := (1, 1). Then we put the 16 sequences of length 2: q 5 := (0 2 , 0 2 ), q 6 := (0 2 , 01), . . . And so on. We will sometimes use the coordinates of q N := (q 0 N , q 1 N ). We put M j := Σ i<j 4 i+1 . Note that the sequence (M j ) j∈ω is strictly increasing, and that q M j is the last sequence of length j of elements of 2×2.

• If l ∈ ω and (a i ) i<l ∈ (ω <ω ) l , then ⌢ i<l a i is the concatenation a 0 . . . a l-1 . Similarly, ⌢ i∈ω a i is the concatenation a 0 a 1 . . .

• Now we define the "nice compact sets". We will sometimes view 2 as an alphabet, and sometimes view it as a letter. To make this distinction clear, we will use the boldface notation 2 for the letter, and the lightface notation 2 otherwise.

We will have the same distinction with 3 instead of 2, so that 2 = {0, 1}, 3 = {0, 1, 2}, 4 = {0, 1, 2, 3}. Let N, j be non-negative integers with N ≤ M j . We set

K N,j := { γ = 2 N ⌢ [ ⌢ i∈ω m i 2 M j+i+1 3 2 M j+i+1 ] ∈ 4 ω | ∀i ∈ ω m i ∈ 2 }.
As the map ϕ N,j : K N,j → 2 ω defined by ϕ N,j (γ) := (m i ) i∈ω is a homeomorphism, K N,j is compact.

• Now we will define the sets that "look like B".

-We define a function c : B×ω → Q by c(α, l) := [f -1 (α), α] ↾ l. Note that Q is countable, so that we equip it with the discrete topology. In these conditions, we prove that c is Σ 0 ξ -measurable.

For any q ∈ Q, it holds that c -1 ({q}) = {(α, l) ∈ B × ω | f -1 (α) ↾ l = q 0 and α ↾ l = q 1 }. But α ↾ l = q 1 means that "l = |q 1 | and α belongs to the basic open set N q 1 ". In the same fashion, f -1 (α) ↾ l = q 0 means that "l = |q 0 | and f -1 (α) belongs to the basic open set N q 0 ", or equivalently that

"l = |q 0 | and α = f (f -1 (α)) belongs to f [C ∩ N q 0 ]". As f [C ∩ N q 0 ] is a Σ 0 ξ subset of B, c -1 ({q}) is a Σ 0 ξ subset of B ×ω and c is Σ 0 ξ -measurable.
-Let N be an integer. We put

E N := { α ∈ 2 ω | q 1 N α ∈ B and c(q 1 N α, |q 1 N |) = q N }. Note that E 0 = { α ∈ 2 ω | α ∈ B and c(α, 0) = ∅} = B. Let us prove that E N ∈ Γ(2 ω ) for each integer N . As c is Σ 0 ξ -measurable and {q N } ∈ ∆ 0 1 (Q), we get c -1 ({q N }) ∈ ∆ 0 ξ (B × ω). Note that the map S : {α ∈ 2 ω | q 1 N α ∈ B} → B×ω defined by S(α) := (q 1 N α, |q 1 N |) is continuous, so that E N = S -1 [c -1 ({q N })] is in ∆ 0 ξ ({α ∈ 2 ω | q 1 N α ∈ B}). As B ∈ Γ(2 ω ) and the map α → q 1 N α is continuous, {α ∈ 2 ω | q 1 N α ∈ B} is in Γ(2 ω ). Thus E N ∈ Γ(2 ω ) since∆ 0 ξ (Γ) ⊆ Γ.
Now we define the transition system obtained from f .

-If m ∈ 2 and n, p ∈ ω, then we write n m → p if q 0 n ≺ q 0 p and q 1 p = q 1 n m.

-As f is continuous on C, the graph Gr(f

) of f is a closed subset of C×2 ω . As C is Π 0 1 (P ∞ ), Gr(f ) is also a closed subset of P ∞ ×2 ω . So there is a closed subset F of 2 ω ×2 ω such that Gr(f ) = F ∩(P ∞ ×2 ω ).
We identify 2 ω ×2 ω with (2×2) ω , i.e., we view (β, α) as [β(0), α(0)], [β(1), α(1)], ... By Proposition 2.4 in [START_REF] Kechris | Classical Descriptive Set Theory[END_REF], there is R ⊆ (2×2) <ω , closed under initial segments, such that

F = {(β, α) ∈ 2 ω ×2 ω | ∀k ∈ ω (β, α) ↾ k ∈ R}.
Notice that R is a tree whose infinite branches form the set F . In particular, we get

(β, α) ∈ Gr(f ) ⇔ β ∈ P ∞ and ∀k ∈ ω (β, α) ↾ k ∈ R. -We set Q f := {(t, s) ∈ R | t = ∅ and t(|t|-1) = 1}. Notice that Q f is simply the set of pairs (t, s) ∈ R such that the last letter of t is a 1.
We have in fact already defined the transition system T obtained from f . This transition system has a countably infinite set Q of states and a set Q f of accepting states. The initial state is q 0 := (∅, ∅). The input alphabet is 2 = {0, 1} and the transition relation

δ ⊆ Q × 2 × Q is given by: if m ∈ 2 and n, p ∈ ω then (q n , m, q p ) ∈ δ iff n m → p.
Recall that a run (t i ) i≥0 of T is said to be Büchi accepting if there are infinitely many integers i such that t i is in Q f . Then the set of ω-words over the alphabet 2 which are accepted by the transition system T from the initial state q 0 with Büchi acceptance condition is exactly the Borel set B.

• Now we define the finitary language π. We set

π :=                                      s ∈ 4 <ω | ∃j, l ∈ ω ∃(m i ) i≤l ∈ 2 l+1 ∃(n i ) i≤l , (p i ) i≤l , (r i ) i≤l ∈ ω l+1 n 0 ≤ M j and ∀i ≤ l n i m i → p i and p i +r i = M j+i+1 and ∀i < l p i = n i+1 and q p l ∈ Q f and s = ⌢ i≤l 2 n i m i 2 p i 2 r i 3 2 r i                                      . • Let us prove that ϕ N,j [π ∞ ∩ K N,j ] = E N if N ≤ M j .
Let γ ∈ π ∞ ∩ K N,j , and α := ϕ N,j (γ). We can write

γ = ⌢ k∈ω [ ⌢ i≤l k 2 n k i m k i 2 p k i 2 r k i 3 2 r k i ].
As this decomposition of γ is in π, we have

n k i m k i → p k i if i ≤ l k , p k i = n k i+1 if i < l k , and q p k l k ∈ Q f , for each k ∈ ω. Moreover, p k l k = n k+1 0 , for each k ∈ ω, since γ ∈ K N,j implies that p k l k +r k l k = r k l k +n k+1 0 = M j+1+m for some integer m. So we get N α(0) → p 0 0 α(1) → . . . α(l 0 ) → p 0 l 0 α(l 0 +1) → p 1 0 α(l 0 +2) → . . . α(l 0 +l 1 +1) → p 1 l 1 . . .
In particular we have

q 0 N ≺ q 0 p 0 0 ≺ . . . ≺ q 0 p 0 l 0 ≺ q 0 p 1 0 ≺ . . . ≺ q 0 p 1 l 1 . . . because n m → p implies that q 0 n ≺ q 0 p . Note that |q 1 p k l k | = |q 1 N |+Σ j≤k (l j +1), so that the sequence (|q 0 p k l k |) k∈ω is strictly increasing since |q 0 n | = |q 1 n | for each integer n. This implies the existence of β ∈ P ∞ such that q 0 p k l k ≺ β for each k ∈ ω. Note that β ∈ P ∞ because, for each integer k, q p k l k ∈ Q f . Note also that (β, q 1 N α) ↾ k ∈ R for infinitely many k's. As R is closed under initial segments, (β, q 1 N α) ↾ k ∈ R for every k ∈ ω, so that q 1 N α = f (β) ∈ B. Moreover, c(q 1 N α, |q 1 N |) = (β ↾ |q 1 N |, q 1 N ) = (q 0 N , q 1 N ) = q N , and α ∈ E N .
Conversely, let α ∈ E N . We have to see that γ

:= ϕ -1 N,j (α) ∈ π ∞ . As γ ∈ K N,j , we are allowed to write γ = 2 N ⌢ [ ⌢ i∈ω α(i) 2 M j+i+1 3 M j+i+1 ]. We set β := f -1 (q 1 N α). There is a sequence of integers (k l ) l∈ω such that q k l = (β, q 1 N α) ↾ l. Note that N α(0) → k |q 1 N |+1 α(1) → k |q 1 N |+2 . . . As N ≤ M j we get k |q 1 N |+i+1 ≤ M j+i+1 . So we can define n 0 := N , p 0 := k |q 1 N |+1 , r 0 := M j+1 -p 0 , n 1 := p 0 . Similarly, we can define p 1 := k |q 1 N |+2 , r 1 := M j+2 -p 1 .
We go on like this until we find some q p i in Q f . This clearly defines a word in π. And we can go on like this, so that γ ∈ π ∞ . Thus π ∞ ∩ K N,j is in Γ(K N,j ) ⊆ Γ(4 ω ). Notice that we proved, among other things, the equality

ϕ 0,0 [π ∞ ∩ K 0,0 ] = B. In particular, π ∞ ∩ K 0,0 is Γ-complete in K 0,0 .
Notice that π ∞ codes on K 0,0 the behaviour of the transition system accepting B. In a similar way, π ∞ codes on K N,j the behaviour of the same transition system, but starting this time from the state q N instead of the initial state q 0 . But some ω-words in π ∞ are not in K 0,0 and not even in any K N,j and we do not know what exactly the complexity of this set of ω-words is. However we remark that all the words in π have the same form

2 N ⌢ [ ⌢ i≤l m i 2 P i 3 2 R i ].
• We are ready to define µ. The idea is that an infinite sequence containing a word in µ cannot be in the union of the K N,j 's.

We set

µ 0 :=                    s ∈ 4 <ω | ∃l ∈ ω ∃(m i ) i≤l+1 ∈ 2 l+2 ∃N ∈ ω ∃(P i ) i≤l+1 , (R i ) i≤l+1 ∈ ω l+2 ∀i ≤ l+1 ∃j ∈ ω P i = M j and P l = R l and s = 2 N ⌢ [ ⌢ i≤l+1 m i 2 P i 3 2 R i ]                    , µ 1 :=                    s ∈ 4 <ω | ∃l ∈ ω ∃(m i ) i≤l+1 ∈ 2 l+2 ∃N ∈ ω ∃(P i ) i≤l+1 , (R i ) i≤l+1 ∈ ω l+2 ∀i ≤ l+1 ∃j ∈ ω P i = M j and ∃j ∈ ω (P l = M j and P l+1 = M j+1 ) and s = 2 N ⌢ [ ⌢ i≤l+1 m i 2 P i 3 2 R i ]                    , µ := µ 0 ∪ µ 1 .
All the words in A have the same form

2 N ⌢ [ ⌢ i≤l m i 2 P i 3 2 R i ].
Note that any finite concatenation of words of this form still has this form. Moreover, such a concatenation is in µ i if its last word is in µ i .

• Now we prove that µ ∞ is "simple". The previous remarks show that

µ ∞ = { γ ∈ 4 ω | ∃i ∈ 2 ∀j ∈ ω ∃k, n ∈ ω ∃t ∈ (µ i ) n+1 n ≥ j and γ ↾ k = ⌢ l≤n t(l) }.
This shows that µ ∞ ∈ Π 0 2 (4 ω ).

• Note again that all words in A have the same form

2 N ⌢ [ ⌢ i≤l m i 2 P i 3 2 R i ].
We set

P := {2 N ⌢ [ ⌢ i∈ω m i 2 P i 3 2 R i ] ∈ 4 ω | (m i ) i∈ω ∈ 2 ω , N ∈ ω, (P i ) i∈ω , (R i ) i∈ω ∈ ω ω and ∀i ∈ ω ∃j ∈ ω P i = M j }.
We define a map F :

P \µ ∞ → ({∅} ∪ µ)×ω 2 as follows. Let γ := 2 N ⌢ [ ⌢ i∈ω m i 2 P i 3 2 R i ] ∈ P \µ ∞ , and j 0 ∈ ω with P 0 = M j 0 . If γ ∈ K N,j 0 -1 , then we put F (γ) := (∅, N, j 0 ). If γ / ∈ K N,j 0 -1
, then there is an integer l maximal for which P l = R l or there is j ∈ ω with P l = M j and P l+1 = M j+1 . Let j 1 ∈ ω with P l+2 = M j 1 . We put

F (γ) := (2 N ⌢ [ ⌢ i≤l m i 2 P i 3 2 R i ] ⌢ m l+1 2 P l+1 3, R l+1 , j 1 ). • Fix γ ∈ A ∞ . If γ / ∈ µ ∞ , then γ ∈ P \µ ∞ , F (γ) := (t, S, j) is defined. Note that t 2 S ≺ γ, and that j > 0. Moreover, γ-t 2 S ∈ K 0,j-1 . Note also that S ≤ M j-1 if t = ∅, and that t 2 S γ(|t|+S) 2 M j 3 / ∈ µ. Moreover, there is an integer N ≤ min(M j-1 , S) (N = S if t = ∅) such that γ -t 2 S-N ∈ π ∞ ∩ K N,j-1 , since the last word in µ in the decomposition of γ (if it exists) ends before t 2 S .
• In the sequel we will say that (t, S, j)

∈ ({∅} ∪ µ) × ω 2 is suitable if S ≤ M j if t = ∅, t(|t|-1) = 3 if t ∈ µ, and t 2 S m 2 M j+1 3 / ∈ µ if m ∈ 2.
We set, for (t, S, j) suitable,

P t,S,j := γ ∈ 4 ω | t 2 S ≺ γ and γ -t 2 S ∈ K 0,j .
Note that P t,S,j is a compact subset of P \µ ∞ , and that F (γ) = (t, S, j+1) if γ ∈ P t,S,j . This shows that the P t,S,j 's, for (t, S, j) suitable, are pairwise disjoint. Note also that µ ∞ is disjoint from (t,S,j) suitable P t,S,j .

• We set, for (t, S, j) suitable and N ≤ min(M j , S)

(N = S if t = ∅), A t,S,j,N := γ ∈ P t,S,j | γ -t 2 S-N ∈ π ∞ ∩ K N,j . Note that A t,S,j,N ∈ Γ(4 ω ) since N ≤ M j .
• The previous discussion shows that

A ∞ = µ ∞ ∪ (t,S,j) suitable N ≤ min(M j , S) N = S if t = ∅ A t,S,j,N .
As Γ is closed under finite unions, the set

A t,S,j := N ≤ min(M j , S) N = S if t = ∅ A t,S,j,N is in Γ(4 ω ).
• We can write

A ∞ = µ ∞ \   (t,S,j) suitable P t,S,j   ∪ (t,S,j) suitable
A t,S,j ∩ P t,S,j .

Note that the P t,S,j 's and (t,S,j) suitable P t,S,j are ∆ 0 3 subsets of 4 ω since (P t,S,j

) (t,S,j) suitable is a countable family of closed sets. Moreover, µ ∞ is a Π 0 2 ⊆ Γ subset of 4 ω . This implies that A ∞ is in ∆ 0 3 -PU(Γ) = Γ. Moreover, the set A ∞ ∩ P ∅,0,0 = π ∞ ∩ P ∅,0,0 = π ∞ ∩ K 0,0 is Γ-complete. This shows that A ∞ is Γ-hard (any reduction with values in K 0,0 is also a reduction with values in 4 ω ). Thus A ∞ is Γ-complete.
We can now end the proof of Theorem 1.2.

(b) If ξ = 1, then we can take A := {s ∈ 2 <ω | 0 ≺ s or ∃k ∈ ω 10 k 1 ≺ s} and A ∞ = 2 ω \ {10 ∞ } is Σ 0 1 -complete.
• If ξ = 2, then we will see in Theorem 2 the existence of A ⊆ 2 <ω such that A ∞ is Σ 0 2 -complete.

• So we may assume that ξ ≥ 3, and we just have to apply (a) to

Γ := Σ 0 ξ . (c) If ξ = 1, then we can take A := {0} and A ∞ = {0 ∞ } is Π 0 1 -complete. • If ξ = 2, then we can take A := {0 k 1 | k ∈ ω} and A ∞ = P ∞ is Π 0 2 -complete.
• So we may assume that ξ ≥ 3, and we just have to apply (a) to

Γ := Π 0 ξ . (d) First notice that D 2 (Σ 0 ξ ) = {B \C | B, C ∈ Σ 0 ξ }. Indeed, ⊆ is clear, and ⊇ comes from the fact that B \ C = (B ∪ C) \ C. This implies that Ď2 (Σ 0 ξ ) = {B ∪ C | B ∈ Σ 0 ξ and C ∈ Π 0 ξ }. A consequence of this is the closure of Ď2 (Σ 0 ξ ) under finite unions. Another consequence is ∆ 0 ξ [ Ď2 (Σ 0 ξ )] ⊆ Ď2 (Σ 0 ξ ). Indeed, if D := B ∪ C ∈ Ď2 (Σ 0 ξ )(X) and E ∈ ∆ 0 ξ (D), then choose Σ ∈ Σ 0 ξ (X) and Π ∈ Π 0 ξ (X) such that E = Σ ∩ D = Π ∩ D. We get E = (Σ ∩ B) ∪ (Π ∩ C) ∈ Ď2 (Σ 0 ξ )(X). • If ξ = 1, then we can take A := {s ∈ 2 <ω | 0 ≺ s or ∃q ∈ ω (101) q 1 3 ≺ s or s = 10 2 } and A ∞ = p∈ω [N (10 2 ) p 0 ∪ ( q∈ω N (10 2 ) p (101) q 1 3 )] ∪ {(10 2 ) ∞ } is Ď2 (Σ 0 1 )-complete (see §7 in [Lec05]
, and also example 9 in [START_REF] Staiger | On ω-Power Languages[END_REF]).

• If ξ = 2, then we can take A := {s ∈ 2 <ω | 1 2 ≺ s or s = 0} and A ∞ = {0 ∞ } ∪ p∈ω N 0 p 1 2 ∩ [(2 ω \P ∞ ) ∪ {α ∈ 2 ω | ∀m ∈ ω ∃n ≥ m α(n) = α(n+1) = 1}] is Ď2 (Σ 0 2 )-complete (see §7 in [Lec05]
).

• So we may assume that ξ ≥ 3, and we just have to apply (a) to Γ := Ď2 (Σ 0 ξ ).

(e) Let X be a zero-dimensional Polish space, and E, F ∈ D η (Σ 0 ξ )(X). By Lemma 4.2 in [vEn],

E × F is D η (Σ 0 ξ ). Now let C ⊆ 2 ω be D η (Σ 0 ξ )-complete, h : 2 ω ×2 ω → 2 ω continuous with C ×C = h -1 (C), and f, g : X → 2 ω continuous with E = f -1 (C) and F = g -1 (C). It is clear that the map c : X → 2 ω defined by c(x) := h[f (x), g(x)] satisfies E ∩ F = c -1 (C). This shows that D η (Σ 0 ξ ) is closed under finite intersections. Thus Ďη (Σ 0 ξ ) is closed under finite unions. Note also that if D ∈ D η (Σ 0 ξ ) and B ∈ Σ 0 ξ , then B ∪ D ∈ D η (Σ 0 ξ ). Indeed, let (A θ ) θ<η ⊆ Σ 0 ξ be an increasing sequence with D = D[(A θ ) θ<η ]. We set B 0 := ∅, B 1 := B, and B 2+θ := A θ ∪ B if θ < η. Then (B θ ) θ<η ⊆ Σ 0 ξ is increasing, and D[(B θ ) θ<η ] = B ∪ 2ρ+1<η (A 2ρ+1 ∪ B)\(A 2ρ ∪ B) = B ∪ D since η is even. This shows that if D ∈ Ďη (Σ 0 ξ ) and B ∈ Π 0 ξ , then B ∩ D ∈ Ďη (Σ 0 ξ ). This implies the inclusion ∆ 0 ξ [ Ďη (Σ 0 ξ )] ⊆ Ďη (Σ 0 ξ ).
Now we can apply (a) to Γ := Ďη (Σ 0 ξ ).

As we already said, a Borel class remains for which we did not provide a complete ω-power yet: the class Σ 0 2 . Note that it is easy to see that the classical example of a Σ 0 2 -complete set, the set 2 ω \P ∞ , is not an ω-power. However we are going to prove the following result.

Theorem 2 There is a recursive (and even context-free) language A ⊆ 2 <ω such that A ∞ ∈ Σ 0 2 \Π 0 2 .

Proof. By Proposition 11 in [START_REF] Lecomte | Omega-Powers and Descriptive Set Theory[END_REF], it is enough to find A ⊆ 3 <ω . We set, for j < 3 and s ∈ 3 <ω ,

n j (s) := Card{i < |s| | s(i) = j}, T := {α ∈ 3 ≤ω | ∀l < 1+|α| n 2 (α ↾ l) ≤ n 1 (α ↾ l)}.
So T is the tree of sequences for which any initial segment contains more coordinates equal to 1 than coordinates equal to 2.

• We inductively define, for s ∈ T ∩ 3 <ω , s ←֓ ∈ 2 <ω as follows:

s ←֓ :=            ∅ if s = ∅, t ←֓ ε if s = tε and ε < 2,
t ←֓ , except that its last 1 is replaced with 0, if s = t2.

• We will extend this definition to infinite sequences. To do this, we introduce a notion of limit. Fix

(s n ) n∈ω ⊆ 2 <ω . We define lim n→∞ s n ∈ 2 ≤ω as follows. For each t ∈ 2 <ω , t ≺ lim n→∞ s n ⇔ ∃n 0 ∈ ω ∀n ≥ n 0 t ≺ s n . • If α ∈ T ∩ 3 ω , then we set α ←֓ := lim n→∞ (α ↾ n) ←֓ .
We define e : T ∩ 3 ω → 2 ω by e(α) := α ←֓ . Note that

T ∩ 3 ω ∈ Π 0 1 (3 ω )
, and e is a Σ 0 2 -recursive partial function on T ∩ 3 ω , since for t ∈ 2 <ω we have

t ≺ e(α) ⇔ ∃n 0 ∈ ω ∀n ≥ n 0 t ≺ (α ↾ n) ←֓ . • We set E := {s ∈ T ∩ 3 <ω | n 2 (s) = n 1 (s) and s = ∅ and 1 ≺ [s ↾ (|s|-1)] ←֓ }. Note that ∅ = s ←֓ ≺ 0 ∞ , and that s(|s|-1) = 2 changes s(0) = [s ↾ (|s|-1)] ←֓ (0) = 1 into 0 if s ∈ E.
• If S ⊆ 3 <ω , then S * := { ⌢ i<l s i ∈ 3 <ω | l ∈ ω and (s i ) i<l ⊆ S}. We put

A := {0} ∪ E ∪ { ⌢ j≤k (c j 1) ∈ 3 <ω | [∀j ≤ k c j ∈ ({0} ∪ E) * ] and [k > 0 or (k = 0 and c 0 = ∅)]}.
Note that A is recursive.

• In the proof of Theorem 1.2.(b) we met the set {s ∈ 2 <ω | 0 ≺ s or ∃k ∈ ω 10 k 1 ≺ s}. We will call this set B, and

B ∞ = 2 ω \{10 ∞ } is Σ 0 1 -complete (and even Σ 0 1 ). Let us show that A ∞ = e -1 (B ∞ ).
-By induction on |t|, we get (st

) ←֓ = s ←֓ t ←֓ if s, t ∈ T ∩3 <ω . Let us show that (sβ) ←֓ = s ←֓ β ←֓ if moreover β ∈ T ∩ 3 ω . Assume that t ≺ (sβ) ←֓ . Then there is m 0 ≥ |s| such that, for m ≥ m 0 , t ≺ [(sβ) ↾ m] ←֓ = [sβ ↾ (m-|s|)] ←֓ = s ←֓ [β ↾ (m-|s|)] ←֓ . This implies that t ≺ s ←֓ β ←֓ if |t| < |s ←֓ |. If |t| ≥ |s ←֓ |, then there is m 1 ∈ ω such that, for m ≥ m 1 , β ←֓ ↾ (|t|-|s ←֓ |) ≺ [β ↾ (m-|s|)] ←֓ .
Here again, we get t ≺ s ←֓ β ←֓ . Thus (sβ) ←֓ = s ←֓ β ←֓ .

Let (s i ) i∈ω ⊆ T ∩ 3 <ω . Then ⌢ i∈ω s i ∈ T , and ( ⌢ i∈ω s i ) ←֓ = ⌢ i∈ω s ←֓ i , by the previous facts.

-Let (a i ) i∈ω ∈ (A\{∅}) ω and α

:= ⌢ i∈ω a i . As A ⊆ T , e(α) = ( ⌢ i∈ω a i ) ←֓ = ⌢ i∈ω a ←֓ i . If a 0 ∈ {0} ∪ E, then ∅ = a ←֓ 0 ≺ 0 ∞ , thus e(α) ∈ N 0 ⊆ 2 ω \{10 ∞ } = B ∞ . If a 0 / ∈ {0} ∪ E, then a 0 = ⌢ j≤k (c j 1), thus a ←֓ 0 = ⌢ j≤k (c ←֓ j 1).
If c 0 = ∅, then e(α) ∈ B ∞ as before.

If c 0 = ∅, then k > 0, so that e(α) = 10 ∞ since e(α) has at least two coordinates equal to 1.

We proved that A ∞ ⊆ e -1 (B ∞ ).

-Assume that e(α) ∈ B ∞ . We have to find (a i ) i∈ω ⊆ A\{∅} with α = ⌢ i∈ω a i . We split into cases:

1. e(α) = 0 ∞ . 1.1. α(0) = 0.
In this case α-0 ∈ T and e(α-0) = 0 ∞ . Moreover, 0 ∈ A. We put a 0 := 0.

1.2. α(0) = 1.
In this case there is a coordinate j 0 of α equal to 2 ensuring that α(0) is replaced with a 0 in e(α). We put a 0 := α ↾ (j 0 +1), so that a 0 ∈ E ⊆ A, α-a 0 ∈ T and e(α-a 0 ) = 0 ∞ . Now the iteration of the cases 1.1 and 1.2 shows that α ∈ A ∞ .

2. e(α) = 0 k+1 10 ∞ for some k ∈ ω.

As in case 1, there is c 0 ∈ ({0} ∪ E) * such that c 0 ≺ α, c ←֓ 0 = 0 k+1 , α-c 0 ∈ T and e(α-c 0 ) = 10 ∞ . Note that α(|c 0 |) = 1, α-(c 0 1) ∈ T and e[α-(c 0 1)] = 0 ∞ . We put a 0 := c 0 1, and argue as in case 1.

3. e(α) = ( ⌢ j≤l+1 0 k j 1)0 ∞ for some l ∈ ω.

The previous cases show the existence of (c j ) j≤l+1 ⊆ ({0} ∪ E) * such that a 0 := ⌢ j≤l+1 c j 1 ≺ α, α-a 0 ∈ T and e(α-a 0 ) = 0 ∞ . We are done since a 0 ∈ A.

4. e(α) = ⌢ j∈ω 0 k j 1.

An iteration of the discussion of case 3 shows that we can take a i of the form ⌢ j≤l+1 c j 1.

• The previous discussion shows that

A ∞ = e -1 (B ∞ ). As e is Σ 0 2 -recursive, e -1 (B ∞ ) ∈ Σ 0 2 (3 ω ).
It remains to see that e -1 (B ∞ ) / ∈ Π 0 2 . We argue by contradiction. We know that

B ∞ = 2 ω \{10 ∞ }, so e -1 ({10 ∞ }) = (T ∩ 3 ω )\e -1 (B ∞ ) is a Σ 0 2 subset of 3 ω since T ∩ 3 ω is closed in 3 ω . Thus e -1 ({10 ∞ }) is a countable union of compact subsets of 3 ω .
Consider now the cartesian product ({0} ∪ E) ω of countably many copies of {0} ∪ E. The set {0} ∪ E is countable and it can be equipped with the discrete topology. The product ({0} ∪ E) ω is equipped with the product topology of the discrete topology on {0} ∪ E. In these conditions, the topological space ({0} ∪ E) ω is homeomorphic to the Baire space ω ω . Consider now the map h : ({0} ∪ E) ω → e -1 ({10 ∞ }) defined by h(γ) := 1[ ⌢ i∈ω γ i ] for each sequence γ = (γ 0 , γ 1 , . . .) ∈ ({0} ∪ E) ω . The map h is a homeomorphism by the previous discussion. As ({0} ∪ E) ω is homeomorphic to ω ω , the Baire space ω ω is also homeomorphic to e -1 ({10 ∞ }). This implies that ω ω is a countable union of compact sets. But this is absurd, by Theorem 7.10 in [START_REF] Kechris | Classical Descriptive Set Theory[END_REF].

• It remains to see that A is context-free. We assume here that the reader is familiar with the theory of formal languages and of context-free languages; basic notions may be found in the Handbook Chapter [START_REF] Autebert | Context Free Languages and Pushdown Automata[END_REF].

It is easy to see that the language E is in fact accepted by a 1-counter automaton: it is the set of words s ∈ 3 <ω such that

∀1 ≤ l < |s| n 2 (s ↾ l) < n 1 (s ↾ l) and n 2 (s) = n 1 (s) and s(0) = 1 and s(|s|-1) = 2.
This implies that A is also accepted by a 1-counter automaton because the class of 1-counter languages is closed under concatenation and star operation. In particular A is a context-free language because the class of languages accepted by 1-counter automata form a strict subclass of the class of context-free languages.

Remark. The operation α → α ←֓ we have defined is very close to the erasing operation defined by J. Duparc in his study of the Wadge hierarchy (see [START_REF] Duparc | Wadge Hierarchy and Veblen Hierarchy: Part 1: Borel Sets of Finite Rank[END_REF]). However we have modified this operation in such a way that α ←֓ is always infinite when α is infinite, and that it has the good property with regard to ω-powers and topological complexity.

Question. What are the Wadge classes Γ for which there is A ⊆ 2 <ω such that A ∞ is Γ-complete? We have seen that Theorem 1.2 solves completely the case where Γ is a Borel class, and it also solves the problem for some other Wadge classes. The problem is solved for a few other Wadge classes in [START_REF] Lecomte | Sur les Ensembles de Phrases Infinies Constructibles a Partir d'un Dictionnaire sur un Alphabet Fini[END_REF][START_REF] Lecomte | Omega-Powers and Descriptive Set Theory[END_REF]. We do not know (yet?) any Wadge class for which this problem cannot be solved.

Effective descriptive set theory background.

Basic facts and notation.

• In [START_REF] Moschovakis | Descriptive Set Theory[END_REF], the classical arithmetical hierarchy is defined as follows (see 3E). Let X be a recursively presented Polish space, [N (X, k)] k∈ω an effective enumeration of a neighborhood basis for the topology of X, and B ⊆ X. We say that

B ∈ Σ 0 1 (X) if there is a recursive map ε : ω → ω such that B = i∈ω N [X, ε(i)]. If n ≥ 1 is an integer, then Π 0 n is the class of complements of Σ 0 n sets. We say that B ∈ Σ 0 n+1 if there is C ∈ Π 0 n (ω×X) such that B = ∃ ω C := {x ∈ X | ∃i ∈ ω (i, x) ∈ C}. We also set ∆ 0 n := Σ 0 n ∩ Π 0 n . • We say that γ ∈ Σ 0 1 if {k ∈ ω | γ ∈ N (ω ω , k)} ∈ Σ 0 1 (ω). Let β ∈ 2 ω . The relativization Σ 0 1 (β) of Σ 0 1 to β is defined as follows. A set P ⊆ X is in Σ 0 1 (β) if there is Q ∈ Σ 0 1 (2 ω ×X) such that P = Q β . As before we say that γ ∈ Σ 0 1 (β) if {k ∈ ω | γ ∈ N (ω ω , k)} ∈ Σ 0 1 (β)(ω).
• Recall the existence of a good parametrization in Σ 0 n for Σ 0 n (see 3E.2, 3F.6 and 3H.1 in [START_REF] Moschovakis | Descriptive Set Theory[END_REF]). This means that there is a system of sets G Σ 0 n ,X ∈ Σ 0 n (ω ω × X) such that for each recursively presented Polish space X and for each P ⊆ X,

P ∈ Σ 0 n ⇔ ∃γ ∈ ω ω P = G Σ 0 n ,X γ , P ∈ Σ 0 n ⇔ ∃γ ∈ Σ 0 1 P = G Σ 0 n ,X γ .
Moreover, if X is a recursively presented Polish space of type at most 1 (i.e., a finite product of spaces equal to ω, ω ω or 2 ω ), and Y is a recursively presented Polish space, then there is S X,Y

Σ 0 n : ω ω ×X → ω ω recursive so that (γ, x, y) ∈ G Σ 0 n ,X×Y ⇔ [S X,Y Σ 0 n (γ, x), y] ∈ G Σ 0 n ,Y .
Note that G Σ 0 n ,X is universal for Σ 0 n (X) (with ω ω instead of 2 ω ).

• Let f : X → Y be a partial function, D ⊆ Domain(f ) and P ⊆ X ×ω. Then P computes f on D if

x ∈ D ⇒ ∀k ∈ ω [f (x) ∈ N (Y, k) ⇔ (x, k) ∈ P ].
If P is in some pointclass Γ and computes f on D, then we say that f is Γ -recursive on D . This means that f -1 [N (Y, k)] is in Γ , uniformly in k. We also say recursive on D for Σ 0 1 -recursive on D.

• We also recall the notation for the coding of partial recursive functions from X into Y introduced in [Mos80] (see 7A). We first define a partial function U :

ω ω ×X → Y by U (γ, x) ↓ ⇔ U (γ, x) is defined ⇔ ∃y ∈ Y ∀k ∈ ω [y ∈ N (Y, k) ⇔ (γ, x, k) ∈ G Σ 0 1 ,X×ω ], U (γ, x) := the unique y ∈ Y such that ∀k ∈ ω [y ∈ N (Y, k) ⇔ (γ, x, k) ∈ G Σ 0 1 ,X×ω ].
Now let γ ∈ ω ω . The function {γ} X,Y : X → Y is defined by {γ} X,Y (x) := U (γ, x). Then a partial function f : X → Y is recursive on its domain if and only if there is γ ∈ Σ 0 1 such that f (x) = {γ} X,Y (x) when f (x) is defined. More generally, the functions of the form {γ} X,Y are the partial continuous functions from a subset of X into Y . We will write {γ} instead of {γ} X,Y when Y = ω ω , in order to simplify the notation.

If X is of type at most 1 and Z is a recursively presented Polish space, then there is a recursive map S X,Y,Z

Σ 0 1 : ω ω ×X → ω ω such that {γ} X×Y,Z (x, y) = {S X,Y,Z Σ 0 1 (γ, x)} Y,Z (y) if (γ, x) ∈ ω ω ×X.
Kleene's Recursion Theorem asserts that if f : ω ω × X → Y is recursive on its domain, then there is

ε * ∈ Σ 0 1 such that f (ε * , x) = {ε * } X,Y (x) when f (ε * , x) is defined (see 7A.2 in [Mos80]
). This will be the fundamental tool in the sequel. It is very useful to prove effective versions of classical results.

• We will use the following basic maps:

-We first define a one-to-one map < . >: ω <ω → ω. Let (p n ) n∈ω be the sequence of prime numbers. We set < ∅ >:= 1, and, if t := (t 0 , ..., t l ) ∈ ω l+1 , then we set t :=< t 0 , ..., t l >:= p t 0 +1 0 ...p t l +1 l .

-If k ∈ ω, then we say that "Seq(k)" (i.e., "k is a sequence") if k =< t 0 , ..., t l-1 > for some t 0 , ..., t l-1 .

-The length lh(k) of k ∈ ω is l if Seq(k) and k =< t 0 , ..., t l-1 >, 0 otherwise.

-If k, i ∈ ω, then we define (k) i := t i if Seq(k), k =< t 0 , ..., t l-1 > and i < l, 0 otherwise.

-If γ ∈ ω ω and i ∈ ω, then we define (γ) i ∈ ω ω by (γ) i (j) := γ(< i, j >). But here we do not use the injection (i, j) → < i, j > above, since we want a bijection from ω 2 into ω. So we use the notation < i, j > for 2 i • (2j +1)-1, when (γ) i is concerned. The inverse bijection is denoted s → [(s) 0 , (s) 1 ].

Borel codes and closure properties.

Notation. We give a coding of Borel sets slightly different from the one given in [START_REF] Moschovakis | Descriptive Set Theory[END_REF] (see 7B), since there is a problem for Σ 0 1 . It can be found in some unpublished notes written by Louveau, [Lou??]. We define by induction on the countable ordinal ξ ≥ 1 the set BC ξ of Borel codes for Σ 0 ξ as follows. If γ ∈ ω ω , then we define γ * ∈ ω ω by γ * (i) := γ(i+1). We set

BC 1 := { γ ∈ ω ω | γ(0) = 0 }, BC ξ := γ ∈ ω ω | γ(0) = 1 and ∀i ∈ ω {γ * }(i) ↓ and {γ * }(i) ∈ 1≤η<ξ BC η if ξ ≥ 2.
The set of Borel codes is BC := 1≤ξ<ω 1 BC ξ . We also set BC * := 2≤ξ<ω 1 ↑ BC ξ . Now let X be a recursively presented Polish space. We define ρ X : BC → ∆ 1 1 (X) by induction:

ρ X (γ) :=    i∈ω N [X, γ * (i)] if γ ∈ BC 1 , i∈ω X \ ρ X [{γ * }(i)] if γ ∈ BC * .
Clearly, ρ X [BC ξ ] = Σ 0 ξ (X), by induction on ξ. The following is a consequence of 7B.1.(ii).(a) in [START_REF] Moschovakis | Descriptive Set Theory[END_REF]. It expresses the fact that the class of Borel sets is uniformly closed under complementation. Lemma 3.1 There is a recursive map u ¬ : ω ω → ω ω such that for each 1 ≤ ξ < ω 1 and for each γ ∈ BC ξ , u ¬ (γ) ∈ BC ξ+1 , and ρ X [u ¬ (γ)] = ¬ρ X (γ) for each recursively presented Polish space X.

Proof. Just copy the proof of 7B.1.(ii).(a) in [START_REF] Moschovakis | Descriptive Set Theory[END_REF]: it gives more than the statement in [START_REF] Moschovakis | Descriptive Set Theory[END_REF].

In the sequel we will need a refinement of 7B.1.(iii) in [START_REF] Moschovakis | Descriptive Set Theory[END_REF]: Lemma 3.2 Let X be a recursively presented Polish space of type at most 1. Then there is a recursive map u X s : ω ω ×X → ω ω such that for each 1 ≤ ξ < ω 1 , for each γ ∈ BC ξ and for each x ∈ X, u X s (γ, x) ∈ BC ξ , and ρ Y [u X s (γ, x)] = ρ X×Y (γ) x for each recursively presented Polish space Y .

Some of the ideas of the proof are contained in 7A.3 in [START_REF] Moschovakis | Descriptive Set Theory[END_REF].

Proof. For ξ = 1, using the description of basic clopen sets in products (see 3B.1 in [START_REF] Moschovakis | Descriptive Set Theory[END_REF]), we define a subset of ω ω ×X ×ω by

(γ, x, k) ∈ P ⇔ ∃i ∈ ω k = 0, γ * (i) 2 and x ∈ N X, 0, γ * (i) 1 .
By 3D.5 in [START_REF] Moschovakis | Descriptive Set Theory[END_REF], Σ 0 1 is closed under recursive substitutions, so that P ∈ Σ 0 1 . By 3C.4 in [START_REF] Moschovakis | Descriptive Set Theory[END_REF], there is

P * ∈ ∆ 0 1 (ω ω ×X ×ω 2 ) with (γ, x, k) ∈ P ⇔ ∃n ∈ ω (γ, x, k, n) ∈ P *
(the idea is that in a space of type at most 1, an open set is a countable union of clopen sets). We define a map g : ω ω ×X → ω ω by g(γ, x)(j) :=    (j -1) 0 if j > 0 and [γ, x, (j -1) 0 , (j -1) 1 ] ∈ P * , 0 otherwise.

Clearly, g is recursive and g(γ, x) ∈ BC 1 .

• For the general case, we define a partial function ψ :

(ω ω ) 2 ×X ×ω → ω ω by ψ(ε, γ, x, i) :=    g[{γ * }(i), x] if {γ * }(i)(0) = 0, {ε}[{γ * }(i), x] if {γ * }(i)(0) = 1.
The idea is that we want to build a recursive map u X s , that will have a recursive code ε * . The function ψ describes the properties that we want for u X s , and Kleene's Recursion Theorem will give the recursive code. By 3G.1 and 3G.2 in [START_REF] Moschovakis | Descriptive Set Theory[END_REF], the collection of partial functions which are recursive on their domain is closed under composition, so that ψ is recursive on its domain. Let

ν ∈ Σ 0 1 such that ψ(ε, γ, x, i) = {ν}(ε, γ, x, i) if ψ(ε, γ, x, i) is defined. Note that {ν}(ε, γ, x, i) = {S (ω ω ) 2 ×X,ω,ω ω Σ 0 1 (ν, ε, γ, x)}(i) when it is defined. We define a recursive map ϕ : (ω ω ) 2 ×X → ω ω by ϕ(ε, γ, x) :=      g(γ, x) if γ(0) = 0, 1 ⌢ S (ω ω ) 2 ×X,ω,ω ω Σ 0 1 (ν, ε, γ, x) if γ(0) = 0.
By Kleene's Recursion Theorem, there is ε * ∈ Σ 0 1 such that ϕ(ε * , γ, x) = {ε * }(γ, x) for each (γ, x) in ω ω × X. We put u X s (γ, x) := {ε * }(γ, x). Note that the map u X s is a total recursive map. We prove that u X s (γ, x) satisfies the required properties by induction on ξ.

• Let (γ, x) ∈ BC 1 ×X. We have u X s (γ, x) = {ε * }(γ, x) = ϕ(ε * , γ, x) = g(γ, x). So u X s (γ, x) is in BC 1 , by the previous discussion. If moreover Y is a recursively presented Polish space, then using the proof of 3B.1 in [START_REF] Moschovakis | Descriptive Set Theory[END_REF] we get

y ∈ ρ X×Y (γ) x ⇔ ∃i ∈ ω (x, y) ∈ N [X ×Y, γ * (i)] ⇔ ∃i ∈ ω y ∈ N Y, 0, γ * (i) 2 and x ∈ N X, 0, γ * (i) 1 ⇔ ∃k ∈ ω [y ∈ N (Y, k) and (γ, x, k) ∈ P ] ⇔ ∃i ∈ ω y ∈ N [Y, (i) 0 ] and [γ, x, (i) 0 , (i) 1 ] ∈ P * ⇔ ∃i ∈ ω y ∈ N Y, [g(γ, x)] * (i) ⇔ y ∈ ρ Y [g(γ, x)].
• Now let (γ, x) ∈ BC ξ ×X, with ξ ≥ 2. We have

u X s (γ, x) = {ε * }(γ, x) = ϕ(ε * , γ, x) = 1 ⌢ S (ω ω ) 2 ×X,ω,ω ω Σ 0 1 (ν, ε * , γ, x).
As γ ∈ BC ξ , {γ * }(i) is defined for each integer i. In particular, ψ(ε * , γ, x, i) is defined for each (γ, x, i) in ω ω ×X ×ω since {γ * }(i)(0) ∈ 2, and equal to

{ν}(ε * , γ, x, i) = {S (ω ω ) 2 ×X,ω,ω ω Σ 0 1 (ν, ε * , γ, x)}(i).
This shows that {u X s (γ, x) * }(i) is defined for each integer i.

If {γ * }(i)(0) = 0, then {u X s (γ, x) * }(i) = g[{γ * }(i), x] = u X s [{γ * }(i), x]. As {γ * }(i) ∈ BC 1 , u X s [{γ * }(i), x] is in BC 1 too. Similarly, if {γ * }(i)(0) = 1, then {u X s (γ, x) * }(i) = {ε * }[{γ * }(i), x] = u X s [{γ * }(i), x]. Then u X s [{γ * }(i), x] ∈ BC η for some 1 ≤ η < ξ, by induction assumption. This shows that u X s (γ, x) is in BC ξ . If Y is a recursively presented Polish space, then ρ Y u X s [{γ * }(i), x] = ρ X×Y [{γ * }(i)] x , by induction assumption. This shows that ρ Y [u X s (γ, x)] = ρ X×Y (γ) x .
Lemma 3.2 expresses, among other things, the fact that the pointclasses Σ 0 ξ are uniformly closed under taking sections at points in spaces of type at most 1. Similarly, we now prove another lemma stating, among other things, that the pointclasses Σ 0 ξ are uniformly closed under substitutions of partial recursive functions (when δ below is recursive). Lemma 3.3 Let X, Y be recursively presented Polish spaces. Then there is u X,Y r : (ω ω ) 2 → ω ω recursive such that for each 1 ≤ ξ < ω 1 , for each γ ∈ BC ξ and for each δ ∈ ω ω , u X,Y r (γ, δ) ∈ BC ξ . Moreover, we have

x ∈ ρ X [u X,Y r (γ, δ)] ⇔ {δ} X,Y (x) ∈ ρ Y (γ) if {δ} X,Y (x) is defined.
Proof. The scheme of the proof is quite similar to that of Lemma 3.2. Indeed, this is again an application of Kleene's Recursion Theorem. For ξ = 1, we choose P ∈ Σ 0 1 (ω ω ×X ×ω) such that

U (δ, x) ↓ ⇒ ∀k ∈ ω [ U (δ, x) ∈ N (Y, k) ⇔ (δ, x, k) ∈ P ].
(this is possible since U is recursive on its domain; see 7A.1 in [START_REF] Moschovakis | Descriptive Set Theory[END_REF]). By 3C.4 and 3C.5 in [START_REF] Moschovakis | Descriptive Set Theory[END_REF], there is

P * ∈ ∆ 0 1 (ω ω ×ω 3 ) with (δ, x, k) ∈ P ⇔ ∃i ∈ ω x ∈ N [X, (i) 0 ] and [δ, k, (i) 0 , (i) 1 ] ∈ P * .
We define a map g :

(ω ω ) 2 → ω ω by g(γ, δ)(j) :=      (j -1) 0 0 if j > 0 and δ, γ * [(j -1) 1 ], (j -1) 0 0 , (j -1) 0 1 ∈ P * , 0 otherwise.
Clearly, g is recursive and g(γ, δ) ∈ BC 1 .

• For the general case, we define a partial function ψ : (ω ω ) 3 ×ω → ω ω by

ψ(ε, γ, δ, i) :=    g[{γ * }(i), δ] if {γ * }(i)(0) = 0, {ε}[{γ * }(i), δ] if {γ * }(i)(0) = 1.
We argue as in the proof of Lemma 3.2 to define ϕ : (ω ω ) 3 → ω ω , and we put u X,Y r (γ, δ) := {ε * }(γ, δ). The map u X,Y r is a total recursive map. We show that u X,Y r (γ, δ) satisfies the required properties by induction on ξ.

• If (γ, δ) ∈ BC 1 ×ω ω and {δ} X,Y (x) is defined, then x ∈ ρ X [u X,Y r (γ, δ)] ⇔ ∃k ∈ ω x ∈ N [X, g(γ, δ) * (k)] ⇔ ∃k ∈ ω x ∈ N X, (k) 0 0 and δ, γ * [(k) 1 ], (k) 0 0 , (k) 0 1 ∈ P * ⇔ ∃j ∈ ω ∃i ∈ ω x ∈ N [X, (i) 0 ] and [δ, γ * (j), (i) 0 , (i) 1 ] ∈ P * ⇔ ∃j ∈ ω [δ, x, γ * (j)] ∈ P ⇔ ∃j ∈ ω {δ} X,Y (x) ∈ N [Y, γ * (j)] ⇔ {δ} X,Y (x) ∈ ρ Y (γ).
• Now let γ ∈ BC ξ with ξ ≥ 2, and δ ∈ ω ω . As in the proof of Lemma 3.

2, u X,Y r (γ, δ) ∈ BC ξ . If {δ} X,Y (x) is defined, then x ∈ ρ X u X,Y r [{γ * }(i), δ] ⇔ {δ} X,Y (x) ∈ ρ Y [{γ * }(i)],
by induction assumption. This shows that

x ∈ ρ X [u X,Y r (γ, δ)] ⇔ {δ} X,Y (x) ∈ ρ Y (γ).
As a corollary, one can prove the uniform closure of the pointclasses Σ 0 ξ under fixations of recursive arguments. It is sometimes convenient to "view a code in BC 1 as an element of BC 2 ", even if it is not formally correct. The next lemma expresses this: Lemma 3.4 Let X be a recursively presented Polish space. Then there is u X * : ω ω → ω ω recursive such that for each γ ∈ BC 1 (resp., BC * ), u X * (γ) ∈ BC 2 (resp., u X * (γ) = γ), and ρ X [u X * (γ)] = ρ X (γ).

Proof. We define

R ∈ Σ 0 1 (ω ω × X) by (γ, x) ∈ R ⇔ ∃i ∈ ω x ∈ N [X, γ * (i)]. As R ∈ Σ 0 2 there is C ∈ Π 0 1 (ω×ω ω ×X) such that R = ∃ ω C. Let ε 0 ∈ Σ 0 1 such that ¬C = i∈ω N [ω×ω ω ×X, ε 0 (i)]. Note that 0 ⌢ ε 0 ∈ Σ 0 1 ∩ BC 1 and ¬C = ρ ω×ω ω ×X (0 ⌢ ε 0 ). Using Lemma 3.2, we see the existence of γ 0 ∈ Σ 0 1 such that {γ 0 }(γ, i) = u ω×ω ω s (0 ⌢ ε 0 , i, γ) for each (γ, i) ∈ ω ω ×ω. Then we define u X * (γ) := 1 ⌢ S ω ω ,ω,ω ω Σ 0 1 (γ 0 , γ) if γ ∈ BC 1 , γ otherwise.
We now prove another lemma stating, among other things, that the pointclasses Σ 0 ξ are uniformly closed under finite intersections and unions: Lemma 3.5 Let X be a recursively presented Polish space. There is u X f : 2×ω ×ω ω → ω ω recursive such that for each (ξ, a, n, γ)

∈ (ω 1 \{0})×2×ω×ω ω , (a) If (γ) i ∈ BC 1 ∪ BC ξ for each i ≤ n, then u X f (a, n, γ) is in BC 1 ∪ BC ξ . Moreover, the equalities ρ X [u X f (0, n, γ)] = i≤n ρ X [(γ) i ] and ρ X [u X f (1, n, γ)] = i≤n ρ X [(γ) i ] hold. (b) If moreover ξ ≥ 2 and (γ) i ∈ BC ξ for some i ≤ n, then u X f (a, n, γ) is in BC ξ .
Proof. Once again, this is an application of Kleene's Recursion Theorem. For ξ = 1, by 3B.2 in [START_REF] Moschovakis | Descriptive Set Theory[END_REF] there is f :

ω 3 → ω recursive such that, for (u, n) ∈ ω 2 , i≤n N [X, (u) i ] = m∈ω N [X, f (u, n, m)].
We set g(a, n, γ)(0) := 0 and

g(0, n, γ)(i+1) := f < [(γ) 0 ] * (i) 0 0 , ..., [(γ) n ] * (i) 0 n >, n, (i) 1 , g(1, n, γ)(i+1) :=    [(γ) (i) 0 ] * [(i) 1 ] if (i) 0 ≤ n, 0 otherwise. Note that g(a, n, γ) ∈ BC 1 . If (γ) i ∈ BC 1 for each i ≤ n, then we get ρ X [g(0, n, γ)] = i∈ω N [X, g(0, n, γ)(i+1)] = (j,m)∈ω 2 N X, f < [(γ) 0 ] * [(j) 0 ], ..., [(γ) n ] * [(j) n ] >, n, m = j∈ω i≤n N X, [(γ) i ] * [(j) i ] = i≤n j∈ω N X, [(γ) i ] * (j) = i≤n ρ X [(γ) i ].
Moreover,

ρ X [g(1, n, γ)] = i∈ω N [X, g(1, n, γ)(i+1)] = i≤n j∈ω N X, [(γ) i ] * (j) = i≤n ρ X [(γ) i ].
• For the general case, using Lemma 3.4 we define a partial function h : ω ω ×ω 2 → ω ω by h(γ, n, j)

i :=      u X * [(γ) i ] * [(j) i ] if i ≤ n, 0 ∞ otherwise.
It allows us to define another partial function ψ : ω ω ×2×ω×ω ω ×ω → ω ω by ψ(ε, a, n, γ, j)

:= {ε}[1-a, n, h(γ, n, j)].
We argue as in the proof of Lemma 3.2 to define ν and a recursive map ϕ :

ω ω ×2×ω×ω ω → ω ω by ϕ(ε, a, n, γ) :=      g(a, n, γ) if (γ) i (0) = 0 for each i ≤ n, 1 ⌢ S ω ω ×2×ω×ω ω ,ω,ω ω Σ 0 1 (ν, ε, a, n, γ) if (γ) i (0) = 0 for some i ≤ n.
By Kleene's Recursion Theorem, there is ε * ∈ Σ 0 1 such that ϕ(ε * , a, n, γ) = {ε * }(a, n, γ) for each (a, n, γ) in 2× ω × ω ω . We put u X f (a, n, γ) := {ε * }(a, n, γ). The map u X f is a total recursive map. We show that u X f (a, n, γ) satisfies the required properties by induction on ξ.

• Assume that (γ) i ∈ BC 1 holds for each i ≤ n. We have u X f (a, n, γ) = g(a, n, γ), so we are done, by the previous discussion. Assume now that ξ ≥ 2, and that (γ) i ∈ BC 1 ∪ BC ξ for each i ≤ n. We may assume that (γ) i ∈ BC ξ holds for some i ≤ n. Then u X * [(γ) i ] * (k) is defined for each integer k. In particular, h(γ, n, j) and ψ(ε * , a, n, γ, j) are defined for each (a, j) in 2×ω. Thus

{u X f (a, n, γ) * }(j) = u X f [1-a, n, h(γ, n, j)]
is defined for each integer j. As

u X * [(γ) i ] * (k) is in some BC η k with 1 ≤ η k < ξ for each integer k, there is 1 ≤ η < ξ such that h(γ, n, j) i is in BC 1 ∪ BC η for each i ≤ n. By induction assumption, we get u X f [1 -a, n, h(γ, n, j)] ∈ BC 1 ∪ BC η . This shows that u X f (a, n, γ) ∈ BC ξ . Moreover, by induction assumption we get ρ X [u X f (0, n, γ)] = j∈ω ¬ i≤n ρ X h(γ, n, j) i = j∈ω i≤n ¬ρ X u X * [(γ) i ] * [(j) i ] = i≤n j∈ω ¬ρ X u X * [(γ) i ] * (j) = i≤n ρ X u X * [(γ) i ] = i≤n ρ X [(γ) i ]. Similarly, we get ρ X [u X f (1, n, γ)] = i≤n ρ X [(γ) i ].
In the sequel we will need a last closure property, asserting, among other things, that the pointclasses Σ 0 ξ are uniformly closed under ∃ ω : Lemma 3.6 (a) There is a recursive map u ∃ : ω ω → ω ω such that for each 1 ≤ ξ < ω 1 and for each γ ∈ BC ξ , u ∃ (γ) ∈ BC ξ , and x ∈ ρ X [u ∃ (γ)] ⇔ ∃n ∈ ω (n, x) ∈ ρ ω×X (γ), for each recursively presented Polish space X and for each x ∈ X. (b) There is a recursive map u (.) :

ω ω → ω ω such that for each 1 ≤ ξ < ω 1 , (γ) n ∈ BC ξ for each n ∈ ω implies that u (.) (γ) ∈ BC ξ , and x ∈ ρ X [u (.) (γ)] ⇔ ∃n ∈ ω x ∈ ρ X [(γ) n ]
for each recursively presented Polish space X and for each x ∈ X.

Proof. Once again we code the properties that we want. So a look at the end of the proofs of (a) and (b) can give an idea of the intuition behind them.

(a) By 3B.1 in [START_REF] Moschovakis | Descriptive Set Theory[END_REF], there are g and h recursive such that

N (ω ×X, k) = N [ω, g(k)]×N [X, h(k)] for each integer k. If γ(0) = 0, then we put u ∃ (γ)(j) :=      h γ * [(j -1) 0 ] if j > 0 and (j -1) 1 ∈ N ω, g γ * [(j -1) 0 ] , 0 otherwise.
Using Lemma 3.2, we define a partial function f :

ω ω ×ω → ω ω by f (γ, i) := u ω s {γ * }[(i) 1 ], (i) 0 .
As f is recursive on its domain, there is

ε 0 ∈ Σ 0 1 such that f (γ, i) = {ε 0 }(γ, i) if f (γ, i) is defined. If γ(0) = 0, then we put u ∃ (γ) := 1 ⌢ S ω ω ,ω,ω ω Σ 0 1 (ε 0 , γ). This defines a recursive map u ∃ . If γ(0) = 0 and γ ∈ BC ξ , then {[u ∃ (γ)] * }(i) = {S ω ω ,ω,ω ω Σ 0 1 (ε 0 , γ)}(i) = {ε 0 }(γ, i) = f (γ, i). Thus u ∃ (γ) ∈ BC ξ , even if γ(0) = 0. Let x ∈ X. If γ(0) = 0, then ∃n ∈ ω (n, x) ∈ ρ ω×X (γ) ⇔ ∃n ∈ ω ∃p ∈ ω (n, x) ∈ N [ω×X, γ * (p)] ⇔ ∃n ∈ ω ∃p ∈ ω n ∈ N ω, g[γ * (p)] and x ∈ N X, h[γ * (p)] ⇔ ∃i ∈ ω (i) 1 ∈ N ω, g γ * [(i) 0 ] and x ∈ N X, h γ * [(i) 0 ] ⇔ x ∈ ρ X [u ∃ (γ)]. If γ(0) = 0, then ∃n ∈ ω (n, x) ∈ ρ ω×X (γ) ⇔ ∃n ∈ ω ∃p ∈ ω (n, x) / ∈ ρ ω×X [{γ * }(p)] ⇔ ∃i ∈ ω ¬ [(i) 0 , x] ∈ ρ ω×X {γ * }[(i) 1 ] ⇔ ∃i ∈ ω ¬ x ∈ ρ X [f (γ, i)] ⇔ x ∈ ρ X [u ∃ (γ)]. (b) If (γ) 0 (0) = 0, then we put u (.) (γ)(j) :=    0 if j = 0, [(γ) (j-1) 0 ] * [(j -1) 1 ] otherwise.
We define a partial function f ′ :

ω ω × ω → ω ω by f ′ (γ, i) := {[(γ) (i) 0 ] * }[(i) 1 ]. As f ′ is recursive on its domain, there is γ 0 ∈ Σ 0 1 such that f ′ (γ, i) = {γ 0 }(γ, i) if f ′ (γ, i) is defined. If (γ) 0 (0) = 0, then we put u (.) (γ) := 1 ⌢ S ω ω ,ω,ω ω Σ 0 1 (γ 0 , γ).
This defines a recursive map u (.) . If ξ ≥ 2 and (γ) n ∈ BC ξ for each integer

n, then {[u (.) (γ)] * }(i) = {S ω ω ,ω,ω ω Σ 0 1 (γ 0 , γ)}(i) = {γ 0 }(γ, i) = f ′ (γ, i). Thus u (.) (γ) ∈ BC ξ , even if ξ = 1. Let x ∈ X. If (γ) 0 (0) = 0, then ∃n ∈ ω x ∈ ρ X [(γ) n ] ⇔ ∃n ∈ ω ∃p ∈ ω x ∈ N X, [(γ) n ] * (p) ⇔ ∃i ∈ ω x ∈ N X, [(γ) (i) 0 ] * [(i) 1 ] ⇔ x ∈ ρ X [u (.) (γ)]. If (γ) 0 (0) = 0, then ∃n ∈ ω x ∈ ρ X [(γ) n ] ⇔ ∃n ∈ ω ∃p ∈ ω x / ∈ ρ X {[(γ) n ] * }(p) ⇔ ∃i ∈ ω ¬ x ∈ ρ X {[(γ) (i) 0 ] * }[(i) 1 ] ⇔ ∃i ∈ ω ¬ x ∈ ρ X [f ′ (γ, i)] ⇔ x ∈ ρ X [u (.) (γ)].
This finishes the proof.

The hyperarithmetical hierarchy.

The notion of a hyperarithmetical set is defined in [START_REF] Moschovakis | Descriptive Set Theory[END_REF] (see 7B): a subset of a recursively presented Polish space is hyperarithmetical if it is Borel and has a recursive Borel code. We can define a hyperarithmetical hierarchy, extending the arithmetical hierarchy. The following characterization of the arithmetical pointclasses Σ 0 n can be found in Louveau's notes [Lou??]:

Theorem 3.7 Let X be a recursively presented Polish space, and n ≥ 1 an integer. Then

Σ 0 n (X) = {ρ X (γ) | γ ∈ Σ 0 1 ∩ BC n }.
Actually, we will use only a small part of it. More specifically, we will only use the fact that if

P is Σ 0 1 (X), then there is γ ∈ Σ 0 1 ∩ BC 1 with P = ρ X (γ). It is very simple: there is ε ∈ Σ 0 1 such that P = i∈ω N [X, ε(i)] = ρ X (0 ⌢ ε). Thus γ := 0 ⌢ ε is suitable.
The following definition comes naturally after Theorem 3.7, and can be found in [Lou??]: Definition 3.8 Let X be a recursively presented Polish space, and 1 ≤ ξ < ω 1 . Then we set

Σ 0 ξ (X) = {ρ X (γ) | γ ∈ Σ 0 1 ∩ BC ξ }, Π 0 ξ (X) = Σ 0 ξ (X), ∆ 0 ξ (X) = Σ 0 ξ (X) ∩ Π 0 ξ (X).
This defines the hyperarithmetical hierarchy.

Note that Lemma 3.3 (resp., 3.5, 3.6) implies that the hyperarithmetical pointclasses are closed under recursive substitutions (resp., finite intersections and unions, ∃ ω ). Now we construct recursive maps giving codes for the basic neighborhoods and their complements in spaces of type at most 1. Lemma 3.9 Let X be a recursively presented Polish space of type at most 1. (a) There is a recursive map u N : ω → ω ω such that u N (k) ∈ BC 1 , and

ρ X [u N (k)] = N (X, k). (b) There is a recursive map u X ¬N : ω → ω ω such that u X ¬N (k) ∈ BC 1 , and ρ X [u X ¬N (k)] = ¬N (X, k). Proof. (a) Put u N (k) := 0k0 ∞ . (b) By 3C.3 in [Mos80], the equivalence (x, k) ∈ R ⇔ x / ∈ N (X, k) defines R ∈ Σ 0 1 (X ×ω). By Theorem 3.7 there is γ 0 ∈ Σ 0 1 ∩ BC 1 with R = ρ X×ω (γ 0 ). Using Lemma 3.2 we set u X ¬N (k) := u ω s (γ 0 , k).
Now we use this to prove that, uniformly in ξ ≥ 2, a set in the pointclass Σ 0 ξ (X) (resp., Σ 0 ξ (X)) is the disjoint union of sets in Π 0 <ξ (resp., Π 0 <ξ ), if X is a space of type at most 1. We will use the notation

E = • i∈ω E i
to express the fact that E is the disjoint union of the E i 's.

Lemma 3.10 Let X be a recursively presented Polish space of type at most 1. Then there is a recursive map

u X d : ω ω → ω ω such that u X d (γ) ∈ BC ξ if γ ∈ BC ξ , for each 1 ≤ ξ < ω 1 . Moreover, (a) There is a recursive map u X c : ω ω ×ω → ω ω such that (1) u X c (γ, i) ∈ BC 1 for each (γ, i) ∈ ω ω ×ω. (2) {[u X d (γ)] * }(i) is defined, in BC 1 , ρ X {[u X d (γ)] * }(i) ∈ ∆ 0 1 and ¬ρ X {[u X d (γ)] * }(i) = ρ X [u X c (γ, i)] for each (γ, i) ∈ BC 1 ×ω. (b) If 1 ≤ ξ < ω 1 and γ ∈ BC ξ , then ρ X (γ) = • i∈ω ¬ρ X {[u X d (γ)] * }(i) .
Proof. For ξ = 1, a look at the computation of ρ X (γ) at the end of this point can help to understand what is going on. We first define a map f : ω ω ×ω → ω ω , using Lemma 3.9, as follows:

f (γ, i) j :=    u X ¬N [γ * (j)] if j < i, u N [γ * (i)] if j ≥ i. As f is recursive, the formula u X c (γ, i) := u X f [0, i, f (γ, i)] defines u X c recursive such that u X c (γ, i) ∈ BC 1 for each (γ, i) ∈ ω ω
×ω (see Lemma 3.5). Then, using Lemma 3.9, we define a map f :

ω ω ×ω → ω ω : f (γ, i) j :=    u N [γ * (j)] if j < i, u X ¬N [γ * (i)] if j ≥ i.
As f is recursive, and using Lemma 3.5, there is

ε 0 ∈ Σ 0 1 such that {ε 0 }(γ, i) = u X f [1, i, f (γ, i)] ∈ BC 1 for each (γ, i) ∈ ω ω × ω.
We define a recursive map g : ω ω → ω ω by g(γ)

:= 0 ⌢ S ω ω ,ω,ω ω Σ 0 1 (ε 0 , γ). If (γ, i) ∈ BC 1 × ω, then {[g(γ)] * }(i) = {S ω ω ,ω,ω ω Σ 0 1 (ε 0 , γ)}(i) = {ε 0 }(γ, i) = u X f [1, i, f (γ, i)] is defined, ρ X {[g(γ)] * }(i) ∈ ∆ 0
1 since it is a finite union of clopen sets, and

¬ρ X {[g(γ)] * }(i) = ρ X [u X c (γ, i)]. Moreover, ρ X (γ) = i∈ω N [X, γ * (i)] = • i∈ω N [X, γ * (i)]\ j<i N [X, γ * (j)] = • i∈ω ¬ ρ X u X ¬N [γ * (i)] ∪ j<i ρ X u N [γ * (j)] = • i∈ω ¬ρ X u X f [1, i, f (γ, i)] = • i∈ω ¬ρ X {[g(γ)] * }(i) .
• For the general case, assume that γ ∈ BC ξ , with ξ ≥ 2. We set B j := ρ X [{γ * }(j)], so that we can write ρ X (γ) = j∈ω ¬B j . Note that {γ * }(j) ∈ BC η j , where 1 ≤ η j < ξ. We set

B j,i :=        ¬N X, [{γ * }(j)] * (i) if [{γ * }(j)](0) = 0, ρ X [{γ * }(j)] * (i) otherwise,
so that B j := i∈ω ¬B j,i .

By Lemma 3.9, B j,i = ρ X u X ¬N [{γ * }(j)] * (i) if [{γ * }(j)](0) = 0, and

¬B j,i =        ρ X u N [{γ * }(j)] * (i) if [{γ * }(j)](0) = 0, ρ X u ¬ [{γ * }(j)] * (i) otherwise, by Lemma 3.1. Thus ρ X (γ)= k∈ω ¬B k = • k∈ω j<k B j \B k = • k∈ω j<k i∈ω ¬B j,i \B k = • k∈ω j<k • i∈ω l<i B j,l \ B j,i \B k = • i∈ω j<lh(i) l<(i) j B j,l \ B j,(i) j \B lh(i) = • i∈ω ¬ B lh(i) ∪ j<lh(i) l<(i) j B j,(i) j ∪ ¬B j,l .
Note that the code for B i,j is a partial recursive function of γ, i and j. Using Lemma 3.5, this shows the existence of a partial function f X : ω ω × ω → ω ω , recursive on its domain, such that f X (γ, i) is in 1≤η<ξ BC η and ρ X (γ) =

• i∈ω ¬ρ X [f X (γ, i)] for each γ ∈ BC ξ with ξ ≥ 2. There is ε 1 ∈ Σ 0 1 such that f X (γ, i) = {ε 1 }(γ, i) = {S ω ω ,ω,ω ω Σ 0 1 (ε 1 , γ)}(i) if f X (γ, i) is defined. We define h : ω ω → ω ω by the formula h(γ) := 1 ⌢ S ω ω ,ω,ω ω Σ 0 1 (ε 1 , γ). The map h is recursive, h(γ) ∈ BC ξ and ρ X (γ) = • i∈ω ¬ρ X {[h(γ)] * }(i) if γ ∈ BC ξ and ξ ≥ 2. • It remains to set u X d (γ) := g(γ) if γ(0) = 0, h(γ) otherwise.
Now we will show that the hyperarithmetical hierarchy makes sense, i.e., the existence of sets of arbitrary complexity under ω CK 1 . The intuition is quite simple: we take universal sets. But we have to check that this is effective. [START_REF] Moschovakis | Descriptive Set Theory[END_REF]), and < α := {(m, n) ∈ ω 2 | α(< m, n >) = 1 and α(< n, m >) = 1}. The first relation is used to define the set W O := {α ∈ ω ω | ≤ α is a wellordering on its domain {n ∈ ω | n ≤ α n}}, which is used to define

Notation. Recall that if α ∈ ω ω , then ≤ α := {(m, n) ∈ ω 2 | α(< m, n >) = 1} (see 4A in
ω CK 1 := sup{|α| | α ∈ W O ∩ Σ 0 1 },
where |α| is the order type of ≤ α . The ordinal ω CK 1 is the first non recursive ordinal. If α ∈ ω ω and p ∈ ω, then we define α |p ∈ 2 ω ⊆ ω ω by α |p (q) = 1 ⇔ Seq(q) and lh(q) = 2 and α(q) = 1 and ∀i ∈ 2 (q) i < α p.

If α ∈ W O, then α |p ∈ W O and ≤ α |p is the restriction of ≤ α to the strict ≤ α -predecessors of p. The next lemma expresses the fact that one can find cofinal sequences of ordinals recursively. Lemma 3.11 There is a partial function η : ω ω ×ω → ω ω , recursive on its domain, defined if α ∈ W O and

|α |p | ≥ 1, such that |α |p | = sup ↑ {|α |η(α,p)(n) |+1 | n ∈ ω}.
Proof. This is an application of Kleene's Recursion Theorem. We define a partial function g : ω ω ×ω → ω by g(α, p) := min{m ∈ ω | m < α p} if it exists. Note that g is recursive on its domain and defined on

D := {(α, p) ∈ W O×ω | |α |p | ≥ 1}. We define a map h : ω ω ×ω 3 → ω by h(α, p, n, m) :=    n if m < α n < α p, m otherwise.
Note that h is recursive. This allows us to define a partial function ψ : (ω ω ) 2 ×ω 2 → ω by:

ψ(ε, α, p, n) :=      g(α, p) if n = 0, h[α, p, n-1, {ε} ω ω ×ω 2 ,ω Σ 0 1 (α, p, n-1)] if n ≥ 1.
Note that ψ is recursive on its domain, so that there is ε

* ∈ Σ 0 1 such that {ε * }(α, p, n) = ψ(ε * , α, p, n) if ψ(ε * , α, p, n) is defined. Now it is clear that ψ(ε * , α, p, n) is defined if (α, p) ∈ D, by induction on n, and that |α |p | = sup ↑ {|α |{ε * }(α,p,n) |+1 | n ∈ ω}. We put η(α, p)(n) := {ε * }(α, p, n) if ψ(ε * , α, p, n) is defined.
Clearly, η is defined on D and suitable.

Notation. In the next lemma we identify (ω ω ) ω with ω ω , using the formula Lemma 3.13 There is u : ω ω → ω ω recursive such that (γ) n ∈ BC 1+ηα,p,n for each integer n implies that u(γ) ∈ BC 1+ηα,p and (β,

(δ q ) q∈ω n = δ n . Let α ∈ W O, γ 0 ∈ ω ω ,
δ) ∈ ρ (2 ω ) 2 [u(γ)] ⇔ ∃n ∈ ω [(β) n , δ] / ∈ ρ (2 ω ) 2 [(γ) n ].
Proof. First note that there is

ε 0 ∈ Σ 0 1 with {ε 0 } ω×(2 ω ) 2 ,(2 ω ) 2 (n, β, δ) = [(β) n , δ] for each (n, β, δ) in ω ×(2 ω ) 2 .
Similarly, using Lemmas 3.2 and 3.3, we see that there is

ε 1 ∈ Σ 0 1 such that, for each (γ, n) in ω ω × ω, {ε 1 }(γ, n) = u ω s u ω×(2 ω ) 2 ,(2 ω ) 2 r [(γ) n , ε 0 ], n . We put u(γ) := 1 ⌢ S ω ω ,ω,ω ω Σ 0 1 (ε 1 , γ), so that u is a recursive map. Moreover, {[u(γ)] * }(n) = {ε 1 }(γ, n) = u ω s u ω×(2 ω ) 2 ,(2 ω ) 2 r [(γ) n , ε 0 ]
, n is defined and in BC 1+ηα,p,n , so that u(γ) ∈ BC 1+ηα,p . Finally,

(β, δ) ∈ ρ (2 ω ) 2 [u(γ)] ⇔ ∃n ∈ ω (β, δ) / ∈ ρ (2 ω ) 2 [{[u(γ)] * }(n)] ⇔ ∃n ∈ ω (β, δ) / ∈ ρ (2 ω ) 2 u ω s u ω×(2 ω ) 2 ,(2 ω ) 2 r [(γ) n , ε 0 ], n ⇔ ∃n ∈ ω (n, β, δ) / ∈ ρ ω×(2 ω ) 2 u ω×(2 ω ) 2 ,(2 ω ) 2 r [(γ) n , ε 0 ] ⇔ ∃n ∈ ω [(β) n , δ] / ∈ ρ (2 ω ) 2 [(γ) n ].
This finishes the proof.

Theorem 3.14 Let 1 ≤ ξ < ω CK 1 , and Γ be one of the classes

Σ 0 ξ , Π 0 ξ . Then there is B ξ ∈ Γ (2 ω )\ Γ. Proof. Assume first that Γ = Σ 0 ξ . As in 22.3 in [Kec95] we set (β, δ) ∈ U 2 ω Σ 0 1 ⇔ ∃k ∈ ω β(k) = 0 and δ ∈ N [2 ω , k], so that U 2 ω Σ 0 1 ∈ Σ 0 1 [(2 ω ) 2 ] is universal for Σ 0 1 (2 ω ). We define a recursive bijection ψ : 2 ω → (2 ω ) 2 by ψ i (γ)(k) := γ(2k + i), for i ∈ 2. We set B 1 := ψ -1 (U 2 ω Σ 0 1 ), so that B 1 is Σ 0 1 . As in 22.4 in [Kec95], we see that U 2 ω Σ 0 1 / ∈ Π 0 1 . Thus B 1 / ∈ Π 0 1 since ψ is a homeomorphism.
So we may assume that ξ ≥ 2 and we will generalize this. Write ξ

= 1 + θ, with 1 ≤ θ < ω CK 1 . Let α ∈ W O ∩ Σ 0 1 with θ + 1 = |α|.
α,p ≥ 1, (β, δ) ∈ U 2 ω Σ 0 1+ηα,p ⇔ ∃n ∈ ω [(β) n , δ] / ∈ U 2 ω Σ 0 1+ηα,p,n , so that U 2 ω Σ 0 1+ηα,p is universal for Σ 0 1+ηα,p (2 ω ).
Note the existence of q ∈ ω with η α,q = θ. As before we put

B ξ := ψ -1 (U 2 ω Σ 0 ξ ), so that B ξ is not Π 0 ξ . By Lemma 3.3, it remains to see that U 2 ω Σ 0 1+ηα,p is Σ 0 1+ηα,p . By Theorem 3.7 there is γ 0 ∈ Σ 0 1 ∩ BC 1 such that U 2 ω Σ 0 1 = ρ (2 ω
) 2 (γ 0 ). Lemma 3.13 gives u recursive. We can apply Lemma 3.12, so that γ |α |p | ∈ Σ 0 1 is defined for each p with p ≤ α p. By induction we see that γ ηα,p ∈ BC 1+ηα,p , by Lemma 3.13. Moreover,

(β, δ) ∈ ρ (2 ω ) 2 (γ ηα,p ) ⇔ (β, δ) ∈ ρ (2 ω ) 2 u[(γ ηα,p,n ) n∈ω ] ⇔ ∃n ∈ ω [(β) n , δ] / ∈ ρ (2 ω ) 2 (γ ηα,p,n ).
This inductively shows that ρ

(2 ω ) 2 (γ ηα,p ) = U 2 ω Σ 0 1+ηα,p . Thus U 2 ω Σ 0 1+ηα,p is Σ 0 1+ηα,p . Assume now that Γ = Π 0 ξ . The previous facts give B ξ ∈ Σ 0 ξ (2 ω )\Π 0 ξ . But it is clear that A ξ := ¬B ξ is in Π 0 ξ (2 ω )\Σ 0 ξ . Remark. We can define, for β ∈ 2 ω , ω β 1 := sup{|α| | α ∈ W O ∩ Σ 0 1 (β)}. If X is a recursively presented Polish space, then we can define Σ 0 ξ (β)(X) = {ρ X (γ) | γ ∈ Σ 0 1 (β) ∩ BC ξ }, Π 0 ξ (β) := Σ 0 ξ (β) and also ∆ 0 ξ (β) := Σ 0 ξ (β) ∩ Π 0 ξ (β).
One can check that this definition of Σ 0 1 (β) is equivalent to the one we gave in section 3. The previous proof shows the existence of B ξ ∈ Σ 0 ξ (β)(2 ω )\Π 0 ξ , for 1 ≤ ξ < ω β 1 . Indeed, the only things to change in the proof are the following. In Lemma 3.12, θ < ω β 1 , α ∈ Σ 0 1 (β), f and ψ become Σ 0 1 (β) on their domain by 3D.7, 3G.1 and 3G.2 in [START_REF] Moschovakis | Descriptive Set Theory[END_REF]. Then we can apply 7A.2 in [START_REF] Moschovakis | Descriptive Set Theory[END_REF] to get ε * . The conclusion becomes γ |α |p | ∈ Σ 0 1 (β). The result follows.

4 Effective versions of Kuratowski's theorem.

Notation. Let ξ < ω 1 . Then ξ -1 will denote the predecessor of ξ if it exists, ξ otherwise. We also define ξ -:= ξ -1 if ξ ≥ 3, ξ otherwise.

Theorem 4.1 Let a ∈ 2. There is a partial function F a : ω ω → (ω ω ) 3 , recursive on its domain, such that (a) For each 1 ≤ ξ ≤ 2 and for each γ ∈ BC ξ , coding

B := ¬ρ 2 ω (γ) ∈ Π 0 ξ , F 0 (γ) is defined and (1) F 0 0 (γ) ∈ BC 1 (codes C := ¬ρ ω ω [F 0 0 (γ)] ∈ Π 0 1 ). (2) f := {F 0 1 (γ)} ω ω ,2 ω |C defines a continuous bijection from C onto B.
(3) F 0 2 (γ) ∈ BC 1 codes an open set computing a partial function g : 2 ω → ω ω , defined and continuous on B, which coincides with f -1 .

We define P ⊆ 2 ω ×ω by

(α, k) ∈ P ⇔ α ∈ N (2 ω , k) and ∀j < µ(k) (k) 1 0 j < 2 .
As P is Σ 0 1 , there is ε 0 ∈ Σ 0 1 ∩ BC 1 with P = ρ 2 ω ×ω (ε 0 ), by Theorem 3.7. We put F a 2 (γ) := ε 0 if γ ∈ BC 1 , so that F a 2 (γ) codes P computing the canonical injection from 2 ω into ω ω since if α ∈ 2 ω , then we have α ∈ N (ω ω , k) ⇔ P (α, k). So we are done if γ ∈ BC 1 .

• For the general case, we give the classical scheme of the construction before getting into the effective details, to make things easier to understand. So let B ∈ Π 0 ξ . There is (B i ) i∈ω ⊆ 1≤η<ξ Π 0 η such that B = i∈ω ¬B i . Using Lemma 3.10 we will find (B i,j ) i,j∈ω ⊆ 1≤η<ξ ∆ 0 η with ¬B i =

• j∈ω B i,j . We will argue by induction on ξ, so that we will get C i,j ∈ Π 0 1 (ω ω ), f i,j : C i,j → B i,j , and g i,j := f -1 i,j . The objects we are looking for will be the following:

C := δ ∈ ω ω | ∀i ∈ ω [(δ) i ] * ∈ C i,(δ) i (0) and f i,(δ) i (0) [(δ) i ] * = f 0,(δ) 0 (0) [(δ) 0 ] * , f (δ) := f 0,(δ) 0 (0) [(δ) 0 ] * . To define g, we define h : B → ω ω by h(α)(i) := min{j ∈ ω | α ∈ B i,j }. Note that h(α)(i)
is also the unique integer j satisfying α ∈ B i,j . We will have g(α)

i := h(α)(i) ⌢ g i,h(α)(i) (α). • We set (ξ, γ) ∈ Q ⇔ ξ ≥ 2 and γ ∈ BC ξ , (ξ, γ, ε) ∈ Q + ⇔ (ξ, γ) ∈ Q and {ε} ω ω ,(ω ω ) 3 2 (δ) is defined and in BC for each δ ∈ 1≤η<ξ BC η , (ξ, γ, ε, α) ∈ Q ++ ⇔ (ξ, γ, ε) ∈ Q + and α ∈ B.
Assume that (ξ, γ) ∈ Q and γ codes B, so that {γ * }(i) is defined for each integer i, and in BC η i for some 1 ≤ η i < ξ. Using Lemma 3.10, we set γ i,j := u 2 ω d [{γ * }(i)] * (j) for each j. Note that γ i,j is recursive in (γ, i, j), γ i,j ∈ BC 1 if {γ * }(i) ∈ BC 1 , and γ i,j ∈ 1≤η<η i BC η if {γ * }(i) ∈ BC * . We also have B i,j = 2 ω \ρ 2 ω (γ i,j ).

The map F a will be obtained by Kleene's Recursion Theorem, so that, for some suitable ε a , we will have F a (γ) = ϕ a (ε a , γ) = {ε a } ω ω ,(ω ω ) 3 (γ). In order to describe ¬C, we define R ∈ Σ 0 1 [(ω ω ) 3 ] as follows:

(ε, γ, δ) ∈ R ⇔ ∃i ∈ ω ∃j ∈ ω [(δ) i ] * ∈ N ω ω , [{ε} ω ω ,(ω ω ) 3 0 (γ i,(δ) i (0) )] * (j) or {ε} ω ω ,(ω ω ) 3 1 (γ i,(δ) i (0) ) ω ω ,2 ω [(δ) i ] * = {ε} ω ω ,(ω ω ) 3 1 (γ 0,(δ) 0 (0) ) ω ω ,2 ω [(δ) 0 ] * .
By 3C.4 and 3C.5 in [START_REF] Moschovakis | Descriptive Set Theory[END_REF], there is

R * ∈ ∆ 0 1 [(ω ω ) 2 ×ω 2 ] with (ε, γ, δ) ∈ R ⇔ ∃i ∈ ω δ ∈ N [ω ω , (i) 0 ] and [ε, γ, (i) 0 , (i) 1 ] ∈ R *
(the idea is that an open subset of (ω ω ) 3 is a countable union of clopen sets)

We define a map ψ 0 : (ω ω ) 2 → ω ω by

ψ 0 (ε, γ)(i) :=    (i) 0 if [ε, γ, (i) 0 , (i) 1 ] ∈ R * , 0 otherwise.
Clearly, ψ 0 is recursive and (ε, γ, δ) ∈ R ⇔ ∃i ∈ ω δ ∈ N [ω ω , ψ 0 (ε, γ)(i)]. We define a recursive map ϕ 0 by ϕ 0 (ε, γ) := 0 ⌢ ψ 0 (ε, γ). Note that ϕ 0 (ε, γ) ∈ BC 1 (we will have F a 0 (γ) = ϕ 0 (ε a , γ), for ε a suitable, if γ ∈ BC * ).

• We define a partial function ψ 1 : (ω ω ) 3 → 2 ω by ψ 1 (ε, γ, δ) := {ε} ω ω ,(ω ω ) 3 1 (γ 0,(δ) 0 (0) )

ω ω ,2 ω [(δ) 0 ] * .
As ψ 1 is recursive on its domain, there is ε 1 ∈ Σ 0 1 such that ψ 1 (ε, γ, δ) = {ε 1 } (ω ω ) 3 ,2 ω (ε, γ, δ) if ψ 1 (ε, γ, δ) is defined. We put ϕ 1 (ε, γ) := S (ω ω ) 2 ,ω ω ,2 ω Σ 0 1 (ε 1 , ε, γ), so that ψ 1 (ε, γ, δ) is equal to {ϕ 1 (ε, γ)} ω ω ,2 ω (δ) when it is defined. Note that ϕ 1 is a total recursive map.

• Now we have to describe ϕ a 2 (ε, γ) coding a set computing g. By the proof of 3C.3 in [START_REF] Moschovakis | Descriptive Set Theory[END_REF] there are recursive maps g ′ : ω → ω and h ′ : ω 2 → ω such that, for each (δ, j, k) ∈ ω ω ×ω 2 , δ(j) = k ⇔ ∃i ∈ ω [δ ∈ N (ω ω , i) and j < g ′ (i) and h ′ (i, j) = k].

We set k j := (k) 1 0 j . We have, for α ∈ B, = 0 and ∀j < µ(k) (j) 1 = 0 and α ∈ B (j) 0 ,k j or (j) 1 > 0 and ∃i ∈ ω g (j) 0 ,h(α)[(j) 0 ] (α) ∈ N (ω ω , i) and (j) 1 ≤ g ′ (i) and h ′ [i, (j) 1 -1] = k j .

But α ∈ B (j) 0 ,k j ⇔ α / ∈ ρ 2 ω (γ (j) 0 ,k j ) ⇔ ∃l ∈ ω [k j = l and α / ∈ ρ 2 ω (γ (j) 0 ,l )]. There is δ 1 ∈ Σ 0 1 such that {δ 1 } 2 ω ×ω,2 ω (α, k) = α if (α, k) ∈ 2 ω × ω. We will code the relation " R0 (α, k) ⇔ α ∈ B (j) 0 ,l ", via a partial function g0 : ω ω ×ω 2 → ω ω .

If {γ * }[(j) 0 ](0) = 0, then by Lemmas 3.10 and 3. This shows the existence of a partial function g0 : ω ω ×ω 2 → ω ω , recursive on its domain, such that g0 (γ, j, l) is defined if (ξ, γ) ∈ Q. In this case, g0 (γ, j, l) ∈ BC 1 if {γ * }[(j) 0 ] ∈ BC 1 , g0 (γ, j, l) ∈ BC η (j) 0 if {γ * }[(j) 0 ] ∈ BC * , and α ∈ B (j) 0 ,l ⇔ α / ∈ ρ 2 ω (γ (j) 0 ,l ) ⇔ (α, k) ∈ ρ 2 ω ×ω [g 0 (γ, j, l)].

Similarly, we now code the relation "R 0 (α, k) ⇔ α ∈ B (j) 0 ,k j ", via a partial function g 0 : ω ω × ω → ω ω . Choose γ 1 ∈ Σ 0 1 ∩ BC 1 such that (α, k, j, l) ∈ ρ 2 ω ×ω 3 (γ 1 ) ⇔ k j = l. Using Lemma 3.2 we see that u ω 2 s (γ 1 , j, l) ∈ BC 1 and (α, k) ∈ ρ 2 ω ×ω [u ω 2 s (γ 1 , j, l)] ⇔ k j = l, for each (α, k, j, l) ∈ 2 ω × ω 3 . Using Lemmas 3.5 and 3.6.(b), we get the existence of a partial function g 0 : ω ω × ω → ω ω , recursive on its domain, such that g 0 (γ, j) is defined if (ξ, γ) ∈ Q. In this case, g 0 (γ, j) ∈ BC 1 if {γ * }[(j) 0 ] ∈ BC 1 , and g 0 (γ, j) ∈ BC η (j) 0 if {γ * }[(j) 0 ] ∈ BC * . If moreover α ∈ B, then α ∈ B (j) 0 ,k j ⇔ (α, k) ∈ ρ 2 ω ×ω [g 0 (γ, j)].

-Similarly, we now deal with the end of the computation of the relation "g(α) ∈ N (ω ω , k)" above. We will have g (j) 0 ,h(α)[(j) 0 ] (α) ∈ N (ω ω , i) ⇔ (α, i) ∈ ρ 2 ω ×ω [{ε} ω ω ,(ω ω ) 3 2 (γ (j) 0 ,h(α)[(j) 0 ] )] ⇔ ∃l ∈ ω (α, i) ∈ ρ 2 ω ×ω [{ε} ω ω ,(ω ω ) 3 2 (γ (j) 0 ,l )] and h(α)[(j) 0 ] = l ⇔ ∃l ∈ ω (α, i) ∈ ρ 2 ω ×ω [{ε} ω ω ,(ω ω ) 3 2 (γ (j) 0 ,l )] and α ∈ B (j) 0 ,l if (ξ, γ, ε, α) ∈ Q ++ . If we apply Lemmas 3.5 and 3.6.(a), then we obtain the existence of a partial function g 0 1 : (ω ω ) 2 ×ω 2 → ω ω , recursive on its domain, such that g 0 1 (ε, γ, j, l) is defined and in BC if (ξ, γ, ε) ∈ Q + , in which case (α, k) ∈ ρ 2 ω ×ω [g 0 1 (ε, γ, j, l)] is equivalent to ∃i ∈ ω (α, i) ∈ ρ 2 ω ×ω [{ε} ω ω ,(ω ω ) 3 2 (γ (j) 0 ,l )] and (j) 1 ≤ g ′ (i) and h ′ [i, (j) 1 -1] = k j . Now we show that µ ∞ is "simple".

Lemma 5.2

The set µ ∞ is Π 0 2 (4 ω ).

Proof. We have γ ∈ µ ∞ ⇔ ∃i ∈ 2 ∀j ∈ ω ∃k ∈ ω ∃t ∈ (µ i ) <ω |t| ≥ j and γ ↾ k = ⌢ l<|t| t(l).

This shows that µ ∞ ∈ Π 0 2 (4 ω ), by Lemma 5.1, since t can be coded by an integer, and the restriction and concatenation maps are recursive. Proof. The map h : ω ×2 ω → 2 ω defined by h(N, α) := q 1 N α is clearly recursive. From this we deduce that E is in Γ , using Lemmas 3.3 and 3.5.

Notation. Now we code the maps ϕ N,j . We set Dom := {(N, j, γ) ∈ ω 2 × 4 ω | N ≤ M j and γ ∈ K N,j }. We define a partial function φ : ω 2 ×4 ω → 2 ω as follows: φ(N, j, γ) is defined if (N, j, γ) ∈ Dom, and its coordinates are the coordinates of γ in 2, in the same order as in γ (we forget the 2's and the 3's).

In the next lemma we consider the set expressing the fact that "π ∞ will look like B on K N,j ".

Lemma 5.4 The set

F := {(N, j, γ) ∈ Dom | φ(N, j, γ) ∈ E N } is in Γ if ξ ≥ 2.
Proof. We define a map ψ : 2 ω ×ω 2 → 4 ω by ψ(α, N, j) := 2 N α(0) ⌢ [ ⌢ k∈ω 2 M (j+k+1) 3 2 M (j+k+1) α(k+1) ] if N ≤ M (j), 0 ∞ if N > M (j).

It is easy to see that ψ is recursive. If N ≤ M j and γ ∈ 4 ω , then γ ∈ K N,j is equivalent to ∀i ∈ ω [ ψ(0 ∞ , N, j)(i) = 0 and γ(i) ∈ 2 ] or [ ψ(0 ∞ , N, j)(i) = 0 and γ(i) = ψ(0 ∞ , N, j)(i) ].

This shows that Dom ∈ Π 0 1 . Then φ is clearly recursive on Dom. This shows that F is in Γ if ξ ≥ 2, by Lemmas 3.3, 3.5 and 5.3. Now we describe the elements of A ∞ \µ ∞ .

Notation. Recall that P t,S,j := γ ∈ 4 ω | t 2 S ≺ γ and γ -t 2 S ∈ K 0,j . Note that the relation defined by "γ ∈ P t,S,j " is Π 0 1 in γ, t, S, j. Let (t, S, j) be suitable and N ≤ min(M j , S) (N = S if t = ∅). Note that (N, j, γ -t 2 S-N ) ∈ F means that γ -t 2 S-N ∈ π ∞ ∩ K N,j . This implies that A t,S,j,N = γ ∈ P t,S,j | (N, j, γ -t 2 S-N ) ∈ F . Lemma 5.5 The set of (γ, t, S, j, N ) ∈ 4 ω ×({∅} ∪ µ)×ω 3 such that (t, S, j) is suitable, N ≤ min[M (j), S], N = S if t = ∅ and γ ∈ A t,S,j,N can be coded by a set in Γ (4 ω ×ω 4 ) if ξ ≥ 2.

Proof. Apply Lemmas 3.3, 3.5 and 5.4.

  and u : ω ω → ω ω a map. Using Lemma 3.11 we can define, by induction on p (with respect to the wellordering ≤ α ), and if|α |p | ≥ 1, γ |α |p | := u[(γ |α |η(α,p)(n) | ) n∈ω ]. The next lemma expresses the fact that γ |α |p | is recursive if the datas are recursive. Lemma 3.12 Let θ < ω CK 1 , α ∈ W O ∩ Σ 0 1 with θ+1 = |α|, γ 0 ∈ Σ 0 1 , u : ω ω → ω ω a recursive map, and p ∈ ω such that p ≤ α p. Then γ |α |p | is Σ 0 1 .Proof. Once again, this is an application of Kleene's Recursion Theorem. Fix p 0 ∈ ω with |α |p 0 | = 0. Using Lemma 3.11, we define a partial function f :ω ω ×ω → ω ω by f (ε, p) := u {ε}[η(α, p)(n)] n∈ω . Notethat f is recursive on its domain. We define a partial function ψ :ω ω ×ω → ω ω by ψ(ε, p) :=    γ 0 if p = p 0 , f (ε, p) if p = p 0 .As ψ is recursive on its domain, there isε * ∈ Σ 0 1 with {ε * }(p) = ψ(ε * , p) if ψ(ε * , p) is defined. It remains to see that ψ(ε * , p)is defined and equal to γ |α |p | if p ≤ α p. We argue by induction on p (with respect to the wellordering ≤ α ). If p = p 0 , then ψ(ε * , p) = γ 0 = γ |α |p 0 | = γ |α |p | . Assume now that |α |p | ≥ 1, and that the statement is proved for q satisfying |α |q | < |α |p |. Then ψ[ε * , η(α, p)(n)] is defined and equal to γ |α |η(α,p)(n) | for each n ∈ ω. It is also equal to {ε * }[η(α, p)(n)]. Thus f (ε * , p) is defined and equal to u[(γ |α |η(α,p)(n) | ) n∈ω ] = γ |α |p | . Notation. In the next lemma, α ∈ W O and we study the formula building universal sets for the additive Borel classes. We set η α,p := |α |p |, and η α,p,n := |α |η(α,p)(n) | if |α |p | ≥ 1.

1 = 0 1 = 0

 1010 g(α) ∈ N (ω ω , k) ⇔ (k) 1 1 = 0 and ∀j < µ(k) g(α)(j) = k j ⇔ (k) 1 and ∀j < µ(k) [g(α)] (j) 0 [(j) 1 ] = k j ⇔ (k) 1 and ∀j < µ(k) (j) 1 = 0 and h(α)[(j) 0 ] = k j or (j) 1 > 0 and g (j) 0 ,h(α)[(j) 0 ] (α)[(j) 1 -1] = k j ⇔ (k) 1 1

  3 we get α / ∈ ρ 2 ω (γ (j) 0 ,l ) ⇔ α ∈ ρ 2 ω u 2 ω c {γ * }[(j) 0 ], l ⇔ (α, k) ∈ ρ 2 ω ×ω u 2 ω ×ω,2 ω r u 2 ω c {γ * }[(j) 0 ], l , δ 1 .If {γ * }[(j) 0 ](0) = 0, then by Lemmas 3.3 and 3.1 we getα / ∈ ρ 2 ω (γ (j) 0 ,l ) ⇔ (α, k) / ∈ ρ 2 ω ×ω [u 2 ω ×ω,2 ω r (γ (j) 0 ,l , δ 1 )] ⇔ (α, k) ∈ ρ 2 ω ×ω u ¬ [u 2 ω ×ω,2 ω r(γ (j) 0 ,l , δ 1 )] .

Notation.

  We define a partial function c :2 ω ×ω → Q on B ×ω by c(α, l) := [g(α), α] ↾ l. Lemma 5.3 The set E := {(N, α) ∈ ω×2 ω | α ∈ E N } is in Γ .

  Using the previous notation, we get η α,p = sup ↑ {η α,p,n + 1 | n ∈ ω} if η α,p ≥ 1, by Lemma 3.11. As in 22.3 in [Kec95] again we inductively define, if η

-hard. As Σ ξ is Π 1 1 , it is Π 1 1 -complete.We argue similarly for Π ξ .

Acknowledgements. We would like to thank J. Saint Raymond for allowing us to present here one of his results (see Theorem 6.3), and the referee for valuable comments on a first version of this paper.

(b) For each 1 ≤ ξ < ω 1 and for each γ ∈ BC ξ , coding B := ¬ρ 2 ω (γ) ∈ Π 0 ξ , F 1 (γ) is defined and

(1) F 1 0 (γ) ∈ BC 1 (codes C := ¬ρ ω ω [F 1 0 (γ)] ∈ Π 0 1 ).

(2) f := {F 1 1 (γ)} ω ω ,2 ω |C defines a continuous bijection from C onto B.

(3) F 1 2 (γ) ∈ BC ξ -codes a Σ 0 ξ -set computing a partial function g : 2 ω → ω ω , defined and Σ 0 ξ --measurable on B, which coincides with f -1 .

Proof. Let us look at the case where ξ = 1 first. We define µ : ω → ω by

Clearly µ is recursive. Let us recall, for each k ∈ ω, the definition of the basic neighborhood:

In 3A.2 in [START_REF] Moschovakis | Descriptive Set Theory[END_REF] the recursive map sg : ω → ω is defined by sg(n) := 0 if n = 0, 1 otherwise. The recursive presentation of 2 ω ensures that

We view 2 ω as a subset of ω ω . We denote by Id 2 ω the partial function defined on 2 ω ⊆ ω ω , with values in 2 ω , by Id 2 ω (α) := α. It is recursive on 2 ω , since the relation "α ∈ N (2 ω , k)" is Σ 0 1 (ω ω ×ω) on 2 ω ×ω. Thus there is δ 0 ∈ Σ 0 1 with {δ 0 } ω ω ,2 ω (α) = Id 2 ω (α) for each α ∈ 2 ω . By Lemma 3.3 we have u ω ω ,2 ω r (γ, δ 0 ) ∈ BC 1 and α ∈ ρ ω ω [u ω ω ,2 ω r (γ, δ 0 )] ⇔ α ∈ ρ 2 ω (γ) if γ ∈ BC 1 and α ∈ 2 ω . As 2 ω ∈ Π 0 1 (ω ω ), there is γ 0 ∈ Σ 0 1 ∩ BC 1 with 2 ω = ¬ρ ω ω (γ 0 ), by Theorem 3.7. We define a recursive map f : ω ω → ω ω by f (γ)

If γ ∈ BC 1 , then using Lemma 3.5 we set F a 0 (γ) := u ω ω f [1, 1, f (γ)], so that F a 0 (γ) ∈ BC 1 and also 2 ω \ρ 2 ω (γ) = ¬ρ ω ω [F a 0 (γ)] since

Thus B = 2 ω \ρ 2 ω (γ) ∈ Π 0 1 (2 ω ), and C = B. We set

But g 0 1 (ε, γ, j, l) could be in BC 1 for some l's, and in BC * for some others. This may happen if ξ ≥ 3. This is a problem since we want to apply Lemma 3.6.(b). We will solve this problem with Lemma 3.4. We define a partial function

it satisfies the previous properties of g 0 1 .

-Lemmas 3.5 and 3.6.(b) imply the existence of a partial function

We also define a partial function g 0 2 : (ω ω ) 2 ×ω → ω ω . It is defined relatively to g 0 1 exactly like g 1 2 was defined relatively to g 1 1 . It will satisfy the previous properties of g 1 2 if ξ = 2, and we will have, for

-We define a partial function g 1 3 : (ω ω ) 2 ×ω → ω ω by

3 is recursive on its domain, and g 1 3 (ε, γ, j) is defined and in BC if (ξ, γ, ε) ∈ Q + . We also define a partial function g 0 3 : (ω ω ) 2 × ω → ω ω . It is defined relatively to g 0 2 , like g 1 3 was defined relatively to g 1 2 , except that g 0 3 (ε, γ, j) := g 0 (γ, j) if (j) 1 = 0. The function g 0 3 will satisfy the previous properties of g 1 3 if ξ = 2.

-By Lemma 3.5, we get the existence of a partial function g 1 4 : (ω ω ) 2 × ω → ω ω , recursive on its domain, such that g 1 4 (ε, γ, m) is defined and in BC if (ξ, γ, ε)

Thus (ξ, γ, ε, α) ∈ Q ++ will imply that

We also define a partial function g 0 4 : (ω ω ) 2 ×ω → ω ω . It is defined relatively to g 0 3 exactly like g 1 4 was defined relatively to g 1 3 . It will satisfy the previous properties of g 1 4 if ξ = 2.

-By Lemma 3.6.(b), we get the existence of a partial function ϕ 1 2 : (ω ω ) 2 → ω ω , recursive on its domain, such that ϕ 1 2 (ε, γ) is defined and in BC if (ξ, γ, ε) ∈ Q + , and

We also define a partial function ϕ 0 2 : (ω ω ) 2 → ω ω . It is defined relatively to g 0 4 exactly the way ϕ 1 2 was defined relatively to g 1 4 . It will satisfy the previous properties of ϕ 1 2 if ξ = 2.

• Now we can define a partial function ϕ a : (ω ω ) 2 → (ω ω ) 3 by

As ϕ a is recursive on its domain, by Kleene's Recursion Theorem there is ε a ∈ Σ 0 1 such that

if ϕ a (ε a , γ) is defined. We define a partial function F a : ω ω → (ω ω ) 3 by F a (γ) := {ε a } ω ω ,(ω ω ) 3 (γ), so that F a is recursive on its domain. We already checked that

So assume that 2 ≤ ξ < ω 1 , and γ ∈ BC ξ codes B := ¬ρ 2 ω (γ) ∈ Π 0 ξ . We will prove that F a (γ) is defined and fullfills the required properties by induction on ξ.

Note that {ε a } ω ω ,(ω ω ) 3 2 (δ) is defined and in BC for each δ ∈ 1≤η<ξ BC η , by induction assumption. This implies that (ξ, γ, ε a ) ∈ Q + , ϕ a 2 (ε a , γ) and F a (γ) are defined, and

(1) Note that

(2) We have F a 1 (γ) = ϕ 1 (ε a , γ), so that, by induction assumption, and for each δ ∈ C,

, and δ = δ ′ . This shows that f is one-to-one. If α ∈ B and i ∈ ω, then there is a unique integer j i with α ∈ B i,j i . There is

-If ξ = 2, then η i = 1 for each i, γ i,j ∈ BC 1 for each (i, j). Thus

This shows that g coincides with f -1 .

Proof of Theorem 1.5. Let γ ∈ Σ 0 1 ∩ BC ξ+1 with B = ¬ρ 2 ω (γ). By Theorem 4.1,

1 and the same conclusion holds.

We also have a ∆ 1 1 version of Theorem 1.5: Theorem 4.2 Let ξ ≥ 1 be a countable ordinal, and

Actually, Louveau does not use the coding for Borel sets that we use here, but he proves this specific result, with this coding, in his notes [Lou??]. So let γ ∈ ∆ 1 1 ∩ BC ξ+1 with B = ¬ρ 2 ω (γ). By Theorem 4.1,

, f and g are partial ∆ 1 1 functions on ∆ 1 1 sets, and can be extended to total ∆ 1 1 maps.

• If ξ ≥ 2, then F 1 (γ) ∈ ∆ 1 1 and the same conclusion holds.

5 Proof of Theorem 1.3.

The proof of Theorem 1.3.( 2) is essentially identical to that of Theorem 1.3.(1), so it is enough to prove Theorem 1.3.(1) to get Theorem 1.3. In the sequel we will assume that ξ < ω CK 1 , except where indicated. Let us indicate the specifications of the proof of Theorem 1.2 that we need. Theorem 3.14 gives B ∈ Γ (2 ω )\ Γ. As B ∈ Π 0 ξ+1 , Theorem 1.5 gives C, f and g. Here again, the dictionary A will be made of two pieces: we will have

Implicitely, we have used the bijection I : Q → Q defined by I(s, t) := < s(0), t(0) > , . . . , < s(|s|-1), t(|s|-1) > .

Note that the map χ : ω → ω defined by χ(r) := I(q r ) is a recursive injection with range Q. We define a recursive map M : ω → ω by M (j) := M j := Σ i<j 4 i+1 . Lemma 5.1 The sets µ 0 , µ 1 and µ can be coded by recursive subsets of ω.

Proof. We define a recursive map Exp : ω 2 → ω coding the finite sequence k j : Exp(k, j) := c ⇔ Seq(c) and lh(c) = j and ∀i < j (c) i = k.

Using Exp, it is easy to build a recursive map f : ω 5 → ω such that f (N, l, m, P, R) codes the sequence

Then we just have to use bounded quantifiers.

Let us specify a few facts about the definition of π.

Notation. As C is Π 0 1 and f is recursive on C, the graph Gr(f ) of f is a Π 0 1 subset of ω ω × 2 ω . As the identity from 2 ω , viewed as a subset of ω ω , into 2 ω is a partial recursive function on 2 ω (see the proof of Theorem 4.1), we can also say that Gr(f ) is a Π 0 1 subset of ω ω ×ω ω , by Lemma 3.3. By 4A.1 in [START_REF] Moschovakis | Descriptive Set Theory[END_REF], there is

recall that t is defined at the beginning of section 3).

• We set Q f := {(t, s) ∈ Q | (t, s) ∈ R and t = ∅ and t(|t|-1) = 1}. Note that Q f can easily be coded by a recursive subset of ω.

• The definition of π is the same as the one in section 2. Here again, π can easily be coded by a recursive subset of ω.

Proof of Theorem 1.3.(1).

We refer to the proof of Theorem 1.2. We put A := µ ∪ π, so that A can be coded by a ∆ 0 1 subset of ω. We will prove that A ∞ ∈ Γ \ Γ.

• Here again we have ϕ

• We also have

As Γ is uniformly closed under finite unions, the set of (γ, t, S, j) ∈ 4 ω ×({∅} ∪ µ)×ω 2 such that (t, S, j) is suitable and γ ∈ A t,S,j can be coded by a set in Γ (4 ω ×ω 3 ) if ξ ≥ 2, by Lemma 5.5.

• By Lemmas 3.5, 3.6 and 5.2, we get A ∞ ∈ Γ (4 ω ) if ξ ≥ 3 and Γ = Σ 0 ξ .

• If ξ ≥ 3 and Γ = Π 0 ξ , then we can write

A t,S,j ∩ P t,S,j .

Thus

Here ¬ µ ∞ ∪ (t,S,j) suitable P t,S,j ∈ ∆ 0 3 (4 ω ) ⊆ Γ (4 ω ). By Lemma 3.6, (t,S,j) suitable P t,S,j \A t,S,j is in Γ (4 ω ), and by Lemma 3.5 ¬A ∞ is in Γ (4 ω ). Thus A ∞ ∈ Γ (4 ω ).

• If 1 ≤ ξ ≤ 2, then we argue as in the proof of Theorem 1.2.

On the complexity of some sets of dictionaries.

The proof of Theorem 1.3 has the following consequence on the complexity of the sets Σ ξ and Π ξ defined in the introduction. Recall that if 1 ≤ ξ < ω 1 , then

Notation. We set

So Σ ξ (resp., Π ξ ) is more complicated than the set of Borel codes for Σ 0 ξ (resp., Π 0 ξ ) sets, on BC, if ξ ≥ 3.

Proof. Theorem 4.1 gives a partial function F 1 . Recall that F 1 1 (γ) codes a bijection defined on a closed subset of ω ω if γ ∈ BC. We now express the fact that its graph is a closed subset of ω ω ×ω ω (see the notation after Lemma 5.5). In Theorem 4.1, the complement of ρ 2 ω (γ) is involved. This leads us to use the map u ¬ given by Lemma 3.1. There is

(see the notation after Lemma 5.5).

We say that (t, s) ∈ Qf if (t, s) ∈ Q, [γ, t, s] ∈ R, t = ∅ and t(|t|-1) = 1 (we use again the definition of Q f after Lemma 5.5, but here it is uniform in γ). Now we define π as we did in section 2, with "q p l ∈ Qf " instead of "q p l ∈ Q f ". After a coding of 4 <ω with ω, we can define a recursive map φ : ω ω → 2 ω coding µ ∪ π ⊆ 4 <ω (we will identify φ(γ) with µ ∪ π, identifying ω with 4 <ω ; the notation φ instead of ϕ is for ω in the range of φ instead of 2 <ω in the range of ϕ).

Proof. (a) Let γ 0 ∈ BC such that B = ρ (2 ω ) 2 (γ 0 ). By Lemma 3.2, we get ρ (2 ω ) 2 (γ 0 ) α = ρ 2 ω [u 2 ω s (γ 0 , α)] for each α ∈ 2 ω . So we just have to set ψ(α) := ϕ[u 2 ω s (γ 0 , α)], using Corollary 6.1.

(b) The proof is similar.

We argue similarly for Π B ξ .

Remarks. (a)

We actually proved that if ξ ≥ 3 and

(b) This proof also shows that if

(c) This proof also shows that if

Proof. We just have to apply Theorem 6.3 and Corollary 6.2.

Remark.

Recall that if X is a recursively presented Polish space and β ∈ 2 ω , then

In [START_REF] Lecomte | Omega-Powers and Descriptive Set Theory[END_REF], the following sets are introduced:

Under the axiom of Σ 1 1 -determinacy, this implies that they are Π 1 1 -complete. Here we can say more: they are Π 1 1 -complete if ξ ≥ 3, without any axiom of determinacy. Indeed, fix a Π 1 1 -complete set Π ⊆ 2 ω . The proof of Theorem 6.3 gives

s (γ 0 , α)] = ∅, and the proof of Theorem 1.3.(1) shows that

) and Σ ξ is Π 1 Definition 6.5 Let Γ be a class, and U 2 ω Γ ⊆ (2 ω ) 2 universal for Γ(2 ω ). We say that U 2 ω Γ is a good universal for Γ if for each set U

for each (α, β, γ) ∈ (2 ω ) 3 . Proposition 6.6 Let 1 ≤ ξ < ω 1 . Then there are good universals for Σ 0 ξ , Π 0 ξ , Σ 1 1 and Π 1 1 .

Proof. Let Γ be one of the classes of the statement, and V

We define, for α ∈ 2 ω and ε ∈ 2, (α) ε ∈ 2 ω by (α) ε (n) := α(2n+ε). We set

) α . We define < ., . >:

and

So we just have to set S(α, β) := α 0 , < α, β > . Lemma 6.7 We consider the good universal U 2 ω Σ 1 1 for Σ 1 1 given by Proposition 6.6. Then there is a continuous map c : 2

) and defined in the proof of Theorem 3.14 as follows:

Similarly, we can define

Using this, we can define

By [START_REF] Lecomte | Omega-Powers and Descriptive Set Theory[END_REF] there is a continuous map π : 2 ω ×ω ω ×ω → 2 <ω such that

for each α ∈ 2 ω and A ⊆ 2 <ω . We define R ∈ Σ 0 1 (2 ω ×ω ω ×2 2 <ω ) by

We define d : 2

is a good universal, we get S continuous, and

Corollary 6.8 Let 3 ≤ ξ < ω 1 . We consider the good universals given by Proposition 6.6.

2 -hard and Σ 1 3 \Σ 1 2 . (b) The set U(Σ 0 ξ , Π 0 ξ ) is Π 1 1 -complete, U(Σ 0 ξ , Π 0 ξ ) ≤ W Π ξ < W U(Σ 1 1 , Π 0 ξ ), and the set U(Σ 1 1 , Π 0 ξ ) is Π 1 2 -hard and Σ 1 3 \Σ 1 2 . (c) ∆ < W U(Σ 1 1 , ∆ 1 1 ), and the set U(Σ 1 1 , ∆ 1 1 ) is Π 1 2 -hard and Σ 1 3 \Σ 1 2 . Moreover, the set U(Σ 1 1 , ∆ 1 1 ) is Π 1 2 -complete.

Proof. (a) By Theorem 6.3 and Remark (a) just after, there is M ∈ Π 0 ξ [(2 ω ) 2 ] such that Σ M ξ is Π 1 1 -complete. Fix α 0 ∈ 2 ω with M = (U (2 ω ) 2 Π 0 ξ ) α 0 . We define f : 2 ω → 2 ω by f (α) := S(α 0 , α), where S is provided by the fact that U 2 ω Π 0 ξ is a good universal. Then we get Σ M ξ = f -1 (U(Π 0 ξ , Σ 0 ξ )), which proves that U(Π 0 ξ , Σ 0 ξ ) is Π 1 1 -hard. By [START_REF] Louveau | A Separation Theorem for Σ 1 1 Sets[END_REF] (or 35.H in [START_REF] Kechris | Classical Descriptive Set Theory[END_REF]), U(Π 0 ξ , Σ 0 ξ ) is Π 1 1 , so it is Π 1 1 -complete.

By Corollary 6.2, we get U(Π 0 ξ , Σ 0 ξ ) ≤ W Σ ξ since

By Lemma 6.7 we get Σ ξ ≤ W U(Σ 1 1 , Σ 0 ξ ). Remark (b) after Theorem 6.3 gives Σ := ¬A ∈ Σ 1 1 [(2 ω ) 2 ] such that Σ Σ ξ is Π 1 2 -complete. The beginning of the proof shows that U(Σ 1 1 , Σ 0 ξ ) is Π 1 2 -hard. In particular, U(Σ 1 1 , Σ 0 ξ ) / ∈ Σ 1 2 , and

(b) The proof is very similar to that of (a).

(c) The proof of the first sentence is very similar to that of (a), using Remark (c) after Theorem 6.3. This proof shows that U(Σ 1 1 , ∆ 1 1 ) is Π 1 2 -hard. It remains to see that

(see Theorem 3.3.1 in [START_REF] Harrington | A Glimm-Effros dichotomy for Borel equivalence relations[END_REF]). This implies that

Thus U(Σ 1 1 , ∆ 1 1 ) is Π 1 2 , and Π 1 2 -complete.


domain: spi phys

text:
Oleg Baranov

Kateryna Bazaka

Thierry Belmonte

Claudia Riccardi

H Eduardo Roman

Mandhakini Mohandas

Shuyan Xu

Uroš Cvelbar

Igor Levchenko

Recent innovations in the technology and applications of low-dimensional CuO nanostructures for sensing, energy and catalysis

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.