EFFECTIVE REFINING OF BOREL COVERINGS

by Gabriel DEBS and Jean SAINT RAYMOND

Abstract : Given a countable family (Γ_{i})_{i∈I} of additive or multiplicative Baire classes (Γ_{i} = Σ_{ξ_{i}}^{0} or Π_{ξ_{i}}^{0}) we investigate the following complexity problem : Let (A_{i})_{i∈I} be a Borel covering of ω^{ω} and assume that there exists some covering (B_{i})_{i∈I} with B_{i} ⊂ A_{i} and B_{i} ∈ Γ_{i} for all i; can one find such a family (B_{i})_{i∈I} in Δ_{1}^{1}(α) where α ∈ ω^{ω} is any reasonable code for the families (A_{i})_{i∈I} and (Γ_{i})_{i∈I} ? The main result of the paper will give a full characterization of those families (Γ_{i})_{i∈I} for which the answer is positive. For example we will show that this is the case if I is finite or if all the Baire classes Γ_{i} are additive ; but in the general case the answer depends on the distribution of the multiplicative Baire classes inside the family (Γ_{i})_{i∈I}.

2000 Mathematics Subject Classification : Primary 03E15 ; Secondary 03E45, 54H05 Key words and phrases : covering , separation, effectivity, Novikov Theorem, distinguished tree

relations

Table of Contents

0. Introduction................................................................................................................. 3 1. Main results ................................................................................................................. 4 2. The representation Theorem for Borel sets.................................................................. 7 3. Resolution of quasi-strategies .................................................................................... 11 4. Local resolution of quasi-strategies ............................................................................ 15 5. Adequate Baire types................................................................................................. 18 6. A dichotomy for coanalytic coverings ........................................................................ 19 7. On the necessity of adequate Baire types ................................................................. 33 8. Proof of the representation Theorem......................................................................... 37

Effective refining of Borel coverings 7/10/2008 – 16:22

INTRODUCTION

In this work we will be concerned in separation and reduction results. For simplicity we restrict our study to the Baire space ω^{ω} but all the results admit straightforward extensions to arbitrary recursively presented Polish spaces. For all undefined descriptive notions and notation we refer the reader to [5].

Let us recall that a set A_{0} is said to be separated from a set A_{1} by the set B if B ⊃ A_{0} and B ∩ A_{1} = ∅. Thus the classical Suslin separation Theorem asserts that any two Σ_{1}^{1} disjoint sets A_{0} and A_{1} can be separated (each from the other one) by a Δ_{1}^{1} set. It is also well known that this result is “effective” in the sense that if A_{0} and A_{1} are Σ_{1}^{1} then they can be separated by a Δ_{1}^{1} set. But a deeper effectivity feature of the separation Theorem is given by the following result due to A. Louveau [2] (in which ξ denotes a recursive ordinal) :

Theorem 0.1 (Louveau). Let A_{0} and A_{1} be two disjoint Σ_{1}^{1} sets. If A_{0} is separated from A_{1} by a Σ_{ξ}^{0} set then A_{0} is separated from A_{1} by a set in Δ_{1}^{1} ∩ Σ_{ξ}^{0}

In fact Louveau’s result asserts that A_{0} can be separated from A_{1} by a set in Σ_{ξ}^{0}(α) for some α ∈ Δ_{1}^{1}. Notice that this result is symmetrical : in swaping the indices 0 and 1 one obtains a similar statement for the multiplicative Baire classes Π_{ξ}^{0}.

Let us also recall that the Suslin Theorem can be extended to infinite families. This extension, which is due to Novikov, also admits the following effective version : For any Σ_{1}^{1} family (A_{i})_{i∈I} of sets such that ⋂_{i∈I} A_{i} = ∅ there exists a Δ_{1}^{1} family (B_{i})_{i∈I} such that B_{i} ⊃ A_{i} for all i, and ⋂_{i∈I} B_{i} = ∅.

Our goal in this work is to investigate an analog of Theorem 0.1 in the context of the Novikov Theorem. More precisely we shall consider the following :

\underline{Question} : Fix a recursive (in any obvious sense) family (Γ_{i})_{i∈I} of additive or multiplicative Baire classes. Let (A_{i})_{i∈I} be a Σ_{1}^{1} family of sets such that ⋂_{i∈I} A_{i} = ∅, and suppose that there exists a family (B_{i})_{i∈I} of Borel sets such that B_{i} ∈ Γ_{i}, B_{i} ⊃ A_{i} for all i, and ⋂_{i∈I} B_{i} = ∅. Can one find such a family (B_{i})_{i∈I} which is moreover Δ_{1}^{1} ?

We shall prove that the answer to this question is positive if we restrict ourselves to finite families but might be negative in the general case. In fact the main result will give a full characterization of those families (Γ_{i})_{i∈I} for which the answer is positive. Surprisingly in this characterization the precise nature (additive or multiplicative) of the Baire classes Γ_{i} will be crucial. In particular, and unlike in the case of Theorem 0.1, this result will not be symmetrical, and one cannot replace freely some Baire class Γ_{i} by its dual class.

In fact we shall derive the main result from a general dichotomy for infinite families of Σ_{1}^{1} sets, which extends the following strengthening of Theorem 0.1 proved in [3] :

Theorem 0.2 (Louveau - Saint Raymond). Fix a Π_{ξ}^{0} subset B_{0} of 2^{ω}. Then for any Σ_{1}^{1} disjoint sets A_{0} and A_{1} in ω^{ω} at least one of the following alternatives holds :

– either A_{0} is separated from A_{1} by a set in Σ_{ξ}^{0}(α) for some Δ_{1}^{1} real α

– or there exists a continuous mapping f : 2^{ω} → ω^{ω} such that B_{0} = f^{−1}(A_{0})

7/10/2008 – 16:22 1. Main results

(to recover Theorem 0.1 apply Theorem 0.2 to any B_{0} ∈ Π_{ξ}^{0} \ Σ_{ξ}^{0} and observe that if A_{0} is separated from A_{1} in Σ_{ξ}^{0} then the second alternative cannot hold). But as we shall see a non negligible part of the difficulty in the new dichotomy result will already lie in its formulation which will be less natural than the statement of Theorem 0.2. In particular in the second alternative one needs to consider some less intuitive notion of reduction.

From now on we shall deal with the dual formulation of all these results, replacing sets by their complements. In this duality families with empty intersection are thus replaced by coverings. This choice is of course completely arbitrary and non fundamental.

1 – MAIN RESULTS

We shall introduce in this section the basic notions needed for stating the main results of the paper that we will present here globally. 1.1. Basic descriptive notions :

Along this work we shall consider various descriptive classes : Δ_{1}^{1}, Σ_{1}^{1}, Π_{1}^{1}, Σ_{ξ}^{0}, Π_{ξ}^{0} … and their effective versions : Δ_{1}^{1}, Σ_{1}^{1}, Π_{1}^{1}, Σ_{ξ}^{0}, Π_{ξ}^{0} …, as well as their relativization to some real : Δ_{1}^{1}(α), Σ_{1}^{1}(α), Π_{1}^{1}(α), Σ_{ξ}^{0}(α), Π_{ξ}^{0}(α) … When the surrounding space is not specified it will be implicitly assumed to be ω^{ω}.

For practical reasons it will be convenient to work with families (A_{i})_{i∈I} of sets with an “abstract” index set I ; however when we use any descriptive notion in this context it will be understood that I is a subset of some ω^{n}.

We shall make frequent use of various notions of \underline{codes}. By definition a code will be an element of ω^{ω}. All these notions are natural variations of classical codings and we shall not explicit them. For example a code for an ordinal ξ will just be an element of the classical space WO. Similarly a code for a Baire class Γ of rank ξ will be a real α ≈ (i, β) ∈ 2 × WO where i = 0, 1 indicates whether Γ is additive or multiplicative and β is a code for ξ … Also given any notion of code for the elements of some set A and ξ any ordinal then a code for the family (a_{η})_{η<ξ} ∈ A^{ξ} will be real γ ≈ ((α_{n})_{n∈ω}, β) with β ∈ WO a code for ξ and such that for all n, α_{n} is a code for a_{η} where η is the order type of β_{|n} …

1.2. Baire types :

Since Baire classes will play a central role in our study let us make it clear that by a Baire class of rank ξ, where 1 ≤ ξ < ω_{1}, we will mean either the corresponding additive boldface Baire class Σ_{ξ}^{0} or the multiplicative boldface Baire class Π_{ξ}^{0}. Also to avoid any possible confusion we shall never refer to a lightface class Σ_{ξ}^{0} or Π_{ξ}^{0} as a Baire class.

A Baire type is simply a family (Γ_{i})_{i∈I} where each Γ_{i} is a Baire class. If for all i ∈ I, Γ_{i} is of rank ξ_{i} we shall say that the Baire type (Γ_{i})_{i∈I} is of rank (ξ_{i})_{i∈I}. We shall say that a family (A_{i})_{i∈I} of Borel sets is of Baire type (or simply of type) (Γ_{i})_{i∈I} if for all i ∈ I, A_{i} ∈ Γ_{i} .

Definition 1.3. Given two families (A_{i})_{i∈I} and (B_{i})_{i∈I} of subsets of some space X, we shall say that (B_{i})_{i∈I} is subordinate to (A_{i})_{i∈I} if :

⋃_{i∈I} B_{i} = ⋃_{i∈I} A_{i}  and  ∀i ∈ I, B_{i} ⊂ A_{i}

We shall very often use this notion when (A_{i})_{i∈I} is a covering of X, in which case a subordinate family (B_{i})_{i∈I} is automatically a covering too and we shall then say that (B_{i})_{i∈I} is a subordinate covering to (A_{i})_{i∈I}. This notion is of quite common use (under different terminologies) in Analysis, namely in connection with the so-called “partitions of unity”. But our main concern here is that the Novikov Theorem or more precisely its dual formulation, that is the “reduction Theorem”, can be expressed by simply saying that any Π_{1}^{1} covering (A_{i})_{i∈I} admits a Borel subordinate covering (B_{i})_{i∈I}. Observe however that we do not impose on the Borel sets B_{i} in the subordinate covering to be pairwise disjoint ; this detail is very important.

Let us also emphasize here that a subordinate family has the same index set as the initial family. In particular the notion of subordination is totally different from the notion of “refinement” considered in general topolgy in which one compares coverings (A_{i})_{i∈I} and (B_{j})_{j∈J} with possibly different index sets.

We shall now state the main result of this work. This result concerns in fact very special Baire types that we will call “adequate” (see Definition 5.2). This totally ad hoc notion is not very intuitive and it would be very difficult to motivate it at this level of the discussion. Let us only point out that a Baire type with only finitely many multiplicative Baire classes is adequate. Conversely in an adequate Baire type a multiplicative Baire class can occur at most finitely many times, though infinitely many different multiplicative Baire classes might occur but then in some very specific configuration.

Theorem A. Let (Γ_{i})_{i∈I} be a Baire type with code α ∈ ω^{ω}. Then the following are equivalent :

(i) For all β ∈ ω^{ω}, any Π_{1}^{1}(β) covering which admits a subordinate covering of type (Γ_{i})_{i∈I} admits a Δ_{1}^{1}(α, β) subordinate covering of type (Γ_{i})_{i∈I}.

(ii) For all β ∈ ω^{ω}, any Δ_{1}^{1}(β) covering which admits a subordinate covering of type (Γ_{i})_{i∈I} admits a Δ_{1}^{1}(α, β) subordinate covering of type (Γ_{i})_{i∈I}.

(iii) (Γ_{i})_{i∈I} is an adequate Baire type.

So (i) asserts that the answer to our initial question is positive, and (iii) gives the necessary and sufficient condition on (Γ_{i})_{i∈I} for this.

To prove Theorem A it is clearly sufficient to prove that (ii) ⇒ (iii) ⇒ (i). Both implications are non trivial. But the first one is much simpler and will be derived from a general complexity argument : assuming that (Γ_{i})_{i∈ω} is not adequate we shall prove that (via some suitable coding) the set of all Δ_{1}^{1}(β) coverings which admit a subordinate covering of type (Γ_{i})_{i∈ω} is Σ_{1}^{1}-hard (i.e. reduces continuously any Σ_{1}^{1} set). It will follow that this set cannot coincide with the set of all Δ_{1}^{1}(β) coverings admitting a Δ_{1}^{1}(α, β)- subordinate covering of type (Γ_{i})_{i∈ω}, since the latter is Π_{1}^{1}(α, β). In particular the argument will not construct any explicit β and the universal quantifications in the statement of (i) and (ii) are crucial to get the equivalence with (iii).

The proof of the second implication (iii) ⇒ (i) is much more elaborate and will follow from a general dichotomy concerning Π_{1}^{1} coverings, which can be viewed as a generalization of Theorem 0.2. To state simply this result we need to introduce one more notion.

Definition 1.4. Let (A_{i})_{i∈I} be a family of subsets of some space X and (B_{i})_{i∈I} be a family of subsets of some space Y. We shall say that (A_{i})_{i∈I} is weakly reducible to the family (B_{i})_{i∈I} of subsets of Y, if there exists a continuous mapping f : X → Y such that :

∀x ∈ ⋃_{i∈I} A_{i} , ∃i_{∗} ∈ I , x ∈ A_{i_{∗}} and f(x) ∈ B_{i_{∗}}

We shall then say that f is a weak reduction of (A_{i})_{i∈I} to (B_{i})_{i∈I}

Observe that if (A_{i})_{i∈I} is a partition then a weak reduction reduces (in the classical sense) each A_{i} to B_{i}. However for our main application we shall need to deal with families which cannot be pairwise disjoint.

The proof of the following result constitutes the major content of the paper.

Theorem B. For any α ∈ ω^{ω}, if (Γ_{i})_{i∈I} is an adequate Baire type with code in Δ_{1}^{1}(α) and (B_{i})_{i∈I} is a Δ_{1}^{1}(α) family of type (Γ_{i})_{i∈I}, then for any Π_{1}^{1}(α) covering (C_{i})_{i∈I} at least one of the following two alternatives holds :

– either (C_{i})_{i∈I} admits a Δ_{1}^{1}(α)-subordinate covering of type (Γ_{i})_{i∈I}

– or (B_{i})_{i∈I} is weakly reducible to (ω^{ω} \ C_{i})_{i∈I}

In fact the real starting point of the present work goes back to the alternative proof of Theorem 0.2 that we gave recently in [1]. At that time this proof was conceived merely as an additional illustration for the use of the representation of Borel sets developed in that work. In both proofs, in [3] as well as in [1], the dichotomy corresponds to the determinacy of some suitable open game which is introduced. However while the whole difficulty in the initial proof in [3] lies precisely in the definition of the game, the game considered in [1], which relies on the representation Theorem of Borel sets, is very simple and quite natural.

Also to prove Theorem B we shall follow the same scheme. But unfortunately in the present case the obstacles will be numerous. In particular we will need to ameliorate the representation of Borel sets developed in [1] which is suitable to analyze a countable family of Borel sets of the same Borel rank, but is not adapted to handle Borel sets of variable rank. Also in the new context the definition of the game as well as the arguments present serious new technical difficulties, and it is precisely to overcome these difficulties that we were led to consider “adequate” Baire types, which happened to be the optimal setting. In particular the arguments for additive and multiplicative Baire classes will not be symmetrical as in the proof of Theorem 0.2. More surprising are the additional problems which appear in the treatment of multiplicative Baire classes of limit rank.

Theorem B, from which follows the implication (iii) ⇒ (i) of Theorem A, will be proved in Section 6 which is the core of this work. This proof will make use of a large amount of material from [1] (more specifically Chapters I and III). In fact the situation is a bit more complicated since the results of [1] are not adapted to our needs and we will have to prove new versions which are not merely generalizations, though the basic ideas and concepts are extracted from [1]. In particular we will need a new version of the representation Theorem for Borel sets proved in [1]. This result is presented in Section 2 ; however its proof which is rather technical and does not really interact with the rest of this work, is postponed to Section 8. In Section 3 we shall present an other basic idea from [1] that we shall then extend in Section 4. In Section 5 we introduce the last ingredient which is the notion of adequate Baire type and prove some elementary properties.

The second implication (i) ⇒ (ii) of Theorem A, which proves the necessity of the “adequate Baire type” assumption in Theorem B, is established in Section 7. This section is totally independent from the rest of the paper.

Despite the high interference of several results from [1] in the present work the paper is essentially self-contained. In particular all basic notions are explicited and widely commented and unless the reader wants to check some proofs he should normally not need to go back to our earlier work.

2 – THE REPRESENTATION THEOREM FOR BOREL SETS

In this section we shall state without proof the representation Theorem for Borel sets which is the main ingredient of the proof of the dichotomy Theorem. For this we need to introduce first the basic notion of distinguished subrelation which is at the heart of this representation. However let us point out to the reader who is only interested in the proof of dichotomy Theorem that he will find at the end of the present section (Remark 2.13) a statement which avoids the non intuitive notion of distinction. 2.1. Tree relations :

Let Ext denote the standard non strict extension relation ⪯ on Seq(ω). The representation Theorem (for Borel subsets of ω^{ω}) will involve relations R on Seq(ω) which are finer than Ext , so :

R ⊂ Ext ⊂ Seq(ω) × Seq(ω)

However it wil be clearer for the exposition to consider these notions in a general setting. Let us recall that a relation R on a set E is a \underline{tree relation} if :

(1) R is a preordering,

(2) R admits a least element,

(3) any initial segment of R is finite and linearly ordered. We then set E = Dom(R) and denote by [R] the set of all infinite R-\underline{branches}, that is the maximal (relatively to the inclusion relation) linearly ordered subsets of Dom(R). We also equip [R] with the topology generated by the sets :

N_{s}^{R} = { σ ∈ [R] : s ∈ σ }

for s ∈ Dom(R). This topology is Polish and the sets N_{s}^{R} are actually clopen and form a basis for this topology (N_{s}^{R} ∩ N_{t}^{R} = ∅ or N_{s}^{R} ⊂ N_{t}^{R} or N_{t}^{R} ⊂ N_{s}^{R}). Observe that Ext-branches are just the sets of the form

x̂ := {x_{|n}; n ∈ ω} ⊂ Seq(ω)

for x ∈ ω^{ω}, and the mapping x ↦ x̂ is obviously a homeomorphism from ω^{ω} onto [Ext ].

2.2. Canonical mappings : If R_{1} ⊂ R_{0} are two tree relations then any infinite R_{1}-branch σ is contained in a unique infinite R_{0}-branch π(σ) ; this defines a \underline{canonical mapping} :

π : [R_{1}] → [R_{0}]

This mapping is clearly continuous but a priori it is neither injective nor surjective. The essence of the representation Theorem is to associate to any Σ_{1+ξ}^{0} set B ⊂ ω^{ω} ≈ [Ext ], a tree relation R ⊂ Ext such that :

(1) the canonical mapping π : [R] → [Ext ] is bijective

(2) the inverse mapping π^{−1} : [Ext ] → [R] is Borel and of Baire class ξ

(3) π^{−1}(B) is Σ_{1}^{0}.

But let us point out that behind the descriptive statement (2) lies a purely algebraic property, that we introduce now.

7/10/2008 – 16:22 2. The representation Theorem for Borel sets

Definition 2.3. Let R_{1} ⊂ R_{0} be two tree relations. R_{1} is said to be distinguished in R_{0} if for all u R_{0} v R_{0} w the following implication holds :

u R_{1} w ⟹ u R_{1} v

In particular if R_{1} is distinguished in R_{0} then for any v such that v R_{0} w, the R_{1}- predecesssor w^{∗} of w is already an R_{1}-predecesssor of v, unless v R_{0} w^{∗}. In fact this last property is equivalent to the distinction of R_{1} in R_{0} and is the “concrete” way in which this notion will be used in most applications. As a trivial example observe that any relation R depending only on the first argument (u R v ↔ u R w) is distinguished in any coarser relation R_{0}⊃R; but we have much better : for any other relation R_{1}⊂R_{0}, if R_{1} distinguished in R_{0} then R_{1} ∪ R is distinguished in R_{0}. This simple observation will play a fundamental role in Section 4. But of course the proof of the representation Theorem in Section 8 will provide other non trivial examples.

The following consequence of Theorem I.3.8 in [1] will give a first indication on the descriptive aspect hidden in the algebraic notion of distinction.

