Hechler and Laver Trees

Arnold W. Miller^{1}

Abstract

A Laver tree is a tree in which each node splits infinitely often. A Hechler tree is a tree in which each node splits cofinitely often. We show that every analytic set is either disjoint from the branches of a Heckler tree or contains the branches of a Laver tree. As a corollary we deduce Silver Theorem that all analytic sets are Ramsey. We show that in Godel’s constructible universe that our result is false for co-analytic sets (equivalently it fails for analytic sets if we switch Hechler and Laver). We show that under Martin’s axiom that our result holds for Σ_{2}^{1} sets. Finally we define two games related to this property.

Definition 1 A subtree H ⊆ ω^{<ω} is Hechler iff ∀s ∈ H ∀^{∞}n sn ∈ H. A subtree L ⊆ ω^{<ω} is Laver iff ∀s ∈ L ∃^{∞}n sn ∈ L.

These definitions are motivated by well-known forcing notions of Laver [4] and Hechler [3]. In the classical Hechler forcing the cofinite sets on the n^{th} level of the tree would all be the same.

Definition 2 For any subtree T ⊆ ω^{<ω} define

[T] = {x ∈ ω^{ω} : ∀n x ↾ n ∈ T }

Theorem 3 For any Σ_{1}^{1} set A ⊆ ω^{ω} either there exists a Hechler tree H with [H] ∩ A = ∅ or there exists a Laver tree L with [L] ⊆ A.

1These results were obtained in December 2002 while visiting the Fields Institute at the University of Toronto. Thanks to its director Juris Steprans and his staff for their hospitality and also for the discussions we had with Steprans at that time. It was presented to the SEALS conference in Gainesville Florida in March 2003, and in a topics course at the University of Wisconsin, Madison in the fall of 2009. Last revised April 2012..

Mathematics Subject Classification 2010: 03E15; 03E05; 03E02 Keywords: Analytic sets, trees, constructible sets, Martin’s Axiom, games.

Proof Since analytic sets are projections of closed sets there exists a tree T on ω^{<ω} × ω^{<ω} such that

A = p[T] =^{def} {x ∈ ω^{ω} : ∃y ∈ ω^{ω} ∀n (x ↾ n, y ↾ n) ∈ T }.

Assume that for every Hechler H that A meets [H] and we will show there is a Laver L with [L] ⊆ A.

For s, t ∈ ω^{<ω} define

A_{s,t} = {x ∈ ω^{ω} ; s ⊆ x∃y ⊇ t (x, y) ∈ [T]}.

Definition 4 We say that H is Hechler with root s if for all t ∈ H either s ⊆ t or t ⊆ s and beneath s there is cofinite splitting.

Lemma 5 Suppose for every Hechler H with root s that A_{s,t}∩[H] ≠ ∅. Then there are infinitely many n such that for every Hechler H with root sn that A_{sn,t} ∩ [H] ≠ ∅.

Proof Otherwise for all but finitely many n (say n > N) there exists a Hechler H_{n} with root sn which misses A_{sn,t}. But then the Hechler tree: H = ⋃_{n>N} H_{n} misses A_{s,t} and has root s. QED

Lemma 6 Suppose for every Hechler H with root s that A_{s,t}∩[H] ≠ ∅. Then there exists an infinite well-founded tree T ⊆ {r : s ⊆ r} with root s and terminal nodes B ⊆ T such that

(1) The nonterminal nodes of T are ω-splitting, i.e., if r ∈ T \B, then there are infinitely many n with rn ∈ T, and

(2) For every r ∈ B there exists n such that for every Hechler tree H with root r, A_{r,tn} ∩ [H] ≠ ∅.

Proof For each ordinal α define a set B_{α} ⊆ {r : s ⊆ r} as follows.

(a) r ∈ B_{0} iff there exists n such that for every Hechler tree H with root r, A_{r,tn} ∩ [H] ≠ ∅.

(b) B_{α+1} = B_{α} ∪ {r : ∃^{∞}n rn ∈ B_{α}}

