THREE DAYS OF Ω-LOGIC

PAUL B. LARSON

The Zermelo-Fraenkel axioms for set theory with the Axiom of Choice (ZFC) form the most commonly accepted foundations for mathematical practice, yet it is well-known that many mathematical statements are neither proved nor refuted from these axioms. One example is given by Gödel’s Second Incompleteness Theorem, which says that no consistent recursive axiom system which is strong enough to describe arithmetic on the integers can prove its own consistency. This presents a problem for those interested in finding an axiomatic basis for mathematics, as the consistency of any such theory would seem to be as well justified as the theory itself. There are many views on how to resolve this situation. While some logicians propose weaker foundations for mathematics, some study the question of how to properly extend ZFC. Large cardinal axioms and their many consequences for small sets have been studied as a particularly attractive means to this goal. Large cardinals resolve the projective theory of the real line and banish the various measure-theoretic paradoxes derivable from the Axiom to Choice from the realm of the definable. Moreover, the large cardinal hierarchy itself appears to serve as universal measuring stick for consistency strength, in that the consistency strength of any natural statement of mathematics (over ZFC) can be located on this hierarchy (see [7] for the definitive reference on large cardinals).

While there is no technical definition of “large cardinal,” Woodin’s Ω-logic is an attempt to give a formal definition for the set of consequences of large cardinals for rank initial segments of the universe. Two definitions are proposed. The first, a form of generic invariance, is called the semantic relation: a theory T is said to imply a statement φ in Ω-logic if φ holds in every rank initial segment satisfying T in every set forcing extension (we deal only with set forcing in this article). Another more elaborate notion, involving a correctness property with respect to universally Baire sets of reals, plays the role of proofs. Woodin’s Ω-conjecture is the statement that these two definitions are in fact equivalent. That the proof relation implies the semantic relation is already known (see Theorem 6.4).

The research of the author is supported by NSF grant DMS-0801009. This article is based on lectures given by the author while he was a JSPS Visiting Professor, and prepared in part while he was visiting the Mittag-Leffler Institute.

Cantor’s Continuum Hypothesis (CH), the statement that the cardinality of the set of real numbers is the least uncountable cardinal, is an important test case for those hoping to find correct extensions of ZFC. By a theorem of Levy and Solovay [12], large cardinals cannot settle the Continuum Hypothesis, as it is always possible to force to change the truth value of CH. Indeed, CH may be least complex natural statement of mathematics not resolved by large cardinals, as large cardinals decide the theory of the inner model L(ℝ) (and larger models) in Ωlogic. In his study of Ω-logic, Woodin has proposed a new approach to resolving CH. Assuming certain unresolved questions about the definability of Ω-logic, any statement implying generic invariance for the theory of H(ℵ_{2}) implies that CH is false. Moreover, the definability of Ω-logic calls into question the idea that generic invariance should be a necessary condition for extensions of ZFC. We briefly survey these arguments in Subsections 8.4 and 8.5.

This paper is a slightly polished version of a lecture series on Ωlogic given at Nagoya University in November of 2009. As such it is a quick tour through the basic concepts of Ω-logic, giving proofs or sketches of proofs when appropriate. We have not attempted to address some of the more technical issues surrounding Ω-logic, such as current attempts to pin down its complexity or to prove the Ωconjecture. There is a significant overlap with other presentations of Ω-logic, such as [1, 2, 21, 22, 23, 24, 25, 26]. None of the results presented here is due to the author. In Sections 1, 2 and 5-9, all results are due to Woodin unless otherwise noted.

Finally, I am very happy to have the chance to contribute to this special issue in honor of Yuzuru Kakuda, who sponsored me for a very enjoyable and productive year as a JSPS postdoctoral fellow at Kobe University in 1999-2000. I would also like to thank the organizers and attendees of this lecture series for their support and attention.

1. The stationary tower

The stationary tower is a partial order developed by Woodin [20], following on a theorem of Foreman, Magidor and Shelah [5] that it is possible, starting from a supercompact cardinal, to force to make the nonstationary ideal on ω_{1} precipitous without collapsing ω_{1}.

Definition 1.1. A set a is club if ⋃ a is nonempty and there is a function F: (⋃ a)^{<ω} → ⋃ a such that a is the set of Y ⊆ ⋃ a closed under F. A set a is stationary if ⋃ a is nonempty and a intersects every club subset of P(⋃ a), i.e., if for every function F: (⋃ a)^{<ω} → ⋃ a there is a Y ∈ a such that F [[Y]^{<ω}] ⊆ Y.

Note that this agrees with the usual notion of stationarity for an unbounded subset of a regular cardinal κ (for clubs, the situation is slightly different : given a club C ⊆ κ, the limit points of C are the closure points of the function α ↦ min(C \ (α + 1))). On the other hand, any set is stationary if it has a (nonempty) ⊆-largest member.

Example 1.2. Given any nonempty set X, the set of Y ⊆ X such that (Y, ∈) is an elementary submodel of (X, ∈) contains a club. For any infinite cardinal κ ≤ |X|, the set of subsets of X of cardinality κ is stationary.

The intersection of countably many clubs is club, and the intersection of a club set with a stationary set is stationary. We let [X]^{ℵ_{0}} denote the set of countable subsets of a given set X.

Fact 1.3. Suppose that X_{0} ⊆ X_{1} are nonempty sets.

• If a ⊆ P(X_{0}) is stationary, then so is {Y ⊆ X_{1} | Y ∩ X_{0} ∈ a}.

• If a ⊆ [X_{0}]^{ℵ_{0}} is stationary, then so is {Y ∈ [X_{1}]^{ℵ_{0}} | Y ∩X_{0} ∈ a}.

• If a ⊆ P(X_{1}) is stationary, then so is {Y ∩ X_{0} | Y ∈ a}.

Proof. The third is the easiest, since we can extend any F: X_{0}^{<ω} → X_{0} to a function F′: X_{1}^{<ω} → X_{1}, and if Y ∈ a is closed under F′, then Y ∩ X_{0} is closed under F.

For the other two, given a function F: X_{1}^{<ω} → X_{1} there is a function F′: X_{1}^{<ω} → X_{1} with the property that F′[Y^{<ω}] is closed under F and contains Y, for all Y ⊂ X_{1} (F′ essentially codes all the F -terms). Then if Y ∈ a is closed under F′ ↾ X_{0}^{<ω} (modified to take some fixed value in X_{0} when F′ takes values outside of X_{0}) , then F′[Y^{<ω}] is closed under F and F′[Y^{<ω}] ∩ X_{0} = Y. □

Definition 1.4. Given a (strongly inaccessible) cardinal κ, the stationary tower ℙ_{<κ} is the partial order whose domain is the set of stationary sets in V_{κ}, where a ≤ b if and only if Y ∩ ⋃ b ∈ b, for all Y ∈ a. The (countable) stationary tower ℚ_{<κ} is the same order, restricted to the set of stationary sets in V_{κ} which consist of countable sets.

Forcing with either ℙ_{<κ} or ℚ_{<κ} induces an elementary embedding, using functions f: a → V, for stationary sets a in the generic filter. Given a relation R in {∈, =}, and functions f: a → V and g: b → V, with a and b in the generic filter G we set fRg in the generic ultrapower if and only if

{Y ⊂ ⋃ a ∪ ⋃ b | f(Y ∩ ⋃ a)Rg(Y ∩ ⋃ b)} ∈ G.

We let [f]_{G} denote the element of the generic ultrapower represented by f.

Fact 1.5. If a is stationary and f(Y) ∈ Y for all Y ∈ a, then f is constant on a stationary set.

Proof. Otherwise, for each z ∈ ⋃ a, choose g_{z}: (⋃ a)^{<ω} → ⋃ a witnessing that f^{−1}[{z}] is nonstationary. Let h: (⋃ a)^{<ω} → ⋃ a be a function such that h(z, σ) = g_{z}(σ) for all σ ∈ (⋃ a)^{<ω}. Then any Y ∈ a closed under h gives a contradiction. □

Fact 1.5 gives the following.

Fact 1.6. For any set Z, the identity function on P(Z) represents j[Z] in the ℙ_{<κ}-generic ultrapower, and the identity function on [Z]^{ℵ_{0}} represents j[Z] in the ℚ_{<κ}-generic ultrapower.

It follows that the function on P(Z) (or [Z]^{ℵ_{0}}) sending X to the transitive collapse of X represents Z in the (corresponding) generic ultrapower, so each element of V_{κ} is in the image model of the generic embedding. In particular, the function on P(α) sending X to the ordertype of X represents α.

Fact 1.7. For each condition a in ℙ_{<κ} or ℚ_{<κ}, a ∈ G if and only if j[⋃ a] ∈ j(a).

Proof. We have that a = {z ⊆ ⋃ a | z ∈ a}. Consider the functions on P(⋃ a) (or [⋃ a]^{ℵ_{0}}) representing j[⋃ a] and j(a) (call them f and g). The former is the identity function and the latter is the constant function taking the value a. Then a ∈ G if and only if

{z ⊆ ⋃ a | z ∈ a} ∈ G

if and only if {z ⊆ ⋃ a | f(z) ∈ g(z)} ∈ G if and only if [f]_{G} ∈ [g]_{G} if and only if j[⋃ a] ∈ j(a). □

It follows that for α < β < κ, j(α) = β if and only if

{Y ⊆ β | α = o.t.(Y)} ∈ G,

since this set is in G if and only if j[β] has ordertype j(α).

Fact 1.8. For any uncountable regular cardinal γ < κ, γ (as a condition) forces in ℙ_{<κ} that the critical point of j is γ.

Proof. Note that j[γ] ∈ j(γ) if and only if γ is the critical point. Now apply Fact 1.7. □

Note that for η < γ, if γ ∈ G then {η} ∈ G, since γ \ η is club in γ and {η} ≥ γ \ η. Fact 1.7 also implies the following.

Fact 1.9. For any nonempty set X ∈ V_{κ}, [X]^{ℵ_{0}} forces (in both ℙ_{<κ} and ℚ_{<κ}) that X will be countable in the image model of the embedding.

The following follows from Facts 1.7 and 1.9.

Fact 1.10. If κ is a strongly inaccessible cardinal, ω_{1}^{V} is the critical point of any ℚ_{<κ}-generic embedding j, and j(ω_{1}^{V}) ≥ κ.

