Dominique Lecomte
email: dominique.lecomte@upmc.fr

Miroslav Zeleny
email: zeleny@karlin.mff.cuni.cz

Baire-class ξ colorings: the first three levels

Keywords: 2010 Mathematics Subject Classification. Primary: 03E15, Secondary: 54H05 Borel chromatic number, Borel class, coloring, dichotomy, Hurewicz, partition, product

The G 0 -dichotomy due to Kechris, Solecki and Todorčević characterizes the analytic relations having a Borel-measurable countable coloring. We give a version of the G 0 -dichotomy for Σ 0 ξ -measurable countable colorings when ξ ≤ 3. A Σ 0 ξ -measurable countable coloring gives a covering of the diagonal consisting of countably many Σ 0 ξ squares. This leads to the study of countable unions of Σ 0 ξ rectangles. We also give a Hurewicz-like dichotomy for such countable unions when ξ ≤ 2.

Introduction

The reader should see [K] for the standard descriptive set theoretic notation used in this paper. We study a definable coloring problem. We will need some more notation:

Notation. The letters X, Y will refer to some sets. We set ∆(X) := {(x 0 , x 1 ) ∈ X 2 | x 0 = x 1 }. Definition 1.1 (1) Let A ⊆ X 2 . We say that A is a digraph if A does not meet ∆(X).

(2) Let A be a digraph. A countable coloring of (X, A) is a map c : X → ω such that A does not meet (c×c) -1 ∆(ω) .

In [K-S-T], the authors characterize the analytic digraphs of having a Borel countable coloring. The characterization is given in terms of the following notion of comparison between relations.

Notation. Let X, Y be Polish spaces, A (resp., B) be a relation on X (resp., Y ), and Γ be a class of sets. We set

(X, A) Γ (Y, B) ⇔ ∃f : X → Y Γ-measurable with A ⊆ (f ×f ) -1 (B).
In this case, we say that f is a Γ-measurable homomorphism from (X, A) into (Y, B). This notion essentially makes sense for digraphs (we can take f to be constant if B is not a digraph).

We also have to introduce a minimum digraph without Borel countable coloring:

• Let ψ : ω → 2 <ω be a natural bijection. More specifically, ψ(0) := ∅ is the sequence of length 0, ψ(1) := 0, ψ(2) := 1 are the sequences of length 1, and so on. Note that |ψ(n)| ≤ n if n ∈ ω. Let n ∈ ω. As |ψ(n)| ≤ n, we can define s n := ψ(n)0 n-|ψ(n)| . The crucial properties of the sequence (s n ) n∈ω are the following:

-(s n ) n∈ω is dense in 2 <ω . This means that for each s ∈ 2 <ω , there is n ∈ ω such that s n extends s (denoted s ⊆ s n ).

-|s n | = n.

• We put G 0 := {(s n 0γ, s n 1γ) | n ∈ ω and γ ∈ 2 ω } ⊆ 2 ω × 2 ω . Note that G 0 is analytic (in fact difference of two closed sets) since the map (n, γ) → (s n 0γ, s n 1γ) is continuous.

The previous definitions were given, when Γ = ∆ 1 1 , in [K-S-T], where the following is proved:

Theorem 1.2 (Kechris, Solecki, Todorčević) Let X be a Polish space, and A be an analytic relation on X. Then exactly one of the following holds: (a) There is a Borel countable coloring of (X, A), i.e., (X, A) ∆ 1 1 ω, ¬∆(ω) , (b) (2 ω , G 0 ) Σ 0 1 (X, A). This result had several developments during the last decade. Here is a non-exhaustive list:

-We can characterize the potentially open sets via a Hurewicz-like test, and in finite dimension it is a consequence of the previous result. Let us specify this. The following definition can be found in [START_REF] Louveau | Ensembles analytiques et boréliens dans les espaces produit[END_REF] (see Definition 3.3).

Definition 1.3 (Louveau) Let X, Y be Polish spaces, A be a Borel subset of X×Y , and Γ be a Borel class. We say that A is potentially in Γ denoted A ∈ pot(Γ) if we can find a finer Polish topology σ (resp., τ ) on X (resp., Y ) such that A ∈ Γ (X, σ)×(Y, τ ) .

The pot(Σ 0 1 ) sets are the countable unions of Borel rectangles. A consequence of this is that the Borel hierarchy built on the Borel rectangles is exactly the hierarchy of the classes of the sets potentially in some Borel class. The good notion of comparison to study the pot(Γ) sets is as follows (see [L3]). Let X 0 , X 1 , Y 0 , Y 1 be Polish spaces, and A ε 0 , A ε 1 ⊆ X ε ×Y ε be disjoint. We set

(X 0 , Y 0 , A 0 0 , A 0 1 ) ≤ (X 1 , Y 1 , A 1 0 , A 1 1 ) ⇔ ∃f : X 0 → X 1 ∃g : Y 0 → Y 1 continuous with A 0 ε ⊆ (f ×g) -1 (A 1 ε ) for each ε ∈ 2.
The following theorem is proved in [L1], and is a consequence of Theorem 1.2:

Theorem 1.4 Let X, Y be Polish spaces, and A 0 , A 1 be disjoint analytic subsets of X × Y . Then exactly one of the following holds: (a) The set A 0 can be separated from A 1 by a pot(Σ 0 1 ) = (∆ 1 1 ×∆ 1 1 ) σ set (i.e., there is S ∈ pot(Σ 0 1 ) with A 0 ⊆ S ⊆ ¬A 1 ), (b) 2 ω , 2 ω , ∆(2 ω ), G 0 ≤ (X, Y, A 0 , A 1 ).

In [L1], it is also proved that we cannot have f one-to-one in Theorem 1.2.(b) in general. It is easy to check that Theorem 1.2 is also an easy consequence of Theorem 1.4. This means that the study of the Borel countable colorings is highly related to the study of countable unions of Borel rectangles.

-We can extend Theorem 1.2 to any finite dimension, and also in infinite dimension if we change the space in which lives the infinite dimensional version of G 0 (see [L2]).

-B. Miller recently developped some techniques to recover many dichotomy results of descriptive set theory, but without using effective descriptive set theory. He replaces it with some versions of Theorem 1.2. In particular, he can prove Theorem 1.2 without effective descriptive set theory.

When A is Borel, it is natural to ask about the relation between the Borel class of A and that of the coloring f when Theorem 1.2.(a) holds. This leads to consider ∆ 0 ξ -measurable countable colorings (or equivalently Σ 0 ξ -measurable countable colorings). We have the following conjecture:

Conjecture 1 Let 1 ≤ ξ < ω 1 . Then there are -a 0-dimensional Polish space X ξ , -an analytic relation A ξ on X ξ such that for any 0-dimensional Polish space X, and for any analytic relation A on X, exactly one of the following holds: A). We will prove it when 1 ≤ ξ ≤ 2, and in these cases we do not have to assume that A is analytic. We will also prove it when ξ = 3, which is much more difficult. We should not have to assume that X is 0-dimensional when ξ ≥ 2, but we have to do it when ξ = 1.