(c) B_{λ} = ⋃_{α<λ} for λ a limit ordinal.

Define function rank(r) on r ⊇ s as follows, rank(r) = α if α is the least ordinal with r ∈ B_{α} and rank(r) = ∞ if there is no such ordinal.

Case 1. rank(s) is an ordinal. In this case it is easy to build T and B as required.

Case 2. rank(s) = ∞. We show that this is impossible. Note that if rank(r) = ∞ then for all but finitely many n we must have that rank(rn) = ∞. Hence we may construct a Hechler tree H with root s such that rank(r) = ∞ for all r ∈ H below the root. For each n < ω for each r ∈ ω^{n+|s|} ∩ H there exists a Hechler H_{r} with root r such that

[H_{r}] ∩ A_{s,tn} = ∅.

Define

K_{n} = ⋃{H_{r} : r ∈ ω^{n+|s|} ∩ H}

Note that K_{n} is a Hechler tree with root s whose n + |s| level is the same as H. It also true that K_{n} ∩ A_{s,tn} = ∅. Because they are so wide K = ⋂_{n<ω} K_{n} is a Hechler tree with root s such that [K] ∩ ⋃_{n} A_{s,tn} = ∅. This contradicts the hypothesis of the Lemma since ⋃_{n} A_{s,tn} = A_{s,t}.

Finally, if T is trivial, i.e., T = B = {s} just apply Lemma 5 to make T infinite. QED

Proof of Theorem 3:

Suppose for every Hechler tree H with trivial root that A∩[H] ≠ ∅. Apply Lemma 6 to obtain a non-trivial well-found tree T_{0} with terminal nodes B_{0} and witnesses of length one.

Suppose we are given a well-founded tree T_{n} with trivial root and terminal nodes B_{n} such that for all s ∈ T_{n}\B_{n} there are infinitely many immediate extensions of s in T_{n} and for each s ∈ B_{n} there is a t_{s} of length n + 1 such that for every Hechler tree H with root s, A_{s,t_{s}} ∩ [H] ≠ ∅. Apply Lemma 6 to each node (s, t_{s}) with s ∈ B_{n}. Union all these trees together to get T_{n+1} which end extends T_{n}. It follows that L is a Laver where

L = ⋃_{n<ω} T_{n}

Note that although the length of the witnesses grow much slower than the s-part, nevertheless, they union up to show that L ⊆ A. QED

Definition 7 For F a filter extending the cofinite filter on ω define ℍ_{F} to be the Hechler trees mod F, i.e., instead of demanding that for each s ∈ H that sn ∈ H for cofinitely many n, we demand that

{n : sn ∈ H} ∈ F.

Analogously define 𝕃_{F} the Laver trees mod F by for each s ∈ L

{n : sn ∈ L} ∈ F^{+}

where F^{+} are the positive F sets, i.e, sets whose complement is not in F.

Theorem 8 For any filter F and any Σ_{1}^{1} set A ⊆ ω^{ω} either there exists a Hechler tree H ∈ ℍ_{F} with [H] ∩ A = ∅ or there exists a Laver tree L ∈ 𝕃_{F} with [L] ⊆ A.

Proof The proof of this goes over mutatis mutandis, the proof of Theorem 3. QED

Any Hechler tree H may be pruned so that every node in it is strictly increasing, i.e. , if ⟨x_{0}, x_{1}, …, x_{n}⟩ ∈ H then x_{0} < x_{1} < … x_{n}. By the range of H we mean all infinite subsets of ω which are the image of some branch f ∈ H, i.e.,

range(H) = {{f(n) : n < ω} : f ∈ [H]}

Proposition 9 Suppose H ∈ ℍ_{F}. Then there exists X ∈ [ω]^{ω} such that [X]^{ω} ⊆ range(H).

Proof We may suppose that the nodes of H are strictly increasing. Construct a strictly sequence x_{0}, x_{1}, …, x_{n} such that for every k and subsequence

0 ≤ i_{1} < i_{2} < ⋯ < i_{k} ≤ n

