A COMBINATORIAL PROPERTY OF FRÉCHET ITERATED FILTERS

GABRIEL DEBS AND JEAN SAINT RAYMOND

Abstract. For all m ≥ 1 let N_{m} be the filter on ω^{m} obtained from the Fréchet filter on ω by iterating the Fubini product operation. One easily checks that N_{m} is a Σ_{2m}^{0} subset of P(ω^{m}) and the main result of this work states that in any Π_{2m}^{0} subset of P(ω^{m}) containing N_{m} one can find m + 1 elements with empty intersection.

1. Introduction

The Fréchet filters were introduced by Katětov in [3] to provide a Lebesgue-Hausdorff type representation of Borel functions (see Section 10 for more details). Let us recall that starting from N_{1} = N the standard Fréchet filter on ω one defines inductively for all m ≥ 1 the filter N_{m} on ω^{m} by:

M ∈ N_{m} ⟺ ∃i ∀j ≥ i M(j) ∈ N_{m−1}

where for all M ⊂ ω^{m} = ω×ω^{m−1} and all j ∈ ω, M(j) = {k̄ ∈ ω^{m−1} : (j, k̄) ∈ M} is the section of M at j.

Our goal is to prove the following result (Σ_{n}^{0} and Π_{n}^{0} denote the additive and the multiplicative Baire classes):

Theorem 1.1. In any Π_{2m}^{0} subset of P(ω^{m}) containing N_{m} one can find m + 1 elements with empty intersection.

Corollary 1.2. N_{m} is a Σ_{2m}^{0} filter which cannot be refined by any Π_{2m}^{0} filter.

The reader will find in the last section of the paper a detailed discussion on the motivation behind these results and their connection with the notion of rank for an analytic filter, introduced in [1].

The paper is entirely devoted to the proof of Theorem 1.1 which will actually be derived from a more technical result, namely Theorem 4.1. The precise statement of this latter result involves several elaborated abstract notions which we will introduce in the coming two sections. Despite its length the proof of Theorem 4.1 is organized in several independent parts that we will present and comment gradually in the sequel. We shall discuss in the last section various possible extensions of these results.

2000 Mathematics Subject Classification. Primary 03E15; Secondary 03E45, 54A20, 54H05.

Key words and phrases. Borel filters, Borel functions, Baire classes.

2. Preliminaries

In all this section E denotes an arbitrary fixed set. We shall fix the notation for some general notions and operations on the set E^{<ω} of all finite sequences in E. Depending on the context, to denote an element of E^{<ω} we shall use either a compact notation such as ā or the developed notation (a_{i})_{i<p}, where p = |ā| is the domain or the length of ā. We shall also denote by ⟨a⟩ the sequence of length 1 with value a ∈ E. The extension relation ⊂ should always be understood in the large sense, that is coarser than the equality relation.

2.1. Concatenation and intertwining:

We shall consider two natural operations on E^{<ω}. The first is the classical concatenation operation. Given two sequences ā and b̄ in E we shall denote simply by ā b̄ the sequence starting by ā followed by b̄.

The second operation is less standard and is actually a partial operation. Given two sequences ā = (a_{i})_{i<p} and b̄ = (b_{j})_{j<q} of length p and q with p − 1 ≤ q ≤ p, we shall denote by ā ⋆ b̄ the sequence of length p + q obtained by intertwining the elements of ā and b̄ starting from ā, so:

ā ⋆ b̄ = (c_{ℓ})_{ℓ<p+q} with c_{2k} = a_{k} and c_{2k+1} = b_{k} .

Also given any two subsets A, B of E^{<ω} we define:

A ⋆ B = {ā ⋆ b̄: ā ∈ A, ā ∈ B, |ā| − 1 ≤ |b̄| ≤ |ā|} .

2.2. The seq functor:

The following notation will avoid some possible confusion in the sequel. Given any family (a_{m})_{m∈M} ∈ E^{M} with domain M ⊂ ω we shall denote by

seq [(a_{n})_{m∈M} ]

the sequence (a_{m_{k}})_{k<card (M)} where (m_{k})_{k<card (M)} is the increasing enumeration of M.

2.3. Trees:

Trees will play a fundamental role in this work. For practical reasons we do not consider the empty set as a tree. So by a tree on E we shall mean a non empty subset of E^{<ω} which is hereditary with respect to the extension relation ⊂.

The rank rk(T) of a well-founded tree T is defined inductively by setting rk({∅}) = 0 and for all T ≠ {∅}:

rk(T) = sup{rk(T_{s}) + 1 , s ∈ T \ {∅}} ,

where T_{s} is the tree {u : s u ∈ T }.

So if T is of finite rank then rk(T) = sup{|s| , s ∈ T }; in particular the rank of ω^{≤n} is n.

We point out here that the definition of the rank given above is not universal. Indeed the initial value rk({0}) = 0 is related to our choice of excluding the empty set from the class of trees. But if one opts for the opposite choice then it is more natural to start with rk(∅) = 0 which gives rank n + 1 to ω^{≤n}.

We denote by Hom(T) the set of all tree homomorphisms on the tree T, that is all mappings φ : T → T satisfying for all s, t ∈ T:

1) |φ(s)| = |s|

2) if s ⊂ t then φ(s) ⊂ φ(t).

Finally given any tree T on E we denote by ⌊T ⌋ ⊂ E^{<ω} the set of its terminal elements, and as usual by ⌈T ⌉ ⊂ E^{ω} the set of all its infinite branches of T, and we set

[T] = ⌊T ⌋ ∪ ⌈T ⌉ ⊂ E^{<ω} ∪ E^{ω} .

2.4. Game trees:

Many notions concerning trees that we shall introduce in this work hide a game theoretical motivation though no win condition is a priori involved in their formal definition. In such a situation we shall speak about the game tree T suggesting thus that T is viewed as the support of some virtual game.

So a game tree is simply a tree T for which we intend to use the language of games. In this context the elements of T, ⌊T ⌋, ⌈T ⌉, [T] will then be called respectively: finite runs, maximal finite runs, infinite runs, maximal runs.

This is particularly convenient for notions for which the elements of the tree behave differently depending whether their length is even or odd, in which case one can replace the reference to the parity of the length by the more intuitive Player I / Player II duality of the language of games. Typical such examples are the notions of strategy or quasi-strategy which are meaningful for an arbitrary tree, in contrast with the notion of winning strategy which obviously refers to a complete game structure. Let us recall that a subtree S of a given game tree T is said to be a quasi-strategy for Player II in T if any element of odd length 2k + 1 in S has exactly the same immediate successors (of length 2k + 2) in both S and T.

2.5. Games:

We assume the reader to be familiar with all basic notions concerning games. Our goal here is just to fix some specific conventions to avoid possible ambiguity in further definitions.

Formally speaking we view a game on a given tree T as a pair (W_{I}, W_{II}) which forms a partition of the set [T] of all maximal runs (see Sections 2.3 and 2.4), though in practice we shall very often explicit only one or the other of these two sets. Notice that we do not impose on the tree T any particular condition. In particular maximal runs in the game might be finite as well as infinite.

Let J=I or II. A maximal run ā is said to be won by Player J if ā ∈ W_{J}. If Player J has a winning strategy in the game we shall say more simply that Player J wins the game.

3. Games on valued trees

We shall consider in this work a very specific class of games which we describe in this section.

3.1. The Part and Fin functors:

For any mapping f we denote by dom(f) its domain. If f : dom(f) → B with dom(f) ⊂ A we shall say that f is a partial mapping from A to B.

We shall denote by Part(A, B) the set of all partial mappings from A to B, which will always be implicitly endowed with the extension relation ⊂ induced by the inclusion relation on A × B. If B = {0, 1} which will be quite often the case then for any f ∈ Part(A, B) we set

supp(f) = {x ∈ dom(f) : f(x) = 1}

Of most importance for our study will be the subset of Part(A, B) constituted of all mappings with finite domain and which we will denote by Fin(A, B).

The set Part(A, B) will be equipped with the topology generated by the sets of the form:

N_{f} = {g ∈ Part(A, B) : f ⊂ g}

for f ∈ Fin(A, B). We can introduce now the central notion of valued tree.

Definition 3.2. An Ω-valuation or more simply a valuation on a set E is a mapping from E to Fin(Ω, 2) for some auxiliary countable set Ω.

Here by countable we mean infinite countable. In fact a substantial part of the results we shall prove do not require the countability assumption on Ω which is needed only for the main theorem.

Definition 3.3. Let ε : E → Fin(Ω, 2) be an Ω-valuation and T a tree on E.

a) We shall say that T is ε-coherent if for any ā = (a_{0}, a_{1}, …, a_{n}) ∈ T \ {∅} we have ε(a_{0}) ⊂ ε(a_{1}) ⊂ ⋯ ⊂ ε(a_{n}); we then set ε(ā) = ε(a_{n}).

b) We shall say that T is ε-free if for all ā ∈ T and all finite Λ ⊂ Ω there exists b ∈ E such that ā⟨b⟩ ∈ T and dom(ε(b)) ⊃ Λ.

c) We shall say that (T, ε) is a valued tree or more precisely an Ω-valued tree if the tree T is ε-coherent and ε-free.

Notice that if T is ε-free then T has no terminal branches, hence any maximal run in the game tree T is necessarily infinite. The following (obvious) lemma points out the fundamental property of a valued tree.

Lemma 3.4. If (T, ε) is an Ω-valued tree then Player II has a strategy in T for which any infinite compatible run (a_{n})_{n∈ω} satisfies that ⋃_{n∈ω} ↑ dom(ε(a_{n})) = Ω.

3.5. The games Γ_{A}(S, ε):

To any valuation ε : E → Fin(Ω, 2) on a set E we associate the tree

T_{ε} = {(a_{0}, a_{1}, …, a_{n−1}) ∈ E^{<ω} : ε(a_{0}) ⊂ ε(a_{1}) ⊂ ⋯ ⊂ ε(a_{n−1})}

which is the largest ε-coherent tree on E. We recall (see Definition 3.3 a) that for any ā = (a_{0}, a_{1}, …, a_{n}) ∈ T_{ε} \ {∅} we set ε(ā) = ε(a_{n}). We then consider the mapping:

ε̄: ⌈T_{ε}⌉ → Part(Ω, 2)

defined for all (a_{n})_{n∈ω} ∈ ⌈T_{ε}⌉ by:

ε̄((a_{n})_{n∈ω}) = ⋃_{n∈ω} ↑ ε(a_{0}, …, a_{n}) = ⋃_{n∈ω} ↑ ε(a_{n}) .

Then given any tree S on E and any set A ⊂ 2^{Ω} we denote by Γ_{A}(S, ε) the game on S ∩ T_{ε} in which Player II wins a given maximal run ā iff ā is infinite and ε̄(ā) ∈ A. We also set:

Γ(S, ε) = Γ_{2^{Ω}}(S, ε)

Observe that if ā is an infinite run in the game Γ_{A}(S, ε) then α = ε̄(ā) is a priori an element of Part(Ω, 2), so just a partial mapping on Ω. But if this run is won by Player II then α ∈ A ⊂ 2^{Ω} hence necessarily dom(α) = Ω. Lemma 3.4 can then be restated as follows:

Lemma 3.6. If (T, ε) is an Ω-valued tree then Player II wins the game Γ(T, ε).

A major part of the paper will consist in proving that Player II wins games of the form Γ_{A}(T, ε), and in this case winning in Γ(T, ε) is a minimal condition which, by Lemma 3.4, is automatically ensured if (T, ε) is a valued tree.

Let us also emphasize the fact that though Γ_{A}(S, ε) is a game on the ε-coherent tree S ∩T_{ε}, this game is defined for an arbitrary tree S on E. This might appear to the reader as a fake generality since Γ_{A}(S, ε) = Γ_{A}(S ∩ T_{ε}, ε). In fact as we mentioned above we shall be concerned in the sequel by proving that Player II wins games of the form Γ_{A}(T, ε) for some valued hence ε-coherent tree T. However a crucial step will consist in reducing this game to another “easier” game of the form Γ_{A}(S, ε) where S ⊃ T is no more ε-coherent, and the full generality of the definition of the games Γ_{A}(S, ε) is then fundamental.

Actually in a large part of the paper we shall work with valued trees of some special type that we introduce now.

Definition 3.7. Given any binary relation R on a set E we denote by T_{R} the tree of all finite R-chains:

T_{R} = {(a_{0}, a_{1}, …, a_{n−1}) ∈ E^{<ω} : ∀i < n, a_{i−1} R a_{i}}

A tree T on E will said to be generated by R if T = T_{R}

Notice that if T is generated by some binary relation R then R is uniquely determined by T since:

a R b ⟺ (a, b) ∈ T

We point out the characteristic fact that in games on such a tree the rules depend only on the last move. Of more particular interest for us will be the case where R is a partial ordering which should be viewed as a closure property for T. For example the transitivity of R states that any subsequence of a sequence in T is also in T.

Definition 3.8. An Ω-valued tree (T, ε) on a set E will said to be ordered if the tree T is generated by a partial ordering on E.

Lemma 3.9. Let ε be an Ω-valuation on a set E and T = T_{R} be a tree on E generated by a partial ordering R.

a) T is ε-coherent if and only if the mapping ε : E → Fin(Ω, 2) is R-monotone.

b) T is ε-free if and only if Player (I) II has a strategy in T for which any infinite compatible run (ā) satisfies dom(ε̄(ā)) = Ω.

4. Main result

We can now state the main result from which Theorem 1.1 will be derived:

Theorem 4.1. For all q ∈ ω there exists an ω^{1+q}-valued tree (T_{q}, ε_{q}) with the following two properties:

(A) For any winning strategy τ for Player II in the game Γ(T_{q}, ε_{q}) there exists a family of q + 2 infinite runs (ā^{r})_{r<q+2} compatible with τ such that ⋂_{r<q+2} supp(ε̄_{q}(ā^{r})) = ∅.

(B) For any Π_{2+2q}^{0} set A ⊃ N_{1+q} Player II wins the game Γ_{A}(T_{q}, ε_{q}).

