BOUNDING THE CONSISTENCY STRENGTH OF A FIVE ELEMENT LINEAR BASIS

BERNHARD KÖNIG, PAUL LARSON, JUSTIN TATCH MOORE, AND BOBAN VELIČKOVIĆ

Abstract. In [13] it was demonstrated that the Proper Forcing Axiom implies that there is a five element basis for the class of uncountable linear orders. The assumptions needed in the proof have consistency strength of at least infinitely many Woodin cardinals. In this paper we reduce the upper bound on the consistency strength of such a basis to something less than a Mahlo cardinal, a hypothesis which can hold in the constructible universe L.

A crucial notion in the proof is the saturation of an Aronszajn tree, a statement which may be of broader interest. We show that if all Aronszajn trees are saturated and PFA(ω_{1}) holds, then there is a five element basis for the uncountable linear orders. We show that PFA(ω_{2}) implies that all Aronszajn trees are saturated and that it is consistent to have PFA(ω_{1}) plus every Aronszajn tree is saturated relative to the consistency of a reflecting Mahlo cardinal. Finally we show that a hypothesis weaker than the existence of a Mahlo cardinal is sufficient to force the existence of a five element basis for the uncountable linear orders.

1. Introduction

In [13] it was shown that the Proper Forcing Axiom (PFA) implies that the class of uncountable linear orders has a five element basis, i.e., that there is a list of five uncountable linear orders such that every

2000 Mathematics Subject Classification. 03E05, 06A05, 06A07. Key words and phrases. Aronszajn tree, basis, consistency strength, Country-

man, Proper Forcing Axiom, reflecting cardinal, saturation, Shelah’s conjecture, uncountable linear order,

The first author acknowledges a fellowship granted by the French ministry of research. The research of the second author was partially supported by the Centre de Rercerca Matemàtica of the Universitat Autònoma de Barcelona, and by NSF Grant DMS-0401603. The second and fourth authors would like to thank CIRM in Luminy for hosting them during a petit group de travaille, and to thank the others participants, Ralf Schindler and Ernest Schimmerling, for discussions on this topic. The second author would also like to thank the third and fourth authors for bringing him to Boise and Paris respectively for further discussions. The third author was supported by NSF grant DMS–0401893.

uncountable linear order contains an isomorphic copy of one of them. This basis consists of X, ω_{1}, ω_{1}^{∗}, C, and C^{∗} where X is any suborder of the reals of cardinality ω_{1} and C is any Countryman line. In fact any five element basis for the uncountable linear orders must have this form.

Recall that a Countryman line is a linear order whose square is the union of countably many non-decreasing relations. These linear orders are necessarily Aronszajn. Their existence was proved by Shelah who conjectured that every Aronszajn line consistently contains a Countryman suborder [14]. In [1, p. 79] it is stated that, assuming PFA, every Aronszajn line contains a Countryman suborder if and only if the Coloring Axiom for Trees (CAT) holds:

There is an Aronszajn tree T such that for every K ⊆ T there is an uncountable antichain X ⊆ T such that ∧(X) is either contained in or disjoint from K.

Here ∧(X) denotes the set of all pairwise meets of elements of X. Over time, this conjecture developed in the folklore and at some point it was known to be equivalent — modulo PFA — to the assertion that the above list forms a basis for the class of uncountable linear orders.^{1} Moreover this reduction does not require any of the large cardinal strength of PFA. The reader is referred to the final section of [15] for proofs of the above assertions.

In [13] it is shown that PFA implies CAT. In fact the conjunction of the Bounded Proper Forcing Axiom (PFA(ω_{1})) [8] and the Mapping Reflection Principle (MRP) [12] suffices. Since the consistency of MRP requires considerable large cardinal assumptions^{2} and since its use is isolated to Lemma 5.29 of [13], it is natural to ask what large cardinals, if any, are necessary for CAT. Here we reduce the consistency strength needed to something less than a Mahlo cardinal,^{3} a hypothesis which can hold in the constructible universe L.

The main goal of this paper is to prove this Key Lemma from a greatly reduced hypothesis. A central notion in our analysis is that of the saturation of an Aronszajn tree T — whenever 𝒜 is a collection of uncountable downward closed subsets of T which have pairwise countable intersection, then 𝒜 has cardinality at most ω_{1}. When possible, this notion will be considered separately as it seems that this could be relevant in other contexts.

1The speculation of the consistent existence of a finite basis for the uncountable linear orders seems to have first been made in print in [3], although it still seems to have been unknown at that point that this was equivalent to Shelah’s conjecture.

2The current upper bound is a supercompact cardinal [12].

3A regular cardinal κ is Mahlo if the set of regular cardinals less than κ is stationary in κ.

Central to the proof in [13] is the notion of rejection. This will be defined after recalling some preliminary definitions from [13]. For the moment, fix an Aronszajn tree T ⊆ 2^{<ω_{1}} which is coherent, special and closed under finite modifications,^{4} and let K be a subset of T.

Definition 1.1. If P is a countable elementary submodel of H(ω_{2}) containing T, let ℐ_{P} (T) be the collection of all I ⊆ ω_{1} such that for some uncountable Z ⊆ T in P and some t in the downwards closure of Z having height P ∩ ω_{1}, I is disjoint from

Δ(Z, t) = {Δ(s, t) : s ∈ Z}.

It is always the case that ℐ_{P} (T) is closed under finite unions and subsets. The former property uses the properties of T and is nontrivial; the argument is similar to the proof of [15, 4.1]. Similarly, ℐ_{P} (T) remains the same if one takes t to be a fixed member of T_{P ∩ω_{1}} instead of letting t vary.

