NON-STANDARD APPLICATIONS OF GANDY-HARRINGTON

Greg Hjorth

greg@math.ucla.edu

April 21, 2001, Las Vegas §1. The object

Definition The Σ ∼_{1}^{1} subsets of a Polish space X are the projections of closed subsets of X ×ℕ^{ℕ}. In the case that X is recursive – for instance, X = ℕ^{ℕ}, infinite sequences of natural numbers, or X = ℝ – we talk about the (lightfaced) Σ_{1}^{1} sets, which can be described as the projections of closed sets C ⊂ X × ℕ^{ℕ} which have a “computable” description.

We can also define Σ_{1}^{1}(R), which is to say Σ_{1}^{1} relative to some oracle R. Since for any fixed R the class Σ_{1}^{1}(R) has structural properties virtually indistinguishable from Σ_{1}^{1}, it is true as a practical matter that a proof of a theorem for Σ_{1}^{1} will typically relativize and give a theorem even for Σ ∼_{1}^{1}.

Note here: Σ ∼_{1}^{1} was considered classically. The Σ_{1}^{1} sets however cannot really be viewed as classical objects.

Gandy-Harrington 2

Definition For X a recursive Polish space, we let P be the partial ordering of all non-empty lightfaced Σ_{1}^{1} sets A ⊂ X ordered by inclusion.

Here one has that for any reasonably generic filter^{1} G ⊂ P there will be a unique point

x(G) ∈ ⋂_{A∈G} A.

For future reference, fix C = (D_{n})_{n∈ℕ} a countable collection of dense^{2} subsets of P such that for any filter G meeting every D_{n} we do indeed have some

x(G) ∈ ⋂ G.

We can also view this as providing a topology on X, whose basis consists of the Σ_{1}^{1} sets. This topology falls short of being Polish, but it has other desirable properties, such as satisfying the Baire category theorem.

1I.e. closed downward and any two elements in G are compatible, in the sense that there is a third element in G below them both.

2I.e. for D ∈ C and p ∈ P there is q ∈ D with q ≤ p

Gandy-Harrington 3

§2. An example of a “standard” application

Just for the purposes of illustration, let us go through a proof of the perfect set theorem for Σ_{1}^{1} sets.

Theorem Let A ∈ Σ_{1}^{1}. Then either:

(I) |A| ≤ ℵ_{0}; or

(II) A contains a homeomorphic copy of {0, 1}^{ℕ} (Cantor space).

Sketch of Proof.

We let B = {x ∈ X : {x} ∈ Σ_{1}^{1}}, the set arising as the union of all Σ_{1}^{1} singletons.

Claim: X \ B is Σ_{1}^{1}.

Proof of claim: Here it is a routine calculation to show that {x} ∈ Σ_{1}^{1} if and only if {x} ∈ Δ_{1}^{1}. (A set is said to be Δ_{1}^{1} if it and its complement are both Σ_{1}^{1}) ¿From this one can show by another routine calculation that X \ B is indeed Σ_{1}^{1}. (Claim□)

Usually in these kinds of arguments there will be some step where the set of “complicated points” is shown to be Σ_{1}^{1}, even though it initially looks more complicated. Here it is straightforward calculation, but in general it can be involved, for instance making use of “Π_{1}^{1} reflection.”

Now there is a split in cases.

Case(I) A ⊂ B.

Then we are immediately finished, since every element of A is a Σ_{1}^{1} singleton, and there are only countably many (lightfaced) Σ_{1}^{1} singletons.

Now we go to the other case. Here we will find a way to build a “perfect set” of generic objects in A \ B. This will give us a homeomorphic copy of Cantor space.

Case(II) A \ B ≠ ∅.

We define a array of elements in P, (p_{s})_{s∈2^{<ℕ}}, indexed by finite binary sequences, such that

(0) each p_{s} ⊂ A \ B; we work below the complicated part of A;

(1) p_{s} ≤ p_{t} for s ⊃ t; that is to say, as the binary sequences get longer, the Σ_{1}^{1} sets get smaller;

(2) if s ∈ 2^{n} (i.e. s has length n), then p_{s} ∈ D_{n};

(3) for s ≠ t of the same length, p_{s} ∩ p_{t} = 0; that is to say, incompatible binary sequences are associated with disjoint binary sequences.

We can start the construction with

p_{empty sequence} = A \ B.

It is routine to diagonalize in to meet the n^{th} dense set at stage n.

The part of this that might be problematic is (3). But here we know that whenever we have some given p_{s} ⊂ A \ B, it must contain two elements, or it would consist of a Σ_{1}^{1} singleton and hence be in B; and so we can divide it up by two disjoint open sets.

In the end we define for any infinite binary sequence w ∈ 2^{ℕ} the filter

G_{w} = {q : ∃n(p_{w|n} ≤ q)}

generated by the conditions associated with the finite initial segments of w.

Each such G_{w} is “sufficiently generic”, and one can show that the function assigning to w the real defined by its generic filter,

