Math. Res. Lett. 15 (2008), no. 00, 10001–100NN \begin{matrix}c \\ ◯ \end{matrix} International Press 2008

A UNIVERSAL ARONSZAJN LINE

Justin Tatch Moore

Abstract. The purpose of this note is to define an Aronszajn line η_{C} and prove that under the assumption of PFA it is universal for the class of Aronszajn lines. Moreover η_{C} can be easily described in terms of a fixed Countryman type C: it is the direct limit of the finite lexicographic products of the form C × (−C) × … × (±C).

1. Introduction

An uncountable linear order is Aronszajn if it has no uncountable separable suborders and does not contain a copy of ω_{1} or −ω_{1}. These linear orders were considered and proved to exist by Aronszajn and Kurepa [8] (see also [15, §5]) in the course of studying Souslin’s Problem [14]. One of the main difficulties in dealing with this class lies in the fact that it is defined in terms of what order types its members do not contain. Hence its members are typically dealt with in a fairly abstract manner.

In this paper I will use the Proper Forcing Axiom (PFA) to prove that all Aronszajn lines are isomorphic to a suborder of a single canonical Aronszajn line η_{C}. Here PFA is a strong Baire category assumption due to Baumgartner. It extends MA_{ℵ_{1}} to a broader class of partial orders and is a natural assumption in this context (see [1], [3], [17, §8], [19], [20]). The universality of η_{C} and the results of this paper also hold in Woodin’s canonical model for the failure of the Continuum Hypothesis [22].

In [10] it was proved that, assuming PFA, the Aronszajn lines contain a two element basis. That is, there are two Aronszajn lines such that any other contains an isomorphic copy of one of these two. The elements of this basis have the following property: their Cartesian square can be covered by countably many non decreasing relations. Such orders are said to be Countryman and were first constructed by Shelah in [12]. Unlike being Aronszajn, being Countryman is phrased in terms of the existence of a simple global structure on the linear order. Remarkably, the existence of such a structure automatically entails that the order is Aronszajn. A further important observation is that if C is Countryman and −C is its reverse, then no uncountable linear order can embed into both C and −C. In particular, the Aronszajn lines cannot have a single element basis.

In [16], Todorcevic produced a number of concrete representations of Countryman lines (see also [21]). He moreover proved that such linear orders are canonical in the

10001

2000 Mathematics Subject Classification. Primary: 03E75, 06A05; Secondary: 03E05, 03E35, 03E65.

Key words and phrases. Aronszajn, Countryman, linear order, PFA, universal.

10002 Justin Tatch Moore

presence of MA_{ℵ_{1}}. The following is a strong form of [21, 2.1.12] which is proved by a similar argument.^{1}

Theorem 1.1. (MA_{ℵ_{1}}) Every two ℵ_{1}-dense non stationary Countryman lines are either isomorphic or reverse isomorphic. In particular if C is a Countryman line, then C and −C form a two element basis for all Countryman lines.

The construction of η_{C} is as follows. Fix a Countyman line C and let ζ_{C} denote the direct sum −C ⊕ {0} ⊕ C. The order η_{C} is the subset of the lexicographic power (ζ_{C})^{ω} consisting of those elements which are eventually 0.

Theorem 1.2. (PFA) Every Aronszajn line is isomorphic to a suborder of η_{C}.

Notice that if we let η denote the ordertype of ℚ, then we have a rather strong analogy between the relationship of ℕ and −ℕ to η and the relationship of C and −C to η_{C}.

In the course of proving the main result, I will also establish the following result which is of independent interest.

Theorem 1.3. (PFA) If A is an Aronszajn line which is not Countryman, then A contains an isomorphic copy of both C and −C for some (equivalently any) Countryman line C.

As this result is proved, it will be remarked how the argument can be adapted to yield a complete proof of Theorem 1.1.

This paper is intended to be fairly self contained, although I will cite some established consequences of PFA at appropriate points. The reader is, however, assumed to have some familiarity with set theory – [7] is a standard reference (chapter 2 is particularly relevant). The reader should recall in particular that ordinals are taken, in the sense of von Neumann, to be the set of their predecessors. A sequences is a function whose domain is an ordinal. Further information on the Proper Forcing Axiom and associated arguments can be found in [4], [13], and [17]. The reader can find additional information on trees and linear orders in [15].

2. Preliminary analysis