Example 1.11. In L, let define f: ω_{1} → ω_{1} by letting f(α) be the least β such that L_{β} ⊧ |α| ≤ ℵ_{0}. Then for any δ < κ, club many countable X ≺ V_{δ} satisfy L_{o.t.(X∩δ)} ⊧ |X ∩ω_{1}| ≥ ℵ_{1}. Then o.t.(X ∩δ) < f(X ∩ω_{1}) for these X, which means that [f]_{G} > δ whenever G is an L-generic filter for either ℙ_{<κ} or ℚ_{<κ}.

The following fact shows that the preceding example contrasts with the large cardinal case. Recall that a cardinal κ is measurable if there exists a nonprincipal κ-complete ultrafilter on κ.

Fact 1.12. If κ is a limit of measurable cardinals, then j(ω_{1}^{V}) = κ for any ℚ_{<κ}-generic embedding j.

Proof. If δ is a measurable cardinal and X ≺ V_{δ+2} has cardinality less than δ, then there is a Y ≺ V_{δ+2} containing X such that Y ∩ δ end-extends X ∩ δ (see [11, Lemma 1.1.18], for instance). So, given a stationary set a ∈ ℚ_{<δ} and a function f: a → ω_{1}, the set of countable X ≺ V_{δ+2} such that X ∩ ⋃ a ∈ a and o.t.(X ∩ δ) > f(X ∩ ⋃ a) is a stationary set below a forcing in ℚ_{<κ} that [f]_{G} < δ. □

Essentially the same argument shows that, given a measurable cardinal δ and a stationary set a ∈ V_{δ}, the set of countable X ≺ V_{δ+2} such that X ∩⋃ a ∈ a and o.t.(X ∩δ) = δ is a stationary set below a forcing that j(δ) = δ. This gives the following.

Fact 1.13. If κ is a limit of measurable cardinals, then for any ℙ_{<κ}- generic embedding j, j(κ) = κ and j(δ) = δ for cofinally many measurable cardinals δ < κ.

Definition 1.14. A cardinal δ is Woodin if it is strongly inaccessible, and if for each f: δ → δ there exist a κ < δ closed under f and an elementary embedding j: V → M with critical point κ such that V_{j(f)(κ)} ⊆ M.

Equivalently, δ is Woodin if for every A ⊆ V_{δ} there is a κ < δ which is <δ-A-strong, i.e., for every γ < δ there is an elementary embedding j: V → M with critical point κ such that j(κ) > γ, V_{γ} ⊂ M and j(A) ∩ V_{γ} = A ∩ V_{γ} (see [7, 11], for instance).

Definition 1.15. A cardinal κ is strong if for each ordinal α there is an elementary embedding j: V → M with critical point κ such that V_{α} ⊆ M.

The wellfoundedness of the image model of stationary tower embeddings, in the presence of a Woodin cardinal, is given by the following theorem.

Theorem 1.16. If δ is a Woodin cardinal, then the image model of any ℙ_{<δ}-generic embedding is closed under sequences of length less than δ in the forcing extension, and the image model of any ℚ_{<δ}-generic embedding is closed under countable sequences in the forcing extension.

In the remainder of this section, we will sketch the proof of Theorem 1.16 for ℙ_{<δ}. The proof uses the following definitions.

Definition 1.17. Given a set D ⊆ V_{κ} (for some cardinal κ), sp(D) is the set of Z ≺ V_{κ+1} of cardinality less than κ with D ∈ Z such that there exists an X ⊇ Z, X ≺ V_{κ+1}, X ∩ ⋃(Z ∩ V_{κ}) = Z ∩ V_{κ} such that for some a ∈ D ∩ X, X ∪ ⋃ a ∈ a.

Definition 1.18. A set D ⊆ V_{κ} is semi-proper in V_{κ} (for some cardinal κ) if sp(D) contains a club relative to [V_{κ+1}]^{<κ}.

Theorem 1.16 follows from Theorem 1.19 (see [11, Theorem 2.5.8]).

Theorem 1.19. If δ is Woodin and ⟨D_{α} : α < δ⟩ is a sequence of predense sets in ℙ_{<δ}, then there are cofinally many strongly inaccessible κ < δ such that for all γ < κ, D_{γ} ∩V_{κ} is semi-proper in V_{κ} and predense in ℙ_{<κ}.

Instead of proving Theorem 1.19 (which is Theorem 2.5.9 of [11]), we give prove the corresponding result in the context of supercompact cardinals, as it is simpler and contains the main ideas.

Definition 1.20. Given a cardinals κ and λ, κ is λ-supercompact if there exists an elementary embedding j: V → M with critical point κ such that M is closed under λ-sequences.

Definition 1.21. A subset D of a partial order P is predense if every element of P is compatible with an element of D.

Theorem 1.22. If κ is a 2^{κ}-supercompact cardinal, then every predense subset of ℙ_{<κ} is semi-proper in V_{κ}.

Proof. Let D be such a predense set, and towards a contradiction, suppose that [V_{κ+1}]^{<κ} \ sp(D) is stationary (call this set a, and note that ⋃ a = V_{κ+1}). Let j: V → M be an elementary embedding with critical point κ such that M is closed under 2^{κ}-sequences. Then a is a stationary set in M. Since j(D) is predense, there is a b ∈ j(D) such that a and b are compatible in ℙ_{<j(κ)}^{M}. Working in in M, let X ≺ V_{j(κ)+1}^{M} be closed under j, with a, b in X and |X| < j(κ), such that X ∩⋃ a ∈ a and X ∩ ⋃ b ∈ b. Let Y = X ∩ V_{κ+1}. Then Y ∈ a, so j(Y) ∈ j(a). Since |Y | < κ, j(Y) = j[Y] and

j(Y) ∩ V_{j(κ)} = Y ∩ V_{κ}.

Then j(Y) ⊆ X,

X ∩ ⋃(j(Y) ∩ V_{j(κ)}) = X ∩ ⋃(Y ∩ V_{κ}) = Y ∩ V_{κ} = j(Y) ∩ V_{j(κ)},

b ∈ X and X ∩ ⋃ b ∈ b, giving a contradiction. □

To see how Theorem 1.16 follows from Theorem 1.19, note first that if A is an antichain in ℙ_{<κ} then

• for each X ≺ V_{κ+1} with A ∈ X, there can be at most one a ∈ A ∩ X with X ∩ ⋃ a ∈ a.

• if b ∈ ℙ_{<κ} is stationary, and for each X ∈ b there is an a ∈ A∩X such that X ∩ ⋃ a ∈ a, then for all c ≤ b there exist c′ ≤ c and a ∈ A such that for all X ∈ c′, a ∈ X and X ∩ ⋃ a ∈ a.

By Theorem 1.19, if A_{α} (α < δ) are maximal antichains in ℙ_{<δ}, each deciding a name τ_{α} for an element of the ultrapower (we may assume that it does this in such a way for each α < δ and each a ∈ A_{α} there is a function g: a → V such that a⊩τ_{α} = [ǧ]_{G}), then there are cofinally many κ < δ such that for any b ∈ ℙ_{<κ}, the set c consisting of those X ≺ V_{κ+1} such that

• X ∩ ⋃ b ∈ b,

• for each α ∈ X ∩ κ there is a unique a ∈ A_{α} ∩ X such that

X ∩ ⋃ a ∈ a

is stationary, and therefore a condition below b.

Define f on c by letting f(X) be a sequence of length o.t.(X ∩κ) such that whenever α is the βth member of X ∩ κ, (β, g(X ∩ ⋃ a)) ∈ f(X), where a ∈ X ∩ A_{α} with X ∩ ⋃ a ∈ a, and a⊩τ_{α} = [ǧ]_{G}.

Note that ⋃ c = V_{κ+1}. Then for any c′ ≤ c, and any α < κ such that α ∈ X for all X ∈ c′, there is for each X ∈ c′, since X ∩ V_{κ+1} ∈ c, a unique a ∈ X ∩ V_{κ+1} ∩ A_{α} such that X ∩ ⋃ a ∈ a, with a g: a → V such that a⊩τ_{α} = [ǧ]_{G}. By pressing down we get an a ∈ A_{α} which is this unique a for all X ∈ c′′ ≤ c′, which means that c′′ ≤ a.

Then for all X ∈ c′′, we get that if α is the βth member of X ∩ κ, then (β, g(X ∩⋃ a)) ∈ f(X ∩⋃ c), which means that c′′ forces that the pair (α, τ_{αG}) is in the sequence [f]_{G} represented by f.

2. ⊧_{Ω}

For every Σ_{2} sentence φ there is a sentence φ′ (e.g., φ + “there is no largest ordinal” + “H(κ) exists for all cardinals κ”) such that φ is equivalent to “there exists a α such that V_{α} ⊧ φ′”. Similarly, for any φ the statement “there is an ordinal α such that V_{α} ⊧ φ” is Σ_{2}. We will often use these two classes of sentences interchangeably.

The following standard forcing fact can be found in the appendix to [11].

Fact 2.1. If P and Q are partial orders, and forcing with P makes P(Q)^{V} countable, then there is a Q-name τ for a partial order such that P is forcing-equivalent to Q ∗ τ.

The following theorem of Woodin shows that, in the presence of a proper class of Woodin cardinals, forceability of Σ_{2}-sentences is forcinginvariant.

Theorem 2.2. Suppose that δ is a Woodin cardinal, φ is a sentence, α < δ and P ∈ V_{δ} a partial order such that P forces the statement “V_{α} ⊧ φ.” Then after forcing with any partial order Q in V_{δ} there exist a partial order P′ and an ordinal α′ such that P′ forces the statement “V_{α′} ⊧ φ.”

Proof. Let G be a V -generic filter for ℙ_{<δ} below the condition [P(Q)]^{ℵ_{0}}. Since [P(Q)]^{ℵ_{0}} forces that P(Q)^{V} is countable, V [G] is a forcing extension of a generic extension of V by Q (below any given condition in Q). Let j: V → M be the corresponding embedding. By elementary, j(P) forces in M that V_{j(α)} ⊧ φ. Since j(α) < δ and V_{δ}^{M} = V_{δ}^{V [G]}, j(P) forces this in V [G] as well. □

As an exercise, one can adapt the proof of Theorem 2.2 to show the following : assuming 2^{<κ} = κ for a cardinal κ below a Woodin cardinal δ, anything that can be forced to hold in a proper rank initial segment of V_{δ} by a forcing preserving all cardinals below κ^{+} can still be forced to hold in such an initial segment by such a forcing after forcing with 2^{<κ}.

