Quasi-Bounded Trees and Analytic Inductions

by J. Saint Raymond

ABSTRACT : A tree T on ω is said to be cofinal if for every α ∈ ω^{ω} there is some branch β of T such that α ≤ β, quasi-bounded if not. We prove here that the set of quasi-bounded trees is a complete Σ_{1}^{1}-inductive set. In particular, it is neither analytic, nor co-analytic.

In a recent joint work with G. Debs, we were led to study the complexity of the set of cofinal trees as a subset of the compact set of all trees on ω, in fact to show that this set is not Π_{1}^{1}. The aim of this paper is to compute the exact complexity of this set, which appears to be beyond the σ-algebra generated by the analytic sets. We also prove similar results concerning the set of cofinal or quasi-bounded closed subsets of the Baire space with respect to the Effros Borel structure on the set F(ω^{ω}) of closed nonempty subsets of ω^{ω}.

Most of the definitions and results we recall here can be found in [4], which we refer to for all undefined notions and basic properties of classical descriptive classes.

Sequences and trees.

For any set E we denote by Seq(E) the set of finite sequences of elements of E. If s = ⟨e_{0}, e_{1}, … e_{k−1}⟩ ∈ Seq(E) we denote by |s| its \underline{length} k. As usual, for any two s = ⟨e_{0}, e_{1}, … e_{k−1}⟩ and t = ⟨a_{0}, a_{1}, … a_{ℓ−1}⟩ in Seq(E) we say that t \underline{extends} s or that s is a \underline{beginning} of t, and write s ≺ t if |s| < |t| and e_{i} = a_{i} for i < |s|. And we write s ⪯ t iff s ≺ t or s = t. When s ∈ Seq(E) and k ≤ |s|, we denote by s_{|k} the sequence s′ of length k such that s′ ⪯ s. Also we denote by s^{⌢}t the \underline{concatenation} of s and t, that is the sequence ⟨e_{0}, e_{1}, … e_{k−1}, a_{0}, a_{1}, …, a_{ℓ−1}⟩ whose length is |s| + |t|.

For s and t in Seq(ω) we write s ≤ t if s and t have the same length and moreover s(i) ≤ t(i) for every i < |s|.

JEAN SAINT RAYMOND

We extend these notations for infinite sequences : for α = (a_{n}) ∈ E^{ω} we denote α_{|k} the sequence t = ⟨a_{0}, a_{1}, … a_{k−1}⟩, and write t ≺ α. For s ∈ Seq(E) of length k and α ∈ E^{ω} the concatenation s^{⌢}α shall denote the infinite sequence β such that s ≺ β and β(k + i) = α(i) for all i ∈ ω. It will also be convenient for s ∈ Seq(ω), α ∈ ω^{ω} and β ∈ ω^{ω} to write α ≤ β iff α(i) ≤ β(i) for all i and s ≤ α iff s ≤ α_{|k} where k = |s|.

2000 Mathematics Subject Classification : 03E15, 54H05

For any countable set I we identify the set P(I) of subsets of I to the compact space 2^{I} = {0, 1}^{I} by associating to each subset J of I its characteristic function χ_{J} : I → {0, 1}. In particular, if a and b are two members of 2^{ω}, we will write a ≤ b as well as a ⊂ b.

By a \underline{tree} T on E we mean a nonempty subset of Seq(E) which is left hereditary with respect to ⪯ , that is : (s ⪯ t and t ∈ T ) ⟹ s ∈ T. So the empty sequence ∅ belongs to any tree. An \underline{infinite branch} (or a \underline{branch} for short) of T is an infinite sequence α ∈ E^{ω} such that α_{|k} ∈ T for all k (or equivalently for infinitely many k’s). And we denote by ⌈T ⌉ the set of branches of T, which is a closed subset of E^{ω} equipped with the product topology when E itself has the discrete topology. Conversely for any closed subset F of E^{ω} there are trees T such that ⌈T ⌉ = F.

A tree T is said to be \underline{well-founded} iff it has no infinite branch, \underline{ill-founded} iff it is not well-founded.

A tree T on ω is said to be \underline{monotone} iff whenever s ≤ t and s ∈ T then t ∈ T. It is clear that if T is monotone and α is any branch of T then β ∈ ⌈T ⌉ whenever β ∈ ω^{ω} and α ≤ β.

We denote by T the set of all trees on ω and by T^{+} the set of all monotone trees on ω, which are both closed subsets of P(Seq(ω)), hence compact metrizable spaces. It is a well-known and fundamental fact that the set WF of well-founded trees on ω is a complete Π_{1}^{1}-subset of T .