It will be helpful to first define some notation and make some observations about Aronszajn lines. First, recall that every Aronszajn line has cardinality ℵ_{1} [15, §5] and hence can be represented as a linear ordering on ω_{1}. Let A be a fixed Aronszajn ordering on ω_{1}. A can be represented as a lexicographic ordering on a subset of 2^{ω_{1}} in the following way. For each α < ω_{1}, let a_{α} : ω_{1} → 2 be the characteristic function of the set of ξ < ω_{1} such that ξ <_{A} α. It is easy to see that the function sending α to a_{α} preserves order if its domain is given the order from A and its range is given the lexicographic order.

If α ≠ β, it will be useful to let Δ_{A}(α, β) denote the least ξ such that a_{α}(ξ) ≠ a_{β}(ξ). The following fact is routine to verify.

Fact 2.1. Suppose that α ≤_{A} α′ ≤_{A} β′ ≤_{A} β. Then Δ_{A}(α, β) ≤ Δ_{A}(α′, β′).

1I made an incorrect reference to this result in [11] by omitting “non stationary” from the statement. Without “non stationary” this theorem becomes false in a very strong sense [2] (see [15, 5.7]).

See [18] for further information on the role of stationary sets in the context of Aronszajn lines.

A UNIVERSAL ARONSZAJN LINE 10003

Notice that, since A is Aronszajn, its elements have both countable cofinality and co-initiality. Consequently, for each α < ω_{1}, there is a least ξ < ω_{1} such that Δ_{A}(α, β) < ξ whenever β < ω_{1}. By letting E be the set of fixed points of the operation α ↦ ξ, we have the following fact.

Fact 2.2. There is a club E ⊆ ω_{1} such that if α < β < ω_{1}, then Δ_{A}(α, β) < min(E \ α).

Let T_{A} denote the set of all a_{ξ} ↾ η such that ξ < ω_{1} and η ≤ min(E \ (ξ + 1)). In addition to its tree structure given by sequential extension, T_{A} is also equipped with the lexicographic ordering which extends the ordering of sequential extension (i.e. if s is an initial part of t, then s ≤_{lex} t). Notice that the map ξ ↦ a_{ξ} ↾ min(E \ (ξ + 1)) is an embedding of A into (T_{A}, ≤_{lex}).

Recall that a linear order L is ℵ_{1}-dense if whenever a < b are in L ∪ {−∞, +∞}, the set of all x in L with a < x < b has cardinality ℵ_{1}. Also, an Aronszajn line A is non stationary if there is a continuous ⊆-increasing sequence ⟨D_{ξ} : ξ < ω_{1}⟩ of countable subsets of A which cover A and have the property that no maximal interval of A \ D_{ξ} has a greatest or least element for any ξ < ω_{1}. Stationarity of Aronszajn lines was introduced in [2] in order to generate a large number of pairwise non isomorphic Aronszajn lines in ZFC (see also [18]). The following is a standard fact about Aronszajn lines.

Fact 2.3. Every Aronszajn line contains an ℵ_{1}-dense suborder which is non stationary.

Finally, we will need the following fact about Countryman lines which follows easily from their definition.

Fact 2.4. If C is Countryman, then C does not contain a Souslin suborder. Equivalently, if X is an uncountable subset of T_{C}, then X contains an uncountable antichain.

3. When Aronszajn lines are Countryman

The purpose of this section is to prove Theorem 1.3 — that every non Countryman Aronszajn line must contain both “orientations” of a given Countryman line. At appropriate points in the argument, I will note how the proof can be adapted to yield a proof of Theorem 1.1. The proof in this section is similar to that of [1, §5] and, e.g., [21, 2.1.12]. For completeness, I will present an argument which draws out the reasons why PFA is (likely) needed in the proof of Theorem 1.3 while MA_{ℵ_{1}} is sufficient for the proof of Theorem 1.1. I will include details which until now have been left to the reader.

For this section, let A be a given Aronszajn line and C be a given Countryman line. We will generally be interested in pairs A and C which satisfying the following hypothesis, but we will make explicit mention of when this property is needed:

H: Whenever X is an uncountable suborder of A, X contains a copy of C.

In particular, (H) implies that A does not contain a Souslin suborder. Without loss of generality, both A and C are orderings on the underlying set ω_{1}. I will freely use the notation and observations collected in Section 2.

Definition 3.1. Define Q_{0} to be the collection of all finite partial functions from A to C which preserve order. This is considered as a forcing notion with the order of reverse inclusion.^{2}

