STRUCTURAL ANALYSIS OF ARONSZAJN TREES

JUSTIN TATCH MOORE

Abstract. In this paper I will survey some recent developments in the combinatorics of Aronszajn trees. I will cover work on coherent and Lipschitz trees, the basis problem for uncountable linear orderings, subtree bases for Aronszajn trees, and the existence of minimal Aronszajn types.

1. Introduction

An Aronszajn tree is an uncountable tree in which all levels and chains are countable. These objects were first constructed by Aronszajn and Kurepa in the course of analyzing Souslin’s Hypothesis. Their study, both in and outside of the context of Souslin’s Hypothesis, has played an important role in the development of set theory ever since. For example, the complete solution of Souslin’s problem represented both some of the pioneering work on the fine structure of the constructible universe by Jensen (see [8]) as well as the birth of the forcing axioms in Solovay and Tennenbaum’s [25]. Todorcevic’s analysis of Aronszajn trees in [29] led to his method of minimal walks which has seen wide and varied applications — see [34].

In [28], Todorcevic presented a survey of trees and linear orderings. At the time it appeared, it captured essentially all of the existing knowledge of Aronszajn trees and lines. The purpose of this article is to survey some of the developments in the study of Aronszajn trees which have occurred since [28]. I will focus on Aronszajn trees which are not Souslin with an emphasis on results which address the structure of these trees both as individuals and as a class.

2000 Mathematics Subject Classification. Primary: 03E05, 03E75, 06A07; Secondary: 03E55, 03E65.

Key words and phrases. Aronszajn tree, basis problem, coherent tree, Countryman line, forcing axiom, Lipschitz tree, non-Suslin base, Shelah’s conjecture, ladder system uniformization.

I would like to acknowledge support provided by NSF grant DMS–0401893.

I would also like to acknowledge partial travel support provided by the ASL to present some of the material surveyed in this article at the 2005 Logic Colloquium in Athens, Greece.

The topics are organized in approximate chronological order. I will begin with some preliminaries on trees in Section 2. Todorcevic’s analysis of coherent and Lipschitz trees is detailed in Sections 3 and 4. Section 5 discusses Shelah’s conjecture for Aronszajn orders and its proof in [20]. Section 6 surveys Baumgartner’s, Hanazawa’s, and Todorcevic’s work on bases for the subtrees of an Aronszajn tree. Section 7 presents joint work with König, Larson, and Veličković in [12] on the consistency strength of Shelah’s conjecture. Aronszajn tree uniformization and its relation to the consistency of “ω_{1} and ω_{1}^{∗} are the only minimal uncountable order types” is discussed in Section 8. The paper closes with some open questions in Section 9.

The reader of this paper is assumed to have some fluency in set theory; [11] and [13] are standard references for background material.

2. Preliminaries

In this section I will present some of the prerequisites on trees and fix some notation and terminology. Further reading can be found in [28]. The end of this section will also provide some discussion of the axioms which I will be quoting from time to time.

Recall that a tree is a partial ordering (T, <) in which the predecessors of any given t in T are well ordered by <. The order type of this set is called the height of t. All trees in this paper are assumed to be Hausdorff — whenever t ≠ t′ both have limit height, they have a different set of predecessors. The set of all elements of T of a given height δ is denoted T_{δ} and called the δ^{th}-level of T. The least strict upper bound for the heights of elements of T is known as the height of T.

Trees of height ω_{1} in which all levels are countable are known as ω_{1}- trees. Those which moreover have no uncountable chains are known as Aronszajn trees or simply A-trees. The following operations are central to the analysis of an A-tree T.

Definition 2.1. If t is in T and α is an ordinal, then t ↾ α is t if α is at least the height of t and otherwise is the element s of T such that s < t and the height of s is α.

Definition 2.2. If s and t are incomparable elements of T, then Δ(s, t) is the greatest ordinal ζ such that s ↾ ζ = t ↾ ζ.

Definition 2.3. If s and t are incomparable elements of T, then s ∧ t is the restriction

s ↾ Δ(s, t) = t ↾ Δ(s, t)

Frequently it will be helpful to utilize the following notation. Typically we will be interested in the cases F = Δ(·, ·) and F = ∧(·, ·).

Definition 2.4. Suppose that F is defined on a subset of T^{k} for some k. If A is a subset of T, then F (A) is the set of all F (ā) such that ā is in the intersection of A^{k} and the domain of F.

Collections of pairwise incomparable elements in T play an important role in the study of A-trees — they are known as antichains. An important subclass of the A-trees are the special A-trees — those which can be covered by countably many antichains.

The study of A-trees is connected to the study of A-lines — those uncountable linear ordering which do not contain a real type, ω_{1}, or ω_{1}^{∗} — by the following definition.

Definition 2.5. If (T, <) is a tree, then a linear ordering ≤_{lex} on T is a lexicographical ordering if, for distinct s and t in T, s ≤_{lex} t is equivalent to s ↾ (ζ + 1) ≤_{lex} t ↾ (ζ + 1) where ζ = Δ(s, t) if s and t are incomparable and ζ = min{ht(s), ht(t)} otherwise.

Any lexicographical ordering on an A-tree is an A-line and every Aline can be represented as a suborder of a lexicographical ordering on an A-tree (see [28]).

Frequently we will be interested in the notion of a subtree of an Atree. There are different ways one can make this precise; we will use the following as our definition.

Definition 2.6. A subtree of an A-tree T is an uncountable subset of T which is closed under the ∧-operation.

Definition 2.7. A subset U of an A-tree T is downwards closed if t ≤ u and u in U implies t is in U.

It is worth noting that if A is an uncountable subset of an A-tree T, then ∧(A) is a subtree of T (in particular, ∧(A) is uncountable). Notice that if A is a downward closed subset of T, then ∧(A) is the set of all members of T which have two or more immediate successors.

Since many statements about A-trees are independent of ZFC, one cannot have a serious discussion of modern work on A-trees without some mention of additional axioms of set theory. That said, I will not define these axioms here and will refer the interested reader to other standard sources.

The additional axioms we will consider fit into two classes. The axioms CH, ♢, and ♢^{+} are progressively stronger axioms which all are consequences of V = L. They are sometimes referred to as enumeration principles as they enable the construction objects with second order properties — such as Souslin trees — by diagonalizations of length ω_{1}. Moreover, ♢^{+} settles most statements about ω_{1}. Each of these can be forced by a σ-closed forcing (see [13]). Further reading can be found in [8], [11], and [13].