Proposition 2.4. If R_{1} is distinguished in R_{0} then the canonical mapping π : [R_{1}] → [R_{0}] is one-to-one. If moreover π is onto then the inverse mapping π^{−1} : [R_{0}] → [R_{1}] is of Baire class 1.

Consider now a finite chain of tree relations :

R^{(n)} ⊂ R^{(n−1)} ⊂ · · · · · · ⊂ R^{(0)}

and suppose that each relation R^{(k)} is distinguished in the previous one. The canonical mapping π_{n} : [R^{(n)}] → [R^{(0)}] is then just the composition of the successive canonical mappings π_{(k,k−1)} : [R^{k}] → [R^{(k−1)}]. Hence it follows from Proposition 2.4 that π_{n} is also one-to-one. Moreover if π_{n} is onto then all the π_{k} are also onto hence, again by Proposition 2.4, π_{n}^{−1} : [R^{(0)}] → [R^{(n)}] is of Baire class n.

Unfortunately these simple arguments do not extend to an infinite chain and in this case the situation is much more delicate.

Definition 2.5. A transfinite chain of tree relations (R^{(η)})_{η≤ξ} is said to be a resolution family if :

1) For all η < ξ, R^{(η+1)} ⊂ R^{(η)} and R^{(η+1)} is distinguished in R^{(η)}

2) For all λ ≤ ξ limit, R^{(λ)} = ⋂_{η<λ} R^{(η)}

Observe that if (R^{(η)})_{η≤ξ} is a resolution family then it follows from Proposition 2.4 that all the canonical mappings π_{η} : [R^{(η)}] → [R^{(0)}] are one-to-one.

Definition 2.6. A resolution family (R^{(η)})_{η≤ξ} is said to be an expansion family if the last canonical mapping π_{ξ} is onto ; in this case all the canonical mappings π_{η} are bijective.

Thus if (R^{(η)})_{η≤ξ} is an expansion family and η ≤ ξ then any R^{(0)}-infinite branch σ contains a unique R^{(η)}-infinite branch π_{η}^{−1}(σ) that we shall also denote by σ^{(η)}. The following simple result which is not stated explicitly in [1] will be enlightening for the sequel.

Proposition 2.7. If (R^{(η)})_{η≤ξ} is an expansion family then :

\{ \begin{matrix}σ^{(η+1)} = \{s ∈ σ^{(η)} : ∀t ∈ σ^{(η)}, (s R^{(η)} t ⇒ s R^{(η+1)} t)\} & if η < ξ \\ σ^{(λ)} = ⋂_{η<λ} σ^{(η)} & if λ ≤ ξ is limit \end{matrix}

\underline{Proof} : Since R^{(η+1)} is distinguished in R^{(η)} the successor case follows from Corollary I-3.6 in [1], and the limit case is obvious. ■

Let R = (R^{(η)})_{η≤ξ} be a given expansion family. To compute the complexity of the mapping π_{η}^{−1} : [R^{(0)}] → [R^{(η)}] consider a basic clopen set N_{s}^{R^{(η)}} of the space [R^{(η)}] and observe that

π_{η}(N_{s}^{R^{(η)}}) = {σ ∈ [R^{(0)}] : s ∈ σ^{(η)}}

Then using Proposition 2.7 one can show by a straightforward induction that the set π_{η}(N_{s}^{R^{(η)}}) is Δ_{η+1}^{0}, hence the image by π_{η} of any Σ_{1}^{0} set is a Σ_{η+1}^{0} set. In particular if η is finite then π_{η}^{−1} is of Baire class η as was already observed above. But if η is infinite, this only proves that π_{η}^{−1} is of Baire class η + 1 (we recall that a mapping is said to be of Baire class η if the inverse image of any Σ_{1}^{0} set is a Σ_{1+η}^{0} set). However it is proved in [1] (Proposition I-4.1) that when ξ is limit then, under some additional “uniformity” assumption on R, the last inverse mapping π_{ξ}^{−1} is of Baire class ξ; but even in this case the mappings π_{η}^{−1} for η < ξ are still of class η + 1.

Moreover the previous complexity bounds are best possible since by the representation Theorem proved in [1] (Theorem I-6.6) any Σ_{ξ}^{0} set B can be obtained as the image of some Σ_{1}^{0} set by the last canonical mapping associated to some expansion family R = (R^{(η)})_{η≤ξ′} with either ξ = ξ′ + 1, or ξ = ξ′ limit and R “uniform”.

Nevertheless we shall prove in the present work that if one strengthens the uniformity condition then all the inverse mappings π_{η}^{−1} become of Baire class η (instead of η + 1), and it will follow from the new representation Theorem (Theorem 2.10 below) that any Σ_{ξ}^{0} set B can be obtained as the image of some Σ_{1}^{0} set by the last canonical mapping associated to some expansion family R = (R^{(η)})_{η≤ξ} satisfying this stronger uniformity condition. However this new version of the representation Theorem is formally incomparable with the one proved in [1] since the latter provides (in the successor case) representations with shorter resolutions families, and this specific detail is crucial for the proof of the main result of [1] (Theorem VI-0.1)

Before we introduce the next basic notion observe that if (R^{(η)})_{η≤ξ} is a resolution family and λ ≤ ξ is limit then it follows from the continuity condition at λ that :

∀ v , ∃ η < λ , ∀ u (u R^{(η)} v ⇒ u R^{(λ)} v)

Definition 2.8. a) We shall say that the resolution family (R^{(η)})_{η≤ξ} is strongly continuous at the limit ordinal λ ≤ ξ if :

∀ u , ∃ η < λ , ∀ v (u R^{(η)} v ⇒ u R^{(λ)} v)

b) We shall say that (R^{(η)})_{η≤ξ} is strongly continuous if it is strongly continuous at any limit ordinal λ ≤ ξ.

The following result that we shall not use can be derived directly from Proposition 2.7 but it can also (see Remark 3.5) be interpreted as a particular case of Theorem 3.10 proved in next section.

Proposition 2.9. If (R^{(η)})_{η≤ξ} is a strongly continuous expansion family then for all η ≤ ξ the mapping π_{η}^{−1} : [R^{(0)}] → [R^{(η)}] is of Baire class η.

We can now state the representation Theorem that we will prove in Section 8.

Theorem 2.10. Let (B_{i})_{i∈I} be a countable family of Borel subsets of ω^{ω} with B_{i} ∈ Σ_{1+ξ_{i}}^{0}, and set ξ = sup_{i∈I} ξ_{i}. Then there exists a strongly continuous expansion family (R^{(η)})_{η≤ξ} with R^{(0)} = Ext such that for all i ∈ I, π_{ξ_{i}}^{−1}(B_{i}) is a Σ_{1}^{0} subset of [R^{(ξ_{i})}].

In the proof of the dichotomy Theorem in Section 6 we will need to apply this result to a family (B_{i})_{i∈ω} of Borel sets of Baire type (Γ_{i})_{i∈I}. Of course taking complements if necessary one can always apply Theorem 2.10 to get a resolution family (R^{(η)})_{η≤ξ} such that B′_{i} := π_{ξ_{i}}^{−1}(B_{i}) is either open or closed, depending whether Γ_{i} is additive or multiplicative. But for technical reasons we will prefer to work with a slightly more concrete such representation.

Definition 2.11. Let R be a tree relation and S ⊂ Dom(R).

a) We shall say that S is R-hereditary if :

(u R v and v ∈ S) ⟹ u ∈ S

b) We shall say that S is R-monotone if Dom(R) \ S is R-hereditary that is if : (u R v and u ∈ S) ⟹ v ∈ S

It is quite clear that R-hereditary sets are the analog of trees (which are precisely the Ext -hereditary sets). For example one can easily see that for any Π_{1}^{0} subset of [R] there exists an R-hereditary set S ⊂ Dom(R) such that for all σ ∈ [R] :

σ ∈ A ⟺ σ ⊂ S

and by duality, for any Σ_{1}^{0} subset of [R] there exists an R-monotone set S ⊂ Dom(R) such that such that for all σ ∈ [R] :

σ ∈ A ⟺ σ ∩ S ≠ ∅

Moreover if A is Δ_{1}^{1}(α) for some α then one can find S in Δ_{1}^{1}(α) : this can be easily derived from the classical case R = Ext .

We can now restate Theorem 2.10 in a more adapted way for our application.

Theorem 2.12. Let (Γ_{i})_{i∈I} be a Baire type of rank (ξ_{i})_{i∈I} with ξ := sup_{i∈I} ξ_{i}. For any family (B_{i})_{i∈I} of Borel subsets of ω^{ω} of type (Γ_{i})_{i∈I} there exist a strongly continuous expansion family R = (R^{(η)})_{η≤ξ} with R^{(0)} = Ext , and a family (S_{i})_{i∈I} of subsets of Seq(ω) satisfying :

a) For all x ∈ ω^{ω} and all η ≤ ξ there exists a unique R^{(η)}-branch x̂^{(η)} contained in x̂ b) If Γ_{i} = Σ_{1+ξ_{i}}^{0} then S_{i} is R^{(ξ_{i})}-monotone and for all x ∈ ω^{ω} :

x ∈ B_{i} ⟺ x̂^{(ξ_{i})} ∩ S_{i} ≠ ∅

c) If Γ_{i} = Π_{1+ξ_{i}}^{0} then S_{i} is R^{(ξ_{i})}-hereditary and for all x ∈ ω^{ω} :

x ∈ B_{i} ⟺ x̂^{(ξ_{i})} ⊂ S_{i}

2.13. Remarks : a) Given any transfinite family R = (R^{(η)})_{η≤ξ} of tree relations on Seq(ω), let us say that a pair ⟨R, (S_{i})_{i∈I}⟩ is a representation of type (Γ_{i})_{i∈I} for (B_{i})_{i∈I} if it satisfies properties a), b), c) of Theorem 2.12 (observe that these properties do not involve the notion of distinguished subrelation). The existence of such a representation (even without any distinction property) is a totally non trivial fact. Still the additional information that one can impose on R to be a resolution family will be crucial for the proof of Theorem 2.10 in Section. Indeed as one can reasonably expect this proof will be by induction, and the only way we know to achieve it is by ensuring at each step this stronger property.

b) Let us also point out that the family R constructed in the proof of Theorem 2.10 will be defined by explicit recursive formulas, and it will be clear that R can then be taken in any admissible fragment of L containing a code for the family (B_{i}, Γ_{i})_{i∈I}. In particular if (B_{i}, Γ_{i})_{i∈I} has a code in Δ_{1}^{1}(α) then we can choose ⟨R, (S_{i})_{i∈I}⟩ with code in Δ_{1}^{1}(α) too and we shall then say that ⟨R, (S_{i})_{i∈I}⟩ is a Δ_{1}^{1}(α)-representation of type (Γ_{i})_{i∈I} for (B_{i})_{i∈I}.

The existence of such representations will be one of the basic ingredients of the proof of the dichotomy Theorem in Section 6. But this is only part of what we will need for this proof which will also make use of another general property of resolution families that we will develop in the following two sections.

3 – RESOLUTION OF QUASI-STRATEGIES

Roughly speaking one can view a resolution family (R^{(η)})_{η≤ξ} as a family of “operators” which transform R^{(0)}-branches into R^{(η)}-branches via the following formulas (see Proposition 2.7) :

\{ \begin{matrix}σ^{(η+1)} = \{s ∈ σ^{(η)} : ∀t (s R^{(η)} t ⇒ s R^{(η+1)} t)\} & if η < ξ \\ σ^{(λ)} = ⋂_{η<λ} σ^{(η)} & if λ ≤ ξ is limit \end{matrix}

The basic idea is then to enlarge the domain of these operators and consider these formulas for arbitrary subsets σ of Dom(R^{(0)}). More particularly we shall consider the case where Dom(R^{(0)}) is the set of all positions for some player in an arbitrary game and σ is a quasi-strategy for this player. Observe that in this procedure the starting resolution family (R^{(η)})_{η≤ξ} is not necessarily associated to some family (B_{i})_{i∈ω} of Borel sets, and in this respect the results of this section are totally independent from the representation Theorem whose only role will be to provide resolution families.

The notions discussed in this section are extracted from Section III.1 of [1] and our goal here is to strengthen (under some additional assumption) the conclusion of Theorem III-1.7.

3.1. General terminolgy and notation : To avoid any ambiguity we fix the definition of the basic notions concerning games.

A \underline{game} Γ on ω is simply a tree on ω. An element u of Γ will then called a position : if |u| is odd (even) we shall say that u is a I-position (II-position), and if u is nonempty we set :

u^{∗} = u_{||u|−1}

Also given any set Λ ⊂ Seq(ω) we set :

Λ_{I} = {u ∈ Λ : u is a I-position }  and  Λ_{II} = {u ∈ Λ : u is a II-position }

In all the sequel quasi-strategies will always be relative to Player I. We recall that a \underline{quasi-strategy} in the game Γ is a subtree Σ of Γ satisfying :

7/10/2008 – 16:22 3. Resolution of quasi-strategies

For any u ∈ Σ_{I} and v ∈ Γ_{II} such that u = v^{∗} there exists w ∈ Σ_{I} such that v = w^{∗}. We shall say that a tree Σ is a quasi-strategy (without any reference to some game) if Σ is a quasi-strategy in the game Σ, that is if Σ has no terminal element of even length.

Before going further let us make it clear that our main concern here is not game determinacy, but the study of quasi-strategies as “large sets”. In particular strategies are irrelevant in this study. The reason for this is that we shall define operators on spaces of quasi-strategies. Of course one can always apply such an operator to a strategy but then the result will still be a quasi-strategy and trying to replace it by a strategy, besides being not natural in this context, would complicate very seriously the statements.

3.2. The games Γ^{(R)} : Let Ext_{I} denote the restriction of Ext to the set {∅} ∪ (Seq(ω))_{I} and let R be a tree relation such that :

R ⊂ Ext_{I}

Then given any set Γ ⊂ Seq(ω) we consider the game Γ^{(R)} \underline{on} Seq(ω) in which at each of their moves : Player I chooses some u_{2n} ∈ Γ_{I} and Player II chooses some u_{2n+1} ∈ Γ_{II} under the following rules :

1) u_{2n−1} ≺ u_{2n} ≺ u_{2n+1}
2) u_{2n−1} = u_{2n}^{∗}
3) u_{2n−1} is the R-predecessor of u_{2n+1}

where by convention u_{−1} = ∅.

Thus formally speaking Γ^{(R)} ⊂ Seq(Seq(ω)). Notice however that any nonempty position ū = (u_{0}, u_{1}, …, u_{n}) in Γ^{(R)} is entirely determined by the last move u_{n} ∈ Γ, hence the correspondence Γ ↦ Γ^{(R)} is one-to-one ; moreover :

ū ∈ (Γ^{(R)})_{I} ⟺ u_{n} ∈ Γ_{I}

We recall that Γ is an arbitrary subset of Seq(ω). But when Γ is a tree then one can consider Γ as a game (on ω) and in this case the significance of the game Γ^{(R)} is quite intuitive : one can view a run in Γ^{(R)} as a run in Γ in which Player I is allowed to choose (under some restrictions) some of Player II’s moves while Player II is playing by simple moves as in Γ.

Definition 3.3. Let R ⊂ Ext_{I} be a tree relation. We shall say that Σ ⊂ Γ is R-strategical (implicitly for Player I) in Γ if :

a) For any u ∈ Σ_{I} if ∅ ≺ u′ R u then u′ ∈ Σ_{I}.

b) For any u ∈ Σ_{I} and v ∈ Γ_{II} such that u = v^{∗} there exists w ∈ Σ_{I} such that u ≺ v ≺ w and u is the R-predecessor of w.

In particular when Γ is a tree then Σ is Ext_{I}-strategical in Γ if and only if Σ is a quasi-strategy in the game Γ. Also by merely inspecting the definitions one can easily check the following :

Proposition 3.4. Σ is R-strategical in Γ if and only if Σ^{<ω} ∩ Γ^{(R)} is a quasi-strategy in the game Γ^{(R)}.

3.5. Remark : We can identify any element σ ∈ [Ext_{I}] to some x ∈ ω^{ω} but also to the trivial game in which at his (n + 1)^{th} move Player I has to play x(n) while Player II has always to play “0”. Then τ ⊂ σ is R-strategical in σ if and only if τ is an R-branch. Thus the notion of R-strategical set is a generalization of the notion of R-branch.

In particular if (R^{(η)})_{η≤ξ} is an expansion family we shall canonically associate to any R^{(0)}-strategical set Σ and any η ≤ ξ an R^{(η)}-strategical set Σ^{(η)} and the mapping Σ ↦ Σ^{(η)} will be a generalization of the mapping π_{η}^{−1} : σ ↦ σ^{(η)} (where σ^{(η)} denotes the unique R^{(η)}- infinite branch contained in the R^{(0)}-infinite branch σ). In fact Σ^{(η)} will be defined essentially by copying the formulas which compute σ^{(η)} from σ (see Proposition 2.9) and as mentioned above this latter result will actually appear as a particular case of Theorem 3.9 below.

Definition 3.6. Let R = (R^{(η)})_{η≤ξ} be a resolution family with R^{(0)} ⊂ Ext_{I}. For any Σ ⊂ Seq(ω) we define inductively the family (Σ^{(η)})_{η≤ξ} by :

Σ^{(0)} = Σ
\{ \begin{matrix}Σ_{I}^{(η+1)} = \{u ∈ Σ_{I}^{(η)} : ∀v, w ∈ Σ_{I}^{(η)} if v R^{(η+1)} u and v R^{(η)} w then v R^{(η+1)} w\} \\ Σ_{II}^{(η+1)} = \{u ∈ Σ_{II}^{(η)} : u^{∗} ∈ Σ_{I}^{(η+1)}\} \end{matrix}
Σ^{(λ)} = ⋂_{ζ<λ} Σ^{(λ)} if λ is limit

We then define :

Φ_{R}(Σ) = Σ^{(ξ)}

Let us start by the following simple observation.

Lemma 3.7. For all v, w ∈ Σ^{(η)} if v R^{(0)} w then v R^{(η)} w.

\underline{Proof} : By induction on η. For η = 0 the result is trivial and the inductive step in the limit case is straightforward.

So suppose that the result is true for η and consider v, w ∈ Σ^{(η+1)} such that v R^{(0)} w. Since R^{(0)}⊂ Ext_{I} then necessarily v, w ∈ Σ_{I}^{(η+1)} ⊂ Σ^{(η)} and applying the inductive hypothesis we get that v R^{(η)} w, and it follows then from the very definition of Σ_{I}^{(η+1)} that v R^{(η+1)} w. ■

3.8. Remark : The formula defining Σ^{(η+1)} from Σ^{(η)} is slightly more complicated than the one defining σ^{(η+1)} from σ^{(η)} in Proposition 2.9, since it involves two universal quantifications (on v and w). In fact the role of the universal quantification on v is to ensure that the set Σ^{(η+1)} is R^{(η+1)} hereditary. However using the distinction of R^{(η+1)} in R^{(η)}, one can prove that if Σ^{(η)} is linearly ordered by R^{(η)} then in this case the two formulas are equivalent.

The following basic result is proved in [1] :

Theorem 3.9. For any expansion family R = (R^{(η)})_{η≤ξ} with R^{(0)} ⊂ Ext_{I}, if Σ ⊂ Seq(ω) is R^{(0)}-strategical then Φ_{R}(Σ) is R^{(ξ)}-strategical in Σ.

This is essentially part 1) of Theorem III-1.7 in [1]. Actually this latter result is stated as an existential result but the reader can easily check from the first lines of the proof that the mapping Φ considered there is exactly what we call Φ_{R} here. One should also observe that the additional “regularity” assumption in Theorem III-1.7 is not used in the proof of this part.

We now investigate the descriptive complexity of the mapping

Φ_{R} : P(Seq(ω)) → P(Seq(ω))

7/10/2008 – 16:22 4. Local resolution of quasi-strategies

where the space P(Seq(ω)) is identified with the space 2^{Seq(ω)} endowed with the product of the discrete topology on Seq(ω). In fact it follows from (the proof of) the second part of Theorem III-1.7 in [1] that :

a) Φ_{R} is of class ξ + 1

