COMPLETE PAIRS OF COANALYTIC SETS

JEAN SAINT RAYMOND

Abstract. Let X be a Polish space, C_{0} and C_{1} be disjoint coanalytic subsets of X. The pair (C_{0}, C_{1}) is said to be complete if for every pair (D_{0}, D_{1}) of disjoint coanalytic subsets of ω^{ω} there exists a continuous function f : ω^{ω} → X such that f^{−1}(C_{0}) = D_{0} and f^{−1}(C_{1}) = D_{1}. We give several explicit examples of complete pairs of coanalytic sets.

1. Introduction and notations

All spaces we consider in this note are metrizable and separable, and often zero–dimensional, hence embeddable in the Cantor set 2^{ω} or in the Baire space ω^{ω}. For unexplained notations we refer to [5].

We will denote by ℚ the dense countable subset of 2^{ω} defined by

ℚ := {α ∈ 2^{ω} : ∃n ∀p ≥ n α(p) = 0}

For any space X we denote by 𝒦 (X) the hyperspace of non-empty compact subsets of X equipped with the Vietoris topology. It is a well-known fact that 𝒦 (ℚ) is complete coanalytic. We will also denote by 𝒦_{ω}(X) the subspace of 𝒦 (X) constituted of the countable compact subsets of X, and by 𝒦 ^{∗}(ℚ) the subset

𝒦 ^{∗}(ℚ) = {K ∈ 𝒦 (2^{ω}) : K \ ℚ has a unique element}

of 𝒦 (2^{ω}) which is clearly disjoint from 𝒦 (ℚ) and contained in 𝒦_{ω}(2^{ω}).

By Seq we will denote the countable set ω^{<ω} of finite sequences of integers and by 𝒯 the set of trees on ω, which we identify to a closed subset of 2^{Seq}. We denote by WF the set of well-founded trees. We also denote by WF^{∗} the subset of 𝒯 constituted of the trees which have a unique branch. For any tree T ∈ 𝒯 we denote by ⌈T ⌉ the set of branches of T and identify it with a closed subset of ω^{ω}. We will always identify a finite sequence of elements of ω × ω with a pair (s, t) of finite sequences of integers having the same length. So any tree T on ω × ω is viewed as a subset of Seq × Seq and for every x ∈ ω^{ω} the set

T (x) := {s ∈ Seq : ∃t ≺ x |s| = |t| and (t, s) ∈ T }

is a tree on ω. Moreover it is clear on the definition that the mapping x ↦ T (x) is then continuous from ω^{ω} to 𝒯 .

Date: February 16, 2007.

2000 Mathematics Subject Classification. Primary 54H05; Secondary 03E15, 28A05 .

Key words and phrases. Coanalytic sets, bianalytic functions, functions with closed graph.

Recall that a function f : X → Y is said to be bianalytic (we write f ∈ Δ_{1}^{1}), if f^{−1}(V) is a (relative) coanalytic subset of X for every open subset V of Y (or equivalently for every (relative) coanalytic subset V of Y). Of course all Borel functions are Δ_{1}^{1}. Moreover the composition of two Δ_{1}^{1} functions is Δ_{1}^{1} too.

Recall that a continuous function f : X → Y reduces a subset D of X to a subset C of Y if D = f^{−1}(C) and that a coanalytic subset C of the Polish space Y is said to be Π_{1}^{1}-complete (or simply complete for short if there is no ambiguity) if every coanalytic subset D of a zero-dimensional Polish space X is continuously reducible to C (i.e. if there is a continuous function f : X → Y which reduces D to C). There are many “natural” examples of complete coanalytic sets, namely WF in 𝒯 , 𝒦 (ℚ) in 𝒦 (2^{ω}) or 𝒦_{ω}(2^{ω}) in 𝒦 (2^{ω}). It is a well-known fact that, under the axiom of analytic determinacy, any coanalytic non-Borel subset of ω^{ω} or of 2^{ω} is Π_{1}^{1}-complete. Moreover it is a classical result of Harrington ([3]) that the converse is true : if any non-Borel coanalytic subset of 2^{ω} is Π_{1}^{1}-complete, then the analytic determinacy holds.

The main goal of this note is to give similar results for disjoint pairs of coanalytic subsets in a Polish space. Let X and Y be two Polish spaces, (C_{0}, C_{1}) be a pair of disjoint coanalytic subsets of Y and (D_{0}, D_{1}) be a pair of disjoint coanalytic subsets of X. We will say that the pair (D_{0}, D_{1}) is continuously reducible to the pair (C_{0}, C_{1}) if there exists a continuous function f : X → Y such that f^{−1}(C_{0}) = D_{0} and f^{−1}(C_{1}) = D_{1}. Like for complete coanalytic sets we define complete pairs of coanalytic sets. Definition. We say that the pair (C_{0}, C_{1}) is complete if every disjoint pair (D_{0}, D_{1}) of coanalytic subsets of a zero-dimensional Polish space X (or equivalently of a closed subspace of ω^{ω}) is continuously reducible to (C_{0}, C_{1}).

We will study the links between Borel separabilty and completeness for pairs of coanalytic subsets. We will also give several “natural” examples of complete pairs of coanalytic subsets, and this will lead us to find a characterization of bianalytic functions. Finally we will give extensions of the previous results to disjoint sequences of coanalytic sets.

2. Some coanalytic sets

The following two theorems are known for long (see for example [2] and the references therein). Theorem 1. Let X and Y be Polish, Z be a subspace of X and f : Z → Y be bianalytic. Then there exists a coanalytic subset C of X containing Z and a bianalytic function f̃: C → Y extending f.

Let Y and Z be Polish spaces and X be a subspace of Y ×Z. We will denote by U(X) the set of elements y of Y such that the fiber X(y) := {z ∈ Z : (y, z) ∈ X} is a singleton. Theorem 2. Let Y and Z be Polish spaces and X be a Borel subset of Y × Z. Then the set U(X) is coanalytic and the function g : U(X) → Z defined by {g(y)} = X(y) is bianalytic on U(X).

Proof. For sake of self-completeness we give here a proof of Theorem 2.

Denote by π : Y × Z → Y the first projection : (y, z) ↦ y. We prove first that the function g is bianalytic on U(X). Indeed let V be an open subset of Z. We have

g^{−1}(V) = U(X) \ π(X ∩ (Y × V^{c}))

which is coanalytic in U(X) since π(X ∩ (Y × V^{c})) ∈ Σ_{1}^{1}. Thus g is bianalytic.

Using Theorem 1 we get a coanalytic subset C of Y containing U(X) and a bianalytic extension g̃ : C → Z of g. The set X_{2} of points of Y where the fiber has at least two points is