The axioms MA_{ℵ_{1}}, PFA(κ), and PFA also represent a progressively stronger list of axioms which act as alternatives to the enumeration principles above. These are examples of forcing axioms. They can be viewed as postulating forms of Σ_{1}-absoluteness between V and its generic extensions. The weakest of these axioms — MA_{ℵ_{1}} — was introduced in [25] in the course of proving the consistency of Souslin’s Hypothesis. The methods of [25] establish its consistency and it in turn implies Souslin’s Hypothesis. MA_{ℵ_{1}} negates CH; in general forcing axioms serve to limit diagonalization constructions of length ω_{1} to those which can be carried out in ZFC. The Proper Forcing Axiom (PFA) has considerable consistency strength; the best known upper bound is the existence of a supercompact cardinal. If κ is an uncountable cardinal, then PFA(κ) is a weakening of PFA introduced in [9] which essentially captures the consequences of PFA for statements about subsets of κ. PFA(ℵ_{1}) is also known as the Bounded Proper Forcing Axiom. While BPFA itself has large cardinal strength — it is equiconsistent with a reflecting cardinal [9] — a number of its consequence cited here have no large cardinal strength. I will use BPFA^{∗} to mean that BPFA is used as a hypothesis and that the stated consequence is consistent relative only to ZFC. Further information on MA_{ℵ_{1}} and PFA can be found in [6], [22], [30]. Reading on PFA(κ) can be found in [9], [15], and [32].

The reader who wishes to simplify the axiomatic picture can replace all the assumptions in this paper with either ♢^{+} or PFA and not lose too much information. Still, the results in Section 7 cannot be appreciated without a finer stratification of the forcing axioms.

3. Coherent trees and Countryman orders

One of the most important notions in the modern analysis of A-trees is that of a coherent tree.

Definition 3.1. [29] A coherent sequence (of length ω_{1}) is a sequence e_{β} (β < ω_{1}) such that the range of each e_{β} is contained in ω and if β ≤ β′ < ω_{1}, then

{ξ < β : e_{β}(ξ) ≠ e_{β′}(ξ)}

is finite. For such a sequence ē, we can consider

T (ē) = {e_{β} ↾ α : α ≤ β < ω_{1}}

as a tree ordered by end extension. Trees having this form are said to be coherent.

Not all coherent trees are Aronszajn: Let T (∅) be the tree of all countable length sequences of elements of ω with finite support. Every uncountable ∧-closed subset of T (∅) has an uncountable chain. It is easily seen, however, that every coherent tree with a co-final branch can be embedded into T (∅). A natural condition on ē which ensures the non-existence of an uncountable branch in T (ē) is that each e_{β} is finite-to-one. While such sequences can be routinely constructed by transfinite induction, we will see momentarily that natural examples can simply be defined by a recursive formula from an appropriate parameter. We will see in the next section that Coherent trees are, in a sense that can be made precise, the irreducible A-trees.

When lexicographically ordered, such sequences give natural examples of Countryman lines — uncountable linear orderings C such that the coordinatewise partial order on C^{2} is the union of countably many chains. The existence of such orderings was first proved in [21]. As we will see in Section 5, the existence of Countryman lines has important implications for the basis problem for uncountable linear orders.

Theorem 3.2. [29] If C = {e_{β} : β < ω_{1}} is a coherent sequence of finite-to-one functions, then C is Countryman when given the lexicographical ordering.

Now we will give the standard example of a coherent sequence of finite-to-one functions. First we will need a definition.

Definition 3.3. A C-sequence (on ω_{1}) is a sequence C_{α} (α < ω_{1}) such that C_{α} ⊆ α is co-final in α and if ζ < α, then C_{α} ∩ ζ is finite for each α < ω_{1}.

Example 3.4. [29] If α ≤ β, define ϱ_{1}(α, β) recursively by

ϱ_{1}(α, α) = 0
ϱ_{1}(α, β) = max (ϱ_{1}(α, min(C_{β} \ α)), |C_{β} ∩ α|).

Alternately,

ϱ_{1}(α, β) = max_{i<l} |C_{ζ_{i}} ∩ α|

where ζ_{0} = β, ζ_{i+1} = min(C_{ζ_{i}} ∩ α) if ζ_{i} > α and l is such that ζ_{l} = α. Set e_{β}(α) = ϱ_{1}(α, β). Then e_{β} (β < ω_{1}) is a coherent sequence of finite-to-one functions.

While it does not quite fall within the scope of this article, let me also point out that the ZFC construction of an L space in [19] is a consequence of the study of certain A-trees such as T (ϱ_{1}). A wide variety of other constructions and applications of the method of minimal walks is presented in [34].

4. The structure of the class of Lipschitz trees

The class of trees themselves are equipped with a number of natural quasi-orderings. The one of interest to us here will be defined by S ≤ T iff there is a strictly increasing function from S into T. The restriction of this ordering to the class 𝒜 of A-trees is already an interesting object to study.

While it was shown in [1] that every two A-trees are consistently club isomorphic, the order ≤ and the corresponding equivalence ≡ allowed for a finer study of A-trees. For example, Laver asked in [14] whether the class of A-trees was well quasi-ordered^{1} by the stronger quasiorder in which the embedding is required to preserve meets after showing that the class of σ-scattered trees is w.q.o. under this quasiorder.

Over the course of several years, Todorcevic produced a number of results regarding this question. The culmination of this work is [26] in which he proves Theorems 4.2 and 4.3 below, giving a strong negative answer to Laver’s question.

Todorcevic showed that coherent trees can be used to construct examples of trees S and T such that S < T; before this is was not even known that the collection of ≡-equivalence classes was infinite.

Example 4.1. [26] Suppose that T is a coherent tree. If t is in T, define t^{+} by

t^{+}(ξ + 1) = t(ξ)

whenever ξ + 1 is in the domain of t and setting t^{+}(ξ) = 0 if ξ is a limit ordinal. Put T^{+} = {t^{+} : t ∈ T }. Then t ↦ t^{+} witnesses that T ≤ T^{+}. It is furthermore possible to show that T < T^{+}.

Theorem 4.2. [26] There are coherent A-trees S_{m} (m ∈ ℤ) such that m < n implies S_{m} < S_{n}.

Theorem 4.3. [26] There is a family ℱ of cardinality 2^{ℵ_{1}} which consists of pairwise incomparable A-trees.

1A reflexive, transitive relation ≤ is a well quasiorder if whenever A_{i} (i < ω) is a sequence of its elements, there are i < j such that A_{i} ≤ A_{j}. This is equivalent to ≤ being both well founded and not containing infinite antichains.

The first result is obtained by finding a tree S for which the inverse of the shift operation in Example 4.1 gives a meaningful output and which can moreover be iterated. The latter result is obtained by carefully “gluing” a number of coherent trees together.

Coherent trees turn out to play a special role in the study of (𝒜 , ≤). The following definitions play a central role in [26].

Definition 4.4. [26] If T is an A-tree and f is a partial map from T to T which is level preserving, then we say f is Lipschitz if

Δ(s, t) ≤ Δ(f(s), f(t))

for all s, t in the domain of f.

Definition 4.5. [26] An ω_{1}-tree T is Lipschitz if whenever f : T → T is a partial level preserving map with uncountable domain, there is an uncountable restriction of f which is Lipschitz. Let 𝒞 denote the collection of all Lipschitz trees.