b) If ξ is limit and R is strongly continuous at ξ then Φ_{R} is of class ξ. But as we shall see next, part a) can be improved if we strengthen the hypothesis on R. We recall (see Definition 2.8) that “strongly continuous” means “strongly continuous at any limit level”.

Theorem 3.10. If R = (R^{(η)})_{η≤ξ} is a strongly continuous resolution family with R^{(0)} ⊂ Ext_{I} then Φ_{R} is of class ξ.

\underline{Proof} : For any Σ ⊂ Seq(ω) let (Σ^{(η)})_{η≤ξ} as in Definition 3.6 and set :

S_{u}^{(η)} = {Σ : u ∈ Σ^{(η)}}

We shall prove by induction on η that for all u ∈ Seq(ω) the set S_{u}^{(η)} is Δ_{1+η}^{0}.

For η = 0, S_{u}^{(0)} is a basic clopen set of the space P(Seq(ω)) and the result is trivial. We now prove the inductive step.

– The successor case : Suppose that for all u the set S_{u}^{(η)} is Δ_{1+η}^{0} and observe that from Definition 3.6 we have :

u ∈ Σ^{(η+1)} ⟺ u ∈ Σ_{I}^{(η+1)} or u^{∗} ∈ Σ_{I}^{(η+1)}
u ∈ Σ_{I}^{(η+1)} ⟺ \{ \begin{matrix}u ∈ Σ_{I}^{(η)} and ∀v, w (v ∉ Σ_{I}^{(η)} or w ∉ Σ_{I}^{(η)} \\ or ¬( v R^{(η+1)} u) or ¬( v R^{(η)} w) or v R^{(η+1)} w) \end{matrix}

Then applying the induction hypothesis one easily sees that the set S_{u}^{(η+1)} is then Π_{1+η}^{0} hence Δ_{1+η+1}^{0}.

– The limit case : Suppose now that λ is a limit ordinal and that for all u and all ζ < λ the set S_{u}^{(ζ)} is Δ_{1+ζ}^{0}. Fix u ∈ Seq(ω) ; since the resolution family (R^{(η)})_{η≤ξ} is strongly continuous we can then fix η < λ such that for any v ⪯ u we have :

∀w (v R^{(η)} w ⇒ v R^{(λ)} w)

\underline{Fact} : S_{u}^{(λ)} = S_{u}^{(η)}.

The inclusion from left to right is obvious. Conversely suppose that Σ ∈ S_{u}^{(η)} ; we shall prove by induction on ζ < λ that Σ ∈ S_{u}^{(ζ)} : For ζ = 0 this is obvious since Σ ∈ S_{u}^{(η)} ⊂ S_{u}^{(0)}. So suppose that Σ ∈ S_{u}^{(ζ′)} for all ζ′ < ζ ; we have to prove that u ∈ Σ^{(ζ)} :

- If ζ is limit this follows directly from the definition of Σ^{(ζ)} in the limit case.

- If ζ is successor set ζ = ζ^{∗} + 1 and consider any v, w ∈ Σ_{I}^{(ζ^{∗})} such that v R^{(ζ)} u and v R^{(ζ^{∗})} w; then v ⪯ u and v R^{(η)} w hence by the choice of η we also have v R^{(λ)}w and a fortiori v R^{(ζ^{∗}+1)}w. This proves that u ∈ Σ^{(ζ^{∗}+1)} = Σ^{(ζ)}. ⋄

Since S_{u}^{(λ)} = S_{u}^{(η)} then by the induction hypothesis the set S_{u}^{(λ)} is Δ_{1+η}^{0} hence Δ_{1+λ}^{0}. This finishes the proof of Theorem 3.10. ■

4 – LOCAL RESOLUTION OF QUASI-STRATEGIES

To analyze a game Γ (here on ω) it is quite common to consider its “localizations” that is the games Γ_{u} = {v ∈ Seq(ω) : u^{⌢}v ∈ Γ}. But this general procedure is not adpated to our setting since we want the localization of a game Γ^{(R)} to be itself of the same type. In fact this localization will be defined as the game Γ^{(R_{u})} where R_{u} will be the “localization to u” of the tree relation R”. Practically all results of this section follow very simply either from the definitions or from the results of the previous section, and we shall leave some verifications to the reader. However this simplicity does should not hide the fundamental fact lying behind all these results and which is the preservation of the notion of distinction by localization. We recall that Dom(Ext_{I}) = {∅} ∪ (Seq(ω))_{I}.

Definition 4.1. Let R be a tree relation such that R ⊂ Ext_{I} and Σ ⊂ Seq(ω). Then for any u ∈ Dom(Ext_{I}) we define the set Σ_{u} ⊂ Σ and the relation R_{u} ⊂ R by :

Σ_{u} = {v ∈ Σ : u ⪯ v}

v R_{u} w ⟺ (v = ∅ or u ⪯ v R w)

The following propositions follow readily from the definitions.

Proposition 4.2. Let R be a tree relation such that R ⊂ Ext_{I} and Σ ⊂ Seq(ω). Then for any u ∈ Dom(Ext_{I}) :

a) R_{u} ⊂ R is a tree relation.

b) [R_{u}] = {σ_{u} : σ ∈ [R] and σ_{u} is infinite}.

c) If Σ is R-strategical and u ∈ Σ then Σ_{u} is R_{u}-strategical.

Proposition 4.3. If R = (R^{(η)})_{η≤ξ} is a (strongly continuous) resolution (expansion) family then R_{u} = (R_{u}^{(η)})_{η≤ξ} is a (strongly continuous) resolution (expansion) family too.

From now on we fix a resolution family R = (R^{(η)})_{η≤ξ} such that R^{(0)} ⊂ Ext_{I}.

4.4. The mappings Φ^{τ} : Our goal now is to define for any τ in some large tree T , a mapping

Φ^{τ} : P(Seq(ω)) → P(Seq(ω))

which generalizes the mapping Φ_{R} associated to R (see Definition 3.6).

The mapping Φ^{τ} will be essentially a composition of mappings of the form Φ_{R′} where each R′ is a resolution family derived from R. Since the precise definitions of T and Φ^{τ} are rather tedious we shall first explicit them in an informal way.

a) Starting from the resolution family R = (R^{(η)})_{η≤ξ} we can construct new resolution families as follows : For any η ≤ η′ ≤ ξ and any u ∈ Dom(Ext_{I}) we can first consider the resolution family :

R^{(η,η′)} := (R^{(η+ζ)})_{ζ≤η′−η} ≈ (R^{(ζ)})_{η≤ζ≤η′}

then by Proposition 4.3 :

R_{u}^{(η,η′)} := (R^{(η,η′)})_{u} = (R_{u})^{(η,η′)}

is also a resolution family.

b) Fix Σ ⊂ Seq(ω). For any η_{0} ≤ ξ let R_{0} = (R^{(η)})_{0≤η≤η_{0}} and define :
Σ^{(η_{0})} := Φ_{R_{0}}(Σ) ⊂ Σ

then given any v_{0} ∈ Dom(Ext_{I}) we can define :

Σ^{(η_{0},v_{0})} := (Σ^{(η_{0})})_{v_{0}} ⊂ Σ^{(η_{0})} ∩ Σ_{v_{0}} ⊂ Σ_{v_{0}}

Now given any η_{1} ≥ η_{0} let R_{1} = R_{v_{0}}^{(η_{0},η_{1})} and define :

Σ^{(η_{0},v_{0},η_{1})} := Φ_{R_{1}}(Σ^{(η_{0},v_{0})}) ⊂ Σ^{(η_{0},v_{0})} ⊂ Σ_{v_{0}}

and again given any v_{1} ⪰ v_{0} we can define :

Σ^{(η_{0},v_{0},η_{1},v_{1})} := (Σ^{(η_{0},v_{0},η_{1})})_{v_{1}} ⊂ Σ^{(η_{0},v_{0},η_{1})} ∩ Σ_{v_{1}} ⊂ Σ_{v_{1}}

and so on.

c) Observe that if Σ is R^{(0)}-strategical then by Theorem 3.9, Σ^{(η_{0})} is R^{(η_{0})}-strategical. If moreover v_{0} ∈ Σ^{(η_{0})} then by Proposition 4.2, Σ^{(η_{0},v_{0})} is R_{v_{0}}^{(η_{0})}-strategical and obviously v_{0} ∈ Σ^{(η_{0},v_{0})}. Then again by Theorem 3.9, Σ^{(η_{0},v_{0},η_{1})} is R_{v_{0}}^{(η_{1})}-strategical but v_{0} might be no more in Σ^{(η_{0},v_{0},η_{1})}. If moreover v_{1} ∈ Σ^{(η_{0},v_{0},η_{1})} then Σ^{(η_{0},v_{0},η_{1},v_{1})} is R_{v_{1}}^{(η_{1})}-strategical and v_{1} ∈ Σ^{(η_{0},v_{0},η_{1},v_{1})}.

d) We now proceed to a precise formal definition. Let T be the tree of all “alternate” sequences

τ = (η_{0}, v_{0}, η_{1}, v_{1}, …)

where η_{0} ≤ η_{1} ≤ … is a non decreasing sequence of ordinals ≤ ξ, and v_{0} ⪯ v_{1} ⪯ … is a non decreasing sequence of positions in Dom(Ext_{I}).

For all τ ∈ T we define

ℓ(τ) = (ℓ_{0}(τ), ℓ_{1}(τ)) ∈ ω_{1} × Seq(ω)

by :

\{ \begin{matrix}ℓ_{0}(τ) = max\{τ(k); k even < |τ|\} & or 0 if τ = ∅ \\ ℓ_{1}(τ) = max\{τ(k); k odd < |τ|\} & or ∅ if |τ| ≤ 1 \end{matrix}

in particular ℓ(∅) = (0, ∅). If τ ≠ ∅ we denote by τ^{∗} its predecessor in T .

We now define, by induction on |τ|, for τ ∈ T the mapping Φ^{τ}. We first set :

Φ^{∅} = Id

Suppose that Φ^{τ} is already defined for some τ ∈ T of even length and set ℓ(τ) = (η, v) then for all η′ ≥ η and all v′ ⪰ v we define for Σ ⊂ Seq(ω) :

Φ^{τ^{⌢}⟨η′⟩}(Σ) = Φ_{R_{v}^{(η,η′)}}(Φ^{τ} (Σ)) and Φ^{τ^{⌢}⟨(η′,v′)⟩}(Σ) = (Φ^{τ^{⌢}⟨η′⟩}(Σ))_{v′}

We also define by induction on |τ| a set S^{τ} ⊂ P(Seq(ω)) as follows :

S^{∅} = {Σ ⊂ Seq(ω) : Σ is R^{(0)}-strategical}

and if τ ≠ ∅ :

S^{τ} = \{ \begin{matrix}\{Σ ∈ S^{τ^{∗}} : u ∈ Φ^{τ^{∗}}(Σ)\} & if |τ| is even and ℓ_{1}(τ) = u \\ S^{τ^{∗}} & if |τ| is odd \end{matrix}

(For the motivation of this definition see the observations in c)).

Finally let us point out that for the aplications we shall only deal with sequences τ of even length and the consideration of sequences of odd length is only needed for the inductive definition of Φ^{τ}. For this reason some of the properties are either trivial or non significant in the odd case.

Theorem 4.5. Let R be an expansion family and τ ∈ T with ℓ(τ) = (η, u). If Σ ∈ S^{τ} is R^{(0)}-strategical then :

a) Φ^{τ} (Σ) is R_{u}^{(η)}-strategical.
b) If |τ| is even then u ∈ Φ^{τ} (Σ).
c) For all v, w ∈ Φ^{τ} (Σ), if v R^{(0)} w then v R^{(η)} w.
d) For all w ∈ Φ^{τ} (Σ) if u ⪯ v R^{(η)} w then v ∈ Φ^{τ} (Σ).

\underline{Proof} : Observe that d) follows from a) since an R_{u}^{(η)}-strategical set is R_{u}^{(η)}-hereditarity. We now prove a), b), c) simultaneously by induction on |τ|.

For τ = ∅ the result is trivial since Φ^{∅}(Σ) = Σ. Suppose that the result is true for τ^{∗} and set ℓ(τ^{∗}) = (η^{∗}, u^{∗}). Then by the induction hypothesis Σ^{∗} := Φ^{τ^{∗}}(Σ) is R_{u^{∗}}^{(η^{∗})}-strategical.

– If |τ| is even then η = η^{∗} and Φ^{τ} (Σ) = Σ_{u}^{∗}; and since Σ ∈ S^{τ} then u ∈ Σ^{∗} hence by Proposition 4.2 c), Φ^{τ} (Σ) is R′-strategical with R′ = (R_{u^{∗}}^{(η^{∗})})_{u} = (R_{u^{∗}}^{(η)})_{u} = R_{u}^{(η)} which proves a). Moreover since u ∈ Σ^{∗} then obviously u ∈ Σ^{∗} ∈ Φ^{τ} (Σ) which proves b). Finally c) follows from the induction hypothesis since Φ^{τ} (Σ) ⊂ Φ^{τ^{∗}}(Σ) and η = η^{∗}.

– If |τ| is odd then u = u^{∗} and Φ^{τ} (Σ) = Φ_{R_{u}^{(η^{∗},η)}}(Σ^{∗}). Then by Theorem 3.9, Φ^{τ} (Σ) is

R′′-strategical with R′′ = (R_{u}^{(η)})_{u}^{(η−η^{∗})} = R_{u}^{(η)} which proves a). In this case there is nothing to prove for b), and c) follows from Lemma 3.7 applied to R_{u}^{(η^{∗},η)}. ■

Theorem 4.6. Let R be a resolution family and τ ∈ T with ℓ_{0}(τ) = η. If R is strongly continuous then the mapping Φ^{τ} is of class η.

\underline{Proof} : By induction on |τ| : for τ = ∅ the result is trivial since Φ^{∅} = Id. Suppose that the result is true for τ^{∗}, and set ℓ(τ) = (η, u) and ℓ(τ^{∗}) = (η^{∗}, u^{∗}).

– If |τ| is even then η = η^{∗} and Φ^{τ} = Ψ_{u} ∘ Φ^{τ^{∗}} where Ψ_{u} denotes the continuous mapping Σ ↦ Σ_{u}. Hence Φ^{τ} is of class η.

– If |τ| is odd then u = u^{∗} and Φ^{τ} = Φ_{R_{u}^{(η^{∗},η)}} ∘ Φ^{τ^{∗}} and by Theorem 3.10, Φ_{R_{u}^{(η^{∗},η)}} is of class η − η^{∗}. Hence Φ^{τ} is of class (η − η^{∗}) + η^{∗} = η. ■

4.7. Remark : As for Theorem 2.12 one can observe that the statement of the previous results can be considered for any transfinite family R, and the reader can check that what

7/10/2008 – 16:22 5. Adequate Baire types

we will really use in the proof of the dichotomy Theorem in Section 6 is the following (see Remark 2.13) :

Any family (B_{i})_{i∈I} of Borel subsets of ω^{ω} of type (Γ_{i})_{i∈I} admits a representation ⟨R, (S_{i})_{i∈I}⟩ of type (Γ_{i})_{i∈I} such that if we identify R to a family of tree relations on Dom(Ext_{I}) then the conclusions of Theorems 4.5 and 4.6 hold.

Moreover if (B_{i})_{i∈I} and (Γ_{i})_{i∈I} have codes in Δ_{1}^{1}(α) then ⟨R, (S_{i})_{i∈I}⟩ can be chosen with a code in Δ_{1}^{1}(α) too.

5 – ADEQUATE BAIRE TYPES

5.1. Notation : In all this section (Γ_{i})_{i∈I} will denote a Baire type of rank (ξ_{i})_{i∈I}. We shall be more particularly interested in the subfamily of (Γ_{i})_{i∈I} constituted by the multiplicative Baire classes. So let :

J := {j ∈ I : Γ_{j} = Π_{ξ_{j}}^{0}}

For all i ∈ I and ξ ∈ ω_{1} let :

J_{i} := {j ∈ J : Γ_{j} ⊂ Γ_{i}}; J(ξ) := {j ∈ J : Γ_{j} = Π_{ξ}^{0}}

and finally let :

Ω := {ξ_{j} : j ∈ J} ; λ := sup Ω

Definition 5.2. We shall say that the Baire type (Γ_{i})_{i∈I} is adequate if for all i ∈ I such that Γ_{i} ≠ Σ_{λ}^{0} the set J_{i} = {j ∈ J : Γ_{j} ⊂ Γ_{i}} is finite.

For example the Baire types : (Π_{k+1}^{0})_{k∈ω} , (Π_{k+1}^{0})_{k∈ω}^{⌢}⟨Σ_{ω}^{0}⟩ are adequate while (Π_{k+1}^{0})_{k∈ω}^{⌢}⟨Π_{ω}^{0}⟩ , (Π_{k+1}^{0})_{k∈ω}^{⌢}⟨Σ_{ω+1}^{0}⟩ are not. The following result will give a more concrete description of general adequate Baire types.

Proposition 5.3. The Baire type (Γ_{i})_{i∈I} is adequate if and only if either J is finite or else the following three conditions are fulfilled :

a) J(ξ) is finite for all ξ.

b) Ω is of order type ω.

c) λ = sup{ξ_{i} : i ∈ I}.

\underline{Proof} : If J is finite then (Γ_{i})_{i∈I} is obviously adequate. So we can assume that J is infinite. – Suppose that (Γ_{i})_{i∈I} is adequate. Firstly for all ξ ∈ ω_{1}, if ξ ∉ Ω then J(ξ) is empty ; if not then ξ = ξ_{i} for some i ∈ J

hence Γ_{i} = Π_{ξ_{i}}^{0} ≠ Σ_{λ}^{0} and so J_{i} is finite, and it follows that J(ξ) ⊂ J_{i} is finite too.

Secondly observe that since J = ⋃_{ξ∈Ω} J(ξ) is infinite then necessarily Ω is infinite. Moreover for all ξ = ξ_{i} ∈ Ω since Γ_{i} = Π_{ξ_{i}}^{0} ≠ Σ_{λ}^{0} then the set J_{i} is finite hence the set {η ∈ Ω : η ≤ ξ} = {ξ_{j} : j ∈ J_{i}} is finite too. This proves that Ω is of order type ω

Finally suppose that λ < ξ_{i} for some i ∈ I then Γ_{i} ≠ Σ_{λ}^{0} and J_{i} = J would be infinite which is a contradiction.

– Conversely suppose that a), b), c) hold and fix i ∈ I such that Γ_{i} ≠ Σ_{λ}^{0}.

Observe that by c) we necessarily have ξ_{i} ≤ λ. On the other hand if we had ξ_{i} = λ then we would necessarily have Γ_{i} = Π_{λ}^{0} hence ξ_{i} = λ ∈ Ω and so λ would be a non isolated element of the ordered set Ω which contradicts b). This proves that ξ_{i} < λ.

Now fix any η ∈ Ω such that ξ_{i} < η < λ; so J_{i} ⊂ ⋃_{ξ∈Ω∩[0,η]} J(ξ) and it follows then from a) and b) that J_{i} is finite. ■

Corollary 5.4. If the Baire type (Γ_{i})_{i∈I} is adequate and no Γ_{i} is an additive Baire class of limit rank then for all i ∈ I the set J_{i} = {j ∈ J : Γ_{j} ⊂ Γ_{i}} is finite.

\underline{Proof} : We may suppose that the set J is infinite. It follows then from condition b) of Proposition 5.3 that λ := sup{ξ_{j}; j ∈ J} is a limit ordinal. Hence for all i ∈ I, Γ_{i} ≠ Σ_{λ}^{0} and since (Γ_{i})_{i∈I} is adequate then the set J_{i} = {j ∈ J : Γ_{j} ⊂ Γ_{i}} is finite. ■

We will also need the following criterion.

Proposition 5.5. The Baire type (Γ_{i})_{i∈I} is non adequate if and only there exist i_{∗} ∈ I and ξ_{∗} ≤ λ such that Γ_{i_{∗}} ⊃ Π_{ξ_{∗}}^{0} and J_{∗} = {j ∈ J : ξ_{j} ≤ ξ_{∗}} is infinite.

Moreover if (Γ_{i})_{i∈I} has a code in Δ_{1}^{1}(α) then we can choose ξ_{∗} with code in Δ_{1}^{1}(α).