If E and F are two sets, a finite sequence s of length n of elements of E × F can be canonically identified to a pair (t, u) with t ∈ Seq(E), u ∈ Seq(F) and |t| = |u| = n. Then a tree T on E × F can be viewed as a set of pairs (t, u) in Seq(E) × Seq(F) satisfying |t| = |u|. So we will say that t ∈ Seq(E) and u ∈ Seq(F) are \underline{T -compatible} if (t_{|k}, u_{|k}) ∈ T, where k = min(|t| , |u|). In the same way, for t ∈ Seq(E) and β ∈ F^{ω}, we say that t and β are T -compatible if (t, β_{|k}) ∈ T, where k = |t|.

It is easy to check that, for β ∈ F^{ω}, the set

T (β) := {t ∈ Seq(E) : t is T -compatible with β}

is a tree on E and that α ∈ ⌈T (β)⌉ if and only if (α, β) ∈ ⌈T ⌉.

Inductions.

Let I and P be sets, with I countable. A mapping Φ : P(I)×P → P(I) is called an \underline{induction} if it is monotone with respect the first variable for every x ∈ P, i.e. : a ⊂ b ⊂ I ⟹ Φ(a, x) ⊂ Φ(b, x).

QUASI-BOUNDED TREES

For such a mapping, one can define inductively on ξ ∈ ω_{1} subsets Φ^{ξ}(x) of I, for fixed x ∈ P by :

Φ^{0}(x) = ∅ ; Φ^{ξ+1}(x) := Φ(Φ^{ξ}(x), x) ; Φ^{λ}(x) = ⋃_{ξ<λ} Φ^{ξ}(x) for limit λ

It is easily shown that Φ^{ξ}(x) ⊂ Φ^{ξ+1}(x) for all ξ, then that Φ^{η}(x) ⊂ Φ^{ξ}(x) for η ≤ ξ. Since I is countable, there is for each x ∈ P a countable ordinal ζ such that Φ^{ζ+1}(x) = Φ^{ζ}(x), thus Φ^{ξ}(x) = Φ^{ζ}(x) for all ξ ≥ ζ. And we denote Φ^{∞}(x) := Φ^{ζ}(x) = ⋃_{ξ∈ω_{1}} Φ^{ξ}(x). Thus a := Φ^{∞}(x) is a fixed point for Φ(., x), i.e. Φ(a, x) = a. Conversely, if a is any fixed point for Φ(., x), it is immediate by induction on ξ that Φ^{ξ}(x) ⊂ a for all x, hence that Φ^{∞}(x) ⊂ a. This implies that Φ^{∞}(x) is the least fixed point for Φ(., x).

Then, if i^{∗} is a fixed element of I, the \underline{inductive set} Ind(Φ, i^{∗}) is defined as

Ind(Φ, i^{∗}) := {x ∈ P : i^{∗} ∈ Φ^{∞}(x)}

and it follows easily from what precedes that x ∉ Ind(Φ, i^{∗}) is equivalent to

∃a ∈ P(I) i^{∗} ∉ a and (∀i ∈ I i ∈ a or i ∉ Φ(a, x))  (∗)

If P is a Polish space and Γ is a class, the induction Φ is said to be a Γ-induction if for every i ∈ I the set E_{i} := {(a, x) : i ∈ Φ(a, x)} is a Γ-subset of P(I)×P, identified to the Polish space 2^{I} ×P. In particular, if Φ is a Δ_{1}^{1}-induction, or even a Π_{1}^{1}-induction, it follows immediately from (∗) that Ind(Φ, i^{∗}) is Π_{1}^{1}.

And a subset X of the Polish space P is said to be Σ_{1}^{1}-inductive if there is a countable set I, a Σ_{1}^{1}-induction Φ on P(I)×P and a i^{∗} ∈ I such that X = Ind(Φ, i^{∗}). We shall denote by Σ_{1}^{1}-IND the class of Σ_{1}^{1}-inductive sets.

The game quantifier.

Let P be a Polish space and A a Borel subset of ω^{ω} × P. For each fixed x ∈ P the set A_{x} := {α ∈ ω^{ω} : (α, x) ∈ A} can be viewed as the payoff of a Borel game on ω. So by Martin’s Borel Determinacy Theorem this game A_{x} is determined : if we denote by ⅁A the set

{x ∈ P : Player I has a winning strategy in A_{x}}

the complement of ⅁A in P is the set

{x ∈ P : Player II has a winning strategy in A_{x}}

whence we deduce that both ⅁A and P \ ⅁A are Σ_{2}^{1}.

