ARONSZAJN LINES AND THE CLUB FILTER

JUSTIN TATCH MOORE

Abstract. The purpose of this note is to demonstrate that a weak form of club guessing on ω_{1} implies the existence of an Aronszajn line with no Countryman suborders. An immediate consequence is that the existence of a five element basis for the uncountable linear orders does not follow from the forcing axiom for ω-proper forcings.

1. Introduction

In [7], Shelah constructed an uncountable linear order C with the property that C^{2} is the union of countably many non decreasing relations. Linear orders with this property are now known as Countryman lines. These orders are necessarily Aronszajn — they do not contain uncountable scattered or separable suborders.

At the end of his construction, Shelah made the following conjecture: It is consistent that every Aronszajn line contains a Countryman suborder. As the understanding of Aronszajn and Countryman lines progressed, it became clear that this conjecture was, assuming the Proper Forcing Axiom (PFA), equivalent to the following stronger statement: The uncountable linear orders have a five element basis. Recall that a basis for the uncountable linear orders is a collection ℬ of uncountable linear orders such that any other contains an isomorphic copy of an element of ℬ. It is not difficult to prove that any five element basis for the uncountable linear orders must be of the following form (up to equimorphism of its members): X, ω_{1}, −ω_{1}, C, and −C where X is a set of reals of cardinality ℵ_{1} and C is a Countryman line. Here, if L is a linear ordering, −L denotes the reverse order on L.

In [5] it was demonstrated that PFA does in fact imply that every Aronszajn line contains a Countryman suborder. The proof, however, utilized a newly isolated consequence of PFA known as the Mapping Reflection Principle (MRP) which was first considered in [4]. Unlike most consequences of PFA, MRP does not follow from the Forcing Axiom ω-proper forcings (ωPFA). The main purpose of this note is to show that the use of MRP in [5] is, in some sense, unavoidable. This is done by showing that a weak form of club guessing — the axiom ℧ — implies the existence of an Aronszajn line with no Countryman suborder.

2000 Mathematics Subject Classification. 03E05, 03E35.

Key words and phrases. Aronszajn, axiom A, club guessing, Countryman, forcing axiom.

This research was supported by NSF grants DMS-0401893 and DMS–0200671.

I would like to thank the anonymous referee for their very carefull reading of this paper and their helpful comments and suggestions.

Theorem 1.1. (℧) There is an Aronszajn line with no Countryman suborder.

The axiom ℧ is a strong failure of MRP at the level of ω_{1}. It is defined as follows:

℧: There is a sequence ⟨f_{α} : α < ω_{1}⟩ such that for all α < ω_{1}, f_{α} is a continuous map from α into ω and whenever E ⊆ ω_{1} is closed and unbounded, there is a δ in E such that f_{δ} takes all values in ω on E ∩ δ.

We will pause for a moment to make a few observations concerning this statement. Notice that if α < ω_{1} and f : α → ω is continuous, then α can be partitioned into open intervals on which f is constant. In such a situation, there is a cofinal C ⊆ α of ordertype at most ω such that f(ξ) depends only on the size of ξ ∩ C. From this observation, it should be immediately clear that ℧ follows from Ostaszewski’s ♣ and hence Jensen’s ♢. This shows that ℧ follows from club guessing on ω_{1} (where ♣ is modified by replacing uncountable subsets of ω_{1} with clubs). Furthermore, ℧ is immune to c.c.c. forcing and therefore is consistent with MA_{ℵ_{1}}. This is because every club E ⊆ ω_{1} in a c.c.c. forcing extension contains a club from the ground model. A somewhat more involved argument can be used to show that ℧ is preserved by ω-proper forcings.

While the most conspicuous feature of Theorem 1.1 is that it establishes that FA(𝒜) is not sufficient to imply the existence of a five element basis for the uncountable linear orders, I would argue that this is more than “just another independence result.” Most of the well known consequences of the Proper Forcing Axiom — 2^{ℵ_{0}} = ℵ_{2}, the failure of □(κ), the non-existence of S spaces and Kurepa trees, for instance — all follow from ωPFA. However a result such as Theorem 1.1 tells us that if a combinatorial statement under consideration is to follow from PFA, methods such as those in [5] are possibly relevant.