Definition 2.3. Given a sentence φ and a theory T, we say that T ⊧_{Ω} φ if in every set forcing extension, for every ordinal α, if V_{α} ⊧ T then V_{α} ⊧ φ. If ∅ ⊧_{Ω} φ, then we say that φ is Ω-valid. If T ⊧_{Ω} φ we say that T implies φ in Ω-logic.

By Theorem 2.2, the set of φ such that ∅ ⊧_{Ω} φ cannot be changed by set forcing. Ω-logic is an attempt to understand this set (for instance, its complexity) by proposing a corresponding notion of “proof.”

3. Universally Baire sets

The following definition is due to Feng, Magidor and Woodin [3].

Definition 3.1. A set of reals A is universally Baire if for all compact Hausdorff spaces X, and any continuous function f: X → ℝ, f^{−1}[A] has the property of Baire in X.

In the definition of universally Baire sets, “compact” can be replaced with “having a base consisting of regular open sets” without changing the corresponding class of sets.

Definition 3.2. A tree on a set X is a subset of X^{<ω} closed under initial segments. Given a tree T on a set X, [T] is the set of all f ∈ ^{ω}X such that f↾n ∈ T for all n ∈ ω. If T is a tree on ω × X, for some set X, then the projection of T, p[T], is the set of a ∈ ^{ω}ω for which there exists an f ∈ ^{ω}X with (a, f) ∈ [T] (identifying pairs of sequences with sequences of pairs).

Definition 3.3. Given an ordinal γ, a set A ⊆ ^{ω}ω is γ-Suslin if it is the projection of a tree on ω × γ, and Suslin if it is γ-Suslin for some ordinal γ. If T is a tree on ω × γ, for some ordinal γ, and p[T] = A, we say that T is a Suslin representation for A.

In the interest of streamlining the presentation, we give the following nonstandard (relative to our definition of universally Baire) definition of λ-universally Baire.

Definition 3.4. Given a cardinal λ, A ⊆ ^{ω}ω is λ-universally Baire if there exists a pair of trees S, T on ω × γ, for some ordinal γ, such that p[S] = A, and p[S] and p[T] are complements in all forcings extensions by partial orders of cardinality less than or equal to λ.

Given a set X, the partial order Coll(ω, X) consists of all finite partial functions from ω to X, ordered by inclusion. It is a standard forcing fact (due to McAloon) that any partial order ℙ forcing the statement |ℙ| = ℵ_{0} is forcing-equivalent to Coll(ω, ℙ). It follows that any partial order of the form ℙ × Coll(ω, ℙ) is forcing-equivalent to Coll(ω, ℙ).

Definition 3.5. Given a partial order P, a nice name for a subset of the ground model is a set of pairs (p, x̌), where p is a condition in P and x̌ is the canonical name for an element x of the ground model.

By a theorem of Feng-Magidor-Woodin [3], a set A is universally Baire if and only if it is λ-universally Baire for all cardinals λ. If A is λ-universally Baire, this is witnessed by trees on ω×2^{λ} (since all partial orders of cardinality λ regularly embed into Coll(ω, λ), and there are just 2^{λ} many nice names for reals in this forcing). It follows that if A is universally Baire and κ is a strong limit, then A is universally Baire in V_{κ}.

In L, every set of reals is a continuous image of a universally Baire set. In fact this follows from the Continuum Hypothesis plus the existence of an ω_{1}-sequence of distinct reals such that the set of codes for initial segments of this sequence is universally Baire. In the current fine-structural inner models for Woodin cardinals, there exists such a sequence which is <δ-universally Baire for δ the least Woodin cardinal. This is discussed in the introduction to [26].

Given a tree S on a set of the form ω × X, membership in the projection of S is upwards absolute to wellfounded models. Given trees S, T of this form, the statement p[S] ∩ p[T] = ∅ is also upwards absolute (one can prove this either by considering a ranking function on the tree of attempts to build a path in common, or by forcing over a countable elementary submodel). From this fact one can see that if S_{0}, T_{0}, S_{1}, T_{1} are two pairs of trees such that p[S_{0}] = p[S_{1}] and the pairs S_{0}, T_{0} and S_{1}, T_{1} project to complements in all forcing extensions in given class, then S_{0} and S_{1} have the same projection in any such extension, as the following facts hold there:

• p[S_{0}] = ^{ω}ω \ p[T_{0}],

• p[S_{1}] = ^{ω}ω \ p[T_{1}],
• p[S_{0}] ∩ p[T_{1}] = ∅,
• p[S_{1}] ∩ p[T_{0}] = ∅.

If A ⊆ ^{ω}ω is λ-universally Baire and V [G] is a forcing extension of V by a partial order of cardinality less than or equal to λ, then we reinterpret A in V [G] as p[S], for any such S as above, and call the reinterpreted set A_{G}.

As shown in [3], universally Baire sets are universally measurable and have the property of Baire. Furthermore, analytic sets are universally Baire, and the class of universally Baire sets is closed under complements and countable unions.

4. The Martin-Solovay tree

Suppose that X is a set, i < j are integers, and σ and τ are ultrafilters on X^{i} and X^{j} respectively. Then τ projects to σ if for all A ∈ σ,

{s ∈ X^{j} | s↾i ∈ A} ∈ τ

(equivalently, if for all B ∈ τ, {s↾i | s ∈ B} ∈ σ). In this case, if j_{σ}: V → M_{σ} and j_{τ}: V → M_{τ} are the induced ultrapowers, there is a factor embedding k: M_{σ} → M_{τ} defined by k([f]_{σ}) = [f^{∗}]_{τ}, where f^{∗}: X^{j} → V is defined by f^{∗}(s) = f(s↾i).

Suppose that ⟨σ_{n} : n ∈ ω⟩ is a sequence of ultrafilters such that, for some underlying set X, σ_{n}(X^{n}) = 1 for all n ∈ ω. The tower is countably complete if whenever B_{n} is a σ_{n}-positive set for each n ∈ ω, there is an f such that f↾n ∈ B_{n} for all n. This is equivalent to saying that the measures project to one another, and that the direct limit of the ultrapowers of the σ_{n}’s (via the factor maps) is wellfounded.

Definition 4.1. Given a cardinal κ, a set A ⊆ ^{ω}ω is κ-homogeneously Suslin if there is a collection of κ-complete measures μ_{σ} (σ ∈ ^{<ω}ω) such that

• for each σ, μ_{σ} concentrates on |σ|-tuples,

• for any a ∈ ^{ω}ω, a ∈ A if and only if ⟨μ_{a↾n} : n ∈ ω⟩ is countably

complete. A set is homogeneously Suslin if it is ℵ_{1}-homogeneously Suslin.

There is an underlying tree here, where one concentrates on the measure one sets giving rise to witnesses for each real not in A (using the fact that if the measures are nontrivial they are 𝔠^{+}-complete).

Homogeneously Suslin sets are determined. If there exists a measurable cardinal, then Π_{1}^{1} sets are homogeneously Suslin (using the same measure, plus principal measures). These facts are due to Martin [13].

Definition 4.2. Given a cardinal κ, a set A ⊆ ^{ω}ω is κ-weakly homogeneously Suslin if there is a collection of κ-complete measures μ_{σ,τ} (σ, τ ∈ ^{<ω}ω, |σ| = |τ|) such that

• for each such pair σ, τ, μ_{σ,τ} concentrates on |σ|-tuples,

• for any a ∈ ^{ω}ω, a ∈ A if and only if there exists b ∈ ^{ω}ω such

that ⟨μ_{a↾n,b↾n} : n ∈ ω⟩ is countably complete. A set is weakly homogeneously Suslin if it is ℵ_{1}-weakly- homogeneously Suslin.

A set of reals is κ-weakly homogeneously Suslin if and only if it is the continuous image of a κ-homogeneously Suslin set.

Given a set of measures witnessing that some set A is weakly homogeneously Suslin, the Martin-Solovay tree [14] for the complement of A is the tree of attempts, for each real x, to produce a witness to the illfoundedness of all the towers corresponding to x. That is, fixing some enumeration ⟨s_{m} : m < ω⟩ of ω^{<ω}, the tree is the set of sequences ⟨(i_{m}, α_{m}) : m < n⟩ (for some n ∈ ω) such that for all m < m′ < n such that s_{m′} extends s_{m},

k_{(⟨i_{j}:j<|s_{m}|⟩,s_{m})(⟨i_{j}:j<|s_{m′}|⟩,s_{m′})}(α_{m}) > α_{m′}.

Again, there is an underlying tree here. Let X be a set such that each measure concentrates on n-tuples from X, for some n ∈ ω. Fix for each non-countably complete tower of the form ⟨μ_{a↾n,b↾n} : n ∈ ω⟩ a witness ⟨A_{a,b,n} : n ∈ ω⟩ to the fact that it is not countably complete, and for each pair σ, τ in ω^{<ω} of the same length n, let B_{σ,τ} be the intersection of all corresponding A_{a,b,n} such that a↾n = σ and b↾n = τ (if there are any such A_{a,b,n}, and if not let B_{σ,τ} = X^{n}). Then the set of pairs (σ, (τ, ρ)) such that ρ ∈ B_{σ,τ} is a tree T projecting to A, and the Martin-Solovay tree projects to the complement of A.

To see this, note that for each a ∈ A the Martin-Solovay tree is wellfounded, since there is a b such that ⟨μ_{a↾n,b↾n} : n ∈ ω⟩ is countably complete. On the other hand, if a ∉ A, then there is a ranking function π on the tree

T_{a} = {(τ, ρ) : (a↾|τ|, (τ, ρ)) ∈ T }.

Then if (τ, ρ) is initial segment of (τ′, ρ′) in T_{a}, π(τ, ρ) > π(τ′, ρ′). For each τ ∈ ω^{<ω}, let θ_{τ} be a function on X^{|τ|} (representing an ordinal in the τ-ultrapower) such that θ_{τ}(ρ) = π(τ, ρ) for each ρ such that (τ, ρ) ∈ T_{a}. If α is the ordinal represented by θ_{τ} in the μ_{a↾|τ|,τ}-ultrapower, then k_{(a↾|τ|,τ),(a↾|τ′|,τ′)}(α) is represented by the function ρ ↦ θ_{τ}(ρ↾|τ|) in the μ_{a↾|τ′|,τ′}-ultrapower, which is greater than θ_{τ′} on a set of measure one, since

θ_{τ}(ρ↾|τ|) = π(τ, ρ↾|τ|) > π(τ′, ρ) = θ_{τ′}(ρ)