The forcing Q_{0} fails to satisfy the countable chain condition for any number of reasons (which should become apparent momentarily). The following notion of [1] is what is needed to refine Q_{0} to a collection which does satisfy the c.c.c..

Definition 3.2. If f is a partial function from A to C and δ < ω_{1}, then f is said to respect δ if:

(1) for all α in the domain of f,

α < δ ⇔ f(α) < δ.

(2) for all α ≠ β in the domain of f,

Δ_{A}(α, β) < δ ⇔ Δ_{C}(f(α), f(β)) < δ.

If E is a subset of ω_{1}, then f respects E if f respects every element of E.

The following lemma gives an indication as to why this definition will play a role. It will be used in the verification of Theorem 1.1.

Lemma 3.3. If R ⊆ A^{2} is a non decreasing relation, then there is a club E ⊆ ω_{1} such that if q is in Q_{0} and q ⊆ R, then for all α ≠ β in the domain of q and δ in E,

Δ_{A}(α, β) < δ ⇔ Δ_{A}(q(α), q(β)) < δ.

Proof. Suppose that ζ is in A. Define h(ζ) to be the supremum of all countable ordinals of the form Δ_{A}(β, β′) such that for some α and α′ in A with α <_{A} ζ <_{A} α′, either both (α, β) and (α′, β′) or both (β, α) and (β′, α′) are in R. This supremum is countable by Fact 2.1 and the assumption that A is Aronszajn. If E is the club of those δ < ω_{1} which are closed under h, then E satisfies the conclusion of the lemma. □

The following lemma will be needed in proving the countable chain condition of certain refinements of Q_{0}.

Lemma 3.4. (H) Suppose that ⟨q_{ξ} : ξ < ω_{1}⟩ is a sequence of elements of Q_{0} which all respect some fixed club E ⊆ ω_{1}. Then there is an uncountable Γ ⊆ ω_{1} such that q_{ξ} ∪ q_{η} is in Q_{0} whenever ξ ≠ η are in Γ.

Proof. It will be useful to first make a definition and adopt a notational convention which will be used later as well. If ⟨q_{ξ} : ξ < ω_{1}⟩ is an uncountable sequence of disjoint elements of Q_{0}, it is possible by routine arguments (and the use of (H) and Fact 2.4) to find an uncountable subset Γ of ω_{1} such that:

(1) for ξ in Γ, | dom(q_{ξ})| does not depend on ξ;

(2) there is a γ < min(Γ) such that if ξ is in Γ, α ≠ α′ are in dom(q_{ξ}), and

Δ_{A}(α, α′) < ξ, then

Δ_{A}(α, α′) < γ
Δ_{C}(q_{ξ}(α), q_{ξ}(α′)) < γ;

2In this paper, p ≤ q means that p is a stronger condition in a given forcing notion.

(3) if ξ < η are in Γ, i < n, α is the i^{th} least element of dom(q_{ξ}) and α′ is the i^{th} least element of dom(q_{η}), then

γ < Δ_{A}(α, α′) < ξ
γ < Δ_{C}(q_{ξ}(α), q_{η}(α′)) < ξ;

(4) if ξ < η are in Γ, then every ordinal mentioned in q_{ξ} is less than every ordinal

mentioned in q_{η}. Such a sequence is said to be in standard form (with uniform size n). If only one such sequence is under discussion and ξ is in Γ, I will use ξ_{i} and qξ_{i} to denote the i^{th} <_{A}-least element of dom(q_{ξ}) and its respective image under q_{ξ}.

Returning to the proof, first refine to a sequence ⟨q_{ξ} : ξ ∈ Γ_{0}⟩ in standard form. Applying (H) n times, using the fact that C^{2n} is the union of countably many non decreasing relations, it is possible to find an uncountable Γ ⊆ Γ_{0} such that if ξ < η are in Γ, then for all i < n, ξ_{i} <_{A} η_{i} iff qξ_{i} <_{C} qη_{i} iff ξ_{0} <_{A} η_{0}. It suffices to show that Γ satisfies the conclusion of the lemma. To this end, let ξ < η be in Γ and let i, j < n.

First suppose that Δ(ξ_{i}, ξ_{j}) ≥ ξ. By definition of Γ_{0}, this implies Δ(η_{i}, η_{j}) ≥ η. Consequently, ξ_{i} <_{A} η_{j} iff ξ_{i} <_{A} η_{i} iff qξ_{i} <_{C} qη_{i} iff qξ_{i} <_{C} qη_{j} as desired. Notice that in the last equivalence we utilized that q_{η} respects η.