If Γ is a class of Borel sets, we denote by ⅁Γ the class {⅁A : A ⊂ ω^{ω} × ω^{ω} , A ∈ Γ}. It is a well-known fact that ⅁Σ_{1}^{0} = Π_{1}^{1}.

For Γ = Σ_{2}^{0}, it follows from Wolfe’s proof of Σ_{2}^{0} determinacy (see for example [4], 6A.3 ) that if A ⊂ ω^{ω} × P is Σ_{2}^{0} one can define an analytic induction Φ : P(I) × P → P(I) (where I is the countable set {s ∈ Seq(ω) : |s| even }), such that Player I has a winning strategy in the game A_{x} if and only if the empty sequence ∅ belongs to Φ^{∞}(x). This shows that ⅁Σ_{2}^{0} ⊂ Σ_{1}^{1}-IND. Conversely it was shown by R. Solovay (see [4], 7C.10) that any Σ_{1}^{1}-inductive set is ⅁Σ_{2}^{0}, that is ⅁Σ_{2}^{0} = Σ_{1}^{1}-IND

Cofinal and quasi-bounded trees.

As we said in the abstract, a tree T on ω is said to be \underline{cofinal} if for every α ∈ ω^{ω} there is an infinite branch β of T such that α ≤ β. We will say that such a branch β is \underline{above α}.

If a tree T is not cofinal there is an α ∈ ω^{ω} such that no branch of T (if any) is above α. Such an α needs not be a bound for the branches of T, what would mean that “ for all β ∈ ⌈T ⌉, β ≤ α ”, and we shall say that α is a \underline{quasi-bound} for T, and that \underline{T is quasi-bounded}.

It is a well known fact that trees on ω and closed subsets of ω^{ω} are closely related. As above a subset A of ω^{ω} is said to be \underline{cofinal} (sometimes also \underline{dominating}) if for every α ∈ ω^{ω} there is some β ≥ α in A. We also will call quasi-bounded the subsets of ω^{ω} which are not cofinal. The structure of cofinal subsets of ω^{ω} was already studied by several people (see namely [5], [1] or [2]).

The aim of this paper is to prove that the set QB of quasi-bounded trees on ω is a ⅁Σ_{2}^{0}-complete subset of T . First we will prove that QB is ⅁Σ_{2}^{0}, hence Σ_{1}^{1}-inductive. Then we will show that every Σ_{1}^{1}-inductive subset of ω^{ω} is continuously reducible to QB. This will complete the proof that QB is Σ_{1}^{1}-IND-complete. In fact this will also prove that any Σ_{1}^{1}-inductive set is ⅁Σ_{2}^{0}, hence yield a new (but more complicated) proof of Solovay’s result.

We will also consider the set QBC of closed quasi-bounded subsets of the Baire space, equipped with the Effros Borel structure. This set was already studied by S. Solecki ([5]), in connection with Haar null sets of a non-locally compact Polish group. He showed this set is Δ_{2}^{1} but not Σ_{1}^{1}. We shall prove here that it is Σ_{1}^{1}-IND-complete.

There are only very few examples in the literature of true ⅁Σ_{2}^{0} sets. The most important one is given by Kechris in [3], where he shows that Σ_{1}^{1}-IND is the exact maximum complexity of σ-ideals of compact sets with Σ_{1}^{1} bases.

The main interest of our result is to yield a “natural” and combinatorially simple example of a ⅁Π_{2}^{0} set. It could be used to prove that a set X is not ⅁Π_{2}^{0} by reducing continuously QB to it, in the same way as one can prove that a set is not Σ_{1}^{1} by constructing a continuous reduction of WF to it.

Definition 1. For any tree T on ω, we denote by T^{∘} the tree defined by

s ∈ T^{∘} ⟺ (s = ∅) or (|s| ≤ s(0)) or (s = ⟨k⟩^{⌢}t with t_{|k} ∉ T )

Notice it is clear from the definition that if ⟨k⟩^{⌢}t belongs to T^{∘} and k ≤ ℓ then ⟨ℓ⟩^{⌢}t belongs to T^{∘} too.

Lemma 2. Let T be a monotone tree on ω. Then the tree T^{∘} is quasibounded if and only if T is ill-founded. Moreover, for any branch α of T, ⟨0⟩^{⌢}α is a quasi-bound for T^{∘}.

Proof : Assume first T is ill-founded and denote by α any branch of T. Then we claim that ⟨0⟩^{⌢}α is a quasi-bound for T^{∘}.