whenever (τ′, ρ) ∈ T_{a}.

If the system of measures witnesses the κ-weak homogeneity of A, then the Martin-Solovay tree witnesses that A is <κ-universally Baire, since in this case the ordinals of the μ_{σ,τ}-ultrapowers are represented by the same functions as in the ground model, so the construction of the Martin-Solovay tree is the same. The following theorem of Kunen [10] was used in his proof that if there exist uncountably many measurable cardinals, then L(Ord^{ω}) does not satisfy Choice.

Theorem 4.3 (Kunen). Suppose that ν is a κ-complete measure on a cardinal κ, that i < j are elements of ω, and that μ_{i} and μ_{j} are κ^{+}- complete measures on the i- and j-tuples from some set X, respectively, such that μ_{j} projects to μ_{i}. If j: V → M is the ν-embedding, then the maps using j(μ_{i}) and j(μ_{j}) in M, and the corresponding factor map, move ordinals in the same way as the corresponding maps using μ_{i} and μ_{j} in V.

Since the definition of the Martin-Solovay tree uses only the images of the ordinals by the factor maps between ultrapowers, it follows from Kunen’s theorem that the Martin-Solovay tree for any set of κ^{+}- complete measures is moved to itself by j as above. Steel proved that this situation persists to stationary tower embeddings (see [11, Theorem 3.3.17]).

Theorem 4.4 (Steel). Suppose that κ is a Woodin cardinal, that i < j are elements of ω, and that μ_{i} and μ_{j} are κ^{+}-complete measures on the i- and j-tuples from some set X, respectively, such that μ_{j} projects to μ_{i}. If j: V → M is an embedding derived from forcing with ℙ_{<κ} or ℚ_{<κ}, then the maps using j(μ_{i}) and j(μ_{j}) in M, and the corresponding factor map, move ordinals in the same way as the corresponding maps using μ_{i} and μ_{j} in V.

It follows that if δ is a Woodin cardinal, then the Martin-Solovay tree for a collection of δ^{+}-complete measures maps to itself under ℙ_{<δ} and ℚ_{<δ} embeddings.

The following theorem, in conjunction with the results of [13] mentioned above, implies that the existence of n Woodin cardinals below a measurable cardinal implies the determinacy of all Π_{n+1}^{1} sets.

Theorem 4.5 (Martin-Steel [15]). If δ is a Woodin cardinal and A ⊂ ωω is δ^{+}-weakly homogeneously Suslin, then^{ω}ω\A is <δ-homogeneously Suslin.

It follows that in the presence of a proper class of Woodin cardinals, the three tree representation properties for sets of reals that we have introduced here are equivalent.

Theorem 4.6. If δ is a limit of Woodin cardinals and A ⊆ ^{ω}ω, then the following are equivalent

(1) A is <δ-universally Baire,

(2) A is <δ-weakly homogeneously Suslin,

(3) A is <δ-homogeneously Suslin.

(3) ⇒ (2) is immediate, and (2) ⇒ (1) follows from the construction of the Martin-Solovay tree. (2) ⇒ (3) follow from the Martin-Steel theorem. (1) ⇒ (2) follows from the following theorem of Woodin.

Theorem 4.7 (Woodin). Suppose that δ is a Woodin cardinal, and S, T are trees on ω × γ, for some ordinal γ such that S and T project to complements in all ℚ_{<δ}-extensions. Then p[S] and p[T] are <δ-weakly homogeneous.

Proof. Since every real added by ℚ_{<δ} is the realization of a ℚ_{<κ}-name for some κ < δ (even though the restriction of the generic filter to ℚ_{<κ} may not be generic), we may assume that S and T have cardinality δ, and even that they are trees on ω ×δ. There are arbitrarily large κ < δ which are <δ-T -strong. It suffices to prove that for any such κ, p[T] is κ-weakly homogeneously Suslin. For each λ < δ, fix an elementary embedding j_{λ}: V → M_{λ} with critical point κ such that j_{λ}(T)∩(ω×λ) = T ∩ (ω × λ) and V_{λ} ⊆ M_{λ}. For each pair (s, u) ∈ T ∩ (ω × λ), define a measure Σ(s, u) on κ^{|s|} by letting X ∈ Σ(s, u) if and only if u ∈ j_{λ}(X). Note that the set A_{s} = {v ∈ κ^{|s|} | (s, v) ∈ T } ∈ Σ(s, u) for each (s, u) ∈ T ∩ (ω × λ) (recall that we are assuming that |s| = |u| in this situation).

Let i: V → N be an embedding derived from ℚ_{<δ}. We claim that in N, the collection of all measures of the form i(Σ_{λ}(s, u)) witnesses that p[i(T)] is i(κ) weakly homogeneously Suslin. Every real of N is either in p[T] or p[S]. For x ∈ p[T], fix λ < δ and f ∈ λ^{ω} such that (x, f) ∈ [T ∩ (ω × λ)]. Then ⟨i(Σ_{λ}(x↾n, f↾n)) : n ∈ ω⟩ is countably complete, as its limit model embeds into the i-image of M_{λ}, and in N, since N is closed under countable sequences. If x ∈ p[S], then x ∉ p[T], so the sets A_{x↾n} witness that no tower of measures of the form ⟨i(Σ_{λ}(x↾n, u_{n})) : n ∈ ω⟩ will be countably complete. □

The following theorem is known as the Tree Production Lemma, and is one of the most useful ways to show that a set of reals is universally Baire.

Theorem 4.8 (Woodin). Suppose that δ is a Woodin cardinal, and let A ⊆ ^{ω}ω. Then A is <δ universally Baire if there exist a formula ψ, and a set y, such that whenever j: V → M is an embedding derived from ℚ_{<δ} and x is a real in M, x ∈ j(A) if and only if V [x] ⊧ ψ(x, y).

Equivalently, if δ is a Woodin cardinal and A ⊆ ^{ω}ω, then A is <δ universally Baire if for every real x which is V -generic for a partial order in V_{δ}, either x ∈ j(A) for all ℚ_{<δ}-generic embeddings j: V → M such that x ∈ M, or x ∈ j(A) for no such embeddings.

One consequence of Theorem 4.4 plus the the Tree Production Lemma is that every universally Baire A set has a universally Baire scale (a set of reals coding a Suslin representation for A).

5. A-closed models

Definition 5.1. Given A ⊆ ^{ω}ω, a countable transitive model M of ZFC is A-closed if for each partial order ℙ ∈ M there is a countable set D consisting of dense open subsets of ℙ (not necessarily members of M) such that for every filter G ⊆ P intersecting every member of D, A ∩ M[G] ∈ M[G].

Since statements of the form “x ∈ p[T]” are absolute between wellfounded models of (a suitable fragment of) ZFC, we have the following.

Example 5.2. Suppose that κ is a cardinal, A ⊆ ^{ω}ω, and V_{κ} ⊧ ZFC + “A is universally Baire.” Let X be a countable elementary submodel of V_{κ} with A ∈ X, and let M be the transitive collapse of X. Then M is A-closed.

This can be generalized as follows.

Fact 5.3. Suppose that • A ⊆ ^{ω}ω,

• θ is an uncountable cardinal

• X is a countable elementary submodel of H(θ) with trees S, T witnessing that A is ℵ_{0}-universally Baire as members,

• N is the transitive collapse of X.

Then A∩N[G] = A_{G}^{N[G]} for every (N, P)-generic filter G for a countable partial order P ∈ X.

Given a universally Baire set of reals A, A-closure has several equivalent formulations. We give just three here ([1] has more).

Fact 5.4. Given an ℵ_{0}-universally Baire set of reals A ⊆ ^{ω}ω and a countable transitive model M of ZFC, the following statements are equivalent.

(1) M is A-closed.

(2) For all partial orders ℙ ∈ M, for all (V, ℙ)-generic filters G, A_{G} ∩ M[G] ∈ M[G].

(3) For all partial orders ℙ ∈ M, the set of pairs (τ, p) such that • τ is a nice ℙ-name for a real,

• p ∈ ℙ forces in V that τ_{G} ∈ A_{G} is a member of M.

(4) For all infinite ordinals γ ∈ M, the set of pairs (τ, p) such that • τ is a nice Coll(ω, γ)-name for a real,

• p ∈ Coll(ω, γ) forces in V that τ_{G} ∈ A_{G} is a member of M.

Proof. (1) ⇔ (2) follows from Fact 5.3, letting N be as described there, with M ∈ N. (1) implies (2) since if M is A-closed and P ∈ M then dense open subsets of P witnessing the A-closure of M will be in N, so for every (N, P)-generic filter G, A ∩ M[G] ∈ M[G] and A ∩ N[G] = A_{G}^{N[G]}, so

A_{G}^{N[G]} ∩ M[G] = A ∩ N[G] ∩ M[G] = A ∩ M[G] ∈ M[G].

For the reverse direction, for all (N, P)-generic filters, A∩N[G] = A_{G}^{N[G]} and A_{G}^{N[G]} ∩ M[G] ∈ M[G], so

A ∩ M[G] = A ∩ N[G] ∩ M[G] = A_{G}^{N[G]} ∩ M[G] ∈ M[G].

(3) ⇒ (2) follows from the fact the M[G] can use G and the set given to decode membership in A_{G} for the realization of any given name for a real. (3) ⇒ (4) is immediate, and (4) ⇒ (3) follows from the fact that ℙ regularly embeds into Coll(ω, |ℙ|), and names in the former partial order can be translated through this embedding to names in the latter. To see (2) ⇒ (4), note that if A_{G} ∩ M[G] ∈ M[G] holds in V [G], then some condition p ∈ Coll(ω, γ) forces that some Coll(ω, γ)-name σ in M represents A_{G} ∩ M[G]. Since Coll(ω, γ) is homogeneous, σ can be converted into a name forced by the empty condition to represent A_{G} ∩ M[G]. □

Fixing a recursive bijection between ω and ω ×ω, we can let W O denote the set of x ⊆ ω whose image under this bijection is a wellordering of ω. Then W O is Π_{1}^{1}, and in fact every Π_{1}^{1} set is a continuous preimage of W O.

Officially, we are considering A-closure only for wellfounded models M. The following example shows that if we were to relax this restriction to require only that M be an ω-model we would get an equivalent notion for suitably complex A.

Fact 5.5. An ω-model of ZFC is W O-closed if and only if it is wellfounded.