\underline{Proof of Theorem 1.1 from Theorem 4.1}: Let A be a Π_{2+2q}^{0} subset of P(ω^{1+q}) containing N_{1+q}. Let τ be a winning strategy for Player II in the game Γ_{A}(T_{q}, ε_{q}) given by condition (B); then τ is a fortiori a strategy in the game Γ(T_{q}, ε_{q}). Now applying condition (A) to τ consider for all r < q + 2 the set M_{r} := supp(ε̄_{q}(ā^{r})): since τ is winning in Γ_{A}(T_{q}, ε_{q}) then each M_{r} is in A, and by condition (A) we have ⋂_{r<q+2} M_{r} = ∅. □

In the rest of this section we shall define the valued trees (T_{q}, ε_{q}) and this will already be a non trivial task. The definitions of ε_{q} and T_{q} will be achieved separately and will each of them necessitate the introduction of some additional notions. We shall also state, mostly without proofs, some basic elementary properties of these various objects. Detailed proofs, that we leave to the reader, can be obtained by direct application of the definitions or by straightforward inductions. We recall that in Theorem 4.1 the parameter q denotes a positive integer; however for practical reasons we shall introduce some of the auxiliary definitions for q = −1.

Definition 4.2. Given any set E we define the set:

Φ(E) = {((a^{(i)})_{i∈J} , (J^{0}, J^{1})) ∈ Fin(ω, E) × (P(ω))^{2} :
such that J^{0} ∪ J^{1} = J and J^{0} ∩ J^{1} = ∅}

and for all a = ((a^{(i)})_{i∈J} , (J^{0}, J^{1})) ∈ Φ(E) we set:

J_{a} = J , J_{a}^{0} = J^{0} , J_{a}^{1} = J^{1} .

The idea behind this definition is the following: we start from a set E with two “projects” P^{0}, P^{1} and we construct a set Φ(E) of a “higher type” in which each element is a family of finitely many copies of E on each of which we shall try to realize either P^{0} or P^{1}. The two “projects” we have in mind are the realizations of conditions (A) and (B) of Theorem 4.1. As one can see these conditions are totally unrelated and the use of different copies to realize them is more or less necessary. So coming back to this heuristic interpretation an element a of Φ(E) appears as a finite family (a^{(i)})_{i∈J} in the lower level set E and the partition (J^{0}, J^{1}) announces the indices i ∈ J where we have in mind to realize the projects P^{0} and P^{1}. Clearly the parametrization (J, J^{0}, J^{1}) is redundant since this triple is entirely determined by any pair of its coordinates, however we shall keep working with this representation. Also if we identify the pair (J^{0}, J^{1}) to a {0, 1} valued mapping on J then we can write up to obvious identifications:

Φ(E) = Fin(ω, E × 2) .

Notice that if ã ∈ Fin(ω, E × 2) is identified to a = ((a^{(i)})_{i∈J} , (J^{0}, J^{1})) ∈ Φ(E) then dom(ã) = J_{a} and we shall also write dom(a) = J_{a}; moreover for all i ∈ J_{a}, ã(i) ∈ E × 2 while a^{(i)} ∈ E is the first coordinate of the pair ã(i) (observe the use of the upper index in the notation a^{(i)} to avoid any possible confusion).

Definition 4.3. For all q ≥ 0 let ε_{q} : E_{q} ↦ Fin(ω^{1+q}, 2) be the valuation defined inductively by:

– ε_{0} is the identity mapping on E_{0} = Fin(ω, 2).

– E_{q+1} = Φ(E_{q}) and for all a = ((a^{(i)})_{i∈J} , (J^{0}, J^{1})) ∈ E_{q+1}

ε_{q+1}(a) = ⋃_{i∈J}{i}× ε_{q}(a^{(i)}) .

The definition of the trees T_{q} is more involved. First these trees will indeed be generated by binary relations R_{q} which happen to be partial orderings, so T_{q} = T_{R_{q}} (see Definition 3.7), and what we will really define are the relations R_{q}. This definition will again be by induction.

As in the case of the ε_{q} we shall start by introducing a number of operators on binary relations involved in the induction scheme.

Definition 4.4. To any pair (S_{0}, S_{1}) of binary relations on E we associate two binary relations

S= Ψ(S_{0}, S_{1}) , S^{1}= Ψ^{1}(S_{0}, S_{1})

on Φ(E) defined by:

a S b ⟺ \begin{cases}J_{a}^{0} ⊂ J_{b}^{0} and ∀i ∈ J_{a}^{0}, a^{(i)} S_{0} b^{(i)} \\ J_{a}^{1} ⊂ J_{b}^{1} and ∀i ∈ J_{a}^{1}, a^{(i)} S_{1} b^{(i)} \end{cases} ,
a S^{1} b ⟺ a S b and J_{a}^{0} = J_{b}^{0} .

The reader who might be disturbed by the switch of the indices 0 and 1 in the last definition should recall that a condition like J_{a}^{0} = J_{b}^{0} means that in b there is no new tentative of P^{0} projects, hence all new projects in b are P^{1} projects and this explains the upper index in S^{1}.

In fact in the sequel we shall apply these operations to partial orderings and in this setting we have the following:

Proposition 4.5. If the relations S_{0} and S_{1} are partial orderings then so are S= Ψ(S_{0}, S_{1}) and S^{1}= Ψ^{1}(S_{0}, S_{1}).

Definition 4.6. Let (E_{q})_{q≥0} be given by Definition 4.3 and set E_{−1} = 2.

For all q ≥ 0 let (R_{q}, R_{q}^{1}) be the pair of partial orderings on E_{q}, defined inductively by:

\{ \begin{matrix}a R_{−1} b ⟺ a = b & , & a R_{−1}^{1} b ⟺ a = b = 1 , \\ R_{q+1} = Ψ(R_{q}^{0}, R_{q}^{1}) & , & R_{q+1}^{1} = Ψ^{1}(R_{q}^{0}, R_{q}^{1}) . \end{matrix}

Finally let T_{q} denote the tree T_{R_{q}} generated by the relation R_{q}.

In particular R_{0} is the extension relation on E_{0} = Fin(ω, 2) while R_{0}^{1} is the “extension by 1” relation on Fin(ω, 2). For q ≥ 1 the domain E_{q} is of the form Fin(ω, Ω) and the binary relation R_{q} is strictly finer than the extension relation on E_{q}.

Proposition 4.7. For all q ≥ 0 , (T_{q}, ε_{q}) is an ω^{1+q}-ordered valued tree.

We also state some elementary properties of the companion relations R_{q}^{1}.

Proposition 4.8. For all q ≥ 0 , R_{q}^{1}⊂ R_{q}. Moreover:

∀a, b such that a R_{q} b, ∃ b′ such that: ε_{q}(b′) = ε_{q}(b) and a R_{q}^{1} b′. In particular R_{q}^{1} is ε_{q}-free.

More fundamental is the following property, which gives an indication on the role that will play the relations R_{q}^{1} in our study.

Proposition 4.9. For any R_{q}^{1}-chain (a_{n})_{n∈ω} in E_{q} one can find α ∈ N_{1+q} such that ⋃_{n∈ω} ε_{q}(a_{n}) ⊂ α. In particular if ⋃_{n∈ω} dom(ε_{q}(a_{n})) = ω^{1+q} then ⋃_{n∈ω} ε_{q}(a_{n}) ∈ N_{1+q}.

Proof. The proof is by induction.

For q = 0 the result is obvious since in this case R_{0}^{1} is the “extension by 1” relation on E_{0} = Fin(ω, 2).

Suppose that the result is true for some q. Observe that by Definition 4.6 we have: R_{q+1}^{1} = Ψ^{1}(R_{q}, R_{q}^{1}).

Let (a_{n})_{n∈ω} be an R_{q+1}^{1}-chain in E_{q+1}. Following the notation of Definition 4.4 we have:

J_{a_{0}}^{0} = ⋯ = J_{a_{n}}^{0} = J_{a_{n+1}}^{0} = … ; J_{a_{0}}^{1} ⊂ ⋯ ⊂ J_{a_{n}}^{1} ⊂ J_{a_{n+1}}^{1} ⊂ … and ∀k, ∀i ∈ J_{a_{k}}^{1}, a_{k}^{(i)} R_{1} … R_{1} a_{n}^{(i)} R_{1} a_{n+1}^{(i)} R_{1} …

Set J^{0} = J_{a_{0}}^{0}, J_{n}^{1} = J_{a_{n}}^{1} for all n, and J^{1} = ⋃_{n∈ω} J_{n}^{1}. Then for all i ∈ J^{1} if k_{i} denotes the first k such that i ∈ J_{k}^{1} then (a_{n}^{(i)})_{n≥k_{i}} is an R_{1}-chain, hence by hypothesis we can find some α^{(i)} ∈ N_{q+1} such that ⋃_{n≥k_{i}} ε_{q}(a_{n}^{(i)}) ⊂ α^{(i)}.

On the other hand since (a_{n})_{n∈ω} is an R_{q+1}-chain then by Proposition 4.7 ε_{q+1}((a_{n}))_{n∈ω} is a chain in Fin(ω^{q+2}, 2), hence for all i ∈ J = J^{0}∪J^{1}, ε_{q}((a_{n}^{(i)}))_{n∈ω} is a chain in Fin(ω^{q+1}, 2). In particular for all i ∈ J^{0}, we can fix some α^{(i)} ∈ 2^{ω^{q+1}} such that ⋃_{n≥0} ε_{q}(a_{n}^{(i)}) ⊂ α^{(i)}.

This defines α^{(i)} for all i ∈ J. Finally for i ∉ J let α^{(i)} = 1_{ω^{q+1}} ∈ 2^{ω^{q+1}} be the constant function 1 on ω^{q+1} and consider α = ⋃_{n∈ω}{i} × α^{(i)} ∈ 2^{ω×ω^{q+1}} ≈ 2^{ω^{q+2}}.

Then for all i ∉ J^{0}, α^{(i)} ∈ N_{q+1} hence α ∈ N_{q+2}. Moreover by the definition of ε_{q+2} for all n, ε_{q+2}(a_{n}) = ⋃_{i∈J^{0}∪J_{n}^{1}}{i}× ε_{q+1}(a^{(i)}) ⊂ ⋃_{i∈J^{0}∪J_{n}^{1}}{i}× α^{(i)} ⊂ α which is the desired conclusion. □

The rest of the paper is devoted to the proof of conditions (A) and (B) of Theorem 4.1. Rather surprisingly the proof of condition (A) will be much simpler than the proof of the more standard condition (B) which will actually be derived from a very technical (stronger) condition (B^{∗}) which we will introduce later on.

5. Nilpotent valued trees

The aim of this section is to reformulate condition (A) of Theorem 4.1 in terms of games. More precisely we shall show that this condition is equivalent to the non existence of a winning strategy for Player II in some kind of product game. But it turns out that the statement asserting that Player I has a winning strategy in this same game yields a much more flexible and efficient condition.

For the notation “seq” in next definition we refer the reader to Section 2.2.

Definition 5.1. Let q ≥ 1 be a fixed integer and denote by ≡ the equality mod q. Given any (finite or infinite) sequence ā = (a_{m})_{m<N} ∈ E^{<N} let, for all r < q:

ā^{r} = seq [(a_{m})_{m<N ∧[\frac{m}{2}]≡r}] ,

where [\frac{m}{2}] denotes the integer part of \frac{m}{2}.

We shall say that (ā^{r})_{r<q} is the double cyclic decomposition of ā and write:

ā = ⟨ā^{r}⟩_{r<q} .

Notice that the integer q is encoded by the length of the family (ā^{r})_{r<q}, and in general we shall not explicit this parameter when considering a particular double cyclic decomposition.

A more dynamic and intuitive picture of the previous definition is to consider that the elements of the initial sequence ā are spread out, two by two, onto q columns as shown in the following diagram.

ā^{0}  ā^{1} . . . . . . . . . ā^{r} . . . . . . . . . ā^{q−1}
a_{0}  a_{2} . . . . . . . . . a_{2r} . . . . . . . . . a_{2(q−1)}
a_{1}  a_{3} . . . . . . . . . a_{2r+1} . . . . . . a_{2q−1}
a_{2q} a_{2q+2} . . . . . . . . . . . . . . . . . . . . . a_{4q−2}
a_{2q+1} a_{2q+3} . . . . . . . . . . . . . . . . . . . . . a_{4q−1}
⋮
⋮
a_{2m}
a_{2m+1}
a_{2m+2q}
⋮

If ā is infinite then so are all the ā^{r}. Also if ā is finite then so are all the ā^{r}, but not necessarily of the same length. More precisely if |ā| = n ≡ s < q and if we set ℓ = [\frac{n}{q}] then |ā^{r}| is equal to 2ℓ + 2 for r < s and to 2ℓ for r > s, while

|ā^{s}| = 2ℓ + 1 or 2ℓ + 2 and is determined by the condition |ā^{s}| = |ā| (mod 2).

Definition 5.2. The double cyclic amalgamation of the family (T_{r})_{r<q} of trees on the set E is the tree T = ⨂_{r<q} T_{r} on E defined by:

T = {ā = ⟨ā^{r}⟩_{r<q} ∈ E^{<ω} : ∀r < q, ā^{r} ∈ T_{r}} .

If T_{r} = S for all r < q we shall write T = S^{⊗ q}.

For a better intuition one should think to the trees T_{r} and T as game trees. Then a run ā = (a_{m})_{m<n} in ⨂_{r<q} T_{r} can be viewed as q runs ā^{0}, …, ā^{q−1} in the game trees T_{0}, …, T_{q−1} respectively played as in the previous diagram.

More precisely the first two moves in ā are actually made in the game tree T_{0}, then the next two moves in ā are two initial moves in the game tree T_{1}, and so on up to the 2q first moves in ā; then again the players come back to T_{0} and make two new successive moves, then to T_{1} and so on …. Observe that the players in each of the runs ā^{r} are in the same position as in ā, that is a move made by some player in ā is interpreted as a move made by the same player in ā^{r}. However while Player II moves in each of the runs ā^{r} follow immediately Player I moves exactly as in ā, Player I moves in ā^{r} are achieved with a delay of length 2q − 1.

Definition 5.3. For any valued tree (T, ε) let N_{q}(T, ε) be the game on the tree T^{⊗ q} in which Player I wins a maximal run ā = ⟨ā^{r}⟩_{r<q} iff:

∀i ∈ ⋂_{r<q} dom(ε̄(ā^{r})), ∃n, ε(a_{n})(i) = 0 .

A valued tree (T, ε) is said to be q-nilpotent if Player I has a winning strategy in the game N_{q}(T, ε).

Observe that if ε is an Ω-valuation and ā = ⟨ā^{r}⟩_{r<q} is a maximal run in T^{⊗q} then each ā^{r} is an infinite branch of T_{ε}, hence if ā = (a_{n})_{n∈ω} then

ε̄(ā^{r}) = ⋃_{m≡r} ε(a_{2m}) = ⋃_{m≡r} ε(a_{2m+1})

is an element of Part(Ω, 2) (we recall that ε(a_{2m}) ⊂ ε(a_{2m+1}) ⊂ ε(a_{2m+2q})).

Proposition 5.4. Let (T, ε) be an Ω-valued tree. If Player II has no winning strategy in the game N_{q}(T, ε), in particular if (T, ε) is q-nilpotent, then for any strategy τ for Player II in the game tree T there exists a family of q infinite runs (ā^{r})_{r<q} compatible with τ such that ⋂_{r<q}{i ∈ dom(ε̄(ā^{r})) : ε̄(ā^{r})(i) = 1} = ∅.

Proof. Any strategy τ for Player II in T induces a strategy τ^{⋆} for Player II in T^{⊗q} such that for any run ā = ⟨ā^{r}⟩_{r<q} compatible with τ^{⋆} each partial run ā^{r} is compatible with τ. Hence, since Player II has no winning strategy in the game N_{q}(T, ε), there exists a maximal run ā in N_{q}(T, ε) compatible with τ^{⋆} and which is won by Player I. It follows then from the win condition of this game that ⋂_{r<q}{i ∈ dom(ε̄(ā^{r})) : ε̄(ā^{r})(i) = 1} = ∅. □

6. Proof of condition (A)

In view of Proposition 5.4, condition (A) of Theorem 4.1 follows from the following result.

Theorem 6.1. For all q ≥ 0 the valued tree (T_{q}, ε_{q}) is q + 2-nilpotent.

Proof. The proof is by induction over q.

a) The initial case q = 0:

Let us recall that R_{0} is the extension relation on E_{0} = Fin(ω, 2) and ε_{0} : E_{0} → Fin(ω, 2) is the identity mapping. Let φ : E_{0} → E_{0} denote the “flip” automorphism on Fin(ω, 2) defined for all a ∈ Fin(ω, 2) by:

dom(φ(a)) = dom(a) and φ(a)(i) = 1 − a(i) .

We now show that the valued tree (T_{0}, ε_{0}) is 2-nilpotent by defining a strategy σ for Player I in N_{2}(T_{0}, ε_{0}) as follows:

– At his first move in σ Player I chooses a_{0} = ∅.

– Suppose that the run ā = (a_{0}, a_{1}, …, a_{2n+1}) is compatible with σ then Player I answers a_{2n+2} = φ(a_{2n+1}).

Notice that since φ is an involution then a_{2n+1} = φ(a_{2n+2}) and since ā ∈ T_{0}^{⊗ 2} then necessarily φ(a_{2n−1}) = a_{2n} R_{0} α_{2n+1} = φ(a_{2n+2}) , hence a_{2n−1} R_{0} a_{2n+2} . So a_{2n+2} is indeed a legal move in T_{0}^{⊗ 2}.

Consider now an infinite run ā = (a_{m})_{m∈ω} in T_{0}^{⊗ 2} compatible with σ and let ā = ⟨ā^{0}, ā^{1}⟩ be the double cyclic decomposition of ā so:

ā^{0} = (a_{0}, a_{1}, … a_{4k}, a_{4k+1}, …) and ā^{1} = (a_{2}, a_{3}, … a_{4k+2}, a_{4k+3}, …)

are both in T_{0}. Then and by definition of σ we have

dom(ε̄_{0}(ā^{0})) = dom(ε̄_{0}(ā^{1})) = ⋃_{n≥0} dom(ε_{0}(a_{2n+1})) = ⋃_{n≥0} dom(ε_{p}(a_{2n+2})) ,

and since a_{2n+2} = φ(a_{2n+1}) then for all i in dom(ε_{0}(a_{2n+2})) = dom(ε_{p}(a_{2n+1})) we have ε_{0}(a_{2n+2}) ▪ ε_{0}(a_{2n+1})(i) = 0.

This proves that the strategy σ is winning in the game N_{2}(T_{0}, ε_{0}) and finishes the proof of the initial case q = 0.

b) The inductive step:

Assume that the valued tree (T_{q}, ε_{q}) is q + 2-nilpotent and set:

R =R_{q}  R^{1} = R_{q}^{1}  ε = ε_{q}  T = T_{q}  Ω = ω^{q+1}
R̃ =R_{q+1}  R̃^{1} = R_{q+1}^{1}  ε̃ = ε_{q+1}  T̃ = T_{q+1}  q̃ = q + 3

and denote by ≡ the equality mod q̃ relation on integers.

We recall that ε : dom(ε) → Fin(Ω, 2) and ε̃: dom(ε̃) → Fin(ω × Ω, 2) are two valuations with dom(ε̃) = Φ(dom(ε)), T = T_{R} is a tree on dom(ε) and T̃ = TR̃ is a tree on dom(ε̃), and R̃= Ψ(R, R^{1}) ⊃R̃^{1}= Ψ^{1}(R, R^{1}) are two binary relations on dom(ε̃), (see Section 4 for more details).

Let us also recall that given any positive integer s a move in T̃^{⊗ s} is just a move in T̃ that is an element of dom(ε̃) = Φ(dom(ε)), while a run in T̃^{⊗ s} is decoded (via the double cyclic decomposition) into s runs in T̃. Moreover any element a of dom(ε̃) = Φ(dom(ε)) can be written under the form ((a^{(i)})_{i∈J}, (J^{0}, J^{1})) where J = J_{a} is a finite subset of ω, (J^{0}, J^{1}) is a partition of J, and a^{(i)} ∈ dom(ε) for all i ∈ J.

Fix a winning strategy σ for Player I in the game N_{q+2}(T, ε). We are going to describe a winning strategy σ̃ for Player I in the game Nq̃(T̃, ε̃).

– At his first move in σ̃ Player I chooses a_{0} = ∅ ∈ dom(ε̃) and we set J_{0} = ∅.

– Suppose that for n > 0 the run ā = (a_{k})_{0≤k<2n} is compatible with σ̃. Then by definition of T̃^{⊗ q̃} for all m < n we necessarily have:

J_{a_{2m}}^{0} ⊃ J_{a_{2m−1}}^{0} ⊃ J_{a_{2m−2q̃}}^{0} and J_{a_{2m}}^{1} ⊃ J_{a_{2m−1}}^{1} ⊃ J_{a_{2m−2q̃+1}}^{1} ,

hence

J_{a_{2m}} ⊃ J_{a_{2m−1}} ⊃ J_{a_{2m−2q̃+1}} ,

but the strategy σ̃ will actually ensure the stronger conditions:

J_{a_{2m}} = J_{a_{2m−1}} and J_{a_{2m}}^{1} = J_{a_{2m−2q̃+1}}^{1} ,

so

J_{a_{2m}}^{0} = J_{a_{2m}} \ J_{a_{2m}}^{1} = J_{a_{2m}} \ J_{a_{2m}−2q̃+1}^{1} ⊃ J_{a_{2m}} \ J_{a_{2m}−2q̃+1}

⊃ J_{a_{2m}} \ J_{a_{2(m−q̃+1)}} = ⋃_{2(m−q̃+1)≤ℓ<m} J_{a_{2(ℓ+1)}} \ J_{a_{2ℓ}} ,

hence by induction:

J_{a_{2m}}^{0} ⊃ ⋃_{{ℓ<m \atop ℓ≢m}} J_{a_{2(ℓ+1)}} \ J_{a_{2ℓ}} .

Now let:

a_{2n} = ((a_{2n}^{(i)})_{i∈J_{n}}, (J_{n}^{0}, J_{n}^{1}))

with as above:

J_{n} = J_{a_{2n−1}} , J_{n}^{1} = J_{a_{2n−2q̃+1}}^{1} , J_{n}^{0} = J_{n} \ J_{n}^{1} ⊃ ⋃_{{m<n \atop m≢n}} J_{m+1} \ J_{m} , and for all i ∈ J_{n}:

a_{2n}^{(i)} = \begin{cases}a_{2n−1}^{(i)} & if i ∈ J_{m+1} \ J_{m} with m ≡ n , \\ σ(seq [(a_{k}^{(i)})_{2m+2≤k<2n ∧ [\frac{k}{2}]≢m}]) & if i ∈ J_{m+1} \ J_{m} with m ≢ n . \end{cases}

First we have to check that this definition is consistent and defines a legal move in the game. For this fix m < n and set:

b̄ = seq [(a_{k})_{2m+2≤k<2n ∧ [\frac{k}{2}]≢m}] = (b_{k})_{k<N} .

Let ā = ⟨ā^{r}⟩_{r<q̃} and b̄ = ⟨b̄^{s}⟩_{s<q̃−1} be respectively the q̃ and the q̃ − 1 double cyclic decomposition of ā and b̄.

Lemma 6.2. For all s < q̃− 1 there exists a unique r < q̃ with r ≢ m such that b̄^{s} is a final segment of the sequence ā^{r}; in particular b̄ ∈ T̃^{⊗(q̃−1)}.

Proof. Represent the family ⟨ā^{r}⟩_{r<q̃} as a matrix with q columns and observe that the set M = {k : 2m+2 ≤ k < 2n and k ≢ m} is invariant under 2q̃ translations. Moreover an even integer 2ℓ is in M if and only if its successor 2ℓ + 1 is in M. It follows then that each column b̄^{s} is a final segment of some ā^{r}. More precisely if we write ā^{r} = (a_{k})_{k∈K_{r}} for some K_{r} ⊂ 2n and set ¯ ā^{r} = seq [(a_{k})_{k∈K_{r} ∧ k≥2m+2} ] then {b̄^{s} : s < q̃ − 1} = {¯ā^{r} : r < q̃ , r ≢ m}. This proves the first part of the lemma.

Now since ā ∈ T̃^{⊗ q̃} then by definition each ā^{r} ∈ T̃ = T_{R̃}, so each ā^{r} forms an R̃-chain and consequently each b̄^{s} too, hence b̄ ∈ T̃^{⊗(q̃−1)}. □

Let c̄ = (c_{k})_{k<K} be a given sequence in a set of the form Φ(E); then to any i ∈ ⋂_{k<K} J_{c_{k}} we can assign the sequence c̄^{(i)} = (c_{k}^{(i)})_{k<K} in E.

Lemma 6.3. If c̄ ∈ T̃^{⊗ s} then c̄^{(i)} ∈ T^{⊗ s}.

Proof. Fix k < K :

– If k = 2ℓ + 1 then it follows from the definition of T^{⊗ s} that c_{2ℓ} R̃ c_{2ℓ+1}. Hence by definition of R̃= Ψ(R, R^{1}) we have either c_{2ℓ}^{(i)} R c_{2ℓ+1}^{(i)} or c_{2ℓ}^{(i)} R^{1} c_{2ℓ+1}^{(i)} depending whether i is in J_{c_{2ℓ}}^{0} or J_{c_{2ℓ}}^{1}. But since R̃^{1}= Ψ^{1}(R, R^{1}) ⊂ R̃= Ψ(R, R^{1}) then we always have c_{2ℓ}^{(i)} R c_{2ℓ+1}^{(i)}.

– Similarly if k = 2ℓ + 2r then c_{2ℓ+1} R̃ c_{2ℓ+2r} and by the same arguments as above one gets c_{2ℓ+1}^{(i)} R c_{2ℓ+2r}^{(i)}. □

Coming back to the definition of a_{2n} observe that if i ∈ J_{m+1} \ J_{m} with m ≢ n then with the notation introduced above we can write a_{2n}^{(i)} = σ(b̄^{(i)}). Now by Lemma 6.2 , b̄ ∈ T̃^{⊗(q̃−1)} and it follows then from Lemma 6.3 that b̄^{(i)} ∈ T̃^{⊗(q̃−1)} too, which by a straightforward induction shows that b̄^{(i)} is in the domain of σ. Hence a_{2n} is well defined.

Lemma 6.4. a_{2n} is a legal move in the game tree T̃^{⊗ q̃}.

Proof. We have to check that a_{2n−1} R̃ a_{2n} that is:

1) J_{a_{2n}}^{0} ⊃ J_{a_{2n−1}}^{0} and J_{a_{2n}}^{1} ⊃ J_{a_{2n−1}}^{1} ,

2) ∀i ∈ J_{a_{2n}}^{0}, a_{2n−1}^{(i)} R a_{2n−1}^{(i)} and ∀i ∈ J_{a_{2n}}^{1}, a_{2n−1}^{(i)} R^{1} a_{2n−1}^{(i)} . The first condition is ensured by construction. To check the second condition fix i ∈ J_{a_{2n}} = J_{n} and m such that i ∈ J_{m+1} \ J_{m}:

– if m ≡ n then a_{2n}^{(i)} = a_{2n−1}^{(i)} and we are done;

– if m ≢ n then as observed above we necessarily have i ∈ J_{a_{2n}}^{0}; moreover by definition, in the present case a_{2n}^{(i)} = σ(b̄_{m}^{(i)}) which implies that a_{2n−1}^{(i)} R a_{2n−1}^{(i)} since σ is a strategy for Player I in T^{⊗(q+2)} = T^{⊗(q̃−1)}. □

Lemma 6.5. The strategy σ̃ is winning in the game Nq̃(T̃, ε̃).

Proof. Let ā = ⟨ā^{r}⟩_{r<q̃} be an infinite run in this game and fix

(i, ī) ∈ ⋂_{r<q̃} dom(¯ε̃(ā^{r})) ⊂ ω × Ω .

Let m be such that i ∈ J_{m+1} \ J_{m} and b̄ = seq [(a_{k})_{2m+2≤k<2n ∧ [\frac{k}{2}]≢m}] and let

b̄ = ⟨b̄^{s}⟩_{s<q̃−1} be the q̃ − 1 double cyclic decomposition of b̄. By Lemma 6.2 for all s < q̃ − 1 there exists a unique r_{s} < q̃ with r_{s} ≢ m such that b̄^{s} is a final segment of ā^{r_{s}}, hence b̄^{(i)} = ⟨(b̄^{s})^{(i)}⟩_{s<q̃−1} is a final segment of some (b̄^{r_{s}})^{(i)} too.

