ABSOLUTENESS FOR UNIVERSALLY BAIRE SETS AND THE UNCOUNTABLE I

ILIJAS FARAH AND PAUL B. LARSON

Cantor’s Continuum Hypothesis was proved to be independent from the usual ZFC axioms of Set Theory by Gödel and Cohen. The method of forcing, developed by Cohen to this end, has lead to a profusion of independence results in the following decades. Many other statements about infinite sets, such as Borel Conjecture, Whitehead’s problem or the automatic continuity for Banach Algebras, were proved independent, perhaps leaving an impression that most nontrivial statements about infinite sets can be neither proved nor refuted in ZFC.^{1} Moreover, Gödel’s incompleteness theorems imply the existence of statements whose consistency with ZFC can be proved using only strong axioms of infinity, so-called large cardinal axioms. A classical example is Banach’s ‘Lebesgue measure has a σ-additive extension to all sets of reals.’ While it is fairly easy to find a model in which this is false and there is no known ZFC-proof of its negation, proving the consistency of this statement requires assuming the existence of a measurable cardinal ([28]).

A remarkable result was proved by Shoenfield ([27]): every statement of the form (∃x ∈ ℝ)(∀y ∈ ℝ)ϕ(x, y), where all quantification in ϕ is over the natural numbers and all of its parameters are real numbers, is absolute between models of ZFC that are transitive and contain all countable ordinals. In this form Shoenfield’s theorem is best possible, as it cannot even be improved by adding one more alteration of quantifiers ranging over ℝ. However, a corollary that the truth of any Σ_{2}^{1} statement (i.e., one of the above syntactical form) cannot be changed by forcing turned out to be susceptible to far-reaching generalizations. One of the more striking results in modern set theory is that the existence of suitable large cardinals implies that the theory of the inner model L(ℝ) (the smallest inner model of ZF, the usual axioms of Set Theory without the Axiom of Choice, containing all real numbers) cannot be changed by set forcing (see [11, 19]). In particular, a sentence with real parameters and any number of alterations of quantifiers ranging over ℝ, has a fixed truth value that cannot be changed by forcing. The impact of large cardinals to sets of reals goes well beyond L(ℝ) to imply absoluteness of certain canonical sets of reals, the universally Baire sets ([9]), as defined below. A remarkable consequence is that the existence of large cardinals outright implies that all sets of reals in L(ℝ), and indeed all universally Baire sets, share all the classical regularity properties of Borel sets such as Lebesgue measurability.

Date: September 4, 2005.

The first author is partially supported by NSERC. The second author was supported in part by NSF grant DMS-0401603. 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.

1Shelah’s pcf-theory witnesses that this impression is false even in the realm of cardinal arithmetic, the subject that was considered essentially closed after Easton’s work in 1970.

The problem of precise calibration of the large cardinal axioms required to prove absoluteness for formulas of a given complexity is currently a very active field of research. In this paper we are taking a different line by proving forcing-absoluteness of sentences that are not statements of L(ℝ).

This impact of large cardinals does not extend to L(P(ℵ_{1})) (the smallest inner model of ZF containing all subsets of the first uncountable cardinal, ℵ_{1}) or to the closely related set-model H(ℵ_{2}) (the set of all sets whose transitive closure is of cardinality not greater than ℵ_{1}), however. Theories of these models are highly susceptible to forcing. For example, the Axiom of Choice implies that the Continuum Hypothesis can be expressed as ‘there exists a well-order of all reals all of whose proper initial segments are countable,’ a statement of these structures. Large cardinals imply that this reformulation of CH is false in L(ℝ), since such a well-order provides a non-Lebesgue measurable subset of the plane, while Cantor’s original reformulation, that every infinite set of reals is either countable or equinumerous with ℝ, holds in L(ℝ). Nevertheless, large cardinals do influence theory of ‘the uncountable,’ even in the context free of metamathematics. Todorcevic ([32]) has shown that the existence of class many Woodin cardinals influences the structure of Banach spaces satisfying Namioka’s ‘generic continuity principle.’ Todorcevic’s conclusion was previously shown to fail in L by Namioka and Pol.

Also, a number of highly nontrivial objects in H(ℵ_{2}) were constructed without the aid of additional set-theoretic axioms: gaps in P(ω)/Fin of Hausdorff and Luzin, special Aronszajn trees, to the more recent negative partition relations ([30]) and L-spaces ([23]). Statements asserting the existence of these objects are absolute simply because they are true. Lévy’s absoluteness theorem ([21]) states that all Σ_{1}-statements, ones of the form (∃X)ϕ(X), where all quantification in ϕ is over the natural numbers and all of its parameters are real numbers, are absolute between models of ZFC that are transitive. One consequence is that every Σ_{1}-statement true in the set-theoretic universe is already witnessed by a set in H(ℵ_{1}) (the set of all sets whose transitive closure is at most countable), thus Σ_{1}-statements reflect to L(ℝ). An absoluteness result that is genuinely about ω_{1} is a consequence of Keisler’s completeness theorem for the logic L_{ω_{1}ω}(Q) ([17]). It has been used to prove a couple of theorems for which no other proof, free of metamathematics, is known. Statements susceptible to Keisler’s theorem are Σ_{1}-statements of H(ℵ_{2}) expressed in an extension of the first-order logic that allows countably infinite conjunctions and has the quantifier ‘there exists uncountably many.’ It is not a consequence of Lévy’s theorem because the witness to Σ_{1} statement can be required to be uncountable. Describing the exact syntactical form of these statements is beyond this introduction (see §5). Keisler’s theorem allows ϕ to contain predicates for arbitrary Borel sets, and a desire to add arbitrary universally Baire predicates to these absoluteness results was the starting point of our investigation. As an application, we prove that for every suitably definable partition of n-tuples of reals the statement ‘there exists an uncountable homogeneous set’ is forcing-absolute (Proposition 7.3) and therefore all suitably defined ccc forcings are productively ccc.

While the majority of absoluteness results depend on the syntactical form of the sentence in question, we also prove a forcing-absoluteness conditioned on a semantical assumption. Statements (∃X)ϕ(X) of H(ℵ_{2}) for which a witness X̄ can be forced so that it is indestructible, in the sense that ϕ(X̄) holds in all further extensions in which ω_{1} is not collapsed, are forcing absolute (Theorem 2.2).

Our results can be expressed in the following form: if a sufficiently large rank initial segment of the universe of sets can be forced to satisfy a sentence ϕ, then there exists a model of ϕ already which has certain correctness properties. The properties we consider in this paper are the following.

(1) Containing any given ℵ_{1} many reals.

(2) Correctness about stationarity for subsets of ω_{1}.

(3) Correctness about any given universally Baire set of reals. The corresponding result for (1) above is essentially Woodin’s Σ_{1}^{2}-absoluteness result from CH ([35], see also [19]). After completing this work we have learned that the results for parts (2) and (3) were previously known to Woodin as well. In a sequel to this paper [8] we will give some additional properties.

Let us say a word about the proofs. A Σ_{1}^{2}-statement is the one of the form (∃A ⊆ ℝ)ϕ(A), where all quantifiers in ϕ range over real numbers and ϕ can have reals as parameters. Note that CH is an example of a Σ_{1}^{2} statement. Assuming suitable large cardinals (a bit stronger than the ones used for forcing-absoluteness of the theory of L(ℝ)), all Σ_{1}^{2} statements are absolute between forcing extensions satisfying CH. Moreover, every Σ_{1}^{2} statement that holds in some forcing extension (even those in which CH is false) holds in every forcing extension satisfying CH. One of the methods used in this note is extracted from Woodin’s proof; without assuming CH and applying Woodin’s construction we show that certain Σ_{1} statements true in the extension also hold in the ground model. We also use this method to prove an extension of Zapletal’s results on isolating cardinal invariants [37], originally proved by using the Σ_{1}^{2} absoluteness theorem. Woodin’s work on the partial order ℙ_{max} ([36]), and in particular the notion of an iterable model is used to show similar absoluteness results from a more modest large cardinal assumptions.

Organization of the paper. In §1 we introduce universally Baire sets and present a corollary to Woodin’s construction of ℙ_{max}. In §2 we use iterable structures to prove Σ_{1}-absoluteness for H(ℵ_{2}). In §3 we present a proof of the absoluteness for universally Baire sets between generic ultrapowers, due to John Steel. In §4 the proof of Σ_{1}^{2} absoluteness is modified to give Σ_{1} absoluteness for H(ℵ_{2}) for models containing any ℵ_{1} many reals. In §5 we enrich Keisler’s theorem by adding predicates for universally Baire sets of reals and the nonstationary ideal. Zapletal’s results on isolating cardinal invariants are extended §6. Applications are given in §7.1 and in §7.2 we prove that some (rather weak) large cardinal assumptions are necessary for some of our results. A related result of John Steel is briefly discussed in §7.3.

Terminology. We are using the standard set-theoretic terminology. Definitions of more advanced notions such as Woodin cardinals, ℙ_{max}, or the stationary towers ℙ_{<δ} and ℚ_{<δ} can be found e.g., in [36] or [19]. For the general theory of large cardinals see also [15].

1. Universally Baire sets and ℙ_{max}

We consider the reals ℝ to be ω^{ω}, the set of all ω-sequences of elements of ω equipped with the product topology. If γ is an ordinal, a tree on ω × γ is a subset of (ω × γ)^{<ω} closed under initial segments. If T is a such a tree, the projection p[T] of T is the set of x ∈ ω^{ω} for which there exists a z ∈ γ^{ω} such that (x↾n, z↾n) is in T for each n ∈ ω.

For a given cardinal κ, a set of reals A is κ-universally Baire if there exist trees T and S such that p[T] = A, p[S] = ω^{ω} \ A and T and S project to complements in every forcing extension by a partial order of cardinality κ (see [9]). A set is universally Baire if it is κ-universally Baire for each cardinal κ. A universally Baire set of reals then has a natural reinterpretation in every set forcing extension, the projection of T, for any T as above (it is a standard fact that this does not depend on the choice of T). This allows us to talk about properties of the set in these forcing extensions. If A is universally Baire, P is a partial order and G ⊂ P is a V -generic filter, we denote the reinterpretation of A in V [G] as A_{G} or A^{V^{P}}.

Universally Baire sets of reals, introduced in [9], tend to satisfy the standard regularity properties. For example, in the presence of a proper class of Woodin cardinals the model L(A, ℝ) satisfies AD^{+} whenever A is universally Baire ([36]). More specifically, in the presence of a proper class of Woodin cardinals universally Baire sets are ∞-homogeneously Suslin (see [22, 29, 19]), a property from which the usual regularity properties are more easily derived. We let Γ_{uB} denote the set of universally Baire set of reals, and let NS_{ω_{1}} denote the nonstationary ideal on ω_{1}.