Definition 1.2. If X is a finite subset of T, K(X) is the set of all γ which are less than the the heights of all elements of X and satisfy s ↾ γ ∈ K for all s in X.

Definition 1.3. If X is a finite subset of T and P is a countable elementary submodel of H(ω_{2}), then P rejects X if K(X \ P) is in ℐ_{P} (T).

It is shown in [13] that the following lemma (Lemma 5.29 of [13]), taken in conjunction with PFA(ω_{1}), is sufficient to prove the existence of an uncountable antichain X ⊆ T such that ∧(X) is contained in or disjoint from K.

Key Lemma 1.4. [13] (MRP) If M is a countable elementary submodel of H(2^{2^{ω_{1}}}^{+}) which contains T and K and X is a finite subset of T, then there is a closed unbounded set E of countable elementary submodels of H(ω_{2}) such that E is in M and either every element of E ∩ M rejects X or no element of E ∩ M rejects X.

We will begin by defining a combinatorial statement φ in Section 2 and showing that this statement implies the Key Lemma. The statement φ is a strengthening of Aronszajn tree saturation — the assertion that every Aronszajn tree is saturated. Moreover, φ is shown to be equivalent to Aronszajn tree saturation in the presence of PFA(ω_{1}). In Section 3 we will demonstrate that PFA(ω_{2}) implies φ. This reduces the upper bound on the consistency strength of Shelah’s conjecture to something less than the existence of 0^{♯} but greater than a weakly compact cardinal. Section 4 further refines the argument to show that an instance of φ can be forced by a proper forcing without a need for large cardinal assumptions. This is then implemented in Section 5 to further optimize the upper bound on the consistency strength of a five element basis for the uncountable linear orders to something less than the existence of a Mahlo cardinal.

4The tree T (ϱ_{3}) of [18] is such an example.

The notation and terminology used in this paper is fairly standard. All ordinals are von Neumann ordinals; they are the set of their predecessors. The cardinal ℶ_{α} is defined recursively so that ℶ_{0} = ω, ℶ_{α+1} = 2^{ℶ_{α}}, and ℶ_{δ} = sup_{α<δ} ℶ_{α} for limit δ. The reader is referred to [9] as a general reference for set theory. In this paper Aronszajn tree or A-tree will mean an uncountable tree in which all levels and chains are countable. A subtree of an A-tree T is an uncountable downward closed subset of T. The reader is referred to [10] or [17] for further reading on bounded fragments of PFA.

2. Aronszajn tree saturation

Recall the notion of the saturation of 𝒫(ω_{1})/NS:

Any collection of stationary sets which have pairwise non-stationary intersection has cardinality at most ω_{1}.

Now consider the following statement ψ_{NS}(𝒜) for a collection 𝒜 of subsets of ω_{1}:

There is a club E ⊆ ω_{1} and a sequence ⟨A_{ξ} : ξ < ω_{1}⟩ of elements of 𝒜 such that for all δ in E, there is a ξ < δ with δ in A_{ξ}.

The assertion ψ_{NS} that ψ_{NS}(𝒜) holds for every predense set 𝒜 ⊆ 𝒫(ω_{1})/NS is in fact equivalent to the saturation of 𝒫(ω_{1})/NS. This was used to prove that Martin’s Maximum implies that 𝒫(ω_{1})/NS is saturated [7]. The significance of ψ_{NS}(𝒜) from our point of view is that it implies that 𝒜 is predense and is Σ_{1} in complexity and therefore upwards absolute.

In this section we will be interested in analogous assertions about subtrees of an A-tree.^{5} Definition 2.1. An A-tree T is saturated if whenever 𝒜 is a collection of subtrees T which have pairwise countable intersection, 𝒜 has cardinality at most ω_{1}.

5Actually, all statements about the saturation of an A-tree make sense in the broader context of all ω_{1}-trees. We will not need this generality and in fact the saturation of all A-trees implies the more general case by Todorcevic’s construction presented in Section 2 of [4].

This statement follows from the stronger assertion shown by Baumgartner to hold after Levy collapsing an inaccessible cardinal to ω_{2} [4].

For every A-tree T, there is a collection ℬ of subtrees of T such that ℬ has cardinality ω_{1} and every subtree of T contains an element of ℬ.

Unlike in the case of 𝒫(ω_{1})/NS, the maximality of an ω_{1}-sized antichain of subtrees can be shown not to be upwards absolute.^{6} This leaves open the question, however, of how to obtain the consistency of A-tree saturation in the presence of a forcing axiom. It is not difficult to show that both Chang’s Conjecture and the saturation of 𝒫(ω_{1})/NS each imply that all A-trees are saturated. Therefore Martin’s Maximum implies all A-trees are saturated. We will pursue a different proof, however, which is weaker in terms of consistency strength and somewhat different in character.

If ℱ is a collection of subtrees of T, then ℱ^{⊥} is the collection of all subtrees B of T such that for every A in ℱ, A ∩ B is countable. If ℱ^{⊥} is empty, then ℱ is said to be predense. For ℱ a collection of subtrees of an A-tree T, we define the following assertions:

ψ(ℱ): 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_{ν} there is a ν_{t} < ν such that if ξ ∈ (ν_{t}, ν) ∩ E, then there is A ∈ ℱ ∩ N_{ξ} such that t ↾ ξ is in A.

φ(ℱ): 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. The following proposition — together with Lemma 4.3 below — captures the important properties of ψ(ℱ).

Lemma 2.2. Let ℱ be a fixed family of trees. ψ(ℱ) is a Σ_{1}-formula with parameters ℱ, T, and ω_{1} which implies that ℱ is predense.

Proof. Let ψ_{0} be the conjunction of the following formulae:

∀α ∈ E(α ∈ ω_{1})

6This can be derived from the arguments in [16, §8] and the construction in [4, §2]. An argument is explicit in [11].

∀α ∈ ω_{1}∃β ∈ E(α ∈ β)
∀α ∈ ω_{1}(¬(α ∈ E) → ∃β ∈ α∀γ ∈ α((γ ∈ E) → (γ ∈ β))).

Clearly ψ_{0} asserts that E is a closed unbounded subset of ω_{1}. Similarly, the assertion N⃗ = ⟨N_{ν} : ν ∈ E⟩ is a continuous chain of countable subsets of ℱ is a Σ_{0}-formula ψ_{1} with parameters E and ℱ. Finally let ψ_{2} be the Σ_{0}-formula asserting for every ν in E and t in T_{ν} there is a ν_{t} < ν such that if ξ ∈ (ν_{t}, ν) ∩ E, then there is A ∈ ℱ ∩ N_{ξ} such that t ↾ ξ is in A. Then ψ(ℱ) is the Σ_{1}-formula

∃E∃N⃗ψ_{0} ∧ ψ_{1} ∧ ψ_{2}.

In order to see that ψ(ℱ) implies that ℱ is predense, suppose that S is a subtree of T and that ⟨N_{ν} : ν ∈ E⟩ witnesses ψ(ℱ). Let M be a countable elementary submodel of H(2^{ω_{1}}^{+}) which contains T, S and ⟨N_{ν} : ν ∈ E⟩ as elements. Set δ = M ∩ ω_{1} and select a t in S of height δ. By choice of ⟨N_{ν} : ν ∈ E⟩, there is δ_{t} < δ such that if ξ ∈ (δ_{t}, δ) ∩ E, then there is an A in ℱ ∩ N_{ξ} with t ↾ ξ in A. Let \overline{N} be a countable elementary submodel of H(ω_{2}) such that \overline{N} is in M and T, S, ⟨N_{ν} : ν ∈ E⟩, and δ_{t} are in \overline{N}. By the continuity assumption on ⟨N_{ν} : ν ∈ E⟩ and elementarity of \overline{N}, ν = \overline{N} ∩ ω_{1} is in E and

N_{ν} ∩ ℱ = ⋃_{ξ∈ν∩E} N_{ξ} ∩ ℱ = \overline{N} ∩ ℱ .

Hence there is an A in ℱ ∩ \overline{N} such that t ↾ ν is in A. Since t ↾ ν is in S ∩ A but not in \overline{N}, the elementarity of \overline{N} implies that S ∩ A must be uncountable, finishing the proof. □

While φ(ℱ) and ψ(ℱ) are equivalent if ℱ is predense, φ(ℱ) is in general not a Σ_{1}-formula in ℱ and T. Let φ be the assertion that whenever T is an A-tree and ℱ is a family of subtrees T, φ(ℱ) holds and let ψ be the analogous assertion but with quantification only over ℱ which are predense. As noted, φ implies ψ. Also if 𝒜 is a predense family of subtrees of T which have pairwise countable intersects and ⟨N_{ν} : ν ∈ E⟩ witnesses ψ(𝒜), then ⋃_{ν∈E} N_{ν} = 𝒜 and in particular 𝒜 has size at most ω_{1}. Hence both ϕ and ψ imply A-tree saturation.

We will now show the relevance of φ to our main goal. Before proceeding, it will be useful to reformulate the notion of rejection presented in the introduction.

Definition 2.3. Let T^{[n]} denote the collection of all elements τ of T^{n} such that every coordinate of τ has the same height and, when considered as a sequence of elements of T, the coordinates of τ are nondecreasing in the lexicographical order on T. T^{[n]} will be considered as a tree with the coordinate-wise partial order induced by T.

Remark 2.4. Morally, elements of T^{[n]} are n-element subsets of T. In order to ensure that T^{[n]} is closed under taking restrictions, it is necessary to allow for n-element sets with repetition and the above definition is a formal means to accommodate this. We will abuse notation and identify elements of T^{[n]} which have distinct coordinates with the set of their coordinates. In our arguments, only the range of these sequences will be relevant.

Definition 2.5. Let n < ω be fixed. For any uncountable set Z ⊆ T, let R_{Z} be downward closure of the set of elements Y of T^{[n]} such that Δ(Z, t) ∩ K(Y) = ∅ for some element t of the downward closure of Z with height(t) = height(Y). Let ℛ_{n} denote the collection of all R_{Z} as Z ranges over the uncountable subsets of T.

Lemma 2.6. Suppose that P is a countable elementary submodel of H(ω_{2}) which has T as a member. For any Y ∈ T^{[n]} with height(Y) ≥ P ∩ ω_{1}, P rejects Y if and only if Y ↾ (P ∩ ω_{1}) is in R_{Z} for some Z ∈ P.

Proof. Suppose first that P rejects Y. Then there exist Z ⊆ T in P and t ∈ (Z ∩ T_{P ∩ω_{1}}) \ P such that Δ(Z, t) ∩ K(Y) = ∅. Since K(Y) ∩ (P ∩ ω_{1}) = K(Y ↾ (P ∩ ω_{1})), Y ↾ (P ∩ ω_{1}) is in R_{Z}.

In the other direction, if Y ↾ (P ∩ ω_{1}) is in R_{Z} for some Z ∈ P, then there exist Y′ ≥ Y ↾ (P ∩ ω_{1}) in R_{Z} and t ∈ Z ∩ T such that height(t) ≥ height(Y′) and Δ(Z, t) ∩ K(Y′) = ∅. Then K(Y′) ∩ (P ∩ ω_{1}) = K(Y ↾ (P ∩ ω_{1})), and Δ(Z, t) ∩ (P ∩ ω_{1}) = Δ(Z, t ↾ (P ∩ ω_{1})), so Δ(Z, t ↾ (P ∩ ω_{1})) ∩ K(Y) = ∅, which means that P rejects Y. □