Now by the definition of ε̃ we have ī ∈ ⋂_{r<q̃} dom(ε̄((b̄^{r})^{(i)})) and a fortiori ī ∈ ⋂_{s<q̃−1} dom(ε̄((b̄^{r_{s}})^{(i)})) and since the strategy σ is winning in the game N_{q̃−1}(T, ε) then there exists some coordinate a_{n}^{(i)} of the sequence b̄^{(i)} (which is also a coordinate of the sequence ā^{(i)}) such that ε(a_{n}^{(i)})(ī) = 0 hence ε̃(a_{n})(i, ī) = ε(a_{n}^{(i)})(ī) = 0 too, which proves that Player I wins the run ā. □

This finishes the proof of the inductive step and consequently Theorem 6.1. □

So Theorem 6.1 ensures condition (A) of Theorem 4.1, and our next goal is to prove condition (B) which will be a much harder task, necessitating the introduction of several new concepts. Note however that, aside for general basic notions, this second part of the paper will be totally independent from the first one. In particular we shall no more refer to nilpotent games in the sequel.

7. Ordered valued trees

This section is essentially self-contained. The main result proved here will constitute a key step in the proof of condition (B) but is quite general and presents a significant interest in itself. The precise statement of this result is rather technical and we shall give in the coming lines a brief sketch of its content.

Given any ordered Ω-valued tree (T, ε) we shall prove that for any Borel set A ⊂ 2^{Ω} the game Γ_{A}(T, ε) is equivalent to some specific game of the form Γ_{A}(S, ε) for some tree S on dom(ε). Notice that the new tree S will not be generated by a partial ordering, nor an ε-coherent tree (we recall that the game Γ_{A}(S, ε) is defined for an arbitrary tree on dom(ε)). The main gain in this transformation is that the new game is formally more favourable for Player II, so a priori one can more easily find winning strategies for Player II in Γ_{A}(S, ε). The precise definition of the operator T ↦ S necessitates some preliminaries.

Definition 7.1. A tree enumeration for a countable tree Σ is a one-to-one mapping ν : Σ → ω satisfying ν(∅) = 0 and for all s, t ∈ Σ:

1) ν(s) ≡ |s| (mod 2)

2) if s ⊂ t then ν(s) ≤ ν(t).

Imposing condition 2) when enumerating a tree is quite standard. But in our study the parity of |s| is a crucial parameter and condition 1) will be fundamental.

Definition 7.2. Let Σ be a countable tree.

a) Σ will said to be semi-linear (s.l.) if any element in Σ of odd length 2k + 1 has at most one extension in Σ of length 2k + 2.

b) A tree enumeration ν : Σ → ω on Σ will said to be semi-linear if for any element s ∈ Σ of even length 2k + 2 if s^{∗} = s_{|2k+1} then ν(s) = ν(s^{∗}) + 1.

We shall then say that (Σ, ν) – or more simply Σ if ν is implicitly fixed – is an enumerated semi-linear tree (e.s.l. tree ).

The significance of the semi-linearity conditions will be clarified soon. Let us only point out here that the existence of a s.l. enumeration for a tree Σ implies that the tree Σ itself is s.l.. Conversely any countable semi-linear tree Σ admits a s.l. tree enumeration ν. Notice however that, unless all terminal elements of Σ are of even length, one cannot impose on ν to be surjective. Nevertheless ν(Σ) is not an arbitrary subset of ω, since whenever it contains an even element 2k + 2 it automatically contains its predecessor 2k + 1.

Definition 7.3. Let (Σ, ν) be an e.s.l. tree. To any non empty tree T on a set E we associate a new tree on E that we denote by T^{(Σ,ν)} defined by:

T^{(Σ,ν)} = \{(a_{m})_{m<n} ∈ E^{<ω} : ∀m < n, \begin{matrix}– if m = ν(s) then (a_{ν(s_{|k})})_{k≤|s|} ∈ T \\ – if m ∉ ν(Σ) then a_{m} = a_{m−1} \end{matrix} \}

Again if ν is implicitly fixed we shall write T^{(Σ)} instead of T^{(Σ,ν)}.

Observe that the condition “a_{m} = a_{m−1} if m ∉ ν(Σ)” in the previous definition is coherent since 0 = ν(∅) is always an element of ν(Σ).

We shall explain now the intuition behind the semi-linearity conditions and the trees T^{(Σ,ν)}. Let us emphasize first that in the definition of T^{(Σ,ν)} the trees Σ and T play totally different roles. More precisely one should view Σ as an “abstract” coding tree by opposition to T which appears as a “concrete” tree. Notice in particular that Σ and T are not assumed to be trees on the same set, and as a matter of fact in all applications T will be one of the trees T_{q} on E_{q} while Σ will be a tree on ω.

Once again for a better understanding one should think to T as a game tree. Then T^{(Σ,ν)} can be viewed as a new game tree in which the players are playing several runs in T. More precisely a run ā = (a_{m})_{m≤n} in T^{(Σ,ν)} can be identified with the finite family of runs ā^{s} = (a_{ν(s_{|k})})_{k≤|s|} in T, with s ∈ Σ such that ν(s) ≤ n (one could also restrict this family to the maximal such s). Notice that the set of all the runs ā^{s} with ν(s) ≤ n, constitutes then a finite subtree of T of order type at most Σ. The role of the parity condition in Definition 7.1 is then to ensure that in all the runs ā^{s} in T the players are in the same position (I or II) as in the initial run ā in T^{(Σ,ν)}. But to determine a run in T^{(Σ,ν)} the runs ā^{s} in T have to be played in a linear order, actually determined by the enumeration ν, hence necessarily at a lower speed than ā. In particular the answer of a player in ā^{s} (which corresponds to a move of the same player in ā) to his opponent’s last move cannot always be at the immediate next move in ā. And the role of the semi-linearity condition on ν is precisely to ensure that this will actually be the case for Player I, that is aside at his first move, Player I plays in ā^{s} immediately after Player II, exactly as in the run ā. Of course, unless Σ is linear (in which case T^{(Σ,ν)} = T), one cannot ensure simultaneously the same privilege to Player II.

Finally observe that the definition of T^{(Σ,ν)} does not refer to any valuation though we shall use it only in the setting of an ordered Ω-valued tree (T, ε). Notice once again that while the tree T is by definition ε-coherent this is no more the case for T^{(Σ,ν)}, hence for any A ⊂ 2^{Ω}, Γ_{A}(T^{(Σ,ν)}, ε) is a game on T^{(Σ,ν)} ∩ T_{ε} and not on T^{(Σ,ν)}.

Proposition 7.4. Let (T, ε) be an ordered Ω-valued tree and A ⊂ 2^{Ω}. If Player II wins the game Γ_{A}(T, ε) then Player II wins the game Γ_{A}(T^{(Σ)}, ε) for any e.s.l. tree Σ.

Proof. Let ν be the s.l. enumeration of Σ and R be the partial ordering generating T. Given any strategy τ for Player II in the game Γ_{A}(T, ε) let τ^{Σ} be the partial mapping on E^{<ω} defined by:

τ^{Σ}((a_{k})_{k≤2p}) = \{ \begin{matrix}τ(seq [(a_{k})]_{k≤2p ∧ k∈ν(Σ)}) & if 2p + 1 ∈ ν(Σ) \\ a_{2p} & if 2p + 1 ∉ ν(Σ) \end{matrix}

and let ā = (a_{n})_{n∈ω} be an infinite sequence compatible with τ^{Σ}.

\underline{Claim}: ā is an R-chain.

\underline{Proof of the claim}: We prove by induction over n that (a_{k})_{k≤n} is an R-chain. For n = 0 this is obvious. So assume that this is true for n. If n + 1 ∉ ν(Σ) then by definition of T^{(Σ)} and τ^{Σ} we have a_{n+1} = a_{n}. Otherwise n + 1 = ν(t) for some t ∈ Σ, and we distinguish the two cases:

– If n = 2p is even then a_{n+1} = a_{2p+1} = τ(seq [(a_{k})]_{k≤2p ∧ k∈ν(Σ)}). Hence if m = max{k ≤ 2p ∧ k ∈ ν(Σ)} then by definition of T we have a_{n} = a_{m} R a_{n+1}.

– If n = 2p + 1 is odd then a_{n+1} is chosen by Player II and by condition b) of Definition 7.2 we necessarily have n = ν(s) where s is the predecessor of t in T, hence by definition of T^{(Σ)} we have a_{n} R a_{n+1}.

This finishes the proof of the claim.⋄

It follows from the claim that for all p, seq [(a_{k})]_{k≤2p ∧ k∈ν(Σ)} is an R-chain which shows that the definition of τ^{Σ} is consistent. It also follows from the claim that for all t ∈ Σ, seq [(a_{ν(s)})]_{s⊂t} is an R-chain hence τ^{Σ} is actually a strategy for Player II in the game tree T^{(Σ)}. Finally, since ε is monotone, it also follows from the claim that for all p, (ε(a_{k})_{k≤2p}) is a ⊂-chain too. Hence τ^{Σ} is a strategy for Player II in the game tree T^{(Σ)} ∩ T_{ε}.

Since (a_{n})_{n∈ω} is an infinite run compatible with τ^{Σ} then seq [(a_{n})_{n∈ν(Σ)}] is an infinite run compatible with τ. Hence if τ is winning in Γ_{A}(T, ε) then ⋃_{n∈ν(Σ)} ε(a_{n}) = ⋃_{n∈ω} ε(a_{n}) ∈ A which proves that τ^{Σ} is winning in Γ_{A}(T^{(Σ)}, ε).

□

We also have the following converse result.

Proposition 7.5. Let (T, ε) be an ordered Ω-valued tree and A ⊂ 2^{Ω}. If Player II wins the game Γ_{A}(T^{(Σ)}, ε) for some ill-founded e.s.l. tree Σ, then Player II wins the game Γ_{A}(T, ε).

Proof. Let ν be the s.l. enumeration of Σ and R be the partial ordering generating T. Fix an infinite branch s̄ of Σ and let (m_{k})_{k∈ω} ∈ ω^{ω} be such that s̄_{|k} = ν(m_{k}) for all k, so in particular m_{0} = 0. Given any strategy τ^{Σ} for Player II in the game Γ_{A}(T^{(Σ)}, ε) we define:

τ((a_{k})_{k≤2p}) = τ^{Σ}((ã_{k})_{k≤m_{2p}}) with ã_{n} = \{ \begin{matrix}a_{k} & if n = m_{k} for some k \\ a_{n−1} & if not \end{matrix}

Then in the lines of the proof of Proposition 7.4 one can check that τ is a well defined strategy for Player II in T, and that τ is winning in Γ_{A}(T, ε) whenever τ^{Σ} is winning in Γ_{A}(T^{(Σ)}, ε). □

Quite clearly when Σ is well-founded the simple arguments above collapse completely and the following result is then totally non trivial.

Theorem 7.6. Let (T, ε) be an ordered Ω-valued tree and A ⊂ 2^{Ω} be Borel. If Player II wins the game Γ_{A}(T^{(Σ)}, ε) for any well-founded e.s.l. tree Σ then Player II wins the game Γ_{A}(T, ε).

We shall actually prove a stronger level by level version of this result. The proof will make use of the following representation of Π_{n}^{0} sets which is essentially a reformulation of the standard inductive definition of multiplicative Baire classes. In all the rest of this section n denotes a positive integer.

Lemma 7.7. A set A ⊂ 2^{ω} is Π_{n}^{0} if and only if there exists a family (A_{u})_{u∈ω^{n}} of Δ_{1}^{0} subsets of 2^{ω} satisfying for all α ∈ 2^{ω}:

1) if n = 2p then α ∈ A ⟺ ∃φ ∈ Hom(ω^{≤p}), ∀s ∈ ω^{p}, α ∈ A_{s⋆φ(s)} α ∉ A ⟺ ∃i ∈ ω, ∃ψ ∈ Hom(ω^{<p}), ∀t ∈ ω^{p−1}, ∀j ∈ ω,

α ∉ A_{⟨i⟩ (t⋆ψ(t))⟨j⟩}

2) if n = 2p + 1 then α ∈ A ⟺ ∃φ ∈ Hom(ω^{≤p}), ∀s ∈ ω^{p}, ∀j ∈ ω, α ∈ A_{(s⋆φ(s)) ⟨j⟩} α ∉ A ⟺ ∃i ∈ ω, ∃ψ ∈ Hom(ω^{≤p}), ∀t ∈ ω^{p}, α ∉ A_{⟨i⟩(t⋆ψ(t))}

We recall that for any tree S, Hom(S) denotes the set of all tree homomorphisms on S (see Section 2.3). For other undefined notation, in particular for the intertwining operation ⋆, we refer the reader to Section 2.1. Observe that in the four formulas of the form “α ∈ A_{u}” , “α ∉ A_{u}” which occur in the equivalences above the sequence u is indeed of length n.

Theorem 7.8. Consider the s.l. tree Σ = ω^{≤[\frac{n}{2}]} ⋆ \{0\}^{≤n−[\frac{n}{2}]−1} and let (T, ε) be an ordered Ω-valued tree. For any Π_{n}^{0} set A ⊂ 2^{Ω} if Player II wins the game Γ_{A}(T^{(Σ)}, ε) for some s.l. enumeration of Σ then Player II wins the game Γ_{A}(T, ε).

Proof. Set p = [\frac{n}{2}] and q = n − 1 − p. So Σ = ω^{≤p} ⋆ \{0\}^{≤q} with p + q = n − 1 and p − 1 ≤ q ≤ p; moreover since n ≥ 2 then p ≥ 1 and q ≥ 0. Let R be the partial ordering with domain E which generates the ordered Ω-valued tree T. Without loss of generality we may and shall assume that Ω = ω.

Fix an arbitrary s.l. enumeration ν of the s.l. tree Σ, a Π_{n}^{0} subset A of 2^{ω} together with a family (A_{u})_{u∈ω^{n}} of Δ_{1}^{0} subsets of 2^{ω} as in Lemma 7.7, and set: Γ = Γ_{A}(T, ε) and Γ^{Σ} = Γ(T^{(Σ,ν)}, ε). We now distinguish the two cases:

\underline{Case 1} : n = 2p so q = p − 1.

Consider the finite game Γ^{∗} of length n = 2p on ω × E in which Player I and Player II construct by alternative moves two sequences (i_{k}, b_{k})_{1≤k≤p} and (j_{k}, c_{k})_{1≤k≤p} as follows:

I : (i_{0}, b_{0})  (i_{1}, b_{1})  (i_{p−1}, b_{p−1})
↘  ↗  ↘  ↗  ↘
II :  (j_{0}, c_{0})  …  (j_{p−1}, c_{p−1})

with

(b_{k})_{0≤k≤p−1} ⋆ (c_{k})_{0≤k≤p−1} ∈ T

that is

b_{0} R c_{0} R b_{1} R ⋯ R b_{p−1} R c_{p−1} .

Then setting s = (i_{k})_{0≤k≤p−1} and t = (j_{k})_{0≤k≤p−1} Player II wins the run in Γ^{∗} iff:

N_{ε(c_{p})} ⊂ A_{s⋆t} .

For all k ≥ 0 let ¯0^{k} denote the sequence of length k with constant value 0, then for any u ∈ Σ:

– if |u| is even then u = s ⋆ ¯0^{|s|} with s ∈ ω^{<p} and then ν(u) is even too,

– if |u| is odd then u = s ⋆ ¯0^{|s|−1} with s ∈ ω^{≤p} and then ν(u) is odd too.

In the rest of the proof we shall consider various strategies in the games Γ, Γ^{Σ} and Γ^{∗}. We shall view a strategy for a player as a mapping assigning to the sequence of the opponent player’s previous moves the player’s next move, so (a_{2ℓ})_{0≤ℓ≤k} ↦ a_{2k+1} for Player I, and (a_{2ℓ−1})_{1≤ℓ≤k} ↦ a_{2k} for Player II. Also given any non empty finite sequence s ∈ ω^{<ω} we shall denote by s^{∗} its predecessor.

Lemma 7.9. If Player II wins the game Γ^{∗} then Player II wins the game Γ.

Proof. Fix a bijection μ : ω^{≤p} \ {0} → ω satisfying: if s ⊂ t then μ(s) ≤ μ(t)). Fix also a winning strategy τ^{∗} for Player II in Γ^{∗}. We shall explicitly define from μ and τ^{∗} a strategy τ for Player II in Γ. In fact during an infinite run (a_{m})_{m∈ω} compatible with τ Player II will construct simultaneously an additional infinite sequence (b_{m})_{m∈ω} satisfying for all m ∈ ω and all s ∈ ω^{≤p}:

(i) dom(ε(b_{m})) ⊃ [0, m]
(ii) a_{2m} R b_{m}
(iii) if μ(s) = m then τ^{∗}(s, (b_{μ(s_{|k})})_{k≤|s|}) = (j, a_{2m+1}).

Here by condition (iii) we implicitly mean that (s, (b_{μ(s_{|k})})_{k≤|s|}) is the sequence of Player I’s moves in some run in Γ^{∗} which is compatible with τ^{∗}, and a_{2m+1} ∈ E is the second coordinate of the response of τ^{∗} in this run (we recall that Γ^{∗} is a game on ω × E).

We proceed by induction over m. Suppose that a_{0}, …, a_{2m}, b_{0}, …, b_{m−1} are already defined. Let s ∈ ω^{≤p} be such that μ(s) = m since μ is monotone then μ(s^{∗}) < m and by condition (iii) τ^{∗}(s^{∗}, (b_{μ(s_{|k}})_{k≤|s^{∗}|}) = (j^{∗}, a_{2m−1}) for some j^{∗} ∈ ω. Now applying condition c) of Definition 3.3 we can find some b_{m} satisfying conditions (i) and (ii) above. But by the definition of the game Γ the sequence (a_{ℓ})_{ℓ≤2m} is an R-chain. In particular we have a_{2μ(s^{∗})+1} R a_{2m} R b_{m}, hence (s, (b_{μ(s_{|k})})_{k≤|s|}) is indeed the sequence of Player I’s moves in a run compatible with τ^{∗}. This achieves the inductive construction.

Consider now an infinite run (a_{m})_{m∈ω} in Γ compatible with τ. It follows from condition (i) that α = ⋃_{m∈ω} ε(a_{m}) is an element of 2^{ω} and we shall now prove that α ∈ A by applying Lemma 7.7. For this let φ be the tree homomorphism on ω^{≤p} defined inductively by φ(∅) = ∅ and φ(s) = φ(s^{∗})⟨j⟩ if s ≠ ∅ with μ(s) = m and τ^{∗}(s, (b_{μ(s_{|k})})_{k≤|s|}) = (j, a_{2m+1}). Since τ^{∗} is winning in Γ^{∗} then for all s ∈ ω^{≤p} we have α ∈ N_{ε(a_{2μ(s)+1})} ⊂ A_{s⋆φ(s)}.

This proves by Lemma 7.7 that α ∈ A, hence the strategy τ is winning. □

Lemma 7.10. If Player II wins the game Γ^{Σ} then Player II wins the game Γ^{∗}.

Proof. Suppose by contradiction that Player II does not win the game Γ^{∗} and fix a winning strategy σ^{∗} for Player I in this game (we recall that Γ^{∗} is a finite game hence determined). Fix also a winning strategy τ^{Σ} for Player II in Γ^{Σ}.

We shall construct an infinite run ā = (a_{m})_{m∈ω} in Γ^{Σ} compatible with τ^{S} and such that α = ⋃_{m∈ω} ε(a_{m}) ∉ A which is a contradiction. Roughly speaking, and as far as this makes sense, ā will be the result of the “composition” of the two strategies σ^{∗} and τ^{Σ}

More precisely let (i_{0}, a_{0}) be the first move of Player I in the game Γ^{∗} given by the strategy σ^{∗}; we define inductively (a_{m})_{m∈ω} satisfying:

(i) a_{2m+1} = τ^{Σ}((a_{2ℓ})_{ℓ≤m}),
(ii) if 2m = ν(t ⋆ 0^{|t|}) with t ≠ ∅ then σ^{∗}(t, (a_{ν(t_{|k}⋆0^{k−1})})_{k≤|t|}) = (i, a_{2m})

As above by condition (ii) we implicitly mean that (t, (a_{ν(t_{|k}⋆0^{k−1})}) is the sequence of Player II’s moves in some run in Γ^{∗} which is compatible with σ^{∗}. We leave to the reader to check by induction that this definition is coherent.

Since τ^{Σ} is winning then α = ⋃_{m∈ω} ε(a_{m}) ∈ A, and again we shall prove that α ∉ A by applying Lemma 7.7. For this we shall construct ψ ∈ Hom(ω^{<p}) such that for all t ∈ ω^{p−1} and all j ∈ ω, α ∉ A_{⟨i_{0}⟩ (t⋆ψ(t))⟨j⟩}, where i_{0} is the integer already fixed by the the first move given by σ^{∗}.

So let ψ be the homomorphism on ω^{<p} defined inductively by ψ(∅) = ∅ and ψ(t) = ψ(t^{∗})⟨i⟩ if t ≠ ∅ with ν(t ⋆ 0^{|t|}) = 2m and σ^{∗}(t, (a_{ν(t_{|k}⋆0^{k−1})})_{k≤|t|}) = (i, a_{2m}). Now fix t = (j_{k})_{0≤k≤p−2} ∈ ω^{p−1}, set ψ(t) = (i′_{k})_{0≤k≤p−2} and let for all 1 ≤ k ≤ p − 1, i_{k} = i′_{k−1} (we recall that i_{0} is already defined). It follows then from condition (ii) that the sequence (i_{k}, a_{ν(t_{|k}⋆0^{k})})_{0≤k≤p−1} ⋆ (j_{k}, a_{ν(t_{|k}⋆0^{k−1})})_{0≤k≤p−1} constitutes a run ρ in Γ^{∗} of length 2p − 1, which is compatible with σ^{∗}:

(i_{0}, a_{0})  (i_{1}, a_{ν(⟨j_{0},0⟩)})  . . . . . .
↘  ↗  ↘  ↗
(j_{0}, a_{ν(⟨j_{0}⟩)})  (j_{1}, a_{ν(⟨j_{0},0,j_{1}⟩)})
(i_{p−2}, a_{ν(t|_{p−2}⋆0^{p−2})})  (i_{p−1}, a_{ν(t⋆0^{p−1})})
↗ ↘ ↗
. . . . . .  (j_{p−2}, a_{ν(t⋆0^{p−2})})

On the other hand since for all k ∈ ω, t⟨k⟩ ⋆ 0^{p−1} ∈ S ∩ ω^{2p−1} it follows from condition (i) and the definition of the game Γ^{S} that

a_{0} R a_{ν(⟨j_{0}⟩)} R a_{ν(⟨j_{0},0⟩)} R … R a_{ν(t⋆0^{p−2})} R a_{ν(t⋆0^{p−1})} R a_{ν(t⟨k⟩⋆0^{p−1})}

Hence for all j ∈ ω, (j, a_{ν(t⟨k⟩⋆0^{p−1})}) is a legal move for Player II beyond the run ρ, and since the strategy σ^{∗} is winning for Player I then by definition of the game Γ^{∗} we have N_{ε(a_{ν(t⟨k⟩⋆0^{p−1})}))} ∩ A_{⟨i_{0}⟩(t⋆ψ(t))⟨j⟩}^{c} ≠ ∅ and since k is arbitrary and A_{⟨i_{0}⟩ (t⋆ψ(t))⟨j⟩} is open then α ∉ A_{⟨i_{0}⟩ (t⋆ψ(t))⟨j⟩}.

This proves by Lemma 7.7 that α ∉ A and finishes the proof of Lemma 7.10 and of Case 1 of Theorem 7.8. □

\underline{Case 2} : n = 2p + 1 so q = p.

The proof is very similar to Case 1. One introduces a game Γ_{∗} of length n on ω × E with the same rules. So a run in Γ_{∗} goes as follows:

I : (i_{0}, b_{0})  (i_{p−1}, b_{p−1})  (i_{p}, b_{p})
↘  · · · · · ·  ↘  ↗
II :  (j_{0}, c_{0})  (j_{p−1}, c_{p−1})

with

b_{0} R c_{0} R b_{1} R ⋯ R b_{p−1} R c_{p−1} R b_{p}

s = (i_{k})_{0≤k≤p−1} ∈ ω^{≤p} and t = (j_{k})_{0≤k<p} ∈ ω^{<p} satisfying now |t| = |s| + 1.

Notice however that in the present case the game Γ_{∗} being of odd length the last move in a maximal run is now made by Player I. This small advantage of Player I is then balanced by weakening slightly the win condition of Player II who wins a run in Γ_{∗} iff:

N_{ε(b_{p})} ∩ A_{s⋆t} ≠ ∅ .

Then one proves in the same lines as Case 1:

1) If Player II wins the game Γ_{∗} then Player II wins the game Γ.

2) If Player II wins the game Γ^{Σ} then Player II wins the game Γ_{∗}. □

Observing that the tree Σ in Theorem 7.8 is of rank n − 1 and gathering this result with Proposition 7.4 one then gets:

Corollary 7.11. Let (T, ε) be an ordered Ω-valued tree. For any Π_{n}^{0} subset A of 2^{Ω} Player II wins the game Γ_{A}(T, ε) if and only if Player II wins the game Γ_{A}(T^{(Σ)}, ε) for any e.s.l. tree Σ of rank < n.

Notice that since the Borel games Γ_{A}(T, ε) and Γ_{A}(T^{(Σ)}, ε) are determined (cf. [4]) one can replace everywhere in the statement of Corollary 7.11 “Player II” by “Player I”. It is however worth noting that one does not need to invoke Borel Determinacy for this. In fact by essentially the same arguments as in Lemma 7.9 one can show that if Player I wins the game Γ^{∗} then Player I wins the game Γ. This shows in particular that the determinacy of the Borel games of the form Γ_{A}(T, ε) follows from the determinacy of finite games which, by well known results of H. Friedman [2] , is far from being the case for arbitrary Borel games, even of finite rank.

8. Proof of condition (B)

Fix m ≥ 1 and q ≥ 0 such that m = 1 + q and set (T, ε) = (T_{q}, ε_{q}). We recall that ε is then an ω^{m}-valuation hence the game Γ_{A}(T, ε) is defined for any set A ⊂ 2^{ω^{m}} in particular for A = N_{m}. Our goal is to prove condition (B) of Theorem 4.1, that is:

Fact 8.1. For any Π_{2m}^{0} set A ⊃ N_{m} Player II wins the game Γ_{A}(T, ε).

Let Σ_{n} denote the s.l. tree ω^{≤[\frac{n}{2}]}⋆\{0\}^{≤n−[\frac{n}{2}]−1} endowed with an arbitrary s.l. tree enumeration; then by Theorem 7.8, Fact 8.1 is equivalent to:

Fact 8.2. For any Π_{2m}^{0} set A ⊃ N_{m} Player II wins the game Γ_{A}(T^{(Σ_{2m})}, ε).

In fact we shall prove the following stronger result:

Fact 8.3. Player II wins the game Γ_{N_{m}}(T^{(Σ_{2m})}, ε).

Let us mention here for completeness the following result that we shall not need and which can be proved by a straightforward induction:

Fact 8.4. Player I wins the game Γ_{N_{m}}(T, ε).

Of course there is no contradiction between the two latter results since N_{m} is precisely a Σ_{2m}^{0} set but not a Π_{2m}^{0} set.

Unfortunately we do not have a direct proof of Fact 8.3 which will actually be obtained as a consequence of a more technical result. Before we state this result let us recall that if (T, ε) is an ordered Ω-valued tree say T = T_{R} then for any tree Σ and any set A ⊂ 2^{Ω}, Γ_{A}(T^{(Σ)}, ε) is a game on the tree T_{ε} ∩ T^{(Σ)}, hence a sequence (a_{k})_{k∈ω} is an infinite run in this game iff:

(0) For all k ∉ ν(Σ), a_{k−1} = a_{k}.

(1) For all k > 0, ε(a_{k−1}) ⊂ ε(a_{k}).
(2) For all t ∈ Σ \ {∅}, a_{ν(t^{∗})} R a_{ν(t)}