On the other hand, ℧ is such a weak assumption that once it is successfully used as a hypothesis, it is sometimes possible to refine the construction to obtain a ZFC result. We will see that the construction of Theorem 1.1, with the proper interpretation, also yields a hereditarily Lindelöf non separable T_{3} space — an L space. This construction was originally circulated in [3] and predates the one in [6] by two months, where the assumption of ℧ was removed. Furthermore, at present it seems plausible that ℧ may follow from the assumption that 2^{ℵ_{0}} > ℵ_{2}. If this is indeed the case, this construction would give new a method for extracting consequences from the assumption 2^{ℵ_{0}} ≠ ℵ_{2}.

The paper is intended to be fairly self contained, though the reader will benefit from some exposure to the material in [10]. Notation is standard and generally follows [2] (see also [1] for background in set theory).

2. Construction of the underlying combinatorial object

In this section we will see how to use ℧ to define a C-sequence so that the corresponding function ϱ_{0} introduced in [9] realizes some additional properties. First I will recall some definitions from [9]; see [10] for further reading and proofs. A C-sequence (on ω_{1}) is a sequence ⟨C_{α} : α < ω_{1}⟩ such that:

(1) C_{α+1} = {α} and C_{0} = ∅.

(2) If α > 0 is a limit, then C_{α} is a cofinal subset of α of ordertype

ω which consists of successor ordinals. Given a C-sequence, define the trace function recursively by

Tr(α, α) = ∅
Tr(α, β) = {β} ∪ Tr(α, min(C_{β} \ α))

for α < β < ω_{1}. The function ϱ_{0}(α, β) is given recursively, by

ϱ_{0}(α, α) = ⟨⟩
ϱ_{0}(α, β) = |C_{β} ∩ α|ˆ ϱ_{0}(α, min(C_{β} \ α))

for α < β < ω_{1}. It is easily shown that ϱ_{0}(α, β) is equal to

⟨|C_{β^{i}(α)} ∩ α| : i < | Tr(α, β)|⟩.

The function ϱ_{1} is defined by letting ϱ_{1}(α, β) be the maximum value in the sequence ϱ_{0}(α, β) (with ϱ_{1}(α, α) = 0). We will need the following standard facts about these functions.

Fact 2.1. For every δ ≤ β < ω_{1} with δ a positive limit ordinal, there is a δ̄ < δ such that δ is in Tr(α, β) whenever δ̄ < α < δ.

Fact 2.2. The following are equivalent for α < β < γ < ω_{1}: (1) β is in Tr(α, γ).

(2) Tr(α, γ) = Tr(α, β) ∪ Tr(β, γ).

(3) ϱ_{0}(β, γ) is an initial part of ϱ_{0}(α, γ).

(4) ϱ_{0}(α, γ) = ϱ_{0}(β, γ)ˆ ϱ_{0}(α, β).

Fact 2.3. If β < ω_{1}, then ϱ_{0}(·, β) is a strictly increasing map from β into ω^{<ω}.

Fact 2.4. If β ≤ β′ and there is an α < β such that ϱ_{0}(α, β) ≠ ϱ_{0}(α, β′), then the least such α is a successor ordinal.

Fact 2.5. For every n < ω and β ≤ β′, the following sets are finite:

{α < β : ϱ_{1}(α, β) ≤ n}
{α < β : ϱ_{1}(α, β) ≠ ϱ_{1}(α, β′)}.

This has the following as an immediate consequence.

Fact 2.6. If B ⊆ ω_{1} is uncountable, then

{ϱ_{1}(α, β) : β ∈ B \ α}

is infinite for all but a countable set of α < ω_{1}.

Now suppose that f_{α} (α < ω_{1}) is a ℧-sequence. Fix a function h : ω → ω such that h^{−1}(n) is infinite for all n < ω. It is routine to construct a C-sequence C_{α} (α < ω_{1}) such that for all limit ordinals α we have f_{α}(ξ) = h(|C_{α} ∩ ξ|) whenever ξ < α is a limit ordinal. For the duration of this paper, I will fix a C-sequence which is derived in this manner and use it to construct the functions Tr, ϱ_{0}, and ϱ_{1} above.

I will now define a function φ : ω^{<ω} → ℤ and show that the composition of φ and ϱ_{0} exhibits strong combinatorial properties if ϱ_{0} is derived from a ℧-sequence as above. Let η be the composition of h followed by a bijection from ω to the finitely supported functions from ω to ℤ.

Definition 2.7. If s is a finite sequence of elements of ω, define

φ(s) = ∑_{i<|s|} η(s(i))(max(s ↾ i)).

