INJECTIVE IMAGES OF COANALYTIC SETS

Greg Hjorth

greg@math.ucla.edu

March 5, 1999 Berkeley §1. DEFINITIONS

1.1 Definition A separable space X is said to be Polish if it allows a complete metric. A subset B of a Polish space is Borel if it appears in the σ-algebra generated by the open sets.

1.2 Examples

(i) ℝ in the usual topology is Polish.

(ii) ℕ^{ℕ}, the space of functions with the topology of pointwise convergence, is Polish.

Let B = {f : ∃N∀n > N(f(n + 1) ≥ f(n))} be the set of all eventually increasing functions. B is Borel (in fact, F_{σ} = Σ ∼_{2}^{0}) since it is a countable union of closed sets.

(iii) ℚ in the usual topology is not Polish, since any countable Polish space contains an isolated point.

1.3 Definition A subset of A of a Polish space X is analytic, or Σ ∼_{1}^{1}, if there is a Polish Y, Borel B ⊂ Y, continuous

f : B → X

with A = f[B] the image of B under f. A subset C ⊂ X is coanalytic, or Π ∼_{1}^{1}, if its complement X \ C is analytic.

Obviously the Borel sets are included in the analytic and the coanalytic.

Coanalytic sets 4

1.4 Examples

(i) Let LO be the collection of all linear orderings on ℕ with subbasic open sets of the form

{≺∈ LO : k ≺ l}.

This is Polish, and the set of linear orderings with an infinite descending chain is analytic but not Borel.

(ii) Let C([0, 1]) be the continuous functions from the unit interval. This is a Polish space (under the topology generated by the sup norm) and the set of functions differentiable in the interior (0, 1) is coanalytic and not Borel.

§2. CLASSICAL RESULTS

2.1 Definition Baire space is the space ℕ^{ℕ} of all functions from the natural numbers to the natural numbers with the topology of point wise convergence. That is to say, the basic open sets have the form

{f ∈ ℕ^{ℕ} : ∀n < K(f(n) = g(n))}

where K ∈ ℕ and g : ℕ → ℕ.

2.2 Theorem (Luzin; Lusin-Souslin^{1}) A subset of a Polish space is Borel if and only if it is the continuous injective image of a closed subset of Baire space.

1Texts differ in their choice of attribution: see for instance Kechris’ Classical Descriptive Set Theory, Springer-Verlag Graduate Texts in Mathematics 156, New-York, 1995.

Some remarks about the “only if”

The proof can be thought of as a variation of the fact that any first order theory T admits a “Skolemization” by a universally axiomatizable theory – that is to say there is a theory T′ ⊃ T all of whose axioms contain a single universal quantifier, and such that the reducts of T′ models to L(T) are exactly the models of T.

In general there will be many models of T′ which expand a given model of T, and so the map is not one to one.

But in the present situation there is a canonical well order of ℕ, which can be thought of as the domain of our “models” in the Borel set. If we only look at models of T′ where the Skolem functions always choose the least natural number possible as a witness, we can reassert injectivity.

For concreteness suppose our Borel set is

B = ⋃_{n∈ℕ^{+}} C_{n},

where each C_{n} is closed. Assume for notational convenience^{2} that the space is zero-dimensional and that we can find basic clopen sets (U_{s})_{s∈ℕ^{<ℕ}}, where

U_{∅} = whole space,

d(U_{s}) ≤ (lh(s))^{−1},

U_{s} = ⋃_{i∈ℕ} U_{s⌢i},

i ≠ j ⇒ U_{s⌢i} ∩ U_{s⌢j} = ∅.

2In the general case we need to consider each U_{s} being an the intersection of an open set and a closed set.

Coanalytic sets 8

Then we can let C_{B} be the space of all triples

(f, k, g) ∈ ℕ^{ℕ} × ℕ × ℕ^{ℕ}

where (i) U_{f|n} ∩ C_{k} ≠ ∅ all n; (ii) g(i) = 0 all i ≥ k; (iii) at each j < k we have that g(j) is the least m such that

C_{j} ∩ U_{f|m} = ∅.