Notice that since Σ is s.l., if ν(t) = 2ℓ then ν(t^{∗}) = 2ℓ − 1 so by condition (2) a_{2ℓ−1} R a_{2ℓ} and since ε is R-monotone then ε(a_{2ℓ−1}) ⊂ ε(a_{2ℓ}). Hence the conjunction of (1) and (2) above is equivalent to the conjunction of the following conditions (I) and (II):

(I) For all t ∈ Σ \ {∅}, if ν(t) = 2ℓ then a_{2ℓ−1} R a_{2ℓ}.

(II) \{ \begin{matrix}For all k, ε(a_{2k}) ⊂ ε(a_{2k+1}) \\ For all t ∈ Σ \ \{∅\}, if ν(t) = 2ℓ + 1 and ν(t^{∗}) = 2k then a_{2k} R a_{2ℓ+1} . \end{matrix}

which express the restrictions in the game on the moves of Player I and Player II respectively (in addition to the trivial condition (0)). In particular when describing a strategy for Player II in such a game we shall always implictly assume that condition (I) is already fulfilled.

We can now state the result from which Fact 8.3 will be derived:

Theorem 8.5. For all q ≥ 0, and any s.l.e. tree (Σ, ν) of rank ≤ 1+2q, Player II has a strategy τ in the game tree T_{ε_{q}} ∩ T_{q}^{(Σ,ν)} such that any maximal run ā compatible with τ is infinite, so ā = (a_{n})_{n∈ω}, and satisfies for all s, t ∈ Σ:

If |s| = |t| = 1 and ν(s) < ν(t) are both odd then a_{ν(s)} R_{q}^{1} a_{ν(t)} .

8.6. Proof of Fact 8.3 from Theorem 8.5:

Again set m = 1 + q, n = 2m and let Σ_{n} be as in 8.2 above. Since the rank of Σ_{n} is n − 1 = 2q + 1 one can apply Theorem 8.5 to Σ = Σ_{n} which provides a strategy τ for Player II in T_{ε_{q}} ∩ T_{q}^{(Σ_{n})}. Since T_{q} is ε_{q}-free then without loss of generality we can assume that for any maximal run (a_{k})_{k∈ω} compatible with τ, ⋃_{k∈ω} dom(ε(a_{k})) = ω^{m} that is α = ⋃_{k∈ω} ε(a_{k}) is an element of 2^{ω^{m}}.

We shall check that such a strategy is winning in the game Γ_{N_{m}}(T_{q}^{(Σ_{n})}, ε_{q}). Let (n_{k})_{k∈ω} be the increasing enumeration of the set

{ν(s) : s ∈ Σ_{n} and |s| = 1}

which is infinite by the definition of Σ_{n}. Since the strategy τ is given by Theorem 8.5 then for any infinite run (a_{k})_{k∈ω} in T_{ε_{q}}∩T_{q}^{(Σ_{n})} compatible with τ, the sequence (a_{n_{k}})_{k∈ω} forms an R_{q}^{1}-chain. It follows then from Proposition 4.9 that α = ⋃_{k∈ω} ε(a_{k}) is an element of N_{m}, which shows that τ is winning in Γ_{N_{m}}(T_{p,q}^{(Σ_{n})}, ε_{p,q}).

□

In fact the inductive proof of Theorem 8.5 will force us to construct strategies with even stronger properties which we will explicit later on. We introduce now a notion which will play a central role in the proof of Theorem 8.5.

8.7. A derivation on e.s.l. tree s:

If Σ is a tree on some set E then given any element s ∈ Σ one can consider Σ_{s} = {u : s u ∈ Σ} which is also a tree on E of smaller rank. This derivation on trees is a classical tool for defining inductive procedures on trees. We introduce now, in the frame of enumerated trees, a variation of the previous derivation.

Let (Σ, ν) be an enumerated tree. For any s ∈ Σ of even length we define:

Σ^{s} = Σ_{s} ∪ {⟨t⟩ : t ∈ Σ, ν(t) is odd and > ν(s)}
∪ {⟨t^{∗}, t⟩ : t ∈ Σ, ν(t) is even and > ν(s)}

which is a tree on E ∪ Σ. So any element of Σ^{s} \ Σ_{s} is a sequence on Σ of length at most 2. Notice that, unless t′ = t^{∗}, two elements ⟨t′⟩ and ⟨t^{∗}, t⟩ of length 1 and 2 in Σ^{s} \ Σ_{s} are incomparable, though t′ and t might be comparable as elements of Σ. In particular if Σ is s.l. then so is Σ^{s}.

Moreover Σ^{s} is endowed with a natural tree enumeration ν^{s} defined by

ν^{s}(u) = \{ \begin{matrix}ν(s u) − ν(s) & if u ∈ Σ_{s} \\ ν(t) − ν(s) & if u = ⟨t⟩ ∈ Σ^{s} \ Σ_{s} \end{matrix}

and if the enumeration ν is s.l. on Σ then so is ν^{s} on Σ^{s}. As usual when there is no ambiguity on ν we shall denote (Σ^{s}, ν^{s}) more simply by Σ^{s}.

Finally let us recall that for all s, rk (Σ_{s}) + |s| ≤ rk (Σ). In particular if s ≠ ∅ then rk (Σ_{s}) < rk (Σ); but this is no more the case with the new derivation, though we always have rk (Σ^{s}) ≤ rk (Σ). For example as one can easily check if Σ is an infinite tree of rank ≤ 2 then rk (Σ^{s}) = rk (Σ) for all s. But fortunately these pathologies disappear whenever rk (Σ) ≥ 3. More precisely:

Lemma 8.8. For any s ≠ ∅ either rk (Σ^{s}) ≤ 2 or rk (Σ^{s}) + 2 ≤ rk (Σ).

Proof. Observe that Σ_{s}^{∗} = {∅}∪(Σ^{s}\Σ_{s}) is a tree of rank ≤ 2. Since Σ^{s} = Σ_{s}∪Σ_{s}^{∗} then rk (Σ^{s}) = max(rk (Σ_{s}), rk (Σ_{s}^{∗}). Hence either rk (Σ^{s}) = rk (Σ_{s}^{∗}) ≤ 2 or rk (Σ^{s}) = rk (Σ_{s}), and in the latter case rk (Σ^{s}) + 2 ≤ rk (Σ_{s}) + |s| ≤ rk (Σ) since s is non empty and of even length. □

Definition 8.9. Let (Σ, ν) be an e.s.l. tree and R^{1} be a partial ordering on a set E. We shall say that a finite sequence ā = (a_{0}, …, a_{n−1}) ∈ E^{<ω} is ⟨Σ, R^{1}⟩-coherent if for all t′, t ∈ Σ with 2k − 1 = ν(t′) < ν(t) = 2ℓ + 1 < n:

(a) If ν(t^{∗}) = 2m then a_{2m} R^{1} a_{2ℓ+1} .

(b) If |t′| = |t| = 1 then a_{2k−1} R^{1} a_{2ℓ+1} .

(c) If |t′| = |t| = 1 and a_{2k−1} R^{1} a_{2k} then a_{2k} R^{1} a_{2ℓ+1} .

Notice that we did not impose any restriction on n = |ā|; however being ⟨Σ, R^{1}⟩-coherent depends only on the largest beginning of ā of even length that is (a_{0}, …, a_{2m−1}) where m = [\frac{n}{2}].

Definition 8.10. Let (T_{R}, ε) be an ordered Ω-valued tree and (Σ, ν) an e.s.l. tree. Given any partial ordering R^{1} ⊂ R, we shall say that a strategy τ for Player II in T_{ε} ∩T_{R}^{(Σ,ν)} in an R^{1}-strategy if any run compatible with τ is ⟨Σ, R^{1}⟩-coherent.

These definitions are of course motivated by Theorem 8.5. Indeed we shall prove this theorem by proving the existence of an R_{q}^{1}-strategy for Player II in T_{ε_{q}} ∩ T_{q}^{(Σ,ν)}. The proof of this latter result will actually be by induction and is behind the precise definition of ⟨Σ, R^{1}⟩-coherent sequences, namely the technical condition (c) of Definition 8.9 whose unique role is to ensure inside the inductive procedure the more crucial condition (b). Finally notice that, since R^{1} ⊂ R, condition (a) is a strengthening of one of the rules imposed on Player II in the game tree T_{ε} ∩ T_{R}^{(Σ,ν)}. In particular we have the following obvious fact.

Lemma 8.11. Let (R^{1}, R, ε, Σ) be as in Definition 8.10 and ā = (a_{0}, …, a_{2ℓ+1}) be a ⟨Σ, R^{1}⟩-coherent sequence of even length in the common domain of R^{1}, R, ε. If ε(a_{2ℓ+1}) ⊂ ε(a_{2ℓ}) and ā^{∗} = (a_{0}, …, a_{2ℓ}) ∈ T_{ε} ∩ T_{R}^{(Σ,ν)} then ā ∈ T_{ε} ∩ T_{R}^{(Σ,ν)}.

In all the sequel we shall view a strategy for Player II as a mapping of the form τ : (a_{0}, …, a_{2ℓ}) ↦ a_{2ℓ+1} where as usual the argument (a_{0}, …, a_{2ℓ}) is implicitly assumed to be a run in the game and compatible with τ. We start by a simple result.

Lemma 8.12. For all q ∈ ω and for any e.s.l. tree (Σ, ν) of rank ≤ 2, Player II has an R_{q}^{1}-strategy in T_{ε_{q}} ∩ T_{R_{q}}^{(Σ)} for which any maximal compatible run is infinite.

Proof. Set (R^{1}, R, ε) = (R_{q}^{1}, R_{q}, ε_{q}) and observe that if (Σ, ν) be an e.s.l. tree of rank ≤ 2 then for any t ∈ Σ if ν(t) is odd then necessarily t^{∗} = ∅, hence condition (a) of Definition 8.9 reduces to a_{0} R^{1} a_{2ℓ+1}.

We then define inductively a_{2ℓ+1} = τ(a_{0}, …, a_{2ℓ}) as follows:

– If either ℓ = 0 or a_{2ℓ−1} R^{1} a_{2ℓ}, let a_{2ℓ+1} = a_{2ℓ}.

– If not, observe first that by condition (I) a_{2ℓ−1} R a_{2ℓ}; then applying Proposition 4.8 take for a_{2ℓ+1} any element such that ε(a_{2ℓ}) = ε(a_{2ℓ+1}) and a_{2ℓ−1} R^{1} a_{2ℓ+1}.

By an easy induction one checks that a_{0} R^{1} a_{2k+1} R^{1} a_{2ℓ+1} for all k < ℓ, from which it follows clearly that τ is an R^{1}-strategy for Player II in T_{ε} ∩ T_{R}^{(Σ)}.

Finally since a_{2ℓ+1} is always defined any maximal run compatible with τ is clearly infinite. □

We can now state the stronger version of Theorem 8.5 that we will in fact prove.

Theorem 8.13. For any e.s.l. tree (Σ, ν) of rank ≤ 1 + 2q, Player II has an R_{q}^{1}-strategy in T_{ε_{q}} ∩ T_{R_{q}}^{(Σ,ν)} for which any maximal compatible run is infinite.

Proof. The proof is by induction over q. For q = 0 the result is a particular instance of Lemma 8.12.

So assume that the result holds for q. To prove that it holds for q + 1 we will have to start with a fixed e.s.l. tree Σ of rank ≤ 1 + 2(q + 1) and try to apply the induction hypothesis to some (actually infinitely many) e.s.l. tree s of the form Σ^{s} with s ≠ ∅. But observe that by Lemma 8.8 either rk (Σ^{s}) ≤ 2 in which case one can apply Lemma 8.12, or else rk (Σ^{s}) ≤ rk (Σ) − 2 ≤ 1 + 2(q + 1) − 2 = 2q + 1 and in this case one can apply the induction hypothesis.

For the rest of the proof we set:

R = R_{q}  R^{1} = R_{q}^{1}  ε = ε_{q}  E = dom(ε)  Ω = ω^{1+q}
R̃ =R_{q+1}  R̃^{1} = R_{q+1}^{1}  ε̃ = ε_{q+1}  Ẽ = dom(ε̃)  Ω̃ = ω × Ω

We recall that ε is an Ω-valuation on E and ε̃ is an Ω̃-valuation on Ẽ and Ẽ = Φ(E) = Fin(ω, E × 2) is viewed as a subset of Fin(ω, E) × Fin(ω, 2). Hence an element a of Ẽ is represented under the form a = ((a^{(i)})_{i∈J_{a}} , (J_{a}^{0}, J_{a}^{1})) where J_{a} = dom(a) is a finite subset of ω and (J_{a}^{0}, J_{a}^{1}) is a partition of J_{a}; in particular any pair of coordinates of the triple (J_{a}, J_{a}^{0}, J_{a}^{1}) determines the third one. We also recall that the relations R̃ and R̃^{1} are defined by:

a R̃ b ⟺ \{ \begin{matrix}J_{a}^{0} ⊂ J_{b}^{0} and ∀i ∈ J_{a}^{0}, a^{(i)} R b^{(i)} \\ J_{a}^{1} ⊂ J_{b}^{1} and ∀i ∈ J_{a}^{1}, a^{(i)} R^{1}b^{(i)} \end{matrix}

a R̃^{1} b ⟺ \{ \begin{matrix}J_{a}^{0} = J_{b}^{0} and ∀i ∈ J_{a}^{0}, a^{(i)} R b^{(i)} \\ J_{a}^{1} ⊂ J_{b}^{1} and ∀i ∈ J_{a}^{1}, a^{(i)} R^{1} b^{(i)} \end{matrix}

(See Section 4 for more details).

So let (Σ, ν) be an e.s.l. tree of a rank ≤ 1 + 2(q + 1). We have to construct an R̃^{1}-strategy τ in the game tree Tε̃ ∩ T(Σ) ; R̃. We shall not define this strategy immediately, but exhibit first partially some of its properties.

In all the sequel we consider a sequence ā = (a_{0}, a_{1}, …, a_{2ℓ}, a_{2ℓ+1}) ∈ Ẽ^{<ω} and set for all n ≤ 2ℓ + 1:

J_{n}^{0} = J_{a_{n}}^{0} ; J_{n}^{1} = J_{a_{n}}^{1} ; J_{n} = J_{a_{n}}

and for all m ≤ ℓ:

\{ \begin{matrix}K_{0}^{0} = J_{0}^{0} & ; & K_{0}^{1} = J_{0}^{1} \\ K_{m}^{0} = J_{2m}^{0} \ J_{2m−1} & ; & K_{m}^{1} = J_{2m}^{1} \ J_{2m−1} & if 0 < m ≤ ℓ \end{matrix}

We shall consider then the following condition:

(⋆) : \{ \begin{matrix}ā^{∗} = (a_{0}, a_{1}, …, a_{2ℓ}) ∈ Tε̃ ∩ T(Σ) ; R̃ \\ ∀m ≤ ℓ, J_{2m+1} = J_{2m} and J_{2m+1}^{0} = \{ \begin{matrix}J_{2k}^{0} & if 2m + 1 = ν(t) \\ & with ν(t^{∗}) = 2k \\ J_{2m}^{0} & if not \end{matrix} \end{matrix}

We emphasize that we do not suppose a priori that ā ∈ Tε̃ ∩ T(Σ) ; R̃. We recall the sets J_{2m+1}^{1} = J_{2m+1} \ J_{2m+1}^{0} are also determined by (⋆).

Lemma 8.14. If ā satisfies (⋆) then:

a) If 2ℓ + 1 ∉ ν(Σ) then J_{2ℓ+1}^{0} = J_{2ℓ}^{0} ; J_{2ℓ+1}^{1} = J_{2ℓ}^{1} and J_{2ℓ+1} = J_{2ℓ}.

b) J_{2ℓ+1} = J_{2ℓ} = ⋃{K_{m}^{0} ∪ K_{m}^{1}; m ≤ ℓ , 2m ∈ ν(Σ)} = ⋃{K_{m}^{0} ∪ K_{m}^{1}; m ≤ ℓ}.

Proof. a) By (⋆) we always have J_{2ℓ+1} = J_{2ℓ} and if moreover 2ℓ + 1 ∉ ν(Σ) then J_{2ℓ+1}^{0} = J_{2ℓ}^{0} , hence J_{2ℓ+1}^{1} = J_{2ℓ}^{1}.

b) Notice that for all m > 0 if m ≤ ℓ then 2m ≤ 2ℓ and by the definition of

Tε̃ ∩ T(Σ) ; R̃ we have a_{2m−1} R̃ a_{2m} hence J_{2m−1}^{0} ⊂ J_{2m}^{0} , J_{2m−1}^{1} ⊂ J_{2m}^{1} and a fortiori

J_{2m−1} ⊂ J_{2m}.

Then by (⋆) we have J_{2m−1} ⊂ J_{2m} = J_{2m+1}, hence J_{2m+1} \ J_{2m−1} = K_{m}^{0} ∪ K_{m}^{1} and by induction J_{2ℓ+1} = ⋃{K_{m}^{0} ∪ K_{m}^{1}; m ≤ ℓ}. Moreover by a) if 2m ∉ Σ then J_{2m+1} \ J_{2m−1} = ∅ hence J_{2ℓ+1} = ⋃{K_{m}^{0} ∪ K_{m}^{1}; m ≤ ℓ , 2m ∈ ν(Σ)}. □

Lemma 8.15. If ā satisfies (⋆) then:

a) If 2ℓ + 1 = ν(t) ∈ ν(Σ) then:

J_{2ℓ+1}^{0} = ⋃{K_{m}^{0}; m ≤ ℓ , 2m = ν(s) , s ⊂ t}

J_{2ℓ+1}^{1} = ⋃{K_{m}^{0}; m ≤ ℓ , 2m = ν(s) , s ⊄ t} ∪ ⋃_{m≤ℓ} K_{m}^{1}

b) If 2ℓ = ν(s) ∈ ν(Σ) then:

J_{2ℓ}^{0} = ⋃{K_{m}^{0}; m ≤ ℓ , 2m = ν(s′) , s′ ⊂ s}

J_{2ℓ}^{1} = ⋃{K_{m}^{0}; m ≤ ℓ , 2m = ν(s′) , s′ ⊄ s} ∪ ⋃_{m≤ℓ} K_{m}^{1}

Proof. a) If 2ℓ + 1 = ν(t) with ν(t^{∗}) = 2k then by (⋆) J_{2k−1}^{0} ⊂ J_{2k}^{0} = J_{2ℓ+1}^{0} and J_{2k−1}^{1} ⊂ J_{2k}^{1}. Hence J_{2ℓ+1}^{0} = J_{2k}^{0} = K_{k}^{0} ∪J_{2k−1}^{0} with 2k −1 = ν(t^{∗∗}); and repeating the argument inductively we get J_{2ℓ+1}^{0} = ⋃{K_{m}^{0}; m ≤ ℓ , 2m = ν(s) , s ⊂ t} hence J_{2ℓ+1}^{1} = J_{2ℓ+1} \ J_{2ℓ+1}^{0} = ⋃{K_{m}^{0}; m ≤ ℓ , 2m = ν(s) , s ⊄ t} ∪ ⋃_{m≤ℓ} K_{m}^{1}.