In [36], Woodin introduces the partial order ℙ_{max}, and proves the following theorem (see also [20]).

Theorem 1.1. Suppose that there exist proper class many Woodin cardinals, and let A be a universally Baire set of reals. Let ϕ be a Π_{2} formula in the language of set theory with additional unary predicate symbols for NS_{ω_{1}} and A. Then if in some set forcing extension the structure

⟨H(ℵ_{2}); NS_{ω_{1}}, A^{∗}, ∈⟩

satisfies ϕ, where A^{∗} is the induced reinterpretation of A, then the structure

⟨H(ℵ_{2}); NS_{ω_{1}}, A, ∈⟩

satisfies ϕ in the ℙ_{max} extension of L(A, ℝ). □

The partial order ℙ_{max} is homogeneous, and so the conclusion of Theorem 1.1 can be interpreted as a statement about L(ℝ). In particular, it is still meaningful if no L(ℝ)-generic filter for ℙ_{max} exists. Since ℙ_{max} adds no reals, it is not necessary to reinterpret A in the conclusion of the theorem.

Theorem 1.1 has the following immediate corollary.

Corollary 1.2. Suppose that there exist proper class many Woodin cardinals, and let A be a universally Baire set of reals. Let ϕ be a sentence in the language of set theory with two additional unary predicate symbols for NS_{ω_{1}} and A, and suppose that ϕ and ¬ϕ are provably equivalent to Π_{2} sentences over H(ℵ_{2}) in the same expanded language. Then either ϕ holds in all set forcing extension or ϕ fails in all forcing extensions.

Proof. Otherwise ϕ and ¬ϕ both hold in the ℙ_{max} extension of L(A, ℝ), by Theorem 1.1. □

The results mentioned here hold for the language with a symbol for each universally Baire set, since each sentence can have only finitely many such symbols, and finitely many (indeed, countably many) universally Baire sets are easily combined into one.

2. Σ_{1}-absoluteness for H(ℵ_{2})

If ϕ is a Boolean combination of Σ_{1} sentences, then ϕ and ¬ϕ are clearly both Π_{2}. It follows from Corollary 1.2 that in the presence of suitable large cardinals, the truth value of such ϕ cannot be changed by set forcing, even with additional predicates for NS_{ω_{1}} and any given universally Baire set. Absoluteness for Boolean combinations of Σ_{1} sentences though follows immediately from absoluteness for Σ_{1} sentences, and, in fact, the only meaningful sentences ϕ we know of for H(ℵ_{2}) with the property that ϕ and ¬ϕ are provably equivalent to Π_{2} sentences are such Boolean combinations. While the proof of Theorem 1.1 is too long to present here (and in any case is presented in full in [36, 20]), we can present a self-contained proof of Σ_{1}-absoluteness, from a slightly weaker large cardinal assumption as well.

Theorem 2.1. Suppose that there exist two Woodin cardinals δ < λ, and let A be a λ^{+}-universally Baire set of reals. Let ϕ be a Σ_{1} sentence in the expanded language with two additional unary predicates. Let P be a partial order in V_{δ}. Then ϕ holds in the structure

⟨H(ℵ_{2}); NS_{ω_{1}}, A, ∈⟩

if and only if ϕ holds in

⟨H(ℵ_{2})^{V^{P}}; NS_{ω_{1}}^{V^{P}} , A^{V^{P}} , ∈⟩,

where A^{V^{P}} is the induced reinterpretation of A in the P -extension.

Proof. This will follow immediately from Theorem 2.8 proved below. □

Note the similarity with Levy’s absoluteness theorem. The similarly-looking assertion that H(ℵ_{2}) ≺_{Σ_{1}} H(ℵ_{2})^{P} is much stronger (it outright implies that P preserves ℵ_{1}). By [2], familiar bounded forcing axioms such as MA or BPFA are equivalent to the assertion that H(ℵ_{2}) ≺_{Σ_{1}} H(ℵ_{2})^{P} for all P in the corresponding class of forcings. Note that Theorem 2.1 cannot be extended to H(ℵ_{3}) since the non-absolute ‘2^{ℵ_{0}} ≥ ℵ_{2}’ is a Σ_{1} statement in this structure.

One way to state the idea behind the proof of Theorem 2.1 is that any sentence (with a parameter for some universally Baire set of reals) that can be forced to hold holds in some ℙ_{max} condition (Lemma 2.6). Almost all of the details of the proof appear in [36, 20], in proving that certain types of ℙ_{max} conditions exist. This proof gives another result of somewhat different nature, in which the assumption on the absolute formula ϕ is semantical, rather than syntactical.

2.1. Indestructible witnesses. A witness X for a formula (∃x)ϕ(x) is indestructible in a model N if for every transitive model M ⊇ N such that ω_{1}^{M} = ω_{1}^{N} and NS_{ω_{1}}^{M} ∩ N = NS_{ω_{1}}^{N} we have M ⊧ ϕ(X). To be precise, we are assuming that the first-order properties of set X imply its (possibly second-order) property asserted by ϕ. Typical indestructible witnesses are Hausdorff/Luzin gaps and special Aronszajn trees. In the first case, ‘zapping’ between two orthogonal ω_{1} towers in P(ω)/Fin assures that they cannot be separated by a single subset of ω (see [31, Theorem 8.6]). In the second case, an ω_{1}-tree is the union of countably many antichains, hence every branch defines a cofinal map from ω onto the height of the branch. Other standard constructions of objects of H(ℵ_{2}) usually yield indestructible witnesses ([30], [23]). The NS_{ω_{1}}-preserving assumption is nonvacuous, since to every stationary A ⊆ ω_{1} one can associate a partition of [ω_{1}]^{2} that has an uncountable homogeneous set iff A contains a club ([33]).

Theorem 2.2. If (∃x)ϕ(x) is a formula of H(ℵ_{2}) such that some forcing of size less than a Woodin cardinal forces an indestructible witness for it, then (∃x)ϕ(x) holds in H(ℵ_{2}).

Proof. Readers interested only in the proof of this theorem can skip all references to universally Baire and weakly homogeneously Suslin sets and read only the beginning of §2.3 and the relevant part of the proof of Lemma 2.6. By Lemma 2.6 (with A = ∅) there is an iterable model (N, NS_{ω_{1}}^{N}) and X ∈ H(ℵ_{2})^{N} such that N ⊧ ϕ(X) and X is indestructible. Let j: (N, NS_{ω_{1}}^{N}) → (N^{∗}, NS_{ω_{1}}^{N^{∗}}) be an iteration of length ω_{1} such that NS_{ω_{1}}^{N^{∗}} ∩N = NS_{ω_{1}}^{N}. Then Y = j(X) is an indestructible witness of ϕ in H(ℵ_{2})^{N^{∗}} = H(ℵ_{2}) ∩ N^{∗} and therefore H(ℵ_{2}) ⊧ ϕ(Y). □

Note that an anti-large cardinal assumption such as V=L implies the conclusion of Theorem 2.2 fails. One can strengthen Theorem 2.2 in an obvious way, by allowing parameters for universally Baire sets, adding an extra Woodin cardinal and appropriately weakening the indestructibility requirement. An axiom resembling the statement Theorem 2.2 was studied by Hamkins in [13].

2.2. Weakly homogeneously Suslin sets. We refer the reader to [15, p. 453^{+}], [36, pages 22–23], [29, §1], or [19, Definitions 1.3.4 and 1.3.6] for the definition of “weakly homogeneously Suslin tree/set of reals.” For every λ-weakly homogeneously Suslin tree T there exists a canonical tree S on ω×(2^{|T |})^{+} such that p[S] = ω^{ω} \p[T] (see [19, p. 23]). This is the so-called Martin–Solovay tree (see [29, Theorem 1.20]). These trees S and T project to complements in every forcing extension by a partial order of cardinality less than λ, and therefore λ-weakly homogeneously Suslin sets are λ-universally Baire. Weakly homogeneously Suslin sets will figure prominently in §3. The following is due to Woodin.

Theorem 2.3. Suppose that λ is a Woodin cardinal, and that A is a λ^{+}-universally Baire set of reals. Then A and ω^{ω} \ A are both < λ-weakly homogeneously Suslin.

Proof. This follows immediately from [19, Theorem 3.3.8]. □

The argument in the proof of the following is standard, and the theorem itself is a variation of standard facts. Since this exact statement does not seem to formally follow from the published results, we include the proof for the convenience of the reader.

Lemma 2.4. Let θ be a regular cardinal, suppose that T is a weakly homogeneous tree on ω×Z in H(θ), for some set Z. Let γ ≥ 2^{ω} be an ordinal such that there exists a countable collection Σ of γ^{+}-complete measures witnessing the weak homogeneity of T. Assume that there is a measurable cardinal in the interval (γ, θ).

Then for every elementary submodel X of H(θ) of cardinality less than γ with T, Σ, γ ∈ X, there is an elementary submodel Y of H(θ) containing X such that Y ∩ θ is uncountable, Y ∩ γ = X ∩ γ and p[T ∩ Y] = p[T].

Proof. Fixing θ, T, Σ and γ as in the statement of the theorem, the theorem follows from the following fact. Suppose that W is an elementary submodel of H(θ) of cardinality less than γ. Fix x ∈ p[T] and a countably complete tower {σ_{i} : i < ω} ⊂ Σ such that for all i < ω, {a ∈ Z^{i} : (x↾i, a) ∈ T } ∈ σ_{i}, and for each i < ω, let A_{i} = ⋂(σ_{i} ∩ W). Then since {σ_{i} : i < ω} is countably complete, there exists a z ∈ Z^{ω} such that for all i < ω, z↾i ∈ A_{i}. Then the pair (x, z) forms a path through T, and, letting

W [z] = {f(z↾i) | i < ω ∧ f: Z^{i} → H(θ) ∧ f ∈ W },

W [z] is an elementary submodel of H(θ) containing W and {z↾i : i < ω}, and, since each σ_{i} is γ^{+}-complete, W ∩ γ = W [z] ∩ γ.

Repeated application of this fact (starting with X) for each real in the projection of T produces a Y containing X such that Y ∩ γ = X ∩ γ, and p[T ∩ Y] = p[T]. Furthermore, Y will have cardinality less than γ.

If Y ∩ θ happens to be countable, then fix a measurable cardinal κ in Y greater than γ and a normal measure μ on κ. Then letting η be any member of ⋂(μ ∩ Y),

Y [η] = {f(η) | f: γ → H(θ) ∧ f ∈ Y }

is an elementary submodel of H(θ) end-extending Y below κ. Iterating this construction ω_{1} times produces an elementary submodel Y′ end-extending Y below κ with Y′ ∩ θ uncountable. □

