A selection theorem for treeable sets^{∗}

Greg Hjorth

November 18, 2006

Abstract

A smooth treeable equivalence relation admits a selector; an essentially countable treeable equivalence relation admits a Borel section meeting each class in a countable non-empty set.

1 Introduction

In the literature of Borel equivalence relations, treeable equivalence relations have largely been studied in the context of a countable vertex set. The purpose of this brief note is to extract the definition from that narrow context, and consider how the notion behaves when we allow trees with possibly uncountable splitting.

Definition A set A in a Polish space is treeable if there is a Borel R ⊂ A × A such that provides the structure of a tree – which is to say, R is symmetric and irreflexive, connected, and without cycles. In this paper it is convenient to use the notions of effective descriptive set theory, in the sense of [6], and naturally enough, we say that the treeing is Δ_{1}^{1}(x) if R ∈ Δ_{1}^{1}(x).

Theorem 1.1 Let x ∈ 2^{ω}, A ⊂ 2^{ω} in Σ_{1}^{1}(x), A non-empty and Δ_{1}^{1}(x) treeable. Then A ∩ Δ_{1}^{1}(x) is non-empty.

Definition An equivalence relation E on a Polish space X is treeable if there is a Borel R ⊂ X × X which provides a forest whose connected components are the E-classes – that is to say, R is symmetric and irreflexive, without cycles, and xEy if and only if there is a sequence x_{0} = x, x_{1}, ..., x_{n} = y with each (x_{i}, x_{i+1}) ∈ R.

An equivalence relation E is smooth if there is a Borel function θ from X to some Polish space with

x_{1}Ex_{2}

if and only if θ(x_{1}) = θ(x_{2}).

An equivalence relation E is essentially countable if and only if there is a Borel function θ from X to some Polish space Y, equipped with a Borel equivalence relation F all of whose classes are countable, such that

x_{1}Ex_{2}

if and only if θ(x_{1})F θ(x_{2}).

Note that any treeable equivalence relation E is necessarily Borel, since there will be a unique loopless path connecting x to y if they are equivalent, and we can apply the theorem on the projection of Borel sets in the plane with countable sections (see 18.10 [5]).

Corollary 1.2 If E is treeable and smooth, then there is a Borel selector – that is to say, a Borel set meeting each equivalence class in exactly one point.

∗Key words and phrases: Borel equivalence relations, treeable equivalence relation, selection theorem, uniformization. 2000 Mathematics Subject Classification: Primary 03E15

Corollary 1.3 If E is treeable and essentially countable, then there is a Borel set meeting each equivalence class in a countable non-empty set.

The proof of 1.2 from 1.1 is short. We may assume E lives on 2^{ω} and there is some single y ∈ 2^{ω} such that the indicated θ and R are in Δ_{1}^{1}(y). We may also assume θ : 2^{ω} → 2^{ω}.

Then for any z ∈ 2^{ω} we can let S(z) be the first element, in some canonical enumeration of Δ_{1}^{1}(θ(z), y) which meets [z]_{E}. By 1.1, such exists. It depends only on θ(z), and hence only on [z]_{E}. I leave to the reader the routine, though tedious, verification z ↦ S(z) is Borel.

The proof of 1.3 is entirely parallel. Given θ as indicated, we again define S(z) to be the first element of Δ_{1}^{1}(θ(z), y) which meets [z]_{E}. Since

{S(z′) : z′Ez}

is always countable, the set {S(z) : z ∈ 2^{ω}} will meet each class in a countable non-empty set.

We give the proof of 1.1 in the next section. In the final section we observe that a treeable equivalence relation induced by the continuous action of a Polish group is essentially countable – answering a question raised in [2].

2 proof

We make use of the language and armory of Gandy-Harrington forcing.

Notation Let P denote the partial order of non-empty Σ_{1}^{1} subsets of 2^{ω} ordered under inclusion and let P_{2} denote the partial order of non-empty Σ_{1}^{1} subsets of 2^{ω} × 2^{ω} likewise ordered under inclusion

The reader should refer to [7] or [1] for a proof of the following.^{1}

Proposition 2.1 (1) If G ⊂ P is sufficiently generic filter, then there will be a unique element in

⋂ G.

(2) If G ⊂ P_{2} is V -generic, then there will be unique V -generic G_{ℓ}, G_{r} ⊂ P with

G ⊂ G_{ℓ} × G_{r}.