we have that ⟨x_{i_{1}}, …, x_{i_{k}}⟩ ∈ H. To obtain x_{n+1} we need only intersect finitely many elements of the filter F. QED Corollary 10 (Silver [5]) Analytic sets have the Ramsey Property. This means that for any Σ_{1}^{1} set A ⊆ [ω]^{ω} there exists an X ∈ [ω]^{ω} with either [X]^{ω} ⊆ A or [X]^{ω} ∩ A = ∅.

Proof Let F be a nonprincipal ultrafilter. Note that ℍ_{F} = 𝕃_{F} for ultrafilters. Define B ⊆ ω^{ω} by f ∈ B iff f is strictly increasing with range in A. Then B is Σ_{1}^{1} and so by Theorem 8 there is a Hechler tree H ∈ ℍ_{F} with [H] ⊆ B or [H] ∩ B = ∅. By Proposition 9 there is an infinite X as required. QED

This gives a proof of Silver’s Theorem which avoids the accept-reject arguments of Galvin-Prikry [2] and Ellentuck [1].

Theorem 11 (V=L) There exists a Π_{1}^{1} set A ⊆ ω^{ω} such that [H] ∩ A ≠ ∅ for every Hechler tree H but A contains no Laver [L].

Proof

Using the definable well-ordering of the reals in L construct B ⊆ ω^{ω} a Σ_{2}^{1} set with the following two properties:

(1) B is an <^{∗} scale, i.e., B = {g_{α} ∈ ω^{ω} : α < ω_{1}} where α < β implies g_{α} <^{∗} g_{β} and for every f ∈ ω^{ω} there exist α such that f <^{∗} g_{α}.

(2) B has the property that for any σ : ω^{<ω} → ω there exists g ∈ B such that for all x ∈ 2^{ω} if f = 2g + x then ∀n f(n) > σ(f ↾ n),

Let C ⊆ ω^{ω} × 2^{ω} be Π_{1}^{1} so that g ∈ B iff ∃x (g, x) ∈ C.

Given f ∈ ω^{ω} define Q(f) = (g, x) where g ∈ ω^{ω} and x ∈ 2^{ω} are determined by f = 2g + x. Define the Π_{1}^{1} set A by

A = {f ∈ ω^{ω} : Q(f) ∈ C}.

Note that for any Hechler H we can find σ : ω^{<ω} → ω such that

H_{σ} =^{def} {f ∈ ω : ∀n f(n) > σ(f ↾ n) } ⊆ H

It follows from (2) that A meets every [H]. On the other hand A cannot contain the branches [L] of a Laver tree. This is because of the scale (1). Take a 3 splitting subtree of T ⊆ L, i.e., for every s ∈ T there are exactly 3 immediate extensions of s in T. For each g ∈ ω^{ω} define

C_{g} = {f ∈ ω^{ω} : ∃x ∈ 2^{ω} f = 2g + x}

and note that A ⊆ ⋃_{g∈B} C_{g}. If [T] ⊆ A then by the scale property of B there would have to be a countable set Q ⊆ B with such that

[T] ⊆ ⋃_{g∈Q} C_{g}

But the C_{g} are the branches of a binary splitting tree and since T is 3splitting, it is easy to construct f ∈ [T] such that f ∉ C_{g} for every g ∈ Q. QED

Theorem 12 Assume MA +¬CH. If A ⊆ ω^{ω} is Σ_{2}^{1}, then either there is a Hechler tree H with [H] ∩ A = ∅ or there is a Laver tree L with [L] ⊆ A. In fact, this is true for any set A which is the union of ω_{1} many Borel sets.

Proof Suppose A = ⋃_{α<ω_{1}} B_{α} where each B_{α} is Borel and the union is increasing. Since no B_{α} contains the branches of a Laver tree we have H_{α} a Hechler tree with [H_{α}] ∩ B_{α} = ∅. Without loss we may assume that

[H_{α}] = {f ∈ ω^{ω} : ∀n f(n) > σ_{α}(f ↾ n) }

