ABSOLUTENESS FOR UNIVERSALLY BAIRE SETS AND THE UNCOUNTABLE II

ILIJAS FARAH, RICHARD KETCHERSID, PAUL LARSON, AND MENACHEM MAGIDOR

Abstract. Using ♢ and large cardinals we extend results of Magidor–Malitz and Farah–Larson to obtain models correct for the existence of uncountable homogeneous sets for finite-dimensional partitions and universally Baire sets. Furthermore, we show that the constructions in this paper and its predecessor can be modified to produce a family of 2^{ω_{1}}-many such models so that no two have a stationary, costationary subset of ω_{1} in common. Finally, we extend a result of Steel to show that trees on reals of height ω_{1} which are coded by universally Baire sets have either an uncountable path or an absolute impediment preventing one.

In [3] it was shown (using large cardinals) that if a model of a theory T satisfying a certain second-order property P can be forced to exist, then a model of T satisfying P exists already. The properties P considered in [3] included the following.

(1) Containing any specified set of ℵ_{1}-many reals.

(2) Correctness about NS_{ω_{1}}.

(3) Correctness about any given universally Baire set of reals (with a predicate

for this set added to the language). In this paper we add the following properties, all proved under the assumption of Jensen’s ♢ principle.

(4) Correctness about Magidor–Malitz quantifiers (and even about the existence of uncountable homogeneous sets for subsets of [ω_{1}]^{<ω} and any [κ]^{<ω}).

(5) Correctness about the countable chain condition for partial orders.

(6) Correctness about uncountable chains through (some) trees of height and cardinality ω_{1}.

(7) Containing a function on ω_{1} dominating any such given function on a club. These results are obtained using two main tools (both due to Woodin):

(a) iterable models (also called ℙ_{max}-preconditions), introduced in [21],

(b) stationary-tower forcing ([11]), or more specifically, Woodin’s proof of Σ_{1}^{2}-

2 ILIJAS FARAH, RICHARD KETCHERSID, PAUL LARSON, AND MENACHEM MAGIDOR

absoluteness ([20]) . While (b) requires higher large cardinal strength than (a), it allows one to assure (1). Aside from (1) and (7), we can obtain all of these properties simultaneously using the method (a) (with “some” being “all” for (5) and (6)). Aside from (1) and (4) we can prove all of these properties simultaneously using the method (b). Property (4) subsumes the next two properties in the list, but we do not see how to obtain it by stationary tower constructions. As a matter of fact, simultaneously obtaining (1) and (4), and even (1) and (6), would imply Σ_{2}^{2}-absoluteness conditioned on ♢ (see Theorem 3.7). That ♢ implies that one can iterate a ℙ_{max} pre-condition to be correct about the countable chain condition for partial orders on ω_{1} is due to Larson and Yorioka [13].

Date: December 21, 2005.

The first author is partially supported by NSERC. The third author was supported in part by NSF grant DMS-0401603, and part of his research was conducted at the Institute for Mathematical Sciences at the National University of Singapore, under the partial support of a summer research grant from Miami University.

In the fourth section we show abstractly that these arguments can be modified to build a family of 2^{ω_{1}} many models, no two having a stationary-costationary subset of ω_{1} in common. In the final section we prove a generalized version of a theorem of Steel which can be used to show that the existence of a model of a given sentence which is correct about a given universally Baire set is absolute, given a proper class of Woodin cardinals.

1. Magidor–Malitz logic

The language L(Q^{<ω}) is formed by adding to the language of set theory quantifiers Q^{n} for each n in ω. In this paper we restrict our attention to the so-called ω_{1}-interpretation of this language. That is, a formula of the form

Q^{n}x_{1}, x_{2}, …, x_{n}ϕ(x_{1}, …, x_{n})

is interpreted as saying that there is an uncountable subset of ω_{1} such that every n-tuple from this set satisfies ϕ. The expressive power of this language is not diminished by requiring ϕ to be symmetric, i.e., invariant under permuting its free variables x_{1}, …, x_{n}. Recall that [Z]^{n} is the set of all n-element subsets of Z and [Z]^{<ω} is the set of all finite subsets of Z. For K ⊆ [ω_{1}]^{n} an X ⊆ ω_{1} is K-homogeneous if and only if [X]^{n} ⊆ K. Since an interpretation of a symmetric formula is a subset of [ω_{1}]^{n}, correctness for Magidor–Malitz logic is equivalent to correctness for the existence of uncountable homogeneous sets (note that the existence of countable homogeneous sets of any given order type is absolute between transitive models.) We therefore say that a model M is correct for Magidor–Malitz logic (or for Ramsey quantifiers) if ω_{1}^{M} is uncountable and, for every n ∈ ω and every K ⊂ ([ω_{1}]^{n})^{M} definable in M from parameters in M (note that we do not assume here that M satisfies ZFC), K has an uncountable homogeneous set if and only if one exists in M. The following theorem was proved in [14].

Theorem 1.1 (♢). If T is a theory in the language L(Q^{<ω}) and it is consistent with ZFC that T has a model which is correct for Magidor–Malitz logic, then T has such a model. □

Requiring T from Theorem 1.1 to contain a large enough fragment of ZFC is not a loss of generality. Here (and throughout this paper) “large enough fragment of ZFC” means large enough to make ultrapower embeddings for generic ultrafilters on ω_{1} elementary; the theory ZFC^{∘} from [12] suffices. In this case Theorem 1.1 can be equivalently reformulated as follows:

Theorem 1.2 (♢). If a theory T extends a large enough fragment of ZFC and it is consistent, then ♢ implies the existence of a model M for T such that ω_{1}^{M} is uncountable and M is correct about the existence of homogeneous sets for partitions of [ω_{1}^{M}]^{n} for all n ∈ ℕ. □

The model M guaranteed by this result is not necessarily well-founded; asserting well-foundedness of M requires some large cardinal strength (this follows from [3, Proposition 7.10]). A model M of a large enough fragment of ZFC is correct for partitions of finite sets if it is correct about the existence of uncountable homogeneous sets for partitions K ⊆ [ω_{1}]^{<ω} in M. Our first result is a strengthening of Theorem 1.2 (see Proposition 2.8).

Theorem 1.3 (♢). If a theory T extends a large enough fragment of ZFC and it is consistent, then ♢ implies the existence of an model M for T such that ω_{1}^{M} is uncountable and M is correct about the existence of homogeneous sets for partitions of [ω_{1}^{M}]^{n} that belong to M, for each n ∈ ω. If T is ω-consistent, then then ♢ implies the existence of an model M for T such that ω_{1}^{M} is uncountable and M is correct about the existence of homogeneous sets for partitions of [ω_{1}^{M}]^{<ω} that belong to M,

The proof is given in Theorem 1.12 at the end of this section. We show that in the presence of large cardinals, correctness for partitions of finite sets can be combined with correctness for any given universally Baire set of reals, with respect to the logic of forceability.

Analogously to [3, §5], given a set of reals A let L(A) be the language of set theory with an additional unary predicate for A. We say that a model M is correct for A and partitions of [ω_{1}]^{<ω} (in short, L(Q^{ω}, A)-correct) if ω_{1}^{M} = ω_{1}, M interprets the additional unary symbol as A ∩ M and about the existence of uncountable homogeneous sets for every partition K ∈ M of [ω_{1}]^{<ω}. Since correctness for Π_{1}^{1}- sets already implies well-foundedness of ω_{1}^{M}, assuming ω_{1}^{M} = ω_{1} is not a loss of generality in our context. The notation L(Q^{≤ω}, A)-correct is perhaps misleading, but L(Q^{<ω}) is an established notation for Magidor–Malitz logic. The reader may wish to compare the following theorem with the results in [1].

Theorem 1.4. Suppose that there exist proper class many Woodin cardinals, let A be a universally Baire set of reals, and let T be a set of sentences in L(A). Suppose that there exists an L(Q^{ω}, A)-correct model of T in some set forcing extension. Then there exists an L(Q^{ω}, A)-correct model of T in every set forcing extension satisfying ♢.

Proof. Immediate from Lemma 1.5, Lemma 1.6, and Theorem 1.7 below. □

The logic L_{ω_{1}ω}(Q^{<ω}) allows countable disjunctions in addition to quantifiers Q^{n} (n ∈ ℕ). It is well-known that an analogue of Theorem 1.1 for this logic can be proved using the methods of [14]; for a proof see e.g., [4]. By standard methods (see e.g., [2] for the case of L_{ω_{1}ω}(Q)), the case of Theorem 1.4 when A is a Borel set follows. This cannot be extended even to analytic sets unless large cardinals are assumed ([3, Proposition 7.8]). An alternative way for proving these results using iterated generic ultrapowers is outlined in our Theorem 1.3 and Theorem 1.12. Note that this semantical result does not recover the full strength of Keisler or Magidor– Malitz theorems. This is because these results provide completeness theorems for logics L_{ω_{1}ω}(Q) and L_{ω_{1}ω}(Q^{<ω}). We do not know whether this can be achieved for the logic with the quantifier corresponding to the existence of uncountable homogeneous subsets of [ω_{1}]^{<ω}.

1.1. Proofs. The following is proved in [3]. In the presence of a proper class of Woodin cardinals, universally Baire sets of reals are δ^{+}-weakly homogeneously Suslin for all δ. We refer the reader to [21, 12, 3] for the definition of A-iterability.

Lemma 1.5. Assume that δ < λ are a Woodin and a measurable cardinal respectively, A and ω^{ω} \ A are δ^{+}-weakly homogeneously Suslin sets of reals, and ϕ is a sentence whose truth is preserved by σ-closed forcing. If there exists a partial order in V_{δ} that forces that ϕ holds in H(θ) for some θ ≥ (2^{λ})^{+}, then there exists an A-iterable model (N, NS_{ω_{1}}^{N}) that satisfies ϕ.