Theorem 2.7. Suppose that T is a coherent A-tree which is closed under finite changes. If φ(ℛ_{n}) holds for every n < ω, then the Key Lemma holds for T.

Proof. Assume the hypothesis of the lemma and let M and X be given as in the statement of the Key Lemma. Without loss of generality, we may assume that X is in T_{M∩ω_{1}}^{[n]} for some n < ω. Note that ℛ_{n} is Σ_{1}-definable using parameters for T and K and therefore there is an N⃗ = ⟨N_{ν} : ν ∈ E⟩ in M which witnesses φ(ℛ_{n}). Either there is a ν_{X} < M ∩ ω_{1} such that for each ξ ∈ E ∩ (ν_{X}, M ∩ ω_{1}) there is an R ∈ N_{ξ} ∩ ℱ with X ↾ ξ ∈ R or there is a B in ℛ_{n} ^{⊥} ∩ N_{M∩ω_{1}} with X ∈ B.

In the first case, let E be the set of countable P elementary submodels of H(ω_{2}) which satisfy N⃗ ∈ P and P ∩ ω_{1} > ν_{X}. Then every member P of E contains N_{P ∩ω_{1}} and thus contains an R ∈ ℛ_{n} with X ↾ (P ∩ ω_{1}) in R. By Claim 2.6, P rejects X.

In the second case, let E be the set of all P countable elementary submodels of H(ω_{2}) with K, T, and B in P. If P in E ∩ M were to reject X, there would be an R in ℛ_{n} ∩ P with X ↾ (P ∩ ω_{1}) ∈ R. It would follow that X ↾ (P ∩ ω_{1}) is in B ∩ R, which by elementarity of P would imply that B ∩ R is uncountable which is contrary to B being in ℛ_{n} ^{⊥}. Hence no element of E ∩ M rejects X. □

3. PFA(ω_{2}) implies φ

In this section we will show that PFA(ω_{2}) implies φ. If λ is a cardinal, then PFA(λ) is the fragment of PFA in which only antichains of size at most λ are considered [8]. We will use the following reformulation which is due to Miyamoto [10]:

PFA(λ): For every A in H(λ^{+}) and Σ_{0}-formula ϕ, if some proper partial order forces ∃Xϕ(X, A), then there is a stationary set of N in [H(λ^{+})]^{ω_{1}} such that A is in N and H(ω_{2}) satisfies ∃Xϕ(X, π_{N}(A)) where π_{N} is the transitive collapse of N.

In [10] it is also shown that PFA(ω_{2}) is equiconsistent with the existence of a cardinal κ which is H(κ^{+})-reflecting. Such cardinals are larger than weakly compact cardinals but still relativize to L and hence do not imply the existence of 0^{♯}. In this section we show that PFA(ω_{2}) implies that every A-tree is saturated. First we recall some definitions from [12].

Definition 3.1. Let θ be a regular cardinal, let X be uncountable, and let M be a countable subset of H(θ) such that [X]^{ω} is in M. A subset Σ of [X]^{ω} is M-stationary iff for all E in M such that E ⊆ [X]^{ω} is club, Σ ∩ E ∩ M is non-empty.

The Ellentuck topology on [X]^{ω} is obtained by declaring a set open iff it is the union of sets of the form

[x, N] = {Y ∈ [X]^{ω}: x ⊆ Y ⊆ N}

where N ∈ [X]^{ω} and x ⊆ N is finite. When we say ‘open’ in this paper we refer to this topology.

Definition 3.2. A set mapping Σ is open stationary iff there is an uncountable set X = X_{Σ} and a regular cardinal θ = θ_{Σ} such that [X]^{ω} ∈ H(θ), dom(Σ) is a club in [H(θ)]^{ω} and Σ(M) ⊆ [X]^{ω} is open and M-stationary, for every M in the domain of Σ.

Definition 3.3. Suppose Σ is an open stationary set mapping. We say that ⟨N_{ξ} : ξ < ω_{1}⟩ is a reflecting sequence for Σ if it a continuous ∈-chain contained in the domain of Σ such that for all limit ν < ω_{1}, there is a ν_{0} < ν such that if ν_{0} < ξ < ν, then N_{ξ} ∩ X is in Σ(N_{ν}).

The Mapping Reflection Principle (MRP) is the assertion that every open stationary set mapping which is defined on a club admits a reflecting sequence. In [12] it was shown that MRP follows from PFA by demonstrating the following theorem which will be useful to us here.

Theorem 3.4. [12] If Σ is an open stationary set mapping defined on a club, then there is a proper forcing which adds a reflecting sequence for Σ.

Lemma 3.5. Suppose that T is a saturated A-tree. Then for every family ℱ of subtrees of T there is a subfamily ℱ′ of ℱ of cardinality at most ω_{1} such ℱ^{⊥} = (ℱ′)^{⊥}.

Proof. Supposing that the lemma is false, for each α < ω_{2}, recursively choose subtrees F_{α}, R_{α} of T such that each F_{α} ∈ ℱ, each R_{α} ∩ F_{α} is uncountable, and R_{α} ∩ F_{β} is countable for each β < α. Then the trees F_{α} ∩ R_{α} form an antichain of cardinality ω_{2}. □

Lemma 3.6. Let κ be a cardinal greater than or equal to (2^{ω_{1}})^{+}. Suppose that T is an A-tree, ℱ is a collection of subtrees of T and M is a countable subset of H(κ) which has T and ℱ as members and satisfies all axioms of ZFC except the power set axiom. If t is an element of T of height M ∩ ω_{1} and