w ↦ x(G_{w}),

is continuous. And thus

{x(G_{w}) : w ∈ 2^{ℕ}}

is a homeomorphic copy of Cantor space. □

Corollary If A is an uncountable Σ_{1}^{1}, then we may continously inject some perfect^{3} Polish space into A.

Note: We used a canonical example. It is not so clear how this proof might fly if (to imagine some crazy counterfactual) we didn’t have a canonical perfect space, 2^{ℕ}, to inject into A.

3A space is perfect if it has no isolated points.

§3. No canonical example

Definition A point x ∈ X is low if ω_{1}^{ck(x)} (the supremum of the computable in x wellorders of ℕ) equals ω_{1}^{ck}.

Fact x is low if and only if for every A ⊂ X in Σ_{1}^{1} either x ∈ A or there is some C ∈ Σ_{1}^{1} with x ∈ C and

A ∩ C = ∅.

Theorem (Gandy) Every non-empty Σ_{1}^{1} set contains a low member.

Proposition (Folk) The set of low elements of a recursive Polish space equipped with the topology of Σ_{1}^{1} sets is a Polish space.

Now we can give a different proof of the corollary from before:

Gandy-Harrington 12

Theorem If A is a Σ_{1}^{1} set, then either (I) |A| ≤ ℵ_{0}, or (II) there is a perfect Polish space Y and continuous injection

ρ : Y ↪ A.

Proof Again let B be the collection of Σ_{1}^{1} singletons. If A ⊂ B we at once obtain |A| ≤ ℵ_{0}.

Otherwise we can argue that A \ B is again Σ_{1}^{1}. And hence the space

{x ∈ A \ B : x is low}

is a Polish space in the topology generated by the Σ_{1}^{1} sets.

By removing B we have ensured there are no isolated points, and so this is exactly the Y we need in (II). □

§4. In the context of group actions

¿From now on assume that G is a recursive Polish (topological) group, and X is a recursive Polish space on which G acts in a continuous and recursive manner.

Definition For V ⊂ G open and B ⊂ X arbitrary, we define the Vaught transforms B^{ΔV} and B^{∗V}:

B^{ΔV}

is the set of x ∈ X for which there is a relatively non-meager collection of g ∈ V with g · x ∈ B.

B^{∗V}

is the set of x ∈ X for which there is a relatively comeager collection of g ∈ V with

g · x ∈ B.

Here is the analog of the folk lemma about low points forming a Polish space. We can use this to prove dichotomy theorems about Polish group actions in cases where there is no canonical example in the complicated case, corresponding to (II).

Proposition Let G be a recursive Polish group and X a recursive Polish G-space. Let

X_{∗low} = ({x ∈ X : x low})^{∗G}.

Then X_{∗low}, in the topology generated by the sets of the form A^{ΔV} where A ⊂ X is Σ_{1}^{1} and V ⊂ G is open, is a Polish G-space.

§5. Using this proposition

Definition A Borel equivalence relation on a Polish space is said to be essentially countable if it is Borel reducible to an equivalence relation all of whose equivalence classes are countable.

This turns out to being equivalent (Kechris) to the existence of a Borel function which has disjoint range on different equivalence classes and has countable image on each individual equivalence class.

There is no straightforward dichotomy theorem which states either an equivalence relation is essentially countable or it is above a canonical counterexample. There is not even such a theorem if we restrict our attention to Borel equivalence relations induced by the continuous actions of Polish groups.

There is no canonical exception.

Definition Let G be a Polish group and X a Polish G-space. The action is said to be stormy if there is no x ∈ X and V ⊂ G open and nonempty having the induced map

V → V · x
g ↦ g · x

open.

One can show, with a bit of work, that stormy actions give rise to orbit equivalence relations which are not essentially countable.

Theorem Let G be a Polish group and X a Polish G-space. Assume the orbit equivalence relation is Borel (as a subset of X × X). Then exactly one of:

(I) the orbit equivalence relation is essentially countable, or (II) there is a stormy Polish G-space Y and continuous G-embedding

ρ : Y → X.

The outline of the proof: As usual, assume everything in sight is effective ( E_{G} lightface Δ_{1}^{1}, action is recursive). Then argue that either we somehow chop up the orbits into countably many pieces, and obtain reduction to a countable equivalence relation, or we can go to X_{∗low} in the topology from before and obtain a relatively open subset on which the action is stormy.

Corollary to the proof IF G is a recursive Polish group, X is a recursive Polish G-space with E_{G} ∈ Δ_{1}^{1}, and E_{G} is essentially countable,

THEN it is reducible to a Δ_{1}^{1} equivalence relation by a Δ_{1}^{1} function.

This consequence would presumably not have been obvious.

X_{∗low} has also been used in another dichotomy theorem, relating to the notion of classifiable by countable structures. For instance, if E_{G} is Δ_{1}^{1} (and various natural assumptions are made), then if it is classifiable by countable structures then we can achieve the classification in a Δ_{1}^{1} manner.