\underline{Proof} : The condition is clearly sufficient : since ξ_{∗} ≤ λ and Γ_{i_{∗}} ⊃ Π_{ξ_{∗}}^{0} then Γ_{i_{∗}} ≠ Σ_{λ}^{0} and J_{∗} ⊂ J_{i_{∗}}, hence J_{i_{∗}} is infinite and so (Γ_{i})_{i∈I} is not adequate.

Conversely suppose that (Γ_{i})_{i∈I} is not adequate. Then the set J is necessarily infinite hence at least one of the three conditions a), b), c) of Proposition 5.3 fails, and we distinguish the three cases :

– If condition a) fails take i_{∗} such that J(ξ_{i_{∗}}) is infinite and set ξ_{∗} = ξ_{i_{∗}} so that

J_{∗} ⊃ J(ξ_{i_{∗}}).

– If condition b) fails take i_{∗} such that ξ_{i_{∗}} ∈ Ω and Ω_{∗} := {ξ ∈ Ω : ξ ≤ ξ_{i_{∗}}} is infinite

and set ξ_{∗} = ξ_{i_{∗}} so that J_{∗} ⊃ {j ∈ J : ξ_{j} ∈ Ω_{∗}}.
– If condition c) fails take i_{∗} such that λ < ξ_{i_{∗}} and set ξ_{∗} = λ so that J_{∗} = J.

For the last part observe that one can always choose ξ_{∗} to be either ξ_{i_{∗}} or λ which both have codes in Δ_{1}^{1}(α). ■

6 – A DICHOTOMY FOR COANALYTIC COVERINGS

For the notion of weak reduction of families of sets see Definition 1.4.

Theorem 6.1. Let (Γ_{i})_{i∈I} be an adequate Baire type with code α ∈ ω^{ω}. Then for any Δ_{1}^{1}(α) family (B_{i})_{i∈I} of type (Γ_{i})_{i∈I} and any Π_{1}^{1}(α) covering (C_{i})_{i∈I} at least one of the following two alternatives holds :

– either (C_{i})_{i∈I} admits a Δ_{1}^{1}(α)-subordinate covering of type (Γ_{i})_{i∈I}

– or (B_{i})_{i∈I} is weakly reducible to (ω^{ω} \ C_{i})_{i∈I}

\underline{Proof} : The reader can check that all the arguments below are uniform in α so for simplicity we shall assume that α is Δ_{1}^{1}. For all i ∈ I let 1 + ξ_{i} be the rank of Γ_{i}; set ξ := sup_{i∈ω} ξ_{i} and :

I^{(+)} := {i ∈ I : Γ_{i} = Σ_{1+ξ_{i}}^{0}}  and  I^{(×)} := {i ∈ I : Γ_{i} = Π_{1+ξ_{i}}^{0}}

7/10/2008 – 16:22 6. A dichotomy for coanalytic coverings

\underline{First reduction step} : For technical reasons we shall actually prove the theorem when the adequate Baire type (Γ_{i})_{i∈I} satisfies some additional assumption, and then derive the general result from this particular case.

Let us say that an adequate Baire type (Γ_{i})_{i∈I} is \underline{regular} if no Γ_{i} is an additive Baire class of limit rank. So suppose that the theorem is already proved for any regular adequate Baire type, and consider now a non regular adequate Baire type (Γ_{i})_{i∈I}.

Consider the nonempty set J := {i ∈ I^{(+)} : ξ_{i} is limit} and fix for all j ∈ J a fundamental sequence (ξ^{(j,n)})_{n∈ω} for ξ_{j}, with each ξ^{(j,n)} a successor ordinal. Then J is clearly Δ_{1}^{1} and we can also assume that (ξ^{(j,n)})_{(j,n)∈J×ω} has a Δ_{1}^{1} code so we can find a Δ_{1}^{1} family (B_{(j,n)})_{(j,n)∈J×ω} such that B_{j} = ⋃_{n} B_{(j,n)} and B_{(j,n)} ∈ Σ_{ξ^{(j,n)}}^{0} for all j ∈ J.

Finally let K := (I \ J) + J × ω, and consider the Baire type (Γ̃_{k})_{k∈K}, the Δ_{1}^{1} family (B̃_{k})_{k∈K} and the Π_{1}^{1} covering (C̃_{k})_{k∈K} defined by :

Γ̃_{k} = Γ_{k} ; B̃_{k} = B_{k} ; C̃_{k} = C_{k} if k ∈ I \ J
Γ̃_{k} = Σ_{ξ^{(j,n)}}^{0}; B̃_{k} = B_{(j,n)}; C̃_{k} = C_{j} if k = (j, n) ∈ J × ω

Then (B̃_{k})_{k∈K} is clearly of Baire type (Γ̃_{k})_{k∈K} which is still adequate but also obviously regular ; moreover one can easily check that :

(1) If (C̃_{k})_{k∈K} admits a Δ_{1}^{1} subordinate covering (Ã_{k})_{k∈K} of type (Γ̃_{k})_{k∈K} and if we define (A_{i})_{i∈I} by :

\{ \begin{matrix}A_{i} = Ã_{i} & if i ∈ I \ J \\ A_{i} = ⋃_{n∈ω} Ã_{(i,n)} & if i ∈ J \end{matrix}

then (A_{i})_{i∈I} is a Δ_{1}^{1} subordinate covering to (C_{i})_{i∈I} of type (Γ_{i})_{i∈I}.

(2) If f is a weak reduction of (B̃_{k})_{k∈K} to (ω^{ω} \C̃_{k})_{k∈K} then f is also a weak reduction of (B_{i})_{i∈I} to (ω^{ω} \ C_{i})_{i∈I}.

From now on we suppose that the adequate Baire type (Γ_{i})_{i∈I} is regular. In particular (see Corollary 5.4) for all i ∈ I the set {j ∈ I^{(×)} : Γ_{j} ⊂ Γ_{i}} is finite.

As explained in the Introduction our plan is to define an open game G such that if Player I wins then the first alternative of Theorem 6.1 holds, and if Player II wins then the second alternative holds.

Fix a Π_{1}^{1} covering (C_{i})_{i∈ω} and a Δ_{1}^{1} sequence (T_{i})_{i∈ω} of trees on ω × ω such that for all i the projection of the set ⌈T_{i}⌉ (that we identify to a closed subset of ω^{ω} × ω^{ω}) on the first factor is the Σ_{1}^{1} set ω^{ω} \ C_{i}.

We identify any tree T on ω ×ω to a subset of ⋃_{n∈ω} ω^{n} ×ω^{n}. Then given an arbitrary pair (t, θ) ∈ Seq(ω) × Seq(ω) we shall say that (t, θ) is \underline{compatible} with T if (t_{|k}, θ_{|k}) ∈ T where k = Dom(t) ∩ Dom(θ).

Applying Theorem 2.12 we also fix a Δ_{1}^{1}-representation ⟨(R^{(η)})_{η≤ξ}, (S_{i})_{i∈I}⟩ of type (Γ_{i})_{i∈I} for (B_{i})_{i∈I}. We recall that S_{i} ⊂ Seq(ω) is such that S_{i} is R^{(ξ_{i})}-monotone if i ∈ I^{(+)}, and R^{(ξ_{i})}-hereditary if i ∈ I^{(×)} ; moreover for all x ∈ ω^{ω} if x̂^{(ξ_{i})} = {x_{|k_{n}}; n ∈ ω} is the unique R^{(ξ_{i})}-branch determined by x then :

\{ \begin{matrix}(x ∈ B_{i} ⟺ ∃n, x_{|k_{n}} ∈ S_{i}) if i ∈ I^{(+)} \\ (x ∈ B_{i} ⟺ ∀n, x_{|k_{n}} ∈ S_{i}) if i ∈ I^{(×)} \end{matrix}

\underline{Second reduction step} : We shall also assume that

⋃_{i∈I} S_{i} = Seq(ω) and I^{(×)} is infinite

To see that this reduction is justified observe that starting from any adequate Baire type (Γ_{i})_{i∈I} we can always find an infinite increasing sequence (η_{n})_{n∈ω} of ordinals with Δ_{1}^{1} code such that the Baire type (Γ_{i})_{i∈I}^{⌢}(Π_{1+η_{n}}^{0})_{n∈ω} is still adequate. Indeed :

– if I^{(×)} is finite one can take for (η_{n})_{n∈ω} any increasing sequence beyond ξ.

– if I^{(×)} is infinite one can take for (η_{n})_{n∈ω} the increasing enumeration of {ξ; i ∈ I^{(×)}}. Moreoever if (Γ_{i})_{i∈I} is regular then obviously (Γ_{i})_{i∈I}^{⌢}(Π_{1+η_{n}}^{0})_{n∈ω} is regular too. Then defining for all n ∈ ω : Γ_{n} := Π_{1+η_{n}}^{0} , B_{n} = C_{n} = ∅ and S_{n} := {s^{(n)} _{|k}; k ≤ |s^{(n)}|} where (s^{(n)})_{n∈ω} is any recursive enuemeration of Seq(ω), it is clear that ⟨Γ_{i}, S_{i}⟩_{i∈I+ω} is also a Δ_{1}^{1}-representation of (B_{i})_{i∈I+ω} and ⋃_{i∈I+ω} S_{i} = Seq(ω). And I^{(×)} + ω is infinite. Finally one easily checks that if the theorem holds for ⟨Γ_{i}, S_{i}, B_{i}, C_{i}⟩_{i∈I+ω} then it also holds for ⟨Γ_{i}, S_{i}, B_{i}, C_{i}⟩_{i∈I}.

\underline{Notation} : For any s ∈ Seq(ω) let :
μ(s) := min{ξ_{j} : s ∈ S_{j}}
I(s) := {i ∈ I : ξ_{i} = μ(s) and s ∈ S_{i}}
J(s) := \{ \begin{matrix}I(s) ∩ I^{(+)} & if this set is non empty \\ I(s) & if I(s) ⊂ I^{(×)} \end{matrix}

To give the intuition behind the definition of J(s) recall that each S_{j} is a coding for the Borel set B_{j}, and the relation “s ∈ S_{j}” should be interpreted as an “indication” that s “might” be the beginning of a real x in B_{j}. Our aim is to define a “guess” procedure which will determine some j such that x ∈ B_{j}. Thus in defining η = μ(s) we are looking for such a B_{j} of minimal Borel rank, and among all possible B_{j} of this minimal rank 1 + η, the definition of J(s) gives the priority to Σ_{1+η}^{0} sets in opposition to Π_{1+η}^{0} sets. The last step will be to choose some particular j ∈ J(s) ; and this will be achieved through the game that we introduce now.

\underline{The game G} : A run in the game G will go as follows :

Player I : s_{0}  s_{1}  …  s_{n}  …
Player II :  (t_{0}, i_{0}, θ_{0})  (t_{1}, i_{1}, θ_{1})  …  (t_{n}, i_{n}, θ_{n})  …

with s_{n} ∈ 2^{n+1} and (t_{n}, i_{n}, θ_{n}) ∈ 2^{n+1} × I × Seq(ω) and satisfying the following rules :

(R_{0}) : s_{n−1} ≺ s_{n} and t_{n−1} ≺ t_{n}
(R_{1}) : i_{n} ∈ J(s_{n}) (hence ξ_{i_{n}} = μ(s_{n}) )
(R_{2}) : (t_{n}, θ_{n}) is compatible with T_{i_{n}}
(R_{3}) : If s_{m} is the R^{(μ(s_{n}))}-predecessor of s_{n} then :
\{ \begin{matrix}– If μ(s_{m}) = μ(s_{n}) and J(s_{m}) ⊂ I^{(+)} then i_{m} = i_{n} and θ_{m} ≺ θ_{n} \\ – If J(s_{m}) = J(s_{n}) ⊂ I^{(×)} then i_{m} = i_{n} and θ_{m} ≺ θ_{n} \end{matrix}

where by convention s_{−1} = ∅.

Observe that if J(s_{m}) = J(s_{n}) then μ(s_{m}) = μ(s_{n}) but the converse is not true. Notice also that rule (R_{3}) is coherent with rule (R_{1}) : indeed by (R_{1}) we already have s_{m} ∈ S_{i_{m}} and if moreover i_{m} ∈ I^{(+)} then S_{i_{m}} is R^{(η_{n})}-monotone and since ξ_{i_{n}} = ξ_{i_{m}} and s_{m} R^{η_{n}} s_{n} then s_{n} ∈ S_{i_{m}}, so i_{m} ∈ J(s_{n}) hence the choice i_{n} = i_{m} respects rule (R_{1}).

\underline{Fact} 1 : Suppose that s_{m} R^{(μ(s_{n}))} s_{n}. Then :
– either μ(s_{m}) ≠ μ(s_{n}) hence J(s_{m}) ∩ J(s_{n}) = ∅
– or μ(s_{m}) = μ(s_{n}), J(s_{m}) ⊂ I^{(×)} and J(s_{n}) ⊂ I^{(+)} hence J(s_{m}) ∩ J(s_{n}) = ∅
– or μ(s_{m}) = μ(s_{n}) and J(s_{m}) ⊂ J(s_{n}) ⊂ I^{(+)}
– or μ(s_{m}) = μ(s_{n}) and J(s_{n}) ⊂ J(s_{m}) ⊂ I^{(×)}

\underline{Proof} : If μ(s_{m}) ≠ μ(s_{n}) then obviously J(s_{m}) ∩ J(s_{n}) = ∅. So suppose that μ(s_{m}) = μ(s_{n}) = η :

– If J(s_{m}) ⊂ I^{(+)} then for all i ∈ J(s_{m}), S_{i} is R^{(η)}-monotone and since s_{m} ∈ S_{i} then s_{n} ∈ S_{i} hence ∅ ≠ J(s_{m}) ⊂ I(s_{n}) ∩ I^{(+)} = J(s_{n}) ⊂ I^{(+)}.

– If J(s_{n}) ⊂ I^{(×)} then for all i ∈ J(s_{n}), S_{i} is R^{(η)}-hereditary and since s_{n} ∈ S_{i} then s_{m} ∈ S_{i} hence J(s_{n}) ⊂ I(s_{m}) = J(s_{m}) ⊂ I^{(×)}.

– Otherwise J(s_{m}) ⊂ I^{(×)} and J(s_{n}) ⊂ I^{(+)} and again J(s_{m}) ∩ J(s_{n}) = ∅. ⋄

It follows from Fact 1 that rule (R_{3}) can be reformulated by the following unique condition :

(R′_{3}) : If s_{m} is the R^{(μ(s_{n}))}-predecessor of s_{n} and J(s_{m}) ⊂ J(s_{n})

then i_{m} = i_{n} and θ_{m} ≺ θ_{n}

\underline{Initializing positions} : Let u be a I-position in G. We shall say that u is an initializing position if

J(s_{m}) ⊄ J(s_{n})

where s_{n} denotes the last I-move in u and s_{m} denotes the R^{(μ(s_{n}))} predecessor of s_{n}.

In particular if u is an initializing position then rule (R_{3}) is irrelevant, and the next move in the game (which has to be made by Player II) can be of the form (t, i, ∅) for any i ∈ J(s_{n}).

By the same arguments as in Fact 1 one can easily prove the following result which will be of very common use in the sequel.

\underline{Fact} 2 : Suppose that s_{m} R^{(η)} s_{n}.
– if μ(s_{m}) ≤ η and J(s_{m}) ⊂ I^{(+)} then μ(s_{n}) ≤ μ(s_{m})
– if μ(s_{n}) ≤ η and J(s_{n}) ⊂ I^{(×)} then μ(s_{m}) ≤ μ(s_{n})

Lemma 6.2. If Player II wins the game G then (B_{i})_{i∈I} is weakly reducible to (ω^{ω} \C_{i})_{i∈I}.

\underline{Proof} : A winning strategy σ for Player II in the game G defines a continuous mapping F : x ↦ (y, (i_{n})_{n∈ω}, (θ_{n})_{n∈ω}) from ω^{ω} to ω^{ω} × I^{ω} × Seq(ω)^{ω} such that for all x and all n, x_{|n} = σ(y_{|m}, i_{m}, θ_{m})_{m≤n}. So fix such a mapping F and let f : ω^{ω} → ω^{ω} denote its first coordinate. We shall prove that f is a weak reduction of (B_{i})_{i∈I} to (ω^{ω} \ C_{i})_{i∈I}. For this fix x ∈ ⋃_{j∈ω} B_{j} ; set F (x) = (y, (i_{n})_{n∈ω}, (θ_{n})_{n∈ω}), so y = f(x) and let :

η = min{ξ_{i}; x ∈ B_{i}} and I(η, x) = {i ∈ I : ξ_{i} = η and x ∈ B_{i}}

Finally let (s_{n}^{(η)})_{n∈ω} be the increasing enumeration of x̂^{(η)} (the R^{(η)}-branch contained in x̂ := {x_{|n}; n ∈ ω}), and set k_{n} := |s_{n}^{(η)}| − 1 so that s_{n}^{(η)} = s_{k_{n}} (with the notations used in the rules of the game above).

Consider then the set H = {j ∈ I^{(×)} : ξ_{j} < η} which, by the adequateness and regularity assumption, is finite. It follows from the minimality of η that for all j ∈ H, x ∉ B_{j} hence the set x̂^{(ξ_{j})} ∩ S_{j} is finite and a fortiori the set x̂^{(η)} ∩ S_{j} is finite too. Hence we can find n_{0} such that for all j ∈ H and all n ≥ n_{0}, s_{n}^{(η)} ∉ S_{j}. For the rest of the proof we distinguish the two cases :

– Case 1 : I(η, x) ∩ I^{(+)} ≠ ∅.

Pick any j_{0} ∈ I(η, x) ∩ I^{(+)} : since x ∈ B_{j_{0}}, there exists some m_{0} such that s_{m_{0}}^{(η)} ∈ S_{j_{0}}, and since S_{j_{0}} is R^{(η)}-monotone then s_{n}^{(η)} ∈ S_{j_{0}} for all n ≥ m_{0}. Finally let n_{∗} := max(n_{0}, m_{0}) and j_{∗} := i_{k_{n∗}}. It follows from rule (R_{1}) and from the choice of n_{0} and m_{0} that ξ_{j_{∗}} = ξ_{j_{0}} = η; and since j_{0} ∈ I(η, s_{n_{∗}}^{(η)}) ∩ I^{(+)} then j_{∗} ∈ I^{(+)}, so s_{n_{∗}}^{(η)} ∈ S_{j_{∗}} and S_{j_{∗}} is R^{η}-monotone hence x ∈ B_{j_{∗}}. Moreover since j_{∗} ∈ I^{(+)} then by additive part of rule (R_{3}) for all n > m ≥ n_{∗} we have i_{k_{m}} = j_{∗} and θ_{k_{m}} ≺ θ_{k_{n}} so θ = ⋃_{m≥n} θ_{k_{m}} ∈ ω^{ω} and it follows from rule (R_{2}) that (y, θ) ∈ ⌈T_{j_{∗}}⌉ hence y ∈ ω^{ω} \ C_{j_{∗}}.

– Case 2 : I(η, x) ⊂ I^{(×)}.

Again pick any j_{0} ∈ I(η, x) ⊂ I^{(×)} : since x ∈ B_{j_{0}} and S_{j_{0}} is R^{(η)}-hereditary then s_{n}^{(η)} ∈ S_{j_{0}} for all n; it follows that for all n ≥ n_{0}, ξ_{i_{kn}} = ξ_{j_{0}} = η. Hence by Fact 1 for all n > m ≥ n_{0} we have I(η, s_{n}^{(η)}) ⊂ I(η, s_{m}^{(η)}) ⊂ I^{(×)}, and since these sets are finite there exists some n_{∗} ≥ n_{0} such that I(η, s_{n}) = I(η, s_{n_{∗}}) for all n ≥ n_{∗}. Finally set j_{∗} := i_{k_{n∗}} then applying the multiplicative part of rule (R_{3}) one can prove as in Case 1 that x ∈ B_{j_{∗}} and y ∈ ω^{ω} \ C_{j_{∗}}. ■

From now we fix a winning strategy Σ for Player I in the game G. Our goal is to define explicitly from Σ a Δ_{1}^{1} covering (A_{i})_{i∈I} of type (Γ_{i})_{i∈I} which is subordinate to (C_{i})_{i∈I}.

\underline{Notation} : For any u ∈ Dom(Ext_{I}) let :

s̃(u) = \{ \begin{matrix}∅ & if u = ∅ \\ s_{n} & if u = (s_{0}, t_{0}, i_{0}, θ_{0}, …, s_{n}) \end{matrix}

we also set :

μ̃(u) := μ(s̃(u)) and J̃(u) := J(s̃(u))

We then consider on Dom(Ext_{I}) the resolution family R̃ = (R̃^{(η)})_{η≤ξ} defined by :

u R̃^{(η)} v ⟺ (u ⪯ v) and (s̃(u) R^{(η)} s̃(v))

Thus R̃^{(0)} = Ext_{I} and identifying G to a game on ω we can apply all the material of Section 4 to R̃. In particular we shall consider the tree T and for τ ∈ T , the sets S^{τ} and the mappings Φ^{τ} introduced in Section 4.4. If τ ∈ T with ℓ_{1}(τ) = u we also set :

J̃(τ) := J̃(u)

For all y ∈ ω^{ω} let Σ_{y} denote the set of all positions v ∈ Σ which are compatible with y in the sense that all Player II’s moves in v are of the form (y_{|n}, i, θ). Since Σ is a quasi-strategy (for Player I) then Σ_{y} too is a quasi-strategy that is an R̃^{(0)}-strategical set, so we can define for all τ ∈ T :

Σ_{y}^{(τ)}= Φ^{τ} (Σ_{y})

we also set :

Λ_{y}^{(τ)}= {v ∈ Φ^{τ} (Σ_{y}) : v is a I-position }

We recall that by Theorem 4.5 if Σ_{y} ∈ S^{τ} with ℓ(τ) = (η, u) then Σ_{y}^{(τ)} is R̃_{u}^{(η)}-strategical.

Definition 6.3. Let τ ∈ T with ℓ_{1}(τ) = u. We shall say that τ is optimal for y ∈ ω^{ω} if :

1) u is an initializing position.

2) Σ_{y} ∈ S^{(τ)}

3) For all v ∈ Λ_{y}^{(τ)}, J̃(u) ⊂ J̃(v)

This notion will play a crucial role in the proof. Let us recall that an initializing position is by definition a I-position hence nonempty ; and a fortiori if τ ∈ T is optimal for y, it is nonempty since ℓ_{1}(τ) ≠ ∅. .

Lemma 6.4. If τ ∈ T is optimal for y then for all i ∈ J̃(τ), y ∈ C_{i}.

\underline{Proof} : Suppose that τ ∈ T is optimal for y; set (η, u) = ℓ(τ) and fix i ∈ J̃(τ) = J̃(u). Observe first that if |τ| is odd then τ^{∗} is also optimal for y since in this case S^{(τ^{∗})}=S^{(τ)} and ℓ_{1}(τ^{∗}) = ℓ_{1}(τ) = u. Hence we may suppose that |τ| is even.

We shall argue by contradiction : assuming that y ∉ C_{i} we shall construct an infinite run in the game (Σ_{y})^{(R)} (see Section 3.2) with R= R̃_{u}^{(η)}. Such a run induces canonically an infinite run in the game G compatible with the strategy Σ, and this is absurd since Σ is winning for Player I in the game G.

If y ∉ C_{i} we can fix θ ∈ ω^{ω} such that (y, θ) ∈ ⌈T_{i}⌉. Set |u| = 2k + 1 and consider in the game (Σ_{y})^{(R)} the run in which, starting with u_{0} = u for the first move, Player I chooses at each move some u_{m} ∈ Λ_{y}^{(τ)} to which Player II answers a_{m} = (y_{|k+1+m}, i, θ_{|m}). We have to check that all these moves are possible and legal in the game (Σ_{y})^{(R)}.

– For m = 0, observe that since |τ| is even then by Theorem 4.5 b), u ∈ Λ_{y}^{(τ)} and it follows from the definition of the relation R= R̃_{u}^{(η)} that the R-predecessor of u is ∅ so u_{0} = u is a legal first move in (Σ_{y})^{(R)}. Moreover since i ∈ J̃(u) and u is an initializing position then a_{0} = (y_{|k+1+m}, i, ∅) is a legal move for Player II in the game Σ_{y}, hence in (Σ_{y})^{(R)}.

– Suppose that for m > 0 the first m moves of both players are legal in (Σ_{y})^{(R)}. Then u_{m−1} ∈ Λ_{y}^{(τ)} and u_{m−1} = v^{∗} where v is the II-position defined by v = u_{m−1}^{⌢}⟨a_{m−1}⟩ ∈ Σ_{y}. Since Σ_{y} ∈ S^{τ} then by Theorem 4.5 a), the set Σ_{y}^{(τ)} is R-strategical, hence we can find some u_{m} ∈ Λ_{y}^{(τ)} such that v ≺ u_{m−1} and u_{m−1} is the R-predecessor of u_{m}. This proves the existence of u_{m}. Finally since J̃(u_{0}) ⊂ J̃(u_{m}) it follows from rules (R) and (R_{2}) of the game G that a_{m} = (y_{|k+1+m}, i, θ_{|m}) is a legal move for Player II in the game Σ_{y} hence in (Σ_{y})^{(R)}.