Here max(s) denotes the maximum entry of s with max(⟨⟩) = 0. It will be convenient to let φ(α, β) denote φ(ϱ_{0}(α, β)). The following lemma captures the property of φ : [ω_{1}]^{2} → ℤ which we will be interested in using.

Lemma 2.8. Let δ < ω_{1} be a limit ordinal and let β_{i} (i < m) be countable ordinals greater than δ such that ϱ_{1}(δ, β_{i}) (i < m) are all distinct. There is a finitely supported σ : ω → ℤ and a δ̄ < δ such that whenever η(|C_{δ} ∩ α|) = σ and δ̄ < α < δ, it follows that

φ(α, β_{i}) = φ(α, β_{0}) + i

for all i < m.

Remark 2.9. This lemma holds for ϱ-functions derived from an arbitrary C-sequence and does not utilize the assumption ℧.

Proof. Let δ̄ < δ satisfy the following conditions:

(1) δ̄ is an upper bound for all ξ < δ such that ϱ_{1}(ξ, β_{i}) ≠ ϱ_{1}(ξ, β_{i′}) for some i < i′ < m.

(2) If δ̄ < α < δ and i < m, then Tr(δ, β_{i}) ⊆ Tr(α, β_{i}). Let σ : ω → ℤ be finitely supported such that for each i < m

σ(ϱ_{1}(δ, β_{i})) = i − φ(δ, β_{i}) + φ(δ, β_{0});

such a σ exists since ϱ_{1}(δ, β_{i}) ≠ ϱ_{1}(δ, β_{i′}) if i ≠ i′.

It now suffices to check that σ and δ̄ work. Let α be such that δ̄ < α < δ and η(|C_{δ} ∩ α|) = σ. Observe that for i < m, δ is in Tr(α, β_{i}) and the following quantities do not depend on i: Tr(α, β_{i})∩δ, and the restriction of ϱ_{1}(·, β_{i}) to the interval (α, δ). For a given i < m,

φ(α, β_{i}) = φ(δ, β_{i}) + σ(ϱ_{1}(δ, β_{i})) + ∑_{ξ∈Tr(α,β_{i})∩δ}[η(|C_{ξ} ∩ α|)](ϱ_{1}(ξ, β_{i})).

Notice that the last summand does not depend on i by the comments made above and

φ(δ, β_{i}) + σ(ϱ_{1}(δ, β_{i})) = i + φ(δ, β_{0})

by arrangement. Hence φ(α, β_{i}) = φ(α, β_{0}) + i for all i < m. □

Before proceeding with the proof of Theorem 1.1, I will first demonstrate the following property of φ. It is both of independent interest and contains the main elements of the more involved proof to come.

Proposition 2.10. (℧) If A and B are uncountable subsets of ω_{1}, then there exist α ∈ A and β, β′ ∈ B \ α such that φ(α, β) is even and φ(α, β′) is odd.

Proof. Let E ⊆ ω_{1} be a closed unbounded set with the property that every element of E is a limit point of A and if δ is in E, then

{ϱ_{1}(δ, β) : β ∈ B \ δ}

is infinite. Since ⟨C_{α} : α < ω_{1}⟩ was derived from a ℧-sequence, there is a δ in E such that for every finitely supported σ : ω → ℤ and every δ̄ < δ, there is a ν in E ∩ (δ̄, δ) such that η(|C_{δ} ∩ ν|) = σ.

Now let β_{0} and β_{1} be two elements of B \ δ such that ϱ_{1}(δ, β_{0}) ≠ ϱ_{1}(δ, β_{1}). By Lemma 2.8, there is a finitely supported σ : ω → ℤ and a δ̄ < δ such that if δ̄ < α < δ and η(|C_{δ} ∩ α|) = σ, then φ(α, β_{1}) = φ(α, β_{0}) + 1. By choice of δ, there is a ν in E ∩ (δ̄, δ) such that η(|C_{δ} ∩ ν|) = σ. Since ν is a limit point of A, there is an α in A ∩ (δ̄, δ) such that η(|C_{δ} ∩ α|) = σ and hence φ(α, β_{1}) = φ(α, β_{0}) + 1. If i is such that φ(α, β_{i}) is even, then let β = β_{i} and β′ = β_{1−i}. □

By generalizing Lemma 2.6 and adapting the above arguments appropriately, one can prove the following strengthening of Proposition 2.10; we leave the details to the interested reader. This should be compared to Theorem 1.5 of [6].