(a) (X, A) ∆ 0 ξ ω, ¬∆(ω) , (b) (X ξ , A ξ ) Σ 0 1 (X,
We saw that the study of the Borel countable colorings is highly related to the study of countable unions of Borel rectangles, and gave some motivation for studying Σ 0 ξ -measurable countable colorings. This motivates the study of countable unions of Σ 0 ξ rectangles. Another motivation is that (X, A) ∆ 0 ξ ω, ¬∆(ω) is equivalent to the fact that ∆(X) can be separated from A by a (Σ 0 ξ ×Σ 0 ξ ) σ set, by the generalized reduction property for the class Σ 0 ξ (see 22.16 in [K]).

Conjecture 2 Let 1 ≤ ξ < ω 1 . Then there are 0-dimensional Polish spaces X 0 ξ , X 1 ξ and disjoint analytic subsets A 0 ξ , A 1 ξ of X 0 ξ ×X 1 ξ such that for any Polish spaces X, Y , and for any pair A 0 , A 1 of disjoint analytic subsets of X ×Y , exactly one of the following holds:

(a) The set A 0 can be separated from A 1 by a (Σ 0 ξ ×Σ 0 ξ ) σ set, (b) (X 0 ξ , X 1 ξ , A 0 ξ , A 1 ξ ) ≤ (X, Y, A 0 , A 1 ).
It is trivial to prove this when ξ = 1. We will prove that Conjecture 2 holds when ξ ≤ 2, which is significantly more and more difficult when ξ increases. We use effective descriptive set theory, and give effective strengthenings of our results. The reader should see [M] for basic notions of effective descriptive set theory. In particular, we will see that to test whether an analytic relation has a Σ 0 ξmeasurable countable coloring, it is enough to test countably many partitions instead of continuum many. We will use the topology T ξ generated by the Σ 1 1 ∩ Π 0 <ξ subsets of a recursively presented Polish space (introduced in [Lo1]) when ξ is 2 or 3 (T 1 is just the basic topology). The last result can be strengthened as follows (see [L3]).

Theorem 1.5 Let 1 ≤ ξ ≤ 2. Then there are 0-dimensional Polish spaces X 0 ξ , X 1 ξ and disjoint analytic subsets A 0 ξ , A 1 ξ of X 0 ξ × X 1
ξ such that for any recursively presented Polish spaces X, Y , and for any pair A 0 , A 1 of disjoint Σ 1 1 subsets of X ×Y , the following are equivalent: (a) The set A 0 cannot be separated from A 1 by a

(Σ 0 ξ ×Σ 0 ξ ) σ set. (b) The set A 0 cannot be separated from A 1 by a ∆ 1 1 ∩ (Σ 0 ξ ×Σ 0 ξ ) σ set. (c) The set A 0 cannot be separated from A 1 by a Σ 0 1 (T ξ ×T ξ ) set. (d) A 0 ∩ A 1 T ξ ×T ξ = ∅. (e) (X 0 ξ , X 1 ξ , A 0 ξ , A 1 ξ ) ≤ (X, Y, A 0 , A 1 ).

Some general effective facts

One can hope for an effective strengthening of Conjecture 1:

Effective conjecture 1 Let 1 ≤ ξ < ω 1 .
We can find a 0-dimensional Polish space X ξ and an analytic relation

A ξ on X ξ such that (X ξ , A ξ ) ∆ 0 ξ ω, ¬∆(ω)
, and for any α ∈ ω ω with 1 ≤ ξ < ω α 1 , for any 0-dimensional recursively in α presented Polish space X, and for any Σ 1 1 (α) relation A on X, one of the following holds:

(a) (X, A) ∆ 1 1 (α)∩∆ 0 ξ ω, ¬∆(ω) , (b) (X ξ , A ξ ) Σ 0 1 (X, A).
We will see that this effective conjecture is true when 1 ≤ ξ ≤ 3. The following statement is a corollary of this effective conjecture, and is in fact a theorem:

Theorem 2.1 Let 1 ≤ ξ < ω CK
1 , X be a 0-dimensional recursively presented Polish space, and A be a Σ 1 1 relation on X. We assume that (X, A)

∆ 0 ξ ω, ¬∆(ω) . Then (X, A) ∆ 1 1 ∩∆ 0 ξ ω, ¬∆(ω) .
A consequence of this is that to test whether an analytic relation has a Σ 0 ξ -measurable countable coloring, it is enough to test countably many partitions instead of continuum many. Another consequence is the equivalence between Conjecture 1 and the Effective conjecture 1. We have in fact preliminary results that will help us to prove also the equivalence between (a)-(d) in Theorem 1.5, in the general case.

Lemma 2.2 Let 1 ≤ ξ < ω CK 1 , X, Y be recursively presented Polish spaces, A ∈ Σ 1 1 (X) ∩ Σ 0 ξ , B ∈ Σ 1 1 (Y ) ∩ Σ 0 ξ , and C ∈ Σ 1 1 (X ×Y ) disjoint from A×B. Then there are A ′ , B ′ ∈ ∆ 1 1 ∩ Σ 0 ξ such that A ′ ×B ′ separates A×B from C. This also holds for Π 0 ξ instead of Σ 0 ξ .
Proof. Note that A and {x ∈ X | ∃y ∈ B (x, y) ∈ C} are disjoint Σ 1 1 sets, separable by a Σ 0 ξ subset of X. By Theorems 1.A and 1.B in [START_REF] Louveau | A separation theorem for Σ 1 1 sets[END_REF], there is A ′ ∈ ∆ 1 1 ∩ Σ 0 ξ separating these two sets. Similarly, B and {y ∈ Y | ∃x ∈ A ′ (x, y) ∈ C} are disjoint Σ 1 1 sets, and there is B ′ ∈ ∆ 1 1 ∩ Σ 0 ξ separating these two sets. The proof for Π 0 ξ is identical to the one for Σ 0 ξ .

Theorem 2.3 Let 1 ≤ ξ < ω CK 1 , X, Y be recursively presented Polish spaces, and

A 0 , A 1 be disjoint Σ 1 1 subsets of X × Y . We assume that A 0 is separable from A 1 by a Σ 0 ξ × Σ 0 ξ σ set. Then A 0 is separable from A 1 by a ∆ 1 1 ∩ (∆ 1 1 ∩ Σ 0 ξ )×(∆ 1 1 ∩ Σ 0 ξ ) σ set.
Proof. By Example 2 of Chapter 3 in [START_REF] Louveau | Ensembles analytiques et boréliens dans les espaces produit[END_REF], the family N (n, X) n∈ω is regular without parameter. By Corollary 2.10 in [START_REF] Louveau | Ensembles analytiques et boréliens dans les espaces produit[END_REF], Π 0 ξ (X), as well as Σ 0 ξ (X) = η<ξ Π 0 η (X) σ , are regular without parameter. By Theorem 2.12 in [START_REF] Louveau | Ensembles analytiques et boréliens dans les espaces produit[END_REF], Σ 0 ξ (X)×Σ 0 ξ (Y ) is also regular without parameter. By Theorem 2.8 in [START_REF] Louveau | Ensembles analytiques et boréliens dans les espaces produit[END_REF], the family Φ := Σ 0 ξ (X) × Σ 0 ξ (Y ) σ is separating, which implies the existence of

S ∈ ∆ 1 1 ∩ Φ separating A 0 from A 1 .
With the notation of [START_REF] Louveau | Ensembles analytiques et boréliens dans les espaces produit[END_REF], let n be an integer with (0

∞ , n) ∈ W and C 0 ∞ ,n = S. Then (0 ∞ , n) is in W Φ , which by Theorem 2.8.(ii) in [Lo2] is (α, n) ∈ W | ∃β ∈ ∆ 1 1 (α) ∀m ∈ ω α, β(m) ∈ W Σ 0 ξ (X)×Σ 0 ξ (Y ) and C α,n = m∈ω C α,β(m) . This implies that S ∈ ∆ 1 1 ∩ ∆ 1 1 ∩ (Σ 0 ξ ×Σ 0 ξ ) σ . It remains to check that ∆ 1 1 ∩ (Σ 0 ξ ×Σ 0 ξ ) = (∆ 1 1 ∩ Σ 0 ξ )×(∆ 1 1 ∩ Σ 0 ξ ).
The second set is clearly a subset of the first one. So assume that R = A×B ∈ ∆ 1 1 ∩ (Σ 0 ξ ×Σ 0 ξ ). We may assume that R is not empty. Then the projections A, B are

Σ 1 1 since R ∈ ∆ 1 1 . Lemma 2.2 gives A ′ , B ′ ∈ ∆ 1 1 ∩ Σ 0 ξ with A×B ⊆ A ′ ×B ′ ⊆ R = A×B. Recall that if A is a relation on X and D ⊆ X, then D is A-discrete if A ∩ D 2 = ∅.
Proof of Theorem 2.1. We apply Theorem 2.3 to Y := X, A 0 := ∆(X) and

A 1 := A. As (X, A) ∆ 0 ξ ω, ¬∆(ω) , ∆(X) is separable from A by a (Σ 0 ξ × Σ 0 ξ ) σ set. Theorem 2.3 gives C n , D n ∈ ∆ 1 1 ∩ Σ 0 ξ such that S := n∈ω C n ×D n ∈ ∆ 1 1 separates ∆(X) from A.
As the set of codes for ∆ 1 1 ∩ Σ 0 ξ subsets of X is Π 1 1 (see Proposition 1.4 and Theorem 1.A in [START_REF] Louveau | A separation theorem for Σ 1 1 sets[END_REF]), the ∆ 1 1 -selection theorem and the separation theorem imply that we may assume that the sequences (C n ) and

(D n ) are ∆ 1 1 . Note that (C n ∩ D n ) is a ∆ 1 1 covering of X into A-discrete ∆ 1 1 ∩ Σ 0 ξ sets.
As X is 0-dimensional we can reduce this covering into a ∆ 1 1 covering of X consisting of ∆ 1 1 ∩ Σ 0 ξ sets, which are in fact ∆ 0 ξ . This gives the desired partition.

Notation. Following [START_REF] Louveau | A separation theorem for Σ 1 1 sets[END_REF], we define the following topologies on a 0-dimensional recursively in α presented Polish space X, for any α ∈ ω ω . Let T 1 (α) be the topology of X, and, for 2 ≤ ξ < ω 1 , T ξ (α) be the topology generated by the Σ 1 1 (α) ∩ Π 0 <ξ subsets of X. The next proposition gives a reformulation of the inequality (X,

A) ∆ 1 1 (α)∩∆ 0 ξ ω, ¬∆(ω) of the Effective conjecture 1. Proposition 2.4 Let 1 ≤ ξ < ω CK 1 , X be a 0-dimensional recursively presented Polish space, and A be a Σ 1 1 relation on X. Then (X, A) ∆ 1 1 ∩∆ 0 ξ ω, ¬∆(ω) is equivalent to ∆(X) ∩ A T ξ ×T ξ = ∅. Proof. Assume first that (X, A) ∆ 1 1 ∩∆ 0 ξ ω, ¬∆(ω) . Then there is a partition (B n ) of X into A-discrete ∆ 1 1 ∩ ∆ 0 ξ sets. In particular, Theorem 1.A in [Lo1] implies that B n is a countable union of ∆ 1 1 ∩ Π 0 <ξ sets if ξ ≥ 2. In particular, B n is T ξ -open and ∆(X) is disjoint from A T ξ ×T ξ (even if ξ = 1). Conversely, assume that ∆(X) ∩ A T ξ ×T ξ = ∅. Then each element x of X is contained in a A- discrete Σ 1 1 ∩ Π 0 <ξ set (basic clopen set if ξ = 1). Lemma 2.2 implies that each element x of X is in fact contained in a A-discrete ∆ 1 1 ∩ Π 0 <ξ set if ξ ≥ 2.
It remains to apply Proposition 1.4 in [START_REF] Louveau | A separation theorem for Σ 1 1 sets[END_REF] and the ∆ 1 1 -selection theorem to get the desired partition.

One can also hope for an effective strengthening of Conjecture 2 generalizing Theorem 1.5:

Effective conjecture 2 Let 1 ≤ ξ < ω 1 . Then there are -0-dimensional Polish spaces X 0 ξ , X 1 ξ , -disjoint analytic subsets A 0 ξ , A 1 ξ of the space X 0 ξ ×X 1 ξ , not separable by a (Σ 0 ξ × Σ 0 ξ ) σ set, such that for any α ∈ ω ω such that 1 ≤ ξ < ω α
1 , for any recursively in α presented Polish spaces X, Y , and for any pair

A 0 , A 1 of disjoint Σ 1 1 (α) subsets of X ×Y , the following are equivalent: (a) The set A 0 cannot be separated from A 1 by a (Σ 0 ξ ×Σ 0 ξ ) σ set. (b) The set A 0 cannot be separated from A 1 by a ∆ 1 1 (α) ∩ (Σ 0 ξ ×Σ 0 ξ ) σ set. (c) The set A 0 cannot be separated from A 1 by a Σ 0 1 T ξ (α)×T ξ (α) set. (d) A 0 ∩ A 1 T ξ (α)×T ξ (α) = ∅. (e) (X 0 ξ , X 1 ξ , A 0 ξ , A 1 ξ ) ≤ (X, Y, A 0 , A 1 ).
In fact, the statements (a)-(d) are indeed equivalent:

Theorem 2.5 Let 1 ≤ ξ < ω CK 1 , X, Y be recursively presented Polish spaces, and A 0 , A 1 be disjoint Σ 1 1 subsets of X ×Y . The following are equivalent: (a) The set A 0 cannot be separated from A 1 by a

(Σ 0 ξ ×Σ 0 ξ ) σ set. (b) The set A 0 cannot be separated from A 1 by a ∆ 1 1 ∩ (Σ 0 ξ ×Σ 0 ξ ) σ set. (c) The set A 0 cannot be separated from A 1 by a Σ 0 1 (T ξ ×T ξ ) set. (d) A 0 ∩ A 1 T ξ ×T ξ = ∅.
Proof. Theorem 2.3 implies that (a) is indeed equivalent to (b). It also implies, using the proof of Proposition 2.4, that (c) implies (a), and the converse is clear. It is also clear that (c) and (d) are equivalent.

A consequence of this is that Conjecture 2 and the Effective conjecture 2 are equivalent.

The case ξ = 1 (A) Continuous colorings

As in [L3], we can separate Conjecture 1 in two parts. We introduce the following notion, that will help us to characterize the relations A for which there is a continuous homomorphism from A into any relation without countable continuous coloring:

Definition 3.1 Let ξ be a countable ordinal, Π 0 0 := ∆ 0 1 , and X be a 0-dimensional Polish space. A family F of subsets of X is ξ-disjoint if the elements of F are Π 0
ξ and pairwise disjoint.

The first part ensures the existence of complicated examples.

Lemma 3.2 (a) Assume that (C ε i ) (ε,i)∈2×ω is a 0-disjoint family of subsets of the space X such that X\( (ε,i)∈2×ω C ε i ) = ∅ and no clopen set meeting X\( (ε,i)∈2×ω C ε i ) is ( i∈ω C 0 i ×C 1 i )-discrete. Then (X, i∈ω C 0 i ×C 1 i ) ∆ 0 1 ω, ¬∆(ω) . (b) There is a 0-disjoint family (C ε i ) (ε,i)∈2×ω
of subsets of 2 ω satisfying the assumption (and thus the conclusion) of (a).

Proof. (a) We argue by contradiction, which gives

f : X → ω continuous such that f (x) = f (y) if (x, y) ∈ i∈ω C 0 i × C 1 i . We set D k := f -1 ({k}), so that (D k ) k∈ω is a partition of X into clopen sets discrete for i∈ω C 0 i × C 1 i . Choose z ∈ X \ ( (ε,i)∈2×ω C ε i ), and k with z ∈ D k . This gives (x, y) ∈ ( i∈ω C 0 i ×C 1 i ) ∩ D 2 k , which is absurd. (b) We set C ε i := N 0 2i+ε 1 , so that i∈ω C 0 i ×C 1 i = {(0 2i 1α, 0 2i+1 1β) | i ∈ ω and α, β ∈ 2 ω }. Note that {0 ∞ } = X\( (ε,i)∈2×ω C ε i ). If C is a clopen neighborhood of 0 ∞ , then N 0 i ⊆ C if i is big enough. This gives an integer i with (0 2i 1 ∞ , 0 2i+1 1 ∞ ) ∈ ( i∈ω C 0 i ×C 1 i ) ∩ C 2 .
The second part ensures the existence of the continuous homomorphism.

Lemma 3.3 Let X be a 0-dimensional Polish space, (C ε i ) (ε,i)∈2×ω be a 0-disjoint family of subsets of X, X be a 0-dimensional Polish space, and A be a relation on X. Then one of the following holds:

(a) (X, A) ∆ 0 1 ω, ¬∆(ω) , (b) (X, i∈ω C 0 i ×C 1 i ) Σ 0 1 (X, A).
Proof. Assume that (a) does not hold. Let us fix a compatible complete metric on X. In the sequel, the diameter will refer to this metric (this will also be the case in all the proofs where diameters are involved to come). We enumerate a basis N (p, X) p∈ω for the topology of X made of clopen sets.

• We build -an increasing sequence of integers (p i ) i∈ω , -a sequence (x k ) k∈ω of points of X.

We want these objects to satisfy the following conditions:

(1) (x 2i , x 2i+1 ) ∈ A ∩ N (p i , X) 2 (2) N (p i+1 , X) ⊆ N (p i , X) (3) diam N (p i , X) ≤ 2 -i (4) There is no covering of N (p i , X) consisting of A-discrete clopen subsets of X
• Assume that this is done. Then we can define a point x of X by {x} = i∈ω N (p i , X). Note that

(x k ) k∈ω tends to x. We define f : X → X by f (z) := x if z / ∈ (ε,i)∈2×ω C ε i , f (z) := x 2i+ε if z ∈ C ε i . Note that f is continuous. Moreover, f (y), f (z) = (x 2i , x 2i+1 ) ∈ A if (y, z) ∈ C 0 i ×C 1 i , so that (b) holds.
• Let us prove that the construction is possible. We set N (p -1 , X) := X. Assume that (p i ) i<l and (x 2i , x 2i+1 ) i<l satisfying (1)-(4) have been constructed, which is the case for l = 0. We choose a covering of N (p l-1 , X) with basic clopen sets of diameter at most 2 -l , contained in N (p l-1 , X). Then one of these basic sets, say N (p l , X), satisfies (4). It remains to choose (x 2l , x 2l+1 ) in the set A ∩ N (p l , X) 2 .

We set X 1 := 2 ω and A

1 := {(0 2i 1α, 0 2i+1 1β) | i ∈ ω and α, β ∈ 2 ω } = i∈ω C 0 i ×C 1 i , so that A 1 is a Σ 0 1 relation on X 1 .
Corollary 3.4 Let X be a 0-dimensional Polish space, and A be a relation on X. Then exactly one of the following holds:

(a) (X, A) ∆ 0 1 ω, ¬∆(ω) , (b) (X 1 , A 1 ) Σ 0 1 (X, A).
Moreover, there are a non 0-dimensional Polish space X, and a closed relation A on X, for which neither (a), nor (b) holds (with this couple (X 1 , A 1 ) or any other). There are also a 0-dimensional Polish space X, and a relation A on X (a difference of two closed sets), for which it is not possible to have f one-to-one in (b) (with this couple (X 1 , A 1 ) or any other).

Proof. Note first that (a) and (b) cannot hold simultaneously, by Lemma 3.2. Lemma 3.3 implies that (a) or (b) holds.

• Consider now X := R and A := {(0, 1)}. Then (a) does not hold since R is connected. If (b) holds, then we must have f (0 2i 1α) = 0 and f (0 2i+1 1β) = 1. By continuity of f , we get f (0 ∞ ) = 0 = 1.

This would be the same with any (X 1 , A 1 ). Indeed, as (X 1 , A 1 ) ∆ 0 1 ω, ¬∆(ω) , we have

Π 0 [A 1 ] ∩ Π 1 [A 1 ] = ∅, since otherwise there would be a clopen subset C of the 0-dimensional space X 1 separating Π 0 [A 1 ] from Π 1 [A 1 ], and we would have ∆(X 1 ) ⊆ C 2 ∪ (¬C) 2 ⊆ ¬A 1 . So we can choose x ∈ Π 0 [A 1 ] ∩ Π 1 [A 1 ], x 2i ∈ Π 0 [A 1 ] such that (x 2i ) tends to x, y 2i+1 ∈ Π 1 [A 1 ] such that (y 2i+1 )
tends to x, y 2i with (x 2i , y 2i ) ∈ A 1 , and x 2i+1 with (x 2i+1 , y 2i+1 ) ∈ A 1 . Then f (x 2i ) = 0, f (y 2i+1 ) = 1 and we conclude as before.

• Consider X := 2 ω and A := {0 ∞ }×(2 ω \{0 ∞ }). Then (a) does not hold since if a clopen subset C of 2 ω contains 0 ∞ , then it contains also some α = 0 ∞ , so that (0 ∞ , α) ∈ A ∩ C 2 . If (b) holds, then f (0 2i 1α) = 0 ∞ for each integer i and f is not one-to-one.
This argument works as soon as Π 0 [A 1 ] has at least two elements. If we argue in the other factor, then we see that an example (X 1 , A 1 ) with injectivity must satisfy that A 1 is a singleton {(α, β)}.

As (X 1 , A 1 ) Σ 0 1 (2 ω , G 0 ), α = β. So take a clopen subset C of X 1 containing α but not β. Then ∆(X 1 ) ⊆ C 2 ∪ (¬C) 2 ⊆ ¬A 1 .
The notion of a 0-disjoint family is essential in the following sense: Proposition 3.5 Let X be a 0-dimensional Polish space, and A be a relation on X. The following are equivalent:

(a) For any 0-dimensional Polish space X, and any relation A on X,

(X, A) ∆ 0 1 ω, ¬∆(ω) ⇒ (X, A) Σ 0 1 (X, A). (b) There is a 0-disjoint family (C ε i ) (ε,i)∈2×ω of subsets of X such that A ⊆ i∈ω C 0 i ×C 1 i .
Proof. (a) ⇒ (b) We set X := X 1 and A := A 1 . By Lemma 3.2, we get f :

X → 2 ω such that A ⊆ (f ×f ) -1 (A 1 ). We set C ε i := f -1 (N 0 2i+ε 1 ). (b) ⇒ (a) By Lemma 3.3 we get (X, i∈ω C 0 i ×C 1 i ) Σ 0 1 (X, A), so that (X, A) Σ 0 1 (X, A).

(B) Countable unions of open rectangles (i.e., open sets)

The content here is completely trivial. It is just the fact that a subset of a metric space is not open exactly when it contains a point that we can approximate by a countable sequence contained in its complement. We give some statements since the situation will be more complicated in the case ξ = 2. As in (A) we can characterize the tuples (X 0 , X 1 , A 0 , A 1 ) ≤-below any tuple (X, Y, A 0 , A 1 ) with A 0 not separable from A 1 by a (Σ 0 1 ×Σ 0 1 ) σ set.

Lemma 3.6 (a) Assume that (C ε i ) i∈ω is a 0-disjoint family of subsets of the space X ε such that

X 0 \( i∈ω C 0 i ) × X 1 \( i∈ω C 1 i ) = ∅ and no open set meeting X 0 \( i∈ω C 0 i ) × X 1 \( i∈ω C 1 i ) is disjoint from i∈ω C 0 i × C 1 i . Then X 0 \( i∈ω C 0 i ) × X 1 \( i∈ω C 1 i ) is not separable from i∈ω C 0 i ×C 1 i by a (Σ 0 1 ×Σ 0 1 ) σ set. (b)
There are 0-disjoint families of subsets of 2 ω satisfying the assumption (and thus the conclusion) of (a).

Proof. (a) is obvious.

(b) We set C ε i := N 0 i 1 , so that i∈ω C 0 i × C 1 i = {(0 i 1α, 0 i 1β) | i ∈ ω and α, β ∈ 2 ω }. Note that {0 ∞ } = X ε \( i∈ω C ε i ). If O is an open neighborhood of (0 ∞ , 0 ∞ ), then N 2 0 i ⊆ O if i is big enough. This gives an integer i with (0 i 1 ∞ , 0 i 1 ∞ ) ∈ ( i∈ω C 0 i ×C 1 i ) ∩ O.
Lemma 3.7 Let X 0 , X 1 be 0-dimensional Polish spaces, (C ε i ) i∈ω be a 0-disjoint family of subsets of X ε , X, Y be Polish spaces, and A 0 , A 1 be disjoint subsets of X×Y . Then one of the following holds:

(a) A 0 is separable from A 1 by a (Σ 0 1 ×Σ 0 1 ) σ set, (b) X 0 , X 1 , X 0 \( i∈ω C 0 i ) × X 1 \( i∈ω C 1 i ) , i∈ω C 0 i ×C 1 i ≤ (X, Y, A 0 , A 1 ).
Proof. Assume that (a) does not hold. Pick (x, y) ∈ A 0 ∩ A 1 , and (x i , y i ) in A 1 tending to (x, y). We define f :

X 0 → X by f (z) := x if z / ∈ i∈ω C 0 i , x i if z ∈ C 0 i . Note that f is continuous. Similarly, we define g : X 1 → Y , so that (b) holds. We define X ε 1 := 2 ω , A 0 1 := {(0 ∞ , 0 ∞ )} = X 0 1 \ ( i∈ω C 0 i ) × X 1 1 \ ( i∈ω C 1 i ) and also A 1 1 := {(0 i 1α, 0 i 1β) | i ∈ ω and α, β ∈ 2 ω } = i∈ω C 0 i × C 1 i .
As in (A) we get the two following consequences:

Corollary 3.8 Let X, Y be Polish spaces, and A 0 , A 1 be disjoint subsets of X×Y . Then exactly one of the following holds:

(a) A 0 is separable from A 1 by a (Σ 0 1 ×Σ 0 1 ) σ set, (b) (X 0 1 , X 1 1 , A 0 1 , A 1 1 ) ≤ (X, Y, A 0 , A 1 ).
Proposition 3.9 Let X 0 , X 1 be 0-dimensional Polish spaces, and A 0 , A 1 ⊆ X 0 ×X 1 be disjoint. The following are equivalent:

(a) For any Polish spaces X, Y , and any

A 0 , A 1 ⊆ X ×Y disjoint, A 0 is not separable from A 1 by a (Σ 0 1 ×Σ 0 1 ) σ set ⇒ (X 0 , X 1 , A 0 , A 1 ) ≤ (X, Y, A 0 , A 1 ). (b) There is a 0-disjoint family (C ε i ) i∈ω of subsets of X ε such that the inclusions A 1 ⊆ i∈ω C 0 i ×C 1 i and A 0 ⊆ X 0 \( i∈ω C 0 i ) × X 1 \( i∈ω C 1 i ) hold.
4 The case ξ = 2

(A) Baire class one colorings Lemma 4.1 (a) Assume that (C ε i ) (ε,i)∈2×ω is a 1-disjoint family of subsets of X such that no non- empty clopen subset of X is ( i∈ω C 0 i ×C 1 i )-discrete. Then (X, i∈ω C 0 i ×C 1 i ) ∆ 0 2 ω, ¬∆(ω) . (b) There is a 1-disjoint family (C ε i ) (ε,i)∈2×ω
of subsets of ω ω satisfying the assumption (and thus the conclusion) of (a).

Proof. (a) We argue by contradiction, which gives a ∆ 0 2 -measurable map f :

X → ω with f (x) = f (y) if (x, y) ∈ i∈ω C 0 i ×C 1 i . We set D k := f -1 ({k}), so that (D k ) k∈ω is a partition of X into ∆ 0 2 sets discrete for i∈ω C 0 i ×C 1 i
. By Baire's theorem, there are an integer k and a nonempty clopen subset

C of X such that D k contains C. This gives (x, y) ∈ ( i∈ω C 0 i ×C 1 i ) ∩ C 2 ⊆ ( i∈ω C 0 i ×C 1 i ) ∩ D 2 k , which is absurd. (b) Let b : ω → ω <ω be a bijection. We set C ε i := b(i) 2|b(i)|+ε ∞ , so that i∈ω C 0 i ×C 1 i = u(2|u|) ∞ , u(2|u|+1) ∞ | u ∈ ω <ω . If ∅ = C ∈ ∆ 0 1 (ω ω ), then C contains some basic clopen set N u , and u(2|u|) ∞ , u(2|u|+1) ∞ is in ( i∈ω C 0 i ×C 1 i ) ∩ C 2 .
Remark. There are a 1-disjoint family (C ε i ) (ε,i)∈2×ω of subsets of ω ω , and a relation

A on ω ω such that (ω ω , A) ∆ 0 2 ω, ¬∆(ω) and (ω ω , i∈ω C 0 i ×C 1 i ) Σ 0 1 (ω ω , A
), so that Lemma 3.3 cannot be extended to Σ 0 2 -measurable countable colorings.

Indeed, we set

C ε i := {u(2i+ ε) ∞ | u ∈ ω i } and A := u(2|u|) ∞ , u(2|u|+ 1) ∞ | u ∈ ω <ω . Then (C ε i ) (ε,i)∈2×ω
is clearly a 1-disjoint family. Lemma 4.1 gives the first assertion. For the second assertion, assume, towards a contradiction, that f : ω ω → ω ω is continuous and satisfies the inclusion

i∈ω C 0 i ×C 1 i ⊆ (f ×f ) -1 (A). If i ∈ ω, then there is u i ∈ ω <ω with f [C 0 i ]×f [C 1 i ] ⊆ u i (2|u i |) ∞ , u i (2|u i |+1) ∞ .
In particular, for any α, β ∈ ω ω we get

f (α), f (β) = lim i→∞ f (α|i)(2i) ∞ , f (β|i)(2i+1) ∞ = lim i→∞ u i (2|u i |) ∞ , u i (2|u i |+1) ∞ .
But this implies that f is constant, which is absurd. To fix this, we refine the notion of a ξ-disjoint family.

Definition 4.2 Let 1 ≤ ξ < ω 1 . A ξ-disjoint family (C ε i ) (ε,i)∈2×ω
of subsets of a 0-dimensional Polish space X is said to be comparing if for each integer q there is a partition (O p q ) p∈ω of X into ∆ 0 ξ sets such that, for each i ∈ ω, (a) if q < i, then there is

p i q ∈ ω such that C 0 i ∪ C 1 i ⊆ O p i q q , (b) if q ≥ i and ε ∈ 2, then C ε i ⊆ O 2i+ε q .
Lemma 4.3 There is a comparing 1-disjoint family (C ε i ) (ε,i)∈2×ω of subsets of ω ω satisfying the assumption (and thus the conclusion) of Lemma 4.1.(a).

Proof. Let b : ω → ω <ω be a bijection satisfying b -1 (s) ≤ b -1 (t) if s ⊆ t. It can be built as follows. Let (p q ) q∈ω be the sequence of prime numbers, and I : ω <ω → ω defined by I(s) := p s(0)+1 0 ...p s(|s|-1)+1 |s|-1 if s = ∅, and I(∅) := 1. Note that I is one-to-one, so that there is an increasing bijection ϕ : I[ω <ω ] → ω. We set b := (ϕ • I) -1 : ω → ω <ω . We define (C ε i ) (ε,i)∈2×ω as in the proof of Lemma 4.1.(b), so that

(C ε i ) (ε,i)∈2×ω is a 1-disjoint family. It remains to see that (C ε i ) (ε,i)∈2×ω is comparing. We set O p q :=              N b(i)(2|b(i)|+ε) max l≤q (|b(l)|+1)-|b(i)| if p = 2i+ε ≤ 2q+1, ω ω \( p ′ ≤2q+1 O p ′ q ) if p = 2q+2, ∅ if p ≥ 2q+3, so that (O p q ) p∈ω is a partition of ω ω into ∆ 0 1 sets. Note that (b) is fulfilled. If q < i, then there is at most one couple (j, ε) ∈ (q+1)×2 such that b(j)(2|b(j)| + ε) max l≤q (|b(l)|+1)-|b(j)| is compatible with b(i). If it exists and if |b(i)| ≥ max l≤q (|b(l)| + 1), then C 0 i ∪ C 1 i ⊆ O 2j+ε q
and we set p i q := 2j +ε. Otherwise,

C 0 i ∪ C 1 i ⊆ O 2q+2 q
and we set p i q := 2q+2.

We have a stronger result than Conjecture 1, in the sense that we do not need any regularity assumption on A, neither that X is 0-dimensional. Lemma 4.4 Let X be a 0-dimensional Polish space, (C ε i ) (ε,i)∈2×ω be a comparing 1-disjoint family of subsets of X, X be a Polish space, and A be a relation on X. Then one of the following holds:

(a) (X, A) ∆ 0 2 ω, ¬∆(ω) , (b) (X, i∈ω C 0 i ×C 1 i ) Σ 0 1 (X, A).
Proof. If A is not a digraph, then choose x 0 with (x 0 , x 0 ) ∈ A, and put f (x) := x 0 . So we may assume that A is a digraph. We set

U := V ∈ Σ 0 1 (X) | ∃D ∈ Π 0 1 (ω×X) V ⊆ p∈ω D p and ∀p ∈ ω A ∩ D 2 p = ∅ . Case 1. U = X.
There is a countable covering of X into A-discrete Σ 0 2 sets. We just have to reduce them to get a partition showing that (a) holds.

Case 2. U = X.

Then Y := X \U is a nonempty closed subset of X.

Claim If V ∈ Σ 0 1 (X) meets Y , then V ∩ Y is not A-discrete.
We argue by contradiction. As V ∩ U can be covered with some p∈ω D p 's, so is V . Thus V ⊆ U , so that V ∩ Y ⊆ U \U = ∅, which is the desired contradiction. ⋄

• We construct a family (x u ) u∈ω <ω of points of Y , and a family (X u ) u∈ω <ω of open subsets of Y . We want these objects to satisfy the following conditions:

(1)

x u ∈ X u (2) X up ⊆ X u (3) diam(X u ) ≤ 2 -|u| (4) (x u(2n) , x u(2n+1) ) ∈ A if u ∈ ω n (5) x u(2n+ε) = x u if u / ∈ ω n and ε ∈ 2 • Assume that this is done. We define f : X → Y ⊆ X by {f (x)} := q∈ω X p 0 ...p q-1 = q∈ω X p 0 ...p q-1 ,
where p i satisfies x ∈ O p i i witnessing comparability, so that f is continuous. Note that f (x) is the limit of x p 0 ...p q-1 , and that

x u(2|u|+ε) = x u(2|u|+ε) 2 = ... = x u(2|u|+ε) q+1 for each (u, ε) ∈ ω <ω ×2. Thus f (x) = lim q→∞ x u(2|u|+ε) q+1 = x u(2|u|+ε) if x ∈ C ε i and u := p i 0 ...p i i-1 , and
f (x), f (y) = (x u(2|u|) , x u(2|u|+1) ) ∈ A if (x, y) ∈ C 0 i ×C 1 i . So (b) holds.
• Let us prove that the construction is possible. We choose x ∅ ∈ Y and an open neighborhood X ∅ of x ∅ in Y , of diameter at most 1. Assume that (x u ) u∈ω ≤l and (X u ) u∈ω ≤l satisfying (1)-( 5) have been constructed, which is the case for l = 0.

An application of the claim gives

(x u(2l) , x u(2l+1) ) ∈ A ∩ X 2 u if u ∈ ω l .
We satisfy ( 5), so that the definition of the x u 's is complete. Note that x u ∈ X u|l if u ∈ ω l+1 .

We choose an open neighborhood X u of x u in Y , of diameter at most 2 -l-1 , ensuring the inclusion X u ⊆ X u|l .

We set X 2 := ω ω and A

2 := u(2|u|) ∞ , u(2|u|+1) ∞ | u ∈ ω <ω = i∈ω C 0 i ×C 1 i , so that A 2 is a Σ 0 2 relation on X 2 .
As in Section 3.(A) we get the two following consequences:

Corollary 4.5 Let X be a Polish space, and A be a relation on X. Then exactly one of the following holds: A). Proposition 4.6 Let X be a 0-dimensional Polish space, and A be a relation on X. The following are equivalent: (a) For any Polish space X, and any relation A on X,