A forcing ℙ has property K_{n} if for all p_{α} (α < ω_{1}) there is an uncountable I ⊆ ω_{1} such that p_{α(1)}, …, p_{α(n)} has a lower bound for all α(1), …, α(n) in I. It has precaliber ℵ_{1} if for all p_{α} (α < ω_{1}) there is an uncountable I ⊆ ω_{1} such that every finite subset of p_{α} (α ∈ I) has a lower bound. The following is well-known.

Lemma 1.6. Assume K ⊆ [Z]^{<ω}. The statement ‘there are no uncountable Khomogeneous sets’ is absolute for (a) σ-closed forcing extensions (b) precaliber ℵ_{1} forcing extensions. (c) If K ⊆ [Z]^{n} then the statement ‘there are no uncountable K-homogeneous sets’ is absolute for property K_{n} forcing extensions.

Proof. In all three cases forcing preserves ℵ_{1}, and therefore we only need to check that it does not add an uncountable homogeneous set.

(a) Assume ℙ forces the existence of an uncountable homogeneous set, and let Ḣ be its name. Pick decreasing conditions p_{α} (α < ω_{1}) such that p_{α} decides first α elements of Ḣ. Then the decided set is uncountable and K-homogeneous.

(b) If ℙ forces an existence of an uncountable homogeneous set Ḣ, pick p_{α} that decides αth element of Ḣ is ξ_{α}. If every finite subset of {p_{α} | α ∈ I} has a lower bound, then {ξ_{α} | α ∈ I} is homogeneous.

(c) This proof is very similar to the proof of (b). □

Theorem 1.7. If ♢ holds and (M, I) is an iterable pair, then there is an iteration j: (M, I) → (M^{∗}, I^{∗}) of length ω_{1} such that M^{∗} is correct for partitions of [ω_{1}]^{<ω}.

We give two proofs of Theorem 1.7. The first uses the presentation of Magidor– Malitz logic given in [4] and its modularity makes it more susceptible to generalizations. The second is shorter and more straightforward. We note that one can easily add correctness about NS_{ω_{1}} to M^{∗}. On the other hand, the proof can easily be adapted to make M^{∗} incorrect about NS_{ω_{1}}, showing that correctness for Ramsey quantifiers does not imply correctness about NS_{ω_{1}}. To see this, note the the proofs of Theorem 1.7 do not require putting any specific set into the generic filter at a given stage. The standard ℙ_{max} bookkeeping argument then allows putting the images of each stationary subset of ω_{1} in each model of the iteration into the generic filter stationarily often, thus assuring NS_{ω_{1}}-correctness (see the game-theoretic formulation of the basic iteration lemma for ℙ_{max} in [12]). On the other hand, we are free to take some costationary subset of ω_{1} in some model and keep it and its images out of all the generic filters, thus assuring that the image of this set will be nonstationary in V even though it is stationary in the final model. With this observation one gets the following strengthening of Theorem 1.4, where if M is a model of a sufficient fragment of ZFC which is correct about ω_{1} we say that M is correct about NS_{ω_{1}} if NS_{ω_{1}} ∩ M = NS_{ω_{1}}^{M}.

Theorem 1.8. Suppose that there exist proper class many Woodin cardinals, let A be a universally Baire set of reals, and let T be a set of sentences in L(A). Suppose that there exists an L(Q^{ω}, A)-correct model of T in some set forcing extension. Then in every set forcing extension satisfying ♢ there exists an L(Q^{ω}, A)-correct models M, M′ of T such that M is correct about NS_{ω_{1}} and M′ is not.

1.2. First proof of Theorem 1.7. For a transitive model N of ZFC^{∘} let L_{N} be the language of set theory extended by adding the constants for elements of N (and all universally Baire sets and NS_{ω_{1}}). Let (∀^{ℵ_{0}}x ∈ z)ϕ(x) be the shortcut for ‘z is uncountable and ϕ(x) holds for all but countably many x ∈ z.’ For a 1-type Φ in L_{N} let

∂Φ(x) = {(∀^{ℵ_{0}}z ∈ x)ϕ(z) | ϕ(z) ∈ Φ(z)}.

Also let ∂^{∘}Φ = Φ and ∂^{n+1}Φ = ∂(∂^{n}Φ). A type Φ is totally unsupported in N if ∂^{n}Φ is not realized in N for all n ≥ 0.

If j: N → N^{∗} is an elementary embedding and Φ is an N-type then jΦ is a type defined in the natural way:

jΦ(x) = {ϕ(x, j(a⃗)) | ϕ(x, a⃗) ∈ Φ(x)}

(here a⃗ stands for an arbitrary n-tuple of parameters).

Lemma 1.9. Assume (N, I) is an iterable pair and types Φ_{i} (i ≥ 0) are totally unsupported in N. Then there is N-generic G ⊆ I^{+} such that each jΦ_{i} is totally unsupported in N^{∗} for the generic embedding j: N → N^{∗}.

Proof. Let ν = ω_{1}^{N}. Enumerate all pairs (f, ∂^{n}Φ_{i}) for f: ν → ν in N. Pick G recursively, by finding a decreasing sequence A_{k} (k ≥ 0) in I^{+}. Assure that A_{2k} is in k-th dense subset of I^{+} in N. To find A_{2k+1}, consider the k-th pair (f, ∂^{n}Φ_{i}). If there is ϕ ∈ ∂^{n}Φ_{i} such that the set

B_{ϕ} = {α ∈ A_{2k} | N ⊧ ¬ϕ(f(α))}

is stationary then let A_{2k+1} = B_{ϕ}.

We claim that such a ϕ has to exist. Otherwise let D = ∇{B_{ϕ} | B_{ϕ} ∈ NS_{ω_{1}}}. Then D ∈ N and C = A_{2k} \ D is equal to A_{2k} modulo a club. Also, if for every ϕ ∈ ∂^{n}Φ_{i} we have that N ⊧ (∀^{ℵ_{0}}α ∈ C)ϕ(f(α)). We consider two possibilities. First, if C′ = f[C] is uncountable, then C′ realizes ∂^{n+1}Φ_{i}, contradicting our assumption that this type is unsupported in N. Otherwise there is α ∈ N such that f^{−1}(α)∩C is uncountable. Therefore N ⊧ ϕ(α) for all ϕ ∈ ∂^{n}Φ_{i}, contradicting the assumption that ∂^{n}Φ_{i} is unsupported in N.

The construction clearly satisfies the requirements. We need to check that N^{∗} does not realize any one of j∂^{n}Φ_{i}. Fix a name ẋ for an element of N^{∗}, n ∈ ℕ, and i ∈ ℕ. Then Int_{G}(ẋ) = [f]_{G} for some f. Let k be such that (f, ∂^{n}Φ_{i}) appears as the kth pair. Then A_{2k+1} ⊆ α ∈ ω_{1} | N ⊧ ¬ϕ(f(α), a⃗)} for some ϕ ∈ ∂^{n}Φ_{i}, hence A_{2k+1}⊩¬ϕ(ẋ, j(a⃗)) and therefore ẋ does not realize ∂^{n}Φ_{i}. □

Let N be a model of ZFC^{∘}, let X ⊆ ω_{1}^{N}, and let ψ(x) be a formula. We write

(aa x ∈ X)ψ(x) for ‘the set of x ∈ X such that ¬ψ(x) holds (in V)

is bounded in ω_{1}^{N},

(aa x⃗ ∈ X^{n})ψ(x⃗) for (aa x_{1} ∈ X)(aa x_{2} ∈ X) … (aa x_{n} ∈ X)ψ(x⃗),

where x⃗ is an n-tuple of variables.

Now write (x⃗ is assumed to be of appropriate length, this length being ω in the definition of Φ_{X}^{<ω})

Φ_{X}(x) = {ϕ(x, a⃗) | a⃗ ∈ N, (aa x ∈ X)N ⊧ ϕ(x, a⃗)}.
Φ_{X}^{n}(x⃗) = {ϕ(x⃗, a⃗) | a⃗ ∈ N, (aa x ∈ X^{n})N ⊧ ϕ(x⃗, a⃗)}.
Φ_{X}^{<ω}(x⃗) = ⋃_{n} Φ_{X}^{n}(x⃗ ↾ n).

We suppress writing parameters a⃗ ∈ N from now on, with the understanding that ϕ is a formula in the language extended by adding constants for all elements of the model N. The proof of the following lemma is modeled on [4, Lemma 7.3.4].

Lemma 1.10. Assume N is a model of ZFC^{∘} and X ⊆ ω_{1}^{N}. if ∂^{d}Φ_{X} is supported in N for some d ≥ 1 then there is an uncountable Y ∈ N such that Φ_{Y}^{<ω} ⊇ Φ_{X}^{<ω}.

Proof. For n ∈ ℕ and d ∈ ℕ write (∀^{ℵ_{0}}x ∈^{d} Z)ϕ(x) for (∀^{ℵ_{0}}x_{1} ∈ Z)(∀^{ℵ_{0}}x_{2} ∈ x_{1}) … (∀^{ℵ_{0}}x_{d} ∈ x_{d−1})ϕ(x),

(∀^{ℵ_{0}} x⃗ ∈ Z^{n})ϕ(x) for (∀^{ℵ_{0}}x_{1} ∈ Z)(∀^{ℵ_{0}}x_{2} ∈ Z) … (∀^{ℵ_{0}}x_{n} ∈ z)ϕ(x⃗),
(∀^{ℵ_{0}} x⃗ ∈^{d} Z^{n}) for (∀^{ℵ_{0}}x_{1} ∈^{d} Z)(∀^{ℵ_{0}}x_{2} ∈^{d} Z) … (∀^{ℵ_{0}}x_{n} ∈^{d} Z)ϕ(x⃗).

Claim. Assume H realizes ∂^{d}Φ_{X} for some d ≥ 1. Then for all m ≥ 0 and n ≥ 1 we have