Since ℕ^{ℕ} × ℕ × ℕ^{ℕ} is homeomorphic to ℕ^{ℕ}, we can think of C_{B} as a closed subset of Baire space. The structure of the definition implies that for each x ∈ B there will be a unique (f_{x}, k_{x}, g_{x}) ∈ C_{B} with

x = ⋂_{n∈ℕ} U_{f_{x}|n}.

2.3 Theorem (Lusin-Souslin) Every analytic set is the continuous image of a closed subset of Baire space.

2.4 Theorem (Classical) Let D be a countable discrete space.

Every uncountable Borel set is the continuous injective image of the disjoint union of ℕ^{ℕ} and D.

Idea of the proof for ℕ^{ℕ} ˙⋃D

In light of Luzin’s theorem, wish to show that every uncountable closed subset of ℕ^{ℕ} is the continuous one to one image of ℕ^{ℕ} ˙⋃D.

Let C ⊂ ℕ^{ℕ} be closed and uncountable. We can let O_{1} ⊂ ℕ^{ℕ} be a maximal open set such that C ∩ O_{1} is countable. (Uses ℕ^{ℕ} separable.)

C \O_{1} is without isolated points and it suffices to show that modulo some countable set it is the continuous injective image of Baire space.

FACT: If Y is Polish and Y_{0} ⊂ Y is countable, then Y \ Y_{0} is again Polish. For instance, Baire space is homeomorphic to {f ∈ 2^{ℕ} : ∃^{∞}n(f(n) ≠ 0)}.

Thus after subtracting off a further countable set C_{0} we may assume that C \ (O_{1} ∪ C_{0}) is nowhere compact. Hence we have that C\(O_{1}∪ C_{0}) is Polish, zero-dimensional, no where compact, and hence homeomorphic to Baire space.

§3. SIERPINSKI’S QUESTION

3.1 Question (Sierpinski; 1936) Is there a subset of Baire space having every uncountable analytic set as its continuous injective image?

Coanalytic sets 12

3.2 Theorem (Slaman; 1997[?]) Yes.

3.3 Theorem (Slaman) BUT there is no analytic set having every uncountable analytic set as its continuous injective image.

Ted Slaman’s proof made serious use of the axiom of choice in constructing the “injectively universal set”. This prompted the further question of whether one could obtain a definable example.

§4. A NEW QUESTION

4.1 Definition We inductively define the projective hierarchy, commencing with the Σ ∼_{1}^{1} sets defined above. We say that a set is Π ∼_{n}^{1} if it is the complement of a Σ ∼_{1}^{1} set and that a set is Σ ∼_{n+1}^{1} if it is the continuous image of a Π ∼_{n}^{1} set.

Note that

Π ∼_{n}^{1}, Σ ∼_{n}^{1} ⊂ Σ ∼_{n+1}^{1} ∩ Π ∼_{n+1}^{1}.

We let Δ ∼_{n}^{1} = Π ∼_{n}^{1} ∩ Σ ∼_{n}^{1}.

Thus one can reasonably ask whether Slaman’s theorem can be proved using say a projective set.

4.2 Theorem There is Π ∼_{1}^{1} (that is to say coanalytic) set having every uncountable Σ ∼_{1}^{1} set as its continuous injective image.

Idea Let U ⊂ ℕ×ℕ^{ℕ} be universal (light faced) Σ_{1}^{1}, so that the Σ_{1}^{1} subsets of ℕ^{ℕ} are exactly those of the form

{x ∈ ℕ^{ℕ} : (n, x) ∈ U}.

For x ∈ ℕ^{ℕ} let O^{x} = {n : (n, x) ∈ U}. Finally let H = {O^{x} : x ∈ ℕ^{ℕ}}.

Then for D a countably infinite discrete set, H ˙⋃D succeeds.^{3} One uses about H that:

3In fact we do not need the countable set D, since the set of hyperjumps of recursive reals is an infinite, discrete, clopen subset of H.

(i) it is zero dimensional;

(ii) H is homeomorphic to ℕ × H;

(iii) ℕ^{ℕ} is the continuous injective image of H (via O^{x} ↦ x);

(iv) for any A ⊂ ℕ^{ℕ} analytic there is relatively closed C_{A} ⊂ H having A as its one to one continuous image. Namely: If