{P ∈ [H(ω_{2})]^{ω} : ∃A ∈ ℱ ∩ P (t ↾ (P ∩ ω_{1}) ∈ A)}

is not M-stationary, then there is an S in M ∩ ℱ^{⊥} which contains t.

Proof. Let δ = M ∩ ω_{1}. Let E ∈ M be a club of countable elementary submodels of H(ω_{2}) such that E ∩ M is disjoint from

{P ∈ [H(ω_{2})]^{ω} : ∃A ∈ ℱ ∩ P (t ↾ (P ∩ ω_{1}) ∈ A)}.

Let S be the set of all s ∈ T such that there exist no P in E with P ∩ ω_{1} < height(s) and A in ℱ ∩ P such that s ↾ (P ∩ ω_{1}) is in A. We claim that t ∈ S. Otherwise, there would exist a P in E with P ∩ ω_{1} < δ and an A in ℱ ∩ P such that t ↾ (P ∩ ω_{1}) is in A. Letting γ = P ∩ ω_{1}, this is a statement about t ↾ γ, which is an element of M, so by the elementarity of M there would exist a P in E ∩ M with P ∩ ω_{1} = γ and an A in ℱ ∩ P such that t ↾ γ is in A, contradicting our choice of E. Therefore, t is in S.

Clearly S is downwards closed and it is uncountable since it is an element of M but not a subset of M. We are finished once we show that S ∩ A is countable for every element A of ℱ. Suppose not. Since S is in M, by elementarity there must be such an A in M ∩ ℱ. Let P be an element of E which contains both A and S. Since A ∩ S is uncountable and downwards closed, there must be an s in A ∩ S of height (P ∩ ω_{1}) + 1. But this contradicts the definition of S. □

Theorem 3.7. PFA(ω_{2}) implies φ.

Proof. In [12], it is shown that PFA(ω_{1}) implies that 2^{ω_{1}} = ω_{2} and hence PFA(ω_{2}) is equivalent to PFA(2^{ω_{1}}). Let

T = {τ(α, i) : α < ω_{1} and i < ω}

be such that τ(α, i) is of of height α for every α and i. Define Σ_{ℱ}^{i} as follows. The domain of Σ_{ℱ}^{i} is the set of all countable subsets M of H(2^{ω_{1}}^{+}) such that M ∩ H(ω_{2}) is an elementary submodel of H(ω_{2}), ℱ and ℱ^{⊥} are in M, and M satisfies that ℱ ∪ ℱ^{⊥} is predense. If M is in the domain of Σ_{ℱ}^{i} and there is no S in M ∩ ℱ^{⊥} with τ(M ∩ ω_{1}, i) in S, then let Σ_{ℱ}^{i} (M) be the collection of all P ∈ [H(ω_{2})]^{ω} such that either P ∩ ω_{1} is not an ordinal or else there is an A in P ∩ ℱ such that τ(M ∩ ω_{1}, i) ↾ (P ∩ ω_{1}) is in A. If there is an S in M ∩ ℱ^{⊥} with τ(M ∩ω_{1}, i) in S, put Σ_{ℱ}^{i} (M) to be all of [H(ω_{2})]^{ω}. Lemma 3.6 implies that Σ_{ℱ}^{i} is open and M-stationary.

We will now argue that PFA(2^{ω_{1}}) implies that each Σ_{ℱ}^{i} admits a reflecting sequence. By the proof of Theorem 3.1 of [12], there is a proper forcing which introduces a reflecting sequence for each Σ_{ℱ}^{i} . Following the proof of Lemma 2.2, let ϕ_{i}(N⃗, ℱ , ℱ^{⊥}, τ) be a Σ_{1}-formula asserting that N⃗ is a reflecting sequence for Σ_{ℱ}^{i} . While Σ_{ℱ}^{i} is not an element of H(2^{ω_{1}}^{+}), it is a definable class within this structure and hence ϕ_{i}(N⃗, ℱ , ℱ^{⊥}, τ) satisfies the hypothesis of PFA(2^{ω_{1}}). Applying Miyamoto’s reformulation of PFA(2^{ω_{1}}), there is an elementary submodel M of H(2^{ω_{1}}^{+}) of size ω_{1} which contains ω_{1} as a subset, ℱ, ℱ^{⊥}, τ as elements and is such that H(ω_{2}) satisfies there is a N⃗ such that ϕ_{i}(N⃗, π(ℱ), π(ℱ^{⊥}), π(τ)) where π is the transitive collapse of M. Notice that since ω_{1} is a subset of M, the collapsing map fixes elements of H(ω_{2}) and in particular τ and elements of ℱ and ℱ^{⊥}. It follows that the postulated N⃗ really is a reflecting sequence for Σ_{ℱ}^{i} .

Now fix, for each i, a reflecting sequence ⟨M_{ν}^{i} : ν < ω_{1}⟩ for Σ_{ℱ}^{i} . Let E be the collection of all ν such that M_{ν}^{i} ∩ ω_{1} = ν, for each i. Letting

N_{ν} = (ℱ ∪ ℱ^{⊥}) ∩ ⋃_{i<ω} M_{ν}^{i},

it is easily checked that ⟨N_{ν} : ν ∈ E⟩ is a witness to φ(ℱ). □

Lemma 3.8. For a given family ℱ of subtrees of an Aronszajn tree T, there is a proper forcing extension which satisfies φ(ℱ).

Proof. Construct a countable support iteration of length ω such that at the i^{th} stage of the iteration, a reflecting sequence is added to Σ̇_{ℱ}^{i} by a proper forcing. It is easily checked that the iteration generated a generic extension which satisfies φ(ℱ). □