While the limitation of this definition to A-trees is in part to prevent trivial discussion, any meaningful extension of this notion already implies that the tree is Aronszajn. For instance, if the tree is uncountable and has the property that every two elements have incomparable extensions, then the above condition implies that the tree is Aronszajn.

While Definition 4.5 is appealing from an aesthetic point of view, the following theorem gives an equivalent formulation which is more useful in applications.

Lemma 4.6. [26] Suppose that T is a Lipschitz tree, Ξ ⊆ ω_{1} is uncountable, and a_{ξ} (ξ ∈ Ξ) are such that a_{ξ} ⊆ T_{ξ} has a fixed finite size k for ξ ∈ Ξ. There is an uncountable Ξ′ ⊆ Ξ such that if ξ ≠ η are in Ξ′, then

Δ(a_{ξ}(i), a_{η}(i))

does not depend on i for i < k.

Here and elsewhere a(i) is the i^{th} least element of a in some fixed lexicographical ordering on T. This lemma is often combined with the following standard Lemma.

Lemma 4.7. Suppose that T is an A-tree, Ξ ⊆ ω_{1} is uncountable, and a_{ξ} (ξ ∈ Ξ) are such that a_{ξ} ⊆ T_{ξ} has a fixed finite size k for ξ ∈ Ξ. There is an uncountable Ξ′ ⊆ Ξ such that if ξ ≠ η are in Ξ′, then

Δ(a_{ξ} ∪ a_{η}) \ (Δ(a_{ξ}) ∪ Δ(a_{η})) = {Δ(a_{ξ}(i), a_{η}(i)) : i < k}.

The following theorems shows that there is a rather natural necessary and sufficient condition for a coherent tree to be Lipschitz.

Theorem 4.8. [26] A coherent tree is Lipschitz iff every uncountable subset contains an uncountable antichain.

In the presence of MA_{ℵ_{1}}, the converse is true as well.

Theorem 4.9. [26] Assuming MA_{ℵ_{1}}, every Lipschitz tree is isomorphic to a coherent tree.

As mentioned above, under an appropriate hypothesis, Lipschitz trees are irreducible objects.

Theorem 4.10. [26] (MA_{ℵ_{1}}) If S is a downwards closed subtree of a Lipschitz tree T, then S ≡ T.

The following combinatorial object is useful both as an invariant and as a tool in the study of Lipschitz trees.

Definition 4.11. [26] Suppose that T is a Lipschitz tree. Define

𝒰 (T) = {X ⊆ ω_{1} : ∃S ⊆ T (S is a subtree) and (Δ(S) ⊆ X)}.

Theorem 4.12. [26] If T is a Lipschitz tree, then 𝒰 (T) is a filter.

This is a routine consequence of Lemma 4.6. Furthermore, if one makes a rather mild set theoretic assumption, then 𝒰 (T) measures all subsets of ω_{1}.

Theorem 4.13. [26] MA_{ℵ_{1}} implies that 𝒰 (T) is an ultrafilter for every Lipschitz tree T.

Hence, assuming MA_{ℵ_{1}}, 𝒰 (T) is an example of a uniform ultrafilter on ω_{1} which is Σ_{1}-definable over H(ℵ_{1}^{+}), a fact of independent interest. It is well known, for instance, that there is no uniform ultrafilter on ω which is Σ_{1}-definable over H(ℵ_{0}^{+}). Notice that the number of elements required to generate 𝒰 (T) is at most the cardinality of a subtree base for T. Hence if T has a subtree base of cardinality ℵ_{1}, 𝒰 (T) is not an ultrafilter.

Rather remarkably, assuming MA_{ℵ_{1}} the ultrafilters 𝒰 (T) provide a complete invariant for (𝒞 , ≤).

Theorem 4.14. (MA_{ℵ_{1}}) Suppose that S and T are Lipschitz trees. The following are equivalent:

(1) S ≤ T

(2) S ≯ T

(3) There is an f : ω_{1} → ω_{1} such that ξ ≤ f(ξ) for all ξ < ω_{1} and

f(𝒰 (S)) = 𝒰 (T). In particular, two element of 𝒞 are equivalent iff their corresponding ultrafilters are equal.

Also, if we make the following definition, we can work in the broader context of A-trees.

Definition 4.15. If T is an A-tree, let ℱ (T) be the collection of all X ⊆ ω_{1} such that T can be covered by countably many sets Z such that Δ(Z) ⊆ X.

Since the collection of partitions of a set into countably many pieces is directed when given the order of refinement, ℱ (T) is a filter. Notice that if t has height δ, then

Δ({s ∈ T : s is comparable with t}) ⊆ ω_{1} \ δ.

Since T_{δ} is countable, ℱ (T) contains every co-countable subset of ω_{1}. Clearly ℱ (T) ⊆ 𝒰 (T), even when T is not Lipschitz and 𝒰 (T) is not necessarily a filter. If T is a Souslin tree, then ℱ (T) is exactly the co-countable subsets of ω_{1}.

The method of proof of Theorem 4.13 can be used to prove the following theorem.

Theorem 4.16. (MA_{ℵ_{1}}) If T is a Lipschitz tree, then ℱ (T) is an ultrafilter and therefore is equal to 𝒰 (T).

Hence, in the context of MA_{ℵ_{1}}, ℱ (T) can be viewed as a generalization of 𝒰 (T) to the class of all A-trees.

Finally, we have the following result which contrasts Theorem 4.3 and shows that the amalgamation of coherent trees is necessary to obtain this result.

Theorem 4.17. [26] (BPFA^{∗}) The collection 𝒞 is a chain which is both co-final and co-initial in (𝒜 , ≤) and which has neither a maximal nor minimal element.

5. Partitions of A-trees and Shelah’s Conjecture

In this section we will discuss a conjecture of Shelah and its recent solution.

Conjecture 5.1. [21] It is consistent that every Aronszajn line contains a Countryman suborder.

This conjecture will subsequently referred to in this paper as Shelah’s Conjecture. First let us consider the motivation for this conjecture. In [2], Baumgartner showed that it is consistent with the usual axioms of set theory that every two ℵ_{1}-dense sets of reals are isomorphic. In fact, he showed that this conclusion follows from PFA.

In particular, BPFA^{∗} implies that the uncountable separable linear orderings have a single element basis consisting of an arbitrary set of reals of size ℵ_{1}.

It is tempting to believe that an analogous result might follow for the class of Aronszajn lines as well. In such simplicity, however, this is false. Shelah proved in [21] that there is a Countryman line — an uncountable linear ordering C such that C^{2} is the union of countably many chains. This refuted a conjecture made by Countryman a few years prior [7]. Countryman orders are necessarily Aronszajn; I will leave this as an exercise to the interested reader.

A key property of Countryman orders is that, unlike ℵ_{1}-dense real types, they have distinct notions of “left” and “right.” If f is an order reversing map partial map from C into C, then f meets every chain in C^{2} in a singleton and therefore must be countable. It follows that C and C^{∗} are not near — no uncountable linear order embeds into both of them. In [21], it was conjectured however that consistently every two Countryman orders are either near or co-near — one is near the converse of the other.