Proof. Suppose that γ were an illfounded “ordinal” of a W O-closed ωmodel M, and consider a filter G ⊂ Coll(ω, γ) such that W O ∩M[G] ∈ M[G]. Then M[G] could identify exactly which ordinals below γ are wellfounded, which is impossible. □

A similar argument shows that A-closure for a certain set of reals A can imply closure under sharps for all sets (see [7] for more on sharps).

Fact 5.6. Suppose that the sharp of every real exists, and let A ⊆ ω×^{ω}ω be the set of pairs (i, x) such that i ∈ x^{#}. Then if M is an A-closed countable transitive model of ZFC, then a^{#} ∈ M for all sets a ∈ M.

Proof. We may assume that a is an infinite set of ordinals. Fix an A-closed model M, and consider a filter G ⊂ Coll(ω, |a|) such that A ∩ M[G] ∈ M[G]. Then in M[G] there is an x ⊆ ω coding a structure isomorphic to (sup(a) + 1, a, ∈). Then x^{#} ∈ M[G], so a^{#} ∈ M[G], which means that a^{#} ∈ M. □

If there exist proper class many Woodin cardinals, then the set of reals ℝ^{#} is universally Baire (this can be seen by applying Corollary 3.1.19 of [11] with Theorem 4.8). An analogous version of the previous fact, using ℝ^{#}, shows that there is a universally Baire set of reals A, simply definable from ℝ^{#}, such that if M is an A-closed model of ZFC, then H(ℵ_{1})^{M} is an elementary submodel of H(ℵ_{1}).

More generally, a recursive bijection between ω and ω × ω enables a coding of hereditarily countable sets by subsets of ω, in such a way that (letting π(x) be the set coded by x; the code for a ∈ H(ℵ_{1}) actually describes the transitive closure of {a}) the set of x coding a set in H(ℵ_{1}) is Π_{1}^{1} (call is C), and such that the relations π(x) = π(y) and π(x) ∈ π(y) are both Σ_{1}^{1}. Now suppose that f: C → C is a universally Baire function (i.e., the graph of f is universally Baire) such that whenever π(x) = π(y), π(f(x)) = π(f(y)). This induces a function on H(ℵ_{1}) which (in the presence of a proper class of Woodin cardinals) extends to a definable class function F on V, since it reinterprets uniquely to a function on H(ℵ_{1}) in any forcing extension (we can use a countable elementary submodel plus Σ_{1}^{1} absoluteness to show that the isomorphism property persists to forcing extensions). Moreover, any f-closed countable transitive model of ZFC is closed under F (on all sets, not just H(ℵ_{1})^{M}).

6. ⊢_{Ω}

We will develop the proof relation for Ω-logic in the context of a proper class of Woodin cardinals. This large cardinal assumption is not strictly necessary, but it makes the analysis simpler, and is natural since it is the hypothesis used for the invariance of ⊧_{Ω}.

Definition 6.1. If T is a countable theory in the language of set theory and φ is a sentence, then T ⊢_{Ω} φ if and only if there exists a universally Baire set A ⊆ ^{ω}ω such that for all countable transitive A-closed models M of ZFC, if T ∈ M, then M ⊧ “T ⊧_{Ω} φ.”

We say T proves φ in Ω-logic if T ⊢_{Ω} φ, that φ is Ω-provable if ∅ ⊢_{Ω} φ, and that φ is Ω-consistent if ∅ ⊬_{Ω} ¬φ (i.e., if ¬φ is not Ωprovable).

Universally Baire sets of reals play the role of proofs in Ω-logic. In this sense, one “proof” can prove many statements; indeed, using Theorem 7.8 one can show that there is one universally Baire set serving as the proof all Ω-provable statements.

Given A, B ⊆ ^{ω}ω, we say that A is Wadge reducible to B (A ≤_{W} B) if there is a continuous function f: ^{ω}ω → ^{ω}ω such that A = f^{−1}[B]. This notation comes from the following game (the Wadge game) for A and B : I plays to build a real x, II builds a real y, and I wins if x ∈ A if and only if y ∈ B. The determinacy of Wadge games implies that for all A, B ⊆ ^{ω}ω, either B ≤_{W} A (in the case I wins) or A ≤_{W} ^{ω}ω \ B (in the case II wins). Martin and Monk showed that if DC (the statement that every tree without terminal nodes has an infinite branch) holds and all sets of reals have the property of Baire, then ≤_{W} is wellfounded; their proof shows that ≤_{W} is a wellfounded relation on the universally Baire sets. Thus we can talk of the Wadge rank of a set A ⊆ ^{ω}ω, and this corresponds roughly to the notion of length of proof in Ω-logic.

The following theorem can be proved using Theorems 4.4 and 4.8. The assumption of a proper class of Woodin cardinals is overkill; the theorem follows from the assumption that universally Baire sets have universally Baire scales and universally Baire sharps.

Theorem 6.2 (Woodin). Suppose that there exist proper class many Woodin cardinals. Let A ⊆ ^{ω}ω be universally Baire. Then in every set generic extension V [G] of V there is an elementary embedding from L(A, ℝ^{V}) to L(A_{G}, ℝ^{V [G]}) sending A to A_{G}.

It follows from Theorem 6.2 that if T ⊢_{Ω} φ holds, then it holds in all set-forcing extensions. The following theorem, which follows from the fact that the Martin-Solovay tree maps to itself (as discussed after Theorem 4.4) implies (along with the fact that every forcing of cardinality less than δ regularly embeds into ℙ_{<δ}) that if T ⊢_{Ω} φ holds in a set forcing extension, then it holds in V.

Theorem 6.3. Suppose that there exists a proper class of Woodin cardinals, δ is Woodin, and j: V → M ⊆ V [G] is a generic elementary embedding induced by forcing with ℙ_{<δ}. Then every universally Baire subset of ^{ω}ω in V [G] is a universally Baire set in M.

Proof. (Sketch) First note that if κ < λ are cardinals, then every λcomplete measure (on an ordinal) in a forcing extension by a partial order of cardinality κ is the canonical extension of (i.e., the set of supersets of members of) such a measure in the ground model. To see this, first note that every measure one set must contain such a set from the ground model. Now assume that for every condition in the generic there is a set in the measure not forced to be there by this condition, and intersect these.

Suppose that A is universally Baire in V [G]. Fixing an arbitrary κ > δ, we will show that A is κ^{+}-weakly homogeneously Suslin in M. Fix a countable set of measures {μ_{σ,τ} : σ, τ ∈ ω^{<ω}} witnessing that A is κ^{+}-weakly homogeneously Suslin in V [G]. These measures are each canonical extensions of measures ν_{σ,τ} in V, and {j(ν_{σ,τ}) : σ, τ ∈ ω^{<ω}} exists in M. By Theorem 4.4, the Martin-Solovay trees for the complements of these two sets are exactly the same. □

The following is the Soundness Theorem for Ω-logic.

Theorem 6.4. Suppose that there exist proper class many Woodin cardinals, T is a theory and φ is a sentence. Then T ⊢_{Ω} φ implies T ⊧_{Ω} φ.

Proof. Suppose that A witnesses T ⊢_{Ω} φ. Let P be a partial order and let α be an ordinal. Let κ be a strongly inaccessible cardinal such that {P, α} ∈ V_{κ}, and let X be a countable elementary submodel of V_{α} with {P, α} ∈ X. Let M be the transitive collapse of X, and let P̄, ᾱ be the images of P and α under this collapse. Then M is A-closed, so M ⊧ “T ⊧_{Ω} φ”, which means that in any forcing extension of M by P̄, the Vᾱ of this extension satisfies φ if it satisfies T. Then in any forcing extension of V by P, the V_{α} of this extension satisfies φ if it satisfies T. □

The Ω-conjecture is the statement that if there exist proper class many Woodin cardinals, then for any sentence φ, ∅ ⊧_{Ω} φ if and only if ∅ ⊢_{Ω} φ. The reverse direction is the Soundness Theorem above. The forward direction is the Completeness Theorem for Ω-logic. Since ⊧_{Ω} and ⊢_{Ω} are forcing absolute, the Ω-conjecture is as well.

7. AD^{+}

The following definition generalizes the notion of Suslin representations for sets of reals.

Definition 7.1. A set A ⊆ ^{ω}ω is ∞-Borel if for some ordinal α, some set of ordinals S, and some formula with two free variables φ(x, y),

A = {y ∈ ℝ | L_{α}[S, y] ⊨ φ(S, y)}.

Equivalently, A is ∞-Borel if there is a set of ordinals giving a transfinite Borel construction of A (see [9]). Recall that DC_{ℝ} is the statement that for every R ⊆ ^{ω}ω × ^{ω}ω such that for every x ∈ ^{ω}ω there exists y ∈ ^{ω}ω with (x, y) ∈ R, there exists a function f: ω → ^{ω}ω such that for all n ∈ ω, (f(n), f(n + 1)) ∈ R (i.e., the restriction of DC to relations on the reals). Assuming AD+DC_{ℝ}, a set of reals A is ∞-Borel if and only if A ∈ L(S, ℝ), for some S ⊆ Ord (again, see [9]).

Definition 7.2. Θ is the least ordinal α which is not the range of any function with domain ℝ.

If the reals can be well ordered, then Θ = 𝔠^{+}. As shown by Solovay, in the context of determinacy, Θ is the Θ-th cardinal.

The following statement (originally called “within scales”) was developed by Woodin as attempt to axiomatize the properties of a model whose sets of reals are all Suslin in a larger model of AD with the same reals.

Definition 7.3. The axiom AD^{+} is the conjunction of the following three statements.

i) DC_{ℝ} ii) Every set of reals is ∞-Borel, iii) If λ < Θ and π: λ^{ω} → ω^{ω} is a continuous function (where λ

has the discrete topology), then π^{−1}[A] is determined for every A ⊆ ω^{ω}.

The inclusion of ordinal determinacy is explained by the following theorem.

Theorem 7.4 ([8]). Assume ZF + AD + DC_{ℝ}, and fix λ < Θ. If A ⊆ ^{ω}ω is Suslin and co-Suslin, and π: λ^{ω} → ^{ω}ω is continuous, then π^{−1}[A] is determined.

While the third part of AD^{+} trivially implies AD, it is not known whether AD implies AD^{+}. Woodin has shown that if L(ℝ) ⊧ AD, then L(ℝ) ⊧ AD^{+}. More generally, he has shown the following in the context of large cardinals.

Theorem 7.5. If there exists a proper class of Woodin cardinals and A ⊆ ℝ is universally Baire then:

1) L(A, ℝ) ⊧ AD^{+},

2) Every set in P(ℝ) ∩ L(A, ℝ) is universally Baire.

The following theorem says that all three parts of AD^{+} reflect from models of AD^{+} to inner models with the same reals. For DC_{ℝ} (and AD) this is immediate.

Theorem 7.6. Assuming ZF + AD^{+}, any transitive inner model M of ZF with ℝ ⊆ M satisfies AD^{+}.

For the ∞-Borel property this follows from Theorem 7.4 below. Given Γ ⊆ P(ℝ), M_{Γ} is the collection of sets X for which there is a bijection π from ℝ to the transitive closure of X such that the sets π^{−1}[X] and {(a, b) | π(a) ∈ π(b)} are both in Γ.

Theorem 7.7. Assume ZF + AD + DC_{ℝ}. If A is ∞-Borel and Γ is collection of sets of reals projective in A, then A has an ∞-Borel code in M_{Γ}.

Strategies in games on ordinals reflect via the Moschovakis Coding Lemma (see [16]), which says that, under ZF + AD + DC_{ℝ}, if ≤ is a prewellordering of ℝ, then any union of ≤-degrees is Σ_{1}^{1}(≤) (so if ≤ is a prewellordering of ^{ω}ω of length γ, then every subset of γ is coded by a set of reals which is Σ_{1}^{1}(≤)). It follows that the form of ordinal determinacy embodied in AD^{+} is absolute to inner models containing all the reals.

The following is the Σ_{1}^{2} basis theorem for AD^{+}.

Theorem 7.8. Suppose that V = L(P(ℝ)) and that AD^{+} holds. Then for every real x, M_{Δ_{1}^{2}(x)} ≺_{Σ_{1}} L(P(ℝ)).

It follows that if A ⊆ ℝ, L(A, ℝ) ⊧ AD^{+} and there is a set B in P(ℝ) ∩ L(A, ℝ) such that all B-closed models satisfy some statement, then there is such a B which is Δ_{1}^{2}(x) in L(A, ℝ), for some real x.

The ℙ_{max} axiom (∗) is an example of a sentence which is Ω-consistent but not known to be provably forceable from large cardinals (i.e., whose negation is not known not to be Ω-valid). To show that (∗) is Ωconsistent it suffices to show that for each universally Baire set of reals A there is a strongly inaccessible cardinal κ and a pair of trees S, T witnessing that A is <κ-universally Baire such that L(S, T, ℝ) ⊧ AD^{+}. Given this situation, we can force over V with ℙ_{max}, without adding reals, getting a generic filter G. Then in V [G], transitive collapses of countable elementary substructures of L_{κ}(S, T, ℝ)[G] will be A-closed models of (∗).

To find such κ, S, T for a given A, we can let κ be the least strongly inaccessible cardinal. The following theorem is the key technical point.

Theorem 7.9. Suppose that δ is a Woodin cardinal, κ < δ is limit of Woodin cardinals, and δ_{0} < κ is Woodin. Let S and T be sets of ordinals which are moved to themselves by all ℚ_{<δ}-embeddings. Then in a forcing extension there exist a set G which is V -generic for Coll(ω, <κ), and elementary embeddings j: V → M and

k: L(S, T, ℝ)^{M} → L(S, T, ℝ^{∗}),

where ℝ^{∗} = ⋃_{γ<κ} ℝ^{V [G∩Coll(ω,<γ)]} and j is derived from ℚ_{<δ_{0}} below any given condition.

This is related to Woodin’s Derived Model Theorem, which can be stated in a weak form as follows. A tree T is said to be <λ-absolutely complemented if there is a tree S such that p[T] = ℝ\p[S] in all forcing extensions by partial orders of cardinality less than λ.

Theorem 7.10 (Derived Model Theorem; Woodin (see [19])). Let λ be a limit of Woodin cardinals. Let G ⊆ Col(ω, <λ) be a V -generic filter. Let

• ℝ^{∗} be ⋃_{α<λ} ℝ^{V [G↾α]};

• Hom^{∗} be the collection of sets of the form p[T] ∩ ℝ^{∗}, for T a

<λ-absolutely complemented tree in V. Then L(Hom^{∗}, ℝ^{∗}) ⊧ AD^{+}.

A variation of this theorem says that in the situation of Theorem 7.9, L(S, T, ℝ) ⊧ AD^{+}. The proof is essentially the same, and we give a quick sketch. From Theorem 7.9 and the Tree Production Lemma (Theorem 4.8) it follows that any set of reals definable in L(S, T, ℝ) from S, T and a real is <δ_{0}-universally Baire, since for any real generic over V for a partial order in V_{δ_{0}}, we can figure out whether the real is in the image of the given set by applying the same definition in the Coll(ω, <κ)-extension mentioned in the theorem via the forcing language. Therefore, L(S, T, ℝ) satisfies AD (if δ_{0} is greater than a Woodin cardinal, by Theorem 8.1 below), since a supposed least counterexample to AD would be definable and thus <δ_{0}-universally Baire. One can similarly show that the supposed least counterexamples to the two parts of AD^{+} are universally Baire, thus Suslin in some larger model of AD (via a universally Baire scale), by the argument just given. Thus these are not counterexamples by Theorem 7.7 and the Moschovakis Coding lemma.

8. The definability of ⊢_{Ω}

8.1. Definability in H(δ_{0}^{+}). For this section, let δ_{0} denote the least Woodin cardinal. In this subsection we show that ⊢_{Ω} is definable in H(δ_{0}^{+}). This result relies on the following theorem.

Theorem 8.1 (Neeman [17, 18]). If δ is a Woodin cardinal, then δuniversally Baire sets are determined.

To see that ⊢_{Ω} is definable in H(δ_{0}^{+}), first note that the set of δ_{0}- universally Baire subsets of ^{ω}ω is definable in H(δ_{0}^{+}), since A ⊂ ^{ω}ω is δ_{0}-universally Baire if and only if for all partial orders P of cardinality ≤ δ_{0} and all P -names for reals there exist a dense set of conditions p ∈ P for which there exists a tree S on ω × δ_{0} such that p⊩τ ∈ p[S] and either p[S] ⊆ A or p[S] ⊆ ^{ω}ω \ A.

By Neeman’s theorem, Wadge determinacy holds for δ_{0}-universally Baire sets. Since the class of universally Baire sets is closed under continuous preimages, the truly universally Baire sets are an initial segment of this hierarchy. For each δ_{0}-universally Baire set A, let T_{A} be the set of sentences φ such that for every A-closed countable transitive model M of ZFC, M ⊧ “∅ ⊧_{Ω} φ.” The union of the T_{A}’s is a superset of the sentences φ such that ⊢_{Ω} φ. If these two sets are equal, then we have given a definition of ⊢_{Ω} in H(δ_{0}^{+}). Otherwise, there is a least Wadge rank of a δ_{0}^{+}-universally Baire set A for which T_{A} includes sentences which are not Ω-provable. Let n_{0} be the Gödel code of some such sentence. Then all truly universally Baire sets have rank less than A, and the union of the sets T_{B}, for B of Wadge rank less than A, is the set of Ω-provable sentences, which is again definable in H(δ_{0}^{+}), this time using the integer n_{0}.

8.2. Gödel sentences. Given that Ω-provability is defined in H(δ_{0}^{+}), and thus in a rank initial segment of the universe, one might expect to refute the Ω-conjecture by means of a Gödel sentence of the form “I am not Ω-provable.” Assuming that there exist proper class many Woodin cardinals, let θ be the unary formula such that any sentence ψ is Ωprovable if and only if H(δ_{0}^{+}) ⊧ θ(⌈ψ⌉). Then there is a unary formula φ such that φ(n) says that if n is the code for a unary formula ψ, and there exists a least Woodin cardinal δ_{0}, then H(δ_{0}^{+}) ⊧ ¬θ(⌈ψ(n)⌉). The corresponding Gödel sentence φ_{0} is φ(⌈φ⌉).

If φ_{0} were Ω-provable, then H(δ_{0}^{+}) ⊧ θ(⌈φ_{0}⌉), and there would be a universally Baire set A such that all A-closed models satisfy “⊧_{Ω} φ_{0}”. That is, all rank initial segments of forcing extensions (even for the trivial forcing) of A-closed models satisfy φ_{0} and therefore satisfy the sentence “there is no rank initial segment of the universe containing a least Woodin cardinal δ such that H(δ^{+}) ⊧ θ(⌈φ_{0}⌉).” However, we can contradict this assertion by taking a countable elementary substructure of a model containing trees witnessing the universal Baireness of A up to some strongly inaccessible cardinal above δ (i.e., just by running the proof that Ω-provable sentence are true in all rank initial segments.)

So φ_{0} is not Ω-provable. Assuming the Ω-conjecture, one can force to make it false in some initial segment of the universe. That is, one can force to make the sentence “there is a least Woodin cardinal δ_{0} and H(δ_{0}^{+}) ⊧ θ(⌈φ_{0}⌉)” hold in some rank initial segment. Since the least Woodin cardinal in a rank initial segment of the universe really is the least Woodin cardinal, we appear to have forced to make φ_{0} Ω-provable in this extension, violating the absoluteness of the Ω-provability relation. However, the definability of Ω-provability in H(δ_{0}^{+}) depends on an integer parameter, the least Gödel number of the sentence ψ which is not Ω-provable but for which there is a δ_{0}-universally Baire set A of least Wadge rank such that all A-closed models satisfy “⊧_{Ω} ψ”; H(δ_{0}^{+}) cannot identify this ψ. This parameter may change from one forcing extension to the next - indeed it must in some cases, since as we shall see there are models in which the Ω-conjecture holds. So the resolution of this apparent contradiction is that our Gödel sentence no longer has its desired meaning in this forcing extension.

8.3. The AD^{+} conjecture. Woodin’s AD^{+} Conjecture is the statement that whenever A and B are sets of reals such that L(A, ℝ) and L(B, ℝ) satisfy AD^{+} and all sets of reals in L(A, ℝ) ∪ L(B, ℝ) are ℵ_{1}-universally Baire, then one of

(Δ ∼_{1}^{2})^{L(A,ℝ)}

and

(Δ ∼_{1}^{2})^{L(B,ℝ)}