Remark 3.9. The reader is cautioned that it does not immediately follow that if ℱ is moreover predense, then there is a proper forcing extension in which ψ(ℱ) holds, since a priori ℱ may fail to be predense in the generic extension. This is addressed in the next section. Similarly, if ℱ is defined by a Σ_{1}-formula, then there are two versions of ℱ in a generic extension — ℱ̇ and ℱ̌. This lemma only implies that ϕ(ℱ̌) can be forced.

Corollary 3.10. If PFA(ω_{1}) holds and T is a saturated A-tree, then φ(ℱ) is true for all families ℱ of subtrees of T.

Proof. Let T be an A-tree and let ℱ be a family of subtrees of ℱ. Applying Lemma 3.5, fix a subfamily ℱ′ of ℱ of cardinality at most ω_{1} such that ℱ^{⊥} = (ℱ′)^{⊥}. Then φ(ℱ′) implies φ(ℱ), and φ(ℱ′) is a Σ_{1}- statement in a parameter listing T and the members of ℱ′. Theorem 3.7 shows that there is a proper forcing making this Σ_{1}-statement hold.

□

4. Forcing instances of ψ

As already noted, Lemma 3.8 comes short of showing that, for a given predense ℱ, there is a proper forcing extension in which ψ(ℱ) holds. Upon forcing a reflecting sequence for Σ_{ℱ}^{0} , ℱ may fail to be predense.

A similar problem arises in the context of 𝒫(ω_{1})/NS. For a given antichain 𝒜 in 𝒫(ω_{1})/NS, there is a stationary subset S of [ω_{1} ∪ 𝒜]^{ω} such that ψ_{NS}(𝒜) is equivalent to S strongly reflecting in the sense of [5, p. 57]. Furthermore, there is a semi-proper forcing 𝒬 such that if generic absoluteness holds for 𝒬 in the sense of the previous section, then S strongly reflects. This does not ensure, however, that ψ_{NS}(𝒜) holds after forcing with 𝒬. In fact, while semi-proper forcing can always be iterated with revised countable support while preserving ω_{1}, there are models such as L in which there is no set forcing which makes 𝒫(ω_{1})/NS saturated. Hence, in the case of 𝒫(ω_{1})/NS, the discrepancy between forcability and the consequences of generic absoluteness can represent an insurmountable difficulty.

In this section we will see that the saturation of A-trees is fundamentally different in this regard. We will show that there is a single set mapping associated with a given predense ℱ such that if the set mapping reflects, ψ(ℱ) is true.

Lemma 4.1. Suppose that n ∈ ω, T is an A-tree, ℱ is a predense collection of subtrees of T and M is a countable elementary submodel of H((ℶ_{n+2})^{+}) which contains T and ℱ as elements. Let δ = M ∩ ω_{1}. Suppose X is an n-element subset of the δ-th level. Then

{P ∈ H(ω_{2}) : ∀t ∈ X∃A ∈ ℱ ∩ P (t ↾ (P ∩ ω_{1}) ∈ A)}

is M-stationary.

Proof. The proof is by induction on n. In the base case n = 0, there is nothing to show. Now suppose that the lemma is true for n and let M be a countable elementary submodel of H((ℶ_{n+3})^{+}) and X be an n+1element subset of the δ-th level of T. Let E be a given closed unbounded subset of [H(ω_{2})]^{ω} which is in M. Let t be any element of X and let X_{0} = X \{t}. The set of elements of [H(ω_{2})]^{ω} of the form N ∩H(ω_{2}) for some countable elementary submodel N of H((ℶ_{n+2})^{+}) is a club set in M, so, applying Lemma 3.6, there is a countable elementary submodel N of H((ℶ_{n+2})^{+}) such that ℱ, E are in N and there is an A in ℱ ∩ N such that t ↾ (N ∩ ω_{1}) is in A. Let E^{∗} be the set of all P in E such that A is in P. Clearly, E^{∗} is a club and belongs to N. Applying the inductive hypothesis to N and X_{0}, there is a P in E^{∗} ∩ N such that for every s in X_{0}, there is a A′ in ℱ ∩ P such that s ↾ (P ∩ ω_{1}) is in A′. But A is also in P and t ↾ (P ∩ ω_{1}) is in A as well since it is downward closed. □

Lemma 4.2. If ℱ is a predense family of subtrees of T, then there is an open stationary set mapping Σ_{ℱ} such that if Σ_{ℱ} admits a reflecting sequence, then ψ(ℱ) is true.

Proof. Fix, for each limit α < ω_{1}, a cofinal C_{α} ⊆ α of order type ω. Let T = {t(α, i) : α < ω_{1} and i < ω} be such that for every α and i, the height of t(α, i) is α. If M is a countable elementary submodel of H((ℶ_{ω+1})^{+}), define Σ_{ℱ} (M) as follows. Let δ = M ∩ ω_{1} and let Σ_{ℱ} (M) be the set of all P ∈ [H(ω_{2})]^{ω} such that either P is not an elementary submodel of H(ω_{2}) or else for every i < |C_{M∩ω_{1}} ∩ P | there is an A in P ∩ ℱ which contains t(δ, i) ↾ (P ∩ ω_{1}).

It is easily checked that Σ_{ℱ} (M) is open for every M. It should be clear that a reflecting sequence of Σ_{ℱ} can easily be modified to produce a witness ⟨N_{ν} : ν ∈ E⟩ to ψ(ℱ). Therefore it remains to show that Σ_{ℱ} (M) is M-stationary for all M in the domain of Σ_{ℱ} . To see this, let E ⊆ H(ω_{2}) be a club. Find a countable elementary submodel N of H((ℶ_{ω})^{+}) which is an element of M and contains E as a member. Put n = |C_{M∩ω_{1}} ∩ N| and apply Lemma 4.1 to N and n to find a P in E ∩ Σ_{ℱ} (M) ∩ M. □