The analysis of this conjecture then developed in the folklore for some time (see, e.g., p 79 of [1], [3], [4]). At some point it was proved that, assuming MA_{ℵ_{1}}, the Countryman lines have a two element basis, proving the second conjecture in [21]. The following theorem finally appeared in full in [26], with some of these equivalences being original to [26].

Theorem 5.2. (BPFA^{∗}) The following are equivalent:

(1) The uncountable linear orderings have a five element basis consisting of X, ω_{1}, ω_{1}^{∗}, C, and C^{∗} whenever X is a set of reals of cardinality ℵ_{1} and C is a Countryman line.

(2) Every Aronszajn order contains a Countryman suborder.

(3) For every A-tree T and every K ⊆ T, there is a subtree of T which is either contained in or disjoint from K.

(4) There is an A-tree T such that for every K ⊆ T, there is a subtree of T which is either contained in or disjoint from K.

(5) For every pair S and T of A-trees and every uncountable partial level preserving f from S into T, either f or f^{−1} has an uncountable Lipschitz restriction.

(6) If T is a Lipschitz tree, then T^{+} is the immediate successor of T in (𝒜 , ≤).

Remark 5.3. The implication 2 implies 3 is a theorem of ZFC.

In [20] I proved that Item 4 follows from PFA and in fact from the conjunction of BPFA and the Mapping Reflection Principle (MRP) introduced in [18]. Combining this with the above theorem yields the following results. Theorem 5.4. [20] (PFA) Every Aronszajn line contains a Countryman suborder. Corollary 5.5. [2] [20] [26] (PFA) The uncountable linear orderings have a five element basis consisting of X, ω_{1}, ω_{1}^{∗}, C, and C^{∗} whenever X is a set of reals of cardinality ℵ_{1} and C is a Countryman line.

In the remainder of this section I will present some of the motivation and insight which led to the proof. To this end, let T be a special coherent binary A-tree which is closed under finite modifications. Adding the finite modifications if necessary, the tree T (ϱ_{3}) of [34] is such an example.

The first standard approach toward building a forcing to introduce a subtree S ⊆ K is the following. Definition 5.6. ℋ (K) is the collection of all finite X ⊆ T such that ∧(X) is contained in K. ℋ (K) is considered as a forcing notion by giving it the order of reverse inclusion.

In fact, if one assumes that K is a union of levels of T, then ℋ (K) is either c.c.c. — in which case it forces that K contains a subtree — or else there is a subtree of T which is disjoint from K [26]. This is a direct consequence of Lemmas 4.6 and 4.7 and is how Theorem 4.13 is proved. Moreover, this shows that if 𝒰 (T) is not an ultrafilter, then the countable chain condition is not productive.

We will now examine how ℋ (K) may fail to be c.c.c. for an arbitrary K ⊆ T. For convenience we will let ℰ denote the collection of all clubs E ⊆ [H(ℵ_{1}^{+})]^{ℵ_{0}} which consist of elementary submodels which contain T and K as elements. Let E_{0} denote the element of ℰ which consists of all such submodels which have T and K as an element. The following object is a local version of 𝒰 (T). Definition 5.7. If P is in E_{0}, then ℐ_{P} (T) is the collection of all I ⊆ ω_{1} which are disjoint from some set of the form

{Δ(t, u) : u ∈ X}

where X is an uncountable subset of T in P, and t is a fixed element of the downward closure of X of height P ∩ ω_{1}.

A proof similar to that for Theorem 4.12 shows that ℐ_{P} (T) is an ideal. The same argument shows that the dual filter 𝒰_{P} (T) — which consists of complements of elements of ℐ_{P} (T) — extends 𝒰 (T) ∩ P.

Definition 5.8. If P is in E_{0} and X is a finite subset of T, then we say that P rejects X if

⋂_{t∈X}{γ < ω_{1} : t ↾ γ ∈ K}

is in ℐ_{P} (T).

The following observation is what motivates the definition of rejection.

Observation 1. Suppose that X is in ℋ (K) and that P is in E_{0}. X is rejected by P iff there is an uncountable antichain 𝒜 ⊆ ℋ (K) in P such that X ↾ δ is in 𝒜 where δ = P ∩ω_{1}. In particular, ℋ (K) satisfies the countable chain condition iff no element of ℋ (K) is rejected by any element of E_{0}.

The follows from applications of Lemmas 4.6 and 4.7 and the observation that — since T_{δ} is countable — there are Ξ ⊆ ω_{1} and ⟨a_{ξ} : ξ ∈ Ξ⟩ in P with δ ∈ Ξ and a_{ξ} = X ↾ δ.

Notice that ℋ (K) contains all of the singletons of elements of T. This provides an important special case of Observation 1.

Observation 2. If t is in T and some P in E_{0} rejects {t}, then there is a subtree of T which is disjoint from K.

A general form of Observation 1 can be phrased as follows.

Observation 3. If E is in ℰ, k < ω, and F_{ξ} (ξ < ω_{1}) is a sequence of disjoint k-element subsets of T such that no element of E rejects any member of the sequence, then there are ξ < η such that F_{ξ}(i) ∧ F_{η}(i) is in K for all i < k.

Notice that any sequence F_{ξ} (ξ < ω_{1}) as in Observation 1 can be refined using Lemma 4.7 so that, for any ξ, η < ω_{1}, any element of

∧(F_{ξ} ∪ F_{η}) \ ( ∧ (F_{ξ}) ∪ ∧(F_{η}))

is of the form F_{ξ}(i) ∧ F_{η}(i) for some i < k. Hence, while elements of the sequence may themselves have meets outside of K, the new meets in ∧(F_{ξ} ∪ F_{η}) can be arranged to all be in K.

The next observation shows that, assuming an appropriate hypothesis, the set of P in E_{0} which reject a given set X satisfies a dichotomy.

Observation 4. (MRP) There is a closed an unbounded subset D of H(2^{ℵ_{1}}^{+}) such that if X is a finite subset of T and N is in D, then there is an E ∈ ℰ ∩ N such that either

(1) every P in E ∩ N rejects X or (2) no P in E ∩ N rejects X.

Here MRP is the Mapping Reflection Principle introduced in [18] in the course of showing that BPFA implies |ℝ| = ℵ_{2}. For us, it suffices to know that Observation 4 follows from MRP which in turn follows from PFA, that MRP has considerable large cardinal strength well beyond that of BPFA, and that its consequences such as the above observation, can generally not be accomplished by a broad class of examples of proper forcings built by Todorcevic’s method of using models as side conditions [27] (see below).

These observations taken together suggest the consideration of another notion of compatibility based upon the definition of rejection. This is built into the following forcing using Todorcevic’s method of using models as side conditions.

Definition 5.9. ∂(K) consists of all pairs p = (X_{p}, 𝒩_{p}) such that: (1) 𝒩_{p} is a finite ∈-chain of elements of D.