A = {x : (n, ⟨x, z_{0}⟩) ∈ U},

then we can take

C_{A} = {O^{⟨x,z_{0}⟩} : x ∈ ℕ^{ℕ}, n ∈ O^{⟨x,z_{0}⟩}}.

§5. GENERALIZATIONS

Under appropriate large cardinal or determinacy assumptions we can hope to extend these results to higher levels in the projective hierarchy.

5.1 Theorem Assume every uncountable Π ∼_{1}^{1} set contains a perfect subset.^{4} (Equivalently: ℵ_{1} is inaccessible in L[z] for every z ⊂ ℕ.) Then every uncountable Σ ∼_{2}^{1} set is the continuous injective image of H ˙⋃D.

4A perfect set is an closed, non-empty set with no isolated points. Every perfect set contains a homeomorphic copy of Cantor space.

Plainly this is not provable in ZFC alone – since H contains a perfect set, the conclusion would imply that every coanalytic set contains a perfect set.

Even in the more modest sense that there just be some “injectively universal Π ∼_{1}^{1} set”, no proof exists in ZFC, as there are generic extensions of L where there are Π ∼_{1}^{1} sets having cardinalities ℵ_{1} and ℵ_{2}.

In fact the assumptions of the theorem fit the conclusion. One can show that if there is a Π ∼_{1}^{1} set having every uncountable Π ∼_{1}^{1} set as its continuous injective image, then

∀z ⊂ ℕ((ℵ_{1})^{L[z]} < ℵ_{1}).

5.2 Theorem Assume Σ ∼_{1}^{1}-determinacy. (Equivalently: Every subset of ℕ has a sharp.) Then whenever B is an uncountable Σ ∼_{2}^{1} set and C is a zero-dimensional Π ∼_{1}^{1} non-Borel set, B is the continuous image of C ˙⋃D.

The main point is to play a Wadge type game to show that C has a relatively closed subset homeomorphic to H.

Coanalytic sets 20

Putting together these results with the classical theorems (Luzin etc) and the not so classical theorems (Moschovakis etc) one can give a complete picture under projective determinacy.

Class of uncountable Least projective set B class Γ where

every such B is the continuous injective image of some fixed C ⊂ ℕ^{ℕ} in Γ

——————————————————– Borel (=Δ ∼_{1}^{1}) closed (=Π ∼_{1}^{0})

Σ ∼_{1}^{1}, Π ∼_{1}^{1}, Σ ∼_{2}^{1}  Π ∼_{1}^{1}
Π ∼_{2n}^{1}, Δ ∼_{2n+1}^{1} (n > 0)  Π ∼_{2n}^{1}
Σ ∼_{2n+1}^{1}, Π ∼_{2n+1}^{1}, Σ ∼_{2n+2}^{1}  Π ∼_{2n+1}^{1}

§6. SOME “REVERSE DESCRIPTIVE SET THEORY” TYPE QUESTIONS

6.1 Question Suppose that for any uncountable Σ ∼_{2}^{1} set B and zero-dimensional Π ∼_{1}^{1} non-Borel set C we have that B is the continuous image of C ˙⋃D. Must Σ ∼_{1}^{1} determinacy hold?

This might be compared with the following theorem and question due to Leo Harrington:

6.2 Theorem (Harrington^{5} ) Suppose that every Σ ∼_{1}^{1} set A ⊂ ℕ^{ℕ} is either Borel or complete in the sense of Wadge degrees – that is to say, for any other analytic B ⊂ ℕ^{ℕ} we have some continuous f : ℕ^{ℕ} → ℕ^{ℕ} with

f^{−1}[A] = B.

Then Σ ∼_{1}^{1} determinacy.

6.3 Question (Harrington) Suppose any two Σ ∼_{1}^{1} non-Borel sets are Wadge comparable. Must we have Σ ∼_{1}^{1} determinacy?

5Analytic determinacy and 0^{♯}, Journal of Symbolic Logic, vol. 43(1978), pp. 685-693

6.4 “Question” For A, B countable metric spaces, set A ≺ B if there is a continuous bijection

π : B → A.

What does ≺ look like? (Is anything known?)

Remark: ω + 1 and ω + ω + 1 (in the order topology) are ≺ incomparable.