Lemma 4.3. If ℱ is a predense family of subtrees of an A-tree, then there is a proper forcing extension in which ψ(ℱ) holds.

Proof. By the proof of Theorem 3.1 of [12], there is a proper forcing which adds a reflecting sequence to the Σ_{ℱ} of Lemma 4.2. □

5. Relative consistency results

In this section we will present a number of iterated forcing constructions aimed at proving upper bounds on the consistency of φ and the existence of a five element basis for the uncountable linear orders. Throughout this section we will utilize the following standard facts about L.

Theorem 5.1. (see [6, 2.2]) Suppose V = L. If κ is an uncountable regular cardinal and E is a stationary subset of κ, then ♢_{E}(κ) holds: there is a sequence ⟨A_{ξ} : ξ ∈ E⟩ such that for all X ⊆ κ,

{ξ ∈ E : X ∩ ξ = A_{ξ}}

is stationary.

Remark 5.2. If ♢_{E}(κ) holds and every element of E is an inaccessible cardinal, then ♢_{E}(κ) is equivalent to the following stronger statement: There is a sequence ⟨A_{δ} : δ ∈ E⟩ of elements of H(κ) such that if X_{i} (i < n) is a finite sequence of subsets of H(κ), then there is a stationary set of δ in E such that

A_{δ} = ⟨X_{i} ∩ H(δ) : i < n⟩.

It is easily checked that if κ is a regular cardinal in V, then it is also a regular cardinal in L. Hence if κ is inaccessible (Mahlo), then L satisfies that κ is inaccessible (Mahlo). Reflecting cardinals also relativize to L [8].

Theorem 5.3. Suppose that there is a Mahlo cardinal. Then there is a forcing extension of L which satisfies φ.

Proof. Let κ be Mahlo and note that κ is also Mahlo in L; from now on, work in L. Let E be the stationary set of inaccessible cardinals less than κ and, applying Theorem 5.1, let ⟨A_{δ} : δ ∈ E⟩ be a ♢_{E}(κ)-sequence in the revised sense stated in Remark 5.2. Construct a countable support iteration ⟨𝒫_{α}; 𝒬_{α} : α < κ⟩ of proper forcing notions of size < κ. If α ∈ E and A_{α} = (Ṫ , ℱ̇) where Ṫ is a 𝒫_{α}-name for an A-tree and ℱ̇ is a 𝒫_{α}-name for a family of subtrees of Ṫ, then we let 𝒬̇_{α} be a proper forcing in H(κ) which first forces ψ(ℱ̇ ∪ ℱ̇^{⊥} ) and then forces φ(ℱ̇). In other cases we can let 𝒬̇_{α} be any proper forcing in H(κ). Let 𝒫_{κ} be the limit of the iteration. By standard arguments the forcing 𝒫_{κ} is proper and κ-c.c. [9].

Suppose now Ṫ is a 𝒫_{κ}-name for an A-tree and ℱ̇ is a 𝒫_{κ}-name for a family of subtrees of Ṫ. Let ℱ̇_{δ} be the set of all 𝒫_{δ}-names Ṡ which are forced by every condition to be in ℱ̇. Since κ is Mahlo and each of the iterands of 𝒫_{κ} has cardinality less than κ, there is a relative closed and unbounded set D of δ in E such that 𝒫_{δ} has the δ-c.c., Ṫ is a 𝒫_{δ}-name, and if Ṡ is a 𝒫_{δ}-name for a subtree of Ṫ which has countable intersection with every element of ℱ̇_{δ} , then Ṡ is forced to be in ℱ̇^{⊥} . Since ⟨A_{α} : α ∈ E⟩ is a ♢_{E}(κ)-sequence, there is a δ in D such that A_{δ} = (Ṫ , ℱ_{δ}). At stage δ the partial order 𝒬̇_{δ} forces both ψ(ℱ̇_{δ} ∪ℬ̇) and φ(ℱ̇_{δ} ) where ℬ̇ is ℱ̇_{δ}^{⊥} computed after forcing with 𝒫_{δ}. By choice of δ, ℬ̇ is forced to be a subset of ℱ̇^{⊥} . Since ψ(ℱ̇_{δ} ∪ ℬ̇) is a Σ_{1}-formula, it is upwards absolute and hence forced by 𝒫_{κ}. By Lemma 2.2, 𝒫_{κ} forces ℱ̇_{δ} ∪ ℬ̇ is predense and hence that ℱ̇_{δ}^{⊥} = ℱ̇^{⊥} . Consequently, φ(ℱ̇_{δ} ) implies φ(ℱ̇). □

Theorem 5.4. If there is a cardinal which is both reflecting and Mahlo, then there is a proper forcing extension of L which satisfies the conjunction of PFA(ω_{1}) and φ. In particular the forcing extension satisfies that the uncountable linear orders have a five element basis.

Proof. This is very similar to the proof of Theorem 5.3, except that at stages α < κ which are not in E, we force with partial orders in H(κ) given by an appropriate book keeping device. Following [8], it is possible to arrange that PFA(ω_{1}) holds in the generic extension as well. □

Theorem 5.5. Suppose that there is an inaccessible cardinal κ such that for every κ_{0} < κ, there is an inaccessible cardinal δ < κ such that κ_{0} is in H(δ) and H(δ) satisfies there are two reflecting cardinals which are greater than κ_{0}. Then there is a proper forcing extension in which κ is ω_{2} and the uncountable linear orders have a five element basis.