The last paragraph of the preceding proof is needed only when the projection of T is analytic. Note also that the theorem implies an ostensibly stronger version where X is expanded to a Y capturing the projection of two weakly homogeneous trees in X, which in any case would be proved directly in the same way.

2.3. Iterable models. The proof of Theorem 2.1 will also use the following notion. ZFC^{0} is a fragment of ZFC that holds in H(θ) for a regular θ ≥ ℵ_{2} (the precise definition will not be needed here; see [20, §1]). If N_{0} is a transitive model of ZFC^{0} and I_{0} is a normal ideal on ω_{1}^{N_{0}} in N_{0}, then an iteration of (N_{0}, I_{0}) of length γ is ⟨(N_{η}, I_{η}), j_{ξη}, G_{η}, ξ < η ≤ γ⟩, where j_{ξη}: (N_{ξ}, I_{ξ}) → (N_{η}, I_{η}) is a commuting family of elementary embeddings, G_{η} ⊆ (P(ω_{1})/I_{η})^{N_{η}} is a generic filter, j_{ηη+1} is the corresponding generic ultrapower embedding, and for a limit η and ξ < η j_{ξη} and N_{η} are the direct limit of j_{ξζ} and N_{ζ} for ξ < ζ < η. An iteration is well-founded if all the models occurring in it are well-founded. A pair is iterable if all of its iterations are well-founded. If A ∈ N_{0} is a universally Baire set then a pair (N_{0}, I_{0}) is A-iterable if it is iterable and its iteration compute A correctly. We shall follow the standard convention and identify an iteration of length γ with the final model together with the embedding j_{0ξ}: (N_{0}, I_{0}) → (N_{γ}, I_{γ}). For more information we refer the reader to [36, 20]. The term ‘iterable model’ is also used to describe inner models of ZFC equipped with strategies for iterating extender-based ultrapowers. This notion will not be used in the present paper.

We will also use the following fact, due to Woodin (see [10, 12, 26, 36]). For our purposes, it is only important that presaturated ideals are precipitous: the corresponding generic ultrapower is forced to be well-founded.

Lemma 2.5. If δ is a Woodin cardinal, then after forcing with Coll(ω_{1}, <δ) the nonstationary ideal on ω_{1} is presaturated. □

Note that the following lemma also applies in the case when ϕ has additional predicates for NS_{ω_{1}} and a universally Baire set.

Lemma 2.6. Assume δ < λ are a Woodin and a measurable cardinal, A and ω^{ω} \A are δ^{+}-weakly homogeneously Suslin set of reals, and ϕ is a sentence whose truth is preserved after forcing which does not add reals. If P is a partial order in V_{δ} that forces ϕ, then there exists an A-iterable model (N, NS_{ω_{1}}^{N}) that satisfies ϕ.

Proof. Let θ be a regular cardinal greater than δ, and let X be a countable elementary submodel of H(θ) with δ, λ, A and P in X. For some fixed γ ∈ X \ δ there are countable sets of γ^{+}-complete measures in X witnessing that A and ω^{ω} \ A are weakly homogeneously Suslin. By Lemma 2.4 there is an elementary submodel Y of H(θ) such that

• X ⊂ Y,

• X ∩ γ = Y ∩ γ,

• Y ∩ θ is uncountable,

• there exist trees S, T on ω × η in X, for some ordinal η ∈ λ ∩ X, such that

p[S ∩ Y] = A and p[T ∩ Y] = ω^{ω} \ A. Now let M be the transitive collapse of Y, and let P̄, Ā, S̄, T̄, γ̄ be the respective images of P, A, S, T and γ under this collapse. Noting that V M ; γ̄ is countable, let N be a forcing extension of M by the forcing P̄ ∗ Coll(ω_{1}, <δ̄) as defined in M. Let A_{N} = p[S̄]. Since P̄ forces ϕ(A_{N}) and Coll(ω_{1}, <δ̄) adds no reals, N satisfies ϕ. By Lemma 2.5 the nonstationary ideal in N is precipitous. Furthermore, P(P(ω_{1}))^{N} is countable. Since N ∩ Ord is uncountable, [20, Lemma 1.5] implies (N, NS_{ω_{1}}^{N}) is iterable. Let j: (N, NS_{ω_{1}}^{N}) → (N^{∗}, NS_{ω_{1}}^{N^{∗}}) be an iteration. The trees S̄ and T̄ project to complements in N (in V, in fact), and, from the point of view of V, p[S̄] ⊂ p[j(S̄)] and p[T̄] ⊂ p[j(T̄)]. Since N^{∗} ⊧ p[j(S̄)] ∩ p[j(T̄)] = ∅, and this fact is absolute, it follows that j(A_{N}) = p[j(S̄)] ∩ N^{∗} = A ∩ N^{∗} and j((ω^{ω})^{N} \ A_{N}) = p[j(T̄)] ∩ N^{∗} = (ω^{ω} \ A) ∩ N^{∗}. Therefore, N^{∗} is correct about A, and we have proved (N, NS_{ω_{1}}^{N}) is A-iterable. □

It only remains to prove that the iterable structures are robust under small forcing.

Lemma 2.7. Assume δ is a Woodin cardinal and A is δ-universally Baire. If a pair (N, NS_{ω_{1}}^{N}) is A-iterable then it is A-iterable in the forcing extension by any forcing P in V_{δ}.

Proof. Iterability is a Π_{2}^{1} property and it is therefore absolute (see [20, Remark 1.3]). Let S and T be trees witnessing the δ-universally Baireness of A, with p[S] = A. Fix a well-founded iteration j: (N, NS_{ω_{1}}^{N}) → (N^{∗}, NS_{ω_{1}}^{N^{∗}}). We need to check that p[S]∩j(N ∩(ω^{ω} \A)) = p[T]∩j(N ∩A) = ∅. The existence of a real z ∈ p[S]∩j(N ∩ (ω^{ω} \ A)) is witnessed by a path x through S with first coordinate projection equal to z, a real y coding an iteration of (N, NS_{ω_{1}}^{N}) (of possibly illfounded ordertype) and an embedding π from the ordertype of this iteration into δ. There is a natural tree (with S as its first two coordinates and functions from ω into δ as its last coordinate) such that any such triple z, y, π corresponds to a path through the tree. Since the wellfoundedness of this tree is absolute between wellfounded models, we conclude p[S] ∩ j(N ∩ (ω^{ω} \ A)) = ∅. The argument for the nonexistence of a real z ∈ p[T]∩j(N ∩A), for j some wellfounded iteration of (N, NS_{ω_{1}}^{N}), is identical. □

Theorem 2.8. Suppose that there exist two Woodin cardinals δ < λ, and let A be a λ^{+}-universally Baire set of reals. Let ϕ be a Σ_{1} sentence in the expanded language with two additional unary predicates. Then the following are equivalent.

(1) ϕ holds in the structure ⟨H(ℵ_{2}); NS_{ω_{1}}, A, ∈⟩.

(2) There is an A-iterable pair (N, NS_{ω_{1}}) such that N ⊧ ϕ.

(3) ϕ holds in ⟨H(ℵ_{2})^{V^{P}}; NS_{ω_{1}}^{V^{P}} , A^{V^{P}} , ∈⟩ for every (some) partial order P in V_{δ}.

Proof. Assume the weaker variant of (3) holds, and let P ∈ V_{δ} be such that every condition in P forces ϕ to hold. By Theorem 2.3, A and ω^{ω} \ A are <λ-weakly homogeneous, and Lemma 2.6 implies (2).

Assume (2) holds, and let (N, NS_{ω_{1}}^{N}) be an A-iterable model for ϕ. There is an iteration j of (N, NS_{ω_{1}}^{N}) with final model N^{∗} such that NS_{ω_{1}}^{N^{∗}} = N^{∗} ∩ NS_{ω_{1}} (this can be assured by a straightforward bookkeeping argument, see [36] or [20]). Since the iteration is correct about A, ω_{1}, and NS_{ω_{1}}, the witness for ϕ in N^{∗} is a witness for ϕ in V, and therefore (1) holds.

Applying Lemma 2.6 with P being the trivial forcing gives that (1) implies (2). Finally, assume (2). By Lemma 2.7, an A-iterable model in which ϕ holds remains

A-iterable after forcing with any P ∈ V_{δ} and therefore we may apply the implication from (2) to (1) to conclude the proof of (3). □

Remark 2.9. Theorem 2.8 (and other results in this paper) have natural reinterpretations in terms of Woodin’s Ω-logic (see [34]). Briefly, given suitable large cardinals, there is a universally Baire set of reals A such that if M is an A-closed model (in the sense of [34]) then in M every set is a member of an inner model containing a Woodin cardinal below a measurable cardinal κ (of M), such that this inner model is iterable (in V) by some measure on κ in M. Given this fact, the arguments in this section show that if ϕ is a Σ_{1} statement for ⟨H(ℵ_{2}), NS_{ω_{1}}, ∈⟩, then ϕ holds in V if and only if it holds in some A-closed model. Similar arguments are discussed in [20].

3. Weakly homogeneously Suslin sets and stationary tower embeddings

Handling the predicates for universally Baire sets requires Theorem 3.1 below (see [19, Theorem 1.7.1 and Theorem 1.7.2] for more on this result, and §2.2 for the definitions).

Theorem 3.1 (Steel). Assume tree T is λ-weakly homogeneously Suslin for an inaccessible λ, P is ℚ_{<δ} or ℙ_{<δ} for δ < λ. If S is the Martin–Solovay tree such that p[S] = ω^{ω} \ p[T] then the generic embedding k: V → M satisfies k(S) = S.

This is [19, Theorem 3.3.17] and the case when T is λ-homogeneous is proved in [29, Corollary 4.6(1)]. Since the proof is only outlined in [19], we include some more details for the convenience of the reader. The proof relies on two lemmas, in which we assume λ, P, δ and k are as in Theorem 3.1.

Lemma 3.2. Assume μ is a |P |^{+}-complete ultrafilter on κ^{<ω}. Then P forces

j_{k(μ)} ↾ Ord = j_{μ} ↾ Ord .

Proof. The proof closely follows the proof of [19, Lemma 1.7.3]. Let M ⊆ V [G] be an inner model such that k: V → M. Let

X = {f: k(κ^{<ω}) → Ord |f ∈ M}
Y = {g: κ^{<ω} → Ord |g ∈ V }.

Define π: X → Y via (π(f))(s) = f(k(s)). We claim the following.

(1) For each f ∈ dom(π) there exists g: κ^{<ω} → Ord in V and A ∈ μ such that (π(f))(s) = g(s) for all s ∈ A.

(2) For each g: κ^{<ω} → Ord in V there exists an A ∈ μ and a f ∈ dom(π) such that (π(f))(s) = g(s) for all s ∈ A.