(∀ϕ ∈ Φ_{X}^{m+n})(aa a⃗ ∈ X^{m})N ⊧ (∀^{ℵ_{0}} x⃗ ∈^{d} H^{n})ϕ(a⃗, x⃗).

Proof. Induction on n, for all m simultaneously. Assume n = 1 and pick ϕ ∈ Φ_{X}^{m+1} (with parameters suppressed). For y⃗ ∈ X^{m} let ψy⃗(x) be ϕ(y⃗, x). Since

(aa y⃗ ∈ X^{m})ψy⃗(x) ∈ Φ_{X}

we have

(aa y⃗ ∈ X^{m})N ⊧ (∀^{ℵ_{0}}x ∈^{d} H)ψy⃗(x).

Now assume the assertion holds for n and fix ϕ ∈ Φ_{X}^{m+n+1}. By the inductive assumption,

(aa w⃗ ∈ X^{m})(aa z ∈ X)N ⊧ (∀^{ℵ_{0}} x⃗ ∈^{d} H^{n})ϕ(w⃗, z, x⃗).

Fix w⃗ such that

(aa z ∈ X)N ⊧ (∀^{ℵ_{0}} x⃗ ∈^{d} H^{n})ϕ(w⃗, z, x⃗).

If we let ψw⃗(y) be (∀^{ℵ_{0}} x⃗ ∈^{d} H^{n})ϕ(w⃗, y, x⃗), then ψw⃗(y) ∈ Φ_{X}(y) and therefore

N ⊧ (∀^{ℵ_{0}}y ∈^{d} H)(∀^{ℵ_{0}} x⃗ ∈^{d} H)ϕ(w⃗, y, x⃗),

equivalently N ⊧ (∀^{ℵ_{0}} x⃗ ∈^{d} H^{n+1})ϕ(w⃗, x⃗). □

By the claim, for every n and ϕ ∈ Φ_{X}^{n} we have M ⊧ (∀^{ℵ_{0}} x⃗ ∈^{d} H^{n})ϕ(x⃗). Write x ∈^{d} Z for x ∈ ⋃ ⋃ ⋯ ⋃ Z, where ⋃ occurs d − 1 times, and A ⊆^{d} B if A ⊆ ⋃ ⋃ ⋯ ⋃ B, where ⋃ occurs d − 1 times. Note that the quantifier (∀^{ℵ_{0}}x ∈^{d} z) introduced earlier agrees with these conventions.

A set E ⊆^{d} H is solid if for all m, n ∈ ℕ, every e⃗ ∈ E^{m}, and every ϕ ∈ Φ_{X}^{m+n} we have M ⊧ (∀^{ℵ_{0}} x⃗ ∈^{d} H^{n})ϕ(e⃗, x⃗). Since E is solid if and only if each of its finite subsets is solid, by Zorn’s Lemma we can find a maximal solid E ⊆ X. We claim E is uncountable. Assume otherwise. For all m, n ∈ ℕ, e⃗ ∈ E^{n} and ϕ ∈ Φ_{X}^{m+n} we have N ⊧ (∀^{ℵ_{0}} x⃗ ∈^{d} H^{n})ϕ(e⃗, x⃗). Since there are only countably many such quadruples (m, n, e⃗, ϕ), we can find a ∈^{d} H such that a ∉ E and E ∪ {a} is still solid, contradicting the maximality of E.

Let Y ⊆^{d} H be uncountable and solid. Then for every n ≥ 1 and ϕ ∈ Φ_{X}^{n} we have N ⊧ ϕ(b⃗) for all b⃗ ∈ Y^{n}, therefore Y is as required. □

The following consequence of Lemma 1.10 is an extension of [4, Lemma 7.3.4].

Lemma 1.11. Assume N is a model of ZFC^{∘} and K ∈ N is such that N models ‘K ⊆ [ω_{1}]^{<ω} and there are no uncountable K-homogeneous sets.’ If X ⊆ ω_{1}^{N} is a maximal K-homogeneous set, then Φ_{X} is totally unsupported in N.

Proof. If Φ_{X} is realized by some b ∈ N, then b ≠ a for all a ∈ X and X ∪ {b} is still K-homogeneous, contradicting the maximality of X. Now assume ∂^{n}Φ_{X} is realized by some H. By Lemma 1.10 there is an uncountable Y ∈ N such that every a⃗ ∈ Y^{<ω} satisfies a⃗ ∈ K, contradicting our assumption. □

First Proof of Theorem 1.7. It will suffice to construct M^{∗} = M_{ω_{1}} with correct ω_{1} and such that for every partition K ⊆ [ω_{1}]^{<ω} in M, if there are no uncountable K-homogeneous sets in M then there are no uncountable K-homogeneous sets in V.

Let ⟨σ_{α} : α < ω_{1}⟩ be a ♢-sequence. We recursively build an iteration

⟨(M_{α}, I_{α}), G_{β}, j_{αγ} : α ≤ γ ≤ ω_{1}, β < ω_{1}⟩

of (M, I) and a set U ⊂ ω_{1} as follows. For each α < ω_{1}, let Φ^{α} be Φ_{σ_{α}} as defined above using M_{α} for N, and put α ∈ U if and only if Φ^{α} is totally unsupported in M_{α}. When constructing G_{α}, we apply Lemma 1.9 to ensure that each j_{β(α+1)}Φ^{β} (β ∈ U ∩ (α + 1)) is totally unsupported in M_{α+1}.

In order to assure correctness for NS_{ω_{1}} we apply the standard construction as described in [21, 12]. At any given stage α the bookkeeping machine requires us to put a specified member B of I_{α}^{+} into G_{α}. Letting I^{∗} be the ideal generated by I_{α} and the powerset of the complement of B the structure (M_{α}, I^{∗}) is an iterable pair and therefore Lemma 1.9 still applies.

Having completed the construction of the iteration, fix K ⊂ [ω_{1}]^{<ω} in M_{ω_{1}} such that in M_{ω_{1}} there exists no uncountable K-homogeneous Y ⊂ ω_{1}. Let X be a maximal K-homogeneous subset of ω_{1}, i.e., such that [X]^{<ω} ⊂ K but [X ∪{ξ}]^{<ω} ⊄ K for any ξ ∈ ω_{1} \ X. Let α < ω_{1} and k ∈ M_{α} be such that K = j_{αω_{1}}(k), and let β ∈ [α, ω_{1}) be such that

(1) ω_{1}^{M_{β}} = β;
(2) σ_{β} = X ∩ β;

(3) j_{βω_{1}}Φ^{β} is contained in Φ_{X} as computed over M_{ω_{1}}; (M_{β}, X∩β) is an elementary submodel of (M_{ω_{1}}, X), in particular σ_{β} is j_{αβ}(k)-maximal over M_{β}.

Then Lemma 1.11 implies Φ_{β} is totally unsupported in M_{β}, hence β ∈ U. Then j_{βω_{1}}Φ^{β} is totally unsupported in M_{ω_{1}}. If ξ ∈ X \ β, then (3) implies j_{βω_{1}}Φ_{X∩β} is realized by ξ in M_{ω_{1}}, a contradiction. Therefore X ⊆ β, and we conclude that there are no uncountable K-homogeneous sets in M_{ω_{1}}. □

1.3. Second proof of Theorem 1.7. This proof is similar and uses the following notion from [9]: a subset of [ω_{1}]^{<ω} is stationary if it contains a subset of every club subset of ω_{1}. More generally, given a normal uniform ideal I on ω_{1} we say that a subset of [ω_{1}]^{<ω} is I-positive if it contains a subset disjoint from each member of I. We also let a < b mean sup(a) < inf(b), when a and b are sets of ordinals.

Let ⟨σ_{δ} : δ < ω_{1}⟩ be a ♢-sequence. We construct an iteration

⟨M_{α}, I_{α}, G_{β}, j_{α,γ} : β < ω_{1}, α ≤ γ ≤ ω_{1}⟩

in the usual way, with the following modifications. We allow the ordinary construction to determine cofinally many members of each G_{β}, including the first one, and fill in the intervening steps ourselves. For each β < ω_{1}, let Φ_{β} be the set of unary formulas with constants in M_{β} satisfied by every member of σ_{β}, and for γ ∈ [β, ω_{1}], let Φ_{β}^{γ} be j_{βγ}Φ_{β}, the set of ϕ such that for some ϕ′ ∈ Φ_{β}, ϕ is ϕ′ with its constants replaced by their j_{βγ}-images.

While constructing G_{β}, we include stage for each tuple (B, f, ξ) of the following type:

• B is a stationary subset of [ω_{1}^{M_{β}}]^{p} in M_{β} for some nonzero p ∈ ω;

• f: B → ω_{1}^{M_{β}} is a function in M_{β} with f(b) ≥ max(b) for all b ∈ dom(f);

• ξ ≤ β.

When we come to the stage for a given (B, f, ξ), we have some A ∈ I_{β}^{+} which we have decided to put into G_{β}. If A has stationary intersection with the complement of the first-coordinate projection of B, then we put this intersection in G_{β}. Otherwise, if possible, we find some ϕ ∈ Φ_{ξ}^{β} such that the following set A′ is in I_{β}^{+}.

• if p = 1, A′ = {α ∈ A | M_{β} ⊧ ¬ϕ(f(α))};

• if p = m + 1, A′ is the set of α ∈ A for which for I_{β}^{+}-many a ∈ [ω_{1}^{M_{β}}]^{m},

(α, a) ∈ B and M_{β} ⊧ ¬ϕ(f(α, a)).

Then we put A′ in G_{β}. If there is no such ϕ, we do nothing at this stage.