(2) X_{p} ⊆ T is a finite set and if N is in 𝒩_{p}, then there is an E in ℰ ∩ N such that X_{p} is not rejected by any element of E ∩ N.

A variation of this forcing which is also relevant is

∂ℋ (K) = {p ∈ ∂(K) : X_{p} ∈ ℋ (K)}.

The proof of Theorem 5.4 can now be summarized as follows.

Lemma 5.10. [20] (BPFA) If ∂ℋ (K) is canonically proper,^{2} then there is a subtree S of T which is either contained in or disjoint from K.

Lemma 5.11. [20] (BPFA) If ∂ℋ (K) is not canonically proper, then neither is ∂(K).

Lemma 5.12. [20] (MRP) If ∂(K) is not canonically proper, then there is a c.c.c. forcing 𝒬 which does not have property K (in particular BPFA is false).

Observation 2 is used to show that if ∂ℋ (K) fails to meet density conditions, then there is a subtree S which is disjoint from K; this is the content of the proof Lemma 5.10. Lemma 5.11 is proved by showing that if ∂ℋ (K) is not canonically proper but ∂(K) is, then ∂(K) can be used to force a failure of Observation 3 which, by BPFA, would exist in V giving a contradiction. In the proof of Lemma 5.12, Observation 4 is used in the verification of the countable chain condition in the forcing 𝒬. The forcing 𝒬 is a collection of finite approximations to a failure of Observation 3 and therefore cannot have property K.

2∂ℋ (K) is canonically proper if p is (M, ∂ℋ (K))-generic whenever M is a countable elementary submodel of a suitable H(θ) and M ∩ H(2^{ℵ_{1}}^{+}).

We will now turn to the necessity of Observation 4. The following axiom gives a canonical failure of MRP at the level of ω_{1}.

℧: There are continuous functions f_{α} : α → ω for each α < ω_{1} such that if E ⊆ ω_{1} is closed and unbounded, then there is a limit point δ in E such that f_{δ} takes all values in ω on any final segment of E ∩ δ.

Theorem 5.13. [16] ℧ implies that there is an Aronszajn order with no Countryman suborder.

The significance of this construction is that instances of ℧ are quite robust. For example, in [16] is it shown that forcings which negate an instance of ℧ cannot be within the class of ϵ-collapse*c.c.c. forcings of [33]. These forcings capture most examples of built using Todorcevic’s method [27]. This class is moreover sufficient for nearly all applications of PFA: MA_{ℵ_{1}}, the isomorphism of all ℵ_{1}-dense sets of reals, the clubisomorphism of A-trees, the non-existence of S spaces and Kurepa trees, the failure of □(κ), OCA, and 2^{ℵ_{0}} = ℵ_{2}. The end of [20] presents an abstract form of Observation 4 which may be useful in handling this difficulty in future applications of PFA.

6. A basis for the subtrees of an A-tree

Before moving on to an analysis of the consistency strength of Shelah’s conjecture, it will be worthwhile recalling some older results of Baumgartner, Hanazawa, and Todorcevic concerning subtrees of Atrees. A basic question to ask regarding the subtrees of a given A-tree T is their co-initiality: what is the minimum cardinality of a collection ℱ of subtrees of T such that every subtree contains an element of ℱ as a subset? In the case of Souslin trees, this cardinal is trivially ℵ_{1} since every subtree of a Souslin tree contains one of the form

T [s] = {t ∈ T : s ≤ t or t ≤ s}.

I will refer to a co-initial family of subtrees as subtree base for T.^{3} In the papers discussed in this section, the notion of a subtree which was considered is that of a downward closed subtree. It is easily seen though, that if ℱ is co-initial in the downward closed subtrees, then {∧(S) : S ∈ ℱ } is co-initial in the subtrees.

The first paper to study the minimum cardinality of a subtree base is [10] in which the following result was proved.

3Subtree bases are sometimes referred to as anti-Souslin bases in the literature.

Theorem 6.1. [10] ♢^{+} implies that there is an A-tree which does not have a subtree base of size ℵ_{1}.

In fact the following example, due to Todorcevic (see [5]) shows that the existence of a Kurepa tree — an ω_{1}-tree with at least ℵ_{2} branches — suffices as a hypothesis.

Example 6.2. Let T be an A-tree and U be an ω_{1}-tree. Consider

T ⊗ U = {(t, u) ∈ T × U : ht(t) = ht(u)}.

Since the projection of chain in T ⊗ U onto the first coordinate is a chain in T, T ⊗U has no uncountable chains. Since both T and U have countable levels, so does T ⊗ U. Hence T ⊗ U is Aronszajn. If b is an uncountable branch in U, let

S_{b} = {(t, u) ∈ T ⊗ U : u ∈ b}.

For such a b, S_{b} is an uncountable subtree of T ⊗ U and if b ≠ b′ are uncountable branches through U, then S_{b} ∩ S_{b′} is countable. In particular any subtree base for T ⊗U must have at least the cardinality of the set of uncountable branches through U.

Remark 6.3. In [1] it was shown that if 2^{ℵ_{0}} = ℵ_{1} and 2^{ℵ_{1}} = ℵ_{2}, then there is a cardinal preserving proper forcing extension in which all A-trees are club-isomorphic. Hence, if there is a Kurepa tree in the ground model, no A-tree is saturated in the extension. Here a tree is said to be saturated if every family of subtrees with pairwise countable intersection has size at most ℵ_{1}. This observation is due to Todorcevic and shows that no Σ_{1}-property of an A-tree T — such as coherence — can imply even that the subtrees of T fail to contain an almost disjoint family of size ℵ_{2}.

On the other hand, we have the following result, discovered by Todorcevic and then independently by Baumgartner.

Theorem 6.4. [28, 8.13]; [5] Suppose that V [G] is a σ-closed forcing extension of V. If T is an A-tree in V and S is a subtree of T which is in V [G], then there is a subtree S_{0} of S with S_{0} in V.

An immediate consequence is the following result contrasting Theorem 6.1.

Theorem 6.5. [5] After Levy collapsing an inaccessible cardinal to ℵ_{2}, every A-tree has a subtree base of size ℵ_{1}.

The proof of Theorem 6.4 — like the result itself — can be considered as an extension of Silver’s argument that σ-closed forcings do not add new branches through ω_{1}-trees [24]. Using an appropriate closing off argument, it is possible to show that if p is an element of a σ-closed forcing and p forces that Ṡ is a downwards closed subset of Ť, then there is a q ≤ p and a δ < ω_{1} such that q forces Ṡ ∩ T_{δ} is empty.

While this was not the emphasis of [5], Theorem 6.4 reveals a rather uncommon phenomenon. Typically enumeration principles — especially those as strong as ♢^{+} — can be used to construct substructures with strong second order properties. For example, Sierpinski has shown that CH implies that every uncountable set of reals X contains a suborder Y such that there is no monotonic function from X into Y. This theorem shows that, in the case of an arbitrary A-tree T, there are considerable limitations the types of subtrees of T which can be constructed using even ♢^{+}. For instance, if V is a σ-closed extension of a model of MA_{ℵ_{1}}, then there is an A-tree — any A-tree which admits a Countryman lexicographical ordering suffices (see Section 5 below) — which club-embeds into all of its subtrees. The implications of this will be discussed some in Section 8.