Theorem 2.11. (℧) If 𝒜 ⊆ [ω_{1}]^{k} and ℬ ⊆ [ω_{1}]^{l} are uncountable families of pairwise disjoint sets, then for every m < ω, there is an a in 𝒜 and b_{x} (x < m) in ℬ with, for all i < k, j < l, and x < m

a(i) < b_{x}(j)
φ(a(i), b_{x}(j)) = φ(a(i), b_{0}(j)) + x.

Put in the context of [6, §5], this yields an example of an L space.

3. Using φ to define an Aronszajn line with no Countryman suborder

Todorcevic showed in [9] that C(ϱ_{0}) – which is the set

{ϱ_{0}(·, β) : β < ω_{1}}

ordered lexicographically — is a Countryman line. In fact, under mild assumptions, C(ϱ_{0}) and its reverse form a two element basis for the class of all Countryman lines.

Theorem 3.1. [10, 2.1.13] (MA_{ℵ_{1}}) Every Countryman order contains an isomorphic copy of either C(ϱ_{0}) or −C(ϱ_{0}).

Furthermore, we have the following lemma which reduces the task of proving Theorem 1.1 to demonstrating the existence of a certain pathological partition of

T (ϱ_{0}) = {ϱ_{0}(·, β) ↾ α : α ≤ β < ω_{1}}.

Suppose that K is a subset of T (ϱ_{0}). We can define a linear order ≤_{K} on T (ϱ_{0}) so that ≤_{K} and ≤_{lex} agree on a pair {ϱ_{0}(·, α), ϱ_{0}(·, β)} iff ϱ_{0}(·, α)∧ϱ_{0}(·, β) is not in K. It is not difficult to show that this defines an Aronszajn order.

Lemma 3.2. [8, 8.7] (MA_{ℵ_{1}}) Suppose K ⊆ T. If for every uncountable X ⊆ ω_{1} there are α, α′, β, β′ in X with

ϱ_{0}(·, α) ∧ ϱ_{0}(·, β) ∈ K
ϱ_{0}(·, α′) ∧ ϱ_{0}(·, β′) ∉ K,

then (T (ϱ_{0}), ≤_{K}) does not contain a Countryman suborder.

I will prove momentarily that φ can be used to define a K ⊆ T (ϱ_{0}) which will have the property stated in Lemma 3.2, so long as the Csequence used in the definition of ϱ_{0} is derived from a ℧-sequence. To see this is sufficient to prove Theorem 1.1, assume V is a model of ZFC + ℧ and go into a c.c.c. forcing extension V [G] which satisfies MA_{ℵ_{1}}. In V [G], K still satisfies the hypothesis of Lemma 3.2 and hence (T (ϱ_{0}), ≤_{K}) does not contain a Countryman suborder by Theorem 3.1 and Lemma 3.2. Since any Countryman suborder of (T (ϱ_{0}), ≤_{K}) in V would remain Countryman in V [G], it follows that (T (ϱ_{0}), ≤_{K}) did not have a Countryman suborder in V.

Define K ⊆ T (ϱ_{0}) by putting τ in K iff τ has successor height ζ + 1 and φ(τ(ζ)) is even. We will need the following lemma. Let Δ(α, β) denote the least ξ such that ϱ_{0}(ξ, α) ≠ ϱ_{0}(ξ, β).

Lemma 3.3. If X ⊆ ω_{1} is uncountable, then there is a club E ⊆ ω_{1} such that if δ is in E, δ̄ < δ, and β_{i} (i < m)is a finite sequence in X \ δ, then there are β′_{i} (i < m) in X ∩ δ with

δ̄ < Δ(β_{0}, β′_{0}) = Δ(β_{i}, β′_{i}) < δ

whenever i < m.

Proof. If ν < ω_{1}, choose f(ν) < ω_{1} so that for all countable ordinals δ and β_{i} (i < m), if:

(1) ν < δ ≤ β_{i} for i < m;

(2) β_{i} is in X for each i < m;

(3) δ is in Tr(ν, β_{i}) for each i < m, then there are δ′, β′_{i} (i < m) satisfying the same conditions such that additionally:

(1) each are less than f(ν);

(2) ϱ_{0}(·, β_{i}) ↾ ν = ϱ_{0}(·, β′_{i}) ↾ ν for each i < m;

(3) ϱ_{0}(δ′, β′_{i}) = ϱ_{0}(δ, β_{i}) for each i < m;

(4) ϱ_{0}(ν, δ) = ϱ_{0}(ν, δ′). Notice that f(ν) exists since T (ϱ_{0}) has countable levels and ϱ_{0} takes values in a countable set.