Now, at the end of our construction, consider some K ⊂ [ω_{1}]^{<ω} in M^{∗} and suppose that X ⊂ ω_{1} is an uncountable K-homogeneous set (without loss of generality, we may assume that [X]^{<ω} ⊂ K). Fix α and K′ such that K = j_{αω_{1}}(K′). We will derive a contradiction from the assumption that for no β ∈ (α, ω_{1}) is there an uncountable j_{αβ}(K′)-homogeneous set in M_{β}.

Let Φ be the set of formulas with constants from M that are satisfied by every member of X. Note then that the set of countable ordinals satisfying all the members of Φ in M is uncountable. Fix ξ ∈ [α, ω_{1}) such that ω_{1}^{M_{ξ}} = ξ, σ_{ξ} = X ∩ ξ and Φ_{ξ}^{ω_{1}} is the set of formulas in Φ with constants in the j_{ξω_{1}}-image of M_{ξ}.

Now suppose that β ≥ ξ, p ∈ ω \ {0}, A ∈ G_{β}, B ∈ M_{β} is a stationary subset of [ω_{1}^{M_{β}}]^{p} with first-coordinate projection containing A modulo I_{β}, and f: B → ω_{1}^{M_{β}} is a function in M_{β}. Then there exist a (possibly 0) k ∈ ω, a k-tuple b contained in the critical sequence of j_{ξ,β}, an I_{ξ}-positive B′ ⊂ [ω_{1}^{M_{ξ}}]^{k+p} in M_{ξ} and a function f′: B′ → ω_{1}^{M_{ξ}} in M_{ξ} such that B = {a | (b∪a) ∈ j_{ξβ}(B′)∧max(b) < min(a\b)} and f(a) = f′(b ∪ a) for all a ∈ B. By induction on k, we show, under the assumption that f(b) ≥ max(b) for all b ∈ dom(f), that there exists a ϕ ∈ Φ_{ξ}^{β} such that the following set A′_{ϕ} is in I_{β}^{+}.

• if p = 1, A′_{ϕ} = {α ∈ A | M_{β} ⊧ ¬ϕ(f(α))};

• if p = m + 1, A′_{ϕ} is the set of α ∈ A for which for I_{β}^{+}-many a ∈ [ω_{1}^{M_{β}}]^{m},

(α, a) ∈ B and M_{β} ⊧ ¬ϕ(f(α, a)).

By our construction, this shows that X ⊂ ξ.

In the case where k = 0 and p = 1, if there is no ϕ as desired then A ∈ P(ω_{1})^{M_{β}} \ I_{β} and f ∈ (ω_{1}^{ω_{1}})^{M_{β}} are such that A forces [f]_{G_{β}} to satisfy each member of Φ_{η}^{β+1}. For each n ∈ ω, we show that there is a club E_{n} ⊂ ω_{1}^{M_{β}} in M_{β} such that for all increasing n-tuples ⟨ν_{0}, …, ν_{n−1}⟩ from A ∩ C, ⟨f(ν_{0}), …, f(ν_{n−1})⟩ is an increasing sequence and {f(ν_{0}), …, f(ν_{n−1})} is in j_{αβ}(K′).” Then in M_{β} there exists a sequence of clubs ⟨E′_{n} : n < ω⟩ such that each E′_{n} satisfies this statement for n, and their intersection is the desired set.

Note first of all that since f(α) ≥ α for all α ∈ dom(f), we may assume by shrinking if necessary that for all finite sequences ⟨ν_{0}, …, ν_{n}⟩ from A ∩ C, ⟨f(ν_{0}), …, f(ν_{n})⟩ is an increasing sequence.

For each n, by reverse (finite) induction starting at i = n − 1 and ending at i = 0 we show that the following holds for each i: for each i-tuple a from σ_{ξ}, M_{β} satisfies the sentence “there is a club subset C ⊂ ω_{1} such that for all n − i-tuples ⟨ν_{0}, …, ν_{n−i−1}⟩ from A ∩ C, if ⟨f(ν_{0}), …, f(ν_{n−i−1})⟩ is an increasing sequence above sup(a), then a ∪ {f(ν_{0}), …, f(ν_{n−i−1})} is in j_{αβ}(K′).” Since σ_{ξ} is j_{αξ}(K′)- homogeneous, this holds for i = n − 1. It if holds for i = j + 1, then for each j-tuple a from σ_{ξ} there is a club set D ∈ P(ω_{1})^{M_{β}} such that in M_{β}, for each χ ∈ D ∩ A there is a club C_{ξ} such that for all n − j-tuples ⟨ν_{0}, …, ν_{n−j−1}⟩ from A ∩ C_{ξ}, if ⟨f(χ), f(ν_{0}), …, f(ν_{n−i−1})⟩ is an increasing sequence above sup(a), then a ∪ {f(χ), f(ν_{0}), …, f(ν_{n−i−1})} is in j_{αβ}(K′). Then letting E_{n}^{i} = D ∩ △{C_{χ} : χ ∈ D ∩ A}, we have the desired statement for i, and E_{n}^{0} is the desired club E_{n}.

The case where k = 0 and p = m+1 is similar. Suppose that for every ϕ ∈ Φ_{β} the set A′_{ϕ} is nonstationary. Let B′ be the set of members of B whose least members are in A. For each n ∈ ω we find a club E_{n} ⊂ ω_{1}^{M_{β}} in M_{β} such that for all increasing n-tuples ⟨b_{0}, …, b_{n−1}⟩ from B′ ∩ [E_{n}]^{n}, ⟨f(b), f(b_{0}), …, f(b_{n−1})⟩ is an increasing sequence and {f(b), f(b_{0}), …, f(b_{n−1})} is in j_{αβ}(K′). Then M_{β} has an intersection of such clubs as above. Again, we may assume by shrinking if necessary that f(b) < α for all α ∈ A and b ∈ B′ ∩ [α]^{<ω}.

Again, by reverse finite induction starting at i = n − 1 and ending at i = 0 we show that the following holds for each i: for each i-tuple a from σ_{ξ}, M_{β} satisfies the sentence “there is a club subset C ⊂ ω_{1} such that for all n − i-tuples ⟨b_{0}, …, b_{n−i−1}⟩ from B′ ∩[C]^{n−i}, if ⟨f(b_{0}), …, f(b_{n−i−1})⟩ is an increasing sequence above sup(a), then a ∪ {f(b_{0}), …, f(b_{n−i−1})} is in j_{αβ}(K′).” Since σ_{ξ} is j_{αξ}(K′)- homogeneous, this holds for i = n − 1. It if holds for i = j + 1, then for each j-tuple a from σ_{ξ} there is a club set D ∈ P(ω_{1})^{M_{β}} such that in M_{β}, for each b ∈ B′ ∩ P(D) there is a club C_{b} such that for all n − j-tuples ⟨b_{0}, …, b_{n−j−1}⟩ from B′ ∩ [C_{b}]^{n−j}, if ⟨f(b), f(b_{0}), …, f(b_{n−i−1})⟩ is an increasing sequence above sup(a), then a ∪ {f(b), f(b_{0}), …, f(b_{n−i−1})} is in j_{αβ}(K′). Then letting

E_{n}^{i} = D ∩ △{C_{b} : b ∈ B′ ∩ P(D)},

we have the desired statement for i. The statement for i = 0 implies that there is an uncountable homogeneous set for j_{αβ}(K′) in M_{β}.

If k = j + 1, let η = max(b) and let b^{−} = b \ {η}. Then by our induction hypothesis there is a ϕ ∈ Φ_{ξ} such that the set of α < ω_{1}^{M_{η}} for which for stationarily many a ∈ [ω_{1}^{M_{η}}]^{n}, b^{−} ∪ {α} ∪ a ∈ j_{ξη}(B′) and M_{η} ⊧ ¬ϕ(j_{ξη}(f)(b^{−} ∪ {α} ∪ a)) is in G_{η}. Then ϕ is as desired.

1.4. Proof of Theorem 1.3. Theorem 1.3 follows from the proof of Theorem 1.7 once we notice that that proof did not require iterability (i.e., we did not use the fact that the models produced were wellfounded). One could rephrase Theorem 1.7 as follows.

Theorem 1.12. Assume M is a countable model of a large enough fragment of ZFC. Then M has an elementary extension M^{∗} whose ω_{1} is uncountable and which is correct about partitions of [ω_{1}]^{n} for each n ∈ ω. If M is an ω-model, then has an elementary extension M^{∗} whose ω_{1} is uncountable and which is correct about partitions of [ω_{1}]^{<ω}. Moreover, M^{∗} is correct about all Borel sets with codes in the well-founded part of M.

Proof. The proof of this is largely the same as the proofs of Theorem 1.7. Let ⟨σ_{α} : α < ω_{1}⟩ be a ♢-sequence. We recursively build a sequence

⟨(M_{α}, I_{α}), G_{β}, j_{αγ} : α ≤ γ ≤ ω_{1}, β < ω_{1}⟩

such that each G_{β} an M_{β}-normal ultrafilter of P(ω_{1}^{M_{β}})^{M_{β}} and M_{β+1} is the G_{β}- ultrapower of M_{β}. We don’t require the ultrafilters G_{β} to be generic over the models M_{β}.

Note that if X ∈ M_{β} is countable in M_{β} and f: ω_{1}^{M_{β}} → X is a function in M_{β}, then the M_{β}-normality of G_{β} implies that f is constant on a set in G_{β}. Conversely, if X is uncountable and f is injective, then f represents a new element of j(X) in the ultrapower (these facts are standard; the point is just that they don’t depend on wellfoundedness). It follows that elements of M_{ω_{1}} will have uncountable extent if and only if they are uncountable in M_{ω_{1}}.

One can likewise construct the iteration following the construction in the proof of Theorem 1.7. The argument goes through without change except for one point. If n is a nonstandard integer of M_{β}, then clearly we cannot argue by finite reverse induction on n. If the integers of M are nonstandard, then, we have to settle for correctness about partitions of [ω_{1}]^{n} for each standard integer n. □