{y ∈ Y : ∃z, z′ z′ ≠ z and (y, z) ∈ X and (y, z′) ∈ X}

hence is analytic. And we have

U(X) ⊂ {y ∈ C \ X_{2} : g̃(y) ∈ X} ⊂ U(X)

and this shows that U(X) ∈ Π_{1}^{1} since the inverse image of the Borel set X under g̃ is coanalytic in the coanalytic set C \ X_{2}. □

Again for sake of self-completeness we now give proofs of the classical fact that 𝒦 ^{∗}(ℚ), 𝒦_{ω}(2^{ω}) \ 𝒦 (ℚ) and WF^{∗} are all coanalytic.

Theorem 3. The set 𝒦 ^{∗}(ℚ) is Π_{1}^{1} in 𝒦 (2^{ω}).

Proof. Let X = {(K, α) ∈ 𝒦 (2^{ω}) × 2^{ω} : α ∈ K and α ∉ ℚ}. Then X is clearly a Π_{2}^{0} subset of the compact space 𝒦 (2^{ω}) × 2^{ω}. And since 𝒦 ^{∗}(ℚ) = U(X) the conclusion follows from Theorem 2. □

Theorem 4. The set WF^{∗} is Π_{1}^{1} in 𝒯 .

Proof. Let X = {(T, α) ∈ 𝒯 × ω^{ω} : α ∈ ⌈T ⌉}. Then X is clearly a closed subset of the Polish space 𝒯 × ω^{ω}. And since WF^{∗} = U(X) the conclusion follows again from Theorem 2. □

Theorem 5. The set 𝒦_{ω}(2^{ω}) \ 𝒦 (ℚ) is Π_{1}^{1} in 𝒦 (2^{ω}).

Proof. The proof of the following lemma which is probably folklore can be found in [4] (Exercise 39.23, p. 368).

Lemma 6. There is a countable family (C_{u}) of coanalytic subsets of 𝒦_{ω}(2^{ω}) and a family (f_{u}) of Δ_{1}^{1} functions from C_{u} to 2^{ω} such that for every countable compact subset K of 2^{ω} :

K = {f_{u}(K) : K ∈ C_{u}}

Proof. Consider the following open game G^{∗}(K) with parameter K ∈ 𝒦 (2^{ω}) : Player II begins by playing some s_{0} ∈ 2^{<ω}, Player I answers a_{0} ∈ {0, 1}, Player II plays s_{1} ∈ 2^{<ω} and Player I answers a_{1} ∈ {0, 1}, and so on. And Player II wins the run (s_{0}, a_{0}, s_{1}, a_{1}, …) iff the infinite dyadic sequence s_{0}^{⌢}a_{0}^{⌢}s_{1}^{⌢} ⋯^{⌢}s_{n}^{⌢}a_{n}^{⌢} ⋯ belongs to K.

If Player II has a winning strategy τ in G^{∗}(K), this strategy defines a continuous mapping f : 2^{ω} → K by

f(α) = s_{0}^{⌢}α(0)^{⌢}s_{1}^{⌢}α(1)^{⌢} ⋯

where (s_{0}, s_{1}, …) is the answer by τ to α. It is easily checked that f is one-to-one hence that K is uncountable if Player II has a winning strategy.

Conversely, if Player I has a winning strategy σ in G^{∗}(K) we consider the set S_{σ} of finite sequences u = ⟨s_{0}, a_{0}, s_{1}, a_{1}, …, s_{n−1}, a_{n−1}⟩ such that for all p < n, a_{p} is the answer by σ to (s_{0}, s_{1}, …, s_{p}), and denote χ(u) := s_{0}^{⌢}a_{0}^{⌢}s_{1}^{⌢}a_{1}^{⌢} …^{⌢}a_{n−1} whenever u = ⟨s_{0}, a_{0}, s_{1}, a_{1}, …, s_{n−1}, a_{n−1}⟩.

Then, for u ∈ S_{σ} we consider the set :

E_{u} := {α ∈ 2^{ω} : χ(u) ≺ α and ∀v ∈ S_{σ} u ≺ v ⟹ χ(v) ⊀ α}

It is easily checked that E_{u} contains at most one point : indeed if χ(u) = α_{|p} and u = ⟨s_{0}, a_{0}, s_{1}, a_{1}, …, s_{n−1}, a_{n−1}⟩ then for every s = ⟨α(p), α(p + 1), …, α(q − 1)⟩ and a = σ(s_{0}, s_{1}, …, s_{n−1}, s) we have v := u^{⌢}⟨s, a⟩ ∈ S_{σ} hence χ(v) ⊀ α. Thus α(q) = 1 − a. This allows to find inductively the coordinates of α from σ.

Moreover, if α ∉ ⋃_{u∈S_{σ}} E_{u}, one can construct inductively a sequence (u_{n}) of elements of S_{σ} such that u_{0} = ∅, u_{n} ≺ u_{n+1} and χ(u_{n}) ≺ α for all n : indeed if u_{n} is defined and satisfies χ(u_{n}) ≺ α then since α ∉ E_{u_{n}} there exists u_{n+1} ∈ S_{σ} such that u_{n} ≺ u_{n+1} and χ(u_{n+1}) ≺ α. And since Player I wins the corresponding infinite run in G^{∗}(K) we conclude that α ∉ K. So

K ⊂ ⋃_{u∈S_{σ}} E_{u}

and K is countable. It follows from what precedes that G^{∗}(K) is won by Player I if and only if K is countable.

The set {(K, s_{0}, a_{0}, s_{1}, a_{1}, …) : Player I wins the game G^{∗}(K)} is open in the Polish space 𝒦 (2^{ω}) × Seq^{ω} × 2^{ω}. It follows by Martin’s theorem that the set 𝒦_{ω}(2^{ω}) of those K such that Player I has a winning strategy in G^{∗}(K) is Π_{1}^{1} and that there exists a bianalytic function K ↦ σ_{K} defined on 𝒦_{ω}(2^{ω}) assigning to each countable compact subset K of 2^{ω} a winning strategy in the game G^{∗}(K).

Then for each sequence u = ⟨s_{0}, a_{0}, s_{1}, a_{1}, …, s_{n−1}, a_{n−1}⟩ the set

C′_{u} := {K ∈ 𝒦_{ω}(2^{ω}) : u ∈ S_{σ_{K}}}

is coanalytic. The function f_{u} defined on C′_{u} by f_{u}(K) = β ∈ 2^{ω} where χ(u) ≺ β and, for q ≥ p := |χ(u)|,