Once proved, (1) and (2) will imply that π^{∗}: X/k(μ) → Y/μ defined by π^{∗}([f]_{k(μ)}) = [π(f)]_{μ} is a bijection. We will then show that it is an order-isomorphism.

We work in V below some p ∈ P throughout. To prove (1), fix an f: k(κ^{<ω}) → Ord and a P -name τ for f. For each s ∈ κ^{<ω} fix p_{s} ≤ p and γ_{s} such that p_{s}⊩(π(τ))(š) = γ̌_{s}. Since μ is |P |^{+}-complete there exist A ∈ μ and q ≤ p such that for all s ∈ A we have q = p_{a}. Define g: κ^{<ω} → Ord via g(s) = γ_{s} for all s ∈ κ^{<ω}. Then q⊩(π(τ))(š) = g(š) for all s ∈ A.

To prove (2), fix a g: κ^{<ω} → Ord in V. For each s ∈ κ^{<ω} find p_{s} ≤ p, a_{s} ∈ P and h_{s}: a_{s} → Ord such that p_{s}⊩[ȟ_{s}]_{G} = ǧ(š) (see [19, §2.2]). Since μ is |P |^{+}-complete there exist A ∈ μ, q ≤ p and a ∈ V_{δ} such that for all s ∈ A we have q = p_{s} and a = a_{s}. Define F: a → Ord^{κ^{<ω}} by letting (F (X))(s) be h_{s}(X) when s ∈ A and 0 otherwise. We wish to see that for each s ∈ A, q forces that π([F]_{G})(s) (which is [F]_{G}(k(s)) by definition) is equal to g(s). This follows from the fact that q forces that h_{s} represents g(s) in the embedding k, the constant function X ↦ s represents k(s), and F (X)(s) = h_{s}(X) for all X ∈ a.

In order to check π^{∗} is order-preserving, we closely follow the proof of [19, Claim 3 on page 11] to prove the following.

(3) For all A ⊆ κ^{<ω} in V and C ⊆ k(κ^{<ω}) in M such that A ∈ μ and C ∈ k(μ)

we have k[A] ∩ C ≠ ∅.

Fix A and C and p ∈ P. By extending p if necessary we may find a p′ below p such that C = [h]_{G} for some h: a → μ with p′ ≤ a. Since μ is |P |^{+}-complete, there is an A ∈ μ which is contained in h(X) for all X ∈ a. Then k(s) ∈ C for all s ∈ A.

Since (3) immediately implies π^{∗} is order-preserving, we conclude π^{∗} is an isomorphism. Fix an ordinal γ. Then j_{μ}(γ) = [g]_{μ} for a function g: κ^{<ω} → Ord in V that is constantly equal to γ. Similarly, j_{k(μ)}(γ) = [f]_{k(μ)} for f: κ^{<ω} → Ord in M that is constantly equal to γ. Since π(f) = g, the conclusion follows. □

Lemma 3.3. Assume μ_{0} is a λ-complete ultrafilter on κ^{i_{0}} and μ_{1} is a λ-complete ultrafilter on κ^{i_{1}} that projects to μ_{0}. Then P forces

j_{k(μ_{0})k(μ_{1})} ↾ Ord = j_{μ_{0}μ_{1}} ↾ Ord .

Proof. The proof is very similar to the proof of Lemma 3.2 and we omit it. □

Proof of Theorem 3.1. This is analogous to the proof of [19, Theorem 1.3.14], but using Lemma 3.3 instead of [19, Lemma 1.1.25]. As in [19, p. 23], S is the increasing union of trees S_{γ} (γ < (2^{|T |})^{+}) and each S_{γ} is defined using only j_{μ_{i}μ_{j}} ↾ γ, where μ_{i} (i < ω) is an enumeration of λ-complete measures witnessing T is weakly homogeneous. By Lemma 3.3, j_{j_{E}(μ_{i})j_{E}(μ_{j})} ↾ Ord = j_{μ_{i}μ_{j}} ↾ Ord for all i, j. Furthermore, S is definable from |T |^{+} in L({j_{μ_{i}μ_{j}} ↾ |T |^{+} : i, j < ω}), and so, since j(|T |^{+}) = |T |^{+}, j(S) = S. □

Theorem 3.4. Assume there are class many Woodin cardinals. Let A be a universally Baire set in V and let V [G] be a set forcing extension of V in which j: V → M is a V -generic elementary embedding obtained via forcing with ℙ_{<δ} or ℚ_{<δ}. Then in V [G], j(A) = A_{G}.

Proof. Fix an inaccessible λ greater than δ and the rank of the partial order for which G is a generic filter. By Theorem 2.3, A and its complement are respectively the projections of λ-weakly homogeneous trees T_{0} and T_{1} which project to complements in V [G]. By Theorem 3.1, we have trees S_{0} and S_{1} in V such that

• p[S_{0}] = A,

• p[S_{1}] = ω^{ω} \ A,
• the pairs (S_{0}, T_{1}) and (S_{1}, T_{0}) project to complements in V [G],
• j(S_{0}) = S_{0},
• j(S_{1}) = S_{1}.

By the absoluteness of well-foundedness of trees, j(A) = (p[S_{0}])^{M} = A_{G} ∩ M. □

Corollary 3.5. Assume there are class many Woodin cardinals and let A be a universally Baire set. Suppose j_{0} : V → M_{0} and j_{1} : V → M_{1} are stationary tower embeddings existing in some forcing extension of V. Then j_{0}(A) ∩ M_{1} = j_{1}(A) ∩ M_{0}. □

Proof. Let δ_{i}, G_{i} be a Woodin cardinal an generic corresponding to j_{i} for i < 2. Pick an inaccessible λ > max(δ_{0}, δ_{1}) and a λ-homogeneously Suslin tree S such that A = p[S]. By Theorem 3.4 the conclusion follows. □

Remark 3.6. Note that Theorem 3.4 (as well as corresponding variants of Corollary 3.5) remain true if δ < ζ for an inaccessible ζ and j: V_{ζ} → M. This remark will be used in the proof of Theorem 4.1.

Remark 3.7. It is well-known that analogues of Theorem 3.4 and Corollary 3.5 hold for generic ultrapowers obtained from precipitous ideals. This is a consequence of an appropriate analogue of Theorem 3.1, also due to Steel (see [19, Theorem 1.7.1, also Theorem 1.7.3]).

4. Σ_{1}^{2}-absoluteness with predicates for universally Baire sets and NS_{ω_{1}}

Theorem 4.1 below subsumes Woodin’s Σ_{1}^{2}-absoluteness theorem, and is proved in this section by a generalization of his proof. An ‘elementary ’ proof (one without using the machinery of stationary tower forcing) can be obtained by modifying Todorcevic’s proof of the Σ_{1}^{2}-absoluteness theorem as presented in [6]. Instead it uses the Lévy collapse followed by P(ω_{1})/I, for a saturated ideal I defined in the collapse. Such a forcing is regularly embedded into the stationary tower by [10].

Theorem 4.1. 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.

(1) Suppose that some partial order P ∈ V_{κ} forces the existence of a model N of ϕ (with the additional symbol interpreted as A^{V^{P}}) containing the reals with the property that NS_{ω_{1}}^{N} = NS_{ω_{1}} ∩N. Then for every every set Z of reals of cardinality ℵ_{1} there exists a model M of ϕ (with the additional symbol interpreted as A∩M) containing Z with the property that NS_{ω_{1}}^{M} = NS_{ω_{1}} ∩M.

(2) Suppose that there exists a model M of ϕ (with the additional symbol interpreted as A) containing the reals with the property that NS_{ω_{1}}^{M} = NS_{ω_{1}} ∩M. Then after forcing with any partial order P ∈ V_{κ}, for any set of reals Z of cardinality ℵ_{1} there exists a model N of ϕ (with the additional symbol interpreted as A^{V^{P}} ∩N) containing Z with the property that NS_{ω_{1}}^{N} = NS_{ω_{1}} ∩N.

The case when ϕ is a Σ_{1} formula of H(ℵ_{2}) implies the conclusion of Theorem 2.1, and the case when ϕ is a Σ_{1}^{2} formula implies Woodin’s theorem.

If D is a collection of stationary sets (i.e., sets in ℙ_{∞}), then we say that a set X captures D if there exists a d ∈ D ∩ X such that X ∩ (∪d) ∈ d.

Say that a strongly inaccessible cardinal κ is robust if the following holds in every forcing extension by a partial order in V_{κ}: for every b ∈ ℚ_{<κ} and every f: b → P(ω_{1}) \ NS_{ω_{1}} the set of countable X ≺ V_{κ+1} such that

• X captures every predense D ⊂ ℚ_{<κ} in X,

• o. t.(X ∩ κ) ∈ f(X ∩ (∪b)) is stationary and compatible with every member of ℚ_{<κ}. The function X ↦ ot(X ∩ α) represents α in any ℚ_{<κ′} or ℙ_{<κ′} embedding for κ′ > α (for ℙ_{<κ} this is [19, Fact 2.2.10] and the proof for ℚ_{<κ} is similar). Therefore, the requirement that o. t.(X ∩ κ) ∈ f(X ∩ (∪b)) ensures that κ will be in the set represented by f in any stationary tower embedding derived from ℚ_{<κ′} or ℙ_{<κ′} for some κ′ > κ by a filter containing the set above.

If κ is a measurable Woodin cardinal, then the set of robust Woodin cardinals is in every normal measure on κ. Aside from the condition that o. t.(X∩κ) ∈ f(X∩(∪b)), this follows from Lemma [19, Lemma 2.7.14]. The remaining part follows from the fact that if κ is measurable, then every countable elementary submodel of V_{κ+2} can be end-extended (as in the last paragraph of the proof of Lemma 2.4), and so the stationarity of the desired set reflects to a member of every normal measure on κ.

For a strongly inaccessible cardinal λ, let a(λ) be the set of X ≺ V_{λ+1} such that (1) o. t.(X ∩ λ) = ω_{1},

(2) X captures every predense D ⊂ ℚ_{<λ} in X,

(3) letting X̄ be the transitive collapse of X, there exists a closed unbounded

set C ⊂ X̄ ∩ ω_{1} such that • each member of C is a robust Woodin cardinal in X̄,

• for each limit point γ of C, if E ∈ P(γ)X̄ is a club subset of γ, then

E contains a tail of C ∩ γ.

Let us say that λ is full if it is a Woodin cardinal and a(λ) is stationary.

Lemma 4.2. Every measurable Woodin cardinal κ is full. Moreover, for any normal uniform measure on κ full cardinals form a set of measure one.