First observe that by taking a direct sum of trees, Theorems 4.2 implies that if T⃗ is an ω-sequence of A-trees and ℱ⃗ is an ω-sequence such that ℱ_{n} is a family of subtrees of T_{n}, then there is a single set mapping Σℱ⃗ such that if Σℱ⃗ admits a reflecting sequence, then ψ(ℱ_{n} ∪ ℱ_{n} ^{⊥}) holds for all n < ω. Theorem 5.5 can be proved by iterating the forcings provided by the following lemmas with appropriate book keeping. By mixing in appropriate σ-closed collapsing forcings as needed, we may ensure that the iteration has the κ-c.c. but collapses every uncountable cardinal less than κ to ω_{1}.

Lemma 5.6. (see [15]) Let L be an uncountable linear order, X be a set of reals of size ℵ_{1}, and C be a Countryman order. There is a proper forcing 𝒫 of cardinality less than ℶ_{ω} which forces that “L contains an isomorphic copy of X, ω_{1}, ω_{1}^{∗}, C, or C^{∗}” is equivalent to an instance of CAT.

Lemma 5.7. Suppose that T is an A-tree, K is a subset of T, and there is a δ such that H(δ) satisfies that there are two reflecting cardinals. Then there is a proper forcing in H(δ) which forces the instance of CAT for K and T.

Proof. If λ is a reflecting cardinal in H(δ), let 𝒫_{λ} denote the proper forcing which satisfies the λ-c.c. and forces that H(δ)^{V^{𝒫_{λ}}} satisfies PFA(ω_{1}). If ℱ⃗ is an ω-sequence of families of subtrees of A-trees, let 𝒬ℱ⃗ be the proper forcing which forces the conjunction of ψ(ℱ_{n} ∪ℱ_{n} ^{⊥}) and φ(ℱ_{n}) for all n. Let λ_{0} < λ_{1} be the two reflecting cardinals in H(δ). We claim that

(𝒫_{λ_{0}} ∗ 𝒬̇ℛ⃗ ) ∗ 𝒫̇_{λ_{1}}

is the desired proper forcing where ℛ_{n} is the family of subtrees of T^{[n]} defined in Section 2. Clearly this forcing is proper and an element of H(δ). It suffices to show that it forces the instance of CAT for T and K. The key observation is that, after forcing with 𝒫_{λ_{0}}, if S is an element of ℛ_{n} ^{⊥} for some n, then S remains in ℛ_{n} ^{⊥} after any proper forcing which is in H(δ)^{V^{𝒫_{λ_{0}}}} . This is because asserting that S is not in ℛ_{n}^{⊥} is a Σ_{1}-statement with parameters T, K, and S. By arguments given in the proof of Theorem 5.3, 𝒬ℛ⃗ forces φ(ℛ̇_{n} ) is true for all n and that moreover this statement remains true after further forcing with 𝒫_{λ_{1}}. Applying Theorem 2.7 in the extension by

(𝒫_{λ_{0}} ∗ 𝒬̇ℛ⃗ ) ∗ 𝒫̇_{λ_{1}} ,

both PFA(ω_{1}) and the Key Lemma for T and K hold. Therefore, by theorems from [13], the instance of CAT for T and K is true. □

6. Concluding remarks and questions

Observe that the property of κ in the statement of Theorem 5.5 is expressible by a Σ_{0}-formula with no parameters. Hence the least such cardinal is not reflecting and it is therefore possible — if such cardinals exist at all — to produce a forcing extension of L in which Shelah’s conjecture is true and ω_{2} is not reflecting in L. On the other hand, we do not known the answer to the following.

Question 6.1. Suppose that the uncountable linear orders have a five element basis. Is there a δ < ω_{2} such that L_{δ} satisfies “there is a reflecting cardinal?”

It is also natural to ask:

Question 6.2. Does PFA(ω_{1}) imply Aronszajn tree saturation?

The only known direct construction of a failure of A-tree saturation is given in [4, §2] and is based upon the existence of a Kurepa tree. Baumgartner has shown that PFA(ω_{1}) implies that there are no Kurepa trees [2, 7.11].^{7} This is likely closely related to the consistency strength of φ.

Question 6.3. If φ is true, must ω_{2} be Mahlo in L?

References

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

[2] James Baumgartner. Applications of the Proper Forcing Axiom. In K. Kunen and J. Vaughan, editors, Handbook of Set-Theoretic Topology. North-Holland, 1984.

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

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

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

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

[7] Matthew Foreman, Menachem Magidor, and Saharon Shelah. Martin’s Maximum, saturated ideals, and nonregular ultrafilters. I. Ann. of Math. (2), 127(1):1–47, 1988.

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

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

[10] 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.

7The hypothesis which appears in [2, 7.11] is PFA but the proof shows that the conclusion follows from PFA(ω_{1}).

[11] J. Tatch Moore. Structural analysis of Aronszajn trees. Proceedings of the 2005 Logic Colloquium, Athens, Greece.

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

[13] Justin Tatch Moore. A five element basis for the uncountable linear orders. Ann. of Math. (2), 163(2):669–688.

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

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

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

[17] 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.

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

Bernhard König, Equipe de Logique Mathématique, Université de Paris 7 Denis Diderot, 75251 Paris, France

Paul Larson, Department of Mathematics and Statistics, Miami University, Oxford, Ohio 45056, USA

Justin Tatch Moore, Department of Mathematics, Boise State University, Boise, Idaho 83725, USA

Boban Veličković, Equipe de Logique Mathématique, Université de Paris 7 Denis Diderot, 75251 Paris, France