β(q) = 1 − σ_{K}(s_{0}, s_{1}, …, s_{n−1}, ⟨β(p), β(p + 1), …, β(q − 1)⟩)

depends continuously on σ_{K}, hence is bianalytic on C′_{u}. It follows from what precedes that C_{u} := {K ∈ C′_{u} : f_{u}(K) ∈ K} is coanalytic and that every countable K in 𝒦 (2^{ω}) satisfies

K = {f_{u}(K) : K ∈ C_{u}}

and this completes the proof of the lemma. □

It follows from the previous lemma that K ∈ 𝒦_{ω}(2^{ω}) \ 𝒦 (ℚ) if and only if there is some u = ⟨s_{0}, a_{0}, s_{1}, a_{1}, …, s_{n−1}, a_{n−1}⟩ such that K ∈ C_{u} and f_{u}(K) ∉ ℚ, hence

𝒦_{ω}(2^{ω}) \ 𝒦 (ℚ) = ⋃_{u} C_{u} ∩ f_{u}^{−1}(2^{ω} \ ℚ)

which is a countable union of coanalytic sets, hence coanalytic itself. □

3. Borel separation of coanalytic sets

We now compare for a disjoint pair of coanalytic sets (C_{0}, C_{1}) the property “(C_{0}, C_{1}) is complete” with the property “C_{0} is not separable from C_{1} by a Borel set”.

Lemma 7. Let (C_{0}, C_{1}) be a disjoint pair of coanalytic subsets of ω^{ω}. If the pair (C_{0}, C_{1}) is complete then no Borel subset B of ω^{ω} can separate C_{0} from C_{1}.

Proof. Assume that some Borel set B separates C_{0} from C_{1}. Then B is Σ_{ξ}^{0} for some countable ordinal ξ. If the pair (C_{0}, C_{1}) were complete then for any Borel subset B_{1} of ω^{ω}, the pair (B_{1}, ω^{ω} \ B_{1}) would be a disjoint pair of coanalytic sets, and there would be a continuous f : ω^{ω} → ω^{ω} such that f^{−1}(C_{0}) = B_{1} and f^{−1}(C_{1}) = ω^{ω} \ B_{1} hence B_{1} = f^{−1}(B), and this would imply that B_{1} ∈ Σ_{ξ}^{0}, in contradiction with the existence of Borel sets in ω^{ω} of arbitrarily large rank. □

Theorem 8. Assume Det(Σ_{1}^{1}). Let (C_{0}, C_{1}) be a disjoint pair of coanalytic subsets of ω^{ω}. Then the pair (C_{0}, C_{1}) is complete if no Borel subset B of ω^{ω} separates C_{0} from C_{1}.

Conversely, if any pair of disjoint and Borel non-separable coanalytic sets is complete then the analytic games are determined.

Proof. Assume that no Borel set separates C_{0} from C_{1} and that (D_{0}, D_{1}) is a disjoint pair of coanalytic subsets of ω^{ω}. Consider the game G where Player I and Player II play alternately integers and construct respectively α ∈ ω^{ω} and β ∈ ω^{ω} and where Player II wins iff

(α ∈ D_{0} and β ∈ C_{0}) or (α ∈ D_{1} and β ∈ C_{1}) or (α ∉ D_{0} ∪ D_{1} and β ∉ C_{0} ∪ C_{1})

Clearly the payoff of this game is the difference of two analytic sets hence the game G is determined under the assumption of analytic determinacy.

If Player I has a winning strategy σ, this strategy induces a continuous function g : ω^{ω} → ω^{ω} such that

g^{−1}(D_{0}) ∩ C_{0} = g^{−1}(D_{1}) ∩ C_{1} = g^{−1}(ω^{ω} \ (D_{0} ∪ D_{1})) ∩ (ω^{ω} \ (C_{0} ∪ C_{1})) = ∅

Then denoting by C′_{0} and C′_{1} the coanalytic sets g^{−1}(D_{0}) and g^{−1}(D_{1}), and by A and A′ the analytic sets ω^{ω} \ (C_{0} ∪ C_{1}) and ω^{ω} \ (C′_{0} ∪ C′_{1}), we have A ∩ A′ = ∅. Thus there exists a Borel set B^{∗} separating A from A′. Since B^{∗} ⊂ C′_{0} ∪ C′_{1} and C′_{0} ∩ C′_{1} = ∅, B^{∗} ∩ C′_{0} and B^{∗} ∩ C′_{1} are both Borel. Moreover ω^{ω} \ B^{∗} ⊂ C_{0} ∪ C_{1} and C_{0} ∩ C_{1} = ∅ hence C_{0} \ B^{∗} and C_{1} \ B^{∗} are both Borel. And it is easily checked that the Borel set

B = (B^{∗} ∩ C′_{1}) ∪ (C_{0} \ B^{∗})

contains C_{0} and is disjoint from C_{1}. Thus Player I cannot have a winning strategy if C_{0} and C_{1} cannot be separated by a Borel set.

So Player II has a winning strategy τ which induces a continuous function f from ω^{ω} to ω^{ω} such that f^{−1}(C_{i}) = D_{i} for i = 0, 1, and this shows that every pair (D_{0}, D_{1}) is reducible to the pair (C_{0}, C_{1}), hence that the pair (C_{0}, C_{1}) is complete.

We now prove that, as in Harrington’s result, the analytic determinacy holds if any pair of coanalytic subsets of 2^{ω} is complete as soon as it is not Borel separable.

Let C be any non-Borel coanalytic subset of 2^{ω}, Γ be a complete coanalytic subset of 2^{ω} and φ be a Π_{1}^{1}-norm on Γ. We claim that if any non-Borel separable pair of coanalytic subsets of 2^{ω} is complete then Γ is continuously reducible to C, and by Harrington’s theorem this will imply that the analytic determinacy holds. Since Γ is Π_{1}^{1}-complete there exists a continuous function g : 2^{ω} → 2^{ω} such that g^{−1}(Γ) = C. Then it is easily checked that the function φ∘g is a Π_{1}^{1}-norm on C and that the sets

C_{0} = {(x, y) ∈ C × 2^{ω} : φ(g(x)) ≤^{∗} φ(y)}
C_{1} = {(x, y) ∈ 2^{ω} × Γ : φ(y) <^{∗} φ(g(x))}

are disjoint and both coanalytic. Then our claim will follow from the next two lemmas.

Lemma 9. No Borel set can separate C_{0} from C_{1}.