Proof. Except for the robustness requirement, the proof adapted from Woodin’s proof of Σ_{1}^{2} absoluteness ([35]) was given in [19, Claim on page 94]. The additional requirement of robustness does not change the proof, though, as the proof used only the fact that the set of Woodin cardinals below a measurable Woodin is in every normal measure, which holds for robust Woodin cardinals as well. □

Lemma 4.3. If λ is full and δ ≥ λ then in ℙ_{<δ} the condition a(λ) forces j(ω_{1}) = λ and G ∩ V_{λ} is V -generic for ℚ_{<λ}. Also, it forces that there is a club C ⊂ λ in M such that

(a) each member of C is a robust Woodin cardinal in V_{λ},

(b) for each limit member γ of C and each club subset E of γ in V_{λ}, E contains a tail of C ∩ γ.

Proof. We have j(ω_{1}) = λ by (1) and [19, Corollary 2.2.11]. Condition (2) implies the ℚ_{<λ} genericity of G. Since a(λ) ∈ G and ⋃ a(λ) = V_{λ+1}, by [19, Fact 2.2.8] we have j[V_{λ+1}] ∈ j(a(λ)). Now V_{λ}, being the transitive collapse of j[V_{λ}], is an element of M and (a) and (b) follow by (3). □

Lemma 4.4. Assume λ is full, δ > λ is Woodin, and G ⊆ ℙ_{<δ} is V -generic below a(λ) with j: V → M the corresponding generic embedding. Then in M for every forcing P ∈ V_{λ} we can find a V -generic h ∗ H ⊆ P ∗ ℚ_{<λ}. Furthermore, we can arrange that the H-generic ultrapower of V [h] is correct for NS_{ω_{1}}, and contains any given Z ⊆ (V_{λ})^{V [G∩ℚ_{<λ}]} of cardinality ℵ_{1} in M.

Proof. Let ζ be a strongly inaccessible cardinal in V between λ and δ. Since M is closed under sequences of length less than δ in V [G] ([19, Theorem 2.5.8]), V_{ζ} and G ∩ V_{λ} are in M. Note that V is not included in M, but all the dense subsets of P ∗ℚ_{<λ} in V belong to V_{ζ}. Hence it will suffice to build a V_{ζ} generic h∗H ⊆ P ∗ℚ_{<λ}.

Since P(ℙ)^{V} is countable in V [G ∩ V_{λ}], by [19, Theorem A.0.9] we may fix a V -generic filter h ⊂ ℙ in M ∩ V [G ∩ V_{λ}]. Let C be a club as in Lemma 4.3. Now, ℙ is ρ-c.c. for some ρ < λ, so for every regular ξ ≥ ρ, every club subset of ξ in V [h] contains a club set in V, which shows that members of C \ρ (which we may assume is the same as C) retain properties (a) and (b) in V [h]. Let Z = {x_{α} : α < λ}.

Fix a partition in M of ω_{1}^{M} into stationary sets A_{α} (α < ω_{1}). Working in M we will produce a continuous increasing sequence of ordinals ⟨η_{α} : α < ω_{1}⟩ ⊂ C and a sequence ⟨H_{α} : α < λ⟩ such that

(c) each H_{α} is a V [h]-generic filter contained in ℚ_{<η_{α}}^{V [h]},
(d) each x_{α} ∈ (V [h][H_{α+1}])_{ζ},
(e) α < α′ implies H_{α′} ∩ (V [h])_{η_{α}} = H_{α}.

(Note that (d) is equivalent to x_{α} ∈ V [h][H_{α+1}] but the latter is not a statement of M.) Our V [h]-generic filter H ⊂ ℚ_{<λ} will be ⋃_{η<ω_{1}} H_{η}. As we do this, for each

b ∈ ℚ_{<λ}^{V [h]} and each function f: b → (P(ω_{1}) \ NS_{ω_{1}})^{V [h]} we will associate some A_{β} and ensure that A_{β} ∩ {η_{α} : α < ω_{1}} ⊂ [f]_{H}, which ensures that the final image model will be correct about NS_{ω_{1}}.

We let η_{0} be the least member of C and let H_{0} be any V [h]-generic filter contained in ℚ_{<_{η_{0}}} .

For the successor stages of the construction, given H_{η_{α}} ⊂ ℚ_{<η_{α}}, if η_{β} ∈ A_{β} and the function f associated to A_{β} has domain in ℚ_{<η_{α}}, then we let a_{α} be the set of countable elementary submodels of (V [h])_{η_{α}+} which witnesses the robustness of η_{α} in V [h] for f. Then for any γ > η_{α} in C, letting

ℚ_{<γ}(a_{α}) = {b ∈ ℚ_{<γ} | b ≤ a_{α}},

the quotient (ℚ_{<γ}(a_{α})/ℚ_{<η_{α}})^{V [h]} is a ℚ_{<η_{α}}-name in V [h] for a partial order such that, in V [h],

ℚ_{<η_{α}} ∗ (ℚ_{<γ}(a_{η_{α}})/ℚ_{<η_{α}}) ≅ ℚ_{<γ}(a_{η_{α}γ}),

and such that η_{α} is in the set represented by f.

Since each set of the form {h, x_{α}, H_{α}} exists in a generic extension of V by a forcing in V_{λ}, if x_{α} is not in V [h][H_{α}] then x_{α} is generic over V [h][H_{α}] for some forcing in (V [h][H_{α}])_{λ}, and by [19, Theorem A.0.9] that forcing can be subsumed by

(ℚ_{<γ}(a_{η_{α}})/ℚ_{<η_{α}})_{H_{α}}^{V [h]}

for some γ > η_{α} in C, and we can meet condition (d) by letting η_{α+1} be this γ. At limit stages α of our construction, if we let

η_{α} = sup{η_{β} : β < α}

then every predense set in (ℚ_{<η_{α}})^{V [h]} is predense in (ℚ_{<β})^{V [h]} for a club set of β < η_{α}. But each of these clubs intersects {η_{β} : β < α}, which shows that H_{α} = ⋃{H_{β} : β < α} is V [h]-generic for (ℚ_{<η_{α}})^{V [h]}. Let C^{∗} = {η_{α} : α < ω_{1}}. Since C^{∗} is a club subset of λ, H = ⋃{H_{α} : α < ω_{1}} is V [h]-generic for ℚ_{<λ}. □

Proof of Theorem 4.1. (1) We closely follow the proof in [19, p. 94]. Let A, κ, ϕ and P be as in the statement of the theorem. Let λ < κ be a full Woodin cardinal with P ∈ V_{λ}. Since κ is a limit of Woodin limits of Woodin cardinals, we may fix a Woodin limit of Woodin cardinals δ greater than λ. Now let G ⊂ ℙ_{<δ} be V -generic with a(λ) ∈ G, and let j: V → M be the corresponding generic embedding. It suffices to show that the conclusion of the theorem holds in M for j(A), since then it holds in V by elementarity.

By Lemma 4.4 find V -generic h ∗ H ⊆ P ∗ ℚ_{<λ} in M. If ζ is the first inaccessible above λ in V, then V_{ζ} ⊆ M and in M we can define j^{∗}: V_{ζ}[h] → M^{∗} the generic embedding. We have j^{∗}(ω_{1}) = λ by Lemma 4.3.

There is a model N of ϕ in M^{∗} which with the additional symbol in ϕ interpreted as j^{∗}(A_{h}) (where A_{h} is the reinterpretation of A in V [h]) such that N contains the reals of M^{∗} and is correct in M^{∗} about ω_{1} and NS_{ω_{1}}. Since A is absolute between M and M^{∗} by Corollary 3.5 (see also Remark 3.6) and M^{∗} is correct in M about ω_{1} and NS_{ω_{1}}, this model N is correct about these things in M as well. Furthermore, we can arrange that M^{∗}, and thus N, contains j(Z), where Z is any family of ℵ_{1}-many reals in V. Elementarity implies that there exists such a correct model in V as well.

(2) By [19, Theorem 2.5.10] (due to Woodin), if δ is a Woodin cardinal and some sentence ψ holds in some initial segment of the universe below δ, then ψ can be forced to hold in some initial segment of the universe by a partial order of cardinality δ after forcing with any partial order in V_{δ}. By Theorem 3.4 and the proof of Theorem 2.5.10 in [19], this fact holds even when one adds a predicate for a given universally Baire set to the language. Part (2) then follows from part (1) of Theorem 4.1. □

5. Universally Baire sets and L(Q)

If Γ is a pointclass let L^{Γ} be an extension of the first-order logic with formulas in which we have

(1) the quantifier Qx, interpreted as ‘there exists uncountably many,’

(2) a predicate NS for the nonstationary ideal on ω_{1},

(3) predicates for all sets in Γ,

(4) constants for all hereditarily countable sets.

Definition 5.1. If ϕ is a sentence of L^{uB} we say that a model 𝔛 of ϕ is correct if the conditions below are satisfied.

(5) The universe X of 𝔛 is a subset of H(ℵ_{1}),

(6) all universally Baire predicates and NS as well as all constants occurring in ϕ are interpreted correctly,

(7) this model is standard: it interprets Qx as ‘there exist uncountably many.’ If Γ is the class of all universally Baire sets then we write L^{uB} for L^{Γ}. For a L^{Γ} sentence ϕ such that Γ=Borel and Γ does not involve the predicate NS the statement ‘ϕ has a correct model’ is absolute between transitive models of ZFC. This folklore consequence of Keisler’s completeness theorem for L_{ω_{1}ω}(Q) ([17]) was stated explicitly in [7]. An apparently stronger result in which ϕ is allowed to have countable conjunctions is still true. We drop infinitary sentences since in our context where we are dealing only with ω-models they would not add to the expressive power of the language.

Theorem 5.2. Suppose κ < δ are Woodin cardinals and ϕ is a sentence in L^{uB}. Then ϕ has a correct model in a forcing extension by a partial order in V_{κ} if and only if ϕ has a correct model in V.

Proof. Let A code all universally Baire sets occurring in ϕ. Since ‘ϕ has a correct model’ is a Σ_{1} sentence in ⟨H(ℵ_{2}); NS_{ω_{1}}, A, ∈⟩, this is a consequence of Theorem 2.1.

□

Theorem 5.3. Suppose κ < δ are Woodin cardinals, κ is full, and ϕ is a sentence in L^{uB}.

(1) If ϕ has a correct model containing all the reals in a forcing extension by a partial order in V_{κ} then for any Z ∈ P_{ℵ_{2}}(ℝ) there is a correct model of ϕ containing Z.

(2) If ϕ has a model containing all the reals in V, then it has a model containing any given ℵ_{1}-many reals in any forcing extension by a poset in V_{κ}.