Now suppose that Δ(ξ_{i}, ξ_{j}) < ξ. Then Δ(ξ_{i}, ξ_{j}) = Δ(η_{i}, η_{j}) and Δ(qξ_{i}, qξ_{j}) = Δ(qη_{i}, qη_{j}). Hence ξ_{i} <_{A} ξ_{j} iff ξ_{i} <_{A} η_{j} and qξ_{q} <_{C} qξ_{j} iff qξ_{i} <_{A} qη_{j}. This finishes the proof. □

The lemma suggests that, for an appropriately chosen club E ⊆ ω_{1}, we consider the collection Q ⊆ Q_{0} of all q which respect E. Such an E will need to satisfy two conditions — one to ensure that Q satisfies the c.c.c. and the other to guarantee that certain sets are dense in Q.

Definition 3.5. A club E ⊆ ω_{1} is fast enough for A and C if whenever ⟨q_{ξ} : ξ < ω_{1}⟩ is a sequence of disjoint elements of Q_{0} which respect E and α < ω_{1}, there are ξ ≠ η greater than α such that q_{ξ} ∪q_{η} respects E. An ordinal ν < ω_{1} is said to be elementary for A and C iff there is a countable elementary submodel N of H(ω_{2}) such that A and C are in N and ν = N ∩ ω_{1}.

If E is fast enough for A and C and consists of elementary ordinals, then define Q to be all elements of Q_{0} which respect every element of E. It follows immediately from Lemma 3.4 and the definition of fast enough that Q satisfies the countable chain condition.

We now turn to the task of finding a fast enough club for a pair A and C.

Lemma 3.6. If A is Countryman and C is isomorphic to a suborder of A, then there is a club E which is fast enough for A and C.

Proof. Since A is Countryman, there are non decreasing relations R_{n} ⊆ A^{2} which cover A^{2}. Applying Lemma 3.3 and intersecting clubs, it is possible to find a club E such that if q is an element of Q_{0} which is a subset of some R_{n}, then for all α ≠ β in the domain of q and δ in E,

Δ_{A}(α, β) < δ ⇔ Δ_{A}(q(α), q(β)) < δ.

It suffices to show that E is fast enough for A and C.

To this end, suppose that ⟨q_{ξ} : ξ < ω_{1}⟩ is given sequence of elements of Q_{0} which each respect E. Select an uncountable Γ ⊆ ω_{1}, an n < ω, and natural numbers m_{i,j} for i < j < n such that if ξ is in Γ, then the domain of q_{ξ} has cardinality n and if i, j < n, then (ξ_{i}, qξ_{j}) is in R_{m_{i,j}}. It is now follows that if ξ < η are in Γ, then q_{ξ} ∪ q_{η} respects E. In particular, Γ satisfies the desired property with respect to E and ⟨q_{ξ} : ξ < ω_{1}⟩. □

Hence if both A and C are Countryman, then Q can be built in V and an application of MA_{ℵ_{1}} to the dense sets provided by Lemma 3.10 below suffices to obtain the conclusion of Theorem 1.1. The next lemma indicates that fast enough clubs always exist in appropriate generic extensions by σ-closed forcing notions. The argument of [1, §5] can be adapted to show that Baumgartner’s forcing for adding a club by finite approximations also can be used to generate fast clubs.

Lemma 3.7. (H) Suppose V [G] is a generic extension by a σ-closed forcing and E ⊆ ω_{1} is a club in V [G] such that for every club E′ ⊆ ω_{1} in V, E \ E′ is countable. Then E is fast enough for every A and C in V.

Remark 3.8. If the cardinality of 𝒫(ω_{1}) ∩ V is collapsed to ℵ_{1} by a σ-closed forcing, then in the extension, there is a club satisfying the hypothesis of Lemma 3.7.

Proof. Suppose for a moment that ⟨q_{ξ} : ξ ∈ Γ⟩ is a sequence in standard form of disjoint elements of Q_{0}. Another such sequence ⟨q′_{ξ} : ξ < Γ⟩ is Δ-equivalent to ⟨q_{ξ} : ξ < ω_{1}⟩ iff they have the same uniform size n and for all i, j < n