Proof. Assume towards a contradiction that B is a Σ_{ξ}^{0} subset of 2^{ω}×2^{ω} separating C_{0} from C_{1}. Let P be a Borel non-Π_{ξ}^{0} subset of 2^{ω}. Since Γ is Π_{1}^{1}-complete, P is reducible to Γ, and there is some continuous f : 2^{ω} → 2^{ω} such that P = f^{−1}(Γ). Then A = f(P) is a Σ_{1}^{1} subset of Γ and the norm φ is bounded on A by some ordinal η. Furthermore since C is coanalytic non-Borel, the norm φ∘g is unbounded on C. Thus there exists some x ∈ C such that η′ := φ∘g(x) > η. Denote by B′ the Π_{ξ}^{0} set {y : (x, y) ∉ B}. Then for y ∈ 2^{ω} we have :

y ∈ A ⟹ η′ > φ(y) ⟹ (x, y) ∈ C_{1} ⟹ (x, y) ∉ B ⟹ y ∈ B′
y ∉ Γ ⟹ η′ ≤^{∗} φ(y) ⟹ (x, y) ∈ C_{0} ⟹ (x, y) ∈ B ⟹ y ∉ B′

hence A ⊂ B′ ⊂ Γ. Thus P ⊂ f^{−1}(B′) ⊂ f^{−1}(Γ) = P. And we conclude that the Π_{ξ}^{0} set f^{−1}(B′) is equal to P, a contradiction. □

Lemma 10. If the pair (C_{0}, C_{1}) is complete, then Γ is continuously reducible to C.

Proof. If (C_{0}, C_{1}) is complete then the pair (Γ, ∅) is reducible to (C_{0}, C_{1}), and there are two continuous functions f_{0} and f_{1} from 2^{ω} to 2^{ω} such that f = f_{0} × f_{1} reduces (Γ, ∅) to (C_{0}, C_{1}). So

x ∈ Γ ⟹ (f_{0}(x), f_{1}(x)) ∈ C_{0} ⟹ f_{0}(x) ∈ C
x ∉ Γ ⟹ (f_{0}(x), f_{1}(x)) ∉ C_{0} ∪ C_{1} ⟹ f_{0}(x) ∉ C

and this shows that f_{0} reduces Γ to C. □

Thus the proof of Theorem 8 is complete. □

The following result is well-known.

Lemma 11. There exist complete disjoint pairs of coanalytic subsets of 2^{ω}.

Proof. Let C be a complete Π_{1}^{1} subset of 2^{ω}. Then C × 2^{ω} and 2^{ω} × C are coanalytic subsets of 2^{ω} × 2^{ω} ≃ 2^{ω} and since the class Π_{1}^{1} has the reduction property there are disjoint coanalytic subsets C_{0} and C_{1} of 2^{ω} × 2^{ω} such that C_{0} ⊂ C × 2^{ω}, C_{1} ⊂ 2^{ω} × C and C_{0} ∪ C_{1} = (C × 2^{ω}) ∪ (2^{ω} × C).

We claim that the pair (C_{0}, C_{1}) is complete. Let X be a zero-dimensional Polish space, and (D_{0}, D_{1}) a disjoint pair of coanalytic subsets of X. Since C is complete there are continuous functions f and g : X → 2^{ω} such that D_{0} = f^{−1}(C) and D_{1} = g^{−1}(C). Then the function h = f × g : X → 2^{ω} × 2^{ω} is continuous and satisfies h(D_{0}) ⊂ C × (2^{ω} \ C) ⊂ C_{0}, h(D_{1}) ⊂ (2^{ω} \ C) × C ⊂ C_{1} and

h(X \ (D_{0} ∪ D_{1})) ⊂ (2^{ω} \ C) × (2^{ω} \ C) = (2^{ω} × 2^{ω}) \ (C_{0} ∪ C_{1})

which shows that the pair (C_{0}, C_{1}) is complete. □

4. Bianalytic functions

Our goal is now to give “natural” examples of complete pairs of coanalytic sets. And for this we need several results on bianalytic functions.

Lemma 12. Let X be a zero-dimensional Polish space and (C_{0}, C_{1}) a disjoint pair of coanalytic subsets of X. Then there exists a bianalytic function h : C_{0} → ω^{ω} such that no point of C_{1} × ω^{ω} lies in the closure of the graph of h.

Proof. It is a well-known fact that WF is Π_{1}^{1}-complete in 𝒯 and that the height T ↦ ht(T) is a Π_{1}^{1} norm on WF. So if we define

Γ_{0} := {(S, T) ∈ 𝒯 × 𝒯 : S ∈ W F and ht(S) <^{∗} ht(T)}
Γ_{1} := {(S, T) ∈ 𝒯 × 𝒯 : T ∈ WF and ht(T) ≤^{∗} ht(S)}

we see as in Lemma 11 that the pair (Γ_{0}, Γ_{1}) is complete in 𝒯 × 𝒯 . So there exists a continuous mapping φ : X → 𝒯 × 𝒯 which reduces (C_{0}, C_{1}) to (Γ_{0}, Γ_{1}). It is enough to prove the lemma for the pair (Γ_{0}, Γ_{1}) since if ψ : Γ_{0} → ω^{ω} has the required property for the pair (Γ_{0}, Γ_{1}), so does h = ψ∘φ for the pair (C_{0}, C_{1}). Indeed assume that the sequence (x_{j}) in C_{0} converges to x ∈ C_{1} and that (h(x_{j})) converges to α ∈ ω^{ω}. Then (β_{j}) = (φ(x_{j})) is a sequence in Γ_{0} which converges to β = φ(x) ∈ Γ_{1} and ψ(β_{j}) → α. So (β, α) is a cluster point of the graph of ψ with β ∈ Γ_{1}, in contradiction with the hypothesis on ψ.

Consider the following open game G(S, T) with parameters S and T in 𝒯 : Player I plays integers m_{0}, m_{1}, … and Player II plays integers n_{0}, n_{1}, … with the rule :

“⟨n_{0}, n_{1}, …, n_{k−1}⟩ must be in S whenever ⟨m_{0}, m_{1}, …, m_{k−1}⟩ is in T ”. And Player II wins a run if it respects the rule forever.

We claim that Player I has a winning strategy in G(S, T) if (S, T) ∈ Γ_{0}. As usual, for T ∈ 𝒯 and t ∈ ω^{<ω} we denote by T_{t} the tree {s ∈ ω^{<ω} : t^{⌢}s ∈ T }. Since

ht(T) = ht(T_{∅}) = sup_{m}(ht(T_{m}) + 1) > ht(S)

there is an m_{0} such that ht(T_{m_{0}}) + 1 > ht(S) hence ht(T_{m_{0}}) ≥ ht(S) > ht(S_{n_{0}}) since S is well-founded.