In the next section we will be interested in the weaker assertion that no A-tree contains an almost disjoint family of subtrees of size ℵ_{2}. This assertion will be referred to as A-tree saturation. This statement shows up in the analysis of the consistency strength of Shelah’s Conjecture. The above argument shows that the consistency strength of this statement is exactly that of an inaccessible cardinal. Obtaining the consistency strength of this statement with, e.g., MA_{ℵ_{1}}, however, is a more subtle matter.

7. The consistency strength of Shelah’s Conjecture and A-tree saturation

Unlike many of the applications of PFA to statements about H(ℵ_{1}^{+}) given in the the past (see [30], [31]), the large cardinals in the proof of Theorem 5.4 cannot be immediately eliminated. In fact, even though Shelah’s Conjecture represents a conjunction of Σ_{1}-formulas in the language of H(ℵ_{1}^{+}), the assertion that ∂(K) is proper is not such a sentence in this language and it may be that the existence of a proper forcing which adds a K-homogeneous subtree for a given K ⊆ T is not a theorem of ZFC. Hence it is not even clear that PFA(ℵ_{1}) (a.k.a. BPFA) — which asserts that (H(ℵ_{1}^{+}), ∈) is Σ_{1}-elementary in every proper forcing extension — suffices to imply Shelah’s Conjecture.

Moreover, while PFA(ℵ_{1}) is equiconsistent with a reflecting cardinal [9], the best upper bound on the consistency strength of Theorem 5.4 provided by [20] is that of a cardinal δ which is H(2^{δ}^{+})-reflecting. The former is weaker in consistency strength than a Mahlo cardinal; the latter is, for instance, sufficient to force SRP(ω_{2}) and to prove the existence of inner models with many Woodin cardinals [32].

The search for a better bound led to [12] in which we investigated the consistency strength of Shelah’s Conjecture and, in particular, the hypothesis necessary to prove Observation 4. The following results are the culmination of this work.

Theorem 7.1. [12] PFA(ω_{2}) implies A-tree saturation.

Theorem 7.2. [12] The conjunction of PFA(ℵ_{1}) and A-tree saturation implies Shelah’s Conjecture. In particular, PFA(ω_{2}) implies Shelah’s Conjecture.

Theorem 7.3. [12] If κ is Mahlo, then there is a set forcing extension of L_{κ} which satisfies Shelah’s conjecture.

The consistency strength of PFA(ω_{2}) is exactly that of a cardinal δ which is H(δ^{+})-reflecting [15]. Such cardinals are weakly compact but weaker in consistency strength than the existence of 0^{♯}. By methods mentioned below, Theorem 7.2 provides us with an even sharper bound on the consistency strength — a cardinal which is both reflecting and Mahlo suffices. If the proper class ordinal is 2-Mahlo, then there are a proper class of such cardinals. Further examination of the proof shows that something less suffices; even Theorem 7.3 is not optimally stated. It is remarked in the conclusion of [12] that the forcing extension of Theorem 7.3 can be arranged so that it satisfies “ω_{2} is not a reflecting cardinal in L.” It is necessarily the case, however, that in this generic extension there are cofinally many δ < ω_{2} which are inaccessible in L and for which L_{δ} satisfies “there is a reflecting cardinal.” While it is not clear at all that Shelah’s Conjecture has any large cardinal strength, the current upper bound seems quite satisfactory until a non-trivial lower bound is established — if this is possible at all.

While Theorem 7.3 is beyond the scope of this note, I will now sketch the proofs of Theorems 7.1 and 7.2. A collection ℱ of subtrees of a given A-tree T is predense if whenever S is a subtree of T, there is a U in ℱ which has uncountable intersection with S. For a collection ℱ of subtrees of an A-tree T, consider the following assertion.

ψ(ℱ): There exist S_{ξ} (ξ < ω_{1}) in ℱ and a club E ⊆ ω_{1} such that if ν is in E and t is in T_{ν}, then there is a ν_{t} < ν such that if ζ is in (ν_{t}, ν) ∩ E, then there is a ξ < ζ with t ↾ ζ in S_{ξ}.

If S_{ξ} (ξ < ω_{1}) witnesses ψ(ℱ), then it can be verified that ℱ_{0} = {S_{ξ} : ξ < ω_{1}} is predense. It is also not difficult to show that, in the presence of PFA(ℵ_{1}), A-tree saturation is equivalent to the assertion ψ that ψ(ℱ) holds for every predense family ℱ of subtrees of arbitrary Atrees. Furthermore, assuming PFA(ω_{1}), ψ is equivalent to the following statement holding for arbitrary collections ℱ of subtrees of A-trees.

φ(ℱ): There is a closed unbounded set E ⊆ ω_{1} and a continuous chain ⟨N_{ν} : ν ∈ E⟩ of countable subsets of ℱ ∪ ℱ^{⊥} such that for every ν in E and t in T_{ν} either

(1) there is a ν_{t} < ν such that if ζ ∈ (ν_{t}, ν) ∩ E, then there is

A ∈ ℱ ∩ N_{ζ} such that t ↾ ζ is in A, or

(2) there is a B in ℱ^{⊥} ∩ N_{ν} such that t is in B.

Here ℱ^{⊥} is the collection of all subtrees S which have countable intersection with every element of ℱ. There is an important caveat though. Unlike the situation with NS_{ω_{1}}, the maximality of an antichain of size ℵ_{1} of subtrees need not be upwards absolute, as the next example shows. In particular, ψ is stronger than A-tree saturation.

Example 7.4. Suppose that U is an ω_{1}-tree with the following properties:

(1) U has exactly ℵ_{1} many uncountable branches.

(2) There is an ℵ_{1}-preserving forcing extension in which U gains a new uncountable branch.

(3) U has no Aronszajn subtrees.

Such a tree can be forced by countable approximations — see p 282 of [28] with κ = ℵ_{1}. The point is that the forcing extension V [G] constructed following 8.12 of [28] can be viewed as an iteration V [G_{0}][b^{∗}] where b^{∗} is a branch of the generic ω_{1}-tree and all branches of this tree except b^{∗} are in V [G_{0}]. Following Example 6.2 above, let T be any A-tree and consider the family ℱ of all subtrees S_{b} of T ⊗ U such that b is an uncountable branch through U. Clearly ℱ has size ℵ_{1} and since U has no Aronszajn subtrees, ℱ^{⊥} is empty. However, adding b^{∗} causes ℱ to no longer be maximal since then S_{b^{∗}} is in ℱ^{⊥}.