Δ(ξ_{i}, η_{j}) = Δ(ξ′_{i}, η′_{j})
Δ(qξ_{i}, qη_{j}) = Δ(qξ′_{i}, qη′_{j}).

(Here, e.g., ξ′_{i} and qξ′_{i} have the obvious meaning.) The following claim follows easily from [15, 8.13].

Claim 3.9. If G is generic for a σ-closed forcing, A and C are in V, and ⟨q_{ξ} : ξ ∈ Γ⟩ is an element of V [G] which is an uncountable sequence of disjoint elements of Q_{0}, then there is an uncountable subsequence which is Δ-equivalent to a sequence in V.

Finally notice that for a sequence ⟨q_{ξ} : ξ < ω_{1}⟩ as above, there is a club Eq⃗ which is fast enough for the sequence. Hence a club E as in the statement of the lemma is fast enough for all ground model sequences and therefore, by Claim 3.9, for all sequences in V [G] as well. □

Now we turn our attention to the relevant density lemma. The proof of this lemma is routine but somewhat tedious. Its proof was omitted in the analogous argument in [21, 2.1.12]. I have included it here for completeness and because this is where the (essential) assumptions of ℵ_{1}-density and non stationarity are used in the proof of Theorem 1.1.

Lemma 3.10. Suppose A and C are Aronszajn lines (C need not be Countryman). If C is non stationary and ℵ_{1}-dense and α is in A, then the set of all q in Q such that α is in the domain of q is dense in Q. Similarly, if A is non stationary and ℵ_{1}-dense and β is in C, then the set of all q in Q such that β is in the range of q is dense in Q.

Proof. By replacing the role of A and C and elements of Q with their inverses, it suffices to prove the first half of the lemma. Assume that C is non stationary and ℵ_{1}-dense and let q be an element of Q and α be in A. If ξ < ω_{1}, let δ(ξ) be the greatest element of E ∪ {0} which is less than or equal to ξ. If α ≠ α′ are in A, then δ_{A}(α, β) will be used to abbreviate δ(Δ_{A}(α, α′)) This is similarly defined for α ≠ α′ in C.

Let α_{0} and α_{1} be elements of dom(q) ∪ {−∞, +∞} such that α_{0} <_{A} α <_{A} α_{1} in A and there is no α′ ≠ α in dom(q) such that α_{0} <_{A} α′ <_{A} α_{1}. We will focus on the case where neither α_{0} nor α_{1} are ±∞ since the argument applies with routine modification to the degenerate cases. There are now three cases depending on the relationship between δ_{A}(α_{0}, α) and δ_{A}(α, α_{1}).

If δ_{A}(α_{0}, α) = δ_{A}(α, α_{1}), then observe that we also have

δ_{A}(α_{0}, α) = δ_{A}(α_{0}, α_{1}) = δ_{C}(q(α_{0}), q(α_{1})).

Let ν denote this common value and let ν^{+} be the least element of E greater than ν. Using elementarity of ν^{+} and ℵ_{1}-density of C, select β_{0} <_{C} β_{1} such that δ(β_{0}) = δ(β_{1}) = ν. Again using ℵ_{1}-density of C and elementarity of ν^{+}, choose an extension q̄ of q to α so that

δ(q̄(α)) = δ(α)
β_{0} <_{C} q̄(α) <_{C} β_{1}.

Observe that δ_{C}(q̄(α_{i}), q̄(α)) is at least ν by Fact 2.1 and at most ν as witnessed by β_{i}. Transitivity of <_{A} and <_{C} implies q̄ is in Q_{0} and Fact 2.1 can be used to verify that q̄ respects E and hence is in Q.

Now suppose that δ_{A}(α_{0}, α) ≠ δ_{A}(α, α_{1}). As the argument is similar in both cases, I will only present the proof for the case δ_{A}(α_{0}, α) < δ_{A}(α, α_{1}). By non stationarity of C and arguing as in the previous case, there is a β in C such that q(α_{0}) <_{C} β <_{C} q(α_{1}), δ(β) = δ(α), and δ_{C}(β, q(α_{1})) = δ_{A}(α, α_{1}). If q̄ is an extension of q to α so that q̄(α) = β, then q̄ is in Q as desired. □

Finally, in Section 5 it will be useful to have the following lemma.

