Coding with ladders a well ordering of the reals

Uri Abraham Department of Mathematics and Computer Science, Ben-Gurion University, Be’er-Sheva, Israel and Saharon Shelah ^{∗} Institute of Mathematics The Hebrew University, Jerusalem, Israel

February 15, 2002

Abstract Any model of ZFC + GCH has a generic extension (made with a poset of size ℵ_{2}) in which the following hold: MA + 2^{ℵ_{0}} = ℵ_{2}+ there exists a Δ_{1}^{2}-well ordering of the reals. The proof consists in iterating posets designed to change at will the guessing properties of ladder systems on ω_{1}. Therefore, the study of such ladders is a main concern of this article.

1 Preface

The character of possible well-orderings of the reals is a main theme in set theory, and the work on long projective well-orderings by L. Harrington [4] can be cited as an example. There, the relative consistency of ZFC + MA +2^{ℵ_{0}} > ℵ_{1} with the existence of a Δ_{3}^{1} well-ordering of the reals is shown. A different type of question is to ask about the impact of large cardinals on definable well-orderings. Work of Shelah and Woodin [7], and Woodin [9] is relevant to this type of question. Assuming in V a cardinal which is both measurable and Woodin, Woodin [9] proved that if CH holds, then there is no Σ_{1}^{2} well-ordering of the reals. This result raises two questions:

∗This research was supported by The Israel Science Foundation founded by the Israel Academy of Sciences and Humanities. Publication # 485.

1. If large cardinals and CH are assumed in V, can the Σ_{1}^{2} result be strengthen to Σ_{2}^{2}? That is, is there a proof that large cardinals and CH imply there is no Σ_{2}^{2} well-orderings of the reals?

2. What happens if CH is not assumed?

Regarding the first question, Abraham and Shelah [2] describes a poset of size ℵ_{2} (assuming GCH) which generically adds no reals and provides a Δ_{2}^{2} well-ordering of the reals. Thus, if one starts with any universe with a large cardinal κ, one can extend this universe with a small size forcing and obtain a Δ_{2}^{2} well-ordering of the reals. Since small forcings will not alter the assumed largeness of a cardinal in V, the answer to question 1 is negative.

Regarding the second question, Woodin (unpublished) uses an inaccessible cardinal κ to obtain a generic extension in which

1. MA for σ-centered posets + 2^{ℵ_{0}} = κ, and

2. there is a Σ_{1}^{2} well-ordering of the reals.

Solovay [8] shows that the inaccessible cardinal is dispensable: any model of ZFC has a small size forcing extension in which the following holds:

1. MA for σ-centered posets + 2^{ℵ_{0}} = ℵ_{2}, and

2. there is a Σ_{1}^{2} well-ordering of the reals.

In [3] we show how Woodin’s result can be strengthened to obtain the full Martin’s axiom. We prove there that if V satisfies the GCH and contains an inaccessible cardinal κ, then there is a poset of cardinality κ that gives generic extensions in which

1. MA + 2^{ℵ_{0}} = κ, and

2. there is a Σ_{1}^{2} well-ordering of the reals.

Our aim in this paper is to show that the inaccessible cardinal is not really necessary, even to get the full Martin’s Axiom.

Theorem 1.1 Assume 2^{ℵ_{0}} = ℵ_{1} and 2^{ℵ_{1}} = ℵ_{2}. There is a forcing poset of size ℵ_{2} that provides a cardinal preserving extension in which Martin’s Axiom +2^{ℵ_{0}} = ℵ_{2} holds, and there is a Σ_{1}^{2} well-ordering of the reals. In fact, there is even a Σ^{2[ℵ_{1}]} well-ordering of the reals there.

The concepts Σ_{1}^{2} and Σ^{2[ℵ_{1}]} will soon be defined, but first we shall point to what we consider to be the main novelty of this paper, the use of ladder systems as coding devices. A ladder over S ⊆ ω_{1} is a sequence \overline{η} = ⟨η_{δ} | δ ∈ S⟩ where η_{δ} : ω → δ is increasing and cofinal in δ. Two ladders over S, \overline{η}′ a subladder of \overline{η}, may encode a real (a subset of ω). Namely the coding of a real r is expressed by the relationship between η′_{δ} and η_{δ} (for every δ). Splitting ω_{1} into ℵ_{2} pairwise almost disjoint stationary sets, it is possible to encode ℵ_{2} many reals (and hence a well-ordering) using ℵ_{2} pairs of ladder sequences. Of course, we need some property that ensures uniqueness of these ladders, in order to make this well-ordering definable. Such a property will be obtained in relation with the guessing power of the ladders. A ladder system ⟨η_{δ} | δ ∈ S⟩ is said to be club (closed unbounded set) guessing if for every closed unbounded C ⊆ ω_{1}, [η_{δ}] ⊆^{∗} C for some δ ∈ S. It turns out that there is much freedom to manipulate the guessing properties of ladders, and, technically speaking, this shall be a main concern of the paper.

We now define the Σ_{1}^{2} and Σ^{2[ℵ_{1}]} relations. The structure with the membership relation on the collection of all hereditarily countable sets is denoted H(ℵ_{1}). Second-order formulas over H(ℵ_{1}) that contain n alternations of quantifiers are denoted Σ_{n}^{2} when the external quantifier is an existential class quantifier. Thus a Σ_{n}^{2} formula has the form

∃X_{1}∀X_{2} … X_{n}φ(X_{1}, …, X_{n})

where φ may only contain first-order quantifiers over H(ℵ_{1}) and predicates X_{1}, …, X_{n} are interpreted as subsets of H(ℵ_{1}). (One can either write X_{i}(s) treating X_{i} as a predicate, or s ∈ X_{i} treating X_{i} as a class.) Σ^{2} denotes the union of all Σ_{n}^{2} formulas.

If the second-order quantifiers only quantify classes (subsets of H(ℵ_{1})) of cardinality ≤ ℵ_{1}, then the resulting set of formulas is denoted Σ_{n}^{2[ℵ_{1}]}. So Σ_{1}^{2[ℵ_{1}]} for example denotes second order formulas of the form “there exists a subset X of H(ℵ_{1}) of size ≤ ℵ_{1} such that φ(X)” where φ is a first order formula. We write Σ^{2[ℵ_{1}]}, without a subscript, for ⋃_{n<ω} Σ_{n}^{2[ℵ_{1}]}.

In Theorem 1.1 above, we get a well-ordering which is Σ^{2[ℵ_{1}]}, and we will explain now why MA + 2^{ℵ_{0}} > ℵ_{1} implies that such a relation is necessarily Σ_{1}^{2}. This transformation which replaces any number of quantifiers over sets of size ℵ_{1} with a single existential quantifier over arbitrary subsets of H(ℵ_{1}) is a trick of Solovay’s that was used by him in [8]. The basic idea is to use the almost-disjoint-sets coding (Jensen and Solovay [5]) in a way which will be sketched here.

Theorem 1.2 (Solovay) Assume MA+2^{ℵ_{0}} > ℵ_{1}. Any Σ^{2[ℵ_{1}]} formula φ(\overline{x}) over H(ℵ_{1}), with free variables x_{1}, …, x_{n}, is equivalent to a Σ_{1}^{2} formula ψ(\overline{x}).

Proof. It seems easier to prove first that every Σ^{2[<𝔠]} formula is equivalent with a Σ_{1}^{2} formula. (The Σ^{2[<𝔠]} formulas are second order formulas over H(ℵ_{1}) in which class quantification occurs only for subset of H(ℵ_{1}) of size less than continuum.) Then the theorem follows because the Σ^{2[ℵ_{1}]} classes are a naturally characterized subclass of the Σ^{2[<𝔠]}.

So let φ(x) be any Σ^{2[<𝔠]} formula. The equivalent Σ_{1}^{2} formula ψ begins as follows (with existential class quantifiers mixed with first-order quantifiers which do not change the complexity of the formula):

There is a set τ ⊂ P(ω) such that the relation

x <_{τ} y iff y \ x is finite

is a well-order of τ such that there is no infinite a ⊆ ω with a ⊆^{∗} x for all x ∈ τ. There is also a map μ : τ ⟶ H(ℵ_{1}), which is onto H(ℵ_{1}), and there is a map ρ : τ ⟶ [ω]^{ℵ_{0}} such that for distinct x, y ∈ τ, τ(x) and τ(y) are almost disjoint. ([ω]^{ℵ_{0}} is the collection of infinite subsets of ω.)

Then ψ continues with first-order quantifiers that replace the Σ^{2[<𝔠]} quantifiers of φ in the following manner. To represent any X ⊆ H(ℵ_{1}) of size < 𝔠, look at the set μ^{−1}X ⊆ τ. Since its size is < 𝔠, there is by Martin’s Axiom an infinite set a ⊆ ω almost included in every set in μ^{−1}X. Hence μ^{−1}X is bounded in τ. So there is t_{0} in τ so that μ^{−1}(x) <_{τ} t_{0} for every x ∈ X. Now look at the collection {ρ(t) | t <_{τ} t_{0}} of almost-disjoint sets (its cardinality is < 𝔠) and use Martin’s Axiom to encode with one r the set ρ[μ^{−1}X]. That is find r ⊂ ω such that for t <_{τ} t_{0}, ρ(t) ∩ r is finite iff μ(t) ∈ X. Then r and t_{0} represent X.

2 Ladder systems

The notation A ⊆^{∗} B is used for “almost inclusion” on subsets of ω_{1}, meaning that A \ B is finite. Similarly A =^{∗} B is defined if A ⊆^{∗} B and B ⊆^{∗} A. A ≠^{∗} B is the negation of A =^{∗} B.

Definition 2.1 1. A ladder system over S ⊆ ω_{1} (consisting of limit ordinals) is a sequence \overline{η} = ⟨η_{δ} | δ ∈ S⟩, where η_{δ} is an increasing ω-sequence converging to δ. S is called “the domain” of \overline{η}, and is denoted dom(\overline{η}). \overline{η} is called “trivial” if dom(\overline{η}) is non-stationary. The range of η_{δ} is denoted [η_{δ}] (so [η_{δ}] = {η_{δ}(i) | i ∈ ω}), and ⋃_{δ∈S} [η_{δ}] is the “range” of \overline{η}. So, [η_{δ}] ⊂^{∗} C means that, except for finitely many k’s, η_{δ}(k) ∈ C always holds.