Notation For G a sufficiently generic filter on P, x(G) denotes the unique real in its intersection. For G ⊂ G_{ℓ} × G_{r} as above,

x_{r}(G) = x(G_{r}),
x_{ℓ}(G) = x(G_{ℓ}).

We will also at times have need to consider the product forcing,

P × P.

Then for any V -generic G ⊂ P × P it is a standard fact for product forcing that there are V -generic G_{ℓ}, G_{r} ⊂ P with G = G_{ℓ} × G_{r}, whence we again let x_{r}(G) = x(G_{r}), x_{ℓ}(G) = x(G_{ℓ}).

Lemma 2.2 If B ∈ P, y ∈ 2^{ω},

B ⊩ y ∈ Δ_{1}^{1}(x(Ġ)),

then y ∈ Δ_{1}^{1}.

1As a forewarning on terminology [7] drops credit to Harrington and calls P Gandy forcing while [1] uses the Gandy-Harrington topology, recasting the results in the language of topological spaces and the Baire category theorem.

Proof We can find A ∈ Σ_{1}^{1} and refine B to B′ ∈ P such that

B′ ⊩ {z : (z, x(Ġ)) ∈ A} = {y}.

Then for all n

y(n) = 0

if and only if there exists

(z, a) ∈ A

with

z(n) = 0.

Thus y is a Σ_{1}^{1} singleton, and hence Δ_{1}^{1} as required. □

Similarly:

Lemma 2.3 If B ∈ P_{2} and

B ⊩_{P_{2}} y ∈ Δ_{1}^{1}(x_{ℓ}(Ġ), x_{r}(Ġ)),

then y ∈ Δ_{1}^{1}.

With these weapons in hand, we can start on the proof of the theorem. For notational convenience let us in fact assume A ∈ Σ_{1}^{1} and R ∈ Δ_{1}^{1}. The general case relativizes without disruption, simply because the relevant facts for P and P_{2} carry through to their relativized versions. The statement that R provides a treeing of A is easily checked to be Π_{2}^{1} and hence absolute to generic extensions.

We will assume that A ∩ Δ_{1}^{1} is empty and fight our way through to a contradiction.

Definition We say that y ∈ A is critical if there exist B_{0}, B_{1} ∈ P below A with (B_{0}, B_{1}) forcing the shortest path in R from x_{ℓ}(Ġ) to x_{r}(Ġ) passes through y.

Lemma 2.4 There are only countably many critical reals.

Proof If y is critical, then any sufficiently generic G ⊂ P ×P below the relevant (B_{0}, B_{1}) has y ∈ Δ_{1}^{1}(G). Since P × P exists up to isomorphism in L_{ω_{2}^{ck}}, any such y will be in the countable set

L_{ω_{1}^{ck}}[G].
□

Notation For x, y ∈ A let f(x, y) denote the first element after x in the shortest R-path from x to y and let l(x, y) denote the last element before y.

f(x, y) and l(x, y) will be well defined when x ≠ y by our assumption of R treeing A. Our assumption that A ∩ Δ_{1}^{1} = 0 entails that for any y and B ≤ A

B ⊩ f(y, x(Ġ)) well defined.

Lemma 2.5 There exists a critical real.

Proof Otherwise choose y_{0} ∈ A arbitrary. By our supposition of the lemma failing, we have for all B_{0}, B_{1} ∈ P below A and C Borel,

B_{0} ⊩ f(y_{0}, x(Ġ)) ∈ C

if and only

B_{1} ⊩ f(y_{0}, x(Ġ)) ∈ C.

Varying over all possible C, we obtain some y_{1} such that

A ⊩ f(y_{0}, x(Ġ)) = y_{1}.

Repeating the same consideration round after round, we obtain a sequence of adjacent points, y_{0}, y_{1}, y_{2}, ... with at each i

A ⊩ f(y_{i}, x(Ġ)) = y_{i+1}.

This at last pushes x(Ġ) to be infinitely far away from y_{0}, and a contradiction on R treeing A in the generic extension. □

Notation Let T_{0} be the convex hull of the critical points; in other words, T_{0} is the smallest subtree of (A, R) containing all the critical points. T_{0} is again countable. For y ∈ A let

c(y)

be the closest point in T_{0} to y. In the case y ∉ T_{0} we let

s(y) = l(y, c(y)).

For y ∈ T_{0} we just let s(y) = y, though this case will have only nominal interest for us.