Theorem 7.2 is derived by showing that if K is a subset of T, then there is a countable sequence ℛ_{n} (n < ω) of families of subtrees of finite powers of T such that if φ(ℛ_{n}) is true for each n, then Observation 4 holds.

The arguments in [12] show that, for a fixed ℱ, ψ(ℱ) can be forced with a proper forcing (this proves Theorem 7.1). With appropriate book-keeping and ground model assumptions one can use this to establish the consistency of PFA(ℵ_{1}) together with the assertion that φ(ℱ) holds for every family of subtrees of an A-tree starting from the existence of a reflecting Mahlo cardinal.

8. Ladder system colorings, A-trees, and minimal uncountable order types

In this section, we will consider a companion result to Theorem 5.5. Suppose for a moment that ℬ is a finite basis for the uncountable linear orderings which is, moreover, as small as possible. Because of the minimality of ℬ, any element of ℬ must embed into all of its uncountable suborders — it must be a minimal uncountable order type. Hence, assuming PFA, ω_{1}, ω_{1}^{∗}, X, C, and C^{∗} are all minimal uncountable order types if X is a set of reals of size ℵ_{1} and C is a Countryman line. By classical results, both ω_{1} and ω_{1}^{∗} are minimal without any axiomatic assumptions: if X ⊆ ω_{1} is uncountable, the collapsing map is an isomorphism between X to ω_{1}. It is reasonable to ask whether there are any other ZFC examples of minimal uncountable order types. This is implicit in Baumgartner’s [4], though it seems to have been present in the folklore before that article.

Regarding real types, Sierpinski proved the following result which implies that there are no minimal real types if one assumes CH.

Theorem 8.1. [23] If X ⊆ ℝ and |X| = |ℝ|, then there is a Y ⊆ X with |Y | = |ℝ| such that if f ⊆ Y^{2} is monotonic, then {y ∈ Y : f(y) ≠ y} has cardinality less than |Y |.

An analogous result for A-lines, however, is a more subtle matter as the following result of Baumgartner shows.

Theorem 8.2. [4] If ♢^{+} is true, then there is an Aronszajn line which is minimal.

This left open the question of whether there could be a ZFC example of a minimal A-line. In [17], I proved that this is not the case.

Theorem 8.3. [17] It is consistent with CH that there are no minimal Aronszajn lines.

This is a consequence of a study of a variation of ladder system uniformization which may be of independent interest.

Definition 8.4. Suppose T is an A-tree and f_{δ} (δ ∈ lim(ω_{1})) is a coloring of a ladder system^{4} C_{δ} (δ ∈ lim(ω_{1})). A T -uniformization of ⟨f_{δ} : δ < ω_{1}⟩ is a function g defined on a downward closed subtree U of T such that if u is an element of U of limit height δ, then

f_{δ}(ξ) = g(u ↾ ξ)

for all but finitely many ξ in C_{δ}.

4For our purposes, a ladder system is a C-sequence defined only on the limit ordinals.

Theorem 8.3 now follows immediately from the next two theorems.

Theorem 8.5. [17] There is a proper forcing extension which satisfies CH in which every ladder system coloring can be T -uniformized for every A-tree T.

Theorem 8.6. [17] Suppose that T is an A-tree and that

(1) Every ladder system coloring can be T -uniformized.

(2) There is lexicographical ordering on a subset of T which is a minimal Aronszajn line.

Then 2^{ℵ_{0}} = 2^{ℵ_{1}}.

These theorems also provide an example related to Woodin’s question on maximization of Π_{2} sentences for H(ω_{2}) in the presence of CH (Question 21 of [35]) and Steel’s question on Σ_{2}^{2}-absoluteness.

Example 8.7. Let ℒ be the language of set theory and let ℒ^{C} denote the language of set theory expanded to add a predicate for a C-sequence. Let ZFC^{C} be the extension of ZFC by adding an axiom asserting that there is a unique C-sequence on ω_{1} which is equal to the predicate. Since ZFC implies the existence of C-sequences on ω_{1}, this yields a conservative extension of ZFC. This is a rather mild logical maneuver as the family of C-sequences on ω_{1} is Δ_{0}-definable with parameter ω_{1}.

If we let ψ_{1} be the assertion that every ladder system coloring can be uniformized relative to every A-tree, then ψ_{1} is a Π_{2}-sentence in ℒ. If we let ψ_{2} be the assertion that the coherent sequence {e_{β} : β < ω_{1}}, defined in Example 3.4 using the predicate, is a minimal Aronszajn type, then ψ_{2} is a Π_{2}-sentence in ℒ^{C}. By Theorem 8.5, the conjunction of ψ_{1} and CH can be forced with a proper forcing. By Theorem 8.6, the conjunction of ψ_{1} and ψ_{2} implies CH is false. Finally, ψ_{2} is a consequence of MA_{ℵ_{1}} (see [26]) and, by Theorem 6.4, is preserved by σ-closed forcing. Therefore, the conjunction of ψ_{2} and ♢^{+} can be forced with a proper forcing. On the other hand, by Theorems 8.5 and 8.6, we can always go into a proper forcing extension in which ψ_{2} is false.

P. Larson noted that the proof of [1, 2.3] can be adapted to show that 2^{ℵ_{0}} < 2^{ℵ_{1}} implies the existence of a non-minimal Aronszajn type which is a lexicographical ordering on a coherent sequence. While it is not completely clear whether the coherent sequence can be constructed as in Example 3.4, there seems to be little hope of improving Example 8.7 by removing the predicate for C.

9. Questions

The work exposited above both leaves open and suggests a number of questions. I have collected a few which I hope will yield interesting mathematics.

I will begin with a question related to the consistency strength of Shelah’s Conjecture and motivated by the work in [12]. If K is a subset of an A-tree T, let

ℱ_{K} = {S ⊆ K : S is a subtree of T }.

Assuming Shelah’s Conjecture, ℱ_{K}^{⊥} is Σ_{1}-definable: U is in ℱ^{⊥} iff there exists a subtree S of T such that S ⊆ U and S ∩ K = ∅. Hence Shelah’s Conjecture implies that φ(ℱ_{K}) is a Σ_{1}-formula in the language of H(ℵ_{1}^{+}). It follows from this and the fact that φ(ℱ_{K}) can always be forced by a proper forcing that — in the presence of BPFA — Shelah’s Conjecture is equivalent to the assertion that φ(ℱ_{K}) holds for all Atrees T and all K ⊆ T.

Question 9.1. Assume BPFA. If T is an A-tree and K ⊆ T, must ℱ_{K} ∪ ℱ_{K}^{⊥} contain a predense family of size ℵ_{1}?

This lends some plausibility to Shelah’s Conjecture having large cardinal strength.

At present at least, Example 6.2 provides us with essentially the only construction of a non-saturated A-tree. This motivates a variety of questions.

Question 9.2. Is the statement that all A-trees are saturated preserved by forcings which do not add subsets of ω_{1}?

Notice that, if this question has a negative answer, then the forcing extension witnessing this would contain a non-saturated tree but no Kurepa trees. The ground model — and consequently the extension — must contain a tree without a subtree base of size ℵ_{1}.