Lemma 3.11. (MA_{ℵ_{1}}) Suppose that C is Countryman. Then there is an uncountable suborder C_{0} of C which is isomorphic to C such that whenever x is in C \ C_{0}, there is a set H ⊆ C which is isomorphic to ℚ such that x is in H and no two elements of H have an element of C_{0} between them.

This can be accomplished by applying Theorem 1.3 to A = C × ℚ for any C (the above arguments show MA_{ℵ_{1}} is sufficient). This gives an embedding of C × ℚ into C and, setting C_{0} equal to the image of C × {0}, we have the desired suborder.

Remark 3.12. The existence of a pair C_{0} ⊆ C as in Lemma 3.11 does not require the assumption of MA_{ℵ_{1}}. This can be achieved either by modifying the constructions of [21] or invoking Keisler’s completeness theorem for ℒ_{ω_{1}ω}(Q) [5].

4. Families of Aronszajn subtrees and PFA

In the proof that η_{C} is universal, we will be interested in certain collections of subtrees of an Aronszajn tree T. In this section I will recall some the result of [6] which will be needed and also prove some additional related lemmas. For ease of reading, T will denote an arbitrary Aronszajn tree for the duration of this section. A subset U ⊆ T is a subtree if U is uncountable and downward closed — whenever s < t are in T with t in U, it follows that s is in U.

Definition 4.1. A collection ℱ of subtrees of T is predense if whenever U is a subtree of T, there is a V in ℱ such that U ∩ V is uncountable (and hence a subtree). If ℱ is a collection of subtrees, then ℱ^{⊥} will be used to denote the set of all subtrees U of T which have countable intersection with every element of ℱ.

Notice that trivially ℱ ∪ ℱ^{⊥} is predense. Also, it is trivial that (ℱ^{⊥})^{⊥} contains ℱ, though in general one does not expect equality to hold.

In order to motivate our interest in these definitions, suppose that T is equipped with a lexicographic order and that C is a Countryman line. Let ±ℱ consist of all subtrees U of T which are embeddable into ±C when equipped with the inherited lexicographic order. It should be clear that every element of +ℱ has countable intersection with every element of −ℱ or, equivalently, that ±ℱ ⊆ ∓ℱ^{⊥}. This follows from the basic property of Countryman lines mentioned in the introduction.

Recall the following theorem of [6].

Theorem 4.2. (PFA) If ℱ is a collection of subtrees of T, then there are ⟨U_{ξ} : ξ < ω_{1}⟩, ⟨V_{ξ} : ξ < ω_{1}⟩, and a club E ⊆ ω_{1} such that:

(1) For all ξ < ω_{1}, either U_{ξ} is in ℱ or is empty and V_{ξ} is in ℱ^{⊥} or is empty.

(2) If t is in T with height δ in E, then either: (a) there is a ξ < δ such that t is in V_{ξ} or

(b) there is a δ_{t} < δ such that if ν is in E with δ_{t} < ν < δ, then there is a ξ < ν with t ↾ ν in U_{ξ}.

If ℱ = (ℱ^{⊥})^{⊥}, then it is possible to draw a stronger, simpler conclusion.

Theorem 4.3. (PFA) If ℱ is a collection of subtrees such that ℱ = (ℱ^{⊥})^{⊥}, then there is a sequence ⟨U_{ξ} : ξ < ω_{1}⟩ of elements of ℱ ∪ ℱ^{⊥} and a club E ⊆ ω_{1} such that if t is in T of height δ in E, then there is a ξ < δ such that t is in U_{ξ}.

Now we will return to our example.

Lemma 4.4. (PFA) Suppose that +ℱ and −ℱ are defined as above. If U is a subtree of T and U has countable intersection with every element of ±ℱ, then U is in ∓ℱ (i.e. ±ℱ^{⊥} = ∓ℱ).

Proof. Since −C is also Countryman, it suffices to prove that +ℱ^{⊥} = −ℱ. Suppose that U is an arbitrary subtree of T. By Theorem 1.3, it suffices to prove that either U has uncountable intersection with some element of +ℱ or else every uncountable subset of U contains an uncountable suborder which embeds into −C. Let X be an arbitrary uncountable subset of U. By [10], there is a subset Y of X which is isomorphic to either C or −C. If it is always the case that this set Y is isomorphic to −C, then we are done.