contains the other. Assuming that this conjecture holds, ⊢_{Ω} is definable in H(𝔠^{+}), by essentially the same argument that was used above for H(δ_{0}^{+}), using Theorem 7.8. The point is that under the AD^{+} Conjecture, the members of the various classes (Δ ∼_{1}^{2})^{L(A,ℝ)} as above fall into a Wadge hierarchy definable in H(𝔠^{+}), and, by the Σ_{1}^{2} basis theorem for AD^{+}, every Ω-provable sentence is proved by one of them.

Woodin has shown that if there exists a measurable Woodin cardinal, then there exist sets of reals A, B such that L(A, ℝ) and L(B, ℝ) satisfy AD^{+} but the Wadge game for the pair (A, B) is not determined.

8.4. An argument against the Continuum Hypothesis. As noted at the end of Section 5, in the presence of a proper class of Woodin cardinals there is a universally Baire set of reals A simply definable from ℝ^{#} witnessing that for every sentence ψ, either

ZF C ⊢_{Ω} “H(ℵ_{1}) ⊧ ψ”

or

ZF C ⊢_{Ω} “H(ℵ_{1}) ⊧ ¬ψ.”

Suppose that ⊢_{Ω} were definable in H(𝔠^{+}), and suppose that the analogous situation were to hold for H(ℵ_{2}). That is, suppose that there were a true sentence φ giving an Ω-complete theory for H(ℵ_{2}), in the sense that for every sentence ψ, either

ZF C + φ ⊢_{Ω} “H(ℵ_{2}) ⊧ ψ”

or

ZF C + φ ⊢_{Ω} “H(ℵ_{2}) ⊧ ¬ψ.”

Aside from the requirement that φ be true, we know that there are such statements φ, for example, the ℙ_{max} axiom (∗) and its variants, again using this simple variant of ℝ^{#} as the universally Baire “proof.” The known examples of such axioms all imply the failure of the Continuum Hypothesis. In fact, if ⊢_{Ω} is definable in H(𝔠^{+}), this must be the case. Otherwise, if the Continuum Hypothesis held and V satisfied a statement which is Ω-complete for H(ℵ_{2}), in the sense above, then truth in H(ℵ_{2}) would be definable in H(ℵ_{2}) = H(𝔠^{+}), which contradicts Tarski’s theorem on the definability of truth. Woodin has shown more, that every Ω-complete sentence for H(ℵ_{2}) would imply that u_{2}, the least ordinal above ω_{1} which is a Silver indiscernible relative to every real number, is equal to ω_{2}.

The application of Tarski’s theorem can be extended to arbitrary uncountable cardinals. Suppose that λ is a definable cardinal, and that there is a true statement ψ which gives an Ω-complete theory for H(λ), in the sense that for every sentence ψ, either

ZF C + φ ⊢_{Ω} “H(λ) ⊧ ψ”

or

ZF C + φ ⊢_{Ω} “H(λ) ⊧ ¬ψ.”

Then we get a contradiction to Tarski’s theorem by supposing that ⊢_{Ω} is definable in H(λ). Since ⊢_{Ω} is definable in H(δ_{0}^{+}), it follows that there is no statement which gives an Ω-complete theory for H(δ_{0}^{+}).

8.5. An argument against the vagueness of the Continuum Hypothesis. It is a commonly held view that the Continuum Hypothesis is in some sense too vague to have a truth value. One argument in support of this view appeals to the fact that it is a theorem of ZFC that the truth value of CH can be changed by forcing. Formalizing this view, suppose then that one were to take the set of true sentences to be those which hold in all forcing extensions. Provability in Ω-logic, being definable in H(δ_{0}^{+}), is Δ_{2} in the language of set theory. If the Ω-conjecture holds, then the set of Π_{2} sentences true in all forcing extensions is then Δ_{2}. Thus if the set of true Π_{2} sentences is the set of such sentences true in every forcing extension, we have a collapse of the complexity of the definability hierarchy. If there is no such collapse, then the fact that one can force the Continuum Hypothesis to be either true or false is not the reason that it doesn’t have a truth value.

9. Proving the Ω-conjecture

As mentioned above, the Ω-conjecture is known to be consistent. In this final section we outline a method for proving the Ω-conjecture. This method works in certain inner models, and it is not known whether it can be used to prove the that Ω-conjecture holds in V. We begin by introducing the partial order (due to Woodin) known as the extender algebra (following the presentation in [4]).

9.1. L_{δ,γ}. For regular cardinals γ ≤ δ, let L_{δ,γ} be the propositional logic with variables a_{ξ} (ξ < γ), the usual connectives ∨, ∧, →, ↔ and ¬, plus infinitary conjunctions and disjunctions of size less than δ. In addition to the standard rules of inference for finitary propositional logic, proofs in L_{δ,γ} can use the infinitary version of DeMorgan’s Laws, can deduce any individual element from an infinitary conjunction, and can deduce an infinitary conjunction from all of its parts.

We let B_{δ,γ} denote the equivalence classes of L_{δ,γ} under mutual provability, and, for any L_{δ,γ} theory T we define the quotient algebra B_{δ,γ}/T by letting φ ∼ ψ if T ⊢ φ ↔ ψ.

A subset x of γ is naturally interpreted as a model in L_{δ,γ} by letting each a_{ξ} have the value True if and only if ξ ∈ x. Similarly, forcing with B_{δ,γ}/T produces a generic subset of γ. If M is a transitive model of (a suitable fragment of) ZFC and B_{δ,γ}/T (as defined in M) satisfies the δ-chain condition in M, then any subset x of γ (in M or not) which satisfies all the sentences of T is M-generic for B_{δ,γ}/T . This follows from the fact that any maximal antichain has size less than δ, which means that T proves its disjunction, which means that x satisfies its disjunction.

9.2. Extenders. Given uncountable cardinals κ < λ, a (κ, λ)-extender is a function E: [λ]^{<ω} \ {∅} → V_{k+2} such that

(1) each E(s) is a nonprincipal κ-complete ultrafilter on κ^{|s|};

(2) (coherence) whenever s ⊂ t are finite subsets of λ and a ⊂ |t| is the set of i such that the ith element of t is in s, X ∈ E(s) if and only if the set of ⟨ξ_{i} : i < |t|⟩ such that ⟨ξ_{i} : i ∈ a⟩ ∈ X is in E(t);

(3) (normality) for each s and each f: κ^{|s|} → λ such that

{a ∈ κ^{|s|} | f(a) < max(s)} ∈ E(s),

there exists a t ⊇ s in [λ]^{<ω} such that

{b ∈ κ^{|s|} | f(b) ∈ t} ∈ E(t).

We say that λ is the length of the extender E. Extenders satisfying condition (1) above are often called short extenders; these are sufficient for our needs. An extender gives rise to a directed system of wellfounded embeddings whose limit model may or may not be wellfounded, but does contain V_{λ}, if λ is a strongly inaccessible cardinal.

A system of extenders is a set of extenders indexed by some set contained in Ord × Ord, though for our purposes we can think of a system of extenders as simply a set of extenders.

Fixing a cardinal δ, we say that a set A ⊆ V_{δ} reflects to a cardinal κ < δ if for every λ < δ there is an elementary embedding j: V → M with critical point κ such that j(A) ∩ V_{λ} = A ∩ V_{λ}. A cardinal δ is Woodin if for each A ⊆ V_{δ} there is a κ < δ such that A reflects to κ.

Given a system E⃗ of extenders, let T_{δ,γ}(E⃗) be the deductive closure of the set of sentences of the form

⋁_{ξ<κ} φ_{ξ} ↔ ⋁_{ξ<λ} φ_{ξ},

where ⟨φ_{ξ} : ξ < λ⟩ is a sequence of sentences in L_{δ,γ} which reflects to κ.

If E⃗ witnesses that δ is Woodin, then W_{δ,γ}(E⃗) = B_{δ,γ}/T_{δ,γ}(E⃗) is δc.c.. To see this, note that if {[φ_{ξ}] : ξ < δ} is a set of elements of W_{δ,γ}(E⃗), then there is a κ < δ such that ⟨[φ_{ξ}] : ξ < δ⟩ reflects to κ, which means that for some λ ∈ (κ, δ),

⋁_{ξ<κ} φ_{ξ} ↔ ⋁_{ξ<λ} φ_{ξ},

so none of the members of {[φ_{ξ}] : κ < ξ < δ} is incompatible with all of the members of {[φ_{ξ}] : ξ < κ}.

9.3. Iteration trees. Given a transitive model M and an extender sequence E⃗ in M, an iteration tree is a tree T on some ordinal η, along with models M_{ξ} (ξ < η) and extenders E_{ξ} (for ξ such that ξ + 1 < η) and commuting elementary embeddings j_{ξν}: M_{ξ} → M_{μ} for ξ ≤_{T} ν such that

• M_{0} = M,

• 0 ≤_{T} ξ for all ξ < η,

• each E_{ξ} ∈ j_{0ξ}(E⃗),

• if α + 1 < η, then α has an immediate predecessor α^{∗} in T, and M_{α+1} is the ultrapower of M_{α^{∗}} by E_{α}, with j_{α^{∗}(α+1)} the induced embedding (we require that M_{α^{∗}} and M_{α} have a long enough initial segment in common for this to make sense, i.e. that all subsets of the critical point of E_{α} in M_{α^{∗}} are in M_{α}),

• if β < λ is a limit ordinal, M_{β} is the direct limit of the M_{α}’s

along some cofinal branch of T ↾β We can construe the construction of an iteration tree as a game

between player I and player II, where I constructs at successor stages, and II constructs at limit stages and the first player unable to continue the construction with a wellfounded model loses. We say that M is ηiterable if II has a strategy which avoids a loss in the version of this game that runs for η-stages.

The following remarkable theorem of Woodin says that every subset of η is generic over some iterate of any (η^{+} + 1)-iterable model.

Theorem 9.1. Let η be an infinite cardinal, let δ be an ordinal greater than η, and suppose that (M, E⃗) is (η^{+} + 1)-iterable, where M is a transitive model of ZF C of cardinality η and E⃗ is an extender sequence witnessing that δ is a Woodin cardinal in M. Suppose that for every (κ, λ)-extender in E⃗, κ > η and λ is a strongly inaccessible cardinal in M. Then for each x ⊆ η there exists an elementary embedding j: M → M^{∗} induced by an iteration tree on M such that x is M^{∗}- generic for j(W_{δ,η}^{M}(E⃗)).

Proof. We construct an iteration tree on M of length at most η^{+} + 1, using E⃗. We fix an η^{+} + 1-iteration strategy for (M, E⃗) and use it to pick the models a limit stages. At each successor stage, given the last model M_{α}, we are done if x is M_{α}-generic for j_{0α}(W_{δ,δ}(E⃗)). If not, there exist a (κ_{α}, λ_{α}) extender E_{α} ∈ j_{0α}(E⃗) and a sequence φ⃗ in M_{α} such that x fails to satisfy the corresponding axiom from j_{0α}(T_{δ,γ}(E⃗)). Let β ≤ α be minimal such that M_{α} and M_{β} have the same subsets of κ_{α}, apply E_{α} to M_{β}, and let M_{α+1} be the corresponding ultrapower. This completes the construction.

The requirement of applying each E_{α} to the earliest possible model gives that λ_{α_{1}} ≤ κ_{α_{2}} that whenever α_{0} <_{T} α_{1} + 1 <_{T} α_{2} + 1 are three consecutive nodes of T. Otherwise, since V_{λ_{α_{1}}}^{M_{α_{0}}} = V_{λ_{α_{1}}}^{M_{α_{1}+1}}, M_{α_{0}} and M_{α_{1}+1} would have the same subsets of κ_{α_{2}}, and E_{α_{2}} could have been applied to M_{α_{0}}. It follows that for all α <_{T} α′, λ_{α} ≤ κ_{α′}.

Now suppose that the construction ran for η^{+} + 1 stages. Take an elementary submodel X of a large enough H(θ) of cardinality η with M, x and the strategy used above as elements, and let α = X ∩ η^{+}. Then the image of M_{η^{+}} under the transitive collapse of X is M_{α}, and j_{α(η^{+}+1)} is the inverse π of the transitive collapse restricted to M_{α}. Let β + 1 be the successor of α along the cofinal branch leading to M_{η^{+}}, and let φ⃗ be the sequence of formulas used at stage β. Then x fails to satisfy ⋁ φ⃗↾κ_{β}, but satisfies ⋁ φ⃗↾λ_{β}. Since φ⃗↾κ_{β} ∈ M_{α}, π(φ⃗↾κ_{β}) = j_{α(η^{+}+1)}(φ⃗↾κ_{β}), By the elementarity of π, π(x) = x fails to satisfy ⋁ π(φ⃗↾κ_{β}). But φ⃗↾λ_{β} is an initial segment of j_{α(η^{+}+1)}(φ⃗↾β), since all subsequent embeddings along the cofinal branch after β have critical point at least λ_{β}, giving a contradiction. □

9.4. Proving the Ω-conjecture. At the end of Section 5 we discussed a definable function π coding elements of H(ℵ_{1}) by reals. Suppose that M is a countable transitive model of (a suitable fragment of) ZFC. We say that M has a universally Baire iteration strategy if (M, E⃗) has an ω_{1}-iteration strategy which is represented by a universally Baire set of reals A via π. The existence of such a strategy shows that (M, E⃗) is fully iterable (i.e., there is a definable class strategy for player II that works for games of all lengths). Moreover, if N is any A-closed model of ZFC with (M, E⃗) ∈ H(ℵ_{1})^{N}, then for any ordinal γ in N, N contains the fragment of this strategy for all iteration trees on (M, E⃗) in N of length γ or less. These facts follow from Theorem 6.2 plus the remarks at the of Section 5. Combined with Theorem 9.1, these facts present a possible route for proving the Ω-conjecture.

Theorem 9.2. Suppose that there exist proper class many Woodin cardinals. Let φ be a sentence such that ¬φ is not Ω-provable. Let δ be a Woodin cardinal, let E⃗_{0} be an extender sequence witnessing that δ is Woodin, let κ > δ be a strongly inaccessible cardinal, and suppose that X is a countable elementary substructure of V_{κ} such that (M, E⃗) has a universally Baire iteration strategy, where M is the transitive collapse of X and E⃗ is the image of E⃗_{0} under this collapse. Then there is a forcing extension in which some rank initial segment satisfies φ.

Proof. Let A be a universally Baire set of reals giving rise to an ω_{1}- iteration strategy for (M, E⃗) via π. Let N be a transitive A-closed model of ZFC with (M, E⃗) ∈ H(ℵ_{1})^{N}, such that for some limit ordinals α < β in N and some partial order P ∈ V_{β}^{N}, P forces in N that V_{α} ⊧ φ. Since (M, E⃗) is fully iterable in N, we may iterate (M, E⃗) in N to make V_{β}^{N} generic for this iterate M^{∗} of M (to apply Theorem 9.1, we need to first iterate M to a model M_{0} such that |V_{β}|^{N} ⊂ M_{0}, and then apply the theorem to this model). Then V_{β}^{N} is the V_{β} of this forcing extension of M^{∗}, so this forcing extension thinks that there exist such α and P. Since M is the transitive collapse of an elementary submodel of a suitable rank initial segment of V, this means that it is possible to force over V to make some rank initial segment satisfy φ. □

All of the currently known canonical inner models for large cardinals have the property that transitive collapses of countable elementary submodels of rank initial segments have universally Baire iteration strategies. The previous theorem then says that these models satisfy the Ω-conjecture. For all we know, it may be a theorem of ZFC that every iteration tree on a rank initial segment of the the universe has a unique cofinal wellfounded branch, if one uses short extenders (i.e., extenders as defined here) whose length is strongly inaccessible. If this is the case, then the Tree Production Lemma would imply that transitive collapses of rank initial segments of the universe are fully iterable with universally Baire iteration strategies (to see this, note that if (x, y) are reals such that x codes an iteration tree on a structure and y codes a cofinal branch through the tree, it is absolute to all wellfounded models containing x and y whether the corresponding limit model is wellfounded), and that the Ω-conjecture holds.

This scenario may not be the likeliest approach to proving the Ωconjecture. There are weaker iteration hypotheses which might hold for V and which would suffice. In another direction, Woodin has recently been developing an inner model which, in the presence of a supercompact cardinal, would contain all the large cardinals of V, and which would satisfy the Ω-conjecture [26]. This would show that the Ω-conjecture is consistent with all large cardinals.

References

[1] J. Bagaria, N. Castells, P.B. Larson, An Ω-logic primer, in : Set Theory, CRM 2003-2004, Birkhauser 2006, pp. 1-28

[2] P. Dehornoy, Progrés rècents sur l’hypothèse du continu (d’aprés Woodin), Sminaire Bourbaki 55me anne, 2002-2003, #915.

[3] Q. Feng, M. Magidor, W.H.Woodin, Universally Baire Sets of Reals. Set Theory of the Continuum (H. Judah, W.Just and W.H.Woodin, eds), MSRI Publications, Berkeley, CA, 1989, pp. 203-242, Springer Verlag 1992.

[4] I. Farah, The extender algebra and Σ_{1}^{2}-absoluteness, in preparation

[5] M. Foreman, M. Magidor, S. Shelah, Martin’s maximum, saturated ideals, and nonregular ultrafilters. I, Ann. of Math. (2) 127 (1988), no. 1, 1–47

[6] T. Jech, Set theory, 3d Edition, Springer, New York, 2003.

[7] A. Kanamori, The Higher Infinite. Perspectives in Mathematical Logic. Springer-Verlag. Berlin, 1994. Large cardinals in set theory from their beginnings.

[8] A. Kechris, E. Kleinberg, Y. Moschovakis, W.H. Woodin, The axiom of determinacy, strong partition properties, and nonsingular measures, in : Cabal Seminar 77–79 (Proc. Caltech-UCLA Logic Sem., 1977–79), Lecture Notes in Math., 839, Springer, Berlin-New York, 1981, pp. 75–99

[9] R. Ketchersid, More structural properties of AD and AD^{+}, to appear in the Proceedings of the 2009 Boise Extravaganza in Set Theory

[10] K. Kunen, A model for the negation of the axiom of choice, in: Cambridge Summer School in Mathematical Logic (Cambridge, 1971), Lecture Notes in Math. Vol. 337, Springer, Berlin, 1973, pp. 489–494

[11] P.B. Larson, The Stationary Tower. Notes on a course by W. Hugh Woodin. University Lecture Series, Vol. 32. American Mathematical Society, Providence, RI. 2004.

[12] A. Levy, R. Solovay, Measurable cardinals and the continuum hypothesis, J. Symbolic Logic 34 (1969) 4, 654-655

[13] D.A. Martin, Measurable cardinals and analytic games, Fund. Math. 66, 1970, 440-442 [14] D.A. Martin, R. Solovay, R., A basis theorem for Σ_{3}^{1} sets of reals, Ann. of

Math. 89, 1969, 138–159

[15] D.A. Martin, J.R. Steel, A proof of projective determinacy, J. Amer. Math. Soc. 2 (1989), no. 1, 71–125

[16] Y. Moschovakis, Descriptive set theory, Second edition. Mathematical Surveys and Monographs, 155. American Mathematical Society, Providence, RI, 2009

[17] I. Neeman, Optimal proofs of determinacy, Bull. Symbolic Logic 1 (1995), no. 3, 327–339

[18] I. Neeman, Determinacy in L(ℝ), in: The Handbook of Set Theory, M. Foreman, A. Kanamori, eds., Springer, 2010

[19] J. Steel, The derived model theorem, in : Logic Colloquium 2006, Lecture Notes in Logic, Association of Symbolic Logic, Chicago, IL, 2009, pp. 280-327

[20] W.H. Woodin, Supercompact cardinals, sets of reals, and weakly homogeneous trees, Proc. Nat. Acad. Sci. U.S.A. 85 (1988), no. 18, 6587–6591

[21] W.H.Woodin, The Continuum Hypothesis. Proceedings of the Logic Colloquium, 2000. To appear.

[22] W.H.Woodin, The Ω-Conjecture. Aspects of Complexity (Kaikoura, 2000), de Gruyter Ser. Log. Appl., Vol. 4, pages 155-169, de Gruyter, Berlin, 2001.

[23] W.H.Woodin, The Continuum Hypothesis, I. Notices Amer. Math. Soc., 48(6):567-576, 2001.

[24] W.H.Woodin, The Continuum Hypothesis, II. Notices Amer. Math. Soc., 48(7):681-690, 2001; 49(1):46, 2002.

[25] W.H.Woodin, Set theory after Russell; The journey back to Eden, in : One hundred years of Russell’s paradox, 29–47, de Gruyter Ser. Log. Appl., 6, de Gruyter, Berlin, 2004

[26] W.H.Woodin, Suitable extender sequences, in preparation

Department of Mathematics, Miami University, Oxford, OH 45056, USA

  E-mail address: larsonpb@muohio.edu