Proof. Let A be the universally Baire set occurring in ϕ. If N is a model of ZFC that correctly computes A, ω_{1} and NS_{ω_{1}}, then a correct model for ϕ in N is also correct in V. Therefore (1) and (2) are consequences of Theorem 4.1 (1) and (2), respectively. By the proof of Theorem 4.1, one needs only that κ is a full Woodin cardinal below a Woodin cardinal. □

Corollary 5.4. If there exists a proper class of Woodin cardinals and ϕ is a formula of L^{uB}, then the set of reals x such that ϕ(x) has a correct model is universally Baire.

Proof. Let X be the set of all reals r such that ϕ(r) has a correct model. Assume that G ⊆ ℚ_{<δ} is a generic filter and j: V → M is the induced generic embedding. If r ∈ ℝ^{M}, then ϕ(r) has a correct model in M if and only if it has a correct model in V [G]. This follows from the fact that M and V [G] have the same reals, and Theorems 2.6 and 3.1, with P in Theorem 2.6 as the trivial forcing. (The existence of a correct model in either of M and V [G] gives rise to a countable A-iterable model - for the relevant universally Baire set A - which can be iterated to produce a correct model in the other.)

By Theorem 5.2, ϕ(r) has a correct model in V [G] if and only if it has a correct model in V [r], an extension by a forcing in V_{δ}. By Woodin’s Tree Production Lemma ([19, Theorem 3.3.15] or [29, Theorem 4.2]) applied with ψ(x) being ‘ϕ(x) has a correct model,’ we conclude that X = {r | ϕ(r) has a correct model} is universally Baire. □

As above, in the following corollary one needs only a proper class of full Woodin cardinals.

Corollary 5.5 (CH). If there exists a proper class of measurable Woodin cardinals and ϕ is a formula of L^{uB}, then the sets of reals x such that ϕ(x) has a correct model containing all the reals is universally Baire.

Proof. Analogous to the proof of Corollary 5.4, but using Theorem 5.3. The one key difference is in showing that V [r] and M agree about whether ϕ(r) has a correct model, in the situation where λ is a full Woodin cardinal, j: V → M′ is the generic embedding induced by a V -generic filter G′ ⊂ ℚ_{<λ} and r ∈ ℝ^{M′}. Forcing over V [G′], we may fix for some Woodin cardinal δ > λ a V -generic G ⊂ ℙ_{<δ} with G ∩ V_{λ} = G′ and a(λ) (as in Section 4) in G. Then there is an elementary embedding from M′ to M with critical point greater than λ which fixes the images of the universally Baire sets from V. Furthermore, M′ contains all subsets of λ in V [G′]. If there exists a correct model of ϕ in V [r], then the proof of Lemma 4.4 shows that there is one in M and so there exists one in M′. If there exists a correct model N in M′, then it suffices to show that N is correct in V [G′]. Since M, M′ and V [G] agree about the universally Baire sets from V, the only issue here is whether NS_{ω_{1}}^{V [G′]} ∩ N = NS_{ω_{1}}^{N}. This follows from the fact that NS_{ω_{1}}^{M} ∩ N = NS_{ω_{1}}^{N} and every club subset of λ in V [G′] is in M. □

The well-known fact that CH and large cardinals imply every Σ_{1}^{2} set is universally Baire (e.g., [19, Theorem 3.3.10]) is an immediate consequence of Corollary 5.5. A Σ_{1}^{2} well-ordering of the reals can be forced starting from any model of ZFC ([1]) and therefore an additional assumption such as CH is necessary here.

In the absence of large cardinals there can exist a formula ϕ with a correct model in V such that some P forces ϕ has no correct models even with Γ = Π_{1}^{1} (Proposition 7.8).

6. Isolating cardinal invariants

Definition 6.1. Assume that ϕ(A) is a formula whose quantifiers range over countable ordinals, and let E ⊂ ℝ^{2} be universally Baire. A set A ⊂ ℝ is ϕ, E-covering if it satisfies ϕ(A) ∧ (∀x ∈ ℝ)(∃y ∈ A)(x, y) ∈ E.

Every tame cardinal invariant as in [37, §B.2] is equal to the minimal size of some ϕ, E-covering set. This includes a large number of standard cardinal invariants of the continuum, and in particular all the invariants occurring in Cichon’s diagram (see [5], [4] for the theory of cardinal invariants). In [37] it was required that ϕ is arithmetic and E is projective (in our case, ϕ is absolute for forcings which preserve ω_{1}). With these additional assumptions, Theorem 6.7 and Corollary 6.3, as well as the auxiliary lemmas below, are due to Zapletal. The cardinal invariants known not to be tame, such as 𝔥 ([37, B.25]) or 𝔤 ([37, B.26]) cannot be expressed as the minimal size of a ϕ, E-covering set either as Theorem 6.3 fails for them.

Let us introduce some of the machinery from [37, §3]. The following technical definition applies to most σ-ideals used in the theory of forcing.

Definition 6.2. A σ-ideal I on the reals such that the collection of all codes for analytic sets in I is given by a universally Baire definition is a universally Baire ideal. An ideal I is iterable and almost full if the following hold.

(1) It is a universally Baire σ-ideal.

(2) Every positive universally Baire set has a positive Borel subset.

(3) The forcing Borel/I is proper in all forcing extensions.

By (2), forcings Borel/I and P(ℝ)/I are forcing equivalent in L(ℝ) and other standard inner models of AD, in the presence of a proper class of Woodin cardinals. Futhermore (in the presence of class many Woodin cardinals), Definition 6.2 describes ideals that are both iterable (see [37, 3.1.1]) and almost full ([37, 2.2.6]) in Zapletal’s terminology. This follows from [37, Claim 3.1.3].

Recall that cov(I) is the smallest size of a subset of I whose union covers the real line. Let cov^{+}(I) be the smallest size of a subset of I whose union covers an I-positive Borel set. If the ideal I is homogeneous, in the sense that for every Borel I-positive set B there is a Borel isomorphism f: B → ℝ such that f[A] ∈ I iff A ∈ I for all A ⊆ B, then clearly cov(I) = cov^{+}(I).

The following is an immediate consequence of Theorem 6.7 proved below.

Theorem 6.3. Assume there are class many Woodin cardinals, ϕ, E are as in Definition 6.1, and let μ be the smallest cardinality of a ϕ, E covering set. Let I be an iterable and almost full σ ideal. Then cov^{+}(I) > μ can be forced if and only if the countable support iteration of Borel/I of length ω_{2} forces this. □

A set A is ϕ, E, I-covering if for every I-positive Borel set B and Borel function f: B → ℝ there is x ∈ A such that

{y ∈ B : (f(y), x)) ∈ E}

contains an I-positive Borel set.

If P is a forcing notion then we say A is ϕ, E, P -covering if for every P -name for a real τ and every p ∈ P there is regular subordering Q of {q ∈ P : q ≤ p} that is forcing-equivalent to Borel/I for a universally Baire ideal I such that τ is a Q-name and A is ϕ, E, I-covering. Typically, P will be a countable support iteration of some quotients Borel/I.

Lemma 6.4. Assume there are class many Woodin cardinals, P is a proper forcing notion, and A is ϕ, E, P -covering. Then P forces A is ϕ, E covering.

Proof. Assume τ is a P -name for a real and p ∈ P. Find a regular suborder Q of P such that τ is a Q-name and forcing equivalent to Borel/I for some universally Baire ideal I below p. Since Q is proper, by [37, Lemma 2.2.1] there is a Borel function f: ℝ → ℝ such that Q forces τ = f(ṙ), where ṙ is the canonical generic real for Borel/I. Find y ∈ A such that {x ∈ ℝ | (f(x), y) ∈ E} contains an I-positive Borel set, B. Then B forces (τ, y) ∈ E because the set C = {z | (f(z), y) ∈ E} is universally Baire (this follows from our large cardinal assumption since C is projective in E, see [19, Exercise 3.3.11]), B ⊆ C and ṙ is forced to belong to B. □

We shall drop references to ϕ, E and write I-covering instead of ϕ, E, I-covering whenever ϕ and E are clear from context.