Indeed assume by contradiction that ⟨k⟩^{⌢}β is a branch of T^{∘} above ⟨0⟩^{⌢}α : then t := β_{|k} ∉ T. But since α ≤ β we have s := α_{|k} ≤ β_{|k} = t. So s ∈ T since α ∈ ⌈T ⌉, t ∉ T and s ≤ t, in contradiction with T ∈ T^{+}.

Assume now T is well-founded and ⟨m⟩^{⌢}α ∈ ω^{ω}. We claim that T^{∘} possesses a branch above ⟨m⟩^{⌢}α.

Indeed, α ∉ ⌈T ⌉ = ∅. Hence there is some integer k such that α_{|k} ∉ T. And replacing if necessary k by max(k, m), we can assume m ≤ k. Then ⟨k⟩^{⌢}α is a branch of T^{∘}, and ⟨m⟩^{⌢}α ≤ ⟨k⟩^{⌢}α. ■

Theorem 3. The set QB is ⅁Σ_{2}^{0}.

Proof : Define the mapping ψ : Seq(2) → Seq(ω) by counting the blocks of contiguous 0’s inside s : if ψ(s) = ⟨n_{0}, n_{1}, … n_{k−1}⟩ for some s ∈ Seq(2), the sequence s contains k terms equal to 1, with n_{0} zeros before the first 1, n_{1} zeros between the first and the second 1, …, n_{k−1} zeros between the last two 1’s.

So ψ is defined inductively by letting :