In the same way, if Player I has played t = ⟨m_{0}, m_{1}, …, m_{k−1}⟩ and Player II has played s = ⟨n_{0}, n_{1}, …, n_{k−1}⟩ in such a way that ht(T_{t}) > ht(S_{s}) we have again :

ht(T_{t}) = sup_{m}(ht(T_{t^{⌢}m}) + 1) > ht(S_{s})

hence Player I can find and play an integer m_{k} such that ⟨m_{0}, m_{1}, …, m_{k}⟩ ∈ T and ht(T_{t^{⌢}m_{k}}) ≥ ht(S_{s}) > ht(S_{s^{⌢}n_{k}}). Since the sequence (ht(S_{⟨n_{0},n_{1},...,n_{k}⟩})) of ordinals is decreasing, there must be a least integer k such that ⟨n_{0}, n_{1}, …, n_{k}⟩ ∉ S whereas ⟨m_{0}, m_{1}, …, m_{k}⟩ ∈ T, and Player I wins.

As in Lemma 6 it follows from Martin’s theorem that there is a bianalytic function (S, T) ↦ σ_{S,T} on Γ_{0} which assigns to each (S, T) a winning strategy for Player I in G(S, T). Viewing a strategy σ as a function ⟨n_{0}, n_{1}, …, n_{k−1}⟩ ↦ m_{k} from Seq = ω^{<ω} to ω, we identify the set Σ of I-strategies to ω^{Seq} ≃ ω^{ω}. We now have to prove that if (S^{(j)}) and (T^{(j)}) are sequences of trees converging to S and T respectively, if (S^{(j)}, T^{(j)}) ∈ Γ_{0} and if σ^{(j)} = σ_{S^{(j)},T^{(j)}} converges to σ ∈ Σ then (S, T) cannot belong to Γ_{1}.

Assume towards a contradiction that (S, T) ∈ Γ_{1}. Then T is well-founded and ht(T) ≤^{∗} ht(S). We define sequences of integers (m_{k}) and (n_{k}) such that for all k:

m_{k} = σ(⟨n_{0}, n_{1}, …, n_{k−1}⟩) and ht(T_{⟨m_{0},m_{1},...,m_{k}⟩}) < ht(S_{⟨n_{0},n_{1},...,n_{k−1}⟩})

Indeed if ht(T_{⟨m_{0},m_{1},...,m_{k}⟩}) < ht(S_{⟨n_{0},n_{1},...,n_{k−1}⟩}), we have

ht(T_{⟨m_{0},m_{1},...,m_{k}⟩}) < ht(S_{⟨n_{0},n_{1},...,n_{k−1}⟩}) = sup_{n}(ht(S_{⟨n_{0},n_{1},...,n_{k−1}⟩^{⌢}n}) + 1)

and there is a n_{k} such that ht(T_{⟨m_{0},m_{1},...,m_{k}⟩}) < ht(S_{⟨n_{0},n_{1},...,n_{k}⟩}) + 1. Then for m_{k+1} = σ(⟨n_{0}, n_{1}, …, n_{k}⟩) we get

ht(T_{⟨m_{0},m_{1},...,m_{k+1}⟩}) < ht(T_{⟨m_{0},m_{1},...,m_{k}⟩}) ≤ ht(S_{⟨n_{0},n_{1},...,n_{k}⟩})

and this allows us to pursue the inductive construction.

And since T is well-founded there is some k such that ⟨m_{0}, m_{1}, …, m_{k+1}⟩ ∉ T whereas ⟨n_{0}, n_{1}, …, n_{k}⟩ ∈ S. Let k the least with this property. Since (S^{(j)}) converges to S, (T^{(j)}) converges to T and (σ^{(j)}) converges to σ we have for all large enough j: ⟨n_{0}, n_{1}, …, n_{p}⟩ ∈ S^{(j)} for p ≤ k, ⟨m_{0}, m_{1}, …, m_{p}⟩ ∈ T^{(j)} for p ≤ k, ⟨m_{0}, m_{1}, …, m_{k+1}⟩ ∉ T^{(j)} and m_{p} = σ^{(j)}(⟨n_{0}, n_{1}, …, n_{p−1}⟩) for p ≤ k + 1, in contradiction with the choice of σ^{(j)} as a winning strategy in G(S^{(j)}, T^{(j)}). And this contradiction completes the proof of Lemma 12. □

Lemma 13. Let X be a Polish space and (C_{0}, C_{1}) a disjoint pair of coanalytic subsets of X. Then there exists a bianalytic function h : C_{0} → ω^{ω} such that no point of C_{1} × ω^{ω} lies in the closure of the graph of h.

Proof. Define C = C_{0} ∪ C_{1}. Since X is Polish there exists a closed subset X^{∗} of ω^{ω} and a continuous bijection φ from X^{∗} onto X. Then φ^{−1} is Borel from X to X^{∗}, and so is h_{0} = φ^{−1}_{|C} : C → X^{∗} ⊂ ω^{ω}. Define C_{i}^{∗} = φ^{−1}(C_{i}) for i = 0, 1. Then (C_{0}^{∗}, C_{1}^{∗}) is a disjoint pair of coanalytic subsets of X^{∗}. Then applying Lemma 12 to (C_{0}^{∗}, C_{1}^{∗}) we get a bianalytic function h^{∗} : C_{0}^{∗} → ω^{ω} such that the graph of h^{∗} has no cluster point in C_{1}^{∗} × ω^{ω}. Put h_{1} = h^{∗}∘h_{0} : C_{0} → ω^{ω} and h = h_{0} × h_{1} : C → ω^{ω} × ω^{ω} ≃ ω^{ω}.

If (x_{j}) were a sequence in C_{0} converging to x ∈ C_{1} with h(x_{j}) → (x^{∗}, α) we would have x_{j}^{∗} := h_{0}(x_{j}) ∈ C_{0}^{∗}, x_{j}^{∗} → x^{∗} and h^{∗}(x_{j}^{∗}) → α, hence x_{j} = φ(x_{j}^{∗}) → φ(x^{∗}). This would show that φ(x^{∗}) = x ∈ C_{1} hence that x^{∗} ∈ C_{1}^{∗}, in contradiction with the choice of h^{∗}. □

Lemma 14. Let X be a Polish space and (C_{0}, C_{1}) be a disjoint pair of coanalytic subsets of X. Denote by C the set C_{0} ∪ C_{1} and by g : C → {0, 1} the bianalytic function defined by g(x) = 0 ⟺ x ∈ C_{0}. Then there exists a bianalytic function h : C → ω^{ω} such that for every sequence (x_{j}) in C converging to some x ∈ C, if (g(x_{j})) converges to a ∈ {0, 1} and (h(x_{j})) converges to some α ∈ ω^{ω} then g(x) = a.