Hence s(y) is the last non-critical point on the path from y back to the convex closure of the set of critical points.

Notation For y_{0}, y_{1} ∈ A set

y_{0}Ey_{1}

if s(y_{0}) = s(y_{1}).

Lemma 2.6

(A, A) ⊩_{P×P} x_{ℓ}(Ġ)E̸x_{r}(Ġ).

Proof Otherwise we could find some single y_{1} ∉ T_{0} and B ≤ A with

B ⊩_{P} s(x(Ġ)) = y_{1}.

Then since y_{1} is not critical,

(B, B) ⊩_{P×P} l(x_{ℓ}(Ġ), y_{1}) = l(x_{r}(Ġ), y_{1}).

Continuing in the same manner we find y_{2}, y_{3}, y_{4}, ... such that at each i,

B ⊩_{P} l(x(Ġ), y_{i}) = y_{i+1},

with the same contradiction as in 2.5. □ Lemma 2.7

A × A ⊩_{P_{2}} x_{ℓ}(Ġ)Ex_{r}(Ġ).

Proof Or else we obtain some B ≤ A × A and some y_{0} ∈ T_{0} with B forcing the least path from x_{ℓ}(Ġ) to x_{r}(Ġ) passing through y_{0}, which gives y_{0} by 2.3, and a contradiction to our assumption A ∩ Δ_{1}^{1} = 0. □

Now events really do screech into contradiction. From 2.6 we can find some B_{0}, B_{1} ≤ A and Borel C with

B_{0} ⊩_{P} x(Ġ) ∈ C,
B_{1} ⊩_{P} x(Ġ) ∉ C,

yielding

B_{0} × B_{1} ⊩ x_{ℓ}(Ġ) ∈ C, x_{r}(Ġ) ∉ C

from projection, in violation of 2.7.

3 An after thought on Polish group actions

We need a couple of notions from the theory of Borel reducibility. [3] is one place where more background can be found.

Definition An equivalence relation E on Polish X is essentially countable if there is a Borel equivalence relation F on Polish Y with all its classes countable and E ≤_{B} F – which is to say, for some Borel θ : X → Y

x_{0}Ex_{1} ⇔ θ(x_{0})F θ(x_{1}).

From now on assume that E is a treeable equivalence relation arising from the continuous action of a Polish group G on a Polish space X, so that x_{1}Ex_{2} if and only if

∃g ∈ G(g · x_{1} = x_{2}).

Let R be the Borel treeing. We will work towards showing E essentially countable.

Notation For V ⊂ G open and

∀^{∗}g ∈ V (...g...)

indicates that for a relatively comeager collection of g ∈ V we have (...g...).

Notation For x_{1}Ex_{2}, let p(x_{1}, x_{2}) denote the shortest R-path from x_{1} to x_{2}.

Lemma 3.1 For all x ∈ X there exists non-empty open V_{0}, V_{1}, W_{0}, W_{1} ⊂ G such that ∀^{∗}g_{0} ∈ V_{0}∀^{∗}g_{1} ∈ V_{1}∀^{∗}h_{0} ∈ W_{0}∀^{∗}h_{1} ∈ W_{1}

p(g_{0} · x, h_{0} · x) intersects p(g_{1} · x, h_{1} · x).

Proof Assuming failure of the lemma we get that for a comeager collection of (g_{0}, g_{1}, h_{0}, h_{1}) ∈ G^{4}

p(g_{0} · x, h_{0} · x) does not intersect p(g_{1} · x, h_{1} · x).

Taking sufficiently generic choices of these group elements can find x_{0} = g_{0} · x, x_{1} = g_{1} · x and y_{0} = h_{0} · x, y_{1} = h_{1} · x such that p(x_{i}, y_{j}) does not intersect p(x_{l}, y_{k}) (i, j, l, k ∈ {0, 1}) when i ≠ l and j ≠ k.

Let x′_{0} be the last common point on p(x_{0}, y_{0}), p(x_{0}, y_{1}). Similarly take x′_{1} to be the last common point on p(x_{1}, y_{0}), p(x_{1}, y_{1}), y′_{0} the last common point on p(y_{0}, x_{0}), p(y_{0}, x_{1}), and y′_{1} the last common point on p(y_{1}, x_{0}), p(y_{1}, x_{1}).

Then we have a cycle obtained by adjoining

p(x′_{0}, y′_{0})^{⌢}p(y′_{0}, x′_{1})^{⌢}p(x′_{1}, y′_{1})^{⌢}p(y′_{1}, x′_{0}),