If Y is isomorphic to C, then I claim that the downward closure V of Y must be an element of +ℱ. Again, by appealing to Theorem 1.3, it is sufficient to show that if Z is any uncountable subset of V, then Z contains a subset embeddable into C. To see that this is indeed the case, let Z ⊆ V be uncountable and select an uncountable Z_{0} ⊆ Z which is an antichain in the tree order. For each z in Z_{0}, let ϕ(z) be an element of Y such that z ≤ ϕ(z) in the tree order on T. It follows from the definition of lexicographic ordering that ϕ preserves the lexicographic order and hence embeds Z_{0} into an isomorphic copy of C. This finishes the proof. □

5. PFA implies η_{C} is universal

I am now ready to argue that PFA implies that η_{C} is universal. In this section A and C will be as in Section 2 and, for brevity, the subscript of A in T_{A} and Δ_{A} will be suppressed. Also, fix a C_{0} ⊆ C as in Lemma 3.11.

Applying the results of Section 4, fix a sequence ⟨U_{ξ} : ξ < ω_{1}⟩ of closed subtrees of T and a club E ⊆ ω_{1} satisfying the conclusions of the Lemma 4.3. Let σ_{ξ} ∈ {+, −} be such that U_{ξ} is in σ_{ξ}ℱ and pick f_{ξ} : U_{ξ} → σ_{ξ}C_{0} which is order preserving. Here we view the range of f_{ξ} as a subset of ζ_{C}. Define Û_{ξ} for ξ < ω_{1} to be the set of all s in S with length in E such that either s is in U_{ξ} or else the length of s is at most the least element of E greater than Δ(s, U_{ξ}). Notice that, for a fixed ξ < ω_{1}, every interval of Û_{ξ} which is disjoint from U_{ξ} is countable. It follows that f_{ξ} can be extended to an order preserving map from Û_{ξ} to C. This extension will also be denoted by f_{ξ}.

Since A is isomorphic to a suborder of T, it is sufficient to define an order preserving map from T into η_{C}. If t is in T, define two finite sequences ⟨ξ_{i} : i < k⟩ and ⟨ν_{i} : i < k⟩ of ordinals as follows. Set ν_{0} equal to the least element of E. If ν_{i} has been defined, ξ_{i} is the least ordinal such that t ↾ ν_{i} is in U_{ξ_{i}}. If ξ_{i} has been defined and t is not in U_{ξ_{i}}, let ν_{i+1} be the least element of E such that t ↾ ν_{i+1} is not in U_{ξ_{i}}. Let k be minimal such that t is in U_{ξ_{k−1}}. Notice that, for all i < k, t ↾ ν_{i} is in Û_{ξ_{i}}. Define Φ(t) in η_{C} as follows. If i < k, put Φ(t)(i) = f_{ξ_{i}}(t ↾ ν_{i}) and if i ≥ k, put Φ(t)(i) = 0.

It now suffices to show that Φ preserves order. Suppose that s <_{lex} t be in T and let γ be the least ordinal such that s(γ) ≠ t(γ). The sequences of ξ_{i}’s and ν_{i}’s which are constructed for s and t coincide at least until ν_{i} is greater than γ; let i be maximal such that ν_{i} ≤ γ. We know that s ↾ γ = t ↾ γ is in U_{ξ} and therefore that s ↾ (γ + 1) and t ↾ (γ + 1) are in Û_{ξ}.

Observe that since s ↾ ν_{i} = t ↾ ν_{i}, Φ(s)(j) = Φ(t)(j) for all j < i. Also, s <_{lex} t iff s ↾ ν_{i+1}^{s} <_{lex} t ↾ ν_{i+1}^{t} iff s ↾ (γ + 1) <_{lex} t ↾ (γ + 1). It follows that s <_{A} t iff Φ(s)(i) <_{ζ_{C}} Φ(t)(i) iff Φ(s) <_{η_{C}} Φ(t). Since s and t were arbitrary, Φ preserves order.

6. Concluding remarks and questions

As mentioned in the introduction, the results of this paper suggest an analogy between the relationship of ω and −ω to η = otp(ℚ) and the relationship of C and −C to η_{C} under the assumption of PFA. In this analogy, ζ_{C} corresponds to the order type ζ of ℤ. Notice that, just as any linear order which does not contain η must contain a non empty interval which is embeddable into ω or −ω, we have the following proposition.

Proposition 6.1. (PFA) If A is an Aronszajn line, then either A is bi-embeddable with C or else A contains a non empty interval which is bi-embeddable with C or −C.