Proof. Applying Lemma 13 to (C_{0}, C_{1}) and to (C_{1}, C_{0}) we get bianalytic functions h_{0} : C_{0} → ω^{ω} and h_{1} : C_{1} → ω^{ω} such that the closure of the graph of h_{i} is disjoint from C_{1−i} × ω^{ω} for i = 0, 1. Define then h : C → ω^{ω} by

h(x) = \begin{cases}h_{0}(x) & if x ∈ C_{0} \\ h_{1}(x) & if x ∈ C_{1} \end{cases}

Clearly h is Δ_{1}^{1} on C. Moreover if the sequence (x_{j}) converges to x ∈ C with g(x_{j}) → a ∈ {0, 1} and h(x_{j}) → α ∈ ω^{ω}, we have for j large enough x_{j} ∈ C_{a} and h(x_{j}) = h_{a}(x_{j}) → α. We can conclude that x ∉ C_{1−a} hence that x ∈ C_{a} and that g(x) = a. □

Lemma 15. Let X be a Polish space and (C_{0}, C_{1}) be a disjoint pair of coanalytic subsets of X. Denote by C the set C_{0} ∪ C_{1} and by g : C → {0, 1} the bianalytic function defined by g(x) = 0 ⟺ x ∈ C_{0}. Then there exists a bianalytic function h : C → ω^{ω} such that the function g × h : C → {0, 1} × ω^{ω} has a closed graph.

Proof. Let (W_{k})_{k∈ω} a sequence of clopen subsets of ω^{ω} separating the points of ω^{ω}. We can define inductively for s ∈ Seq bianalytic functions g_{s} : C → {0, 1} and h_{s} : C → ω^{ω} in such a way that

(i) g_{∅} = g, (ii) g_{s^{⌢}k}(x) = 1 ⟺ h_{s}(x) ∈ W_{k}, (iii) For every sequence (x_{j}) converging to x in C, if (g_{s}(x_{j})) converges to a

in {0, 1} and (h_{s}(x_{j})) converges to α in ω^{ω} then g_{s}(x) = a.

Indeed, if g_{s} is defined, we get h_{s} by Lemma 14. And if h_{s} is Δ_{1}^{1}, so are the functions g_{s^{⌢}k} = 1_{W_{k}} ∘h_{s}, where 1_{W_{k}} is the characteristic function of W_{k}, which is continuous on ω^{ω}.

Then if we define h = ∏_{s∈Seq} h_{s} : C → (ω^{ω})^{Seq} ≃ ω^{ω}, the function h is Δ_{1}^{1}. Moreover, if (x_{j}) is a sequence in C converging to x ∈ C with

g_{∅}(x_{j}) = g(x_{j}) → a_{∅} := a ∈ {0, 1} and h(x_{j}) → β = (α_{s})_{s∈Seq}

we have h_{s}(x_{j}) → α_{s} for all s ∈ Seq hence g_{s^{⌢}k}(x_{j}) → a_{s^{⌢}k} := 1_{W_{k}}(α_{s}) for all s ∈ Seq and all k.

For all s we have g_{s}(x_{j}) → a_{s} and h_{s}(x_{j}) → α_{s} hence g_{s}(x) = a_{s}. In particular g(x) = g_{∅}(x) = a_{∅} = a. And if we had h_{s}(x) ≠ α_{s} for some s ∈ Seq there would exist some k such that 1_{W_{k}}(h_{s}(x)) ≠ 1_{W_{k}}(α_{s}), hence g_{s^{⌢}k}(x) ≠ a_{s^{⌢}k}, a contradiction. We conclude that g(x) = a and h(x) = β, hence that the graph of g × h is closed. □

Theorem 16. Let X and Y be Polish spaces, C be a coanalytic subset of X and g : C → Y be a Δ_{1}^{1} function. Then there exists a Δ_{1}^{1} function h : C → ω^{ω} such that the graph of g × h is closed in C × Y × ω^{ω}.

Proof. There exists a closed subset Y^{∗} of ω^{ω}, a continuous bijection φ : Y^{∗} → Y and a homeomorphic embedding ρ of Y^{∗} into 2^{ω}. Then ψ = φ^{−1} : Y → Y^{∗} is Borel, ρ∘ψ∘g : C → 2^{ω} is bianalytic, and so are the coordinate functions g_{n} : C → {0, 1} of ρ∘ψ∘g. Applying Lemma 15 to each g_{n} we find bianalytic functions h_{n} : C → ω^{ω} such that the graph of g_{n} × h_{n} is closed in C × {0, 1} × ω^{ω} for all n.

Define then h = (ψ∘g) × ∏_{n} h_{n} : C → ω^{ω} × (ω^{ω})^{ω} ≃ ω^{ω}. If the sequence (x_{j}) converges in C to x with y_{j} := g(x_{j}) → y and h(x_{j}) → β = (y^{∗}, (α_{n})_{n∈ω}), the sequence (y_{j}^{∗}) := (ψ∘g(x_{j})) converges to y^{∗}. Thus y_{j} = φ(y_{j}^{∗}) → φ(y^{∗}) and this shows that φ(y^{∗}) = y hence y^{∗} = ψ(y). Moreover ρ∘ψ∘g(x_{j}) = ρ(y_{j}^{∗}) → ρ(y^{∗}) = (a_{n}) ∈ 2^{ω} and ρ(y^{∗}) = ρ∘ψ(y). Hence g_{n}(x_{j}) → a_{n} and h_{n}(x_{j}) → α_{n}. Since the graph of g_{n} × h_{n} is closed we get a_{n} = g_{n}(x) and h_{n}(x) = α_{n} for all n, hence ρ∘ψ∘g(x) = ρ∘ψ(y) and h(x) = β. Thus g(x) = y and h(x) = β, and this shows that g × h has a closed graph. □

Corollary 17. Let X be a separable metrizable space, Y be a Polish space and g be a mapping from X to Y. Then g is bianalytic if and only if there exists a Polish space Z and a mapping h : X → Z such that g × h : X → Y × Z has a closed graph in X × Y × Z.

Proof. Assume first that there exists h : X → Z such that g×h has a closed graph G. Let X̂ be the completion of X and \overline{G} be the closure of G in X̂ ×(Y ×Z). Since G is closed in X × (Y × Z) we have X ⊂ U(\overline{G}) and the mapping x ↦ (g(x), h(x)) is bianalytic on U(\overline{G}) by Theorem 2. It follows that g is Δ_{1}^{1} on X.