\{ \begin{matrix}ψ(∅) = ∅ \\ ψ(⟨1⟩) = ⟨0⟩ \\ ψ(s^{⌢}⟨0⟩) = ψ(s) \\ ψ(s^{⌢}⟨1, 1⟩) = ψ(s^{⌢}⟨1⟩)^{⌢}⟨0⟩ \\ ψ(s^{⌢}⟨1⟩) = u^{⌢}⟨p⟩ ⟹ ψ(s^{⌢}⟨0, 1⟩) = u^{⌢}⟨p + 1⟩ \end{matrix}

Then it is clear that |ψ(s)| ≤ |s| and that for any two sequences s and s′ such that s ≺ s′ we have ψ(s) ⪯ ψ(s′).

Let us denote by P_{∞} the set of those γ’s in 2^{ω} which have infinitely many coordinates equal to 1. For γ ∈ P_{∞} there is a unique β ∈ ω^{ω} which we denote by ψ̂(γ) such that s ≺ γ ⟹ ψ(s) ≺ β. It is easily checked and well known that 2^{ω} \ P_{∞} is countable and that ψ̂ is a homeomorphism from P_{∞} onto ω^{ω}.

For T a given tree we define the game G_{qb}(T) where Player I plays integers n_{0}, n_{1}, …, and Player II plays c_{0}, c_{1}, … in {0, 1} with the following two rules :

R_{1} - for every k, ψ(⟨c_{0}, c_{1}, … c_{k−1}⟩) ∈ T.

R_{2} - for every k, ⟨n_{0}, n_{1}, … n_{p−1}⟩ ≤ ψ(⟨c_{0}, c_{1}, … c_{k−1}⟩), where p is the length of ψ(⟨c_{0}, c_{1}, … c_{k−1}⟩) And the run where Player I plays (n_{k}) and Player II plays (c_{k}) is won by Player II iff (c_{k}) ∈ P_{∞}.

Clearly the set

A := {((n_{k}), (c_{k}), T) : Player II respects the rule and (c_{k}) ∉ P_{∞}}

is Σ_{2}^{0} in ω^{ω} ×2^{ω} ×T . Hence the set ⅁A is ⅁Σ_{2}^{0}. Theorem 3 will then follow from the next two lemmas.

Lemma 4. If Player II has a winning strategy in the game G_{qb}(T), then the tree T is continuously cofinal, i.e. there is a continuous fonction f : ω^{ω} → ⌈T ⌉ such that f(α) ≥ α for every α ∈ ω^{ω}. In particular, T is cofinal.

If τ is a winning strategy for Player II, it defines a continuous function g : ω^{ω} → 2^{ω} such that for every α in ω^{ω} and every s = ⟨n_{0}, n_{1}, … n_{k−1}⟩ ≺ α played by Player I the answer ⟨c_{0}, c_{1}, … c_{k−1}⟩ of Player II under τ satisfies ⟨c_{0}, c_{1}, … c_{k−1}⟩ ≺ g(α). It follows then from the rule R_{1} that ψ(⟨c_{0}, c_{1}, … c_{k−1}⟩) ∈ T. Moreover, since Player II wins, the run g(α) ∈ P_{∞}. Hence ψ̂(g(α)) ∈ ω^{ω} and ψ̂(g(α))_{|p} ∈ T for arbitrarily large p, whence we conclude that f(α) := ψ̂(g(α)) ∈ ⌈T ⌉. Since ψ in continuous on P_{∞}, f = ψ̂∘g itself is continuous. Finally, it follows from the rule R_{2} that f(α)_{|k} ≥ α_{|k} for arbitrarily large k, hence that f(α) ≥ α. ■

Lemma 5. If Player I has a winning strategy in G_{qb}(T), then T is quasibounded.

If σ is a winning strategy for Player I, it induces as above a continuous function h : 2^{ω} → ω^{ω}. Then the range K := h(2^{ω}) is a compact subset of ω^{ω}, and one can define for all n the integer α(n) = sup_{x∈K} x(n) . And we claim that this α is a quasi-bound for T.

Indeed, if β was a branch of T such that α ≤ β, then Player II could play the following infinite run γ : β(0) times 0, then 1, then β(1) times 0, then 1, . . .. This would respect the rule R_{1} since ψ(γ_{|k}) ≺ β for all k. And since γ ∈ P_{∞}, we would have β = ψ̂(γ). Moreover, since h(γ) ∈ K, we would have h(γ) ≤ α ≤ β = ψ̂(γ) ; this shows that the rule R_{2} also would be respected. Finally since γ ∈ P_{∞}, Player II would win the run against the strategy σ. And this contradiction completes the proof of the Lemma. ■

Thus the proof of Theorem 3 is complete. One can notice that a similar game was used in [2] in order to prove that any cofinal Σ_{1}^{1} subset of ω^{ω} is continuously cofinal.

Remark.

It follows from the previous proof that a quasi-bound for T can be computed continuously from a winning strategy for Player I in G_{qb}(T). Conversely a quasi-bound α for T yields a simple strategy σ for Player I : he plays α whatever Player II is answering. And this strategy is clearly winning : in any run compatible with σ a position (α_{|k}, ⟨c_{0}, c_{1}, … c_{k−1}⟩) is reached for which no extension of ψ(⟨c_{0}, c_{1}, … c_{k−1}⟩) can be found in T above α; and beyond this position Player II must always play 0.

We now intend to show that QB has complexity at least Σ_{1}^{1}-IND.

Theorem 6. If X is a Σ_{1}^{1}-IND subset of ω^{ω}, there exists a continuous mapping x ↦ S(x) from ω^{ω} to T such that S(x) ∈ QB if and only if x ∈ X.

Proof : Without loss of generality we assume that Φ : 2^{ω} × ω^{ω} → 2^{ω} is a Σ_{1}^{1}-induction on ω and that

x ∈ X ⟺ 0 ∈ Φ^{∞}(x)

Then for each n the set E_{n} := {(a, x) ∈ 2^{ω} × ω^{ω} : n ∈ Φ(a, x)} is Σ_{1}^{1} and there is some tree T_{n} on 2 × ω × ω such that

(a, x) ∈ E_{n} ⟺ ∃β ∈ ω^{ω} (a, β, x) ∈ ⌈T_{n}⌉

where we identify the subset ⌈T_{n}⌉ of (2 × ω × ω)^{ω} with a subset of 2^{ω} × ω^{ω} × ω^{ω}. Identifying Seq(2 × ω × ω) with the set

{(s, t, u) ∈ Seq(2) × Seq(ω) × Seq(ω) : |s| = |t| = |u|}

we define now trees T̂_{n} and U_{n} on 2 × ω × ω by

(s, t, u) ∈ T̂_{n} ⟺ ∃s′ ∃t′ s′ ≤ s , t′ ≤ t , (s′, t′, u) ∈ T_{n}

(s, t, u) ∈ U_{n} ⟺ \{ \begin{matrix}(s, t, u) = (∅, ∅, ∅) \\ or |s| = |t| = |u| ≤ t(0) \\ or else t = ⟨k⟩^{⌢}t^{∗} with (s_{|k}, t_{|k}^{∗}, u_{|k}) ∉ T̂_{n} \end{matrix}

Fix a bijection (n, p) ↦ n ∗ p from ω × ω onto ω which is separately increasing with respect to each variable and satisfies n ∗ 0 ≤ 0 ∗ n. Then we have necessarily 0 ∗ 0 = 0. For example we can put

n ∗ p = \frac{(n + p)(n + p + 1)}{2} + p

Then, for each s ∈ Seq(ω) and each n ∈ ω, we define the sequence θ_{n}(s) ∈ Seq(ω) by

θ_{n}(s) = ⟨s(n∗0), s(n∗1), … s(n∗(k −1))⟩ where n∗(k −1) < |s| ≤ n∗k

In particular we get θ_{n}(s) = ∅ if |s| ≤ n ∗ 0. Define also θ^{∗}(s) ∈ Seq(2) by

θ^{∗}(s) = ⟨c_{0}, c_{1}, … c_{p−1}⟩ where \{ \begin{matrix}(p − 1) ∗ 0 < |s| ≤ p ∗ 0 \\ and c_{i} = 1 ⟺ s(i ∗ 0) is odd \end{matrix}

Observe that for any s ∈ Seq(ω) and any n, if k = |θ_{n}(s)| and p = |θ^{∗}(s)|, we have

0 ∗ (k − 1) ≤ n ∗ (k − 1) < |s| ≤ p ∗ 0 ≤ 0 ∗ p

hence k − 1 < p, thus |θ_{n}(s)| ≤ |θ^{∗}(s)|. Moreover it is clear that if s ≺ s′ we have θ_{n}(s) ⪯ θ_{n}(s′) for all integer n, and θ^{∗}(s) ⪯ θ^{∗}(s′). We will extend θ_{n} and θ^{∗} to ω^{ω} by letting

θ̂_{n}(α)(k) = α(n ∗ k)
θ̂^{∗}(α)(i) = \{ \begin{matrix}1 & if s(i ∗ 0) est impair \\ 0 & if not \end{matrix}

We define now, for x ∈ ω^{ω}, a tree S(x) by

s ∈ S(x) ⟺ \{ \begin{matrix}s = ∅ or (s(0) = 0 and ∀n < |θ^{∗}(s)| \\ (θ^{∗}(s)(n) = 1 or (θ^{∗}(s)_{|k}, θ_{n}(s), x_{|k}) ∈ U_{n}, )) \end{matrix}

where k = |θ_{n}(s)|.

The theorem will follow from the next four lemmas.

Lemma 7. The mapping x ↦ S(x) is continuous from ω^{ω} to T .

Proof : For any s ∈ Seq(ω) denote k := |θ^{∗}(s)|. Then “ s ∈ S(x) ” depends only on x_{|k}. Hence {x ∈ ω^{ω} : s ∈ S(x)} is open and closed. This shows that the mapping x ↦ S(x) is continuous from ω^{ω} to T . ■

Lemma 8. For a ∈ 2^{ω} and x ∈ ω^{ω} one has

n ∈ Φ(a, x) ⟺ ∃β ∈ ω^{ω} (a, β, x) ∈ ⌈T̂_{n}⌉ ⟺ U_{n}(a, x) ∈ QB

Moreover, if β is any branch of T̂_{n}(a, x), ⟨0⟩^{⌢}β is a quasi-bound for U_{n}(a, x).

Proof : Notice that T_{n} ⊂ T̂_{n}. Thus if n ∈ Φ(a, x), we have (a, x) ∈ E_{n} hence there exists a β such that (a, β, x) ∈ ⌈T_{n}⌉ ⊂ ⌈T̂_{n}⌉.

Conversely, if (a, β, x) ∈ ⌈T̂_{n}⌉ then for every integer k, (a_{|k}, β_{|k}, x_{|k}) belongs to T̂_{n}. Hence there are s ∈ 2^{k} and t ∈ ω^{k} such that (s, t, x_{|k}) ∈ T_{n}, s ≤ a_{|k} and t ≤ β_{|k}. It follows that the set

V := {(s, t, u) ∈ T_{n} : |s| = |t| = |u| , s ≤ a , t ≤ β , u ≺ x}

is an infinite and finitely branching tree. By König’s Lemma the tree V is ill-founded. If (a′, β′, x′) is a branch of V, one has necessarily a′ ≤ a and x′ = x. Thus (a′, x) ∈ E_{n}, hence n ∈ Φ(a′, x) ⊂ Φ(a, x).

Notice that for any a ∈ 2^{ω} and any x ∈ ω^{ω}, U_{n}(a, x) = T̂_{n}(a, x)^{∘} and T̂_{n}(a, x) is monotone. Then it follows from Lemma 2 that U_{n}(a, x) = T̂_{n}(a, x)^{∘} is quasi-bounded if and only if T̂_{n}(a, x) is ill-founded, that is if and only if n ∈ Φ(a, x). ■

Lemma 9. If x ∉ X then S(x) is cofinal.

Proof : Assume x ∉ X and let a = Φ^{∞}(x). Then 0 ∉ a and for all n ∉ a we have n ∉ Φ(a, x). Let α ∈ ω^{ω} and define for all n : α_{n} = θ̂_{n}(α). We will produce a branch β of S(x) such that β ≥ α.

For n ∈ a we define β_{n} = α_{n}. And for n ∉ a, since U_{n}(a, x) is cofinal by Lemma 8 we can find β_{n} ∈ ⌈U_{n}(a, x)⌉ such that α_{n} ≤ β_{n}. Replacing if necessary β_{n}(0) by β_{n}(0) + 1, we can assume that β_{n}(0) is odd for n ∈ a and even for n ∉ a. Then defining β by

∀n ∀p β(n ∗ p) = β_{n}(p)

we get θ̂_{n}(β) = β_{n} ≥ α_{n} = θ̂_{n}(α), β(0) = β_{0}(0) is even and θ̂^{∗}(β) = a.

It follows easily that β ≥ α and that for each ℓ, β_{|ℓ} ∈ S(x), hence β ∈ ⌈S(x)⌉. ■

Lemma 10. If x ∈ X then S(x) is quasi-bounded.

Proof : Assume now that x ∈ X. Then 0 ∈ Φ^{∞}(x), and we can define for every n ∈ Φ^{∞}(x) the rank ρ_{n} := min{ξ : n ∈ Φ^{(ξ)}(x)} ∈ ω_{1} and then a_{n} := {p ∈ ω : ρ_{p} < ρ_{n}}. Thus, for n ∈ Φ^{∞}(x), we have n ∈ Φ(a_{n}, x). It follows that T̂_{n}(a_{n}, x) is ill-founded. Then we can choose a branch α_{n}^{∗} of T̂_{n}(a_{n}, x) and let α_{n} := ⟨0⟩^{⌢}α_{n}^{∗}.

For n ∉ Φ^{∞}(x) we choose α_{n} equal to the null sequence 0. And finally defining α by

∀n ∀p α(n ∗ p) = α_{n}(p)

we get θ̂_{n}(α) = α_{n} for all n.

We claim that α is a quasi-bound for S(x). Indeed, assuming by contradiction that β is a branch of S(x) above α, we should have β_{n} := θ̂_{n}(β) ≥ θ̂_{n}(α) = α_{n}. Then put a := θ̂^{∗}(β) ∈ 2^{ω}. Since β ∈ ⌈S(x)⌉, we should have β(0) even, hence 0 ∈ Φ^{∞}(x) \ a. It follows that {ρ_{n} : n ∈ Φ^{∞}(x) \ a} should be nonempty. Thus there would be an integer m ∈ Φ^{∞}(x) \ a such that ρ_{m} = min{ρ_{n} : n ∈ Φ^{∞}(x) \ a}. In particular m ∉ a hence β_{m} ∈ ⌈U_{m}(a, x)⌉

By minimality of ρ_{m} we would have a_{m} = {p : ρ_{p} < ρ_{m}} ⊂ a, hence m ∈ Φ(a, x). Since α_{m}^{∗} ∈ ⌈T̂_{m}(a_{m}, x)⌉, this would also imply that α_{m}^{∗} ∈ ⌈T̂_{m}(a, x)⌉, hence α_{m} would be a quasi-bound for U_{m}(a, x) by Lemma 8, in contradiction with α_{m} ≤ β_{m} and β_{m} ∈ ⌈U_{m}(a, x)⌉. ■

And this completes the proof of Theorem 6.

Quasi-bounded closed subsets of the Baire space

Now we are interested in closed subsets of ω^{ω} and will denote by F(ω^{ω}) the set of nonempty closed subsets of ω^{ω} which we equip with the Effros Borel structure. As for trees on ω, we shall say that a closed subset F of ω^{ω} is cofinal if for every α ∈ ω^{ω} there is some β ≥ α in F, and that F is quasi-bounded if it is not cofinal. We shall say that α is a quasi-bound for F iff F ∩ {β : β ≥ α} = ∅. We will denote by QBC the subset of F(ω^{ω}) constituted of quasi-bounded closed subsets of ω^{ω}.

And we shall show by the following theorem that QBC behaves with respect to Borel reducibility in the same way as QB with respect to continuous reducibility.

Theorem 11. QBC is Σ_{1}^{1}-IND-complete.

This follows immediately from next two lemmas.

Lemma 12. If P is a Polish space and F : P → F(ω^{ω}) a Borel mapping then F^{−1}(QBC) is Σ_{1}^{1}-inductive.

Proof : For each s ∈ Seq(ω) we denote by N_{s} the basic open set : {α ∈ ω^{ω} : s ≺ α}. And for x ∈ P define :

T (x) := {s ∈ Seq(ω) : N_{s} ∩ F (x) ≠ ∅}

which is clearly a tree on ω such that ⌈T (x)⌉ = F (x). By definition of the Effros Borel structure {H : N_{s} ∩ H ≠ ∅} is Borel in F(ω^{ω}), thus {x ∈ P : s ∈ T (x)} is Borel for all s. Hence the mapping f : x ↦ T (x) is Borel from P to T .

It is immediate from the definitions that f(x) ∈ QB ⟺ F (x) ∈ QBC. So F^{−1}(QBC) = f^{−1}(QB).

Since QB is Σ_{1}^{1}-inductive in T , there is an analytic induction Φ : P(ω) × T → P(ω) such that T ∈ QB ⟺ 0 ∈ Φ^{∞}(T). Then define for a ∈ P(ω) and x ∈ P :

Ψ(a, x) := Φ(a, f(x))

Then Ψ is an induction and clearly for each ξ : Ψ^{ξ}(x) = Φ^{ξ}(f(x)), hence Ψ^{∞}(x) = Φ^{∞}(f(x)) and

F (x) ∈ QBC ⟺ f(x) ∈ QB ⟺ 0 ∈ Φ^{∞}(f(x)) ⟺ 0 ∈ Ψ^{∞}(x) ⟺ x ∈ Ind(Ψ, 0)

Then n ∈ Ψ(a, x) ⟺ ∃T ∈ T (T = f(x)) and (n ∈ Φ(a, T)), whence we conclude that Ψ is Σ_{1}^{1} and finally that F^{−1}(QBC) is Σ_{1}^{1}-inductive. ■

Lemma 13. If X is a Σ_{1}^{1}-IND subset of ω^{ω} there exists a Borel reduction of X to QBC.

Proof : By theorem 6 there is a continuous function S from ω^{ω} to T such that S(x) ∈ QB ⟺ x ∈ X. Denote for n ∈ ω by z_{n} the null sequence of length n, and

S̃(x) := {s^{⌢}z_{n} : s ∈ S(x) , n ∈ ω}

Clearly if α ∈ ω^{ω} is any sequence such that α(n) > 0 for all n, we have for all β ∈ ω^{ω} :

β ≥ α and β ∈ ⌈S(x)⌉ ⟺ β ≥ α and β ∈ ⌈S̃(x)⌉

hence S(x) ∈ QB ⟺ S̃(x) ∈ QB. Since

s ∈ S̃(x) ⟺ (∃k, ℓ ≤ |s| s_{|k} ∈ S(x) and s = s_{|k}^{⌢}z_{ℓ})

one sees that S̃ is continuous and that X = S̃^{−1}(QB). Then define F (x) := ⌈S̃(x)⌉. It is immediate that F (x) is a quasi-bounded closed subset of ω^{ω} iff S̃(x) ∈ QB, i.e. iff x ∈ X. Finally it is enough to notice that for each s ∈ Seq(ω) and each x ∈ ω^{ω}

F (x) ∩ N_{s} ≠ ∅ ⟹ s ∈ S̃(x) ⟹ ∀n s^{⌢}z_{n} ∈ S̃(x) ⟹ s^{⌢}0 ∈ ⌈S̃(x)⌉ ⟹ F (x) ∩ N_{s} ≠ ∅

to see that {x : N_{s} ∩ F (x) ≠ ∅} is clopen, hence that F is Borel. ■

REFERENCES

[ 1 ] J. Brendle, G. Hjorth and O. Spinas, Regularity properties for dominating projective sets, Ann. Pure Appl. Logic 72 (1995), 291-307

[ 2 ] G. Debs and J. Saint Raymond, Cofinal Σ_{1}^{1} and Π_{1}^{1} subsets

of ω^{ω}. Fund. Math. 159 (1999), 161-193

[ 3 ] A. Kechris, The descriptive set theory of σ-ideals of compact sets. Logic Colloquium ’88 (Padova, 1988), 117-138, Stud. Logic Found. Math., 127, North Holland, Amsterdam, 1989

[ 4 ] Y.N.Moschovakis, Descriptive Set Theory (North Holland,

Amsterdam, 1980)

[ 5 ] S. Solecki, Haar null and non-dominating sets, Fund. Math.

170 (2001), 197-217

[ 6 ] O. Spinas, Dominating projective sets in the Baire space, Ann. Pure Appl. Logic 68 (1994), 327-342

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