So this run is infinite and this gives the contradiction. ■

If for a fixed i we consider the set :

Ã_{i} = {y ∈ ω^{ω} : ∃ τ ∈ T optimal for y such that i ∈ J̃(τ)}

then Lemma 6.4 asserts that Ã_{i} ⊂ C_{i}, so the family (Ã_{i})_{i∈I} is subordinate to (C_{i})_{i∈I}. In fact we shall prove that (Ã_{i})_{i∈I} is actually a covering of ω^{ω}. Also basing on Theorem 4.6 it is not difficult to see that Ã_{i} is Borel : unfortunately the natural syntactical analysis of Ã_{i} gives that this set is Σ_{1+ξ_{i}+1}^{0}. Also our strategy will be to define a subset A_{i} ⊂ Ã_{i} of lower complexity, namely A_{i} ∈ Γ_{i}, and such that (A_{i})_{i∈I} is still a covering of ω^{ω}. More precisely we shall construct a mapping y ↦ σ_{y} from ω^{ω} to T such that for all y, σ_{y} is optimal for y and then define :

A_{i} = {y : i ∈ J̃(σ_{y})} ⊂ Ã_{i} ⊂ C_{i}

Then (A_{i})_{i∈I} will be a subordinate covering to (C_{i})_{i∈I}. The difficulty is that we will have to control simultaneously the pointwise condition “σ_{y} is optimal for y” and the global condition “A_{i} ∈ Γ_{i}”.

\underline{Notation} : We fix on Dom(Ext_{I}) a Δ_{1}^{1} total ordering ◁ of type ω satisfying :
u ≺ v ⟹ u ◁ v

and equip the space ω_{1} × Dom(Ext_{I}) with the lexicographical product ordering <_{lex} defined by :

(η, v) <_{lex} (ζ, w) ⟺ (η < ζ) or (η = ζ and v ◁ w)

Let also

Ω := {ξ_{i}; i ∈ I^{(×)}}

Since I^{(×)} was supposed to be infinite this set is infinite and since the Baire type (Γ_{i})_{i∈I} is adequate then Ω is of order type ω, and for all η < ξ we define :

η^{+} := min{η′ ∈ Ω : η < η′}

Definition 6.5. Set τ_{−1} = ∅ and (η_{−1}, v_{−1}) = (−1, ∅).

For any y ∈ ω^{ω} let φ(y) = (η_{m}, v_{m}, τ_{m})_{m} be the sequence with maximal domain defined inductively for m ≥ 0 by :

(η_{m}, v_{m}) := the <_{lex}-minimum element (ζ, w) ∈ [η_{m−1}, ω_{1}[×Λ_{y}^{(τ_{m−1}^{⌢}⟨ζ⟩)}

satisfying at least one of the following three conditions :

\{ \begin{matrix}(i) : & “ η_{m−1} = μ̃(v_{m−1}) = ζ ≤ μ̃(w) , J̃(v_{m−1}) ⊄ J̃(w) ” \\ (ii) : & “ η_{m−1} < μ̃(v_{m−1}) , ζ = μ̃(w) < ηm−1^{+} , J̃(w) ⊂ I^{(+)} ” \\ (iii) : & “ η_{m−1} < μ̃(v_{m−1}) , ζ = ηm−1^{+} ≤ μ̃(w) ” \end{matrix}
τ_{m} = (η_{0}, v_{0}, η_{1}, . . . . . . , v_{m−1}, η_{m}, v_{m})

Finally let :

σ_{y} = ⋃_{m} τ_{m}

6.6. Remarks : This definition calls for some comments.

a) Let (j) denote any of conditions (i), (ii), (iii) above. In the sequel we shall view such a condition as a formula ψ^{(j)}(η_{m−1}, v_{m−1}, ζ, w) with parameters η_{m−1}, v_{m−1} and variables ζ, w. Also when there is no ambiguity on the parameters η_{m−1}, v_{m−1} we shall simply say that “(ζ, w) satisfies (j) at level m” to mean that ψ^{(j)}(η_{m−1}, v_{m−1}, ζ, w) holds.

b) Notice that in each of these conditions ζ is entirely determined by w (and η_{m−1}) but the point is that we minimize with respect to the lexicographical ordering, hence first on ζ and then on w. This is namely the case in (ii) ; however in (i) and (iii), ζ is constant (ζ = η_{m−1} or ηm−1^{+}), and in these two cases the minimization is just over w with respect to the linear ordering ◁.

c) On a more semantical level one can divide the positions v_{m} occuring in σ_{y} into two groups depending whether : (1) η_{m} = μ(v_{m}) or (2) η_{m} < μ(v_{m}). As we shall see the role of the positions in the first group is to ensure that the sequence σ_{y} is optimal for y, while positions of the second group are just coding some informations about the values of the η_{m} which will enable us to control some complexity computations later on.

From the previous definition we clearly have :

η_{m−1} ≤ η_{m} ≤ μ(v_{m}) and v_{m−1} ⪯ v_{m}

in particular τ_{m} ∈ T , but as we shall see next we even have : v_{m−1} R̃^{(η_{m−1})} v_{m}

\underline{Fact} 3 : a) Σ_{y} ∈ S^{τ_{m}} ;  b) v_{m} ∈ Λ_{y}^{(τ_{m})} ;  c) For all v ∈ Λ_{y}^{(τ_{m})}, v_{m} R̃^{(η_{m})} v

\underline{Proof} : a) Observe first that |τ_{m}| is even and ℓ_{1}(τ_{m}) = v_{m}; also from the definition of φ we have : v_{m} ∈ Σ_{y}^{(τ_{m−1}^{⌢}⟨η_{m}⟩)} = Σ_{y}^{(τ_{m}^{∗})}. It follows then by induction that Σ_{y} ∈ S^{τ_{m}}.

b) Since |τ_{m}| is even this follows from Theorem 4.5 b).

c) Observe that Σ_{y}^{(τ_{m})} ⊂ (Σ_{y})_{v_{m}} hence v_{m}, v ∈ Λ_{y}^{(τ_{m})} with v_{m} R̃^{(0)} v, and the result follows from Theorem 4.5 c). ⋄

Lemma 6.7. For all y the sequence σ_{y} is finite.

\underline{Proof} : Notice that if (η_{m}, v_{m}) satisfies (i) then v_{m−1} ≺ v_{m}; and if it satisfies (iii) then η_{m−1} < η_{m}; finally if it satisfies (ii) and η_{m−1} = η_{m} then we have η_{m−1} = η_{m} = μ̃(v_{m}) < μ̃(v_{m−1}) hence v_{m−1} ≺ v_{m}. This proves that (η_{m}, v_{m}) ≠ (η_{m−1}, v_{m−1}).

Assume now that σ_{y} is infinite. Since all the v_{m} are compatible with the fixed winning strategy Σ for Player I in the game G, the sequence (v_{m})_{m} is eventually constant, say v_{m} = v_{n} for m ⩾ n. Thus η_{m−1} < η_{m} for m > n. So (η_{m}, v_{m}) cannot satisfy (i) for any m > n. Moreover if (η_{m}, v_{m}) satisfies (ii) for some m > n then we would have

μ̃(v_{n}) = μ̃(v_{m}) = η_{m} < η_{m+1} ⩽ μ̃(v_{m+1}) = μ̃(v_{n})

which is absurd. Hence (η_{m}, v_{m}) satisfies (iii) for all m > n. It follows that η_{m} = η_{m−1}^{+} ∈ Ω and η_{m−1} < η_{m} ⩽ μ(v_{m}) = μ(v_{n}) for each m > n. But since {η ∈ Ω : η ⩽ μ(v_{n})} is finite, this is impossible. ■

Lemma 6.8. For all y the sequence σ_{y} is optimal for y.

\underline{Proof} : Fix y and set φ(y) = (η_{m}, v_{m}, τ_{m})_{m≤n}. In all the sequel m denotes an arbitrary integer ≤ n.

\underline{Fact} 4 : If m < n and μ̃(v_{m}) = η_{m} then J̃(v_{m}) ⊂ I^{(×)}.

\underline{Proof} : Suppose that for some m < n we have μ̃(v_{m}) = η_{m} and J̃(v_{m}) ⊂ I^{(+)} then v_{m+1} is necessarily defined by condition (i) hence η_{m+1} = η_{m} ≤ μ̃(v_{m+1}). But since J̃(v_{m}) ⊂ I^{(+)} and v_{m}R̃^{(η_{m})}v_{m+1} then (Fact 2) μ̃(v_{m+1}) ≤ μ̃(v_{m}). Hence μ̃(v_{m+1}) = μ̃(v_{m}) and so (Fact 1) J̃(v_{m}) ⊂ J̃(v_{m+1}) which contradicts (i). ⋄

\underline{Fact} 5 : The set \{η_{m}; m < n\} is an initial segment of Ω.

\underline{Proof} : Fix m < n : by Fact 4, (η_{m}, v_{m}) cannot be defined by condition (ii) ; hence :

– If η_{m−1} < μ̃(v_{m−1}) then (η_{m}, v_{m}) is defined by condition (iii) hence η_{m} = ηm−1^{+} ∈ Ω.

– If η_{m−1} = μ̃(v_{m−1}) then (η_{m}, v_{m}) is defined by condition (i) and η_{m} = η_{m−1}. But again by Fact 4 in this case we necessarily have J̃(v_{m−1}) ⊂ I^{(×)} hence η_{m} = η_{m−1} ∈ Ω.

The conclusion follows then by a straightforward induction. ⋄

\underline{Fact} 6 : For all w ∈ Λ_{y}^{(τ_{m})} we have μ̃(w) ≥ η_{m}.

\underline{Proof} : Assume that w ∈ Λ_{y}^{(η_{m})} is such that μ̃(w) < η_{m} ≤ μ̃(v_{m}). By Fact 3 we have v_{m} R̃^{(η_{m})} w hence (Fact 2) J̃(w) ⊂ I^{(+)}. Moreover since τ_{m} = τ_{m−1}^{⌢}(η_{m}, v_{m}) and μ̃(w) < η_{m} then w ∈ Λ_{y}^{(τ_{m−1}^{⌢}⟨η_{m}⟩)} ⊂ Λ_{y}^{(τ_{m−1}^{⌢}⟨μ̃(w)⟩)}. Finally by Fact 5 there exists a unique k < m such that η_{k} ≤ μ̃(w) < ηk^{+} = η_{k+1}. This proves that (μ̃(w), w) satisfies condition (ii) at level k + 1.

Since η_{k} < η_{k+1} then (η_{k+1}, v_{k+1}) is not defined by condition (i) ; by the previous observations, (η_{k+1}, v_{k+1}) is necessarily defined by condition (ii). Hence (η_{k+1}, v_{k+1}) satisfies condition (ii) and so : J̃(v_{k+1}) ⊂ I^{(+)} and η_{k} ≤ μ̃(v_{k+1}) < ηk^{+} = η_{k+1} ; but since

v_{k+1} R̃^{(η_{k+1})} v_{m} then (Fact 2) we have η_{m} ≤ μ̃(v_{m}) ≤ μ̃(v_{k+1}) < ηk^{+} = η_{k+1}, which is

impossible. ⋄

\underline{Fact} 7 : v_{m} is an initializing position.

\underline{Proof} : Let v be the R̃^{(μ(v_{m}))}-predecessor of v_{m}; we have to show that J̃(v) ⊄ J̃(v_{m}). Notice that since η_{m} ≤ μ(v_{m}) then v R̃^{(η_{m})} v_{m}. Let k ≤ m be the unique integer such that v_{k−1} ⪯ v ≺ v_{k} ; since v_{m} ∈ Λ_{y}^{(τ_{m})} ⊂ Λ_{y}^{(τ_{k−1})} and v_{k−1} ⪯ v R̃^{(η_{k−1})} v_{m} then by Theorem 4.5 d), v ∈ Λ_{y}^{(τ_{k−1})}. We now distinguish two cases :

– Case 1 : η_{k−1} = μ̃(v_{k−1}).

In this case (η_{k}, v_{k}) is necessarily defined by condition (i). So η_{k−1} = η_{k} ≤ μ̃(v_{k}) and since v ≺ v_{k} then by the ◁-minimality of v_{k} we necessarily have J̃(v_{k−1}) = J̃(v) ⊄ J̃(v_{k}) and a fortiori μ̃(v_{k−1}) = μ̃(v), hence η_{k−1} = η_{k} = μ̃(v) ≤ η_{m} ≤ μ̃(v_{m}). Moreover by Fact 4 J̃(v_{k−1}) = J̃(v) ⊂ I^{(×)}.

Observe that if either J̃(v_{m}) ⊂ I^{(+)} or μ̃(v) < μ̃(v_{m}) then obviously J̃(v) ∩ J̃(v_{m}) = ∅ and we are done. So we may assume that : (1) J̃(v_{m}) ⊂ I^{(×)} and (2) μ̃(v) = μ̃(v_{m}).

Consider now an arbitrary j ∈ [k, m]. If j < m ≤ n then it follows from Fact 4 that J̃(v_{j}) ⊂ I^{(×)}, and by (1) this is also true for j = m; hence (η_{j}, v_{j}) is not defined by condition (ii). On the other hand it follows from (2) that η_{k−1} = η_{j−1} = η_{j} = η_{m} so (η_{j}, v_{j}) is not defined by condition (iii). Hence (η_{j}, v_{j}) is defined by condition (i) and we necessarily have η_{j−1} = μ̃(v_{j−1}) ; but again by (2) we also have η_{m} = μ̃(v_{m}). This proves that for all j ∈ [k, m] we have μ̃(v_{j}) = μ̃(v_{j−1}) and J̃(v_{j}) ⊄ J̃(v_{j−1}) ⊂ I^{(×)}. Hence by Fact 1 we necessarily have : J̃(v_{k−1}) = J̃(v) ⫌ J̃(v_{k−1})⫌J̃(v_{j}) ⫌ J̃(v_{m}) which proves that J̃(v) ⊄ J̃(v_{m}).

– Case 2 : η_{k−1} < μ̃(v_{k−1}).

In this case (η_{k}, v_{k}) is defined either by condition (ii) or by condition (iii), but as we shall see the last alternative never occurs. Observe first that by Fact 6, μ̃(v) ≥ η_{k−1} and we now distinguish two subcases :

– Case 2.a : η_{k−1} ≤ μ̃(v) < ηk−1^{+}.

We claim that in this case J̃(v) ⊂ I^{(+)}. For otherwise we would necessarily have μ̃(v) = η_{k−1} and since v_{k−1} R̃^{(η_{k−1})} v then by Fact 2 we would have μ̃(v_{k−1}) ≤ μ̃(v) = η_{k−1} which contradicts the assumption of Case 2.

So J̃(v) ⊂ I^{(+)} and since v ∈ Λ_{y}^{(τ_{k−1})} then (μ̃(v), v) satisfies condition (ii) at level k which proves that (η_{k}, v_{k}) is actually defined by condition (ii) hence μ̃(v_{k}) = η_{k} and (η_{k}, v_{k}) <_{lex} (μ̃(v), v). Moreover by Fact 4 we necessarily have k = m = n. So μ̃(v_{m}) = η_{m} and (η_{m}, v_{m}) <_{lex} (μ̃(v), v) and since v ◁ v_{m} then η_{m} = μ̃(v_{m}) < μ̃(v) and a fortiori J̃(v) ∩ J̃(v_{m}) = ∅.