Conversely, if g is Δ_{1}^{1} on X, it has a Δ_{1}^{1} extension g̃ on a coanalytic subset C of X̂ containing X. Applying Theorem 16 we get a Δ_{1}^{1} mapping h : C → ω^{ω} such that g̃ × h has a closed graph on C. It follows that the graph of g × h_{|X} is closed in X × Y × ω^{ω}. □

5. Some examples of complete pairs of coanalytic sets

Lemma 18. Let X be a Polish space and (C_{0}, C_{1}) be a disjoint pair of coanalytic subsets of X. Denote by π : X × 2^{ω} → X the projection (x, α) ↦ x. Then there exists a Π_{2}^{0} subset B of X × 2^{ω} such that C_{0} ⊂ X \ π(B) and C_{1} ⊂ U(B).

Proof. Let C = C_{0} ∪ C_{1} and g : C → {0, 1} be the bianalytic function defined by g(x) = 0 ⟺ x ∈ C_{0}. By Lemma 15 there exists a Δ_{1}^{1} function h : C → ω^{ω} such that the graph G of g × h is closed in C × {0, 1} × ω^{ω}. Then for x ∈ C, a ∈ {0, 1} and α ∈ ω^{ω} we have

(x, a, α) ∈ \overline{G} ⟺ a = g(x) and α = h(x)

Denote by φ a homeomorphism from ω^{ω} to a Π_{2}^{0} subset Y of 2^{ω} (e.g. 2^{ω} \ ℚ) and define

B = \{(x, β) ∈ X × Y : (x, 1, φ^{−1}(β)) ∈ \overline{G}\}

Clearly B is closed in X × Y hence Π_{2}^{0} in X × 2^{ω}. Moreover for x ∈ C_{0} there is exactly one point (x, a, α) ∈ \overline{G} and a = 0. Thus x ∉ π(B). And for x ∈ C_{1} there is exactly one point (x, a, α) ∈ \overline{G}, and a = 1. So x ∈ U(B). □

Theorem 19. Let X be a zero-dimensional Polish space and (C_{0}, C_{1}) a disjoint pair of coanalytic subsets of X. Then there exists a continuous function Φ : X → 𝒦 (2^{ω}) such that Φ(x) ∈ 𝒦 (ℚ) if x ∈ C_{0}, Φ(x) ∈ 𝒦 ^{∗}(ℚ) if x ∈ C_{1} and Φ(x) ∉ 𝒦_{ω}(2^{ω}) if x ∉ C_{0} ∪ C_{1}.

Proof. By Lemma 18 there exists a Π_{2}^{0} subset B of X ×2^{ω} such that C_{0}∩π(B) = ∅ and C_{1} ⊂ U(B). Since X × 2^{ω} is zero-dimensional there is a continuous function f : X × 2^{ω} → 2^{ω} reducing the Π_{2}^{0} set B to 2^{ω} \ ℚ. Then for x ∈ X we put

Φ′(x) = f({x} × 2^{ω}) ∈ 𝒦 (2^{ω})

Since the mapping x ↦ {x} × 2^{ω} is continuous from X to 𝒦 (X × 2^{ω}), it follows that Φ′ is continuous.

If x ∈ C_{0} then x ∉ π(B) hence {x} × 2^{ω} ⊂ f^{−1}(ℚ) and Φ′(x) ∈ 𝒦 (ℚ). If x ∈ C_{1} then x ∈ U(B) hence ({x}×2^{ω})\f^{−1}(ℚ) has exactly one point : it follows that Φ′(x) ∈ 𝒦 ^{∗}(ℚ).

Moreover C = C_{0} ∪ C_{1} is coanalytic, and there exists a continuous mapping Φ′′ from X to 𝒦 (2^{ω}) such that Φ′′(x) ∈ 𝒦 (ℚ) for all x in C and Φ′′(x) ∉ 𝒦_{ω}(2^{ω}) for all x outside C (see for example Lemma 5.1.7 in [1]).

Then the mapping Φ : x ↦ Φ′(x) ∪ Φ′′(x) is clearly continuous from X to 𝒦 (2^{ω}) and has the required properties. □

We deduce immediately from this theorem the two next corollaries.

Corollary 20. The pair (𝒦 (ℚ), 𝒦 ^{∗}(ℚ)) of coanalytic subsets of 𝒦 (2^{ω}) is complete.

Corollary 21. The pair (𝒦 (ℚ), 𝒦_{ω}(2^{ω})\𝒦 (ℚ)) of coanalytic subsets of 𝒦 (2^{ω}) is complete.

We give one more example of complete disjoint pair of coanalytic subsets.

Theorem 22. The pair (WF, WF^{∗}) of coanalytic subsets of 𝒯 is complete.

Proof. Let X be a closed subset of ω^{ω} and (C_{0}, C_{1}) a disjoint pair of coanalytic subsets of X. Let C = C_{0} ∪ C_{1} and g : C → {0, 1} be the bianalytic function defined by g(x) = 0 ⟺ x ∈ C_{0}. By Lemma 15 there exists a Δ_{1}^{1} function h : C → ω^{ω} such that the graph G of g × h is closed in C × {0, 1} × ω^{ω}. Then for x ∈ C, a ∈ {0, 1} and α ∈ ω^{ω} we have

(x, a, α) ∈ \overline{G} ⟺ a = g(x) and α = h(x)

Then define F′ := \{(x, α) ∈ X × ω^{ω} : (x, 1, α) ∈ \overline{G}\}. Clearly F′ is closed in X × ω^{ω} and we have C_{0} ∩ π(F′) = ∅ and C_{1} ⊂ U(F′). Since C is coanalytic there exists a closed subset H of X × ω^{ω} such that π(H) = X \ C. Then H × ω^{ω} is a closed subset of (X × ω^{ω}) × ω^{ω} ≃ X × (ω^{ω} × ω^{ω}) ≃ X × ω^{ω}. Thus there exists a closed subset F′′ of X × ω^{ω} such that π(F′′) = X \ C and that the fiber F′′(x) is uncountable for x ∉ C.

The closed subset F = F′ ∪ F′′ of X × ω^{ω} satisfies then F (x) = ∅ if x ∈ C_{0}, F (x) is a singleton if x ∈ C_{1} and F (x) is uncountable if x ∈ X \ C. Let T be a tree on ω × ω such that ⌈T ⌉ = F ⊂ X × ω^{ω} ⊂ ω^{ω} × ω^{ω}. Define a continuous mapping from X to 𝒯 by :

T (x) = {s ∈ Seq : ∃t ≺ x |t| = |s| and (t, s) ∈ T } .