If we define an Aronszajn line to be fragmented^{3} if it does not contain a copy of η_{C}, then the above analogy extends to give a strong connection between the (countable) scattered linear orders and the fragmented Aronszajn lines. In particular, one can associate a rank to a fragmented Aronszajn line which corresponds to how many applications of a derivative operation are necessary in order to trivialize it.

3This definition is only appropriate under a hypothesis such as PFA.

Laver has shown the countable linear orders are well quasi-ordered by embeddability [9] and the above analogy suggests the following conjecture.

Conjecture 6.2. (PFA) The Aronszajn lines are well quasi-ordered by embeddability.

This could be verified using the methods of [9] if one could prove the following from PFA (see [9] for undefined notions): If Q is a better quasi-order and C is a Countryman line, then Q^{C} is a better quasi-order.

Finally, it should be noted that some large cardinal assumptions are likely necessary in order to establish the relative consistency of the results in this paper. The results of [6] show that all of the conclusions mentioned in this paper can be established consistent relative to the existence of a Mahlo cardinal. The conclusion of Theorem 4.2 implies that there are no Kurepa trees and hence has the consistency strength of at least an inaccessible cardinal. It is an open problem, however, whether the conclusion of Theorem 1.2 has any non-trivial consistency strength. It is also an intriguing problem whether the conclusion of Theorem 1.2 implies |ℝ| ≤ ℵ_{2}.

Acknowledgments

This research was supported by NSF grants DMS–0401893 and DMS–0757507. I would like to thank Max Burke for his careful reading and review of [10]. The presentation in Section 3 owes much to my conversations with him while he was preparing the review.

References

[1] U. Abraham and S. Shelah, Isomorphism types of Aronszajn trees, Israel J. Math. 50 (1985), no. 1-2, 75–113.

[2] J. Baumgartner, Topological properties of Specker types, Notices Amer. Math. Soc. 22 (1975) 219.

[3] M. Goldstern and S. Shelah, The Bounded Proper Forcing Axiom, J. Symbolic Logic 60 (1995), no. 1, 58–73.

[4] T. Jech, Set theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, second edition (1997).

[5] H. J. Keisler, Logic with the quantifier “there exist uncountably many”, Ann. Math. Logic 1 (1970) 1–93.

[6] B. König, P. Larson, J. T. Moore, and B. Veličković, Bounding the consistency strength of a five element linear basis, Israel Journal of Math (to appear in 2008).

[7] K. Kunen, An introduction to independence proofs, Vol. 102 of Studies in Logic and the Foundations of Mathematics, North-Holland (1983).

[8] D. Kurepa, Ensembles ordonnés et ramifiés, Publ. Math. Univ. Belgrade 4 (1935) 1–138.

[9] R. Laver, On Fraïssé’s order type conjecture, Ann. of Math. (2) 93 (1971) 89–111.

[10] J. T. Moore, A five element basis for the uncountable linear orders, Annals of Mathematics (2) 163 (2006), no. 2, 669–688.

[11] ———, ω_{1} and ω_{1} may be the only minimal uncountable order types, Michigan Math. Journal 55 (2007), no. 2, 437–457.

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

[13] ———, Proper and improper forcing, Springer-Verlag, Berlin, second edition (1998), ISBN 3-540-51700-6.

[14] M. Souslin, Problème 3, Fund. Math. 1 (1920) 223.

[15] S. Todorcevic, Trees and linearly ordered sets, in Handbook of set-theoretic topology, 235–293, North-Holland, Amsterdam (1984).

[16] ———, Partitioning Pairs Of Countable Ordinals, Acta Math. 159 (1987), no. 3–4, 261–294.

[17] ———, Partition Problems In Topology, Amer. Math. Soc. (1989).

[18] ———, Aronszajn orderings, Publ. Inst. Math. (Beograd) (N.S.) 57(71) (1995) 29–46. D̄uro Kurepa memorial volume.

[19] ———, A classification of transitive relations on ω_{1}, Proc. London Math. Soc. (3) 73 (1996), no. 3, 501–533.

[20] ———, Basis problems in combinatorial set theory, Doc. Math. Extra Vol. II (1998) 43–52.

[21] ———, Walks on ordinals and their characteristics, Vol. 263 of Progress in Mathematics, Birkhäuser (2007).

[22] W. H. Woodin, The Axiom of Determinacy, Forcing Axioms, and the Nonstationary Ideal, Logic and its Applications, de Gruyter (1999).

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

   E-mail address: justin@math.cornell.edu