– Case 2.b : ηk−1^{+} ≤ μ̃(v).

Again since v ∈ Λ_{y}^{(τ_{k−1})} then in this case (ηk−1^{+}, v) satisfies condition (iii). But we claim that (η_{k}, v_{k}) is actually defined by condition (ii). For otherwise it would be defined by condition (iii) and then η_{k} = ηk−1^{+} and (ηk−1^{+}, v_{k}) <_{lex} (ηk−1^{+}, v) which is impossible since v ◁ v_{k}.

So (η_{k}, v_{k}) is defined by condition (ii). In particular μ̃(v_{k}) < ηk−1^{+} and J̃(v_{k}) ⊂ I^{(+)}, and as in the previous case this implies that k = m. Hence μ̃(v_{m}) < ηm−1^{+} ≤ μ̃(v) and again J̃(v) ∩ J̃(v_{m}) = ∅. ⋄

\underline{Fact} 8 : μ̃(v_{n}) = η_{n}, and σ_{y} ≠ ∅.

\underline{Proof} : Suppose by contradiction that η_{n} < μ̃(v_{n}) ; we shall show that one can extend the sequence φ(y) by the induction scheme of Definition 6.5 by defining (η_{n+1}, v_{n+1}), which will contradict the maximality of φ(y). In fact it is sufficient to find some (ζ, w) satisfying one of conditions (i), (ii) or (iii) at level n + 1, but since μ̃(v_{n}) < η_{n} then condition (i) will never be realized.

By Fact 3, Σ_{y} ∈ S^{τ_{n}} and since |τ_{n}| is even then Σ_{y} ∈ S^{τ_{n}^{⌢}⟨ξ⟩} so by Theorem 4.5 a) the set Σ_{y}^{(τ_{n}^{⌢}⟨ξ⟩)} is R̃_{v_{n}}^{(ξ)}-strategical hence it contains at least one I-position. So pick any w ∈ Λ_{y}^{(τ_{n}^{⌢}⟨ξ⟩)} ⊂ Λ_{y}^{(τ_{n})} : by Fact 6 we have μ̃(w) ≥ η_{n} and we distinguish three cases :

– If μ̃(w) = η_{n} then since v_{n} R̃^{(η_{n})} w and μ̃(w) < μ̃(v_{n}) we have (Fact 2) μ̃(w) ⊂ I^{(+)} ; moreover w ∈ Λ_{y}^{(τ_{n}^{⌢}⟨ξ⟩)} ⊂ Λ_{y}^{(τ_{n}^{⌢}⟨μ(w)⟩)} hence (μ(w), w) satisfies condition (ii).

– If η_{n} < μ̃(w) < ηn^{+} then μ(w) ∉ Ω hence μ̃(w) ⊂ I^{(+)} and as in the previous case (μ(w), w) satisfies condition (ii).

– If ηn^{+} ≤ μ̃(w) then w ∈ Λ_{y}^{(τ_{n}^{⌢}⟨ξ⟩)} ⊂ Λ_{y}^{(τ_{n}^{⌢}⟨η_{n}^{+}⟩)} hence (ηn^{+}, w) satisfies condition (iii).

In particular, since η_{−1} = −1 < 0 ⩽ μ̃(v_{−1}), the previous argument shows that (η_{0}, v_{0}) is well defined, hence that σ_{y} ≠ ∅. ⋄

\underline{End of the proof of Lemma 6.8} :

We have to show that σ_{y} satisfies conditions 1), 2), 3) of Definition 6.3. So set u := v_{n}; by Fact 7, u is an initializing position and by Fact 3, Σ_{y} ∈ S^{τ}. To finish suppose that for some v ∈ Λ_{y}^{(η_{n})} we have J̃(v_{n}) ⊄ J̃(v) ; since by Fact 8 we have μ̃(v_{n}) = η_{n} then (η_{n}, v) would satisfy condition (i) which contradicts the maximality of φ(y). This proves that σ_{y} is optimal for y. ■

\underline{Notation} : We recall that if τ ∈ T with ℓ(τ) = (η, u) we already defined J̃(τ) := J̃(u) ; we also set :

μ̃(τ) := μ̃(u) and ν̃(τ) := η

Let T^{∘} denote the set of all τ ∈ T of even length. Notice that σ_{y} ∈ T^{∘}; moreover for any τ ⪯ σ_{y} such that τ ∈ T^{∘} we have :

ν̃(τ) ≤ μ̃(τ)

Finally we define for all i ∈ I :

A_{i} = {y ∈ ω^{ω} : i ∈ J̃(σ_{y})}

Lemma 6.9. (A_{i})_{i∈I} is a covering of Baire type (Γ_{i})_{i∈I}.

\underline{Proof} : Since by definition J̃(σ_{y}) is nonempty, (A_{i})_{i∈I} is clearly a covering of ω^{ω} and all we have to prove is that for all i, A_{i} ∈ Γ_{i}.

This proof will necessitate a number of descriptive complexity computations. But for practical reasons we will prefer to work with relations rather than sets. So given any pointclass Γ and any predicate Ψ we shall say that “ condition Ψ(y) is Γ ” or simply that “ Ψ is Γ ” to mean that the set {y ∈ ω^{ω} : Ψ(y)} is in Γ. This abuse of terminology will not be confusing in the sequel since we shall never be concerned in the syntactical complexity of the formula Ψ.

\underline{Fact} 9 : For all τ ∈ T^{∘} there exists a Δ_{1+ν̃(τ)}^{0} predicate Ψ_{τ} satisfying :

τ ⪯ σ_{y} ⟹ Ψ_{τ} (y) ⟹ \{ \begin{matrix}τ ⪯ σ_{y} \\ or \\ J̃(σ_{y}) ⊂ I^{(+)} and μ̃(σ_{y}) < ν̃(τ) \end{matrix}

\underline{Proof} : We prove the result by induction on |τ|.

We first set Ψ_{∅} := “0 = 0” which satisfies obviously the statement. Consider now τ = (η_{0}, v_{0}, …, η_{n}, v_{n}) ≠ ∅; let τ′ = (η_{0}, v_{0}, …, η_{n−1}, v_{n−1}) = τ_{||τ|−2} suppose that Ψ_{τ′}

is already defined and satisfies the statement. Let φ^{(j)}(ζ, w) = ψ^{(j)}(η_{m−1}, v_{m−1}, ζ, w) be the formula defining condition (j) in Definition 6.5 (see Remark 6.6) with parameters η_{m−1}, v_{m−1}. Observe that these formulas depend on the fixed τ and are not a priori involved in the definition of some σ_{y}. Now set φ = φ^{(i)} ∨ φ^{(ii)} ∨ φ^{(iii)} and define for all y :

Ψ_{τ} (y) := \{ \begin{matrix}“ Ψ_{τ′}(y) and v_{m} = min\{w : w ∈ Λ_{y}^{(τ′^{⌢}⟨η_{m}⟩)} and φ(η_{m}, w)\}” & if well defined \\ “ 0 = 1 ” & if not \end{matrix}

where the minimum here is relative to the linear ordering ◁.

By the induction hypothesis condition “ Ψ_{τ′}(y) ” is Δ_{1+η_{m−1}}^{0}, and by Theorem 4.6

condition “ w ∈ Λ_{y}^{(τ′^{⌢}⟨η_{m}⟩)} ” is Δ_{1+η_{m}}^{0}. Then noting that v_{m} has finitely many predecessors (since the order ◁ is of type ω) one easily checks that “ Ψ_{τ} (y) ” is Δ_{1+η_{m}}^{0}.

To prove the implications of Fact 9 fix some y and set σ_{y} = (ζ_{0}, w_{0}, …, ζ_{n}, w_{n}).

– If τ ⪯ σ_{y} then it follows from the induction hypothesis that Ψ_{τ′}(y) holds. Moreover since (ζ_{m−1}, w_{m−1}) = (η_{m−1}, v_{m−1}) then from the definition of σ_{y} we have : (η_{m}, v_{m}) = min{(ζ, w) : w ∈ Λ_{y}^{(τ′^{⌢}⟨ζ⟩)} and φ(ζ, w)} so a fortiori v_{m} = min{w : w ∈ Λ_{y}^{(τ′^{⌢}⟨η_{m}⟩)} and φ(η_{m}, w)}. This proves the first implication.

– We now prove the second implication ; so suppose that Ψ_{τ} (y) holds. It follows then from the induction hypothesis that either “ τ′ ⪯ σ_{y} ” or “ J̃(σ_{y}) ⊂ I^{(+)} and μ̃(σ_{y}) < ν̃(τ′) ”, and in the latter case we are done since ν̃(τ′) ≤ ν̃(τ). So we may assume that τ′ ⪯ σ_{y} that is (ζ_{k}, w_{k}) = (η_{k}, v_{k}) for all k < m. It also follows from Ψ_{τ} (y) that φ(η_{m}, v_{m}) holds and we distinguish the three cases :

– Case 1 : φ^{(i)}(η_{m}, v_{m}) holds.

Since ζ_{m−1} = η_{m−1} = μ̃(v_{m−1}) = μ̃(w_{m−1}) then in the construction of σ_{y}, (ζ_{m}, w_{m}) is necessarily defined by condition (i), and φ_{τ}^{(i)}(η_{m}, v_{m}) states precisely that (ζ_{m}, w_{m}) = (η_{m}, v_{m}) ; hence τ ⪯ σ_{y}.

– Case 2 : φ^{(ii)}(η_{m}, v_{m}) holds.

Since ζ_{m−1} = η_{m−1} < μ̃(v_{m−1}) = μ̃(w_{m−1}) then in the construction of σ_{y}, (ζ_{m}, w_{m}) is defined by either condition (ii) or (iii), but since (η_{m}, v_{m}) realizes (ii) and is <_{lex} smaller than any (ζm^{+}, w) satisfying (iii) then (ζ_{m}, w_{m}) is necessarily defined by condition (ii) ; moreover :

ζ_{m−1} = η_{m−1} ≤ ζ_{m} ≤ η_{m} < ηm−1^{+} = ζm−1^{+}

– If ζ_{m} = η_{m} then φ^{(ii)}(η_{m}, v_{m}) states precisely that (ζ_{m}, w_{m}) = (η_{m}, v_{m}), hence in this case τ ⪯ σ_{y}.

– If ζ_{m} < η_{m} then from the statement of condition (ii) we have ζ_{m} = μ̃(w_{m}) and J̃(w_{m}) ⊂ I^{(+)} ; but then by Fact 4 we necessarily have m = n and so J̃(σ_{y}) = J̃(w_{m}) ⊂ I^{(+)} and μ̃(σ_{y}) = μ̃(w_{m}) = ζ_{m} < η_{m} = ν̃(τ).

– Case 3 : φ^{(iii)}(η_{m}, v_{m}) holds.

Observe again that (ζ_{m}, w_{m}) is defined by either condition (ii) or (iii) with ζ_{m} ≤ η_{m}. Then by the same arguments as in Case 2 one proves that if ζ_{m} = η_{m} then τ ⪯ σ_{y}, and if not then J̃(σ_{y}) ⊂ I^{(+)} with μ̃(σ_{y}) = ζ_{m} < η_{m} = ν̃(τ).

This finishes the proof of the second implication of Fact 9. ⋄

\underline{Fact} 10 : If i ∈ I^{(+)} then A_{i} is Σ_{1+ξ_{i}}^{0}.

\underline{Proof} : We prove the fact by induction on ξ_{i}. So fix i ∈ I^{(+)} and suppose that for all j ∈ I^{(+)} such that ξ_{j} < ξ_{i}, A_{j} is Σ_{1+ξ_{j}}^{0}. Since the Baire type is regular then ξ_{i} is necessarily a successor ordinal, say ξ_{i} = η + 1, and it follows then from the induction assumption that the set :

A^{+}(ξ_{i}) := ⋃{A_{j} : j ∈ I^{(+)}, ξ_{j} < ξ_{i}}

is Σ_{1+η}^{0} ⊂ Δ_{1+ξ_{i}}^{0}. We claim that for all y :

E^{(+)} :  y ∈ A_{i} ⟺ ∃τ ∈ T^{∘} : τ ⪯ σ_{y} , ν̃(τ) = μ̃(τ) , i ∈ J̃(τ) ⊂ I^{(+)}

To prove the implication from left to right take τ = σ_{y} which by Fact 8 satisfies ν̃(τ) = μ̃(τ). Conversely if τ is as on the right hand side of E^{(+)} then it follows from Facts 4 and 8 that we necessarily have τ = σ_{y}, hence i ∈ J̃(σ_{y}) and so y ∈ A_{i}.

Consider now the set Â_{i} defined by :

y ∈ Â_{i} ⟺ ∃τ ∈ T^{∘} : Ψ_{τ} (y) , ν̃(τ) = μ̃(τ) , i ∈ J̃(τ) ⊂ I^{(+)}

then by Fact 9, Â_{i} is Σ_{1+ξ_{i}}^{0} ; it also follows from the first implication of Fact 9 that Â_{i} ⊃ A_{i} and from the second implication that Â_{i} ⊂ A_{i} ∪ A^{+}(ξ_{i}). But since A^{+}(ξ_{i}) is disjoint from A_{i} then A_{i} = Â_{i} \ A^{+}(ξ_{i}), hence A_{i} is Σ_{1+ξ_{i}}^{0}. ⋄

\underline{Fact} 11 : If i ∈ I^{(×)} then A_{i} is Π_{1+ξ_{i}}^{0}.

\underline{Proof} : We prove the fact by induction on ξ_{i}. So fix i ∈ I^{(×)} and suppose that for all j ∈ I^{(×)} such that ξ_{j} < ξ_{i}, A_{j} is Π_{1+ξ_{j}}^{0}. It follows then from Fact 10 and from the induction hypothesis that the set :

A(ξ_{i}) := ⋃{A_{j} : j ∈ I, ξ_{j} < ξ_{i}}

is Σ_{1+ξ_{i}}^{0}. We claim that for all y :

E^{(×)} :  y ∉ A_{i} ⟺ \{ \begin{matrix}μ̃(σ_{y}) < ξ_{i} \\ or \\ ∃τ ∈ T^{∘} : τ ⪯ σ_{y}, ν̃(τ) = ξ_{i}, i ∉ J̃(τ) \end{matrix}

If μ̃(σ_{y}) < ξ_{i} then obviously y ∉ A_{i}. On the other hand if i ∈ J̃(σ_{y}) ⊂ I^{(×)} then by Fact 1 for any τ ⪯ σ_{y} such that ν̃(τ) = ξ_{i} we necessarily have i ∈ J̃(σ_{y}) ⊂ J̃(τ). This proves the implication from right to left.

Suppose now that y ∉ A_{i} where σ_{y} = (η_{0}, v_{0}, …, η_{n}, v_{n}) is such that μ̃(σ_{y}) ≥ ξ_{i}. Then by Fact 8, η_{n} = μ̃(σ_{y}) ≥ ξ_{i} hence by Fact 5 there exists some k such that η_{k} = ξ_{i}. Consider then the maximal m ≤ n such that η_{m} = ξ_{i} and observe that since y ∉ A_{i} then necessarily m < n, or m = n and i ∉ J̃(v_{m}). We claim that i ∉ J̃(v_{m}) : for otherwise we would have μ̃(v_{m}) = ξ_{i} = η_{m} and then in the construction of σ_{y}, (η_{m+1}, v_{m+1}) should necessarily satisfy condition (i) which implies that η_{m+1} = η_{m}, and this contradicts the choice of m. Hence τ = (η_{0}, v_{0}, …, η_{m}, v_{m}) satisfies ν̃(τ) = ξ_{i} and i ∉ J̃(τ). This proves the converse implication.

Thus if we denote by A′_{i} the set defined by the second line of the right hand side of E^{(×)} then we have A_{i}^{c} = A′_{i} ∪ A(ξ_{i}) and if we consider the set Â′_{i} defined by :

y ∈ Â′_{i} ⟺ ∃τ ∈ T^{∘} : Ψ_{τ} (y), ν̃(τ) = ξ_{i}, i ∉ J̃(τ)

then applying Fact 9 as in Fact 10 we get that Â′_{i} is Σ_{1+ξ_{i}}^{0} and A′_{i} ⊂ Â′_{i} ⊂ A′_{i} ∪ A^{+}(ξ_{i}) ; but since A^{+}(ξ_{i}) ⊂ A_{i}^{c} then A′_{i} = Â′_{i} and so A_{i}^{c} = A′_{i} ∪ A(ξ_{i}), hence A_{i}^{c} is Σ_{1+ξ_{i}}^{0}. ⋄

This finishes the proof of Lemma 6.9. ■

\underline{End of the proof of Theorem 6.1} :

– If Player II wins the game G then by Lemma 6.2, (B_{i})_{i∈I} is weakly reducible to (ω^{ω} \ C_{i})_{i∈I}, and the second alternative of Theorem 6.1 holds.

– If Player I wins the game G then since this game is Δ_{1}^{1}, by a classsical result of Martin, Player I admits a Δ_{1}^{1} strategy ; so fix such a strategy Σ. Consider then the corresponding mapping φ : ω^{ω} → T^{∘} (as in Definition 6.5) and the family (A_{i})_{i∈I} defined above. It follows from Lemmas 6.4 and 6.8 that A_{i} ⊂ C_{i} for all i ∈ I. Hence by Lemma 6.9 (A_{i})_{i∈I} is of type (Γ_{i})_{i∈I} and is a subordinate covering to (C_{i})_{i∈I}.

Finally observe that if α ∈ ω^{ω} is any Δ_{1}^{1} code for Σ then all the previous construction can be achieved in L^{ω_{1}^{α}} (see Remark 2.13). In particular the relation R(τ, y) defined by “ Ψ_{τ} (y) ” is clearly in L^{ω_{1}^{α}}. It follows then that the family (A_{i})_{i∈I} is Δ_{1}^{1}(α) = Δ_{1}^{1}, which proves that the first alternative of Theorem 6.1 holds.

6.10. Remarks : The proof of Theorem 6.1 is the resultant of numerous attempts using simpler, but unfortunately incomplete, arguments ; and we strongly believe that one cannot bring drastic simplifications to this proof. Also we shall try through the following comments to throw light on some technical aspects.

a) First of all observe that the reduction to the case where ⋃_{i∈I} S_{i} = Seq(ω) is unessential and one can easily repeat the proof without this additional assumption. The price to pay for this fake generality is that most of the definitions should include then one additional case which induces useless complications in the arguments.

However the reduction to the “regular” case is fundamental. More precisely Lemma 6.2 is false if the Baire type (Γ_{i})_{i∈I} does contain an additive Baire class of limit rank (though by the reduction argument, Theorem 6.1 is still true).

b) The main difficulty in this proof lies in the fact that the Baire classes Γ_{i} that we handle are of different rank and nature (additive or multiplicative). For example if one restricts the study to Baire classes of constant rank or only to additive Baire classes Σ_{1+ξ_{i}}^{0} then many of the arguments become trivial (in the last case the sequence σ_{y} of positions could be replaced by one position v_{y}). Most of the complications come from the treatment of the multiplicative Baire classes. A typical example is condition (iii) in the definition of σ_{y} whose only role is to avoid “skipping” any ordinal in Ω even if this ordinal is a priori irrelevant for the analysis of the fixed point y. This detail is crucial for the computation of the complexity of the sets A_{i} when i ∈ I^{(×)} while it does not interfer in the case i ∈ I^{(+)} (observe by the way that despite some formal similarities, the proofs of Fact 10 and Fact 11 are based on totally different arguments. Also quite surprisingly these complexity computations could be simplified in the case where the Baire type does not contain multiplicative Baire classes of limit rank ; but this case cannot be eliminated by a reduction argument as for additive classes.

c) Theorem 6.1 possesses two aspects which are both non trivial. On one hand it is quite clear that Theorem 6.1 is firstly an effectivity result, and in this respect even when restricted to Borel coverings this result is new and this additional assumption does not simplify any part of the previous proof. On the other hand for arbitrary Π_{1}^{1} coverings even the “boldface” version of Theorem 6.1 is new and again not simpler to prove.

Let us also point out that using Borel determinacy Matrai obtains in [4] a similar boldface dichotomy for Borel partitions, in the particular case where the Baire type (Γ_{i})_{i∈I} is a constant additive Baire class Σ_{ξ}^{0}. In fact given any adequate Baire type (Γ_{i})_{i∈I} one can replace the game G used in the proof of Theorem 6.1 by a much simpler Borel version (in the spirit of Wadge games) and obtain very easily the same conclusion than Theorem 6.1 : the sets A_{i} can then be obtained (like in Wadge games) as the inverse images, by a winning strategy, of the sets ω^{ω} \ C_{i} and the long construction of σ_{y} as well as the descriptive computations via the predicates Ψ_{τ} are then no more needed. Unfortunately this soft approach based on Borel determinacy can neither give any effectivity information nor be applied to arbitrary Π_{1}^{1} coverings.

d) Finally observe that the statement of Theorem 6.1 is not a dichotomy in the sense that both alternatives might be realized simultanesouly. To obtain a real dichotomy one has to ensure that the testing family (B_{i})_{i∈I} is “really” of Baire type (Γ_{i})_{i∈I} that is not “simpler”, and as we shall see next this is always possible.