(a) (X, A) ∆ 0 2 ω, ¬∆(ω) , (b) (X 2 , A 2 ) Σ 0 1 (X,
(X, A) ∆ 0 2 ω, ¬∆(ω) ⇒ (X, A) Σ 0 1 (X, A). (b) There is a comparing 1-disjoint family (C ε i ) (ε,i)∈2×ω of subsets of X such that A ⊆ i∈ω C 0 i ×C 1 i . (B) Countable unions of Σ 0 2 rectangles Lemma 4.7 (a) Assume that (C ε i ) (ε,i)∈2×ω is a 1-disjoint family of meager subsets of X such that no nonempty clopen subset of X is ( i∈ω C 0 i × C 1 i )-discrete. Then ∆ X \( (ε,i)∈2×ω C ε i ) is not separable from i∈ω C 0 i ×C 1 i by a Σ 0 2 X\( i∈ω C 1 i ) ×Σ 0 2 X\( i∈ω C 0 i ) σ set.
(b) There is a comparing 1-disjoint family (C ε i ) (ε,i)∈2×ω of subsets of ω ω satisfying the assumption (and thus the conclusion) of (a).

Proof. (a) We argue by contradiction, which gives C n ∈ Π 0 1 X \( i∈ω C 1 i ) on one side, and also

D n ∈ Π 0 1 X\( i∈ω C 0 i ) with ∆ X\( (ε,i)∈2×ω C ε i ) ⊆ n∈ω (C n ×D n ) ⊆ ¬( i∈ω C 0 i ×C 1 i ). In particular, X \( (ε,i)∈2×ω C ε i ) = n∈ω C n ∩ D n
, and Baire's theorem gives n and a nonempty clopen subset

C of X such that C \( (ε,i)∈2×ω C ε i ) ⊆ C n ∩ D n . Note that C \( i∈ω C 1 i ) ⊆ C n and C \( i∈ω C 0 i ) ⊆ D n since the C ε i 's are meager and X\( (ε,i)∈2×ω C ε i ) is dense in X\( i∈ω C ε i ). The assumption gives (x, y) ∈ ( i∈ω C 0 i ×C 1 i ) ∩ C 2 . Then (x, y) ∈ ( i∈ω C 0 i ×C 1 i ) ∩ (C n ×D n ), which is absurd. (b) Let (C ε i ) (ε,i)∈2×ω
be the family given by Lemmas 4.1.(b) and 4.3. As the C ε i 's are singletons, they are meager.

Remark. Note that ∆ X\( (ε,i)∈2×ω C ε i ) = ∆(X) ∩ X\( i∈ω C 1 i ) × X\( i∈ω C 0 i ) is a closed subset of X\( i∈ω C 1 i ) × X\( i∈ω C 0 i )
. This shows that the spaces X 0 2 , X 1 2 of Conjecture 2 cannot be both compact, which is quite unusual in this kind of dichotomy (even if it was already the case in [L2]). Indeed, our example shows that A 0 2 , A 1 2 must be separable by a closed set C, and C, A 1 2 must have disjoint projections. If X 0 2 , X 1 2 are compact, then C and its projections are compact too. The product of these compact projections is a (Σ 0 2 ×Σ 0 2 ) σ set separating A 0 2 from A 1 2 , which cannot be. We will meet an example where X = 3 ω . This fact implies that we cannot extend the continuous maps of Theorem 1.5.(e) to 3 ω in general.

To ensure the possibility of the reduction, we introduce the following notion:

Definition 4.8 Let 1 ≤ ξ < ω 1 . A ξ-disjoint family (C ε i ) (ε,i)∈2×ω
of subsets of a 0-dimensional Polish space X is said to be very comparing if for each integer q there is a partition (O p q ) p∈ω of X into ∆ 0 ξ sets such that, for each i ∈ ω, (a) if q < i, then there is

p i q ∈ ω such that C 0 i ∪ C 1 i ⊆ O p i q q , (b) if q ≥ i and ε ∈ 2, then C ε i ⊆ O 2i+ε q , (c) if (ε, i) ∈ 2×ω, then r≥i q≥r O 2i+ε q = C ε i .
Lemma 4.9 There is a very comparing 1-disjoint family (C ε i ) (ε,i)∈2×ω of subsets of ω ω satisfying the assumptions (and thus the conclusion) of Lemma 4.7.(a).

Proof. Let (C ε i ) (ε,i)∈2×ω
= r≥i q≥r N b(i)(2|b(i)|+ε) max l≤q (|b(l)|+1)-|b(i)| = {b(i)(2|b(i)| + ε) ∞ } = C ε i .
This finishes the proof.

Notation. We now recall some facts about the Gandy-Harrington topology (see [L2]). Let Z be a recursively presented Polish space. The Gandy-Harrington topology GH on Z is generated by the Σ 1 1 subsets of Z. We set

Ω Z := {z ∈ Z | ω z 1 = ω CK 1 }. Then Ω Z is Σ 1 1 , dense in (Z, GH), and W ∩ Ω Z is a clopen subset of (Ω Z , GH) for each W ∈ Σ 1 1 (Z). Moreover, (Ω Z , GH) is a 0-dimensional Polish space. So we fix a complete compatible metric d GH on (Ω Z , GH).
The following notion is important for the next proof. Definition 4.10 Let a be a countable set, ξ < ω 1 , and

F := (S ε i ) (ε,i)∈2×ω be a ξ-disjoint family of subsets of a ω . We say that s ∈ a <ω is F-suitable if there is (α, β) ∈ i∈ω S 0 i ×S 1 i such that s = α ∧ β is the longest common initial segment of α and β.
Example. In the next proof, we will take a := 3, ξ := 1, and s will be suitable when s is empty or finishes with 2. If θ : ω → {s ∈ 3 <ω | s is suitable} is a bijection such that |θ(i)| i∈ω is nondecreasing, then we can define a 1-disjoint family F of subsets of 3 ω by S ε i := {θ(i)εα | α ∈ 2 ω }, and s is suitable exactly when s is F-suitable.

In particular, a non suitable sequence is of the form sεt, where s is suitable, ε ∈ 2 and t ∈ 2 <ω (we will use this notation in the next proof). If ∅ = s is suitable, then we set

s -:= s|max{l < |s| | s|l is suitable}. Lemma 4.11 Let X be a 0-dimensional Polish space, (C ε i ) (ε,i)∈2×ω
be a very comparing 1-disjoint family of subsets of X, X, Y be Polish spaces, and A 0 , A 1 be disjoint analytic subsets of X×Y . Then one of the following holds:

(a) A 0 is separable from A 1 by a (Σ 0 2 ×Σ 0 2 ) σ set, (b) X\( i∈ω C 1 i ), X\( i∈ω C 0 i ), ∆ X\( (ε,i)∈2×ω C ε i ) , i∈ω C 0 i ×C 1 i ≤ (X, Y, A 0 , A 1 ).
Proof. We may assume that X, Y are recursively presented and that A 0 , A 1 are Σ 1 1 . Assume that (a) does not hold. By Theorem 2.5 we get N

:= A 0 ∩ A 1 T 2 ×T 2 = ∅. Lemma 2.2 implies that (x, y) / ∈ A 1 T 2 ×T 2 ⇔ ∃C, D ∈ Σ 1 1 ∩ Π 0 1 (x, y) ∈ C ×D ⊆ ¬A 1 ⇔ ∃C, D ∈ ∆ 1 1 ∩ Π 0 1 (x, y) ∈ C ×D ⊆ ¬A 1 .
This and Proposition 1.4 in [START_REF] Louveau | A separation theorem for Σ 1 1 sets[END_REF] show that

N is Σ 1 1 . We construct -A sequence (x u ) u∈3 <ω of points of X, -A sequence (y u ) u∈3 <ω of points of Y , -A sequence (X u ) u∈3 <ω of Σ 0 1 subsets of X, -A sequence (Y u ) u∈3 <ω of Σ 0 1 subsets of Y , -A sequence (V s ) s∈3 <ω suitable of Σ 1 1 subsets of X ×Y .
We want these objects to satisfy the following conditions:

(

1) (x u , y u ) ∈ X u ×Y u (2) (x s , y s ) ∈ V s ⊆ N ∩ Ω X×Y if s is suitable (3) X uε ⊆ X u if u is suitable or u = s0t, and X s1t2 ⊆ X s (4) Y uε ⊆ Y u if u is suitable or u = s1t, and Y s0t2 ⊆ Y s (5) V s ⊆ V s -if ∅ = s is suitable (6) diam(X u ), diam(Y u ) ≤ 2 -|u| (7) diam GH (V s ) ≤ 2 -|s| if s is suitable (8) (x s0 , y s1 ) ∈ Π 0 [(X s ×Y s ) ∩ V s ]×Π 1 [(X s ×Y s ) ∩ V s ] ∩ A 1 if s is suitable (9) (x s0t , y s1t ) = (x s0 , y s1 ) if s is suitable and t ∈ 2 <ω
• Assume that this is done. We define φ : This map allows us to define Φ : ω ω → 3 ω by Φ(γ)(p) := φ γ|(p+1) (p), and Φ is continuous.

ω
As (C ε i ) (ε,i)∈2×ω is very comparing, there are some witnesses (O p q ) p∈ω . Let x ∈ X. As in the proof of Lemma 4.4, we associate the sequence (p q ) q∈ω ∈ ω ω defined by x ∈ O pq q . As (C ε i ) (ε,i)∈2×ω is very comparing, (p q ) q∈ω is not eventually constant if x / ∈ (ε,i)∈2×ω C ε i . Thus Φ (p q ) q∈ω has infinitely many 2's in this case. If x ∈ C ε i , then If x / ∈ (ε,i)∈2×ω C ε i , then the sequence (k j ) j of integers such that Φ (p q ) q∈ω |k j is suitable is an infinite subsequence of both (n 0 k ) k∈ω and (n 1 k ) k∈ω . Note that (V Φ((pq)q∈ω)|k j ) j∈ω is a nonincreasing sequence of nonempty closed subsets of Ω X×Y whose GH-diameters tend to 0, so that we can define F (x) by {F (x)} := j∈ω V Φ((pq)q∈ω)|k j ⊆ N ⊆ A 0 . As F (x) is the limit (in (X ×Y, GH), and thus in X × Y ) of (x Φ((pq)q∈ω)|k j , y Φ((pq)q∈ω)|k j ) j∈ω , we get

Φ (p q ) q∈ω = Φ p i 0 ...p i i-1 (2i+ε) ∞ = φ(p i 0 ...p i i-1 )2ε ∞ . If x ∈ X\( i∈ω C 1 i ), then the increasing sequence (n 0 k ) k∈ω of integers such that Φ (p q ) q∈ω |n 0 k is suit- able or of the form s0t is infinite. Condition (3) implies that (X Φ((pq)q∈ω)|n 0 k ) k∈ω is non-increasing.
F (x) = f (x), g(x) . Therefore ∆ X\( (ε,i)∈2×ω C ε i ) ⊆ (f ×g) -1 (A 0 ).
Note that x s0 = x s0 2 = ... = x s0 q+1 for each s suitable. Thus

f (x) = lim q→∞ x φ(p i 0 ...p i i-1 )20 q+1 = x φ(p i 0 ...p i i-1 )20 if x ∈ C 0 i . Similarly, g(y) = y φ(p i 0 ...p i i-1 )21 if y ∈ C 1 i and i∈ω C 0 i ×C 1 i ⊆ (f ×g) -1 (A 1 ).
• Let us prove that the construction is possible. As N = ∅, we can choose

(x ∅ , y ∅ ) ∈ N ∩ Ω X×Y , a Σ 1 1 subset V ∅ of X×Y with (x ∅ , y ∅ ) ∈ V ∅ ⊆ N ∩ Ω X×Y of
GH-diameter at most 1, and a Σ 0 1 neighborhood X ∅ (resp., Y ∅ ) of x ∅ (resp., y ∅ ) of diameter at most 1. Assume that (x u ) u∈3 ≤l , (y u ) u∈3 ≤l , (X u ) u∈3 ≤l , (Y u ) u∈3 ≤l and (V s ) s∈3 ≤l suitable satisfying (1)-( 9) have been constructed, which is the case for l = 0.

Let s ∈ 3 <ω be suitable. Note that (x s , y

s ) ∈ (X s ×Y s ) ∩ V s ⊆ A 1 T 2 ×T 2 . We choose X ′ , Y ′ ∈ Σ 0 1 with (x s , y s ) ∈ X ′ × Y ′ ⊆ X ′ × Y ′ ⊆ X s × Y s . As Π ε [(X ′ × Y ′ ) ∩ V s ] is Σ 1 1 , Π ε [(X ′ ×Y ′ ) ∩ V s ] is Σ 1 1 ∩ Π 0 1 . In particular, Π ε [(X ′ ×Y ′ ) ∩ V s ] is T 2 -open.
This shows the existence of

(x s0 , y s1 ) ∈ Π 0 [(X ′ ×Y ′ ) ∩ V s ]×Π 1 [(X ′ ×Y ′ ) ∩ V s ] ∩ A 1 .
Note that (x s0 , y s1 ) ∈ X ′ ×Y ′ ⊆ X s ×Y s . We set x s1 := x s , y s0 := y s . We defined x u , y u when u ∈ 3 l+1 is not suitable but u|l is suitable.

Assume now that u ∈ 3 l+1 is suitable, but not u|l. This gives (s, ε, t) such that u = sεt2. Assume first that ε = 0. Note that

x s0t = x s0 ∈ X s0t ∩ Π 0 [(X s ×Y s ) ∩ V s ]. This gives x u ∈ X s0t ∩ Π 0 [(X s ×Y s ) ∩ V s ],
and also y u with

(x u , y u ) ∈ (X s0t ∩ X s )×Y s ∩ V s = (X s0t ×Y s ) ∩ V s . If ε = 1, then similarly we get (x u , y u ) ∈ (X s ×Y s1t ) ∩ V s .
If u and u|l are both suitable, or both non suitable, then we set (x u , y u ) := (x u|l , y u|l ). So we defined x u , y u in any case. Note that Conditions (8) and ( 9) are fulfilled, and that (x s , y s

) ∈ V s -if s is suitable. Moreover, x u ∈ X u|l if u|l is suitable or u|l = s0t, and x u ∈ X s if u = s1t2, and similarly in Y . We choose Σ 0 1 sets X u , Y u of diameter at most 2 -l-1 with (x u , y u ) ∈ X u ×Y u ⊆ X u ×Y u ⊆    X u|l ×Y u|l if u is not suitable or u|l is suitable, X u|l ×Y s if u = s0t2, X s ×Y u|l if u = s1t2.
It remains to choose, when s is suitable,

V s ∈ Σ 1 1 (X × Y ) of GH-diameter at most 2 -l-1 such that (x s , y s ) ∈ V s ⊆ V s -. We set X ε 2 := ω ω \{u(2|u|+1-ε) ∞ | u ∈ ω <ω } = X\( i∈ω C 1-ε i ), A 0 2 := ∆(ω ω \{u(2|u|+ε) ∞ | (u, ε) ∈ ω <ω ×2}) = ∆ X\( (ε,i)∈2×ω C ε i ) ,
and

A 1 2 := u(2|u|) ∞ , u(2|u|+1) ∞ | u ∈ ω <ω = i∈ω C 0 i ×C 1 i .
Corollary 4.12 Let X, Y be Polish spaces, and A 0 , A 1 be disjoint analytic subsets of X ×Y . Then exactly one of the following holds:

(a) A 0 is separable from A 1 by a (Σ 0 2 ×Σ 0 2 ) σ set, (b) (X 0 2 , X 1 2 , A 0 2 , A 1 2 ) ≤ (X, Y, A 0 , A 1 ).
Recall the sequence (s n ) n∈ω defined in the introduction. In G 0 , we put s n , i.e., a finite sequence of elements of 2, before the changed coordinate. In A 3 , we will put a finite sequence of elements of 2 <ω , together with a way to recover them after concatenation, before the changed coordinate. In order to do that, we identify ω with ω 2 . Notation. Let < ., . >: ω 2 → ω be a natural bijection. More precisely, < n, p >:= (Σ k≤n+p k)+p. Note that the inverse bijection q → (q) 0 , (q) 1 is build as follows. We set, for q ∈ ω, M (q) := max{m ∈ ω | Σ k≤m k ≤ q}.

Then we define (q) 0 , (q) 1 := M (q)-q+(Σ k≤M (q) k), q-(Σ k≤M (q) k) . More concretely, ω = {< 0, 0 >, < 1, 0 >, < 0, 1 >, . . . , < M (q), 0 >, < M (q)-1, 1 >, ..., < 0, M (q) >, ...}.

If u ∈ 2 ≤ω and n ∈ ω, then we define (u) n ∈ 2 ≤ω by (u) n (p) := u(< n, p >) if < n, p >< |u|.

Here also we define < α 0 , α 1 , ... >∈ 2 ω by < α 0 , α 1 , ... > (< n, p >) := α n (p), for any sequence (α n ) n∈ω of elements of 2 ω . In particular, α → (α) n n∈ω and (α n ) n∈ω →< α 0 , α 1 , ... > are inverse bijections.

Lemma 5.2 Let u, v ∈ 2 <ω . (a) u ⊆ v implies that (u) n ⊆ (v) n for each n ∈ ω. (b) |(u) 0 | ≤ |u|. (c) |(u) n | ≤ |u|+1-n if n ≤ |u|+1. Proof. (a) If < n, p >< |u|, then (u) n (p) = u(< n, p >) = v(< n, p >) = (v) n (p) because of the inequality < n, p >< |v|, so that (u) n ⊆ (v) n . (b) We set, for n, q ∈ ω, c n q := Card({p ∈ ω |< n, p >< q}). As < ., . > is a bijection, we get c n q+1 ≤ c n q +1. As c n 0 = 0, c n q ≤ q. We are done since |(u) n | = c n |u| . (c) Note first that < n, p >= (Σ k≤n+p k)+p < (Σ k≤n ′ +p ′ k)+p ′ =< n ′ , p ′ > if n+p < n ′ +p ′
, and that (q) 0 +(q) 1 = M (q) ≤ q < q+1. This implies that q =< (q) 0 , (q) 1 ><< n, q+1-n > if n ≤ q+1.

It remains to apply this to q :

= |u| since |(u) n | = c n |u| .
We can view G 0 as the countable union n∈ω Gr(ϕ n ), where ϕ n is the homeomorphism defined on the basic clopen set N sn0 onto the clopen set N sn1 defined by ϕ n (s n 0γ) := s n 1γ. The set A 3 will also be the countable union of the graphs of some homeomorphisms, indexed by ω <ω instead of ω. Their domain and range will be G δ subsets of 2 ω instead of clopen sets. We first define the closures of these G δ 's. They will be copies of 2 ω . In fact, our homeomorphims will also be defined on the closure of these final domains. We will fix the coordinates whose number is in one of the verticals before that of the number of the changed coordinate. This leads to the following notation.

Notation. If t ∈ ω <ω and k ≤ |t|, then we set Σ t k := Σ j<k t(j)+2 , and Σ t :=< Σ j<|t| t(j)+2 , 0 >=< Σ t |t| , 0 > (Σ t will be the number of the unique changed coordinate). We set w n := s n 0, so that |w n | = n+1 and (w n ) n∈ω is dense (we want w n to be nonempty).

We define the following objects for t ∈ ω <ω .

• We first define a copy K t of 2 ω by K t := α ∈ 2 ω | ∀k < |t| (α) Σ t k = (w t(k) ) 0 0 t(k)+1-|(w t(k) ) 0 | 10 ∞ and ∀0 < i < t(k)+2 (α) Σ t k +i = w t(k) i 0 ∞ . This is well defined since |w t(k) | = t(k)+ 1, so that we can apply Lemma 5.2.(b) to u := w t(k) and t(k)+1-|(w t(k) ) 0 | ≥ 0. In particular, the last 1 in (α) Σ t k is at the position t(k)+1. Here is the picture of K t when t = (4, 2):

• We define a non-trivial partition (K 0 t , K 1 t ) of K t into clopen sets by K ε t := {α ∈ K t | α(Σ t ) = ε}.

• We define a homeomorphism ϕ t : K 0 t → K 1 t by ϕ t (α)(m) := 1 if m = Σ t , α(m) otherwise.

We can view the construction of K t , K ε t and ϕ t inductively. Indeed, K ∅ = 2 ω , K ε ∅ is the basic clopen set N ε , and ϕ ∅ (α)(m) is 1 when m = 0, α(m) otherwise. Then 3complete set (see 23.A in [K]). We will more or less recover this example, but the 1's have to be well placed. This leads to the following technical but crucial notion. Definition 5.3 We say that u ∈ 2 <ω is placed if u = ∅ and there is t ∈ ω <ω such that N u ∩ K t = ∅, (|u|-1) 0 = Σ t |t| , and u(|u|-1) = 1 if (|u|-1) 1 > 0. We also say that t is a witness for the fact that u is placed.

This means that the last coordinate of u has a number on the vertical Σ t |t| , on which the coordinates of the elements of K t are left free by t, and which is the first vertical with this property. The coordinates of u whose number is on one of the verticals before the previous one are determined by t. Finally, the last coordinate of u is 1, except maybe if this coordinate has the number Σ t , which is at the bottom of the vertical Σ t |t| .

Examples. Let α ∈ K nj = K (n,j) . Then • α|1, α|(< 0, n+1 > +1) are placed with witness ∅.

• α|(< n+2, 0 > +1), α|(< n+2, j +1 > +1) are placed with witness (n).

• α|(< n + 2 + j + 2, 0 > +1) is placed with witness (n, j). If α(< n + 2 + j + 2, q >) = 1, then α|(< n+2+j +2, q > +1) is placed with witness (n, j).

We are now ready to define X 3 and A 3 .

Notation. We set X 3 := α ∈ 2 ω | ∀n ∈ ω ∃p ≥ n α|p is placed . Let t ∈ ω <ω . We set We now start to prove the required properties of X 3 and A 3 . Lemma 5.5 (a) The set X 3 is a dense Π 0 2 subset of 2 ω . In particular, X 3 is a 0-dimensional Polish space. (b) Let t ∈ ω <ω . The set H t is a dense Π 0 2 subset of K 0 t . (c) The set A 3 is a Σ 0 3 subset of X 2 3 . In particular, A 3 is an analytic relation on X 3 . (d) Let β ∈ ω ω . Then n∈ω K β|(n+1) ⊆ X 3 . (e) (X 3 , A 3 ) ∆ 0

  be the family given by Lemmas 4.1.(b), 4.3, and 4.7.(b). It remains to check Condition (c). Note first that the inclusion r≥i q≥r O 2i+ε q

  <ω → 3 <ω by φ(∅) := ∅ and φ(sn) := φ(s)2ε if n = 2|s|+ε or s = ∅ and n = s(|s|-1) , φ(s)ε if (n = 2q+ε and q = |s|) and s = ∅ or s = ∅ and n = s(|s|-1) .

  Moreover, (X Φ((pq)q∈ω)|n 0 k ) k∈ω is a sequence of nonempty closed subsets of X whose diameters tend to 0, so that we can define {f (x)} := k∈ω X Φ((pq)q∈ω)|n 0 k = k∈ω X Φ((pq)q∈ω)|n 0 k . This defines a continuous map f : X \ ( i∈ω C 1 i ) → X with f (x) = lim k→∞ x Φ((pq)q∈ω)|n 0 k . Similarly, we define g : X\( i∈ω C 0 i ) → Y continuous with g(x) = lim k→∞ y Φ((pq)q∈ω)|n 1 k .

K

  tn := {α ∈ K wn(0) t | (α) Σ t |t| = (w n ) 0 0 n+1-|(wn) 0 | 10 ∞ and ∀0 < i < n+2 (α) Σ t |t| +i = (w n ) i 0 ∞ }, K ε tn := {α ∈ K tn | α(< Σ t |t| +n+2, 0 >) = ε}, and ϕ tn (α)(m) is 1 when m is equal to < Σ t |t| +n+2, 0 >, α(m) otherwise.The set S 3 := {α ∈ 2 ω | ∃m ∈ ω ∀n ∈ ω ∃p ≥ n (p) 0 = m and α(p) = 1} is a standard Σ 0

H

  t := {α ∈ K 0 t | ∀n ∈ ω ∃p ≥ n (p) 0 = Σ t|t| and α(p) = 1}, and A 3 := t∈ω <ω Gr(ϕ t|H t ). In this sense, we recover S 3 . More concretely,A 3 = t∈ω <ω (u0γ, u1γ) | |u| = Σ t and u0γ ∈ K t and ∀n ∈ ω ∃p ≥ n (u0γ)(< Σ t |t| , p >) = 1 . Lemma 5.4 Let t ∈ ω <ω and ε ∈ 2. (a) (K tn ) n∈ω,wn(0)=ε is a sequence of pairwise disjoint meager subsets of K ε t . (b) Any nonempty open subset of K ε t contains one of the K tn 's.Proof. (a) This comes from the fact that the last 1 in (α)Σ t |t| is at the position n+1 if α ∈ K tn . (b) A nonempty open subset of K ε t contains a basic clopen set C of the form {α ∈ K ε t | εu ⊆< (α) Σ t |t| , (α) Σ t |t| +1 , ... >}, where u ∈ 2 <ω . We choose n ∈ ω such that εu ⊆ w n . It remains to see that K tn ⊆ C. So let m =< i, p >≤ |u|. Note first that M (q) ≤ min q, M (q+1) Thus, as |u| ≤ |w n | = n+1, i = (m) 0 ≤ (m) 0 +(m) 1 = M (m) ≤ M (|u|) ≤ M (n+1) ≤ n+1 < n+2.Lemma 5.2.(a) allows us to write(εu)(m) = (εu)(< i, p >) = (εu) i (p) = (w n ) i (p) = (α) Σ t |t| +i (p) = (< (α) Σ t |t| ,(α) Σ t |t| +1 , ... >) i (p) = (< (α) Σ t |t| , (α) Σ t |t| +1 , ... >)(m). This finishes the proof.

ω, ¬∆(ω) .

The work is a part of the research project MSM 0021620839 financed by MSMT and partly supported by the grant GA ČR 201/09/0067.

Acknowledgements. This work started in summer 2009, and was continued during spring 2010, when the first author was invited at the University of Prague by the second one.

Remark. In the remark after Lemma 4.7 we announced an example with X := 3 ω . In fact, we already met it after Definition 4.10. Recall that the formula S ε i := {θ(i)εα | α ∈ 2 ω } defines a 1-disjoint family of subsets of 3 ω , which are clearly meager. It is also clear that no nonempty clopen subset of 3 ω is ( i∈ω S 0 i ×S 1 i )-discrete. One can check that the formula

defines witnesses for the fact that (S ε i ) (ε,i)∈2×ω is very comparing.

To close this section, we notice that the notion of a very comparing 1-disjoint family gives only a sufficient condition, and not a characterization like in 3.5, 3.9 or 4.6: Proposition 4.13 Let X be a 0-dimensional Polish space, (C ε i ) i∈ω be a very comparing 1-disjoint family of subsets of X, X ε ⊆ X\( i∈ω C 1-ε i ), A 0 ⊆ ∆ X\( (ε,i)∈2×ω C ε i ) , and A 1 ⊆ i∈ω C 0 i ×C 1 i be as in the definition of ≤. Then for any Polish spaces X, Y , and any disjoint analytic subsets A 0 , A 1 of X ×Y , A 0 is not separable from A 1 by a (Σ 0 1 ×Σ 0 1 ) σ set ⇒ (X 0 , X 1 , A 0 , A 1 ) ≤ (X, Y, A 0 , A 1 ).

5 The case ξ = 3: Baire class two colorings Remark. Unlike when ξ ∈ {1, 2}, we cannot have A 3 of the form n∈ω C 0 n ×C 1 n , where (C ε n ) (ε,n)∈2×ω is a 2-disjoint family. Indeed, we will see that there is a Borel graph G ⊆ 2 ω × 2 ω of a partial injection such that (2 ω , G) ∆ 0 3 ω, ¬∆(ω) . We would get f : X 3 → 2 ω continuous such that A 3 ⊆ (f ×f ) -1 (G), and f [C 0 n ]×f [C 1 n ] would be a singleton. The set (f ×f )[A 3 ] would be countable, and (2 ω , (f × f )[A 3 ]) ∆ 0 3 ω, ¬∆(ω) , (X 3 , A 3 ) ∆ 0 3 ω, ¬∆(ω) would hold, which is absurd. However, the following result holds.

Theorem 5.1 There are a 0-dimensional Polish space X 3 and an analytic relation A 3 on X 3 such that for any Polish space X, and for any analytic relation A on X, exactly one of the following holds:

We can take X 3 = ω ω , but this is not the most natural thing to do. Note that we can replace X 3 with any copy of it. Our space X 3 will be a dense G δ subset of 2 ω , in fact a copy of ω ω . This G δ subset is not necessary to see that (X 3 , A 3 ) satisfies the "exactly" part of Theorem 5.1 (i.e., that

), but it is useful to build and ensure the continuity of the homomorphism of Statement (b). The definition of X 3 and A 3 is based on the construction of the following basic objects.

Proof. (a) X 3 is clearly a Π 0 2 subset of 2 ω . So let us prove its density. We just have to prove that α ∈ 2 ω | ∃p ≥ n α|p is placed is dense in 2 ω for each integer n. So let ∅ = w ∈ 2 <ω . Note that

So let us prove its density. We just have to prove the density in

As in the proof (a), we see (with w(0) := 0) that α := w1 ∞ ∈ N w ∩ K 0 t and p ≥ max(n, |w|) with (p) 0 = 0 are suitable. If |t| ≥ 1, then we argue similarly. We put again w1 ∞ , in the coordinates not determined by t.

n∈ω is strictly increasing. In particular,

+1≥ n and t := β|(n + 1) are witnesses for the fact fact α ∈ X 3 .

(e) We argue by contradiction, which gives a partition

Applying this inductively, we construct β ∈ ω ω such that C n ∩ K β|(n+1) = ∅ for each n ∈ ω. By compactness, there is α ∈ n∈ω K β|(n+1) , and α / ∈ n∈ω C n = X 3 . But this contradicts (d).

The following uniqueness properties will be important in the sequel.

Lemma 5.6 Let t ∈ ω <ω and α ∈ K t .

(a) Assume that u ∈ 2 <ω is placed with witness t. Then Σ t < |u|, the last 1 in u strictly before the position < Σ t k+1 , 0 > is at the position < Σ t k , t(k)+1 > for each k < |t|, and t is unique. (b) Let p > Σ t be such that α|p is placed with witness t ′ . Then t ⊆ t ′ .

Proof. (a) As

• Let us prove that the last 1 in u strictly before the position < Σ t k+1 , 0 > is at the position

There are

and we are done.

• As the last 1 in u strictly before the position < Σ t |t| , 0 > is at the position < Σ t |t|-1 , t(|t|-1)+1 >, t(|t|-1) is determined. It remains to iterate this argument to see the uniqueness of t.

(b) We argue by induction on l := |t|, and we may assume that our property is proved for l. So let t ∈ ω l+1 , α ∈ K t , and p > Σ t be such that α|p is placed with witness t ′ . Note that α ∈ K t|l and p > Σ t|l . By the induction assumption, we get t|l ⊆ t ′ .

Let us prove that t|l = t ′ . We argue by contradiction, so that (p -1)

(a) If u is placed, then let t ∈ ω <ω be the unique witness given by Lemma 5.6.(b). We will consider

(b) We say that u is l-placed if u is placed and l(u) = l. We say that u is (≤ l)-placed (resp.,

The following lemma will be crucial in the construction of the homomorphism. We construct some finite approximations of the homomorphism. The lemma says that these finite approximations can be constructed independently.

When we consider the finite approximations of an element of A 3 , we have to guess the finite sequence t. We usually make some mistakes. In this case, we have to be able to come back to an earlier position. This is the role of the following predecessors.

Notation. Let u ∈ 2 <ω . Note that < ε > is 0-placed. This allows us to define

and, for l ∈ ω,

Before proving our main theorem, we study the relation between these predecessors and the placed sequences.

Lemma 5.9 Let l ∈ ω and u ∈ 2 <ω be l-placed with |u| ≥ 2.

Then exactly one of those two sequences is (> l)placed, and the other one is l-placed.

.

(e) l(u -l ) ∈ {l-1, l}.

Proof. Let t ∈ ω l (resp. t ′ ∈ ω <ω ) be a witness for the fact that u (resp., u -) is placed, and α ∈ N u ∩K t .

Claim. Assume that (|u|-1)

Proof. Note that l ≥ 1 since |u| ≥ 2. The consecutive integers between the values < Σ t l-1 , t(l-1)+1 > and Σ t are < Σ t l-1 , t(l-1)+1 >, < Σ t l-1 -1, t(l -1)+2 >, ..., < 0, Σ t l-1 +t(l -1)+1 > and Σ t . By Lemma 5.6.(b), Σ t < |u| and the last 1 in u strictly before the position Σ t is at the position < Σ t l-1 , t(l-1)+1 >. This shows that u|(Σ t +1) and u|(< Σ t l-1 , t(l-1)+1 > +1) are placed and u|(Σ t +1)

Assume now that (u l ) -is l-placed. As u l is l-placed with witness t, there is some

that t is the witness for the fact that (u l ) -is l-placed. If u -= u|(< Σ t l , j 0 > +1), then there is no j 0 < j < (|u|-1) 1 with u(< Σ t l , j >) = 1, and

(b) Assume that u -l is l-placed. As in (a) we get (|u|-1) 1 > 0 and j 1 with u -l = u|(< Σ t l , j 1 > +1), and (u l ) -l = u l |(< Σ t l , j 1 > +1) = (u -l ) l is l-placed. The equivalence comes from the fact that (u l ) l = u. We argue as in (a) to see that ε(u -l ) = ε(u) if u -l is l-placed.

(c) Assume first that u -is (< l)-placed. The proof of (a) shows that |t ′ | ≥ l if (|u|-1) 1 > 0. Thus (|u|-1) 1 = 0 and the claim gives the result. If (u l ) -is (< l)-placed, then we apply this to u l , using the facts that u l is l-placed and (u l ) l = u.

(d) Assume first that u -is (> l)-placed. As in (a) we get t t ′ . In particular, the last 1 in (u -) Σ t l is at the position t ′ (l)+1. Let us prove that u -l = u|(< Σ t l , t ′ (l)+1 > +1). Note that u|(< Σ t l , t ′ (l)+1 > +1) is l-placed, so that u|(< Σ t l , t ′ (l)+1 > +1) ⊆ u -l ⊆ u -. Lemma 5.6.(c) shows that u -l is l-placed with witness t. As the last 1 in (u -) Σ t l is at the position t ′ (l)+1, we are done.

Note that u l |(< Σ t l , t ′ (l)+1 > +1) ⊆ (u l ) -. We argue by contradiction to see that (u l ) -is not (> l)-placed. This gives a witness t ′′ , which is a strict extension of t by Lemma 5.6.(c). We saw that the last 1 in (u l ) - Σ t l is at the position t ′ (l)+1. But it is also at the position t ′′ (l)+1, which shows

Assume now that (u l ) -is (> l)-placed. As u l is l-placed and (u l ) l = l, the previous arguments show that u -is l-placed. In particular,

Proof of Theorem 5.1. X 3 and A 3 have been defined before. The "exactly" part comes from Lemma 5.5.(e). So we just have to prove that (a) or (b) holds. We may assume that X is recursively presented and A is a Σ 1 1 relation. We set

There is a countable covering of X into A-discrete Σ 0 3 sets. We just have to reduce them to get a partition showing that (a) holds.

Case 2. U = X.

Note that if V is as in the definition of U , then V and ¬ p∈ω D p are disjoint Σ 1 1 sets, separable by a Π 0 1 set. By Theorems 1.A and 1.B in [START_REF] Louveau | A separation theorem for Σ 1 1 sets[END_REF], there is W ∈ ∆ 1 1 ∩ Π 0 1 separating these two sets. This shows that we can replace the condition "

(see [START_REF] Louveau | A separation theorem for Σ 1 1 sets[END_REF]). This shows that Y := X \U is a nonempty

We argue by contradiction. Note that

• We construct, when u is placed, some points x u of Y , some Σ 0 1 subsets X u of X, and some Σ 1 1 subsets U u of X 2 . We want these objects to satisfy the following conditions:

(1) x u ∈ X u and

As we will see, Conditions ( 1)-( 4) are sufficient to get the required objects. Condition ( 5) is used to prove that the construction is possible. The idea is the following. When we extend some u ∈ 2 <ω , some new links may appear. But we may also break some links, and preserve only an initial segment of them. In this case, to ensure Condition (3), we have to be able to come back to the last preserved link. This is possible if we use iteratively Conditions (3) and ( 5).

• Assume that this is done. Let α ∈ X 3 and (p α k ) k∈ω be the infinite strictly increasing sequence of integers Condition (2). This shows that (X α|p α k ) k∈ω is a non-increasing sequence of nonempty closed subsets of X whose diameters tend to 0, and we define {f (α)} := k∈ω X α|p α k = k∈ω X α|p α k , so that f : X 3 → X is continuous and f (α) = lim k→∞ x α|p α k . Now let (α, β) ∈ A 3 . If (α, β) ∈ |t|=l Gr(ϕ t|H t ), then let (p j ) j∈ω be the infinite strictly increasing sequence of integers p j ≥ 1 such that (p j -1) 0 = Σ t |t| , (p j -1) 1 > 0 and α(p j -1) = 1. In particular, α|p j is l-placed and ε(α|p j ) = 0. Note that (p j ) j∈ω is also the infinite strictly increasing sequence of integers p j ≥ 1 such that (p j -1) 0 = Σ t |t| , (p j -1) 1 > 0 and β(p j -1) = 1 on one side, and a subsequence of both (p α k ) k∈ω and (p β k ) k∈ω on the other side.

If moreover p ≥ p 0 and α|p is placed, then the witness is an extension of t and l(α|p) ≥ l, by Lemma 5.6.(c). In particular, if p ≥ p 0 and α|p is l-placed, then the witness is t. This proves that (p j ) j∈ω is the infinite strictly increasing sequence of integers p j ≥ p 0 such that α|p j is lplaced. Therefore (α|p j+1 ) -l = α|p j . By Condition (3), (U α|p j ) j∈ω is a non-increasing sequence of nonempty clopen subsets of A ∩ Ω X 2 whose GH-diameter tend to 0. So we can define

• Let us prove that the construction is possible. We do it by induction on the length k of u.

Subcase 1. k = 0

We are done since ∅ is not placed.

Subcase 2. k = 1

The claim gives

If there is no placed sequence in 2 k , then there is nothing to do. If u ∈ 2 k is l-placed, then u l ∈ 2 k is l-placed and ε(u l ) = 1-ε(u). Assume for example that ε(u) = 0. Lemma 5.8 ensures that we just have to define x u , x u l , X u , X u l and U u = U u l , independently from the other sequences in 2 k .

-If u -and (u l ) -are l-placed, then u -, (u l ) -= u -l , (u l ) -l . Moreover, ε(u -) = ε(u) = 0, (u l ) -= (u -) l and (u l ) -l = (u -l ) l , by Lemma 5.9. We set

Assume for example that we are in the second case. Then

The claim gives a couple

-If u -or (u l ) -is (> l)-placed, then by Lemma 5.9.(d) exactly one of those two sequences is (> l)placed, and the other one is l-placed. If u -(resp., (u l ) -) is (> l)-placed, then u -l = (u l ) -l (resp., u -l = u -). So assume first that u -is (> l)-placed, so that (u l ) -= (u l ) -l = (u -l ) l and u -l is l-placed.

Here is an illustration of what is going on in this case.

We define (u n ) n≤L by u 0 := u -, u L := u -l and u n+1 := u -l(un) n

if n < L. This can be done, by Lemma 5.9.(e). Note that u n is placed. We enumerate injectively the sequence l(u n ) n≤L by the non-increasing sequence (l k ) k≤K . More concretely,

This gives

If we iterate the previous argument, then we get

If now (u l ) -is (> l)-placed, then we argue similarly, using the fact that

This finishes the proof.

At the beginning of the section, we mentioned the fact that it is not necessary to use the dense G δ subset X 3 of 2 ω to find a relation G on 2 ω satisfying (2 ω , G) ∆ 0 3 ω, ¬∆(ω) . We now specify this.

Notation. We set, for t ∈ ω <ω , Ht :

The set H t is a subset of Ht , and thus satisfies the previous disjointness properties.

Proof. (a) Note first that K tn ⊆ K wn(0) t ⊆ K t and (K tn ) n is a sequence of pairwise disjoint sets. This implies that K t ∩K t ′ = ∅ if t, t ′ are incompatible. In particular, as Ht ⊆ K 0 t \( n∈ω,wn(0

has finitely many 1's.

Remarks. (a)

We set G := t∈ω <ω Gr(ϕ t | Ht ), so that (2 ω , G) ∆ 0 3 ω, ¬∆(ω) , by the proof of Lemma 5.5. By Lemma 5.10, G is the Borel graph of a partial injection, as announced at the beginning of the section.

(b) Note that (X 3 , A 3 ) ∆ 0 4 ω, ¬∆(ω) , as we can see with the following partition of X 3 :

with H t ∈ Π 0 2 and A 3 -discrete by Lemma 5.10.(b), X 3 \( t∈ω <ω H t ) ∈ Π 0 3 and A 3 -discrete.

(c) There are a comparing 2-disjoint family (C ε i ) (ε,i)∈2×ω of subsets of X 3 , and also homeomorphisms ϕ i : C 0 i → C 1 i such that A 3 = i∈ω Gr(ϕ i ). Indeed, we choose a bijection b : ω → ω <ω with b -1 (s) ≤ b -1 (t) if s ⊆ t, as in the proof of Lemma 4.3, and set C 0 i := H b(i) , C 1 i := ϕ b(i) [H b(i) ],

, so that A 3 = i∈ω Gr(ϕ i ). It remains to see that (C ε i ) (ε,i)∈2×ω is comparing. We set

so that (O p q ) p∈ω is a partition of X 3 into ∆ 0 2 sets since K tn ⊆ K wn(0) t ⊆ K t , K 0 t ∩ K 1 t = ∅ and K t ∩ K t ′ = ∅ if t and t ′ are incompatible.

As Ht ⊆ K 0 t \ ( n∈ω,wn(0)=0 K tn ), ϕ t [ Ht ] ⊆ K 1 t \ ( n∈ω,wn(0)=1 K tn ) and H t ⊆ Ht , (b) in Definition 4.2 is fulfilled. If q < i, then -either there is no j ≤ q such that b(i) is compatible with b(j). C 0 i ∪ C 1 i ⊆ K b(i) ⊆ O 2q+2 q and we set p i q := 2q+2.

-or there are j ≤ q and n such that b(j)n ⊆ b(i), in which case K b(i) ⊆ K . By disjointness, there is at most one couple (j, ε) such that K b(i) ⊆ O 2j+ε q . If it exists, then we set p i q := 2j +ε. If it does not exist, then we set p i q := 2q+2.


Quentin Thommen

Jean Claude Garreau

Véronique Zehnlé

A quantum motor: directed wavepacket motion in an optical lattice

Keywords: numbers: 03.65.-w, 03.65.Ge, 03.65.Aa, 37.10.Jk

We propose a method for arbitrary manipulations of a quantum wavepacket in an optical lattice by a suitable modulation of the lattice amplitude. A theoretical model allows to determine the modulation corresponding to a given wavepacket motion, so that arbitrary atomic trajectories can be generated. The method is immediately usable in state of the art experiments.

The fine manipulation of wavepackets is a fundamental requirement in a large number of fields. Particularly important examples are quantum transport [1][2][3][4][5], "quantum simulators" that aim to reproduce solid state models [6][7][8][9][10][11][12], quantum information [13][14][15][16] and quantum metrology [17]. The possibility of trapping very cold atoms by light was a decisive step leading to enormous progress in this field. Tailored optical potentials, created by multiple interfering beams interacting with cold atoms, allow to trap and to guide atomic wavepackets for long times (compared to the dynamics of the atom external degrees of freedom) and distances (compared to the de Broglie wavelength). Moreover, using far offresonance beams reduces decoherence effects to negligible levels. With such techniques old problems of quantum dynamics have been experimentally studied, as the elusive Bloch oscillations [18,19] or quantum chaos [20][21][22][23][24][25][26]. In the emerging, and rapidly developing, field of quantum information, controlled motion in optical lattices provides ways to manipulate q-bits [27,28]. The next step in the development of such techniques is the shaping and displacing of wavepackets at will, and this is the problem addressed in the present work. We consider the motion of a wavepacket in a driven two-dimensional (2D) optical lattice (the generalization to the 3D case is straightforward). By carefully engineering the temporal driving of the optical potential, we demonstrate a way to coherently impinge to an atom in an lattice almost any kind of motion, including coherent rotations of its wavepacket. Tailored wavepacket motions have been previously studied both theoretically and experimentally by using Bloch oscillations [12,29], but in this case the amplitude of the motion is directly limited by the spatial extension of the wavepacket coherence. Controlled motion in modulated lattices has also been observed experimentally in [2,12]. Our work shows how a suitably "overmodulated" driving allows to displace a wavepacket along paths of arbitrary shape with controlled (and even engineered) dispersion.

Let us first consider the quantum dynamics of an atom in a 1D tilted (or "washboard") potential formed by a sinusoidal potential superposed to a constant force F x , or a linear potential F x x. We use normalized variables such that lengths are measured in units of the lattice step d (= λ L /2, λ L = 2π/k L being the laser wavelength), energy in units of the recoil energy E R = 2 k 2 L /(2M ) where M is the atom mass, and time is measured in units of /E R . The corresponding Hamiltonian is

H x = - 1 2m * ∂ 2 ∂x 2 + [V x + A x (t)] cos(2πx) + F x x, (1)
where m * = π 2 /2 is the mass in normalized units, F x is the constant force measured in units of E R /d, = 1, and V x is the lattice amplitude, to which a time-dependent component A x (t) can be added. Tilted optical lattices have been experimentally realized by many groups [18,19,30]. Dynamics in a tilted lattice is conveniently described by Wannier-Stark (WS) states [19,[31][32][33][34], which are the eigenstates of the Hamiltonian of Eq. (1) with A x (t) = 0. In numerical simulations a finite lattice is used, but if the bounds of the lattice are far from the region of interest there is no essential difference in the dynamics. The eigenenergies of the Hamiltonian. (1) form a "ladder" structure separated by the "Bloch frequency" ω B ≡ 2π/T B = F x (ω B = F x d/ in usual units). Depending on the ratio V x /F x each well can host more than one WS state, each family of states then forming its own ladder [32]. Throughout this paper the parameters of the potential and the initial conditions are chosen so that the atomic dynamics is accurately described by the lowestladder WS states only. This situation can be realized experimentally by using cold enough atoms and raising the optical potential adiabatically [19]. As WS states are, for the parameters used in the present work, highly localized on a potential well, we label a WS state by the well index n in which it is centered ϕ n (x). These states are invariant under a translation of a integer number n of lattice steps, provided the associated energy is also shifted by nω B , that is

ϕ n (x) = ϕ 0 (x -n) (2) E n = E 0 + nω B (3)
(in what follows we set E 0 = 0). It is well known that a wavepacket submitted to the Hamiltonian of Eq. (1) with A x (t) = 0 has an oscillatory behavior, called Bloch oscillation, of period T B . Adding a time-dependent potential modulated at (or around) the frequency ω B is thus a good way to create a resonant response in the dynamics.

We can expand the atomic wave function ψ x (t) over the WS states (of the first ladder):

ψ x (t) = n c n (t)e iφn(t) ϕ n (x), (4)
where the phase φ n (t) is conveniently defined by:

φ n (t) = -nω B t -V x M 0 t 0 A x (t ′ )dt ′ (5)
and M 0 is the p = 0 value of the coupling parameter M p :

M p ≡ ϕ i | cos(2πx) |ϕ i+p = ϕ 0 | cos(2πx) |ϕ p . (6)
[the last identity is a consequence of Eq. ( 2)]. Bringing Eq. ( 4) into the Schrödinger equation associated to the Hamiltonian Eq. ( 1) one obtains the following set of equations:

ċn (t) = -iA x (t) p =0 M p c p+n e -ipωB t . (7)
Eqs. ( 7) can be simplified by using the fact a WS state overlaps significantly only with the WS states associated with the nearest neighbor sites, that is M p ≈ 0 for |p| > 1.

We now set in Eq. ( 1) the driving as

A x (t) = α x (t) sin (ω B t + β x ) . ( 8
)
where α x (t) is a slowly varying function ( α -1

x dα x /dt ≪ ω B ). An additional simplification is obtained by neglecting fast oscillating terms; one then finds from Eq. ( 7):

ċn (t) = M 1 α x (t) 2 c n-1 e -iβx -c n+1 e iβx (9)
whose general solution is

c n (t) = p c n+p (t = 0)e ipβx J p -M 1 ˆt 0 α x (t ′ ) dt ′ (10) (J p (x)
is the Bessel function of the first kind and order p) which is a straightforward extension of a previous result [35]. The mean position of the wavepacket, averaged over a Bloch period T B , is

x t = x t=0 + ˆt 0 v x (t ′ ) dt ′ , where v x (t) = M 1 α x (t) Re(σe -iβx ) (11)
is the instantaneous wavepacket drift velocity and σ ≡ p c * p (0) c p+1 (0) is the initial coherence of the wavepacket. The wavepacket also presents a diffusion characterized by an instantaneous diffusion coefficient D(t) ∝ M 1 α x (t)Im(σe -iβx ) . Hence, the motion and the diffusion can be controlled by changing the temporal driving α x and phase β x . The diffusion can be suppressed by setting β x so that Im(σe -iβx ) = 0; one then obtains an undeformed translation of the wavepacket with a velocity given by Eq. ( 11), v x (t) = ±M 1 α x (t) |σ|. Conversely, setting β x so that Re(σe -iβx ) = 0 leads to a purely diffusive motion with no displacement of the wavepacket's center of mass.

Consider now a "square" 2D lattice formed by the interference of two orthogonal pairs of counterpropagating laser beams. It can be shown that the resulting Hamiltonian is separable [29]: H xy = H x + H y , where H x is given by Eq. ( 1) and H y is the obvious generalization for the y coordinate. The solution can be written as Ψ xy (t) = ψ x (t)ψ y (t) and the 2D dynamics is obtained simply by solving two identical 1D Schrödinger equations for each ψ u (t) (u = x, y), with the corresponding Hamiltonian H u . We can thus induce a controlled 2D motion of the wavepacket by choosing suitable lattice modulations A u (t) = α u (t) sin(ω B t + β u ). In order to illustrate the possibilities opened by our method, we present in Fig. 1 different trajectories obtained by numerical integration of the Schrodinger equation with fixed parameters and an initial wavepacket of gaussian shape

Ψ xy (0) = l,m exp(- l 2 + m 2 9 )ϕ l (x)ϕ m (y). (12)
Note that this form implies that σ is real, the "zero diffusion" condition is thus fulfilled if β x = β y = 0. Plots (a)-(c) in Fig. 1 show the square-modulus of the wavepacket integrated on time, and the arrows indicate the sense of the motion. Plot (a) shows a square trajectory obtained with α x = 1, α y = 0, for 0 ≤ t ≤ 15T B , α x = 0 , α y = 1 for 15T B ≤ t ≤ 30T B , and so on. In plot (b), we drive the wavepacket into an ∞-shaped Lissajous curve by setting α x (t) = cos (Ωt), β x = 0 and α y (t) = cos (2Ωt), β y = 0, with the overmodulation frequency Ω = ω B /250. By combining paths one can generate any type of trajectories in 2D (and, by an obvious generalization of the above discussion, in 3D): Plot (c) in Fig. 1 displays a β-shaped trajectory, where even a turning point has been "drawn". In all these numerical experiments the diffusion is very small, the width of the wavepacket varies only slightly during the evolution. New kinds of dynamics can be obtained by using an overmodulation whose amplitude varies slowly also in space, i.e A x (t) → A x (x, t) in Eq. ( 1). This can be realized [8,36] by adding a second laser beam with a different spatial period k ′ L , which produces a spatial modulation of the lattice amplitude corresponding to the beat note of the two spatial frequencies. The potential is then

A u (u, t) = sin(ku) (sin ω B t + β u ) (13)
where k = (k L -k ′ L )/k L . In the limit |k| ≪ 1, sin(ku) ≈ ku and the velocity of the wavepacket, which is propor-tional to the modulation amplitude, varies linearly with the position, as one can deduce from Eq. ( 11): v u = M 1 σku (taking β u = 0). All parts of the wavepacket, whatever their positions, will move towards the origin (0, 0), and the closer of the origin it is, the smallest its velocity. This effect can thus be used to concentrate a large wavepacket, or various wavepackets distributed at arbitrary positions, on a few potential wells. Fig. 2(a) shows a numerical experiment in which such a concentration is realized. Each colored spot represents a wavepacket, or a part of a large wavepacket. As times goes by, the different spots are seen to converge to the same position. Plot (b) in Fig. 2 shows the evolution of the total spatial dispersion ( ∆r 2 1/2 ). This unavoidable dispersion limits the maximum time during which the overmodulation can be applied, and thus the maximum density which can be obtained.

One can also combine temporal and spatial modulations to produce a rotation of a wavepacket. Consider a cigar-shape wavepacket as shown in Fig. 3(a). Inducing a uniform rotation around the origin (0, 0) means to give a slice at position r a local velocity v perpendicular to r. This can be done by producing a modulation of the form In conclusion, this paper illustrates the almost unlimited power of overmodulated optical lattices to manipulate atom wavepackets. The technique is immediately applicable to state-of-art experiments, and that can play an important role in preparing complex initial state for fundamental studies of quantum dynamics, but might also useful for playing with atomic qbits in the realm

A x = -sin(ky) sin (ω B t + β x ) ≈ -ky sin (ω B t + β x ) A y = sin(kx) sin (ω B t + β y ) ≈ kx sin (ω B t + β y ) .

Figure 1 :

 1 Figure 1: (Color online) Arbitrary wavepacket motion in two dimensions. The plots display the probability of presence |Ψxy(t)| 2 integrated on time, and the arrows indicate the sens of the motion. (a) Square path formed of four straight lines. (b) ∞-path, obtained by choosing αx = cos (Ωt), αy = cos (2Ωt), βx = βy = 0. Plot (c) is made is made by combining straight lines and arcs. Parameters of the potential are Vx,y = 2.5 and Fx,y = 0.2 (note the different scales in each plot).

Figure 2 :

 2 Figure 2: (Color online) The left plot on the top row displays a few wavepackets (or different slices of a large wavepacket) arbitrarily distributed in space. The potential defined by Eq. (13) sets the different wavepackets in motion with a velocity directed towards the origin (situated close to the upright corner) whose amplitude increases with the distance from the origin. The slices are thus progressively concentrated around the origin. Plot (b) show the evolution of the total spatial dispersion with respect to the origin. Parameters of the potential are Vx,y = 2.5, Fx,y = 0.25 and k/kL = 0.02.

Figure 3

 3 Figure 3 shows an example of wavepacket rotation produced by this technique.In conclusion, this paper illustrates the almost unlimited power of overmodulated optical lattices to manipulate atom wavepackets. The technique is immediately applicable to state-of-art experiments, and that can play an important role in preparing complex initial state for fundamental studies of quantum dynamics, but might also useful for playing with atomic qbits in the realm

Figure 3 :

 3 Figure 3: (Color online) Rotation of the wavepacket, obtained by using combined spatial and temporal overmodulations (cf. text).