2. Let \overline{η} and \overline{μ} be two ladder systems. We say that \overline{η} and \overline{μ} are almost disjoint iff, for some club C ⊆ ω_{1}, for any δ ∈ C ∩dom(\overline{η})∩dom(\overline{μ}), [η_{δ}]∩ [μ_{δ}] =^{∗} ∅.

3. We say that \overline{η} is a subladder of \overline{μ} iff the following holds for some club C ⊆ ω_{1}:

C ∩ dom(\overline{η}) ⊆ dom(\overline{μ}) and for δ ∈ C ∩ dom(\overline{η}), [η_{δ}] ⊆^{∗} [μ_{δ}].

In such a case we write \overline{η} ⊲ \overline{μ}. Also, \overline{η} =^{∗} \overline{μ} iff both \overline{η} ⊲ \overline{μ} and \overline{μ} ⊲ \overline{η}. That is, \overline{η} =^{∗} \overline{μ} iff there is a club set C ⊆ ω_{1} such that dom(\overline{η}) ∩ C = dom(\overline{μ}) ∩ C, and [η_{δ}] =^{∗} [μ_{δ}] for δ ∈ dom(\overline{η}) ∩ C.

4. The difference ladder \overline{ρ} = \overline{η} \ \overline{μ} is defined by

[ρ_{δ}] = \{ \begin{matrix}[η_{δ}] & if δ ∈ dom(\overline{η}) \ dom(\overline{μ}) \\ [η_{δ}] \ [μ_{δ}] & if this set is infinite \\ undefined & otherwise \end{matrix}

It is the ⊲-maximal ladder included in \overline{η} and (almost) disjoint from \overline{μ}.

5. Given any A ⊆ ω_{1}, the restriction ladder \overline{η} ↾ A is naturally defined, and its domain is A ∩ dom(\overline{η}). If x ⊆ ω is infinite, then \overline{η} ↾ x means something else: it is obtained by enumerating x = {x_{k} | k ∈ ω} in increasing order, and setting (\overline{η} ↾ x) = \overline{ρ} where ρ_{δ}(k) = η_{δ}(x_{k}) for every δ ∈ dom(\overline{η}).

We shall define some properties of ladders (in fact, of =^{∗} equivalence classes).

Definition 2.2 Let \overline{η} be a ladder over S.

1. We say that \overline{η} is club-guessing iff for every club C ⊆ ω_{1} there is δ ∈ S such that [η_{δ}] ⊆^{∗} C. (So, in this case, δ ∈ C, and hence dom(\overline{η}) is stationary if \overline{η} is club guessing.) For brevity, we may use the term guessing instead of club-guessing.

2. We say that \overline{η} is strongly club guessing (or just strongly guessing) iff for any club C ⊆ ω_{1} for some club D, if δ ∈ D ∩ S then [η_{δ}] ⊆^{∗} C. If \overline{η} is strongly guessing and \overline{ρ} ⊲ \overline{η}, then clearly \overline{ρ} is also strongly guessing. (Be careful: if \overline{ρ} ⊲ \overline{η} and \overline{η} is strongly guessing, you cannot infer that \overline{ρ} is guessing, unless \overline{ρ} is non-trivial.) The trivial ladder is (trivially) strongly guessing, and hence we cannot say that a strongly guessing ladder is always guessing. A strongly guessing non-trivial ladder is, of course, guessing.

3. We say that a club set C ⊆ ω_{1} avoids \overline{η} iff for every δ ∈ S (except a non-stationary set), [η_{δ}] ∩ C =^{∗} ∅.

4. We say that \overline{η} is avoidable iff some club set avoids \overline{η}. If every ladder over S is avoidable, then we say that S itself is avoidable. Hence, in particular, if S is non-stationary, then S is avoidable. Remark that if \overline{η} is avoidable, then \overline{η} is non-guessing. So \overline{η} is strongly guessing and avoidable iff \overline{η} is trivial. The collection of all avoidable sets forms an ideal which will be shown to be normal in the following subsection.

5. Maximal ladders. Suppose that \overline{η} is some strongly guessing ladder over S, and X ⊇ S is a subset of ω_{1}. If every ladder over X and (almost) disjoint from \overline{η} is avoidable, then we say that \overline{η} is maximal for X. In such a case, for every X′ ⊆ X, \overline{η} ↾ X′ is maximal for X′. The trivial ladder ∅ is trivially maximal for any avoidable set. Our terminology may be misleading because a maximal ladder for X is not necessarily defined over X, it is rather the maximality which is for X. Thus, if \overline{η} is maximal for X, then \overline{μ} ⊲ \overline{η} for every strongly guessing ladder \overline{μ} over a subset of X. (Because \overline{μ} \ \overline{η} is, in that case, strongly guessing and disjoint from \overline{η}, and is hence avoidable. Thus dom(\overline{μ} \ \overline{η}) is not stationary, and hence \overline{μ} ⊲ \overline{η}.) Hence if both \overline{μ} and \overline{η} are maximal for X, then \overline{μ} =^{∗} \overline{η}. We denote this unique ladder, maximal for X, by χ(X).

It is easy to see that if \overline{η} is maximal for X and X_{0} ⊆ X then \overline{η} ↾ X_{0} is maximal for X_{0}.

2.1 Ideals connected with ladders

We are going to define four ideals on ω_{1}: the ideal of non-guessing restrictions, denoted I\overline{η}, the ideal of avoidable sets, denoted I_{0}, the ideal of maximal guesses, denoted I_{1}, and the ideal of bounded intersections, I(\overline{S}). Then we will prove that all are normal ideals.

Definition 2.3 The ideal of non-guessing restrictions. Let \overline{η} be a guessing ladder over X. The collection of all subsets S ⊆ ω_{1} for which \overline{η} ↾ S is not guessing is a proper, normal ideal, denoted I\overline{η}.

The ideal of avoidable sets. S ∈ I_{0} iff every ladder system over S is avoidable.

The ideal of maximal guesses. The ideal I_{1} is the collection of all sets X ⊆ ω_{1} such that there is a maximal ladder for X.

So S ∈ I_{1} iff there is a strongly guessing ladder system \overline{η} such that dom(\overline{η}) ⊆ S and any ladder over S and disjoint from \overline{η} is avoidable. As said above, this unique ladder \overline{η} is denoted χ(S). (Uniqueness is up to =^{∗}, where non-stationary sets and finite differences do not count.)

In case S ∈ I_{0}, then S ∈ I_{1}, and χ(S) is the trivial (empty) ladder ∅. So

I_{0} ⊆ I_{1}.  (1)

The ideal of bounded intersections. Let \overline{S} = ⟨S_{i} | i ∈ ω_{2}⟩ be a collection of ℵ_{2} stationary subsets of ω_{1} such that the intersection of any two is non-stationary (we say that \overline{S} is a sequence of pairwise almost disjoint stationary sets). The ideal I(\overline{S}) consists of those sets H ⊆ ω_{1} for which

|{i ∈ ω_{2} | H ∩ S_{i} is stationary }| ≤ ℵ_{1}.

Sets in I(\overline{S}) will also be called \overline{S}-small sets. It may seem that I(\overline{S}) is not connected to ladders, but we will later show the consistency of I(\overline{S}) = I_{1}.

Lemma 2.4 All four ideals are normal.

Proof. An ideal on ω_{1} is said to be normal if it is closed under diagonal unions.

The ideal of non-guessing restrictions. Let \overline{η} be a guessing ladder over X. To prove normality of I\overline{η}, suppose A_{ξ} ∈ I\overline{η}, for ξ < ω_{1}. Thus, for every ξ there is a club set C_{ξ} such that δ ∈ A_{ξ} ∩ X ⇒ [η_{δ}] ⊄^{∗} C_{ξ}. Let

A = ∇_{ξ∈ω_{1}}A_{ξ} {def \atop =} \{α ∈ ω_{1} | ∃ξ < α(α ∈ A_{ξ})\}

be the diagonal union, and C = Δ_{ξ∈ω_{1}}C_{ξ} be the diagonal intersection of the club sets. Then A ∈ I\overline{η} because for δ ∈ A ∩ X, [η_{δ}] ⊄^{∗} C.

The ideal of avoidable sets. We check that I_{0} is normal. Suppose S_{ξ} ∈ I_{0} for ξ ∈ ω_{1}, and let S = ∇_{ξ∈ω_{1}}S_{ξ} be the diagonal union. Let \overline{η} = ⟨η_{δ} | δ ∈ S⟩ be any ladder over S, and we will show that \overline{η} is avoidable and hence that S ∈ I_{0}. Indeed, a slightly more general fact will be used later:

If S_{ξ} ⊆ ω_{1} are arbitrary sets, S = ∇_{ξ∈ω_{1}}S_{ξ}, and \overline{η} is a ladder over S such that \overline{η} ↾ S_{ξ} is avoidable for every ξ ∈ ω_{1}, then \overline{η} is avoidable.

To see this, let C_{ξ} for ξ ∈ ω_{1} be a club set that avoids \overline{η} ↾ S_{ξ}, and let C = Δ_{ξ∈ω_{1}}C_{ξ} be their diagonal intersection. Then C avoids \overline{η}, as can easily be checked.

The ideal of maximal guesses. We prove that I_{1} is normal. So suppose that S_{ξ} ∈ I_{1} for ξ ∈ ω_{1} are given, and S = ∇_{ξ∈ω_{1}}S_{ξ} is their diagonal union. We must prove that S ∈ I_{1}. First we claim that the sets {S_{ξ} | ξ ∈ ω_{1}} may be assumed to be pairwise disjoint. Indeed, define S_{ξ}^{∗} = S_{ξ} \ ⋃{S_{ξ′} | ξ′ < ξ}. Then S = ∇S_{ξ}^{∗}, and the sets S_{ξ}^{∗} are in I_{1} and are pairwise disjoint. So we do assume now that the S_{ξ}’s are pairwise disjoint. For every ξ ∈ ω_{1}, χ(S_{ξ}) is a strongly guessing ladder over its domain S_{ξ}^{0} ⊆ S_{ξ} (and S_{ξ}^{0} = ∅ when S_{ξ} ∈ I_{0}). Define S^{0} = ∇_{ξ∈ω_{1}}S_{ξ}^{0}. Clearly S^{0} ⊆ S. For δ ∈ S^{0} define η_{δ} to be χ(S_{ξ})_{δ} for the (unique) ξ < δ such that δ ∈ S_{ξ}^{0}.

Claim: \overline{η} = ⟨η_{δ} | δ ∈ S^{0}⟩ is maximal for S, and hence S ∈ I_{1}.

Proof. We first prove that \overline{η} is strongly guessing. Well, if C ⊆ ω_{1} is club, find for each ξ ∈ ω_{1} a club set D_{ξ} such that for δ ∈ D_{ξ} ∩ S_{ξ}^{0}, (χ(S_{ξ}))_{δ} ⊆^{∗} C. Now define D = Δ_{ξ∈ω_{1}}D_{ξ} to be the diagonal intersection. It follows that for every δ ∈ S^{0} ∩ D, [η_{δ}] ⊂^{∗} C.

To prove maximality, assume \overline{μ} is defined on S and is disjoint from \overline{η}. Then \overline{μ} ↾ S_{ξ} is disjoint from χ(S_{ξ}) ↾ S_{ξ} \ (ξ + 1). Hence \overline{μ} ↾ S_{ξ} is avoidable for every ξ < ω_{1}, and by the proof of normality of I_{0}, \overline{μ} is avoidable.

The ideal of bounded intersections. Let \overline{S} = ⟨S_{i} | i ∈ ω_{2}⟩ be a collection of pairwise almost disjoint stationary subsets of ω_{1} defining I(\overline{S}). If H_{ξ} for ξ ∈ ω_{1} are in I(\overline{S}), then there is a bound j_{0} < ω_{2} such that for every j_{0} ≤ j < ω_{2} S_{j} ∩H_{ξ} is non-stationary. Hence ∇_{ξ}S_{j} ∩H_{ξ} = S_{j} ∩∇H_{ξ} is non-stationary, and thus ∇_{ξ}H_{ξ} ∈ I(\overline{S}).

2.2 A(\overline{S}, \overline{η})

In this subsection we formulate a statement, A(\overline{S}, \overline{η}), and show that it implies I(\overline{S}) = I_{1}. The consistency of A(\overline{S}, \overline{η}) will be proved in the subsequent sections.

Definition 2.5 A(\overline{S}, \overline{η}) is the conjunction of the following six statements:

A1 \overline{S} = ⟨S_{i} | i ∈ ω_{2}⟩ is a sequence of pairwise almost disjoint stationary subsets of ω_{1}. \overline{η} is a ladder system, and ⋃_{i<ω_{2}} S_{i} ⊆ dom(\overline{η}).

A2 Every ladder disjoint from \overline{η} is avoidable. (It immediately follows that if \overline{μ} is strongly guessing, then \overline{μ}\\overline{η} is both avoidable and strongly guessing and thus \overline{μ} \ \overline{η} =^{∗} ∅, so that \overline{μ} ⊲ \overline{η}.)

A3 For every i < ω_{2}, S_{i} ∈ I_{1}. In fact, χ(S_{i}) is defined over S_{i} (and it is a non-trivial strongly guessing ladder over S_{i} such that any ladder over a subset of S_{i} and disjoint from χ(S_{i}) is avoidable). It follows by A2 that χ(S_{i}) ⊲ \overline{η}.

A4 If X ⊆ ω_{1} is such that X ∩ S_{i} is non-stationary for every i < ω_{2}, then X is avoidable (equivalently, in view of (A2), \overline{η} ↾ X is avoidable).

A5 If X ⊆ ω_{1} is not \overline{S}-small, \overline{ρ} is a ladder over X and \overline{ρ} ⊲ \overline{η}, then there exists i < ω_{2} such that S_{i} ⊆ X and χ(S_{i}) ⊲ \overline{ρ}.

A6 For every i ∈ ω_{2} either (χ(S_{i}), \overline{η} ↾ S_{i}) is clearly not encoding, or else r = d(χ(S_{i}), \overline{η} ↾ S_{i}) is defined, and in this case r = d(χ(S_{j}), \overline{η} ↾ S_{j}) for unboundedly many j’s. The meaning of this statement is clarified later in this subsection.

A′(\overline{T} , \overline{η}) is the following statement: \overline{T} = ⟨T_{i} | i < ω_{2}⟩ is a sequence of pairwise almost disjoint stationary subsets of ω_{1}. For every i < ω_{2}, T_{i} ∈ I_{1}, and if S_{i} denotes dom(χ(T_{i})), then A(\overline{S}, \overline{η}) holds for \overline{S} = ⟨S_{i} | i < ω_{2}⟩.

We first collect some simple consequences of the first five statements of A(\overline{S}, \overline{η}).

Lemma 2.6 The first five statements of A(\overline{S}, \overline{η}) imply that:

1. If \overline{ρ} ⊲ \overline{η} is avoidable, then dom(\overline{ρ}) is \overline{S}-small.

2. I_{0} ⊆ I(\overline{S}).

3. If \overline{μ} ⊲ \overline{η} is strongly guessing, then dom(\overline{μ}) is \overline{S}-small.

4. Actually: If \overline{μ} is strongly guessing, then dom(\overline{μ}) is \overline{S}-small.

5. I_{1} = I(\overline{S}).

Proof. To prove 1, assume \overline{ρ}⊲\overline{η} but X = dom(\overline{ρ}) is not \overline{S}-small. Then (A5) implies that, for some i < ω_{2}, χ(S_{i}) ⊲ \overline{ρ}. Hence \overline{ρ} is not avoidable (by (A3) which says that χ(S_{i}) is (strongly) guessing).

We prove 2. If X ∈ I_{0} (X is avoidable) then any ladder system over X, and in particular \overline{η} ↾ X, is avoidable. Hence (by item 1) dom(\overline{η} ↾ X) is \overline{S}-small. Thus X is \overline{S}-small (because X = X_{0} ∪ X_{1} where X_{0} = X ∩ ⋃_{i} S_{i} and X_{1} = X \ X_{0}. X_{1} is clearly \overline{S}-small, and X_{0} = dom(\overline{η} ↾ X)).

To prove 3, assume that dom(\overline{μ}) is not \overline{S}-small. Split \overline{μ} into \overline{μ}^{1} and \overline{μ}^{2}, two “halves” defined by taking (μ^{1})_{δ} to be an infinite co-infinite subset of μ_{δ} (for every δ ∈ dom(\overline{μ})), and letting \overline{μ}^{2} = \overline{μ} \ \overline{μ}^{1}. If X = dom(\overline{μ}) is not \overline{S}-small, then, by (A5) applied to \overline{μ}^{1}, there is i such that S_{i} ⊆ X and

χ(S_{i}) ⊲ \overline{μ}^{1}.  (2)

Since \overline{μ} is strongly guessing, \overline{μ}^{2} ↾ S_{i} is strongly guessing (and non-trivial as its domain is the stationary set S_{i}), but formula (2) shows that \overline{μ}^{2} ↾ S_{i} is disjoint from χ(S_{i}), and this contradicts the maximality of χ(S_{i}) for S_{i}.

To prove 4, suppose that \overline{ρ} is a strongly guessing ladder over X. To show that X ∈ I(\overline{S}), we reduce this claim to the case that \overline{ρ} ⊲ \overline{η}. Look at \overline{ρ} \ \overline{η} and its domain

X_{1} = {δ ∈ X | [ρ_{δ}] \ [η_{δ}] is infinite}.

By (A2), \overline{ρ} \ \overline{η} is avoidable. But, as \overline{ρ} is strongly guessing, any subladder of \overline{ρ} is also strongly guessing, and hence \overline{ρ} \ \overline{η} is strongly guessing and avoidable, which could only be if X_{1} is non-stationary.

Now set X_{2} = X \ X_{1}, and \overline{μ} = \overline{ρ} ↾ X_{2}. Then \overline{μ} ⊲ \overline{η} is strongly guessing, and hence by the previous item dom(\overline{μ}) is \overline{S}-small.

Finally we prove 5. If X ∈ I_{1} then X = X_{0} ∪ X_{1}, where X_{0} ∈ I_{0} and X_{1} is the domain of a strongly guessing ladder—namely χ(X). Hence X ∈ I(\overline{S}) by items 2 and 4.

Suppose now that X ∈ I(\overline{S}). By definition, there is γ < ω_{2} such that, for i ≥ γ, X ∩ X_{i} is non-stationary. Let ⟨T_{j} | j ∈ ω_{1}⟩ be an ω_{1}-enumeration of the collection {S_{i} | i < γ}. Then each T_{j} ∈ I_{1} by (A3). Let T = ∇_{j∈ω_{1}}T_{j} be the diagonal union. By normality of I_{1}, T ∈ I_{1}. Hence X ∩T ∈ I_{1}. But X \T has only countable intersections with each T_{j} (for in fact (X \T)∩T_{j} ⊆ j+1), and hence, certainly, has non-stationary intersections with every S_{i}, and is thus in I_{0} (by (A4)). As I_{0} ⊆ I_{1} (by formula (1) in Definition 2.3), X ∈ I_{1}.

We will prove next that if A(\overline{S}, \overline{η}) holds, then \overline{η} is determined, up to an I_{1} set, as that ladder \overline{η} for which (∃\overline{S})A(\overline{S}, \overline{η}).

Lemma 2.7 If the first five statements hold for A(\overline{S}, \overline{η}^{1}) and A(\overline{T} , \overline{η}^{2}), then I(\overline{S}) = I(\overline{T}) = I_{1}, and \{δ ∈ ω_{1} | [η_{δ}^{1}] ≠^{∗} [η_{δ}^{2}]\} ∈ I_{1}.

Proof. Define S^{1} = dom(\overline{η}^{1} \ \overline{η}^{2}), and S^{2} = dom(\overline{η}^{2} \ \overline{η}^{1}). We claim that S^{1}, S^{2} ∈ I_{1}. This implies the lemma because S^{1} ∪ S^{2} ∈ I_{1} follows. By symmetry, it suffices to deal with only one of these sets, for example with S^{1}.

Set \overline{ρ} = \overline{η}^{1}\\overline{η}^{2} (so S^{1} = dom(\overline{ρ})). Since it is disjoint from \overline{η}^{2}, \overline{ρ} is avoidable (by item (A2) of A(\overline{T} , \overline{η}^{2})). Yet, \overline{ρ} ⊲ \overline{η}^{1} , and so, by Lemma 2.6 (1), dom(\overline{ρ}) is \overline{S}-small, which, in view of Lemma 2.6(5), implies that S^{1} ∈ I_{1}.

Whenever A(\overline{S}, \overline{η}) holds, a set of reals can be decoded which we denote code(\overline{S}, \overline{η}). We will encode reals (subsets of ω) by taking subladders of \overline{η} appropriately chosen. Suppose that σ is a cofinal subset of order-type ω of some δ < ω_{1}. Identifying σ with ω, any σ′ ⊆ σ corresponds to a subset of ω. This encoding of reals as subsets of σ is too crude, because if we take end segments of σ and σ′ then a different real may be decoded. Since we shall be able to recover the ladder \overline{η} only up to finite changes we must have a more stable decoding procedure. So we look for a function d that associates with every pair (σ′, σ) as above some real d(σ′, σ) so that:

If σ_{1} =^{∗} σ_{2} and σ′_{1} =^{∗} σ′_{2}, then d(σ′_{1}, σ_{1}) = d(σ′_{2}, σ_{2}).

The range of d should be all subsets of ω, i.e., for every σ for every x ⊆ ω there is σ′ ⊆ σ such that d(σ′, σ) = x. It is not difficult to find such a function d, and we assume that the reader has picked one. (For example, you may look at the intervals of σ formed by successive members of σ′ and take those cardinalities that appear infinitely often.)

Now let \overline{σ}′ ⊲ \overline{σ} be two ladders; we say that (\overline{σ}′, \overline{σ}) encodes the real r ⊆ ω if, for every δ ∈ dom(\overline{σ}′), d([σ′_{δ}], [σ_{δ}]) = r. We may just write d(\overline{σ}′, \overline{σ}) = r in such a case.

Not every pair \overline{σ}′ ⊲ \overline{σ} encodes a real. An extreme case is when, for every δ_{1} ≠ δ_{2} in dom(\overline{σ}′), d(σ′_{δ_{1}}, σ_{δ_{1}}) ≠ d(σ′_{δ_{2}}, σ_{δ_{2}}). We shall say in such a case that (\overline{σ}′, \overline{σ}) are “clearly” not encoding.

Now we can understand the meaning of A6. If A(\overline{S}, \overline{η}) holds, we define

code(\overline{S}, \overline{η}) = \{r ⊆ ω | r = d(χ(S_{i}), \overline{η} ↾ S_{i}) for some i ∈ ω_{2}\}.

Clearly if r ∈ code(\overline{S}, \overline{η}), then r = d(χ(S_{i}), \overline{η} ↾ S_{i}) for an unbounded set of i ∈ ω_{2}.

Lemma 2.8 If A(\overline{S}, \overline{η}^{1}) and A(\overline{T} , \overline{η}^{2}), then code(\overline{S}, \overline{η}^{1}) = code(\overline{T} , \overline{η}^{2}).

Proof. Suppose that r ∈ code(\overline{S}, \overline{η}^{1}) and let U ⊂ ω_{2} be the unbounded set of indices i such that r = d(χ(S_{i}), \overline{η}^{1} ↾ S_{i}). We must check that for some (and hence for unboundedly many) j ∈ ω_{2}, r = d(χ(T_{j}), \overline{η}^{2} ↾ T_{j}) We know that [\overline{η}_{δ}^{1}] =^{∗} [\overline{η}_{δ}^{2}] except for an I_{1} set, and I_{1} = I(\overline{S}) = I(\overline{T}) (Lemma 2.7). That is, if H = \{δ ∈ ω_{2} | [\overline{η}_{δ}^{1}] ≠^{∗} [\overline{η}_{δ}^{2}]\}, then H ∈ I_{1}, and hence H ∈ I(\overline{S}). Thus there is an index i ∈ U such that

H ∩ S_{i} is non-stationary.  (3)

That is,

1. \overline{η}^{1} ↾ S_{i} =^{∗} \overline{η}^{2} ↾ S_{i} (that is, [\overline{η}_{δ}^{1}] =^{∗} [\overline{η}_{δ}^{2}] for all δ ∈ S_{i}, except for a non-stationary set),

2. d(χ(S_{i}), \overline{η}^{1} ↾ S_{i}) = r.

Now χ(S_{i}) is maximal for S_{i} (a stationary set) and hence its domain S_{i} is not avoidable. So by (A4) of A(\overline{T} , \overline{η}^{2}), for some j ∈ ω_{2}, X = S_{i} ∩T_{j} is stationary. Hence χ(S_{i}) ↾ X is maximally guessing (and non-trivial). Similarly χ(T_{j}) ↾ X is maximally guessing, and thus

χ(S_{i}) ↾ X =^{∗} χ(T_{j}) ↾ X

by the uniqueness of the maximal ladder over X (namely χ(X)). Since X ∩H is non-stationary (by (3) above),

\overline{η}^{1} ↾ X =^{∗} \overline{η}^{2} ↾ X

and thus (χ(T_{j}), \overline{η}^{2} ↾ T_{j}) encodes a real, and d(χ(T_{j}), \overline{η}^{2} ↾ T_{j}) = r.

3 The consistency of A(\overline{S}, \overline{η})

Our aim in this section is to prove the following Theorem. Assume that 2^{ℵ_{0}} = ℵ_{1} and 2^{ℵ_{1}} = ℵ_{2}. Suppose that \overline{T} = ⟨T_{i} | i < ω_{2}⟩ is a collection of ℵ_{2} pairwise almost disjoint stationary subsets of ω_{1}, and \overline{η} is a ladder system such that

(1) \overline{η} ↾ T_{i} is guessing (but not necessarily strongly guessing) for every i < ω_{2}.

(2) range(\overline{η}) ∩ T_{i} is empty for every i.

Then there is a generic extension in which A′(\overline{T} , \overline{η}) and Martin’s Axiom hold.

The extension is an iteration of the posets R(\overline{μ}), and P (\overline{η}, C) described below. Before proving this theorem, however, we review some notions from proper forcing theory.

3.1 Some proper forcing theory

This short subsection assembles some known definitions and results on proper forcing, such as α-properness and S-properness for a stationary set S. Our notations and terms are taken (with some minor changes) from Shelah’s book [6] (see also [1]).

Recall that if P is a forcing poset and N ≺ H_{λ} a countable elementary substructure, then a condition q ∈ P is N generic iff for every D ∈ N, dense in P, every extension of q is compatible with some condition in D ∩ N. A forcing poset P is proper is for some cardinal λ, for every countable N ≺ H_{λ} such that P ∈ N, every p ∈ P ∩ N has an extension that is N generic.

Definition 3.1 (of α-properness.) Let α be a countable ordinal. A poset P is said to be α-proper iff for every large enough cardinal λ, if ⟨N_{i} | i ≤ α⟩ is an increasing, continuous sequence of countable elementary submodels of H_{λ} such that P ∈ N_{0} and ⟨N_{j} | j ≤ i⟩ ∈ N_{i+1} for every i < α, then any p_{0} ∈ P ∩ N_{0} can be extended to q ∈ P that is N_{i}-generic for every i ≤ α.

Definition 3.2 Let S ⊆ ω_{1} be stationary. A forcing poset P is S-proper if it is proper for structures M such that M ∩ω_{1} ∈ S. That is, P is S-proper iff for sufficiently large λ, if M ≺ H_{λ} is countable, S, P ∈ M, and M ∩ ω_{1} ∈ S then any p ∈ P ∩ M can be extended to an M-generic condition.

A stronger property is that of a poset being S-complete. It means that whenever M ≺ H_{λ} is countable, with P, S ∈ M, and M ∩ ω_{1} ∈ S, then every increasing and generic ω-sequence of conditions in P ∩M has an upper bound in P. (A sequence of conditions is generic if it intersects every dense set of P in M.)

The notion (E, α)-properness is defined in Shelah ([6] (Chapter V). Just as properness is equivalent to the preservation of stationarity of S_{ℵ_{0}}(μ), so is (E, α)-properness equivalent to the preservation of an appropriate notion of stationarity defined there. However, for our article, a notion of somewhat less generality suffices.

Let I^{ω} be the collection of all increasing sequences of countable ordinals. We write \overline{α} = ⟨α_{i} | i < ω⟩ for \overline{α} ∈ I^{ω}. The club guessing property can be regarded as a notion of non-triviality of subsets of I^{ω}.

Definition 3.3 1. A family E ⊆ I^{ω} is stationary if for every club C ⊆ ω_{1} there is \overline{α} ∈ E such that [\overline{α}] = \{α_{i} | i ∈ ω\} ⊂ C.

2. Let E ⊆ I^{ω} be stationary. We say that the poset P is E-proper (or (E, ω)-proper, to emphasize that this notion is related to ω-properness) iff for every sufficiently large cardinal λ, whenever M_{i} ≺ H_{λ}, for i < ω, are countable with E, P ∈ M_{0} and are such that M_{i} ∈ M_{i+1} for all i < ω, if

⟨M_{i} ∩ ω_{1} | i < ω⟩ ∈ E

then any p ∈ P ∩M_{0} can be extended to a condition which is M_{i}-generic for every i < ω.

In Shelah [6] it is proved that the countable support iteration of posets that are S-proper (α-proper or E-proper) is again S-proper ( α-proper or Eproper, respectively). Also, if P is S-proper (E-proper), then, in V^{P}, S (respectively E) remains stationary.

Lemma 3.4 If E ⊆ I^{ω} is stationary and P is an E-proper poset, then E remains stationary in V^{P}.

Proof. Let D be a name in V^{P} forced by some p ∈ P to be a club subset of ω_{1}. Define an ω_{1} sequence ⟨M_{i} | i ∈ ω_{1}⟩ where M_{i} ≺ H_{λ} are countable with ⟨M_{i} | i ≤ j⟩ ∈ M_{j+1}, and such that p, P, D ∈ M_{0}. The set C = {M_{i} ∩ω_{1} | i ∈ ω_{1}⟩ is closed unbounded in ω_{1}. Since E is stationary, there is \overline{α} ∈ E such that {α_{n} | n ∈ ω} ⊂ C. Then α_{n} = M_{i(n)} ∩ ω_{1} and N_{n} = M_{i(n)} is an increasing sequence of structures with N_{n} ∈ N_{n+1} and such that ⟨N_{i} ∩ ω_{1} | i < ω⟩ ∈ E. So there is an extension q ∈ P that is N_{i}-generic for every i < ω. So for every i q ⊩ α_{i} ∈ D. (Because q forces that D is unbounded below α_{1} = ω_{1}^{N_{i}}.) Thus q ⊩ [\overline{α}] ⊆ D, as required.

We shall define now two subsets of I^{ω}, E\overline{η} and D\overline{η}, which will be used later.

Definition 3.5 1. Let \overline{η} be a ladder system and S = dom(\overline{η}). Define

E\overline{η} ⊆ I^{ω} by

\overline{α} = ⟨α_{i} | i < ω⟩ ∈ E\overline{η}

iff

\overline{α} ∈ I^{ω} and, for δ = sup\{α_{i} | i < ω\}, δ ∈ S and \overline{α} is an end
segment of η_{δ} (i.e., for some k, η_{δ}(k + i) = α_{i} for all is).

It is obvious that E\overline{η} is stationary iff \overline{η} is club guessing. Thus, if \overline{η} is club guessing and P is E\overline{η}-proper, then \overline{η} remains a guessing ladder in V^{P}.

2. The set D\overline{μ} ⊆ I^{ω} (D is for disjoint) is defined for any ladder \overline{μ} as follows: \overline{α} ∈ D\overline{μ} iff for δ = sup\{α_{i} | i < ω\}, either δ ∉ dom(\overline{μ}) or [\overline{α}] ∩ [μ_{δ}] =^{∗} ∅. If \overline{μ} is disjoint from \overline{η}, then E\overline{η} ⊆ D\overline{μ}. Thus, in this case, if P is (D\overline{μ}, ω)-proper, then P is (E\overline{η}, ω)-proper as well.

3.2 The building blocks

Two families of posets are described in this subsection: R(\overline{μ}) and P (\overline{η}, C).

The poset R(\overline{μ}). Let \overline{μ} be a ladder over a set S ⊆ ω_{1}. The poset R(\overline{μ}) introduces a generic club to ω_{1} that avoids \overline{μ}. So, naturally,

c ∈ R(\overline{μ})

iff

c ⊆ ω_{1} is countable, closed (in particular max(c) ∈ c), and for every δ ∈ S, [μ_{δ}] ∩ c is finite.

The ordering on R(\overline{μ}) is end-extension.

The cardinality of R(\overline{μ}) is the continuum. It is clear that R(\overline{μ}) is ω_{1} \ S complete. A short argument is needed in order to prove that it is proper.

Observe first that for any condition q ∈ R(\overline{μ}) and dense set D ⊆ R(\overline{μ}), if α_{0} = max(q) then there is a closed unbounded set of ordinals γ < ω_{1}, α_{0} < γ, such that for every α_{1} with α_{0} < α_{1} < γ there is an extension q′ ∈ D such that q′ ⊂ γ and α_{1} ∈ q′ is the successor of α_{0} in q′. For example, the club set can be obtained by defining a continuous, increasing chain ⟨N_{α} | α ∈ ω_{1}⟩ of countable elementary substructures of some H_{λ} with \overline{μ} and the dense set D in N_{0}. Then ⟨ω_{1} ∩ N_{α} | α ∈ ω_{1}⟩ is as required.

Suppose that a countable M ≺ H_{λ} and a condition p_{0} ∈ R(\overline{μ}) ∩ M are given. We want to define an increasing, generic sequence of conditions p_{i} extending p_{0} so that for δ = M ∩ ω_{1}, p = ⋃_{i∈ω} p_{i} ∪ {δ} is a condition. The case M ∩ ω_{1} ∉ S is trivial and so assume that δ = M ∩ ω_{1} ∈ S. The problem is that we may decide infinitely often to put μ_{δ}(n) in ⋃_{i} p_{i}, and then p is not a condition. The preliminary observation enables the construction of the sequence p_{i} in such a way that p ∩ [μ_{δ}] ⊆ p_{0} is finite. The point is that when we need to extend a condition p_{i} into a dense set D, we first consider the club set formulated above (do it in the substructure M) and find a limit ordinal γ in the club that is in M. Now α_{1} < γ is chosen so that the interval [α_{1}, γ] is disjoint to [μ_{δ}]. (The fact that [μ_{δ}] is only an ω sequence implies the existence of such an ordinal.

R(\overline{μ}) is not ω-proper. For suppose M_{i}, i < ω is an increasing sequence of elementary submodels such that α_{i} = M_{i} ∩ ω_{1} ∈ [μ_{δ}] for infinitely many i’s, where δ = sup{α_{i} | i < ω}. Then no condition can be generic for all of the M_{i}s. However, if δ ∉ S or ⟨M_{i} ∩ ω_{1} | i < ω⟩ is disjoint from [μ_{δ}] (or has only a finite intersection) then there is no problem in finding such a generic condition. That is, R(\overline{μ}) is (D\overline{μ}, ω)-proper. In fact, if p_{i} is any sequence of increasing conditions where p_{i} ∈ M_{i} is M_{i−1} generic, then ⋃_{i} p_{i} gives a condition. This property is stronger than (D\overline{μ}, ω)-properness, but in application we shall mix proper forcings with R(\overline{μ}) forcings and hence the iteration itself is (D\overline{μ}, ω)- proper.

Hence we have the following which will be used in Lemma 3.9.

Lemma 3.6 Suppose that \overline{μ} is a ladder system and A, B ⊆ dom(\overline{μ}) are such that \overline{μ} ↾ A ∩ B is not guessing. Then R(\overline{μ} ↾ A) is E_{\overline{μ}↾B}-proper.

Proof. Suppose that A, B ⊆ dom(\overline{μ}) are such that \overline{μ} ↾ A∩B is not guessing. Let C ⊆ ω_{1} be a club set such that, for every δ ∈ A ∩ B, [μ_{δ}] ⊄^{∗} C. Suppose that M_{i} ≺ H_{λ} for i < ω are as in the definition of E_{\overline{μ}↾B} properness and δ = sup(M_{i} ∩ ω_{1} | i < ω). So, E_{\overline{μ}↾B}, R(\overline{μ} ↾ A) ∈ M_{0}. Hence A, B ∈ M_{0} and thus C ∈ M_{0} can be assumed. Then M_{i} ∩ ω_{1} ∈ C for every i. Since ⟨M_{i} ∩ ω_{1} | i < ω⟩ ∈ E_{\overline{μ}↾B}, δ ∈ B and [μ_{δ}] =^{∗} \{M_{i} ∩ ω_{1} | i < ω\}. Thus [μ_{δ}] ⊆^{∗} C and hence δ ∉ A∩B. So δ ∉ A and as R(\overline{μ} ↾ A) is ω_{1} \A complete, there is no problem in finding a condition that is M_{i}-generic for every i. The poset P (\overline{η}, c). Let \overline{η} be a guessing ladder over a stationary co-stationary set S, such that

S ∩ range(\overline{η}) is non-stationary.

(See Definition 2.1 for range(\overline{η}). Then, for any club set c ⊆ ω_{1}, the poset P (\overline{η}, c) introduces a generic club set D ⊂ ω_{1}, such that for every δ ∈ D ∩ S, [η_{δ}] ⊂^{∗} c. This may be viewed as forcing a club subset to the stationary set {δ ∈ S | [η_{δ}] ⊆^{∗} c} ∪ (ω_{1} \ S).

Accordingly, we define d ∈ P (\overline{η}, c) iff d ⊆ ω_{1} is countable, closed (with max(d) ∈ d), and for every δ ∈ d ∩ S, [η_{δ}] ⊆^{∗} c.

The order is end-extension.

It is easy to check that any condition has extensions to arbitrary heights (as there are no restrictions on ω_{1} \ S). The cardinality of P (\overline{η}, c) is the continuum.

P (\overline{η}, c) is not necessarily proper, because if, for δ = M ∩ ω_{1}, [η_{δ}] ⊈^{∗} c, then no M-generic condition can be found. Still, P (\overline{η}, c) possesses two good properties which allows its usage:

1. P (\overline{η}, c) is (ω_{1} \ S)-complete (the proof of this is obvious).

2. P (\overline{η}, c) is (E\overline{η}, ω)-proper. (E\overline{η} is stationary since \overline{η} is guessing.)

We check the second property — it is for its sake that the requirement that dom(\overline{η}) ∩ range(\overline{η}) is non-stationary was made. So let ⟨M_{i} | i < ω⟩ be an increasing sequence of countable elementary submodels of H_{λ}, with M_{i} ∈ M_{i+1}, and such that P (\overline{η}, c), \overline{η}, c ∈ M_{0}. Denote δ_{i} = M_{i} ∩ ω_{1}, and δ = sup{δ_{i} | i < ω}.

The assumption is that ⟨δ_{i} | i < ω⟩ ∈ E\overline{η}, and the desired conclusion is that any p_{0} ∈ P ∩ M_{0} can be extended to a condition that is generic for every M_{i}. So the assumption is that δ ∈ S and ⟨δ_{i} | i < ω⟩ is an end segment of η_{δ}. Since dom(\overline{η}) ∩ range(\overline{η}) is non-stationary, δ_{i} ∉ S (becauseM_{0} contains a club that is disjoint from this intersection), and it is easy to find (in M_{i+1}) an M_{i}-generic condition extending any given condition (using the (ω_{1} \ S)-completeness). Thus, given p_{0} ∈ P (\overline{η}, c) ∩ M_{0}, we may construct an increasing sequence of conditions p_{i} ∈ M_{i}, such that p_{i+1} is M_{i}-generic. Then p = \{δ\} ∪ ⋃_{i<ω} p_{i} is in P (\overline{η}, c) because [η_{δ}] ⊆^{∗} c follows from the fact that δ_{i} ∈ c for every i (as c ∈ M_{i}).

As a warm-up we shall present some simple models obtained by countable support iteration of the posets R(\overline{μ}) and P (\overline{η}, c) just described. We assume 2^{ℵ_{0}} = ℵ_{1} and 2^{ℵ_{1}} = ℵ_{2} in the ground model.

1. A model in which MA+2^{ℵ_{0}} = ℵ_{2} +ω_{1} is avoidable. This is achieved by iterating c.c.c posets to obtain Martin’s Axiom, and posets of the form R(\overline{μ}) (varying over all possible ladders \overline{μ} over ω_{1}). Countable support is used in this iteration of proper forcing posets, and hence the final poset is proper. The final poset satisfies the ℵ_{2}-chain condition (see [6], Chapter VIII, or [1]). The length of the iteration is ω_{2} so that each possible c.c.c poset of size ℵ_{1} and each ladder \overline{μ} are taken care of at some stage.

2. Given a guessing ladder \overline{η} such that dom(\overline{η}) ∩ range(\overline{η}) = ∅ a model of MA + 2^{ℵ_{0}} = ℵ_{2} can be obtained in which \overline{η} is strongly guessing. This time posets of type P (\overline{η}, c) are iterated (varying club sets c ⊆ ω_{1}) as well as c.c.c. posets. The iteration is with countable support and of length ω_{2} as before. Put S = dom(\overline{η}). Then S is stationary (as \overline{η} is guessing) and co-stationary (as S ∩ range(\overline{η}) = ∅). Since each poset P (\overline{η}, c) is ω_{1} \ S complete, and each c.c.c. poset is obviously ω_{1} \ S proper, we have here an iteration of ω_{1} \ S proper posets. Thus the final poset itself is ω_{1} \ S proper and ω_{1} is not collapsed. Moreover, since the iterands (both P (\overline{η}, c) and the c.c.c. posets) are E\overline{η} proper, the final iteration is E\overline{η} proper. Hence \overline{η} remains guessing at each stage and in the final extension. It is strongly guessing since we took explicit steps to ensure this.

3. Now we want to combine 1 and 2. We are given a guessing ladder system \overline{η} defined over a stationary co-stationary set T, such that T ∩range(\overline{η}) = ∅, and we want a generic extension in which \overline{η} is maximal for ω_{1}. For the iteration, decompose ω_{2} into three sets ω_{2} = J ∪K ∪I of cardinality ℵ_{2} each. At stage α < ω_{2} of the iteration, supposing that P_{α} has been defined, define the poset Q_{α} in V^{P_{α}} as follows:

(a) If α ∈ J, then Q_{α} is a c.c.c poset, and the iteration of all posets along J guarantees Martin’s Axiom.

(b) For α ∈ K, Q_{α} will be of type R(\overline{μ}) where \overline{μ} ∈ V^{P_{α}} is a ladder system disjoint from \overline{η}. R(\overline{μ}) is proper and it is (D\overline{μ}, ω) proper. Hence as E\overline{η} ⊆ D\overline{μ}, R(\overline{μ}) is E\overline{η} proper.

(c) For α ∈ I, Q_{α} will be of type P (\overline{η}, c) where c is a club set in V^{P_{α}}. These posets are ω_{2} \ T complete, and E\overline{η} proper.

Any of the posets along the iteration is either proper or ω_{2} \ T proper (namely, the P (\overline{η}, c) posets which are ω_{2} \T complete). So the iteration itself is ω_{1} \ T proper, and thus ω_{1} is not collapsed. Moreover, the posets are E\overline{η} proper, and hence \overline{η} retains its guessing property in the extension.

3.3 The iteration scheme

Recall that our aim is to prove the following theorem.

Theorem 3.7 Assume 2^{ℵ_{0}} = ℵ_{1} and 2^{ℵ_{1}} = ℵ_{2}. Suppose

(1) A sequence \overline{T} = ⟨T_{i} | i ∈ ω_{2}⟩ of pairwise almost disjoint stationary subsets of ω_{1}. (Almost disjoint in the sense that T_{i} ∩T_{j} is non-stationary.)

(2) A ladder system \overline{η} such that

1. ⋃\{T_{i} | i ∈ ω_{2}\} ⊆ dom(\overline{η}), and ω_{1} \ dom(\overline{η}) is stationary.

2. For every i, \overline{η} ↾ T_{i} is club guessing.

3. dom(\overline{η})∩ range(\overline{η}) = ∅.

Then there is cofinality preserving generic extension in which A′(\overline{T} , \overline{η}) and MA + 2^{ℵ_{0}} = ℵ_{2} hold. (The definition of A′(\overline{T} , \overline{η}) is immediately after Definition 2.5.)

Proof. It is not difficult to get \overline{T} and \overline{η} as in the theorem, and the following section contains a generic construction of such objects. Here we just assume their existence and prove the theorem. The generic extension is made via P = P_{ω_{2}}, obtained as an iteration, ⟨P_{α} | α ≤ ω_{2}⟩, with countable support of posets of cardinality ℵ_{1}. At successor stages, P_{α+1} ≅ P_{α} ∗ Q_{α}, where Q_{α} ∈ V^{P_{α}} is one of the following three types.

(1) A c.c.c. poset. (To finally obtain Martin’s Axiom.)

(2) A P (\overline{σ}, c) poset, where \overline{σ} ∈ V^{P_{α}} is a guessing ladder such that \overline{σ} ⊲ \overline{η}, and c ∈ V^{P_{α}} is a club set. Recall that P (\overline{σ}, c) introduces a generic club subset D such that δ ∈ D ∩ dom(\overline{σ}) implies σ_{δ} ⊆^{∗} c. We have checked that this poset is (ω_{1}\ dom(\overline{σ}))-complete, and (E\overline{σ}, ω)-proper (as dom(\overline{η}) ∩ range(\overline{η}) = ∅).

(3) The third type of iterated posets is R(\overline{μ}) where \overline{μ} ∈ V^{P_{α}} is a ladder system. This forcing makes \overline{μ} avoidable. We have seen that R(\overline{μ}) is proper, (D\overline{μ}, ω)-proper, and (ω_{1} \ dom(\overline{μ}))-complete.

Each iterated poset Q_{α} is (ω_{1}\dom(\overline{η})) proper in V^{P_{α}}. Hence the iteration itself is (ω_{1} \ dom(\overline{η})) proper, and it satisfies the α_{2}-c.c.

We must specify how to choose the posets Q_{α} for the iteration. Every P_{α} will have cardinality ≤ ℵ_{2} and will satisfy the ℵ_{2}-c.c. When we say that a name in V^{P_{α}} satisfies property ϕ, we mean that it is forced by every condition in P_{α} to satisfy ϕ. We say that a V^{P_{α}} name of a subset of ω_{1} is standard iff it associates with every β ∈ ω_{1} a maximal antichain of conditions that decide whether β is in this subset or not. Every subset of ω_{1} in V^{P_{α}} has (an equivalent) standard name. For every poset P of size ℵ_{2} that satisfies the ℵ_{2}-c.c., Fix an enumeration {E(P, γ) | γ < ω_{2}} of all standard names in V^{P} of subsets of ω_{1} and of ladder systems. Thus any ladder or subset of ω_{1} in V^{P_{α}} has a name of the form E(P_{α}, γ) for some γ < ω_{2}. Fix a natural well-ordering of the pairs {⟨α, γ⟩ | α, γ < ω_{2}} that has order-type ω_{2}. So each ⟨α, γ⟩ has its “place” in ω_{2}. This will serve in the choice of Q_{α}.

To define the iteration, we partition ω_{2} (in V):

ω_{2} = J ∪ K ∪ L ∪ ⋃{I_{i} | i < ω_{2}},

where each set in this partition has cardinality ℵ_{2}. The type of Q_{α} depends on the set in this partition that contains α.

For α ∈ J, Q_{α} is a c.c.c. poset of cardinality ℵ_{1}, and the iteration of these posets in J shall provide Martin’s Axiom. By now this is so standard that no further details will be given.

For α ∈ K, Q_{α} will be of type R(\overline{μ}), where \overline{μ} ∈ V^{P_{α}} is a ladder system disjoint from \overline{η} (namely, \overline{μ} is a name forced by every condition to be a laddersystem disjoint from \overline{η}). The final result of iterating these posets along K is that, every \overline{μ} ∈ V^{P} disjoint from \overline{η} is avoidable in V^{P}. Thus property (A2) of A′(\overline{T} , \overline{η}) can be assured.

Before going on, let’s discuss the problem involved in the direct approach to obtain (A5) and why we do not get A(\overline{T} , \overline{η}) but rather A′(\overline{T} , \overline{η}) (namely A(\overline{S}, \overline{η}) where S_{i} ⊆ T_{i}). A possible approach to (A5) is to consider each possible ladder \overline{ρ} ⊲ \overline{η} such that X = dom(\overline{ρ}) is not \overline{T} -small, and to find for this \overline{ρ} some i ∈ ω_{2} such that X ∩ T_{i} is stationary. Then, if possible, to transform \overline{ρ} ↾ X ∩ T_{i} into a maximally guessing ladder. For this to have any chance, it must be the case that \overline{ρ} ↾ T_{i} is guessing. Yet it is possible that \overline{ρ} ↾ T_{i} is non-guessing for every i. In this case we must shrink the T_{i}’s so as to make X \overline{S}-small. This shows the need for defining subsets S_{i} ⊆ T_{i}. But now (A4) causes a problem because, if X ⊆ ω_{1} is such that in V^{P} X ∩ S_{i} is non-stationary for every i < ω_{2}, then we must be able to identify this X at some intermediary stage of the iteration so as to make \overline{η} ↾ X avoidable. Yet, as the S_{i} are not yet all defined in any intermediate stage, it is not clear how to identify these X’s.

We describe now in general terms how the sets I_{i} from the partition will be used in the iteration. For every i < ω_{2} let α(i) be the first ordinal in I_{i}. A stationary subset S_{i} ⊆ T_{i} and a guessing ladder \overline{σ}^{i} over S_{i} will be defined in V^{P_{α(i)}}. The iteration of the posets Q_{α} for α ∈ I_{i} will make \overline{σ}^{i} maximal for T_{i}, and will achieve (A3) by establishing χ(T_{i}) = \overline{σ}^{i}. Finally, in V^{P}, A(\overline{S}, \overline{η}) will hold for \overline{S} = ⟨S_{i} | i ∈ ω_{2}⟩.

To define S_{i} and \overline{σ}^{i} we assume a function, ρ, which assigns to any α of the form α = α(i) a name ρ(α) ∈ V^{P_{α}} that is one of the following.

1. If i is an even ordinal then ρ(α(i)) is a name of a real in V^{P_{α}}. The complete definition of ρ is given in the following section where it is used to define the encoding of the well-ordering of reals. Here we only assume that ρ(α) is defined.

2. If i is an odd ordinal, then ρ(α(i)) is determined as a name of the ladder system ρ(α), defined as follows in V^{P_{α}}. With respect to the well-ordering of names in V^{P_{α}}, ρ(α) is the least ladder \overline{ρ} ⊲ \overline{η} that is not of the form ρ(α′) for α′ < α, and is such that for D = dom(\overline{ρ})

\overline{η} ↾ D ∩ T_{i} is guessing.

Suppose that α = α(i). Instead of defining the names S_{i} and Q_{α} directly in V^{P_{α}}, we let G ⊆ P_{α} be V -generic and we shall describe the interpretations of S_{i} and Q_{α}. We will later see (Lemma 3.9) that \overline{η} ↾ T_{i} remains guessing in V [G]. In V [G], collect all sets X ⊆ ω_{1} such that

1. a standard name of X appeared before α in the well-ordering of the names (i.e., for some α′ ≤ α and γ < ω_{2}, ⟨α′, γ⟩ is placed before α in the well-ordering of ω_{2} ×ω_{2}, and E(P_{α′}, γ), the γth name in V^{P_{α′}}, gives X), and

2. X is such that \overline{η} ↾ (T_{i} ∩ X) is not guessing (i.e., T_{i} ∩ X ∈ I\overline{η}).

Let ⟨X_{ξ} | ξ < ω_{1}⟩ be an enumeration of these sets. Take their diagonal union

A = ∇_{ξ∈ω_{1}}(X_{ξ} ∩ T_{i}).  (4)

Then A ∈ I\overline{η}. Since \overline{η} ↾ T_{i} is guessing in V [G], T′_{i} = T_{i} \ A ∉ I\overline{η} (that is, \overline{η} ↾ T′_{i} is guessing). (The reason for this specific definition of A and T′_{i} will only be apparent in the proof of item (A5) in V^{P}.)

Now ρ(α) is either a real or a ladder system in V [G]. Accordingly the definition of S_{i} and \overline{σ}^{i} is split in two. Suppose that ρ(α) is a real r ⊆ ω in V [G]. We want to encode r. Define S_{i} = T′_{i}, and let \overline{σ}^{i} ⊲ \overline{η} ↾ S_{i} be a ladder system over S_{i} such that

d(\overline{σ}^{i}, \overline{η} ↾ S_{i}) = r.

Since \overline{η} ↾ S_{i} is guessing and \overline{σ}^{i} ⊲ \overline{η} ↾ S_{i} has domain S_{i}, \overline{σ}^{i} is also guessing.

Suppose next that α = α(i) for i an odd ordinal and \overline{ρ} = ρ(α) is (in V [G]) a ladder over X = dom(\overline{ρ}) (such that \overline{ρ}⊲\overline{η}, and \overline{η} ↾ X ∩T_{i} is guessing). Then \overline{η} ↾ X ∩ T′_{i} is guessing, because T_{i} \ T′_{i} ∈ I\overline{η}. It follows that \overline{ρ} ↾ X ∩ T′_{i} is guessing as well, because \overline{ρ} ⊲ \overline{η} and X ∩ T′_{i} ⊆ dom(\overline{ρ}). In this case define

S_{i} = X ∩ T′_{i},

and define

\overline{σ}^{i} ⊲ \overline{ρ} ↾ S_{i} so that (\overline{σ}^{i}, \overline{η} ↾ S_{i}) is clearly not encoding.

The iteration along I_{i} builds up the properties of \overline{σ}^{i} and establishes χ(T_{i}) = \overline{σ}^{i} in V^{P}. For this, the posets Q_{ξ}, for ξ ∈ I_{i}, are of two types:

(1) P (\overline{σ}^{i}, c), where c “runs” over all possible clubs. This ensures that \overline{σ}^{i} becomes strongly club guessing in V^{P}. To enable the use of P (\overline{σ}^{i}, c) we rely on the assumption, proved later to hold, that \overline{σ}^{i} remains club guessing at each stage.

(2) R(\overline{μ}), where \overline{μ} “runs” over all possible ladders over S_{i} that are disjoint from \overline{σ}^{i}. This ensures the maximality of \overline{σ}^{i}.

To satisfy item (A4) (in the definition of A(\overline{S}, \overline{η})), every X must be made avoidable whenever all the intersections X ∩S_{i} are non-stationary. It suffices to show in such a case that the ladder \overline{η} ↾ X is avoidable to conclude that X is avoidable, because any ladder disjoint from \overline{η} is necessarily avoidable in V^{P}. It is the iteration along L that achieves this, by forcing with posets of type R(\overline{η} ↾ X) as follows.

Given ζ ∈ L and a generic filter G ⊆ P_{ζ}, we will define Q_{ζ} in V [G]. For i < ω_{2} such that α(i) < ζ, the sets S_{i} have been defined. For every i < ω_{2} define

S_{i}^{∗} = \{ \begin{matrix}S_{i} & if α(i) < ζ \\ T_{i} & otherwise \end{matrix}

Using the well-ordering of standard names, take the least set X ⊆ ω_{1} (if there is one) that was not taken before at a stage in L, such that

∀i < ω_{2} \overline{η} ↾ X ∩ S_{i}^{∗} is not guessing.  (5)

Then define Q_{ζ} to be R(\overline{η} ↾ X) (or a trivial poset if no such X exists).

This ends the definition of the iteration, but it is not yet clear why items (A4) and (A5) hold in V^{P}. To prove (A4) we shall first prove that if

(∀i < ω_{2})X ∩ S_{i} is non-stationary in V^{P} ,

then (5) holds at some stage V^{P_{ξ}}, ξ ∈ L, and hence \overline{η} ↾ X is avoidable in the next step of the iteration. To see that this is indeed the case, we need the following pivotal observation.

Lemma 3.8 Suppose G ⊆ P_{ω_{2}} is V -generic. If γ < ω_{2} and \overline{ρ} ∈ V [G ↾ γ] is a ladder over X such that, in V [G ↾ γ] \overline{ρ} ⊲ \overline{η} and

|\{i ∈ ω_{2} | \overline{η} ↾ X ∩ T_{i} is guessing\}| = ℵ_{2}.  (6)

Then there is i such that S_{i} ⊆ X ∩ T_{i} and \overline{σ}^{i} ⊲ \overline{ρ}.

Proof. The proof of this lemma depends on the fact that for any i (with α(i) ≥ γ) such that \overline{η} ↾ X ∩ T_{i} is guessing in V [G ↾ γ], \overline{η} ↾ X ∩ T_{i} remains guessing in V [G ↾ α(i)] as well. Thus, as the turn of \overline{ρ} cannot be delayed ω_{2} many times, at some stage α = α(i), \overline{ρ} = ρ(α) holds, and then S_{i} = X ∩ T′_{i} and \overline{σ}^{i} ⊲ \overline{ρ} ↾ S_{i} were defined in V [G ↾ α].

Now we can prove item (A4) in V [G]. For this, let X ⊆ ω_{1} be such that (∀i < ω_{2}) X ∩ S_{i} is non-stationary. We will show that, at some stage ζ ∈ L, the poset R(\overline{η} ↾ X) was taken as Q_{ζ}. If, for some γ < ω_{2}, (6) of Lemma 3.8 holds in V [G ↾ γ], then S_{i} ⊆ X contradicts the fact that S_{i} is stationary. Hence formula (6) never holds, and for γ such that X ∈ V [G ↾ γ] there are only boundedly many js for which \overline{η} ↾ X ∩ T_{j} is guessing. So let γ < j_{0} < ω_{2} be such that if \overline{η} ↾ X ∩ T_{j} is guessing, then j < j_{0}. Since, in V [G], X ∩ S_{j} is non-stationary for every j < ω_{2}, there is a stage j_{1} such that for every j < j_{0}, X ∩ S_{j} is non-stationary in V [G ↾ j_{1}]. Thus, for ζ ≥ j_{1}, in V [G ↾ ζ], for every i < ω_{2}, if i < j_{0} then S_{i} is defined (that is, α(i) ≤ ζ) and X ∩ S_{i} is non-stationary, and hence \overline{η} ↾ X ∩ S_{i} is non-guessing, and if i ≥ j_{0}, then \overline{η} ↾ X ∩T_{i} is non-guessing. But this is exactly the condition required at stages ζ ∈ L to force with R(\overline{η} ↾ X).

Finally, we turn to prove item (A5). So let \overline{ρ} ⊲ \overline{η} with X = dom(\overline{ρ}) be given in the generic extension V [G]. Then for some γ < ω_{2}, \overline{ρ} ∈ V [G ↾ γ], and a name of X appeared before γ in the well-ordering of names.

Case 1: In V [G ↾ γ]: There is i_{0} < ω_{2} such that, for every i ≥ i_{0}, α(i) > γ and

\overline{η} ↾ X ∩ T_{i} is not guessing.

Then, in defining S_{i} for i ≥ i_{0}, α(i) > γ, and the set X appears as some X_{ξ} (in equation (4)), and hence X ∩ S_{i} is at most countable (it is included in ξ + 1). Thus, in Case 1, X ∩ S_{i} is non-stationary (and even countable) for a co-bounded set of indices. That is, X is \overline{S}-small. (It is for this argument that, in defining S_{i}, we asked S_{i} ∩ A = ∅)

Case 2: Not Case 1. Hence (6) holds in V [G ↾ γ]. So, by Lemma 3.8 there is i such that S_{i} ⊆ X ∩ T_{i} and \overline{σ}^{i} ⊲ \overline{ρ}, which establishes (A5).

Our proof relied on preservation claims that some ladders retain their guessing property, and we intend now to prove these claims. First, set T = ∪T_{i}. Then ω_{1} \ T is stationary by assumption, and all the posets used are (ω_{1} \ T)-proper. (The c.c.c. posets are certainly proper. The P (\overline{σ}, c) posets (defined for \overline{σ} ⊲ \overline{η}) are (ω_{1} \ dom(\overline{σ}))-complete, and hence (ω_{1} \ T)-proper. The R(\overline{μ}) posets are proper.) This secures the preservation of ℵ_{1}.

Lemma 3.9 \overline{η} ↾ T_{i} remains guessing in V^{P_{α}} for α = α(i).

Proof. This follows from the fact that the posets iterated at stages ζ < α are all (E_{\overline{η}↾T_{i}}, ω)-proper:

1. The c.c.c. posets are always ω-proper.

2. The R(\overline{μ}) posets iterated at stages in K are defined for \overline{μ}’s that are disjoint from \overline{η}. In such a case E\overline{η} ⊆ D\overline{μ}. But we remarked that R(\overline{μ}) is (D\overline{μ}, ω)-proper.

3. The P (\overline{σ}, c) posets introduced for ζ < α are defined along I_{j} only for js such that α(j) < α, and thence for \overline{σ}’s such that \overline{σ} ⊲ \overline{η} ↾ T_{j}, implying the (E_{\overline{η}↾T_{i}}, ω)-properness. (Since T_{j} ∩ T_{i} is non-stationary, and range(\overline{η}) ∩ T_{j} = ∅.)

4. The R(\overline{μ}) posets defined along I_{j} for α(j) < α are defined for ladders \overline{μ} over T_{j}. As T_{j} is almost disjoint from T_{i}, these R(\overline{μ})’s are (E_{\overline{η}↾T_{i}}, ω)- proper.

5. The R(\overline{η} ↾ X) posets defined for ζ ∈ L, ζ < α, are such that \overline{η} ↾ X ∩ T_{i} is non-guessing and the poset is thence (E_{\overline{η}↾T_{i}}, ω)-proper (by Lemma 3.6).

Then, we must also show that the guessing ladder \overline{σ}^{i} ⊲ \overline{η} ↾ S_{i} defined in V^{P_{α(i)}} remains guessing at every stage in I_{i} (and thus the posets P (\overline{σ}^{i}, c) can be applied). This is basically the same proof, done in V^{P_{α(i)}} for the quotient poset P/P_{α(i)} which is again a countable support iteration of posets as above that are E\overline{σ}^{i} proper.

4 The Σ^{2[ℵ_{1}]} well-ordering

The main theorem, Theorem 1.1, is proved in this section. So 2^{ℵ_{0}} = ℵ_{1} and 2^{ℵ_{1}} = ℵ_{2} are assumed in the ground model V. We need a sequence \overline{T} of pairwise almost disjoint stationary sets, and a guessing ladder system \overline{η}; and we are going to define them first.

Since we want to describe the ℵ_{2} stationary sets in the language Σ^{2[ℵ_{1}]}, we need a compact form of generation for such sets. This is provided by the following definition.

Definition 4.1 Let ^{≤α}{0, 1} denote the set of all functions f : β → {0, 1} for β ≤ α. Ordered by function extension, this forms a tree. Define ^{<α}{0, 1} similarly.

A stationarity tree is a subtree T ⊆ ^{<ω_{1}}{0, 1} of cardinality ℵ_{1} such that:

1. If f, g ∈ T and α are such that f ↾ α = g ↾ α but f(α) ≠ g(α), then f^{−1}{1} ∩ g^{−1}{1} ⊆ α.

2. T has ℵ_{2} branches of length ω_{1} and each gives a stationary set (that is, the union of the nodes along any ω_{1}-branch forms a function f and f^{−1}{1} is a stationary subset of ω_{1}). It follows from item 1 that the intersection of any pair of these stationary sets is countable. Thus the branches of T give ℵ_{2} pairwise disjoint stationary sets enumerated as T_{i} for i < ω_{2}.

3. We also require that U = ∪_{i<ω_{2}} T_{i} is a co-stationary set.

The poset S, defined below, will produce a stationarity tree by forcing.

Conditions in S will be countable trees, together with countable information on the family of branches. Define p ∈ S iff p = (T_{p}, f_{p}) where:

1. For some countable ordinal β (called the “height” of p) T_{p} ⊆ ^{≤β}{0, 1} is a countable tree of functions ordered by inclusion, and satisfying property 1, and such that T_{p} ∩ ^{β}{0, 1} ≠ ∅.

2. f_{p} is a countable (partial) map defined on ω_{2} that assigns to ζ in its domain a node f_{p}(ζ) ∈ T_{p} ∩ ^{β}{0, 1}. (dom(f_{p}) is called the “domain” of p.)

The extension relation p_{2} ≥ p_{1} on S is defined by requiring that T_{p_{1}} = T_{p_{2}} ∩ ^{≤α_{1}}{0, 1} where α_{1} = height (T_{p_{1}}), and that f_{p_{2}}(ζ) extends f_{p_{1}}(ζ) for every ζ ∈ dom(f_{p_{1}}).

If p_{1}, p_{2} ∈ S are such that T_{p_{1}} = T_{p_{2}}, and f_{p_{1}} agrees with f_{p_{2}} on the intersection of the domains, then p_{1} and p_{2} are compatible. Hence, CH implies the ℵ_{2}-c.c. for S.

It is not difficult to prove that every condition has arbitrarily high extensions, and that for every ξ ∈ ω_{2} the set of conditions p with ξ ∈ dom(f_{p}) is dense in S. Clearly, S is countably closed. If ⟨p_{n} | n ∈ ω⟩ is an increasing sequence of conditions, let p = sup{p_{n} | n < ω} be defined as follows. T_{p} = ⋃{T_{p_{n}} | n ∈ ω} ∪ {f_{p}(ξ) | ξ ∈ dom(f_{p_{n}}) for some n ∈ ω} where f_{p}(ξ) = ⋃{f_{p_{n}}(ξ) | n ∈ ω & ξ ∈ dom(p_{n})}. That is, if α is the height of p, then T_{p} ∩ ^{α}{0, 1} consists only of the functions f_{p}(ξ) for ξ ∈ dom(p). If G ⊆ S is V -generic, define T = T (G) = ⋃{T_{p} | p ∈ G}. Then T is a stationarity tree. Define f(ζ) = ⋃{f_{p}(ζ) | p ∈ G}. Then f(ζ) is an ω_{1}-branch of T, and for ζ_{1} ≠ ζ_{2} f(ζ_{1}) ≠ f(ζ_{2}). Thus T has ℵ_{2} many ω_{1}-branches. The fact that every f(ξ) gives a stationary set requires a simple density argument. We will check now the following:

Claim 4.2 Any ω_{1}-branch of T in V [G] is some f(ζ).

Proof: Suppose, toward a contradiction, that p forces that τ is a branch of T which is not f(ζ) for any ζ ∈ ω_{2}. Observe first that since S is σ-closed, any condition p can be extended to a condition q that describes τ up to height(p). Then, every condition p and ξ ∈ dom(p) have an extension q such that f_{q}(ζ) diverges from the value of τ determined by q. Repeating this procedure ω^{2} times, we finally get an extension q of p with δ = height(q) limit, and such that q determines τ as a branch of T_{q} of height δ which is different from each of the branches f_{q}(ζ). Since T_{q} ∩ ^{δ}{0, 1} consists only of the branches of the form f_{q}(ξ), the branch of τ is not in T_{q}. Then q forces τ ⊆ T ↾ δ.

We denote with \overline{T} = ⟨T_{i} | i < ω_{2}⟩ the collection of stationary sets thus obtained from the branches f(ζ) of T. Let U = ∪_{i<ω_{2}}T_{i}.

It is not difficult to show that ω_{1} \ U is also stationary. If C is a name of a closed unbounded subset of ω_{1}, find a countable M ≺ H_{λ} with C ∈ M, and define an M-generic condition p that puts δ = M ∩ ω_{1} in ω_{1} \ U.

Next, we obtain a ladder system \overline{η} over U such that range(\overline{η}) ∩ U = ∅, and \overline{η} ↾ T_{i} is guessing for every i. It is possible to get this \overline{η} by forcing with the natural (countable) conditions. This forcing notion is countably closed, and, assuming CH, it has cardinality ℵ_{1}.

Now comes the main stage of the iteration.

Using the construction of the previous section we obtain an extension in which A′(\overline{T} , \overline{η}) + MA + 2^{ℵ_{0}} = ℵ_{2} hold, and such that for every i < ω_{2} either (\overline{σ}_{i}, \overline{η}) is clearly not encoding (where \overline{σ}_{i} = χ(T_{i}) is the maximal ladder for T_{i}), or else it encodes a real r_{i}, and in that case r_{i} = r_{j} for ℵ_{2} many js (any encoded real is encoded unboundedly often). The set of encoded reals, E = {r_{i} | i < ω_{2}}, is (in some natural encoding of pairs) our wellordering of the reals. We must prove that this well-ordering is Σ^{2[ℵ_{1}]}. After the extension, Claim 4.2 may no longer be true because new branches were added to T. However, the stationary sets T_{i} are Σ^{2[ℵ_{1}]} definable. They are exactly those stationary sets X obtained from a branch of T and such that X is not avoidable (any ω_{1}-branch of T that is not one of the original f(ξ) branches is almost disjoint to any original branch and hence by (A4) its stationary set is avoidable).

We describe the Σ^{2[ℵ_{1}]} formula ψ(x) that decodes this well-ordering (ψ(x) iff x ∈ E). First consider the Σ^{2[ℵ_{1}]} formula φ(T_{0}, \overline{η}_{0})(with class variables T_{0} and \overline{η}_{0}) which says that T_{0} is a stationarity tree, and \overline{η}_{0} is a ladder system such that A′(\overline{T}_{0}, \overline{η}_{0}) holds (where \overline{T}_{0} is the collection of non-avoidable stationary sets derived from the branches of T_{0}). (The statement “there are ℵ_{2} indices such that… ” can be expressed by saying “there is no ℵ_{1}-class containing all the indices such that… ”).

This enables a Σ^{2[ℵ_{1}]} rendering of the formula x ∈ E:

ψ(x) ≡ there exists T^{0} and \overline{η}^{0} such that φ(T^{0}, \overline{η}^{0}) and
x ∈ code(T^{0}, \overline{η}^{0})

Clearly, ψ(x) holds for every x ∈ E (by virtue of the “real” T and \overline{η}), and we must also prove that if ψ(x) then x ∈ E. But this follow from Lemma 2.8.

References

[1] U. Abraham, Proper Forcing, in Foreman, Kanamori, and Magidor, eds, Handbook of Set Theory.

[2] U. Abraham and S. Shelah, A Δ_{2}^{2} well-order of the reals and incompactness of L(Q^{MM}). Annals of Pure and Applied Logic 59 (1993) 1-32.

[3] U. Abraham and S. Shelah, Martin’s Axiom and Δ_{1}^{2} well-ordering of the reals. Archive for Mathematical Logic (1996) 35, 287–298.

[4] L. Harrington, Long projective well-orderings. Annals of Mathematical Logic, 12 (1977), 1–24.

[5] R. B. Jensen and R. M. Solovay, Some applications of almost disjoint sets, in: Y. Bar-Hillel, ed., Mathematical Logic and Foundation of Set Theory (North-Holland, Amsterdam, 1970) 84-104.

[6] S. Shelah, Proper and improper forcing, 2nd edition, Springer 1998.

[7] S. Shelah and H. Woodin, Large cardinal imply that every reasonably definable set of reals is Lebesgue measurable, Israel J. Math. 70 (1990) 381-394.

[8] R. M. Solovay, a paper to be published in the Archive.

[9] H. Woodin, Large Cardinals and Determinacy, in preparation.