It would be interesting to have an internal construction of nonsaturation inside members of a reasonably definable class of A-trees.

Question 9.3. Is there a Σ_{1}-definable class 𝒮 of A-trees such that if S is in 𝒮, then L[S] correctly computes ω_{1} and satisfies that S is a non-saturated?

In models such as the Levy collapse A-trees are saturated for the simple reason that there are essentially very few subtrees of a given tree. It is reasonable to ask whether the saturation of an A-tree which has an abundance of subtrees requires more substantial large cardinals.

Question 9.4. Suppose that T is a saturated coherent A-tree and 𝒰 (T) is an ultrafilter. Must ω_{2} be Mahlo in L?

The methods of [20] definitely entail that |ℝ| = ℵ_{2} holds in the resulting models of Shelah’s Conjecture.

Question 9.5. Does Shelah’s Conjecture imply that |ℝ| ≤ ℵ_{2}?

This question would have a positive answer if ℧ follows from |ℝ| > ℵ_{2}. At present, this seems plausible.

It is also reasonable to ask if there is a consistent higher dimensional analogue of Item 3 of Theorem 5.2.

Question 9.6. Does PFA imply that whenever T is an A-tree and

T^{[2]} = {{s, t} : s, t ∈ T and s < t}

is partitioned into infinitely many sets K_{i} (i < ω), then there is an i < ω and a subtree S of T such that S^{[2]} is disjoint from K_{i}?

It seems likely that if this question has a positive answer, then it is possible to replace ω with some finite n and also obtain a positive answer. It is worth noting that there is a canonical counterexample if n = 2: If T is a subtree of 2^{<ω_{1}}, put {s, t}_{<} in K_{i} iff t(ht(s)) = i. Džamonja and J. Larson have modified this partition to show that there is also a counterexample if n = 3.

A natural question to ask after the results of [17] is the following. This is at least implicit in [3].

Question 9.7. Is it consistent that if L is a linear order which is not σ-scattered, then there is a suborder X ⊆ L which is not σ-scattered such that L does not embed in X?

Aronszajn and real types are examples of linear orders which are not σ-scattered; another type of example is constructed in [3].

The construction mentioned at the end of Section 8 leaves the following question open.

Question 9.8. If C is a Countryman line, is there a proper forcing which makes C minimal and which does not add reals?

Notice that it is possible to go into a forcing extension in which C is minimal and in which even ♢^{+} holds.

Finally, I will mention the following question offered by Todorcevic.

Question 9.9. (PFA) What is the co-initiality of (𝒞 , ≤)?

References

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

[2] James E. Baumgartner. All ℵ_{1}-dense sets of reals can be isomorphic. Fund. Math., 79(2):101–106, 1973.

[3] James E. Baumgartner. A new class of order types. Ann. Math. Logic, 9(3):187– 222, 1976.

[4] James E. Baumgartner. Order types of real numbers and other uncountable orderings. In Ordered sets (Banff, Alta., 1981), volume 83 of NATO Adv. Study Inst. Ser. C: Math. Phys. Sci., pages 239–277. Reidel, Dordrecht, 1982.

[5] James E. Baumgartner. Bases for Aronszajn trees. Tsukuba J. Math., 9(1):31– 40, 1985.

[6] M. Bekkali. Topics in set theory. Springer-Verlag, Berlin, 1991. Lebesgue measurability, large cardinals, forcing axioms, ρ-functions, Notes on lectures by Stevo Todorčević.

[7] R. Countryman. Spaces having a σ-monotone base. preprint 1970.

[8] Keith J. Devlin. Constructibility. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1984.

[9] Martin Goldstern and Saharon Shelah. The Bounded Proper Forcing Axiom. J. Symbolic Logic, 60(1):58–73, 1995.

[10] Masazumi Hanazawa. On Aronszajn trees with a non-Souslin base. Tsukuba J. Math., 6(2):177–185, 1982.

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

[12] Bernhard König, Paul Larson, Justin Tatch Moore, and Boban Veličković. Bounding the consistency strength of a five element linear basis. in preparation, November 2005.

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

[14] Richard Laver. Better-quasi-orderings and a class of trees. In Studies in foundations and combinatorics, volume 1 of Adv. in Math. Suppl. Stud., pages 31–48. Academic Press, New York, 1978.

[15] Tadatoshi Miyamoto. A note on weak segments of PFA. In Proceedings of the Sixth Asian Logic Conference (Beijing, 1996), pages 175–197. World Sci. Publishing, 1998.

[16] Justin Tatch Moore. Persistent counterexample to basis conjectures. Unpublished note, September 2004.

[17] Justin Tatch Moore. ω_{1} and ω_{1}^{∗} may be the only minimal uncountable order types. Preprint, October 2005.

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

[19] Justin Tatch Moore. A solution to the L space problem. J. Amer. Math. Soc., to appear July 2006.

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

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

[22] Saharon Shelah. Proper and improper forcing. Springer-Verlag, Berlin, second edition, 1998.

[23] W. Sierpiński. Sur un problème concernant les types de dimensions. Fundamenta Mathematicae, 19:65–71, 1932.

[24] Jack Silver. The independence of Kurepa’s conjecture and two-cardinal conjectures in model theory. In Axiomatic Set Theory (Proc. Sympos. Pure Math., Vol. XIII, Part I, Univ. California, Los Angeles, Calif., 1967), pages 383–390. Amer. Math. Soc., Providence, R.I., 1971.

[25] Robert Solovay and S. Tennenbaum. Iterated Cohen extensions and Souslin’s problem. Ann. of Math., 94:201–245, 1971.

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

[27] Stevo Todorcevic. A note on the proper forcing axiom. In Axiomatic set theory (Boulder, Colo., 1983), volume 31 of Contemp. Math., pages 209–218. Amer. Math. Soc., Providence, RI, 1984.

[28] Stevo Todorcevic. Trees and linearly ordered sets. In Handbook of set-theoretic topology, pages 235–293. North-Holland, Amsterdam, 1984.

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

[30] Stevo Todorcevic. Partition Problems In Topology. Amer. Math. Soc., 1989.

[31] Stevo Todorcevic. A classification of transitive relations on ω_{1}. Proc. London Math. Soc. (3), 73(3):501–533, 1996.

[32] Stevo Todorcevic. Localized reflection and fragments of PFA. In Logic and scientific methods, volume 259 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 145–155. AMS, 1997.

[33] Stevo Todorcevic. Countable chain condition in partition calculus. Discrete Math., 188(1-3):205–223, 1998.

[34] Stevo Todorcevic. Coherent sequences. In Handbook of Set Theory. North-Holland, (forthcoming).

[35] W. Hugh Woodin. The Axiom of Determinacy, Forcing Axioms, and the Nonstationary Ideal. Logic and its Applications. de Gruyter, 1999.

Department of Mathematics, Boise State University, Boise, Idaho 83725–1555

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