b) Observe that since a_{2ℓ−1} R̃ a_{2ℓ} then by definition J_{2ℓ}^{0} = K_{ℓ}^{0} ∪ J_{2ℓ−1}^{0} and J_{2ℓ}^{1} = K_{ℓ}^{1} ∪ J_{2ℓ−1}^{1} and conclude by applying a). □

Definition of τ: For all s ∈ Σ \ {∅} such that ν(s) is even consider the e.s.l. tree (Σ^{s}, ν^{s}) (see Section 8.7). We recall that by Lemma 8.8 either rk (Σ^{s}) ≤ 2 or rk (Σ^{s}) ≤ rk (Σ) − 2 ≤ 1 + 2q. Hence by applying Lemma 8.12 in the first case or the induction hypothesis in the second case, we can fix an R^{1}-strategy τ^{s} in the game tree T_{ε} ∩ T_{R}^{(Σ^{s})}. Then we define a_{2ℓ+1} = τ(a_{0}, a_{1}, …, a_{2ℓ}) inductively by:

a_{2ℓ+1} = ((a_{2ℓ+1}^{(i)})_{i∈J_{2ℓ+1}}, (J_{2ℓ+1}^{0}, J_{2ℓ+1}^{0}))

where J_{2ℓ+1}, J_{2ℓ+1}^{0}, J_{2ℓ+1}^{1} are defined by (⋆) and for all i ∈ J_{2ℓ+1}:

a_{2ℓ+1}^{(i)} = \{ \begin{matrix}τ^{s}(a_{2m}^{(i)}, a_{2m+1}^{(i)}, …, a_{2ℓ}^{(i)}) & if i ∈ K_{m}^{0} with 2m = ν(s) > 0 \\ a_{2ℓ}^{(i)} & if not \end{matrix}

We have to check that in the first alternative a_{2ℓ+1}^{(i)} is well defined. So fix i ∈ K_{m}^{0} such that 2m = ν(s) > 0 for some s ∈ Σ; we have to prove that (a_{2m}^{(i)}, a_{2m+1}^{(i)}, …, a_{2ℓ}^{(i)}) ∈ T_{ε} ∩ T_{R}^{(Σ^{s})}, which we do by induction on ℓ. For ℓ = 0 this is obvious. So suppose that (a_{2m}^{(i)}, a_{2m+1}^{(i)}, …, a_{2ℓ−2}^{(i)})) ∈ T_{ε} ∩ T_{R}^{(Σ^{s})} and is compatible with τ^{s}. Since a_{2ℓ−1} R̃ a_{2ℓ} then for all j ∈ J_{2ℓ−1} we have either a_{2ℓ−1}^{(j)} R a_{2ℓ}^{(j)} or a_{2ℓ−1}^{(j)} R^{1} a_{2ℓ}^{(j)} depending whether j is in J_{2ℓ−1}^{0} or in J_{2ℓ−1}^{1}; but since R^{1} ⊂ R then in both cases we have a_{2ℓ−1}^{(j)} R a_{2ℓ}^{(j)}. In particular since i ∈ K_{m}^{0} ⊂ J_{2ℓ−1} then a_{2ℓ−1}^{(i)} R a_{2ℓ}^{(i)} which shows that a_{2ℓ}^{(i)} is a legal move for Player I in T_{ε} ∩ T_{R}^{(Σ^{s})} hence (a_{2m}^{(i)}, a_{2m+1}^{(i)}, …, a_{2ℓ}^{(i)}) is indeed a run in T_{ε} ∩ T_{R}^{(Σ^{s})} and a_{2ℓ+1}^{(i)} is well defined.

Lemma 8.16. If ā is compatible with τ then:

a) For all i ∈ K_{0}^{0}, (a_{0}^{(i)}, a_{1}^{(i)}, …, a_{2ℓ+1}^{(i)}) is an R-chain.

b) For all i ∈ K_{m}^{1}, (a_{2m}^{(i)}, a_{2m+1}^{(i)}, …, a_{2ℓ+1}^{(i)}) is an R^{1}-chain.

Proof. a) If i ∈ K_{0}^{0} then by Lemma 8.15, since 0 = ν(∅), i ∈ J_{2n−1}^{0}, and since a_{2n−1} R̃ a_{2n} then a_{2n−1}^{(i)} R a_{2n}^{(i)}; and by the definition of τ we have a_{2n}^{(i)} = a_{2n+1}^{(i)}.

b) Similarly if i ∈ K_{m}^{1} then by Lemma 8.15 for all n > m, i ∈ J_{2n−1}^{1} hence a_{2n−1}^{(i)} R^{1} a_{2n}^{(i)} and again by the definition of τ we have a_{2n}^{(i)} = a_{2n+1}^{(i)}. □

If ā = (a_{0}, a_{1}, . . . . . . , a_{2ℓ+1}) and i ∈ K_{m}^{0} (notice that m is entirely determined by i) we define

ā^{(i)} = (a_{2m}^{(i)}, a_{2m+1}^{(i)} . . . . . . , a_{2ℓ+1}^{(i)}) = (b_{0}, b_{1}, . . . . . . , b_{2ℓ+1−2m})

We now come to the main lemma.

Lemma 8.17. If ā is compatible with τ, ā^{∗} is ⟨Σ, R̃^{1}⟩-coherent, and ā^{(i)} is ⟨Σ^{s}, R^{1}⟩-coherent for all possible i and s, then ā is ⟨Σ, R̃^{1}⟩-coherent.

Proof. The proof is rather long and we will split it into three parts corresponding to the three conditions (a), (b), (c) of Definition 8.9 that we will prove in the following order: (b), (c), (a).

Proof of condition (b): Let k ≤ ℓ be such that ν(t′) = 2k − 1 < 2ℓ + 1 = ν(t), with |s| = |t| = 1, we have to prove that a_{2k−1} R̃^{1} a_{2ℓ+1} .

Recall that by Lemma 8.15, J_{2k−1} ⊂ J_{2ℓ+1} and by (⋆) J_{2k−1}^{0} = J_{2ℓ+1}^{0} = J_{0}^{0}, hence J_{2k−1}^{1} ⊂ J_{2ℓ+1}^{1}; so what we only need to prove is that a_{2k−1} R̃ a_{2ℓ+1} , that is for i ∈ J_{2k−1}:

\{ \begin{matrix}1) If i ∈ J_{2k−1}^{0} then a_{2k−1}^{(i)} R a_{2ℓ+1}^{(i)} \\ 2) If i ∈ J_{2k−1}^{1} then a_{2k−1}^{(i)} R^{1} a_{2ℓ+1}^{(i)} \end{matrix}

So let i ∈ J_{2k−1}:

FRÉCHET ITERATED FILTERS 29

1) If i ∈ J_{2k−1}^{0} = J_{0}^{0} = K_{0}^{0} then by Lemma 8.16, a_{2k−1}^{(i)} R a_{2ℓ+1}^{(i)}.

2) If i ∈ J_{2k−1}^{1} then by Lemma 8.15:

– either i ∈ K_{m}^{1} for some m ≤ k and then by Lemma 8.16, a_{2k−1}^{(i)} R^{1} a_{2ℓ+1}^{(i)}.

– or else i ∈ K_{m}^{0} for some 0 < m ≤ k such that 2m = ν(s) < ν(t′) < ν(t) for some s ∈ Σ, and ā^{(i)} is compatible with τ^{s} hence is (Σ^{s}, R^{1})-coherent. Since ν(s) = 2m > 0 and |t′| = |t| = 1 then s is necessarily incomparable with t′ and t, hence ⟨t′⟩, ⟨t⟩ ∈ Σ^{s}; and since t′ ≠ t then ⟨t′⟩, ⟨t⟩ are incomparable elements of Σ^{s} of length 1. Moreover 2k − 1 − 2m = ν^{s}(⟨t′⟩) < ν^{s}(⟨t⟩) = 2ℓ + 1 − 2m hence by condition (b), applied to the (Σ^{s}, R^{1})-coherent sequence ā^{(i)}, we have a_{2k−1}^{(i)} = b_{ν^{s}(⟨t′⟩)} R^{1} b_{ν^{s}(⟨t⟩)} = a_{2ℓ+1}^{(i)}.

Proof of condition (c): Let k ≤ ℓ be such that ν(t′) = 2k − 1 < 2ℓ + 1 = ν(t), with |t′| = |t| = 1, and suppose in addition that a_{2k−1} R̃^{1} a_{2k}. We have to prove that a_{2k} R̃^{1} a_{2ℓ+1} . Since a_{0} R̃^{1} a_{2k} then J_{2k}^{0} = J_{0}^{0} = J_{2ℓ+1}^{0}, so as above all we need to prove is that a_{2k} R̃ a_{2ℓ+1} .

Notice also that since J_{2k}^{0} = J_{0}^{0} = J_{2k−1}^{0} then K_{k}^{0} = J_{2k}^{0} \ J_{2k−1} = ∅. Hence by Lemma 8.15, J_{2k}^{1} = ⋃_{0<m<k} K_{m}^{0} ∪ ⋃_{0≤m≤k} K_{m}^{1}. So let i ∈ J_{2k}:

1) If i ∈ J_{2k}^{0} = K_{0}^{0} then by Lemma 8.16, a_{2k}^{(i)} R a_{2k+1}^{(i)}.

2) If i ∈ J_{2k}^{1} then:

– either i ∈ K_{m}^{1} for some m ≤ k and then by Lemma 8.16, a_{2k}^{(i)} R^{1} a_{2k+1}^{(i)}.

– or else i ∈ K_{m}^{0} for some 0 < m < k such that 2m = ν(s) < ν(t′) < ν(t) and ā^{(i)} is compatible with τ^{s} hence is (Σ^{s}, R^{1})-coherent. Since J_{2k−1}^{0} = K_{0}^{0} then K_{m}^{0} ⊂ J_{2k−1}^{1} and since a_{2k−1} R̃^{1} a_{2k} then a_{2k−1}^{(i)} R^{1} a_{2k}^{(i)}. But as we already showed ⟨t′⟩, ⟨t⟩ are incomparable elements of length 1 in Σ^{s}. Hence by condition (c) applied to ā^{(i)} we have a_{2k}^{(i)} R^{1} a_{2ℓ+1}^{(i)}.

Proof of condition (a): Suppose that ν(t) = 2ℓ + 1 and ν(t^{∗}) = 2k; we have to prove that a_{2k} R̃^{1} a_{2ℓ+1} . Again by (⋆), J_{2k}^{0} = J_{2ℓ+1}^{0}, and we only need to prove that a_{2k} R̃ a_{2ℓ+1} . So let i ∈ J_{2k}:

1) If i ∈ J_{2k}^{0} then:

– either i ∈ K_{0}^{0} and then by Lemma 8.16, a_{2k}^{(i)} R a_{2ℓ+1}^{(i)}.

– or else i ∈ K_{m}^{0} for some 0 < m ≤ k such that 2m = ν(s) < ν(t) for s ∈ Σ with s ⊂ t, and ā^{(i)} is compatible with τ^{s} hence is (Σ^{s}, R^{1})-coherent. Moreover if we set t = s u with u ∈ Σ^{s} then t^{∗} = s u^{∗} and ν^{s}(u) = 2ℓ + 1 − 2m and ν^{s}(u^{∗}) = 2k − 2m. Hence by condition (a) applied to ā^{(i)} we have a_{2k}^{(i)} R^{1} a_{2ℓ+1}^{(i)} and a fortiori a_{2k}^{(i)} R a_{2ℓ+1}^{(i)}.

2) If i ∈ J_{2k}^{1} then:

– either i ∈ K_{m}^{1} for some m ≤ k and then by Lemma 8.16, a_{2k}^{(i)} R^{1} a_{2k+1}^{(i)}.

– or else i ∈ K_{m}^{0} for some 0 < m ≤ k such that 2m = ν(s) < ν(t) for s ∈ Σ with s ⊄ t, hence m < k so K_{m}^{0} ⊂ J_{2k−1}^{1}, and ā^{(i)} is compatible with τ^{s} hence is (Σ^{s}, R^{1})-coherent. Let t^{∗∗} be the predecessor of t^{∗} then ν(t^{∗∗}) = 2k − 1 and s ⊄ t^{∗∗}. Then as above ⟨t⟩, ⟨t^{∗∗}⟩, ⟨t^{∗∗}, t^{∗}⟩ ∈ Σ^{s} with ν^{s}(⟨t^{∗∗}⟩) = 2k − 1 − 2m, ν^{s}(⟨t^{∗∗}, t^{∗}⟩) = 2k − 2m and ν^{s}(⟨t⟩) = 2ℓ + 1 − 2m. Since K_{m}^{0} ⊂ J_{2k−1}^{1} and a_{2k−1} R̃^{1} a_{2k} then a_{2k−1}^{(i)} R^{1} a_{2k}^{(i)}. Hence by condition (c) applied to ā^{(i)} we have a_{2k}^{(i)} R^{1} a_{2ℓ+1}^{(i)}.

This finishes the proof of Lemma 8.17. □

To finish the proof of Theorem 8.13 observe that if ā is compatible with τ then for all i ∈ J_{2ℓ+1}, ā^{(i)} ∈ T_{ε} ∩ T_{R}^{(Σ)} hence ε(a_{2ℓ}^{(i)}) ⊂ ε(a_{2ℓ+1}^{(i)}) and applying Definition 4.3 we get:

ε̃(a_{2ℓ}) = ⋃_{i∈J_{2ℓ}}{i} × ε(a_{2ℓ}^{(i)}) ⊂ ⋃_{i∈J_{2ℓ}}{i} × ε(a_{2ℓ+1}^{(i)}) = ε̃(a_{2ℓ+1}) .

It follows then from Lemma 8.11 that under the same hypothesis as in Lemma 8.17 one can conclude that ā ∈ Tε̃ ∩ T(Σ) ; R̃. Applying this observation inductively one gets that τ is a strategy for Player II in Tε̃ ∩ T(Σ) ; R̃, and Lemma 8.17 shows that

τ is an R̃^{1}-strategy. □

This ends up the proof of condition (B) of Theorem 4.1.

9. Optimality

In this section we prove that the number m + 1 in Theorem 1.1 is optimal.

Theorem 9.1. For all m ≥ 2 there exists a Δ_{2m}^{0} set H_{m} containing N_{m} with the property that the intersection of any family of m elements in H_{m} is non empty .

Proof. Let H_{1} be the set of infinite subsets of ω, so:

H_{1} = {M ⊂ ω : ∀p ∃q ≥ p q ∈ M} .

We then define inductively for m ≥ 1 :

H_{m+1} = {M ∈ P(ω^{m+1}) : ∀p ∃q ≥ p M(q) ∈ N_{m} and ∃p ∀q ≥ p M(q) ∈ H_{m}}

We recall that for any M ⊂ ω^{m+1} = ω × ω^{m} and any j ∈ ω we denote by M(j) the section M(j) = {k̄ ∈ ω^{m} : (j, k̄) ∈ M} .

Lemma 9.2. For all m ≥ 2 the set H_{m} is Δ_{2m}^{0}.

Proof. The proof is by induction on m. H_{1} is clearly a Π_{2}^{0} subset of P(ω).

Assume that the set H_{m} is Π_{2m}^{0}. Since for all j ∈ ω the mapping M ↦ M(j) is continuous from P(ω^{m+1}) to P(ω^{m}), then the set

{M ∈ P(ω^{m+1}) : ∃p ∀q ≥ p M(q) ∈ H_{m}}

is Σ_{2m+1}^{0}; and since the set N_{m} is Σ_{2m}^{0}, then the set

{M ∈ P(ω^{m+1}) : ∀p ∃q ≥ p M(q) ∈ N_{m}}

is Π_{2m+1}^{0}. It follows that H_{m+1} is difference of two Σ_{2m+1}^{0} sets, hence a Δ_{2m+2}^{0} (and in particular Π_{2m+2}^{0}) set. □

Lemma 9.3. For all m ≥ 1 the set H_{m} contains N_{m}.

Proof. Since every member of N_{1} is cofinite, hence infinite, we have N_{1} ⊂ H_{1}.

Assume N_{m} ⊂ H_{m}, and let M ∈ N_{m+1}. Then for all but finitely many j we have M(j) ∈ N_{m} ⊂ H_{m}, hence M ∈ H_{m+1}. □

Lemma 9.4. For all m ≥ 1 the intersection of m elements of H_{m} is compatible with N_{m}, hence non empty.

Proof. Again the proof is by induction on m. For m = 1 every element M of H_{1} is infinite: thus it meets every cofinite N ∈ N_{1}.

Assume that the intersection of any m elements of H_{m} is compatible with N_{m}. Let (M_{0}, M_{1}, …, M_{m}) ∈ H_{m+1} and N ∈ N_{m+1}: we have to prove that ⋂_{0≤k≤m} M_{k} ∩ N ≠ ∅. By definition of H_{m+1}, we know that there exists some p such that M_{k}(q) ∈ H_{m} for all q ≥ p and every k ≤ m. Then by the induction hypothesis we have

∀q ≥ p M^{∗}(q) = ⋂_{0≤k<m} M_{k}(q) ∈ N̂_{m}

where N̂_{m} denotes the set of all subsets of ω^{m} which are compatible with N_{m}. Moreover there is an infinite set D ⊂ ω such that M_{m}(q) is in N_{m} whenever q ∈ D, and since N ∈ N_{m+1}, there exists a p′ ≥ p such that for all q ≥ p′ the set N(q) is in N_{m}. Then for q ≥ p′ in D, M_{m}(q) ∩ N(q) is in N_{m}, hence intersects M^{∗}(q) in some k̄ ∈ ω^{m}. And this shows that (q, k̄) ∈ N ∩ ⋂_{0≤k≤m} M_{k}. □

This finishes the proof of Theorem 9.1. □

10. Extensions

We shall discuss in this section several possible extensions of Theorem 1.1. The first extension concerns the definability feature of this result. For this we need to deal with concepts from Effective Descriptive Set Theory and we shall assume the reader to be familiar with this theory, for example as exposed in [5]. We can then state the following:

Theorem 10.1. In any Π_{2m}^{0} subset of P(ω^{m}) containing N_{m} one can find m + 1 Δ_{1}^{1} elements with empty intersection.

For a formal proof of this result one has to repeat the whole arguments of the paper and check step by step that all constructions and definitions which occur in this proof are indeed Δ_{1}^{1}. This is obvious in almost all the proof since most of the definitions are given by explicit arithmetical formulas. There is only one exception to this, which is the proof of Lemma 7.9. Indeed this proof makes use of an arbitrary winning strategy τ^{∗} for Player II in the game Γ^{∗}. But one can observe that since the win condition for Player II in this game is Π_{1}^{1} and open (actually clopen) then by the effective version of Gale-Stewart’s theorem (see [5]) one can find a Δ_{1}^{1} such winning strategy.

The second natural direction for extending Theorem 1.1 is to look for a similar conclusion starting with an arbitrary Π_{n}^{0} set containing N_{m}. Notice that since N_{m−1} embeds obviously in N_{m} then without loss of generality one may suppose that m < n. On the other hand since N_{m} is itself a Σ_{2m}^{0} set and is closed under finite intersections then one has has to impose that n ≤ 2m.

Conjecture A_{0} : If 1 ≤ m < n ≤ 2m then in any Π_{n}^{0} set containing N_{m} one can find a family of n − m + 1 elements with empty intersection.

So Theorem 1.1 treats the case n = 2m. But we are also able to prove that this conjecture holds for n = 2m − 1 and n = 2m − 2 (with n > m). The proofs, which combine the method of proof of Theorem 1.1 with some additional non trivial work, are unfortunately quite tedious.

Before we go further in our discussion let us recall some basic facts from [1]. If F is an analytic filter with countable domain – say ω for simplicity – then by the Separation Theorem, any pointwise limit f = lim_{F} f_{n} along F of a sequence of continuous functions f_{n} is automatically Borel. But it is a non trivial fact, proved in [1], that the set of all such functions f on 2^{ω} is exactly the set of all Borel functions of class ξ for some uniquely determined ordinal ξ = rk(F), that we call the rank of the filter F.

We also point out that the construction of the filters N_{m} can be extended to define inductively for any countable ordinal ξ ≥ 1, a Borel filter N_{ξ} of rank ξ: for successor ordinals the construction is due to Katětov and is quite similar to the finite case, while for limit ordinals one takes a sort of inductive limit of previous filters (see [1] for more details).

We conjecture the following generalization of A_{0}:

Conjecture A : If λ is a limit ordinal and 0 ≤ m ≤ n ≤ 2m are finite integers then in any Π_{2+λ+n}^{0} set containing N_{1+λ+m} one can find a family of n − m + 2 elements with empty intersection.

(Notice that for λ = 0 the condition 0 ≤ m ≤ n ≤ 2m in A is equivalent to the A_{0}-condition 1 ≤ m + 1 < n + 2 ≤ 2m + 2.)

Now since all the filters N_{ξ} are Borel the following question arises naturally: What is the minimal Baire class containing a filter of a given rank ? By easy computations (see [1]) we have the following:

– If λ is a limit ordinal then N_{λ} is a Σ_{λ}^{0} set.

– If ξ = λ + n is a successor ordinal (with λ limit and n ≥ 1 finite) then N_{ξ} is in the Baire class Σ_{1+λ+2n−1}^{0}.

which gives a lower bound for the possible complexity of a Borel filter of rank ξ, and we conjecture that it is the best bound (in a strong sense). Observe that if λ is a limit ordinal then by [1] Theorem 8.4 there is no Π_{λ}^{0} filter of rank λ nor a Π_{λ+1}^{0} filter of rank λ + 1, hence in these cases the question above is already settled.

Conjecture B: If ξ = λ+n is a successor ordinal (with λ limit and n ≥ 1 finite) then there is no Π_{1+λ+2n−1}^{0} filter of rank ≥ ξ.

As we shall see now this latter conjecture is actually related to Conjecture A. Notice first that any analytic filter refining N_{ξ} is obviously of rank ≥ ξ, and it was conjectured in [1] that the converse is also true:

Conjecture C: Any analytic filter of rank ≥ ξ contains a copy of N_{ξ}.

and obviously if Conjecture C were true then Conjecture B would follow from Conjecture A.

To finish let us point out that Conjectures A, B, C are simple consequences of Baire Theorem in the case ξ = 1, and in [1] it is proved that they all three hold for ξ = 2 too.

References

1. G. Debs and J. Saint Raymond, Filter descriptive classes of Borel functions, Fund. Math. 204 (2009), 189–213

2. H. M. Friedman, Higher set theory and mathematical practice, Ann. Math. Logic 2 (1970/1971) no. 3, 325–357

3. M. Katětov, Product of filters, Comm. Math. Univ. Carolinæ 9 (1968), 173–184

4. D.A. Martin, A purely inductive proof of Borel determinacy, Recursion theory (Ithaca, N.Y., 1982), 303–308, Proc. Sympos. Pure Math., 42

5. Y.N. Moschovakis, Descriptive Set Theory, Norh Holland, (1980).

Analyse Fonctionnelle, Institut de Mathématique de Jussieu, Université Pierreet-Marie Curie, Boîte 186, 4 place Jussieu, F- 75252 Paris Cedex 05, FRANCE

  E-mail address: debs@math.jussieu.fr

Analyse Fonctionnelle, Institut de Mathématique de Jussieu, Université Pierreet-Marie Curie, Boîte 186, 4 place Jussieu, F- 75252 Paris Cedex 05, FRANCE

  E-mail address: raymond@math.jussieu.fr