While M^{∗} constructed in the above proof of Theorem 1.12 need not be wellfounded, the wellfounded part of its ω_{1} contains the well-founded part contains the well-founded part of ω_{1}^{M}. Therefore, assuming M is well-founded, M^{∗} is correct about L_{ω_{1}ω} sentences belonging to M. Note that the method of the proof gives proof of the following consequence of Keisler’s completeness theorem for L_{ω_{1}ω}(Q): For any L_{ω_{1}ω}(Q) sentence ϕ the statement ‘ϕ has a correct model’ is forcing-absolute.

In [14] Magidor and Malitz provide an axiomatization for L(Q^{<ω}) and, using ♢, prove the corresponding completeness theorem. Their axiomatization involves schemata of arbitrarily high complexity (and necessarily so; see [15]), Our result is purely semantic and we do not know whether there is a reasonable axiomatization for the logic of ‘correctness for partitions of [ω_{1}]^{<ω}.’ Note that we have completely avoided the problem of defining the syntax for this logic by embedding T into ZFC.

2. More on correctness for partitions of finite sets

2.1. Partitions of [κ]^{<ω} for κ > ω_{1}. If (M, I) is an iterable pair and j: (M, I) → (M^{∗}, I^{∗}) is an iteration, then M^{∗} is equal to the collection of all sets of the form j(f)(a), where f is a function in M and a is a finite subset of the critical sequence corresponding to j. It follows that if M is countable and j is an iteration of length ω_{1}, then M^{∗} is the union of countably many sets each having cardinality ℵ_{1} in M^{∗}. The results of the previous section then give the following.

Theorem 2.1. If ♢ holds and (M, I) is an iterable pair, then there is an iteration j: (M, I) → (M^{∗}, I^{∗}) of length ω_{1} such that M^{∗} is correct about the existence of uncountable homogeneous sets for partitions of [κ]^{<ω} for every κ ∈ M. □

Theorem 2.2. Suppose that there exist proper class many Woodin cardinals, let A be a universally Baire set of reals, and let T be a set of sentences in L(A). Suppose that there exists an A-correct model of T that is correct about the existence of uncountable homogeneous sets for partitions of any [κ]^{<ω} in some set forcing extension. Then there exists such model in every set forcing extension satisfying ♢.

Correctness about the existence of uncountable homogeneous sets for partitions of pairs implies the following.

Corollary 2.3. Suppose ♢ holds and that there exist proper class many Woodin cardinals. Let T be a large enough fragment of ZFC that holds in some forcing extension. Then there is an uncountable transitive model M of T that is correct about the countable chain condition of all partial order in M. We can also assure M is A-correct for any given universally Baire set A. □

Analogously to Theorem 1.3 we obtain the following.

Theorem 2.4 (♢). If a theory T extends a large enough fragment of ZFC and it is consistent, then ♢ implies the existence of a model M for T such that ω_{1}^{M} is uncountable and M is correct about the existence of homogeneous sets for partitions of [κ]^{<ω} that belong to M for every κ ∈ M.

2.2. [ω_{1}]^{n} vs. [ω_{1}]^{<ω}. By the results of §1, the existence of class many Woodin cardinals implies the following.

R^{<ω} If A is universally Baire and ϕ is a sentence of L(Q^{<ω}, A) that has a correct model in some forcing extension, then ϕ has a correct model in every forcing extension satisfying ♢.

R^{≤ω} If A is universally Baire and ϕ is a sentence of L(Q^{≤ω}, A) that has a correct model in some forcing extension, then ϕ has a correct model in every forcing extension satisfying ♢.