Proposition 6.11. For any Baire type (Γ_{i})_{i∈I} of code α ∈ ω^{ω} there exists a Δ_{1}^{1}(α) family (B_{i})_{i∈I} of type (Γ_{i})_{i∈I} such that for any covering (C_{i})_{i∈I} at most one of the following two alternatives holds :

– either (C_{i})_{i∈I} admits a subordinate covering of type (Γ_{i})_{i∈I}

– or (B_{i})_{i∈I} is weakly reducible to (ω^{ω} \ C_{i})_{i∈I}

\underline{Proof} : By standard arguments we can find a Δ_{1}^{1}(α) family (V_{i})_{i∈I} of type (Γ_{i})_{i∈I} of subsets of ω^{ω} × ω^{ω} which is universal in the sense that for any family (E_{i})_{i∈I} of type (Γ_{i})_{i∈I} of subsets of ω^{ω} there exists some a ∈ ω^{ω} such that for all i ∈ I and all x :

x ∈ E_{i} ⟺ (a, x) ∈ V_{i}

Consider then the “diagonal” family (B_{i})_{i∈I} defined by :

B_{i} = {x ∈ ω^{ω} : (x, x) ∈ V_{i}}

and suppose that (C_{i})_{i∈I} is a covering which satisfies both alternatives. So (C_{i})_{i∈I} admits a subordinate covering (A_{i})_{i∈I} of type (Γ_{i})_{i∈I}, and there exists a continuous mapping f : ω^{ω} → ω^{ω} which is a weak reduction (B_{i})_{i∈I} to (ω^{ω} \ C_{i})_{i∈I}. Then the covering (f^{−1}(A_{i}))_{i∈I} is also of type (Γ_{i})_{i∈I} and by the universality of (V_{i})_{i∈I} we can find a ∈ ω^{ω} such that for all i ∈ I, V_{i}(a) = f^{−1}(A_{i}). Hence for all i ∈ I :

(⋆) a ∈ B_{i} ⟺ (a, a) ∈ V_{i} ⟺ a ∈ f^{−1}(A_{i}) ⟺ f(a) ∈ A_{i} ⟹ f(a) ∈ C_{i}

But since (A_{i})_{i∈I} is a covering we have f(a) ∈ ⋃_{i∈I} A_{i}, so by the equivalences in (⋆) we also have a ∈ ⋃_{i∈I} B_{i}. Hence there exists some i_{∗} ∈ I such that a ∈ B_{i^{∗}} and f(a_{i^{∗}}) ∉ C_{i} and this contradicts (⋆). ■

Corollary 6.12. Let (Γ_{i})_{i∈I} be an adequate Baire type of code α ∈ ω^{ω} and let (C_{i})_{i∈I} be a Π_{1}^{1}(α)-covering. If (C_{i})_{i∈I} admits a subordinate covering of type (Γ_{i})_{i∈I} then (C_{i})_{i∈I} admits a Δ_{1}^{1}(α)-subordinate covering of type (Γ_{i})_{i∈I}.

\underline{Proof} : Apply Theorem 6.1 with (B_{i})_{i∈I} given by Proposition 6.11. Since (C_{i})_{i∈I} admits a subordinate covering of type (Γ_{i})_{i∈I} then the second alternative of Theorem 6.1 cannot hold hence the first alternative does hold. Consequently (C_{i})_{i∈I} admits a Δ_{1}^{1}(α)- subordinate covering of type (Γ_{i})_{i∈I}. ■

The following dual statement of Corollary 6.12 answers the initial question raised in the Introduction :

Corollary 6.13. Let (Γ_{i})_{i∈I} be an adequate Baire type of code α ∈ ω^{ω} and let (A_{i})_{i∈I} be a Σ_{1}^{1}(α)-family of subsets of ω^{ω}. If there exists a family (B_{i})_{i∈I} of type (Γ_{i})_{i∈I} such that for all i, A_{i} ⊂ B_{i} and ⋂_{i∈I} B_{i} = ∅ then there exists such a family in Δ_{1}^{1}(α).

Corollary 6.12 proves the implication (iii) ⇒ (i) of Theorem A quoted in the Introduction, and we now prove the second implication (ii) ⇒ (iii).

7 – ON THE NECESSITY OF ADEQUATE BAIRE TYPES

Theorem 7.1. Let (Γ_{i})_{i∈I} be a non adequate Baire type of code α ∈ ω^{ω}. Then there exists β ∈ ω^{ω} and a Δ_{1}^{1}(β)-covering (C_{i})_{i∈I} such that :

(1) (C_{i})_{i∈I} admits a subordinate covering of type (Γ_{i})_{i∈I}

(2) (C_{i})_{i∈I} does not admit any Δ_{1}^{1}(α, β)-subordinate covering of type (Γ_{i})_{i∈I}

\underline{Proof} : Suppose that (Γ_{i})_{i∈I} is of rank (ξ_{i})_{i∈I} ; by Proposition 5.5 we can then find i_{∗} ∈ I and ξ_{∗} < ω_{1} with code in Δ_{1}^{1}(α) such that Γ_{i_{∗}} ⊃ Π_{ξ_{∗}}^{0} and

J_{∗} = {j ∈ I : ξ_{j} ≤ ξ_{∗} and Γ_{j} = Π_{ξ_{j}}^{0}}

is infinite. Then the Baire type (Γ_{i})_{i∈{i_{∗}}∪J_{∗}} is still non adequate and has a code in Δ_{1}^{1}(α) ; and if we construct a family (C_{i})_{i∈{i_{∗}}∪J_{∗}} satisfying conditions (1) and (2) relatively to (Γ_{i})_{i∈{i_{∗}}∪J_{∗}} then setting C_{i} = ∅ for i ∈ I \ ({i_{∗}} ∪ J_{∗}) we get a family (C_{i})_{i∈I} satisfying these conditions relatively to (Γ_{i})_{i∈I}. And without loss of generality we can assume that I = ω , i_{∗} = 0 , J_{∗} = I \ {0} and ξ_{∗} = sup{ξ_{j}; j ∈ J_{∗}} that is :

\{ \begin{matrix}Γ_{i} = Π_{ξ_{i}}^{0} & for all i > 0 \\ Γ_{0} ⊃ Π_{ξ_{∗}}^{0} & with ξ_{∗} = sup\{ξ_{i}; i > 0\} \end{matrix}

7/10/2008 – 16:22 7. On the necessity of adequate Baire types

For practical reasons we shall not work directly in ω^{ω} but in some homeomorphic copy X which will be precised later on. Also the definition of the sequence (C_{i})_{i∈ω} will not be uniform : we shall first define (C_{i})_{i>0}, but the definition of C_{0} will not be explicit. In fact we shall introduce some parameter T and define for all T a Δ_{1}^{1}(T) set C_{0}(T) ⊃ ω^{ω} \⋃_{i>0} C_{i}; then we shall prove that for some value T_{0} of the parameter the sequence

(C_{i})_{i∈ω} := ⟨C_{0}(T_{0})⟩^{⌢}(C_{i})_{i>0}

satisfies conditions (1) and (2) with β ≈ (α, T_{0}).

Let T denote the space of all trees on ω that we view as a Π_{1}^{0} subset of the compact space 2^{(ω^{<ω})}. The parameter T will run a subset T̃ of T that we describe now. For this consider on ω^{<ω} the partial ordering ≤ defined by :

s ≤ t ⟺ |s| = |t| = n and ∀i < n, s(i) ≤ t(i)

then T̃ will be the set of all trees T on ω which are right hereditary with respect to this ordering, that is satisfying :

s ∈ T and s ≤ t ⟹ t ∈ T

Let T_{WF} denote the set of all well-founded trees on ω and set T̃_{WF} := T̃ ∩ T_{WF}. It is well known that the set T_{WF} is Π_{1}^{1}-complete.

Lemma 7.2. T̃_{WF} is Π_{1}^{1}-complete.

\underline{Proof} : Consider the mapping Ψ : T ↦ T defined by :

t ∈ Ψ(T) ⟺ ∃s ∈ T : s ≤ t

Since for all t the set {s ∈ ω^{<ω} : s ≤ t} is finite Ψ is continuous ; and we shall prove that T̃_{WF} = Ψ^{−1}(T_{WF}). First observe that Ψ(T ) ⊂ T̃ so it is enough to check that T_{WF} = Ψ^{−1}(T_{WF}).

If Ψ(T) is well-founded then a fortiori T which is a subset of Ψ(T) is well-founded too. On the other hand if Ψ(T) is ill-founded and possesses some infinite branch γ then T (γ) := {t ∈ T : t ≤ γ_{||t|}} is an infinite and finitely branching tree hence T (γ) admits an infinite branch and a fortiori T is ill-founded too. ■

We now fix some more notations. Let X := ∏_{i>0} X_{i} with X_{i} := ω^{ω} for all i > 0 and denote by π_{i} : X → X_{i} the canonical projections. Then clearly X is homeomorphic to ω^{ω} but to avoid any confusion we shall not identify these two spaces.

Let α ∈ ω^{ω} be any real such that (ξ_{i})_{i∈ω} admits a code in Δ_{1}^{1}(α) ; we can then find a Δ_{1}^{1}(α)-family (A_{i,k})_{i>0,k∈ω} of subsets of ω^{ω} such that for all i > 0, (A_{i,k})_{k∈ω} is an increasing family of Δ_{ξ_{i}}^{0} sets with A_{i,0} = ∅, and A_{i} := ⋃_{k∈ω} A_{i,k} is Σ_{ξ_{i}}^{0}-complete. We then define for all i > 0 and k ∈ ω :

C_{i,k} := π_{i}^{−1}(A_{i,k}) and C_{i} := π_{i}^{−1}(A_{i})

We now proceed to the definition of C_{0}(T) for T ∈ T̃. Consider first the mappings φ_{i} : X → ω for i ∈ ω (including n = 0), and φ : X → ω^{ω} defined by :

φ_{i}(x) := \{ \begin{matrix}0 & if x ∉ C_{i+1} \\ k + 1 & if x ∈ C_{i+1,k+1} \ C_{i+1,k} \end{matrix}

φ(x) := (φ_{i}(x))_{i∈ω}

Finally for all T ∈ T̃ let :

T^{∗} := {s ∈ Seq(ω) : ∀m ≤ |s| , s_{|m} ∈ T or ∃j < m, s(j) = 0}
C_{0}(T) := {x ∈ X : ∀n ∈ ω, φ(x)_{|n} ∈ T^{∗}}
(C_{i}(T))_{i∈ω} := ⟨C_{0}(T)⟩^{⌢}(C_{i})_{i>0}

We recall that ξ_{∗} = sup_{i>0} (ξ_{i}) and we now set

ξ^{∗} = sup_{i>0} (ξ_{i} + 1)

Lemma 7.3. (C_{i}(T))_{i∈ω} is a Δ_{1}^{1}(α, T) covering of Baire type ⟨Π_{ξ^{∗}}^{0}⟩^{⌢}(Σ_{ξ_{i}}^{0})_{i>0}.

\underline{Proof} : If x ∈ X \ ⋃_{i>0} C_{i} then φ_{i}(x) = 0 for all i ∈ ω so x ∈ C_{0}(T). Hence (C_{i}(T))_{i∈ω} is a covering which is clearly Δ_{1}^{1}(α, T). Observe that x ∈ C_{0}(T) if and only if :

∀i ∈ ω, (∃j < i, x ∉ C_{j}) or (∃s ∈ ω^{i} ∩ T, ∀j < i, x ∈ C_{j+1,s(j)+1} \ C_{j+1,s(j)})

which proves that C_{0}(T) is Π_{ξ^{∗}}^{0}. On the other hand by construction C_{i}(T) = C_{i} ∈ Σ_{ξ_{i}}^{0} for all i > 0. ■

Lemma 7.4. If T ∈ T̃ \ T̃_{WF} then the covering (C_{i}(T))_{i∈ω} admits a subordinate covering of Baire type (Π_{ξ_{i}}^{0})_{i∈ω}.

\underline{Proof} : Fix some infinite branch γ of T. Set B_{i} := C_{i,γ(i−1)} for all i > 0, and B_{0} := ⋂_{i>0} X \ C_{i,γ(i−1)}. It is quite clear from these definitions that (B_{i})_{i∈ω} is a covering of Baire type (Π_{ξ_{i}}^{0})_{i∈ω} and that B_{i} ⊂ C_{i} for all i > 0. Finally if x ∈ B_{0} then for all i ∈ ω, φ_{i}(x) ≥ γ(i) + 1 hence φ(x)_{|n} ≥ γ_{|n} ∈ T ; and since T ∈ T̃ then φ(x)_{|n} ∈ T^{∗}, hence x ∈ C_{0}(T). This proves that (B_{i})_{i∈ω} is a subordinate covering to (C_{i}(T))_{i∈ω}. ■

Lemma 7.5. Let Γ be an arbitrary Baire class. If the covering (C_{i}(T))_{i∈ω} admits a subordinate covering of Baire type ⟨Γ⟩^{⌢}(Π_{ξ_{i}}^{0})_{i>0} then T ∈ T̃ \ T̃_{WF}.

\underline{Proof} : Let us recall that X = ∏_{i>0} X_{i} with each X_{i} = ω^{ω}. We can then fix a homeomorphism ȷ : X → ω^{ω} with the property that if x = (x_{i})_{i>0} and γ = ȷ(x) then γ_{|m} depends only on (x_{i} _{|m})_{i≤m}

Suppose now that (B_{i})_{i∈ω} is a subordinate covering to (C_{i}(T))_{i∈ω} of Baire type ⟨Γ⟩^{⌢}(Π_{ξ_{i}}^{0})_{i>0} and fix i > 0 in ω. Then ȷ(B_{i}) ⊂ ω^{ω} is Π_{ξ_{i}}^{0}, and since A_{i} ⊂ X_{i} = ω^{ω} is Σ_{ξ_{i}}^{0}-complete then in Wadge’s game G_{W} (A_{i}, ȷ(B_{i})) Player II cannot win ; hence by the determinacy of this game Player I wins the game. Now any winning strategy for Player I induces a continuous mapping σ_{i} : ω^{ω} → X_{i} = ω^{ω} satisfying ȷ(B_{i}) = σ_{i}^{−1}(X_{i} \ A_{i}) and moreover for all m ∈ ω, σ_{i}(γ)_{|m+1} depends only on γ_{|m}.

Consider then the product mapping σ : ω^{ω} → X defined by

σ(γ) = (σ_{i}(γ))_{i>0} ∈ X = ∏_{i>0} X_{i}

So π_{i}∘σ = σ_{i} : ω^{ω} → X_{i} and ȷ∘σ : ω^{ω} → ω^{ω}. It follows from the choice of ȷ and σ_{i} that for all m ∈ ω, ȷ∘σ(γ)_{|m+1} depends only on γ_{|m}. Then one can define by induction sequences u_{m} ∈ ω^{m} such that

∀γ (u_{m} ≺ γ ⇒ u_{m+1} ≺ ȷ(σ(γ)))

7/10/2008 – 16:22 8. Proof of the representation Theorem

Since u_{0} = ∅ ≺ u_{1}, it is easily shown by induction that u_{m} ≺ u_{m+1} for all m. Then ε = ⋃_{i>0} u_{i} satisfies ȷ(σ(ε)) = ε and if we set x := ȷ^{−1}(ε) then

σ(ȷ(x)) = σ(ε) = ȷ^{−1}(ε) = x

and for all i > 0 :

π_{i}(x) = π_{i}(σ(ȷ(x))) = σ_{i}(ȷ(x))

Hence

x ∉ C_{i} ⟺ π_{i}(x) = σ_{i}(ȷ(x)) ∉ A_{i} ⟺ ȷ(x) ∈ ȷ(B_{i}) ⟺ x ∈ B_{i} ⟹ x ∈ C_{i}

and it follows that x ∈ ⋂_{i>0}(C_{i} \ B_{i}) ⊂ B_{0} ⊂ C_{0}(T). Then for all n ∈ ω, φ(x)_{|n} ∈ T^{∗}; but since x ∈ C_{i} then φ_{i}(x) > 0 and so necessarily φ(x)_{|n} ∈ T. Hence φ(x) is an infinite branch of T and so T ∈ T̃ \ T̃_{WF}. ■

\underline{End of the proof of Theorem 7.1} : Fix α ∈ ω^{ω} which codes (Γ_{i})_{i∈ω} then clearly (ξ_{i})_{i∈ω} admits a code in Δ_{1}^{1}(α) and we can repeat the previous construction. Consider now the sets :

S := {T ∈ T̃ : (C_{i}(T)))_{i∈ω} admits a subordinate covering of type (Γ_{i})_{i∈ω}
S_{0} := {T ∈ T̃ : (C_{i}(T))_{i∈ω} admits a Δ_{1}^{1}(α, T) subordinate covering of type (Γ_{i})_{i∈ω}}

Then clearly S_{0} ⊂ S and we shall now prove that this inclusion is strict. Observe first that by a straightforward computation the set :

U := {(T, γ) ∈ T̃ × ω^{ω} : (W_{i}^{α}(γ))_{i∈ω} is a subordinate covering for (C_{i}(T))_{i∈ω}}

is Π_{1}^{1}(α) ; and since

T ∈ S_{0} ⟺ ∃γ ∈ Δ_{1}^{1}(α, T), (T, γ) ∈ U

then S_{0} is also Π_{1}^{1}(α). On the other hand since Γ_{0} ⊃ Π_{ξ_{∗}}^{0}, then by Lemmas 7.4 and 7.5 we have S = T̃ \ T̃_{WF}, hence by Lemma 7.2 the set S is Σ_{1}^{1}-complete.

It follows from these observations that S \ S_{0} ≠ ∅ and if T is any element of S \ S_{0} then obviously (C_{i}(T))_{i∈ω} satisfies the conclusion of Theorem 7.1. ■

7.6. Remark : One cannot a priori impose on the element T ∈ S \ S_{0} (chosen at the end of the previous proof) to be in Δ_{1}^{1}(α). Also it seems quite unlikely that Theorem 7.1 could hold with β = α. But one can obviously choose T, hence β, in any class which constitute a basis for the class Σ_{1}^{1} ; for example applying Gandy basis Theorem one can choose β such that ω_{1}^{β} = ω_{1}^{ck}.

8 – PROOF OF THE REPRESENTATION THEOREM

In this section we prove Theorem 2.10 stated in Section 2. For this we need to construct resolution families (R^{(η)})_{η≤ξ} which are strongly continous at each limit level λ ⩽ ξ. Unfortunately the tree products technique used in [1] enables one to ensure the strong continuity condition only at the last level ξ (whenever it is limit). So we have to describe a new method which keeps under control all intermediate limit levels.

In fact as in [1] we shall ensure a stronger condition than the strong continuity condition. This stronger condition that we introduce now is probably less intuitive but has proved to be efficient in many applications (see [1]).

As in [1] we denote by h_{R}(s), for any tree relation R and s in its domain, the height of s, it is the number of strict R-predecessors of s.

Definition 8.1. Let R = (R^{(η)})_{η⩽ξ} be a resolution family.

If λ ⩽ ξ is limit ordinal we shall say that R is uniform at level λ if for all integer n there exists η_{n} < λ such that for all s and t in Dom(R^{(0)}) with min(h_{R^{(λ)}}(s)h_{R^{(λ)}}(t)) ⩽ n we have :

s R^{(η_{n})} t ⟹ s R^{(λ)} t

We shall say that R is completely uniform if it is uniform at every limit level λ ⩽ ξ.

Clearly if R is uniform at some level λ then it is strongly continuous at this level (if n := h_{R^{(λ)}}(s) and ζ := η_{n} then (s R^{(ζ)} t ⇒ s R^{(λ)} t)). Hence any completely uniform expansion family is strongly continuous. Observe also that “uniform” in the sense of [1] means exactly “uniform at the last level”.

The following lemma will be the key for the construction of transfinite completely uniform expansion families.

Lemma 8.2. Let (S^{(η)})_{η⩽ξ} be a completely uniform expansion family, θ < ξ and p ∈ ω. Define the family (R^{(η)})_{η⩽ξ} of relations by :

s R^{(η)} t ⟺ (s S^{(η)} t) or (s S^{(θ)} t and η ⩾ θ and h_{S^{(θ)}}(s) ⩽ p)

Then :

i) (R^{(η)})_{η⩽ξ} is a completely uniform expansion family, and R^{(η)}=S^{(η)} if η ⩽ θ.
ii) the canonical mapping j_{η} : [S^{(η)}] → [R^{(η)}] is a homeomorphism.
iii) for θ ⩽ η ⩽ ξ and k ⩽ p, we have h_{R^{(η)}}(s) = k ⟺ h_{S^{(θ)}}(s) = k.
iv) (h_{R^{(ξ)}}(s) ⩽ p and s R^{(θ)} t) ⟹ s R^{(ξ)} t