Let I be a σ-ideal on ℝ and α < ω_{1}. For B ⊆ ℝ^{α} let T_{B} = {s ∈ ⋃_{β<α} ℝ^{β} : s = x ↾ β for some x ∈ B}. A set B ⊆ ℝ^{α} is I-perfect ([37, 3.1.4, 3.2.2] if

(1) For every s ∈ T_{B} the set {r ∈ ℝ : sˆ r ∈ T_{B}} is I-positive, and

(2) T_{B} is σ-closed: if s_{n} (n ∈ ω) is an increasing sequence in T_{B} then ⋃_{n∈ω} s_{n} ∈

T_{B}.

There is another natural way to define when B ⊆ ℝ^{α} is ‘large’ with respect to I introduced in [37, 3.2.1]. Consider a game G(B) of length α in two players, Adam and Eve. Adam plays first at all limit stages and his move is always a set A_{ξ} ∈ I. Eve plays reals x_{ξ} (ξ < α) so that ⟨x_{ξ} : ξ < η⟩ ∈ T_{B} for all η and x_{ξ} ∉ A_{ξ} for all ξ. If at some stage Eve is unable to make a move, then Adam wins. Otherwise Eve wins. The family of all sets for which Adam has a winning strategy is denoted by I^{α}. Clearly I^{1} = I. It is not difficult to see that I^{α} is a σ-ideal and that all I-perfect subsets of ℝ^{α} are I^{α}-positive.

Lemma 6.5 (Zapletal, [37, 3.4.1]). Assume there are class many Woodin cardinals. If I is iterable and almost full then every universally Baire set in ℝ^{α} is either in I^{α} or it contains a Borel I-perfect subset.

Proof. We shall only point to the main ingredients of the proof, as the reader can find the details in [37]. First, the large cardinal assumption implies all perfect information games of fixed countable length in which the opponents are playing reals with a universally Baire payoff are determined, and moreover the winning strategy can be coded as a universally Baire set of reals ([24, Exercise 2E.11]). Adam’s moves in the game G(A) need not be coded as reals, but Zapletal defines an auxiliary game H(A) with this property that is equivalent to G(A). Therefore A ⊆ ℝ^{α} is not in I^{α} if and only if Eve has a winning strategy in G(A) if and only if Eve has a universally Baire winning strategy in H(A). Second, Eve has a universally Baire winning strategy in H(A) if and only if A contains an I-perfect Borel subset. □

The following was essentially proved by Zapletal ([37, Claim 5.1.18]).

Lemma 6.6. Assume there are class many Woodin cardinals. Assume ϕ(A), E are as in Definition 6.1 and I is iterable and almost full.

(1) For every α < ω_{1}, every ϕ, E-covering set of size < cov^{+}(I) is ϕ, E, I^{α}- covering.

(2) Every ϕ, E-covering set of size < cov^{+}(I) is ϕ, E, P -covering, where P is any countable support iteration of Borel/I.

Proof. (1) By induction on α we show that an I-covering set A of size < cov^{+}(I) is I^{α}-covering. By Lemma 6.5, for all β every I^{β}-positive universally Baire set contains a Borel I-perfect subset. Assume B ⊆ ℝ^{α} is I-perfect, f: B → ℝ is Borel, and towards obtaining a contradiction assume

B_{y} = {z ∈ B : (f(z), y) ∈ E}

is in I^{α} for all y ∈ A. For y ∈ A let τ_{y} be a winning strategy for Adam in the I-perfect game for B_{y}. We construct a sequence ⟨x_{ξ} : ξ < α⟩ of Eve’s simultaneous responses to all τ_{y} in G(B).

If s = ⟨x_{η} : η < ξ⟩ have been chose, let Z_{ξ} = ⋃_{y∈A} Z_{ξ,y}, where Z_{ξ,y} ∈ I is the set provided to Adam by τ_{y} as a response to Eve’s moves, coded by s ∈ T_{B}. Note that this is not necessarily a legal move in G(B) for Adam since Z_{ξ} need not be in I. Since each Z_{ξ,y} is in I we have that Z_{ξ} does not cover the set X = {r : sˆ r ∈ T_{B}} (because this set is universally Baire and I-positive, by almost fullness of I it contains a Borel I-positive set). Eve extends s by picking x_{ξ} ∈ X \ Z_{ξ}. This shows that Eve can play at any successor stage of the game. Since T_{B} is σ-closed and B is I-perfect, Eve wins the game. The obtained sequence belongs to B \ ⋃_{y∈A} B_{y}, contradicting our assumption.

(2) This is a consequence of (1). It is well-known (see [37, §3.1]) that for every condition B in a countable support iteration P_{κ} of Borel/I of any length there is α < ω_{1} and a regular subalgebra Q of P_{κ} forcing-equivalent to the algebra of Borel subsets of ℝ^{α} modulo I^{α} and such that every positive set contains an I-perfect positive subset. Since the assumption on I being iterable implies the iteration is proper, Q can be chosen so that any given name for a real is a Q-name. □

We can finally state and prove the main theorem of this section.

Theorem 6.7. Assume there are class many full Woodin cardinals. For ϕ, E as in Definition 6.1 and an iterable and almost full I the following are equivalent.

(1) In some forcing extension there is a ϕ, E-covering set A of size < cov^{+}(I).

(2) In some forcing extension there is an A that is ϕ, E, I^{α}-covering for all α < ω_{1}.

(3) In every forcing extension satisfying CH there is an A that is ϕ, E, I^{α}- covering for all α < ω_{1}.

(4) A countable support iteration of Borel/I of length ω_{2} forces there is a ϕ, Ecovering set A of size ℵ_{1}.

Proof. If I is a universally Baire σ ideal then the set I^{∗} of codes for Borel members of ⋃_{α<ω_{1}} I^{α} is also universally Baire. Then ‘there exists A which is ϕ, E, I^{α}-covering for all α < ω_{1}’ is a Σ_{1}^{2}-formula in I^{∗} and E. Therefore, (2) implies (3) by Theorem 5.3. Since a countable support iteration P_{ω_{2}} of length ω_{2} of Borel/I forces CH in an intermediate model, (3) implies (4) by Lemma 6.4. Since P_{ω_{2}} forces cov^{+}(I) > ℵ_{1},

(4) implies (1). Finally, (1) implies (2) is Lemma 6.6. □

7. Concluding remarks

7.1. Applications. In this section let Γ be a pointclass such that the conclusion of Theorem 2.1 holds for all ϕ whose predicates for universally Baire sets are restricted to sets in Γ. If Γ ⊆ Borel then the results below are provable in ZFC.

For B ⊆ ω_{1} let B^{∗} = {x ∈ ℝ : x codes an ordinal in B} be its code.

Proposition 7.1. Assume B ⊆ ω_{1}. If B^{∗} ∈ Γ then there is a club C ⊆ ω_{1} that is either contained in or disjoint from B.

Proof. Assume B is stationary. Then in an ω_{1}-preserving forcing extension in which no new reals are added there is a club D ⊆ B. Then there is a function f: ω_{1} → ω_{1} such that for every α < ω_{1} closed under f we have α ∈ B^{∗}. By Theorem 2.1 such a function exists in V and therefore B contains a club. □

Proposition 7.2. (1) If Γ ⊇ P(ℝ)^{M} for some inner model M such that ω_{1}^{M} =

ω_{1} then ω_{1} is measurable in M.

(2) If Γ contains all codes for subsets of ω_{1} constructible from x then x^{#} exists.

Proof. (1) By Proposition 7.1 the club filter on ω_{1} in M is an ultrafilter. (2) By Proposition 7.1, the club filter on ω_{1} is an L[x]-ultrafilter. □

If n ≥ 1 then [X]^{n} = {s ⊆ X | |s| = n}. For K ⊆ [X]^{n} a set Y ⊆ X is K-homogeneous if [Y]^{n} ⊆ K.

Proposition 7.3. For every partition [ℝ]^{n} = K_{0} ∪K_{1} such that K_{0} is a continuous image of a set in Γ the statement ‘there is an uncountable K_{0}-homogeneous set’ is forcing-absolute.

Proof. Let A be such that f[A] = K_{0} for some continuous f. Note that the graph of f is in Γ since it is Borel. Let ϕ be a sentence ‘there exist an uncountable X ⊆ ℙ and Y ⊆ A such that [X]^{n} ⊆ f[Y]’ and apply Theorem 2.1. □

The ZFC case of Proposition 7.3, when Γ = Borel was proved in [18]. By Proposition 7.8 this theorem is optimal since even the Π_{1}^{1} case cannot be proved in ZFC. It is known (see [25]) that for a Borel K ⊆ [ℝ]^{2} ‘there exists an uncountable K-homogeneous set’ is strictly weaker than ‘there exists a perfect K-homogeneous set.’ Therefore Proposition 7.3, as well as the following two propositions, do not follow from forcing-absoluteness for universally Baire sets of reals.

A forcing notion ℙ is in Γ if ℙ ⊆ ℝ and ℙ, ≤_{ℙ} and ⊥_{ℙ} are all in Γ. Proposition 7.3 immediately implies the following.

Proposition 7.4. If P is a ccc forcing in p[Γ] (the pointclass of continuous images of sets in Γ) then it is productively ccc. □

In particular, assuming a proper class of Woodin cardinal exists all universally Baire ccc posets are productively ccc. In [3] productiveness of various projective ccc forcings with ccc forcings in Solovay’s model was proved, starting from more modest large cardinal assumptions. The case when Γ is Borel is a well-known result of Shelah ([14]).

A variant of Proposition 7.3 may be worth stating. If A ⊆ X ×Y and x ∈ X then A_{x} = {y | (x, y) ∈ A}. First note that if there are class many Woodin cardinals and A ⊆ ℝ^{2} is universally Baire, then the set B = {x | A_{x} is uncountable} is universally Baire. This is because under our assumption every set projective in a universally Baire set is universally Baire [19, Exercise 3.3.11]) and x ∈ B if and only if (∃y ∈ ℝ^{ℕ})(∀z ∈ A_{x})(∃n ∈ ℕ)z = y(n). A higher-dimensional variant of this fact is also true.

Proposition 7.5. Assume there are class many measurable Woodin cardinals. If n ≥ 1 and A ⊆ ℝ×[ℝ]^{n} is universally Baire, then the set {x | there is an uncountable Y ⊆ ℝ such that [Y]^{n} ⊆ A_{x}} is universally Baire.

Proof. With ϕ(x, A) being an L^{uB}-formula ‘there is an uncountable A_{x}-homogeneous set of reals’ this is an immediate consequence of Corollary 5.4. □

We leave other applications, such as those involving homogeneous sets for square bracket partition relations or homogeneous clubs, to an interested reader.

7.2. Limitations. The case of Theorem 5.3(5.2) when ϕ ∈ L^{Borel} and it does not include a predicate for NS_{ω_{1}} is a well-known ZFC consequence of Keisler’s completeness theorem for L_{ω_{1}ω}(Q) ([17]). It was apparently stated explicitly for the first time in [7]. This was proved by associating an L_{ω_{1}ω}(Q) sentence ϕ^{M} in an expanded language to each L^{Borel} sentence ϕ such that a (reduction of a) standard model for ϕ^{M} is a correct model for ϕ. By Proposition 7.7 below this method cannot be applied if Γ includes all Π_{1}^{1} sets. The proof relies on the following observation, communicated to us by Boban Velickovic and included here with his kind permission (A, E are unary and binary relation symbols and A, E are their interpretations).

Lemma 7.6. Assume ϕ is an L_{ω_{1}ω}(Q) sentence in language including {A, E} such that (A, E)^{𝔛} is an uncountable well-ordering in some correct model 𝔛 of ϕ. Then (A, E)^{𝔜} is not a well-ordering in some corect model 𝔜 of ϕ.

Proof. We assume familiarity with the theory of L_{ω_{1}ω}(Q), as presented in [17]. Assume the contrary. Let α = sup{o. t.(A, <)^{(𝔜,q)}|(𝔜, q) a weak model of ϕ}. Since the set of all weak models of ϕ is Borel, by the Boundedness Theorem ([16, Theorem 31.2]) α is countable. Let M be a countable transitive model of a large enough fragment of ZFC such that ω_{1}^{M} > α. By Keisler’s theorem, there exists a correct model 𝔜 of ϕ in M. If q = {B ⊆ Y |B is definable and uncountable in 𝔜} then (𝔜, q) is a weak model of ϕ and o. t.(A, E)^{𝔜} > α, a contradiction. □

Proposition 7.7. There is a Π_{1}^{1} set A such that there is no L_{ω_{1}ω}(Q) sentence ϕ in language containing a predicate A for A with the property that all standard models of ϕ are correct about A.

Proof. Assume the contrary, that for every Π_{1}^{1} set A there is a sentence ϕ such that every standard model of ϕ is correct about A. Let A be the Π_{1}^{1} set of all subsets ℕ^{2} that code a well ordering. Let ϕ be a sentence of L_{ω_{1}ω}(Q) such that each standard model of ϕ is correct for A. Let ψ be the conjunction of ϕ and the sentence ‘E is an ω_{1}-like ordering of B and every proper initial segment is order-isomorphic to some x ∈ A.’ Then in every model of ψ we have that E is a well-ordering of B in type ω_{1}, contradicting Lemma 7.6. □

Proposition 7.7 in particular shows that the approach of [7] cannot be applied to prove the version of Theorem 5.3(5.2) for L^{Π_{1}^{1}}. The following Proposition shows that the version of Theorem 5.3(5.2) for L^{Π_{1}^{1}} cannot be proved in ZFC.

Proposition 7.8. If the conclusion of Theorem 2.1 holds for all ϕ in L^{Π_{1}^{1}} then ω_{1} is inaccessible in L.

Proof. Assume otherwise. Let x be a real such that ω_{1}^{L[x]} = ω_{1}. Then there exists an an uncountable Π_{1}^{1}(x) set A with no perfect subset. Then ‘A has an uncountable subset’ is a sentence of L^{Π_{1}^{1}} true in V but false in its extension obtained by collapsing ω_{1}. □

Assume ϕ is a sentence of L_{ω_{1}ω}(Q) whose language includes {X, E} such that the interpretation of (X, E) is an ω_{1}-like linear order in every model of ϕ. Many arguments using L_{ω_{1}ω}(Q) in set theory would be simplified if the statement W (ϕ) Sentence ϕ has a model in which the interpretation of (X, E) is a well-

ordering were known to be forcing-absolute.

Proposition 7.9. Assume there are class many full Woodin cardinals. Using the notation from the last paragraph, W (ϕ) is forcing-absolute.

Proof. By [19, Theorem 2.5.10] it will suffice to show that if W (ϕ) holds in a forcing extension then it holds in V. Assume W (ϕ) holds in some forcing extension. By the construction from Theorem 4.1(1) there is a transitive model M^{∗} of ZFC with correct ω_{1} such that W (ϕ) holds in M^{∗}. Then a standard well-founded model of ϕ is a standard well-founded model of ϕ in V. □

The conclusion of Proposition 7.9 has some large cardinal strength.

Proposition 7.10. Assume W (ϕ) is forcing-absolute for every ϕ in L_{ω_{1}ω}(Q). Then ω_{1} is inaccessible in L.

Proof. Assume ω_{1} = ω_{1}^{L(x)} for a real x, and fix an uncountable thin Π_{1}^{1}(x) set B. Let A be the Π_{1}^{1} set of codes for countable ordinals. Then B = f^{−1}(A) for some continuous function f. Let ϕ be an L_{ω_{1}ω}(Q) formula in the language {A, B, f, X, E} saying:

(1) A, B are sets of reals,

(2) each element of B codes a countable linear ordering,

(3) E is an ω_{1}-well-ordering of a set X,

(4) each initial interval (−∞, x] of (X, E) is coded by some element of B,

(5) The interpretation of f is the restriction of f to the reals of the model,

(6) A is the f-preimage of B. If in a model of ϕ the interpretation of (B, E) is well-founded, then it is correct about B and A. But such a model contains uncountably many elements of A, therefore if ω_{1}^{L(x)} is collapsed then ϕ cannot have such models. □

7.3. Special trees in L(ℝ). A consequence of Theorem 2.1 is that if T ⊆ ℝ^{<ω_{1}} is a tree coded by a universally Baire set, then large cardinals imply that the statement ‘T has an ω_{1}-branch’ is forcing-absolute. Such an ω_{1}-branch constructs an ω_{1}- sequence of reals and therefore cannot exist in L(ℝ, T), but it is natural to ask whether it is possible to determine whether T has an ω_{1}-branch in V by working in the model L(ℝ, T). It turns out that this question has already been considered.

After the first author presented some of our results at the Annual Meeting of ASL at Stanford in March 2005, John Steel communicated Theorem 7.12 to us. The following definition is also due to him.

Assume T ⊆ ℝ^{<ω_{1}} is coded by a universally Baire set. Write

σT = {p ∈ ℝ^{<ω_{1}} | (∀α < dom(p))p ↾ α ∈ T }.

If there is a function g such that g(p) is a surjection from ω onto dom(p) for every p ∈ σT we say that T is specialized by g. Every tree that is covered by countably many antichains is specialized by a function definable from the sequence of antichains. In the presence of the Axiom of Choice every tree is specialized by a function, but the following shows that this is the right notion in the context of L(ℝ). A ‘universally Baire function’ is a function whose graph is a universally Baire set of pairs of reals.

Lemma 7.11. Assume there are two Woodin cardinals δ < λ and T is a universally Baire tree specialized by a universally Baire function g. Then T has no ω_{1} branches.

Proof. Assume the contrary. By Theorem 2.3 both T and g are weakly homogeneously Suslin, and by Lemma 2.6 there is a T, g-iterable model (N, NS_{ω_{1}}^{N}) satisfying ‘T has an ω_{1}-branch,’ p. (We only need NS_{ω_{1}}^{N} to be precipitous and the generic ultrapower to be correct about T and g.) Let j: N → N^{∗} be the generic ultrapower embedding. Then p = j(p) ↾ ω_{1}^{N} belongs to N^{∗}, hence by elementarity and T -correctness p ∈ T. Thus g(p), a surjection from ω onto ω_{1}^{N}, is a real in N^{∗}. If τ is a NS_{ω_{1}}^{+}-name in N for g(p), then it is forced that τ = g(p), and therefore g(p) ∈ N, a contradiction. □

Lemma 7.11 has a converse.

Theorem 7.12 (Steel). Suppose 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:

• T has an uncountable branch in V.

• T is specialized by a function in L(ℝ). □

The relevance of the theorem is that for each Σ_{1} statement ϕ for ⟨H(ℵ_{2}); A, ∈⟩, where A is a set of reals in L(ℝ) as in Theorem 2.1 there is a tree in L(ℝ) which has an uncountable branch if and only if ϕ holds. The second conclusion of the theorem is a statement in L(ℝ), and thus forcing-absolute. The theorem then gives an absolute impediment witnessing the failure of a given Σ_{1} statement. At a key place in the proof of Theorem 7.12 a rather deep result from the inner model theory is employed to construct a T -iterable model (see §2.3) of ‘T has an ω_{1}-branch.’ It would be interesting to find an ‘elementary’ proof of this theorem and to extend it to the context of arbitrary universally Baire sets. As pointed out to us by Stuart Zoble, extending to arbitrary universally Baire sets necessitates a different proof since the required inner model theory result is not known to be true in this context. We would also like to thank Richard Ketchersid for discussions on this topic.

References

[1] Uri Abraham and Saharon Shelah. Coding with ladders a well ordering of the reals. J. Symbolic Logic, 67(2):579–597, 2002.

[2] Joan Bagaria. Bounded forcing axioms as principles of generic absoluteness. Arch. Math. Logic, 39(6):393–401, 2000.

[3] Joan Bagaria and Roger Bosch. Solovay models and forcing extensions. J. Symbolic Logic, 69(3):742–766, 2004.

[4] T. Bartoszynski. Invariants of measure and category. In M. Foreman and A. Kanamori, editors, Handbook of Set Theory. to appear.

[5] A. Blass. Cardinal invariants of the continuum. In M. Foreman and A. Kanamori, editors, Handbook of Set Theory. to appear.

[6] I. Farah. A proof of the Σ_{1}^{2}-absoluteness theorem. preprint available at http://www.math.yorku.ca/∼ifarah, 2005.

[7] I. Farah, M. Hrušák, and C.A. Martínez Ranero. A countable dense homogeneous set of size ℵ_{1}. Fund. Math., to appear. preprint available at http://www.math.yorku.ca/∼ifarah.

[8] I. Farah, P.B. Larson, and M. Magidor. Absoluteness for universally Baire sets and the uncountable II. in preparation, 2005.

[9] Q. Feng, M. Magidor, and W.H. Woodin. Universally baire sets of reals. In H. Judah, W. Just, and W.H. Woodin, editors, Set Theory of the Continuum, pages 203–242. Springer-Verlag, 1992.

[10] M. Foreman and M. Magidor. Large cardinals and definable counterexamples to the continuum hypothesis. Ann. Pure Appl. Logic, 76:47–97, 1995.

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

[12] N. Goldring. Woodin cardinals and presaturated ideals. Ann. Pure Appl. Logic, 55:285–303, 1992.

[13] J.D. Hamkins. A simple maximality principle. The Journal of Symbolic Logic, 68:527–550, 2003.

[14] Jaime I. Ihoda and Saharon Shelah. Souslin forcing. J. Symbolic Logic, 53:1188–1207, 1988.

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

[16] A.S. Kechris. Classical descriptive set theory, volume 156 of Graduate texts in mathematics. Springer, 1995.

[17] H. J. Keisler. Logic with the quantifier “There exists uncountably many”. Annals of Mathematical Logic, 1:1–93, 1970.

[18] Wiesław Kubiś and Saharon Shelah. Analytic colorings. Ann. Pure Appl. Logic, 121(2-3):145– 161, 2003.

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

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

[21] A. Lévy. A hierarchy of formulas in set theory, volume 57 of Memoirs of the Amer. Math. Soc. 1965.

[22] D.A. Martin and J. Steel. A proof of projective determinacy. Journal of the American Mathematical Society, 2:71–125, 1989.

[23] J.T. Moore. A solution to the L space problem and related ZFC constructions. preprint, 2004.

[24] Itay Neeman. The determinacy of long games, volume 7 of de Gruyter Series in Logic and its Applications. Walter de Gruyter GmbH & Co. KG, Berlin, 2004.

[25] S. Shelah. Borel sets with large squares. Fund. Math., 159:1–50, 1999.

[26] S. Shelah and W.H. Woodin. Large cardinals imply that every reasonably definable set of reals is Lebesgue measurable. Israel Journal of Mathematics, 70:381–394, 1990.

[27] J.R. Shoenfield. The problem of predicativity. In Y. Bar-Hillel et al., editors, Essays on the Foundations of Mathematics, pages 132–142. The Magens Press, Jerusalem, 1961.

[28] R. Solovay. Real-valued measurable cardinals. In D. Scott, editor, Axiomatic set theory, volume 13 of Proceedings of symposia in pure mathematics, pages 397–428. 1971.

[29] J. Steel. The derived model theorem. preprint, available at http://math.berkeley.edu/∼steel/, 2003.

[30] S. Todorcevic. Partitioning pairs of countable ordinals. Acta Math., 159:261–294, 1987.

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

[32] S. Todorcevic. Universally meager sets and principles of generic continuity and selection in Banach spaces. preprint, 2004.

[33] S. Todorcevic. Stationary sets and partitions of [ω_{1}]^{2}. handwritten note, May 1997.

[34] W. Hugh Woodin. Set theory after Russell: the journey back to Eden. In One hundred years of Russell’s paradox, volume 6 of de Gruyter Ser. Log. Appl., pages 29–47. de Gruyter, Berlin, 2004.

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

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

[37] J. Zapletal. Descriptive set theory and definable forcing. Mem. Amer. Math. Soc., 167(793):viii+141, 2004.

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: larsonpb@muohio.edu
   URL: http://www.users.muohio.edu/larsonpb/