It is easily checked that the set ⌈T (x)⌉ of infinite branches of the tree T (x) is equal to the fiber F (x). So T (x) ∈ WF if x ∈ C_{0}, T (x) ∈ WF^{∗} if x ∈ C_{1} and T (x) ∉ WF ∪ WF^{∗} if x ∉ C. And this shows that the mapping x ↦ T (x) is a continuous reduction of the pair (C_{0}, C_{1}) to the pair (WF, WF^{∗}).

It follows that the pair (WF, WF^{∗}) is complete. □

6. Complete sequences of coanalytic sets

More generally one can consider disjoint sequences of coanalytic sets instead disjoint pairs. We will say that the sequence (C_{n}) of pairwise disjoint coanalytic subsets of the Polish space Y is complete if for every Polish zero-dimensional space X and every sequence (D_{n}) of pairwise disjoint coanalytic subsets of X there exists a continuous function f : X → Y such that D_{n} = f^{−1}(C_{n}) for all n.

For every n ∈ ω we denote by WF^{(n)} the set of trees on ω having exactly n infinite branches. So WF^{(0)} = WF and WF^{(1)} = WF^{∗}. We intend to prove that the sequence (WF^{(n)})_{n∈ω} is complete.

Lemma 23. Let Y and Z be Polish spaces, and X be a Borel subset of Y × Z. Then, for every integer n, the set U_{n}(X) of points y ∈ Y such that the fiber X(y) has exactly n points in Z is coanalytic.

Proof. This is already proved for n = 0 and n = 1. Let (W_{k}) be a countable basis of the topology of Z, and

D_{n} = {(k_{0}, k_{1}, … k_{n−1}) ∈ ω^{n} : W_{k_{i}} ∩ W_{k_{j}} = ∅ for 0 ≤ i < j < n}

Let π : Y × Z → Y denote the first projection. Define for all k the coanalytic set E_{k} by E_{k} := U(X ∩ (Y × W_{k})) and for (k_{0}, k_{1}, … k_{n−1}) ∈ D_{n} the analytic set A_{(k_{0},k_{1},...k_{n−1})} by

A_{(k_{0},k_{1},...k_{n−1})} = π(X ∩ (Y × (Z \ ⋃_{j<n} W_{k_{j}})))

It is clear that a point y lies in U_{n}(X) if and only if there are n pairwise disjoint open sets (V_{0}, V_{1}, …, V_{n−1}) such that X(y) contains exactly one point in each V_{j} and no point outside ⋃_{j<n} V_{j}. So

U_{n}(X) = ⋃_{(k_{0},k_{1},...,k_{n−1})∈D_{n}}(⋂_{j<n} E_{k_{j}} \ A_{(k_{0},k_{1},...,k_{n−1})})

and this shows that U_{n}(X) ∈ Π_{1}^{1}. □

Lemma 24. For all integer n, WF^{(n)} is a coanalytic subset of 𝒯 .

Proof. Let X be the set {(T, α) ∈ 𝒯 ×ω^{ω} : α ∈ ⌈T ⌉}. Then X is closed in 𝒯 ×ω^{ω} and WF^{(n)} = U_{n}(X) for all n ∈ ω. So the conclusion follows immediately from Lemma 23. □

Lemma 25. Let X be a Polish space and (C_{n}) be a sequence of pairwise disjoint coanalytic subsets of X. Then there exists a closed subset F of X × ω^{ω} such that C_{n} = U_{n}(X) for all integer n.

Proof. Consider the bianalytic function g defined on the coanalytic set C = ⋃_{n} C_{n} by g(x) = n ⟺ x ∈ C_{n}. By Theorem 16 there is a bianalytic function h : C → ω^{ω} such that the graph G of g × h is closed in C × ω × ω^{ω}. Then \overline{G} is closed in X × ω × ω^{ω} and we have \overline{G}(x) = \{(n, h(x))\} for every x ∈ C_{n}. As in the proof of Theorem 22 we can find a closed subset F′ of X × (ω × ω^{ω}) such that F′(x) = ∅ for x ∈ C and F′(x) is uncountable for x ∉ C.

Then we define F ⊂ X × (ω × ω^{ω}) ≃ X × ω^{ω} by

(x, m, α) ∈ F ⟺ ((x, m, α) ∈ F′) or (∃n n ≤ m < 2n and (x, n, α) ∈ \overline{G})

It is easily checked that F is closed, that F (x) ⊃ F′(x) is uncountable for x ∉ C and that, for x ∈ C_{n}, F (x) = {(m, h(x)) : n ≤ m < 2n} hence has exactly n points. Thus U_{n}(X) = C_{n}. □

Theorem 26. The sequence (WF^{(n)})_{n∈ω} of pairwise disjoint coanalytic subsets of 𝒯 is complete.

Proof. Let X be a closed subset of ω^{ω} and (C_{n}) a sequence of pairwise disjoint coanalytic subsets of X. By Lemma 25 there is a closed subset F of X × ω^{ω}, hence of ω^{ω} × ω^{ω}, such that U_{n}(F) = C_{n} for all n. Let T be a tree on ω × ω such that F = ⌈T ⌉. Then we define a continuous mapping from X to 𝒯 by :

T (x) = {s ∈ Seq : ∃t ≺ x : (t, s) ∈ T and |s| = |t|} .

Since ⌈T (x)⌉ = F (x) for all x ∈ X we have x ∈ C_{n} ⟺ T (x) ∈ WF^{(n)} for all n. Thus the mapping x ↦ T (x) is a continuous reduction of the sequence (C_{n}) to the sequence (WF^{(n)}).

And since X and the sequence (C_{n}) are arbitrary this shows that the sequence (WF^{(n)}) is complete. □

References

1. G. Debs and J. Saint Raymond, Borel liftings of Borel sets : some decidable and undecidable statements, to appear in Memoirs of the Amer. Math. Soc. (2007) (preprint available at

www.institut.math.jussieu.fr/˜ raymond/preprints/treerep.pdf)

2. C. Dellacherie, Ensembles analytiques : théorèmes de séparation et applications, Séminaire de Probabilités IX, université de Strasbourg, Lecture notes in Mathematics 465.

3. L. Harrington, Analytic Determinacy and 0^{♯}, J. Symbolic Logic 43 (1978), 685–693

4. A. Kechris, Classical Descriptive Set Theory, (Springer-Verlag, New York, 1995)

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

Analyse Fonctionnelle, Institut de Mathématique de Jussieu, Boîte 186, 4, place Jussieu, 75252 Paris CEDEX 05

  E-mail address: jsr@ccr.jussieu.fr