\underline{Proof} :

i) It is readily seen that R^{(η)} is a tree relation for all η ⩽ ξ, that R^{(η+1)} is distinguished in R^{(η)} for all η < ξ, that R^{(λ)}= ⋂_{η<λ} R^{(η)} for limit λ ⩽ ξ and that R^{(η)}=S^{(η)} for η ⩽ θ.

We now prove that the canonical mapping π′_{η} : [R^{(η)}] → [R^{(0)}] is onto for η ⩽ ξ : for every σ ∈ [S^{(η)}], both π_{η}(σ) and π′_{η}∘j_{η}(σ) are infinite S^{(0)}-branches containing σ, hence π_{η}(σ) = π′_{η}∘j_{η}(σ). And since π′_{η}∘j_{η} = π_{η} is onto, then π′_{η} is onto.

Finally let λ ⩽ ξ be a limit ordinal. We have to prove that the expansion family is uniform at level λ. It is clear if λ ⩽ θ. If λ > θ, for any integer n there is some η_{n} < λ, which can be assumed to be greater than θ, such that for all s and t : min(h_{S^{(λ)}}(s), h_{S^{(λ)}}(t) ⩽ n and s S^{(η_{n})} t imply s S^{(λ)} t. But since S^{(η)}⊂R^{(η)}, we have h_{S^{(η)}}(u) ⩽ h_{R^{(η)}}(u) for all u. Thus if s and t satisfy s R^{(η_{n})} t and min(h_{R^{(λ)}}(s), h_{R^{(λ)}}(t) ⩽ n, we have - either s S^{(η_{n})} t and min(h_{S^{(λ)}}(s), h_{S^{(λ)}}(t)) ⩽ n, hence s S^{(λ)} t and a fortiori s R^{(λ)} t – or h_{S^{(θ)}}(s) ⩽ p and s S^{(θ)} t, hence s R^{(λ)} t.

ii) Since S^{(η)}⊂R^{(η)}, the mapping j_{η} is continuous ; it is bijective since j_{η} = π_{η}^{−1}∘π′_{η}. To see that it is a homeomorphism it remains to show that for all η ⩾ θ and all s in Dom(S^{(0)}) the set E_{s} := {σ ∈ [R^{(η)}] : s ∈ ȷ_{η}^{−1}(σ)} is clopen. Denote by W_{s} the clopen set {σ ∈ [R^{(η)}] : s ∈ σ}. Then since

j_{η}^{−1}(σ) = {t : ∃u ∈ σ t R^{(η)} u} = σ ∪ {t : h_{S^{(θ)}}(t) ⩽ p and ∃u ∈ σ t S^{(θ)} u}

one has E_{s} = W_{s} or E_{s} ∪ ⋃{W_{u} : s S^{(θ)} u}, hence E_{s} is open. Similarly :

\begin{aligned}j_{η}^{−1}(σ) & = \{t : ∀u ∈ σ u ⪯ t or t R^{(η)} u\} \\ & = σ ∪ \{t : h_{S^{(θ)}}(t) ⩽ p and ∀u ∈ σ h_{S^{(θ)}}(u) > p ⟹ t S^{(θ)} u\} \end{aligned}

hence E_{s} = W_{s} or E_{s} = W_{s} ∪ ⋂{W_{u}^{c} : h_{S^{(θ)}}(u) > p and ¬(s S^{(θ)} u)}. Thus E_{s} is closed.

iii) Let θ ⩽ η ⩽ ξ. One has R^{(η)}⊂S^{(θ)}=R^{(θ)}, hence h_{R^{(η)}}(s) ⩽ h_{S^{(θ)}}(s) = h_{R^{(θ)}}(s). Thus h_{R^{(θ)}}(s) = k ⩽ p ⟹ h_{R^{(η)}}(s) ⩽ k. Conversely, if h_{S^{(θ)}}(s) = k ⩽ p, there are pairwise distinct (t_{i})_{0⩽i⩽k} such that ∅ = t_{0} S^{(θ)} t_{1} S^{(θ)} t_{2} … S^{(θ)} t_{k} = s, and since t_{i} R^{(η)} s for i = 1, 2, … k, we have h_{R^{(η)}}(s) ⩾ k = h_{R^{(θ)}}(s) ⩾ h_{R^{(η)}}(s).

iv) Assume that k := h_{R^{(ξ)}}(s) ⩽ p. It follows from iii) that h_{S^{(θ)}}(s) = k ⩽ p. If moreover s R^{(θ)} t, we then have s R^{(ξ)} t. ■

In the sequel we will call a graduate family of Borel sets any family (A_{i}, ξ_{i})_{i∈I} where the ξ_{i}’s are countable ordinals and A_{i} are Σ_{1+ξ_{i}}^{0} subsets of ω^{ω}.

Definition 8.3. We shall say that a graduate family (A_{i}, ξ_{i})_{i∈I} of Borel sets is complete of level ξ if :

(1) sup_{i∈I} ξ_{i} ⩽ ξ.

(2) for all i ∈ I such that ξ_{i} is successor, there is a subset J of I such that A_{i} = ⋃_{j∈J} A_{j}^{c} and ∀j ∈ J ξ_{j} < ξ_{i}.

(3) for all i ∈ I such that ξ_{i} is limit, there is a subset J of I such that A_{i} = ⋃_{j∈J} A_{j} and ∀j ∈ J ξ_{j} < ξ_{i}.

We leave to the reader the proof of the following simple lemmas.

Lemma 8.4. Let (A_{i}, ξ_{i})_{i∈I} be a complete graduate family of Borel sets of level ξ. If ζ ⩽ ξ and I_{ζ} := {i ∈ I : ξ_{i} ⩽ ζ}, the subfamily (A_{i}, ξ)_{i∈I_{ζ}} is complete of level ζ.

Lemma 8.5. If (B_{i}, ξ_{i})_{i∈I} is a countable graduate family of Borel subsets of ω^{ω} with ξ := sup ξ_{i}, then one can find a countable complete graduate family (A_{j}, η_{j})_{j∈J} of level ξ such that I ⊂ J and (A_{i}, η_{i}) = (B_{i}, ξ_{i}) for i ∈ I.

Definition 8.6. Let (A_{i}, ξ)_{i∈I} be a graduate family of Borel subsets of ω^{ω}. A strongly continuous expansion family (R^{(η)})_{η⩽ξ} is said to be adapted to (A_{i}, ξ)_{i∈I} if, for all i ∈ I , π_{ξ_{i}}^{−1}(A_{i}) is an open subset of [R^{(ξ_{i})}], where π_{ξ_{i}} denotes the canonical mapping : [R^{(ξ_{i})}] → ω^{ω}.

Theorem 8.7. Let (B_{i}, ξ)_{i∈I} be a countable graduate family of Borel subsets of ω^{ω}, with ξ = sup_{i} ξ_{i}. Then there exists a completely uniform expansion family (R^{(η)})_{η⩽ξ} adapted to (B_{i}, ξ)_{i∈I}.

\underline{Proof} : Using Lemma 8.5 we can and do assume that (B_{i}, ξ)_{i∈I} is complete of level ξ. We will prove by induction on ξ the following statement :

(H_{ξ}) : For all ζ ⩽ ξ, all complete family (A_{i}, ξ_{i})_{i∈I} of level ξ and all completely uniform expansion family (R^{(η)})_{η⩽ζ} adapted to the subfamily (A_{i}, ξ_{i})_{i∈I_{ζ}}, there exists a completely uniform expansion family (R^{(η)})_{η⩽ξ} adapted to (A_{i}, ξ_{i})_{i∈I} and extending the given expansion family (R^{(η)})_{η⩽ζ}.

It is clear that Theorem 8.7 follows from this statement applied to ζ = 0, R^{(0)}= Ext and (A_{i}, ξ_{i})_{i∈I} = (B_{i}, ξ_{i})_{i∈I}. Notice that if ζ = ξ there is nothing to prove. So we can always assume that ζ < ξ.

a) \underline{The initial case} : For ξ = 0, we have necessarily ζ = ξ = 0 and there is nothing to prove.

b) \underline{The successor case} : Assume that H_{ξ} holds and let ζ < ξ + 1, (A_{i}, ξ_{i})_{i∈I} be a complete family of level ξ + 1 and (R^{(η)})_{η⩽ζ} a completely uniform expansion family adapted to the subfamily (A_{i}, ξ_{i})_{i∈I_{ζ}}. The statement H_{ξ} applied to the family (A_{i}, ξ_{i})_{i∈I_{ξ}} enables us to assume that ζ = ξ. We have then only to define the tree relation R^{(ξ+1)} distinguished in R^{(ξ)} in such a way that π_{ξ+1} be onto and the set π_{ξ+1}^{−1}(A_{i}) be open in [R^{(ξ+1)}] for every i ∈ I \ I_{ξ}.

Observe that by completeness of the family, for each i ∈ I \ I_{ξ}, ξ_{i} = ξ + 1 and there is a subset J_{i} of I_{ξ} such that A_{i} = ⋃_{j∈J_{i}} A_{j}^{c}. Then F_{j} := π_{ξ}^{−1}(A_{j}^{c}) is closed in [R^{(ξ)}] for all j in J_{i}. Using Lemma I-6.3 of [1], we can find a tree relation R distinguished in R^{(ξ)} such that π is onto and π^{−1}(F_{j}) is Δ_{1}^{0} for each j ∈ ⋃_{i∈I\I_{ξ}} J_{i} (where π denotes the canonical mapping [R] → [R^{(ξ)}]). Then putting R^{(ξ+1)}:= R, we have π_{ξ+1} = π_{ξ}∘π, hence π_{ξ+1}^{−1}(A_{i}) = ⋃_{j∈J_{i}} π^{−1}(F_{j}) ∈ Σ_{1}^{0}.

c) \underline{The limit case} : Assume that ξ is limit and H_{θ} holds for all θ < ξ. Choose a fundamental sequence (θ_{k}) for ξ. Let (A_{i}, ξ_{i})_{i∈I} be a complete family of level ξ, ζ < ξ and (R^{(η)})_{η⩽ζ} be a completely uniform expansion family adapted to the subfamily (A_{i}, ξ_{i})_{i∈I_{ζ}}. Denote by ℓ the least integer k such that ζ ⩽ θ_{k}.

We define inductively for k ⩾ ℓ completely uniform expansion families (S_{k}^{(η)})_{η⩽θ_{k+1}} and (R_{k}^{(η)})_{η⩽θ_{k+1}} in the following way :

– applying (H_{θ_{ℓ+1}}) we find (S_{ℓ}^{(η)})_{η⩽θ_{ℓ+1}} extending (R^{(η)})_{η⩽ζ} and adapted to the subfamily (A_{i}, ξ_{i})_{i∈I_{θ_{ℓ+1}}} .

– applying Lemma 8.2 we find (R_{ℓ}^{(η)})_{η⩽θ_{ℓ+1}} which agrees with (R_{ℓ}^{(η)})_{η⩽θ_{ℓ+1}} up to η_{ℓ} and satisfies properties i) to iv) of Lemma 8.2 for (θ, p) = (θ_{ℓ}, ℓ).

– if (S_{k}^{(η)})_{η⩽θ_{k+1}} and (R_{k}^{(η)})_{η⩽θ_{k+1}} are defined for some k ⩾ ℓ we define (S_{k+1}^{(η)})_{η⩽θ_{k+2}} extending (R_{k}^{(η)})_{η⩽θ_{k+1}} by applying (H_{θ_{k+2}}), then (R_{k+1}^{(η)})_{η⩽θ_{k+2}} by applying Lemma 8.2 to (S_{k+1}^{(η)})_{η⩽θ_{k+2}} with (θ, p) = (θ_{k+1}, k + 1).

It is easy to check that (R_{k+1}^{(η)})_{η⩽θ_{k+2}} extends (R_{k}^{(η)})_{η⩽θ_{k+1}} for all k, hence that there is a family (R^{(η)})_{η<ξ} such that

s R^{(η)} t ⟺ s R_{k}^{(η)} t for any k such that η_{k+1} ⩾ η

Set R^{(ξ)} = ⋂_{k} R_{k}^{(θ_{k})}. Clearly the family (R^{(η)})_{η⩽ξ} is an expansion family which is uniform at each limit level λ < ξ. It follows from the inductive construction that for each i ∈ I such that ξ_{i} < ξ the set π_{ξ_{i}}^{−1}(A_{i}) is open in [R^{(ξ_{i})}].

It remains only to prove that (R^{(η)})_{η⩽ξ} is uniform at level ξ and that π_{ξ}^{−1}(A_{i}) is open in [R^{(ξ)}] whenever ξ_{i} = ξ.

First observe that from the inductive construction we have : if s and t satisfy h_{R^{(θ_{k})}}(s) ⩽ k and s R^{(θ_{k})} t, for some k ⩾ ℓ, then for all m ⩾ k :

s R^{(θ_{m})} t and h_{R^{(θm)}}(s) ⩽ m ⟹ s R^{(θ_{m+1})} t and h_{R^{(θ_{m+1})}}(s) ⩽ h_{R^{(θm)}}(s) ⩽ m ⩽ m + 1

and this proves by induction on m that s R^{(ξ)} t.

We now prove that for s ∈ Dom(R^{(0)}) and k ⩾ ℓ, h_{R^{(ξ)}}(s) ⩽ k ⟺ h_{R^{(θ_{k})}}(s) ⩽ k. Indeed assume that h_{R^{(θ_{k})}}(s) ⩽ k; since R^{(ξ)} ⊂ R^{(θ_{k})}, we have h_{R^{(ξ)}}(s) ⩽ h_{R^{(θ_{k})}}(s) ⩽ k. Conversely, if h_{R^{(ξ)}}(s) ⩽ k and h_{R^{(θ_{k})}}(s) > k, there are t_{i} ≠ s for i ⩽ k such that t_{i} R^{(θ_{k})} s and h_{R^{(θ_{k})}}(t_{i}) = i. It follows from what precedes that t_{i} R^{(ξ)} t_{i+1} hence by induction on i ⩽ k that h_{R^{(ξ)}}(t_{i}) ⩾ i. Finally we also have t_{k} R^{(ξ)} s, hence h_{R^{(ξ)}}(s) > k.

Assume now that min(h_{R^{(ξ)}}(s), h_{R^{(ξ)}}(t)) ⩽ k and s R^{(θ_{k})} t. If h_{R^{(ξ)}}(s) ⩽ k and s R^{(θ_{k})} t, we have h_{R^{(θ_{k})}}(s) ⩽ k and s R^{(θ_{k})} t, hence s R^{(ξ)} t. On the contrary, if h_{R^{(ξ)}}(t) ⩽ k and s R^{(θ_{k})} t, we have h_{R^{(θ_{k})}}(t) ⩽ k and a fortiori h_{R^{(θ_{k})}}(s) ⩽ k; and we conclude as above that s R^{(ξ)} t.

Finally if i ∈ I with ξ_{i} = ξ, there is a subset J of I such that A_{i} = ⋃_{j∈J} A_{j} and ξ_{j} < ξ for all j in J. Since R^{(ξ_{j})} ⊂ R^{(ξ)}, the canonical mapping π_{ξ_{j},ξ} is continuous from [R^{(ξ)}] onto [R^{(ξ_{j})}], and the set π_{ξ_{j}}^{−1}(A_{j}) is open in [R^{(ξ_{j})}]. Thus π_{ξ}^{−1}(A_{j}) = π_{ξ_{j},ξ}^{−1}(π_{ξ_{j}}^{−1}(A_{j})) is open in [R^{(ξ)}]. And so is π_{ξ}^{−1}(A_{i}) = ⋃_{j∈J} π_{ξ}^{−1}(A_{j}).

And this completes the proof of Theorem 8.7. ■

Theorem 2.10 follows immediately from Theorem 8.7 since every completely uniform expansion family is strongly continuous.

Index of Definitions

I(s) . . . . . . . . . . . . . . . . . . . . . 6.1 J(s) . . . . . . . . . . . . . . . . . . . . . 6.1 R-strategical . . . . . . . . . . . . . . . 3.3 S^{τ} . . . . . . . . . . . . . . . . . . . . . . 4.4 μ(s) . . . . . . . . . . . . . . . . . . . . . 6.1 Φ^{τ} . . . . . . . . . . . . . . . . . . . . . . 4.4 adequate Baire type . . . . . . . . . 5.2 Baire type . . . . . . . . . . . . . . . . 1.2 canonical mapping . . . . . . . . . . 2.2 code . . . . . . . . . . . . . . . . . . . . . 1.1 compatible . . . . . . . . . . . . . . . . 6.1 completely uniform . . . . . . . . . . 8.1 distinguished relation . . . . . . . . 2.3 expansion family . . . . . . . . . . . . 2.6 game . . . . . . . . . . . . . . . . . . . . 3.1 hereditary . . . . . . . . . . . . . . . . 2.11 initializing position . . . . . . . . . . 6.1 monotone . . . . . . . . . . . . . . . . 2.11 optimal position . . . . . . . . . . . . 6.3 quasi-strategy . . . . . . . . . . . . . . 3.1 regular adequate Baire type … 5.2 resolution family . . . . . . . . . . . . 2.5 strongly continuous . . . . . . . . . 2.8 subordinate covering . . . . . . . . . 1.3 subordinate family . . . . . . . . . . 1.3 tree relation . . . . . . . . . . . . . . . 2.1 uniform . . . . . . . . . . . . . . . . . . 8.1 weak reduction . . . . . . . . . . . . . 1.4 weakly reducible . . . . . . . . . . . . 1.4

REFERENCES

[ 1 ] G. Debs and J. Saint Raymond, Borel liftings of Borel sets : some decidable

and undecidable statements, Memoirs of the Amer. Math. Soc. 187 ( 2007) no 876

[ 2 ] A. Louveau, A separation theorem for Σ_{1}^{1} sets Trans. Amer. Math. Soc. 260-2

(1980) 363-378

[ 3 ] A. Louveau and J. Saint Raymond, Borel classes and closed games : Wadge-

type and Hurewicz-type results. Trans. Amer. Math. Soc. 304-2 (1987) 431-467

[ 4 ] T.Matrai, Hurewicz tests : separating and reducing analytic sets on the

conscious way, thesis Central European University (2005)

[ 5 ] Y.N.Moschovakis, Descriptive Set Theory (North Holland, Amsterdam, 1980)

Gabriel DEBS Analyse Fonctionnelle Institut de Mathématique de Jussieu Boîte 186 4, place Jussieu 75252 Paris CEDEX 05 E-mail : gad@ccr.jussieu.fr Jean SAINT RAYMOND Analyse Fonctionnelle Institut de Mathématique de Jussieu Boîte 186 4, place Jussieu 75252 Paris CEDEX 05 E-mail : jsr@ccr.jussieu.fr