with a nasty rebuttal of our assumption that R was a treeing. □

Corollary 3.2 For all x ∈ X there exists non-empty open V, W ⊂ G such that ∀^{∗}(g_{0}, g_{1}) ∈ V^{2}∀^{∗}(h_{0}, h_{1}) ∈ W^{2}

p(g_{0} · x, h_{0} · x) intersects p(g_{1} · x, h_{1} · y).

Proof Referring back to 3.1, take V, V′, W, W′ to be non-empty open subsets of V_{0}, V_{1}, W_{0}, W_{1} such that for some m, n ∀^{∗}g ∈ V ∀^{∗}g′ ∈ V′∀^{∗}h ∈ W ∀^{∗}h′ ∈ W′ we have the n^{th} element of p(g · x, h · x) equals the m^{th} element of p(g′ · x, h′ · x). Then V and W are as required. □

Definition For V, W ⊂ G basic open and non-empty, x ∈ X, y ∈ [x]_{E}, we say that (V, W, x) conquers y if ∀^{∗}g ∈ V ∀^{∗}h ∈ W the point y appears somewhere along p(g · x, h · x). It follows from 3.2 that for every x there will be some y, W, V with (V, W, x) conquering y. We let T_{x} be the convex hull of the set of points

{y ∈ [x]_{E} : ∃V, W ((V, W, x) conquers y)}.

Lemma 3.3 T_{x} is always a countable non-empty set.

Proof Non-empty by the last lemma and countable by the second countability of G. □

Lemma 3.4 If x_{0}Ex_{1} then T_{x_{0}} = T_{x_{1}}.

Proof Since if (V_{0}, W_{0}, x_{0}) conquers y then we can choose non-empty basic open V_{1}, W_{1} with

V_{1} · x_{1} ⊂ V_{0} · x_{0},
W_{1} · x_{1} ⊂ W_{0} · x_{0}.
□

Lemma 3.5 The set of x with x ∈ T_{x} is Borel.

Proof Let B ⊂ X × X be the set of (x, y) for which there exists V, W with (V, W, x) conquering y. Since the assignment

(x, g, h) ↦ p(g · x, h · x)

is Borel as a function from X to X^{<∞}, it follows from the preservation of Borel sets under the categoricity quantifiers ∀^{∗}, ∃^{∗} (see 16.1 [5]) that B is Borel. x ∈ T_{x} if and only if there are y_{0}, y_{1} with (x, y_{0}), (x, y_{1}) ∈ B and the unique shortest R-path from y_{0} to y_{1} passes through x.

We finish by using that the projection of a Borel set in the plane with countable sections is Borel. □

Lemma 3.6 There is a Borel function

x ↦ θ(x)

such that θ(x) ∈ T_{x}.

Proof By the uniformization of Borel sets with countable sections. □

Finally we let X_{0} = {x : x ∈ T_{x}}. We have seen this is a Borel subset of X, and hence a standard Borel space in its own right, and thus allowing a compatible topology under which it is Polish (see 13.4 [5]). The lemmas above established that E has countable classes when restricted to X_{0} and θ witnesses E ≤_{B} E|_{X_{0}}.

The ebullient conjectures of [3] suggest the following:

Question Let E be treeable. Must it be the case that either:

(I) E essentially countable, or (II) E_{1} ≤_{B} E?

References

[1] L. Harrington, A.S. Kechris, A. Louveau, A Glimm-Effros dichotomy for Borel equivalence relations, Journal of the American Mathematical Society, vol. 3 (1990), 903–928.

[2] G. Hjorth, Non-treeability for product group actions, to appear in the Israel Journal of Mathematics.

[3] G. Hjorth, A.S. Kechris, New dichotomies for Borel equivalence relations, Bulletin of Symbolic Logic, vol. 3 (1997), 329–346.

[4] S. Jackson, A.S. Kechris, A. Louveau, Countable Borel equivalence relations, Journal of Mathematical Logic, vol. 2 (2002), 1–80.

[5] A.S. Kechris, Classical Descriptive Set Theory, Springer-Verlag, New York, 1995.

[6] Y.N. Moschovakis, Descriptive Set Theory, Studies in Logic and the Foundations of Mathematics, 100. North-Holland Publishing Co., Amsterdam-New York, 1980.

[7] G.E. Sacks, Higher recursion theory, Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1990.