where σ_{α} : ω^{<ω} → ω. By Martin’s axiom we may find σ : ω^{<ω} → ω which eventually dominates each σ_{α}. By a counting argument we can find a single σ : ω^{<ω} → ω which everywhere dominates ω_{1} of the σ_{α}. But this means that H_{σ} is a Hechler tree disjoint from A since the B_{α}’s are an increasing union. QED

Finally we make some remarks about games.

Game 1. Given A ⊆ ω^{ω}. Player I and II alternatingly play

n_{0}, m_{0} > n_{0}, n_{1}, m_{1} > n_{1}, …

with Player I playing n_{k} ∈ ω and Player II responding with m_{k} > n_{k}. The play of the game is won by Player II iff (m_{i} : i < ω) ∈ A.

Proposition 13 (a) Player II has a winning strategy in Game 1 iff there exists a Laver tree L with [L] ⊆ A. (b) Player I has a winning strategy in Game 1 iff there exists a Hechler tree H with [H] ∩ A = ∅.

Proof Given the trees it easy to get the strategies. For the other direction:

(a) Use player II’s winning strategy to construct a Laver tree as required.

(b) If σ : ω^{<ω} → ω is Player I’s winning strategy, then for any sequence (m_{i} : i < ω) such that m_{i+1} > σ(m_{0}, …, m_{i}) for every i we have that (m_{i} : i < ω) ∉ A. But this gives a Hechler tree H with [H] disjoint from A. QED

Game 2. Given A ⊆ ω^{ω}. Player I and II alternatingly play

X_{0}, m_{0} ∈ X_{1}, X_{1}, m_{1} ∈ X_{1}, …

with Player I playing X_{k} ∈ [ω]^{ω} and Player II responding with m_{k} ∈ X_{k}. Player II wins the play of the game iff (m_{i} : i < ω) ∈ A.

Proposition 14 (a) Player II has a winning strategy in Game 2 iff there exists a Hechler tree H with [H] ⊆ A. (b) Player I has a winning strategy in Game 2 iff there exists a Laver tree L with [L] ∩ A = ∅.

Proof From right-to-left in both cases is easy. For the other direction:

(a) Let σ be a winning strategy for Player II. Consider

{m_{0} : ∃X_{0} σ(X) = m_{0}}

This set must be cofinite, since otherwise consider σ’s response to its complement. Similarly given any sequence X_{0}, X_{1}, …, X_{n−1} the set

{m_{n} : ∃X_{n} σ(X_{0}, …, X_{n}) = m_{n}}

must be cofinite. Construct X_{s} for s ∈ ω^{<ω} and get a Hechler tree H all of whose branches are plays of the winning strategy and hence are in A.

(b) The sequence of X_{s} played by winning strategy of Player I determine a Laver tree L. QED

Some of the results in this note follow from Zapletal [6].

References

[1] Ellentuck, Erik; A new proof that analytic sets are Ramsey. J. Symbolic Logic 39 (1974), 163-165.

[2] Galvin, Fred; Prikry, Karel; Borel sets and Ramsey’s theorem. J. Symbolic Logic 38 (1973), 193-198.

[3] Hechler, Stephen H.; On the existence of certain cofinal subsets of ^{ω}ω. Axiomatic set theory (Proc. Sympos. Pure Math., Vol. XIII, Part II, Univ. California, Los Angeles, Calif., 1967), pp. 155-173. Amer. Math. Soc., Providence, R.I., 1974.

[4] Laver, Richard; On the consistency of Borel’s conjecture. Acta Math. 137 (1976), no. 3-4, 151-169.

[5] Silver, Jack; Every analytic set is Ramsey. J. Symbolic Logic 35 (1970), 60-64.

[6] Zapletal, Jindrich; Isolating cardinal invariants. J. Math. Log. 3 (2003), no. 1, 143-162.

Arnold W. Miller miller@math.wisc.edu http://www.math.wisc.edu/∼miller University of Wisconsin-Madison Department of Mathematics, Van Vleck Hall 480 Lincoln Drive Madison, Wisconsin 53706-1388