The case of R^{<ω} (R^{≤ω}, respectively) when A is a Borel set easily follows from the method of [14] (Theorem 1.12, respectively) and it does not require large cardinals. The general case of R^{<ω} (and therefore of R^{≤ω} requires large cardinals; this easily follows from [3, §7.2], where the weaker logic L(Q, A) was considered.

In this section we shall show that R^{≤ω} is a genuine improvement of R^{<ω} already in the case when A is Borel. For a universally Baire set A consider the following two assertions. R^{<ω}(A) If ϕ is a sentence of L(Q^{<ω}, A) that has a correct model in some forcing

extension, then ϕ has a correct model. R^{≤ω}(A) If ϕ is a sentence of L(Q^{≤ω}, A) that has a correct model in some forcing

extension, then ϕ has a correct model. Along with proving that ♢ implies R^{<ω}(Borel), Magidor and Malitz showed that forcing with a Cohen algebra preserves R^{<ω}(Borel) ([14, p. 257]). This shows that R^{<ω}(Borel) does not imply CH. Below we dwell on their ideas and further investigate in which models R^{<ω}(A) and R^{≤ω}(A) hold.

Lemma 2.5. Assume R^{<ω}(Borel). Then there exists a Suslin tree, a ccc-destructible (ω_{1}, ω_{1})-gap in P (ω)/Fin and an entangled set of reals.

Proof. This is immediate; for the definitions see e.g., [18]. □

Before stating a less trivial consequence of R^{≤ω}, let us record an immediate consequence of Lemma 1.6.

Lemma 2.6. Assume A is universally Baire.

(1) If R^{<ω}(A) holds then it holds in every forcing extension by a forcing that has property K_{n} for all n.

(2) If R^{≤ω}(A) holds then it holds in every forcing extension by a forcing that has precaliber ℵ_{1}. □

The content of (1) of Lemma 2.7 below is in the well-known equivalence of statements ‘the real line is not covered by ℵ_{1} many Lebesgue null sets’ and ‘the Lebesgue measure algebra has precaliber ℵ_{1}.’ We reproduce proof for the reader’s convenience and to assure that the former assertion’s expressibility in L_{ω_{1}ω}(Q^{≤ω}) is transparent. Clause (2) is essentially given in [14, p. 257], where it was shown that R^{<ω} is preserved by the forcing for adding any number of Cohen reals. We don’t state the obvious variations for R^{<ω}(A) or R^{≤ω}(A) of two propositions below.

Proposition 2.7. (1) Assume R^{≤ω}(Borel). Then the real line can be covered

by ℵ_{1} Lebesgue null sets.

(2) Every model of ZFC has a forcing extension in which R^{≤ω}(Borel) holds but the real line cannot be covered by ℵ_{1} meager sets.

(3) Every model of ZFC has a forcing extension in which R^{<ω}(Borel) holds but the real line cannot be covered by ℵ_{1} Lebesgue null sets.

Proof. (1) We shall find a sentence ϕ of L(Q^{≤ω},Borel) that has a correct model if and only if the real line can be covered by ℵ_{1} null sets.

Assume for a moment there is an increasing sequence of null G_{δ} sets N_{α} (α < ω_{1}) such that ⋃_{α<ω_{1}} N_{α} = ℝ. Let F_{α} ⊆ ℝ be a compact set of positive measure disjoint from N_{α}, and define K ⊆ [ω_{1}]^{<ω} by s ∈ K if and only if ⋂_{α∈s} F_{α} ≠ ∅. An uncountable K-homogeneous set gives a family of compact sets with a finite intersection property, and the intersection of this family is disjoint from ⋃_{α} N_{α}. Therefore a sentence ϕ asserting enough ZFC plus ‘There exist compact sets of positive measure F_{α} (α < ω_{1}) such that the partition K defined by s ∈ K if and only if ⋂_{α∈s} F_{α} ≠ ∅ has no uncountable homogeneous set’ has a correct model in every extension in which the real line can be covered by ℵ_{1} many null sets. (Note that we only need correctness for a rather simple Borel set.)

We claim that the converse is also true. Assume otherwise. Let M be a model correct for ϕ and assume the real line cannot be covered by ℵ_{1} many null sets. Let F_{α} (α < ω_{1}) be compact positive sets witnessing ϕ in M. By downward Löwenheim–Skolem theorem we may assume M is of size ℵ_{1}. By the ccc-ness of Lebesgue measure algebra there is a compact positive set F ∈ M forcing that the generic filter contains uncountably many of the F_{α}’s. Let r ∈ F be a real that avoids all null sets coded in M. Then r is a random real over M, hence H = {α < ω_{1} | r ∈ F_{α}} is uncountable. Then H is an uncountable homogeneous set, contradicting the assumption on M.

(2) A model of ♢ satisfies R^{<ω} by the L_{ω_{1}ω} variant of Theorem 1.1, e.g., Theorem 1.12. The standard forcing for adding ℵ_{2} Cohen reals has precaliber ℵ_{1} and it forces that the real line cannot be covered by fewer than ℵ_{2} meager sets . By Lemma 2.6 the extension obtained by adding Cohen reals to a model of ♢ is as required.

(3) This is similar to the proof of (2), using the well-known fact that every measure algebra has property K_{n} for all n. □

The model of (3) of Proposition 2.7 gives the following.

Proposition 2.8. Every model of ZFC has a forcing extension in which R^{<ω}(Borel) holds, but R^{≤ω}(Borel) fails. □

3. Extensions of the Σ_{1}^{2}-absoluteness argument

Let us recall a conjecture of John R. Steel presented in [19].

Conjecture 3.1. Assuming sufficient large cardinals, every Σ_{2}^{2} sentence ϕ that holds in some forcing extension satisfying ♢ holds in all forcing extensions satisfying ♢.

Note the resemblance to Woodin’s Σ_{1}^{2} absoluteness based on CH ([20], [11]) which was one of the starting points to the first part of this paper ([3]). By standard facts about Woodin cardinals ([11, Theorem 2.5.10]), Conjecture 3.1 is equivalent to its consequence stating that ♢ (together with appropriate large cardinals) implies every Σ_{2}^{2} statement true in some forcing extension satisfying ♢. Results of §1 can be interpreted as confirmation of Conjecture 3.1 in the case when the Σ_{2}^{2} sentence ϕ states the existence of a partition of [ω_{1}]^{<ω} satisfying some first-order properties with no uncountable homogeneous sets. However, Conjecture 3.1 is not likely to be proved by iterating ℙ_{max} preconditions as in §1. A major obstacle is that for each ℙ_{max} precondition (N, I) there exists a real number not belonging to any of the iterates of (N, I) (take e.g., the real coding (N, I)). At this point we do not see how to prove a version of absoluteness for Magidor–Malitz logic using the stationary tower. In this section we solve some other technical problems related to Conjecture 3.1. Assuming ♢ and using stationary tower, we find a model containing all reals and satisfying the following

(1) Correctness about the countable chain condition for partial orders on ω_{1} (Theorem 3.5).

(2) Correctness about uncountable chains through (some) trees of height and cardinality ω_{1} (Theorem 3.5).

(3) Containing a function on ω_{1} dominating any such given function on a club

(Proposition 3.9). While both (1) and (2) are consequences of correctness for the existence of uncountable homogeneous sets for partitions of [ω_{1}]^{2}, (3) cannot be obtained using ℙ_{max} preconditions. This is because if for every f: ω_{1} → ω_{1} there is an iteration of a ℙ_{max} precondition (N, I) with a function dominating f on a club, then CH fails. This assertion easily implies that a function definable from (N, I) dominates f on a club, and therefore that the size of the continuum is not smaller than the cofinality of ω_{1}^{ω_{1}} ordered by the dominance modulo NS_{ω_{1}}, and therefore that CH fails. This is one of the points in Woodin’s proof that the saturatedness of NS_{ω_{1}}, together with the existence of H(ℵ_{2})^{#} implies CH fails ([21, §3.1]).

The version for correctness about the countable chain condition was proved in [13] before the work in this paper and its predecessor. The version for trees on ω_{1} is left to the reader.

3.1. The setup. Definitions of the stationary towers ℙ_{<δ} and ℚ_{<δ} can be found e.g., in [21] or [11]. We work with the terms from Section 4 of [3]. There, V [h] is a forcing extension of V, and M is a model whose ω_{1} (which we also call λ) is a Woodin cardinal in V [h], which sees a club C ⊂ λ contained in the Woodin cardinals of V [h] whose limit points β have the property that C ∩β is contained modulo a tail in each club subset of β in V [h], and such that V_{ζ}[h] ∈ M for some strongly inaccessible cardinal ζ > λ of V [h]. Inside the model M, then, one can construct V [h]-generics for ℚ_{<λ}^{V [h]}. The following theorem (due to Woodin, see [11, 3]) summarizes the situation. As discussed in [3], the assumption of a measurable Woodin cardinal can be replaced with a so-called full Woodin cardinal.

Theorem 3.2. Suppose that δ is a measurable Woodin cardinal and κ > δ is a Woodin cardinal. Then there is a condition a ∈ ℙ_{<κ} such that if G ⊂ ℙ_{<κ} is a V - generic and a ∈ G, then G∩V_{δ} is a V -generic filter for ℚ_{<δ} and, letting j: V → M be the embedding induced by G,

• j(ω_{1}^{V}) = δ;

• κ is a Woodin cardinal in V [G];

• M is closed under sequences of length less than κ in V [G];

• there exists in M a club set C ⊂ δ contained in the Woodin cardinals of V such that for each limit point β of C, (C ∩ β) \ D is a bounded subset of β for each club D ⊂ β in V.

Note that in this context, since δ is strongly inaccessible in V and ω_{1} in M, there exist in M V -generic filters for each partial order in V_{δ}.

In Theorem 3.5, we show that if ♢ holds in M then M can build the generic so that the final image model is correct about the countable chain condition for its partial orders on ω_{1}, and correct about whether its trees of height and cardinality ω_{1} have uncountable paths. In each case the argument involves inserting cofinally many steps into the construction of each generic filter H_{α} (or just stationarily many), in order to ensure that a set given by a fixed ♢-sequence is not an initial segment of an uncountable path or antichain.

Lemma 3.3. Suppose that δ < λ are Woodin cardinals, G ⊂ ℚ_{<δ} is V -generic, a ∈ ℚ_{<λ} is such that ℚ_{<δ} regularly embeds into the restriction ℚ_{<λ}(a) of ℚ_{<λ} to a. Let j: V → N be the embedding induced by G. Let T be a tree on ω_{1}^{N} of height ω_{1}^{N} with no uncountable branches in N. Let p be a cofinal branch of T, let b be a condition in ℚ_{<λ}(a) and let f be a function in V from b to ω_{1}^{V}. Then there is a b′ ≤ b forcing that [f]_{H} does not extend p, where H is the induced ℚ_{<λ}-generic.

Proof. It is a standard fact that in this situation N and V [G] agree about the existence or nonexistence of cofinal paths through T (more generally, about Σ_{1} sentences with parameters in P(δ)^{N}; briefly, there is in some outer model an elementary embedding with critical point above δ from N into a model containing P(δ)^{V [G]}; as an example of this, see the relationship between M_{λ} and M on page 95 of [11]). Consider then the set of nodes in T which b forces [f]_{H} to extend. This set cannot be p, but it must be a pairwise compatible set, so it cannot contain p, either. So extend b to b′ forcing that [f]_{H} does not extend some fixed member of p. □

Lemma 3.4. Suppose that δ < λ are Woodin cardinals, G ⊂ ℚ_{<δ} is V -generic, a ∈ ℚ_{<λ} is such that ℚ_{<δ} regularly embeds into the restriction ℚ_{<λ}(a) of ℚ_{<λ} to a. Let j: V → M be the embedding induced by G. Let P be a partial order on ω_{1}^{M} in M which is ccc in M. Let A be a predense subset of P, not necessarily in M, let b be a condition in ℚ_{<λ}(a) and let f be a function in V from b to ω_{1}^{V}. Then there is a b′ ≤ b forcing that [f]_{H} is compatible with some member of A, where H is the induced ℚ_{<λ}-generic.

Proof. By the same standard fact as in the proof of Lemma 3.3, M and V [G] agree about the existence or nonexistence of uncountable antichains of P. Consider then the set X of elements of P which b forces [f]_{H} to be incompatible with. If X does not contain A then the lemma clearly holds, so assume otherwise. In V [G], and thus in M there is a countable X′ ⊂ X such that every element of P is compatible with an element of X if and only if it is compatible with an element of X′. Since A is predense and A ⊂ X, this means that X′ is predense, so every element of P is compatible with some member of X′. Since X′ is countable, it will continue to have this property in the ℚ_{<λ}-ultrapower, contradicting that b forces that [f]_{H} will be incompatible with every member of X′. □

We say that a model N is correct about the countable chain condition on partial orders on ω_{1} if ω_{1}^{N} = ω_{1} and for every partial order P on ω_{1} in N, P has an uncountable antichain in N if and only if it has one in V. We say that a model N is correct about uncountable paths through trees of height and cardinality ω_{1} if ω_{1}^{N} = ω_{1} and for every tree of height and cardinality ω_{1} in N, P has an uncountable branch in N if and only if it has one in V.

Theorem 3.5. Suppose that κ is a measurable Woodin cardinal. Let A be a κuniversally Baire set of reals and let ϕ be a sentence in the language of set theory with one additional unary predicate. Then the following hold, where the models are taken to be over a language with an additional unary predicate for the interpretation of A in the corresponding model.

(1) Suppose that some partial order P ∈ V_{κ} forces the existence of a model N of ϕ which is correct about uncountable paths though trees of height and cardinality ω_{1}. Then in every set forcing extension of V by a forcing in V_{κ} which satisfies ♢ there exists a model M of ϕ which is correct about uncountable paths through trees of height and cardinality ω_{1}.

(2) Suppose that some partial order P ∈ V_{κ} forces the existence of a model N of ϕ which is correct about the ccc on partial orders on ω_{1}. Then in every set forcing extension of V by a forcing in V_{κ} which satisfies ♢ there exists a model M of ϕ which is correct about the ccc on partial orders on ω_{1}.

Correctness about NS_{ω_{1}} can be added to conclusion of Theorem 3.5 and Theorem 3.6 below. The proof of each theorem involves adding a few steps to the construction of each H_{α} in the proof of the corresponding theorem in [3]. The point is that the model M from that proof constructs a collection of V [h]-generic filters H_{α} (α < λ), and if at a given stage a ♢-sequence in M guesses a cofinal branch in a given tree in the current model ((V [h][H_{α}])_{ζ}), Lemma 3.3 says that we can extend our construction in such a way that that branch is not extended in the extension of the tree. Similarly, if at a given stage a ♢-sequence in M guesses a maximal antichain in a given partial order in the current model, Lemma 3.4 says that we can extend our construction in such a way that that antichain is not extended in the extension of the partial order. The new elements of the construction discussed here require only cofinally many stages of the construction of each H_{α}, and so do not interfere with the original argument. They do not interfere with each other, either: one can combine these two arguments to obtain both correctness properties. However, they do interfere with the argument that allows the construction in M to put any given real in the model it is constructing, as adding a given real to a model requires control over the entire construction of the generic filter at that stage. If we restrict to the set of ω_{1}-trees, however, then we can obtain correctness about paths while picking up all the reals. The point here is that for each level of each ω_{1}-tree in the construction, there is only one stage where nodes on that level are created. So once Lemma 3.3 has been applied to make sure that a given path is not extended, that path can never be extended accidentally later in the construction, while picking up a given real, say. Combining this observation with the arguments from Section 4 of [3], we have the following.

Theorem 3.6. Suppose that κ is a measurable Woodin cardinal. Let A be a κuniversally Baire set of reals and let ϕ be a sentence in the language of set theory with one additional unary predicate. Suppose that some partial order P ∈ V_{κ} forces the existence of a model N of ϕ (with the additional symbol interpreted as A^{V^{P}}) which is correct about uncountable paths though ω_{1}-trees and which contains all the reals. Then in every set forcing extension of V by a forcing in V_{κ} which satisfies ♢ there exists a model M of ϕ (with the additional symbol interpreted as A ∩ M) which is correct about uncountable paths through ω_{1}-trees and contains any given ℵ_{1}-many reals.

The following well-known observation shows that a version of this construction which obtained correctness about uncountable paths through trees of height and cardinality ω_{1} while picking up all the reals would show that ♢ decides all Σ_{2}^{2} sentences with respect to models obtained by set forcing.

Theorem 3.7. Suppose that M is a transitive model of ZFC + CH which contains the reals, and for every tree T of height and cardinality ω_{1} in M, T has an uncountable path in M if and only if it has on in V. Suppose that M satisfies a sentence ϕ of the form ∃A ⊂ ℝ∀B ⊂ ℝψ(A, B), where the quantifiers of ψ range over the reals. Then ϕ holds in V.

Proof. Let A ⊂ ℝ be such that ∀B ⊂ ℝψ(A, B) holds in M, let ⟨x_{α} : α < ω_{1}⟩ be a listing of the real in M, and for each α < ω_{1} and any set of reals X let X↾α denote X ∩ {x_{β} : β < α}. Then for any X ⊂ ℝ and any formula θ whose quantifiers range only over reals, θ(A, B) holds if and only if there is a club C ⊂ ω_{1} such that for all α ∈ C, θ_{α}(X↾α) holds, where θ_{α} is the formula θ with its quantifiers restricted to {x_{α} : α < ω_{1}}. Since CH holds in M, there is a natural tree in M of height and cardinality ω_{1} giving the initial segments of a supposed club C ⊂ ω_{1} and set B ⊂ ℝ such that for all α ∈ C, ¬ψ_{α}(A↾α, B↾α) holds. Since A witnesses ϕ in M, there is no uncountable path through this tree in M, and thus by the assumption of the theorem, there is none in V, which means that A witnesses ϕ in V. □

As we noted above, the following theorem follows easily from Theorem 1.7, though it can be proved much more easily using the approach from Lemmas 3.3 and 3.4.

Theorem 3.8 (♢). If (M, I) is an iterable pair, then there is an iteration j: (M, I) → (M^{∗}, I^{∗}) of (M, I) such that the model M^{∗} is correct about the ccc on partial orders on ω_{1} and about the existence of uncountable paths through trees of height and cardinality ω_{1}.

Proposition 3.9. In the situation of Theorem 3.2, assuming ♢ holds in V [h] then there is a function in V [h] whose image under the ℚ_{<λ}^{V [h]}-generic filter can be made to dominate any function from λ to λ in M on a club.

The proof given below uses the following standard fact from the stationary tower (see [11]): for any ordinal γ < λ, the function on P_{ℵ_{1}}(γ) which takes each X ⊂ γ to the ordertype of X represents γ in the generic ultrapower. The stationary set defined in the lemma then forces that the image of g will take the value γ at δ. This contrasts with the situation when canonical function bounding (see [10], for instance) holds; then, no function in ω_{1}^{ω_{1}} can represent any ordinal above the ω_{2} of the ground model.

Lemma 3.10. Let δ be a Woodin cardinal and let ⟨σ_{α} : α < ω_{1}⟩ be a sequence witnessing that ♢ holds. Define g: ω_{1} → ω_{1} by letting g(α) be the corresponding ordertype if σ_{α} codes a wellordering of α, and 0 otherwise. Then for any γ > δ the set of countable X ⊂ V_{γ} such that o. t.(X ∩ γ) = g(o. t.(X ∩ δ)) and X captures every predense subset of ℚ_{<δ} in X is compatible with every condition in ℚ_{<δ}.

Proof. Pick a ∈ ℚ_{<δ} and F: [V_{λ}]^{<ω} → V_{λ}. By a standard argument (see Corollary 2.7.12 of [11]), there exists a continuous increasing ⊂-chain ⟨X_{α} : α ≤ ω_{1}⟩ of countable subsets of V_{γ} such that

• X_{0} ∩ ∪a ∈ a;

• each X_{α} is closed under F;

• each X_{α+1} end-extends X_{α} below δ;

• each X_{α} captures every predense subset of ℚ_{<δ} in X_{α}. Let f: ω_{1} → (X_{ω_{1}} ∩ γ) be a bijection, and let S be the set of (α, β) ∈ ω_{1}^{2} such that f(α) ≤ f(β). Then some σ_{α} codes S↾α, and this α is as desired. □

Proof of Proposition 3.9. Suppose H ⊂ ℚ_{<η_{α}} is a V [h]-generic filter as in the Σ_{1}^{2}- absoluteness proof in [3]. Suppose that γ is less than η_{α+1} (which itself can be chosen to arbitrarily large below λ). Let a be the stationary set of countable subsets of V_{γ} given by Lemma 3.10. Then ℚ_{<η_{α}} regularly embeds into the restriction of ℚ_{<η_{α+1}} to conditions below a, and a forces that the image of g under the induced ℚ_{<η_{α+1}}-embedding will take value γ at η_{α}. In this way, Lemma 3.10 can be used in M to ensure that the image of the function g dominates any given function in M on a club. □

An another warm-up problem towards proving Σ_{2}^{2}-absoluteness from ♢ is the question of whether the model M^{∗} constructed in the Σ_{1}^{2} absoluteness proof can be made to contain a sequence which is a ♢-sequence in M. If M had contained a canonical function which necessarily dominated every function in N on a stationary set then this would have shown that M^{∗} could not contain a ♢-sequence of M. We note the following fundamental fact ([21, 12]) about ℙ_{max} iterations which shows that for every iterable pair (M, I) there is a function f: ω_{1} → ω_{1} such that for every iteration j: (M, I) → (M^{∗}, I^{∗}) of length ω_{1}, f dominates every member of ω_{1}^{ω_{1}} ∩ M^{∗} on a club: if (M, I) is an iterable pair coded by a real x such that M is countable and x^{#} exists, then for every countable ordinal β and every iteration j: (M, I) → (M^{∗}, I^{∗}) of length β, the ordinal height of M^{∗} is less than the least x-indiscernible above β.

4. Trees of models

Here we show that any of these constructions can be modified to produce a 2^{<ω_{1}}-tree of models whose paths produce models with no stationary, costationary subsets of ω_{1} in common. The statement of the following theorem is essentially its own proof. The point is that during the construction of a ℙ_{max} iteration or a sequence of stationary tower generic as in the Σ_{1}^{2} absoluteness argument, one can take any given stationary, costationary set in the current model and choose whether to put the current ω_{1} in the image of this set (for ℙ_{max} this is standard, for the Σ_{1}^{2} argument this was shown in [3]). The tree-of-models construction below is an attempt to capture the idea that if CH implies some Σ_{1}^{2} statement ϕ (which doesn’t follow from ZFC), then there are 2^{ω_{1}} many distinct witnesses ϕ. Undoubtedly this can be made more precise.

Theorem 4.1. Let S(α, β, γ) (α, β, γ < ω_{1}) be pairwise disjoint stationary subsets of ω_{1}. Let N_{x} (x ∈ 2^{≤ω_{1}}) be a collection of transitive models of ZFC such that P(ω_{1})^{N_{x}} is countable for each N_{x}, and for each pair x ⊂ y in 2^{≤ω_{1}} let j_{xy}: N_{x} → N_{y} be an elementary embedding with critical point ω_{1}^{N_{x}}. Suppose that for each x ∈ 2^{≤ω_{1}} of limit length the model N_{x} is the direct limit of the models N_{y} (y ⊊ x) under these embeddings. For each x ∈ 2^{<ω_{1}} of limit length we let ⟨A_{α}^{x} : α ∈ dom(x)⟩ list the stationary, costationary subsets of ω_{1}^{N_{x}} in N_{x}, in such that a way that x ⊂ y implies that A_{α}^{y} = j_{xy}(A_{α}^{x}) for each α ∈ dom(x).

Suppose further that

• whenever x(γ) = 0 and ω_{1}^{N_{x}} ∈ S(α, β, γ) for some β and some α < ω_{1}^{N_{x}},

then ω_{1}^{N_{x}} is in A_{α}^{y} for all y ⊃ x, and that

• whenever x(γ) = 1 and ω_{1}^{N_{x}} ∈ S(α, β, γ) for some α and some β < ω_{1}^{N_{x}},

then ω_{1}^{N_{x}} is not in A_{β}^{y} for any y ⊃ x.

Now let x, y be any two distinct elements of 2^{ω_{1}}, and suppose that γ < ω_{1} is such that x(γ) = 0 and y(γ) = 1. Let C_{x} = {ω_{1}^{N_{x′}} : x′ ⊊ x} and let C_{y} = {ω_{1}^{N_{y′}} : y′ ⊊ y}, and let B_{x} and B_{y} be two stationary, costationary subsets of ω_{1} in N_{x} and N_{y} respectively. Fix α, β < ω_{1} such that B_{x} = A_{α}^{x} and B_{y} = A_{β}^{y}, and let η be the maximum of min(C_{x} \ (α + 1)) and min(C_{y} \ (β + 1)). Then B_{x} △ B_{y} contains C_{x} ∩ C_{y} ∩ S(α, β, γ) ∩ (ω_{1} \ η), and so is stationary.

5. Special trees on reals

In [16], Steel shows that in the presence of large cardinals, trees on reals in L(ℝ) without uncountable branches in V have an absolute impediment preventing such a branch from being added by forcing. In this section we generalize this result to trees coded by arbitrary universally Baire sets, using results of Woodin on the inner model HOD (the class model consisting of all hereditarily ordinal definable sets, see [5, 8]) in place of inner model theory.

Given a tree T, we let T^{+} denote the set of sequences whose proper initial segments are all in T. We think of the trees on reals in this section as sets of reals.

Theorem 5.1 ([16]). Assume that there exist infinitely many Woodin cardinals below a measurable cardinal. Let T ⊂ ℝ^{<ω_{1}} be a tree in L(ℝ). Then exactly one of the following holds.

• There is an uncountable branch of T in V.

• There is a function f: T^{+} → ω^{ω} in L(ℝ) such that for each p ∈ T^{+}, f(p) codes a wellordering of ω in ordertype dom(p).

In our generalization of this result, we can prove one of the two directions in a slightly more general context than the other.

We will be using the following well-known facts, though some of them are unpublished. The axiom AD^{+} is a strengthening of the Axiom of Determinacy due to Woodin (for this and the two following theorems, see [7]).

Theorem 5.2 (Woodin). If AD^{+} holds and S is a set of ordinals, there is a Q ⊂ θ such that L[Q] = HOD_{S} and L[Q, x] = HOD_{S,x} for every countable x ⊂ ω_{1}.

Theorem 5.3 (Woodin). If AD^{+} holds and Q is a set of ordinals, then for a Turing cone of reals x, ω_{2}^{L[Q,x]} is a Woodin cardinal in HOD_{Q}^{L[Q,x]}.

Note that if Q is a set of ordinals and x is a real, then every set of ordinals in L[Q] is in HOD_{Q}^{L[Q,x]}.

The statement DC_{ℝ} says that trees on reals of height ω have maximal branches.

Theorem 5.4 (Martin; see [6]). If AD + DC_{ℝ} holds, then every set of Turing degrees contains or is disjoint from a cone, and the intersection of countably many cones is nonempty.

Our proof uses a simple version of Woodin’s stacking argument.

Theorem 5.5. Let T ⊂ ℝ^{<ω_{1}} be a tree, let S be a set of ordinals coding trees on the ordinals projecting to T and its complement, and suppose that L(S, ℝ) ⊧ AD^{+}. Then at least one of the following two statements is true.

(1) There is an uncountable branch of T in V.

(2) There is a function f: T^{+} → ω^{ω} in L(S, ℝ) such that for each p ∈ T^{+},

f(p) codes a wellordering of ω in ordertype dom(p). Furthermore, if there exists a Woodin cadinal δ and every set of reals in L(S, ℝ) is δ^{+} weakly homogeneously Suslin in V, at least one of (1) and (2) is false.

Proof. We work in L(S, ℝ). First suppose that (2) fails. We show that (1) holds. Since there are wellorderings of P(ω)^{HOD_{S,p}} uniformly definable from p, there must be a p ∈ T^{+} which is uncountable in HOD_{S,p}. Fix Q ⊂ θ as in Theorem 5.2, with respect to S. Then p is uncountable in L[Q, p]. We have then by Theorem 5.3 that for a Turing cone of reals x, ω_{2}^{L[Q,p,x]} is a Woodin cardinal in HOD_{Q,p}^{L[Q,p,x]}. We would like to see that for a cone of x,

ω_{1}^{HOD_{Q,p}^{L[Q,p,x]}} ≤ ω_{1}^{L[Q,p]}.

This follows from the fact that each model of the form HOD_{Q,p}^{L[Q,p,x]} has a definable (uniformly from p) wellordering <_{x} of its reals, and so the following set of triples is definable from Q and p: the set of (α, i, j) such that for a cone of x,

ω_{1}^{HOD_{Q,p}^{L[Q,p,x]}} > α

and the pair (i, j) is in the <_{x}-least element of ω^{ω} in HOD_{Q,p}^{L[Q,p,x]} coding a wellordering of ω of ordertype α. By the countable completeness of the cone measure (Theorem 5.4), this gives a sequence of surjections in L[Q, p] from ω onto each ordinal α which is less than

ω_{1}^{HOD_{Q,p}^{L[Q,p,x]}}

for a cone of x.

Now, fix an x such that

ω_{1}^{HOD_{Q,p}^{L[Q,p,x]}} ≤ ω_{1}^{L[Q,p]}

and ω_{2}^{L[Q,p,x]} is a Woodin cardinal in HOD_{Q,p}^{L[Q,p,x]}. Let

M = HOD_{Q,p}^{L[Q,p,x]}.

Let δ = ω_{2}^{L[Q,p,x]}. Since δ is countable in V, we can choose an M-generic filter g for Coll(ω_{1}, <δ)^{M}. Then the nonstationary ideal is presaturated in M[g]. Furthermore, since S ∈ M, there are trees in M[g] projecting in V to T and its complement. This means that M[g] is T -iterable [21, 12]. Stepping outside of L(S, ℝ) to a model of Choice and taking any iteration j of M[g] of length ω_{1}, then, j(p) is an uncountable member of T^{+}.

To see the last part of the Theorem, suppose that T and f are coded by δ^{+}- weakly homogeneously Suslin sets of reals, and suppose that p is an uncountable path through T. Then there is a countable elementary submodel X of some large enough initial segment of the universe containing δ, T, f and p whose transitive collapse M has the property that (letting δ̄ be the image of δ under the collapse), if M[g] is a forcing extension of M by Coll(ω_{1}, δ̄)^{M}, then M[g] is (T, f)-iterable ([21, 12, 3]). Letting p̄ be the image of p under the collapse, then, every forcing extension of M[g] by (P(ω_{1})/NS_{ω_{1}})^{M[g]} has f(p̄) as an element, which means that M[g] has f(p̄) as an element, giving a contradiction, since f(p̄) codes a wellordering of ω of the same length as p̄, and this length is ω_{1}^{M[g]}. □

The following theorems can be used to show that if there exists a proper class of Woodin cardinals and the tree T is a weakly homogeneously Suslin set of reals, then there is a model of the form L(S, ℝ) satisfying AD^{+}, where S is a set of ordinals coding trees projecting to T and its complement. In this context, then, exactly one of (1) and (2) above hold.

Theorem 5.6 (Steel [17, 11]). Suppose that there exist proper class many Woodin cardinals. Then universally Baire sets of reals have universally Baire scales.

Theorem 5.7 (Woodin [17]). Suppose that there exist proper class many Woodin cardinals, and let A be a weakly homogeneously Suslin set of reals. Then A is universally Baire and L(A, ℝ) ⊧ AD^{+}.

Theorem 5.8 (Woodin). Suppose that AD^{+} holds and that M is an inner model containing the reals. Then M ⊧ AD^{+}.

References

[1] Uri Abraham and Saharon Shelah. A Δ_{2}^{2} well-order of the reals and incompactness of L(Q^{MM}). Ann. Pure Appl. Logic, 59(1):1–32, 1993.

[2] I. Farah, M. Hrušák, and C.A. Martínez Ranero. A countable dense homogeneous set of size ℵ_{1}. Fundamenta Mathematicae, 186:71–77, 2005.

[3] I. Farah and P.B. Larson. Absoluteness for universally Baire sets and the uncountable I. preprint, 2005.

[4] Wilfrid Hodges. Building models by games, volume 2 of London Mathematical Society Student Texts. Cambridge University Press, Cambridge, 1985.

[5] T. Jech. Set Theory. Academic Press, 1978.

[6] A. Kanamori. The higher infinite: large cardinals in set theory from their beginnings. Perspectives in Mathematical Logic. Springer–Verlag, Berlin–Heidelberg–New York, 1995.

[7] P. Koellner and W.H. Woodin. Large cardinals from determinacy. In Handbook of Set Theory. to appear.

[8] K. Kunen. An Introduction to Independence Proofs. North–Holland, 1980.

[9] P. Larson. A uniqueness theorem for iterations. J. Symbolic Logic, 67:1344–1350, 2002.

[10] P. Larson and S. Shelah. Bounding by canonical functions, with ch. J. Math Logic, 3:193–215, 2003.

[11] P.B. Larson. The stationary tower, volume 32 of University Lecture Series. American Mathematical Society, Providence, RI, 2004. Notes on a course by W. Hugh Woodin.

[12] P.B. Larson. Forcing over models of determinacy. In Handbook of Set Theory. to appear.

[13] P.B. Larson and T. Yorioka. ℙ_{max} variations for destructible gaps. in preparation, 2005.

[14] Menachem Magidor and Jerome Malitz. Compact extensions of L(Q). Ia. Ann. Math. Logic, 11(2):217–261, 1977.

[15] Saharon Shelah and Charles Steinhorn. The nonaxiomatizability of L(Q_{ℵ_{1}}^{2}) by finitely many schemata. Notre Dame J. Formal Logic, 31(1):1–13, 1990.

[16] J. Steel. Note to Jouko Väänänen. unpublished, 2000.

[17] J. Steel. The derived model theorem. preprint, 2003.

[18] S. Todorcevic. Partition Problems in Topology, volume 84 of Contemporary mathematics. American Mathematical Society, Providence, Rhode Island, 1989.

[19] W. Hugh Woodin. Beyond Σ_{1}^{2} absoluteness. In Proceedings of the International Congress of Mathematicians, Vol. I (Beijing, 2002), pages 515–524, Beijing, 2002. Higher Ed. Press.

[20] W.H. Woodin. Σ_{1}^{2}-absoluteness. handwritten note of May 1985.

[21] W.H. Woodin. The Axiom of Determinacy, forcing axioms and the nonstationary ideal, volume 1 of de Gruyter Series in Logic and Its Applications. de Gruyter, 1999.

Dept. of Mathematics and Statistics, York University, 4700 Keele Street, Toronto, Canada M3J 1P3

Matematicki Institut, Kneza Mihaila 35, 11 000 Beograd, Serbia and Montenegro

   E-mail address: ifarah@mathstat.yorku.ca
   URL: http://www.mathstat.yorku.ca/∼ifarah

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

   E-mail address: richard.ketchersid@gmail.com
   E-mail address: larsonpb@muohio.edu
   URL: http://www.users.muohio.edu/larsonpb/

Mathematics Institute, Hebrew University, Givat Ram, 91904 Jerusalem, Israel

   E-mail address: menachem@math.huji.ac.il