It suffices to show that if E is the set of all limit ordinals δ which are closed under f, then E satisfies the conclusion of the lemma. To this end, let δ be in E, δ̄ < δ, and let β_{i} (i < m) be elements of X \ δ. By increasing δ̄, we may assume that δ is in Tr(δ̄, β_{i}) for all i < m. Let δ′ and β′_{i} (i < m) be ordinals satisfying 1–4 for ν = δ̄. Clearly ϱ_{0}(δ′, β_{i}) ≠ ϱ_{0}(δ′, β′_{i}) since ϱ_{0}(·, β_{i}) is one-to-one by Fact 2.3. Hence δ̄ < Δ(β_{i}, β′_{i}) ≤ δ′ < δ. Furthermore, by Fact 2.2,

ϱ_{0}(ξ, β_{i}) = ϱ_{0}(δ, β_{i})ˆ ϱ_{0}(ξ, δ)
ϱ_{0}(ξ, β′_{i}) = ϱ_{0}(δ′, β′_{i})ˆ ϱ_{0}(ξ, δ′)

whenever δ̄ < ξ < δ′. It follows that Δ(β_{i}, β′_{i}) does not depend on i. □

It is now sufficient to prove that the K defined above satisfies the hypothesis of Lemma 3.2. Let X be given and select a club E ⊆ ω_{1} witnessing the conclusion of Lemma 3.3 for this X such that, moreover,

{ϱ_{1}(δ, β) : β ∈ X \ δ}

is infinite for all δ in E. Using that ⟨C_{α} : α < ω_{1}⟩ was derived from a ℧-sequence, it is possible to select a δ in E such that for all finitely supported σ : ω → ℤ and δ̄ < δ, there is a ν in E with η(|C_{δ} ∩ ν|) = σ. Let β_{0} and β_{1} be elements of X \ δ such that ϱ_{1}(δ, β_{0}) ≠ ϱ_{1}(δ, β_{1}). By Lemma 2.8, there is a finitely supported σ : ω → ℤ such that if δ̄ < α < δ and η(|C_{δ} ∩ α|) = σ, then φ(α, β_{1}) = φ(α, β_{0}) + 1. Let ν be an element of E with δ̄ < ν < δ and η(|C_{δ} ∩ ν|) = σ. Let ν̄ < ν be such that C_{δ} ∩ ν̄ = C_{δ} ∩ ν. By choice of E, there are α_{0} and α_{1} in X such that

ν̄ < Δ(α_{0}, β_{0}) = Δ(α_{1}, β_{1}) < ν

and hence if ζ + 1 = Δ(α_{0}, β_{0}), then C_{δ} ∩ ζ = C_{δ} ∩ ν. Putting this all together, we have that

φ(ζ, α_{i}) = φ(ζ, β_{i}),
φ(ζ, α_{1}) = φ(ζ, α_{0}) + 1

and hence ϱ_{0}(·, α_{0}) ∧ ϱ_{0}(·, β_{0}) is in K iff ϱ_{0}(·, α_{1}) ∧ ϱ_{0}(·, β_{1}) is not in K. This finishes the proof.

References

[1] Thomas Jech. Set theory. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, second edition, 1997.

[2] Kenneth Kunen. An introduction to independence proofs, volume 102 of Studies in Logic and the Foundations of Mathematics. North-Holland, 1983.

[3] Justin Tatch Moore. Persistent counterexamples to basis conjectures. circulated note, September 2004.

[4] Justin Tatch Moore. Set mapping reflection. J. Math. Log., 5(1):87–97, 2005.

[5] Justin Tatch Moore. A five element basis for the uncountable linear orders. Annals of Mathematics (2), 163(2):669–688, 2006.

[6] Justin Tatch Moore. A solution to the L space problem. Jour. Amer. Math. Soc., 19(3):717–736, 2006.

[7] Saharon Shelah. Decomposing uncountable squares to countably many chains. J. Combinatorial Theory Ser. A, 21(1):110–114, 1976.

[8] Stevo Todorcevic. Lipschitz maps on trees. report 2000/01 number 13, Institut Mittag-Leffler.

[9] Stevo Todorcevic. Partitioning pairs of countable ordinals. Acta Math., 159(3– 4):261–294, 1987.

[10] Stevo Todorcevic. Walks on ordinals and their characteristics, volume 263 of Progress in Mathematics. Birkhäuser, 2007.

Department of Mathematics, Cornell University, Ithaca, NY 14853– 4201, USA