An Introduction to Determinacy and Large Cardinals

(Mengenlehre und Logik III)

Bonn, WS 2001/2002

Peter Koepke

25. November 2001

Inhaltsverzeichnis

1 Introduction: The Position of Descriptive Set Theory within Set Theory 2

2 Descriptive Set Theory over the Hereditarily Finite Sets 5 2.1 Topological Complexities . . . . . . . . . . . . . . . . . . . . . 6 2.2 Projective Complexities . . . . . . . . . . . . . . . . . . . . . 8

3 Regularity Properties 10

4 Game-Theoretic Characterizations of Regularity Properties 12 4.1 Infinitary Games . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.2 The Perfect Subset Property . . . . . . . . . . . . . . . . . . . 13 4.3 Lebesgue-Measurability . . . . . . . . . . . . . . . . . . . . . . 14

1 INTRODUCTION: THE POSITION OF DESCRIPTIVE SET THEORY WITHIN SET THEORY2

5 Determinacy Axioms 15 5.1 Some Consequences . . . . . . . . . . . . . . . . . . . . . . . . 15 5.2 Some Complexities Associated to Determinacy . . . . . . . . . 17 6 Open/Closed Determinacy: The Gale-Stewart Theorem 17

6.1 Borel-Determinacy . . . . . . . . . . . . . . . . . . . . . . . . 19

7 Analytic Sets 20 7.1 A First Normal Form . . . . . . . . . . . . . . . . . . . . . . . 20 7.2 Tree Representations for Analytic Sets . . . . . . . . . . . . . 21 7.3 The Boundedness Theorem . . . . . . . . . . . . . . . . . . . . 25 7.4 Solovay Unfolding . . . . . . . . . . . . . . . . . . . . . . . . . 26

8 Closed Unbounded Filters 28

9 Measurable Cardinals from AD 30

10 Measurable Cardinals under AC 34 10.1 Ultrapowers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 10.2 Combinatorial Consequences . . . . . . . . . . . . . . . . . . . 37 10.3 The Rowbottom Theorem . . . . . . . . . . . . . . . . . . . . 38

11 Analytic Determinacy from a Measurable Cardinal 40

12 Borel-Determinacy 41

13 Some Combinatorial Principles Related to Borel Determinacy 41

1 Introduction: The Position of Descriptive Set Theory within Set Theory

The development of the field of descriptive set theory is closely linked to central questions in the foundations of mathematics. From a technical viewpoint the general question What is Mathematics? has the quite satisfying answers: the mathematical objects are sets and the mathematical methods are those of first-order predicate logic. To understand the mathematical universe one has to understand the Cantorean universe of all sets which is almost universally axiomatized by the system of Zermelo-Fraenkel set theory. The fundamental question then turns into what sets do exist? Such questions reach back into the 19th century: what are numbers, what is space, what are functions. Cantorean set theory has unified these questions into questions about sets. The technical work of Cantor strived to classify all possible sets according to the way they were built from simpler constituents. Cantor hoped to analyse all sets of real numbers as built from topologically simple pieces and countably many extra points (the Cantor-Bendixson-Theorem). This program had rather limited success, and we know from modern axiomatic set theory that the analysis of “most” sets is beyond the boundaries of the systems ZF or ZFC (Zermelo-Fraenkel set theory without or with the axiom of choice). In relation to the grand questions of general set theory, descriptive set theory concentrates on a very modest approach. One restricts the attentention basically to sets of real numbers and studies them under a limited range of criteria, namely whether they possess regularity properties. This means that they allow a classification under various measure of size like cardinality, Baire measure, or Lebesgue measure. The sets under consideration are built simply from basic sets. They could be called descriptive, meaning that they could be described or obtained through simple operations. The early descriptive set theorists (Baire, Borel, Lebesgue, Hausdorff, Alexandroff, Souslin, Luzin) introduced several classifications of simple sets (Borel hierarchy, projective hierarchy) and proved regularity properties for sets in these classes. Part of this theory was presented in the previous lecture course. The early work in the field provided a satisfying theory of Borel sets with generalizations to the first and sometimes second level of the projective hierarchy. The suspicion expressed by some that the regularity of the higher levels were outside the scope of the usual set theoretical foundations was first vindicated by Gödel’s study of descriptive set theory within his model of constructible sets. There is widespread agreement, though, that the “real” mathematical universe should not be the constructible universe, and that one should look for further set theoretical axioms which imply that complicated sets of reals have regularity properties. We only mention some foundational questions raised. The French school of early descriptive set theorists (or rather descriptive function theorists advocated the restriction of universe of discourse to descriptive sets and functions. On the other hand, postulating further axioms poses the question of their justification, which of course transcends the technical side of the theory. In these lectures, we shall be content with the pragmatic justification, that certain assumptions lead to a mathematically rich and satisfying theory of (projective) sets of reals. Let us consider a concrete regularity question. We have seen that the perfect subset property holds for Σ_{1}^{1}-sets. Does PSP hold for Π_{1}^{1}-sets, which is the pointclass consisting of the complements of Σ_{1}^{1}-sets? It has been shown that the answer depends on the model / situation where one is working: in Gödel’s constructible model, one can define Π_{1}^{1}-sets without the perfect subset property. We shall, however, consider hypotheses which imply that every Π_{1}^{1}-set has the perfect subset property. So the perfect subset property for Π_{1}^{1}-sets is not decided by ZF(C). We shall consider two types of extensions of the axiomatic system: determinacy assumptions and large cardinals. Regularity Properties can by characterized through the existence of winning strategies in certain infinitary games. Determinacy axioms postulate the existence of such strategies and thus regularity properties. Large cardinal axioms state that there are uncountable cardinalities which have a very regular behaviour in terms of infinitary combinatorics. It is surprising that this behaviour influences the realm of real numbers, and in particular that strong large cardinal assumptions imply determinacy axioms. This course focusses on the determinacy of games which have an analytic,i.e., Σ_{1}^{1}-winning set. This level of determinacy implies that every Π_{1}^{1}-set has the perfect subset property. Analytic determinacy is implied by the existence of measurable cardinals. And actually we can obtain measurable cardinals from AD, the Axiom of Determinacy. After having learnt a sufficient amount of determinacy in the context of large cardinals we shall restrict to the system ZF(C) and prove the determinacy of all Borel sets. Descriptive set theory often has to use complicated coding mechanisms to express a variety of mathematical objects as real numbers. In our presentation we try to avoid some of these technicalities by using the set H_{ω} of hereditarily finite sets as underlying set. Since (H_{ω}, ∈) is a model of all axiom of ZFC except the axiom of infinity, most mathematical notions can be defined naturally over (H_{ω}, ∈), and if their basic properties do not depend on the axiom of infinity, they can be used in the normal way. So we do not need to say that a descriptive objects “codes” a function or a tree, we can simply stipulate that it is a function or a tree.

2 DESCRIPTIVE SET THEORY OVER THE HEREDITARILY FINITE SETS5

2 Descriptive Set Theory over the Hereditarily Finite Sets

Set theory is the mathematical study of the infinite, finite objects are considered to be basic and simple. Whereas this usually means, that the natural numbers are taken as basic objects, we prefer to take the set of all hereditarily finite sets, i.e., those which are finite, and all whose iterated elements are finite:

H_{ω} = {a|card(TC(a)) < ω} = {a|the transitive closure of a is finite}.

Of course, H_{ω} = V_{ω}, which is the ω^{th} level of the von Neumann hierarchy. The strong closure properties of the class of finite sets implies that all ZFCaxiom are true in (H_{ω}, ∈), except of course the axiom of infinity. So we can start a standard development to set theory within (H_{ω}, ∈). This includes the basic set operations of unions (∪), intersections (∩), and set differences (\), the theory of ordered pairs, relations, and functions, and the theory of von Neumann ordinals, which are equal to the natural numbers in this context. The schemas of induction and recursion, whose proofs do not require the axiom of infinity, hold in (H_{ω}, ∈), and so we can define the usual arithmetical operations. Actually, (H_{ω}, ∈) satisfies a stronger a second-order set theory which takes the collection of subclasses of H_{ω} as given. Let us define an appropriate second order language L^{II} which will also be the basis for the definability considerations of descriptive set theory. L^{II} has first order variables x_{0}, x_{1}, …, for elements of H_{ω} and second order variables X_{0}, X_{1}, … for subsets of H_{ω}. We use letters x, y, z, … and X, Y, Z, … resp. to denote both kinds of variables. The atomic formulas of L^{II} are of the form x = y, x ∈ y, and X(x⃗) where x⃗ is a vector of variables of the right length. We shall not go into the question of arities of second order variables, since the model H_{ω} is anyway closed under the formation of ordered pairs and tuples. Formulas of L^{II} can be joined by the usual propositional connectives ¬, ∧, ∨, →, ↔. We can quantify with respect to first and second order variables x and X: if ϕ is a formula then ∃xϕ, ∀xϕ, ∃Xϕ, and ∀Xϕ are formulas of L^{II}. The satisfaction relation

(H_{ω}, ∈) ⊧ ϕ[P_{0}, …, P_{m−1}, p_{0}, …, p_{n−1}]

for ϕ ∈ L^{II}, P_{0}, …, P_{m−1} ⊆ H_{ω} and p_{0}, …, p_{n−1} ∈ H_{ω} is defined in the obvious way. One can view the majority of descriptive set theory as the study of sets which are L^{II}-definable over (H_{ω}, ∈). A priori, such sets are subsets of some product 𝔓(H_{ω}) × ⋯ × 𝔓(H_{ω}) × H_{ω} × ⋯ × H_{ω}. Since 𝔓(H_{ω}) × 𝔓(H_{ω}) can be injected into 𝔓(H_{ω}) by the function (A, B) ↦ A × B, and since H_{ω} is closed relative to ordered tuples, we can view all L^{II}-definable sets as subsets of 𝔓(H_{ω}). Descriptive set theory considers elements of 𝔓(H_{ω}) as points (in some space), subsets of 𝔓(H_{ω}), i.e., elements of 𝔓𝔓(H_{ω}), are pointsets, and subsets of 𝔓𝔓(H_{ω}) are pointclasses, which means: class of pointsets. Let us introduce some classifications of pointsets according to the complexities of their definitions A formula of L^{II} is called a first order formula if it contains no second order quantification; let L^{I} be the set of such first order formulas.

2.1 Topological Complexities

Definition 2.1 (a) A ⊆ 𝔓(H_{ω}) is called basic if there are p_{0}, …, p_{n−1} ∈ H_{ω} and a quantifier-free formula ϕ such that A = {P |(H_{ω}, ∈) ⊧ ϕ[P, p_{0}, …, p_{n−1}]}.

(b) A ⊆ 𝔓(H_{ω}) is called open if it is a union of basic sets. A is called closed if its complement 𝔓(H_{ω}) \ A is open.

(c) The class of Borel sets is the smallest pointclass B ⊂ 𝔓𝔓(H_{ω}) which contains all open sets and is closed under complementations and countable unions: B ∈ B → 𝔓(H_{ω}) \ B ∈ B and (B_{i})_{i<ω} ⊆ B → ⋃_{i<ω} B_{i} ∈ B.

Remarks: 1. Obviously, the class of open sets is a topology on 𝔓(H_{ω}). The topology is Hausdorff: if P, Q ∈ 𝔓(H_{ω}), P ≠ Q there is some p ∈ H_{ω} such that p ∈ P ↔ p ∉ Q. Assume by symmetry that p ∈ P and p ∉ Q. Then P and Q are separated by the disjoint basic sets {R|R(p)} and {R|¬R(p)}. The topology is second countable since there are countably many basic sets.

2. If A is a basic set then the quantifier-free formula ϕ defining A = {P | …} is logically equivalent to some quantifier-free formula ϕ′ in disjunctive normal form. The components of the disjunction are conjunctions of atomic formulas or negated atomic formulas. The atomic formulas without second order variables are constantly true or false; the only occuring second order variable corresponds to P. So a component is equivalent to b_{0} ∈ P ∧ … ∧ b_{k−1} ∈ P ∧ c_{0} ∉ P ∧ … ∧ c_{l−1} ∉ P for some hereditarily finite sets b⃗ and c⃗. If χ_{P} is the characteristic function of P, this is equivalent to χ_{P} (b_{0}) = ⋯ = χ_{P} (b_{k−1}) = 1 ∧ χ_{P} (c_{0}) = ⋯ = χ_{P} (c_{l−1}) = 0. This shows that the basic open of sets of our topology are basically basic open sets of the product topology on ∏_{a∈H_{ω}}{0, 1}. So our topology on 𝔓(H_{ω}) is homeomorphic to ∏_{a∈H_{ω}}{0, 1} which is of course homeomorphic to ∏_{n<ω}{0, 1}. Since the latter is often identified with the reals in descriptive set theory, we may also write ℝ = 𝔓(H_{ω}).

3. Since the basic sets are defined via quantifier-free formulas, the basic sets form a Boolean subalgebra of 𝔓𝔓(H_{ω}) = 𝔓(ℝ). So a basic set is clopen (= closed and open). We argue that conversely every clopen set A is basic: By the previous remark, 𝔓(H_{ω}) is homeomorphic to ∏_{n<ω}{0, 1} which is compact. So A is compact. Since A is open it is some union of basic sets. By compactness, A is indeed a finite union of basic sets, and thus A is a basic set itself. Let us consider some examples of relevant sets of “reals”; we want to see that most of them are of low topological complexity.

4. The set REL = {R|R is a relation} = {R|∀c(c ∈ R → ∃a∃bc = {a, b})} is closed: If some R is not a relation, there is c ∈ R which is not an ordered pair. But then {P |c ∈ P } is a neighbourhood of R which does not intersect REL. Similarly the sets of functions and of injective functions are closed.

5. The set TREE = {T |T is a tree} is closed: If T is not a tree, then T is not a relation, or it is a relation in which some element has two incomparable predecessors, or some element is not above the unique minimal element. These conditions are open.

6. If ϕ(X, x⃗, Z⃗, z⃗) is a quantifier-free formula, Q⃗ ⊆ H_{ω}, and q⃗ ∈ H_{ω}, then A = {P |(H_{ω}, ∈) ⊧ ∀x⃗ϕ(P, x⃗, Q⃗, q⃗)} is closed, since it is a countable intersection of basic (and closed) sets.

7. From the definition of a Borel set it is not clear that a Borel set is (second order) definable over H_{ω} since it is defined via infinitary unions. We shall see, however, that all Borel sets have a uniform definition over H_{ω} in parameters. These parameters are then codes for the set in question, in this case they are called Borel codes. The intended operations on the pointclasses correspond to certain operations on the codes. It will be very important later to introduce efficient coding methods for pointclasses. The set of codes as well as the mentioned operations on codes should be definable over H_{ω}. For basic sets and for Borel sets we introduce the following coding methods:

Definition 2.2 (a) A characteristic function f : dom(f) → 2, f ∈ H_{ω} is called a basic code. f canonically codes the basic set B_{f} = {P ∈ ℝ|χ_{P} ⊇ f}.

(b) Fix two distinguished sets ˙¬ ∈ H_{ω} and ˙⋃ ∈ H_{ω}. A Borel code is a non-empty well-founded tree (c, ⊇) ⊆ (H_{ω}^{<ω}, ⊇) such that

• if s ∈ c is a terminal node in c then s(|s| − 1) is a basic code;

• if s ∈ c is not a terminal node in c then s(|s|−1) = ˙⋃ or s(|s|−1) = ˙¬;

• it s ∈ c and s(|s| − 1) = ˙¬ then s has a unique ⊆-predecessor in c.

(c) A Borel code c is decoded as follows: define a decoding function D_{c} : c → 𝔓(ℝ) by recursion on the well-founded tree c:

• if s ∈ c is a terminal node in c with last element f = s(|s| − 1) then let D_{c}(s) = B_{f};

• if s ∈ c has last element s(|s| − 1) = ˙⋃ then let D_{c}(s) = ⋃{D_{c}(t)|t ∈ c ∧ t ⊇ s ∧ |t| = |s| + 1};

• if s ∈ c has last element s(|s|−1) = ˙¬ then let D_{c}(s) = ℝ\D_{c}(t) where t is the unique predecessor of s in c.

Then the Borel set coded by c is B_{c} = D_{c}(∅).

Obvious manipulations with Borel codes show that the class of set B_{c} thus defined contains all open sets and is closed under complementations and countable unions. On the other hand, an induction along the Borel code c shows that every set D_{c}(s) is indeed a Borel sets. So the function c ↦ B_{c} is a surjection onto the class of all Borel sets. One can show by diagonalization that the set of Borel codes is not a Borel set. It can be classified, however, as a projective set.

2.2 Projective Complexities

Definition 2.3 (a) A set A ⊆ 𝔓(H_{ω}) is called arithmetical (in class parameters) if there is are sets P_{1}, …, P_{n} ⊆ H_{ω} and a first-order sentence ϕ such that A = {P_{0}|(H_{ω}, ∈) ⊧ ϕ[P_{0}, P_{1}, …, P_{n}]}.

(b) A set A ⊆ 𝔓(H_{ω}) is called projective if there is are sets P_{1}, …, P_{n} ⊆ H_{ω} and a second-order sentence ϕ such that A = {P_{0}|(H_{ω}, ∈) ⊧ ϕ[P_{0}, P_{1}, …, P_{n}]}.

(c) A set A ⊆ 𝔓(H_{ω}) is Σ_{n}^{1} (over H_{ω}) if there is are sets P_{1}, …, P_{n} ⊆ H_{ω} and a second-order sentence of the form ϕ = ∃U_{n}∀U_{n−1} … QU_{1}ψ starting with an alternating sequence of second-order quantifiers where ψ is a firstorder formula such that A = {P_{0}|(H_{ω}, ∈) ⊧ ϕ[P_{0}, P_{1}, …, P_{n}]}. A is called analytic if it is Σ_{1}^{1}.

(d) A set A ⊆ 𝔓(H_{ω}) is Π_{n}^{1} (over H_{ω}) if there is are sets P_{1}, …, P_{n} ⊆ H_{ω} and a second-order sentence of the form ϕ = ∀U_{n}∃U_{n−1} … QU_{1}ψ starting with an alternating sequence of second-order quantifiers where ψ is a firstorder formula such that A = {P_{0}|(H_{ω}, ∈) ⊧ ϕ[P_{0}, P_{1}, …, P_{n}]}.

Remarks: 1. The structure (H_{ω}, ∈) interprets the structure (ℕ, +, ×, 0, 1) and vice versa; the non-trivial direction involves a Gödel-type coding of finite sets by natural numbers. Therefore the above definitions over H_{ω} are equivalent to the corresponding definitions over ℕ. These definitions are equivalent to the corresponding definitions over the underlying structure (ℕ, +, ×, 0, 1). Note that the arithmetical operations are definable in (H_{ω}, ∈). As usual, formulas of the second-order language are logically equivalent to formulas in prenex normal form, which start with a block of quantifiers and are quantifier-free otherwise. First-order quantifiers can be substituted by second-order quantifiers in the following way: ∀u_{s}QU_{r_{m}} … QU_{r_{1}} ϕ is logically equivalent to: ∀U_{s}QU_{r_{m}} … QU_{r_{1}} (∀u_{s}(∀w(w ∈ u_{s} ⟺ U_{s}(w)) → ϕ). Since we can introduce dummy quantifiers, every formula is equivalent to one as in parts (c) or (d) of the definition . Thus:

Theorem 2.1 A set A ⊆ 𝔓(H_{ω}) is projective iff it is Σ_{n}^{1} (Π_{n}^{1}) for some n.

Computations of complexities in the projective hierarchy are based on some rules which are contained in the following theorem:

Theorem 2.2 (a) The class of arithmetical sets is closed under (finite) unions, intersections, and complementations.

(b) Every projective class Σ_{n}^{1} and Π_{n}^{1} is closed under finite unions and intersections.

Let us look at some specific sets in 𝔓(ℝ):

1. Any arithmetic set is Borel since quantification by the first-order quantifiers ∃x and ∀x correspond to countable unions and intersections.

2. Many simple set theoretic (= mathematical) concepts are arithmetical. We can construe integers (ℤ) as certain pairs of natural numbers, rationals (ℚ) are certain pairs of integers. The arithmetical operations on these numbers are arithmetical (without parameters) in the sense of our definition.

3. There are many ways to define the classic real numbers ℝ over H_{ω}. In the following formalisation the standard topology of the classic real numbers is the relative topology of the topology on 𝔓𝔓(H_{ω}): a pair (L, R) ⊆ H_{ω} × H_{ω} is a (classic) real number, if

• L and R are sets of rational numbers, and ∀p ∈ L∀q ∈ R p < q;

• the left and right halfs are “open”, i.e., ∀p ∈ L∃q ∈ L p < q and ∀q ∈ R∃p ∈ R p < q;

• the remainder ℚ \ (L ⋃ R) has at most one element.

Let ℝ^{cl} be the set of standard real numbers.If the remainder is empty (L, R) is an irrational Dedekind cut; if the remainder contains an element q then (L, R) is basically the Dedekind cut for q. The set of reals is definable over H_{ω} by a first-order ∀∃-formula. This corresponds to a countable intersection of a countable union of basic sets, i.e., a countable intersection of open sets, i.e., a G_{δ}-set. It is easy to check, that the relative topology on ℝ^{st} is the classical topology on ℝ^{st}. There is a general theorem by Hausdorff that a G_{δ}-set in a polish space is itself polish.

3 Regularity Properties

The Borel sets as defined above are usually considered to be well-understood objects. Due to their “concrete” definition out of simple building blocks, their existence is not at issue in foundational discussions. The foundations of ordinary mathematics would be easy if every mathematically relevant set would turn out to be a Borel set. Indeed, Lebesgue claimed just that in his 1905 paper. The crucial mistake, however, was the claim that a projection of a Borel set was again Borel. The discovery of that mistake by Souslin marked the beginning of descriptive set theory beyond the Borel sets. Borel sets are attractive since they are amenable to various “measures of size”. Alexandroff and Hausdorff have shown that every Borel set B satisfies the Continuum Hypothesis: card(B) ≤ ℵ_{0} or card(B) = 2^{ℵ_{0}}, i.e., B is either “small” or as “large” as possible, difficult intermediate values are excluded. This was shown by Alexandroff and Hausdorff through the perfect subset property which is a typical regularity property:

Definition 3.1 (a) A tree (T, ⊆) ⊆ (H_{ω}^{<ω}, ⊆) is perfect if ∀r ∈ T ∃s, t ∈ T (r ⊆ s ∧ r ⊆ t ∧ ¬s ⊆ t ∧ ¬t ⊆ s).

(b) A set A ⊆ ℝ is perfect if it is empty, or there is a perfect tree (T, ⊆) such that A = {P |P ∈ (H_{ω})^{ω} ∧ ∀n < ω P ↾ n ∈ T }.

(c) A set A ⊆ ℝ has the perfect subset property (PSP) if it is at most countable or it possesses a non-empty perfect subset.

Theorem 3.1 (Alexandroff;Hausdorff) Every uncountable Borel subset of ℝ has a perfect subset.

The classic measure on Borel sets is probably the most universal measure of size in mathematics. Borel and Lebesgue have shown how to define a measure function μ on all Borel sets such that:

• if a_{0}, …, a_{m−1} and b_{0}, …, b_{n−1} are pairwise distinct elements of H_{ω} then μ({P ⊆ H_{ω}|a_{0} ∈ P ∧ … ∧ a_{m−1} ∈ P ∧ b_{0} ∉ P ∧ … ∧ b_{n−1} ∉ P }) = 2^{−(m+n)};

• μ is countably additive: if (B_{n})_{n<ω} is a sequence of pairwise disjoint Borel sets then μ(⋃_{n<ω} B_{n}) = ∑_{n<ω} μ(B_{n}).

It is a non-trivial task to construct μ since one has to show that different representations of the same Borel set B by complementations and disjoint unions yield the value for μ(B).

Definition 3.2 (a) A set N ⊆ ℝ has measure zero (is a null set) if there is a Borel set B with N ⊆ B and μ(B) = 0.

(b) A set X ⊆ ℝ is Lebesgue measurable if there is a Borel set B such that the symmetric difference X△B is a measure zero set.

Null sets are negligable sets of reals in certain situations. Another notion of negligable set is given by:

Definition 3.3 (a) X ⊆ ℝ is nowhere dense if every non-empty basic set B possesses a non-empty basic subset C ⊆ B such that X ∩ C = ∅.

4 GAME-THEORETIC CHARACTERIZATIONS OF REGULARITY PROPERTIES12

(b) Y ⊆ ℝ is meager if Y = ⋃_{n<ω} X_{n} for a sequence (X_{n})_{n<ω} of nowhere dense sets.

(c) A set X ⊆ ℝ has the Baire property if there is a Borel set B such that the symmetric difference X△B is a meager set.

Regularity Properties can be seen as an attempt to hold up the Borel perspective in a non-Borel world: sets are considered to be well-behaved, or regular, it they differ from Borel sets by some negligable difference. Such a neglibable difference could mean for example “at most countable”, or “measure zero”, or “meager”. Ideally, every set of real numbers would be at least regular. Results of axiomatic set theory show that this assumption can consistently be made if one accepts certain hypotheses. In the Solovay model which is an extension of a model of set theory obtained by forcing, every set of reals is regular. Assuming strong determinacy hypotheses, every set of reals is regular. The strong determinacy hypotheses can in turn be justified by the use of large cardinals. One has to note, however, that the axiom of choice implies non-regularities:

Theorem 3.2 (ZFC) There is a set X ⊆ [0, 1] which is not Lebesguemeasurable.

Proof: By a diagonal-argument, based on a well-ordering of ℝ. qed Remark 1. This result is usually carried out via a Vitali-set.

2. One can refine the argument and control the complexity of the nonmeasurable set in relation to the complexity of a given well-ordering of ℝ.

4 Game-Theoretic Characterizations of Regularity Properties

The modern development of descriptive set theory was initiated by the game theoretic perspective. We shall define infinitary two-player games and present games which are adequate for treating regularity properties of given sets of reals.

4.1 Infinitary Games

We introduce some game theoretic notions:

Definition 4.1 (a) G is a game on X if G ⊆ X^{ω}. The elements of X^{ω} are called plays (in the game G). The elements of G are called winning plays for player I. We say that player I wins the play p in the game G if p ∈ G. We say that player II wins the play p in the game G if p ∉ G.

(b) σ is a strategy on X if σ : X^{<ω} → X.

(c) Let G be a game on X and let σ be a strategy on X. σ is a winning strategy for player I in G if ∀p ∈ X^{ω}((∀n < ω p(2n) = σ(p ↾ 2n)) → p ∈ G). Similarly τ is a winning strategy for player II in G if ∀p ∈ X^{ω}((∀n < ω p(2n + 1) = σ(p ↾ (2n + 1)) → p ∉ G).

(d) The game G on X is determined if player I or player II has a winning strategy in G.

Remarks: 1. Determinacy possesses some features of a regularity property. We shall see in particular that all Borel sets are determined.

2. A game can be visualized as a “temporal” sequence (x_{0}, x_{1}, …) of alternating moves by players I and II:

\begin{matrix}I & x_{0} & & x_{2} & & x_{4} & & … \\ II & & x_{1} & & x_{3} & & x_{5} & & … \end{matrix}

Player I aims at steering the play into the winning set G whereas II aims at avoiding G.

4.2 The Perfect Subset Property

If some A ⊆ 2^{ω} has a non-empty perfect subset P then this immediately implies that Player I can ensure that a 0-1-sequence is an element of A where Players I and II draw alternately finite sequences of O’s and 1’s resp. 0’s and 1’s. So Player I is able to win this kind of “game”.

Definition 4.2 The *-game G_{2}^{∗}(A) adequate for the perfect subset property of A.

(1). If A contains a non-empty perfect subset then I has a winning strategy in G_{2}^{∗}(A). (2). The converse of (1). (3). If A is countable, II has a winning strategy. Proof: An easy diagonal argument. (4). If II has a winning strategy τ then A is countable.

Proof: A 0-1-sequence x in A can not come from a run in which II uses τ. So there must be an initial segment of x which can be construed as an initial play according to τ but which cannot be lengthened into a longer play according to τ. This fact allows x to be reconstructed recursively from the initial play. Since there are contably many initial plays, A must be countable. qed

Theorem 4.1 (M. Davis, 1964) For A ⊆ 2^{ω}:

(a) I wins G_{2}^{∗}(A) iff A has a non-empty perfect subset.

(b) II wins G_{2}^{∗}(A) iff A is countable.

(c) G_{2}^{∗}(A) is determined iff A satisfies PSP.

(d) If all games G_{2}^{∗}(A) are determined, every A satisfies PSP, hence the continuum hypothesis holds (without AC!).

4.3 Lebesgue-Measurability

The relation between Lebesgue-measurability and determinacy of games is more subtle. We motivate a game, in which II is supposed to cover a given set by a small cover of intervals.

Definition 4.3 (The Covering Game) For ϵ > 0: G(A, ϵ).

Theorem 4.2 Let A ⊆ 2^{ω}, ϵ > 0.

(a) If I wins G(A, ϵ) then there is a Lebesgue-measurable B ⊆ A with μ(B) > 0.

(b) If II wins G(A, ϵ) then there is an open set O ⊇ A with μ(O) < ϵ.

The Lebesgue-measurability of a set X ⊆ ℝ: Usual measure-theoretic techniques yield a set L ⊇ X, L Lebesgue-measurable, so that there is no Lebesguemeasurable set B ⊆ L \ X which has positive measure. The above theorem implies:

Theorem 4.3 If all games G(L \ X, ϵ) for ϵ > 0 are determined then X is Lebesgue-measurable.

Theorem 4.4 (a) If every set of real numbers is determined then every set of real numbers is Lebesgue-measurable.

(b) There are “local” version of (a) at various levels of the projective hierarchy.

Proof: The set of moves of G(A, ϵ) is countable. Thus G(A, ϵ) can be seen as a game on ω. qed

5 Determinacy Axioms

Definition 5.1 (a) Det(K) denotes that every set in K is determined.

(b) Borel-determinacy: Det(Δ_{1}^{1}).

(c) Analytic determinacy: Det(Σ_{1}^{1}).

(d) Projective determinacy (PD): Det(⋃_{n<ω} Σ_{n}^{1}).

(e) The Axiom of Determinacy (AD): Det(𝔓(ℝ).

(f) The Axiom of Real Determinacy (AD_{ℝ}): Det(𝔓(ℝ^{ω})).

Remarks: 1. In the sequel we shall restrict to point classes K ⊆ 𝔓(X^{ω}) where X is countable.

2. There are also “lightface” versions of these determinacy axioms.

3. We have already shown that AD together with AC are inconsistent. One can prove this directly by enumerating all possible strategies in ordertype ℵ = 2^{ℵ_{0}} (under AC) and constructing a non-determined set recursively by a diagonal argument much like the diagonal construction of a non-Lebesgue-measurable set above.

4. Determinacy is a principle which can be seen as a principle of some infinitary logic: ∃c_{0}∀c_{1}∃c_{2}∀c_{3} … (c_{0}, c_{1}, c_{2}, c_{3}, …) ∈ G ⇔ I has a winning strategy for G ⇔ II does not have a winning strategy for G ⇔ ¬∀c_{0}∃c_{1}∀c_{2}∃c_{3} … (c_{0}, c_{1}, c_{2}, c_{3}, …) ∉ G. Finite versions of this principle are tautologies of first-order logic.

5.1 Some Consequences

Theorem 5.1 (ZFC) Let K ⊆ X^{ω} be a good enough pointclass. Then Det(K) implies Det(∼ K) where ∼ K = {x^{ω} \ A|A ∈ K}.

Proof: Let G ∈∼ K. For x ∈ X let G_{x} = {(d(1), d(2), …) ∈ X^{ω}|(x, d(1), d(2), …) ∈ G}; G_{x} is basically an intersection of G with a basic clopen set, and we assume that the pointclass ∼ K is closed under this operation. Then the game X^{ω} \ G_{x} ∈ K is determined by assumption. Case 1: There is x_{0} ∈ X such that II has a winning strategy τ in X^{ω} \ G_{x}. Then a winning strategy σ for I in the original game G can be defined by: σ(∅) = x_{0}, σ(x_{0}, x_{1}, …, x_{2n+1}) = τ(x_{1}, …, x_{2n+1}).

If I plays according to σ with resulting sequence (x_{0}, x_{1}, x_{2}, …) then the sequence (x_{1}, x_{2}, …) is a play in X^{ω} \ G_{x_{0}} in which II plays according to τ. Since τ is a winning strategy, (x_{1}, x_{2}, …) ∈ G_{x_{0}}, and (x_{0}, x_{1}, x_{2}, …) ∈ G. Hence σ is a winning strategy for I. Case 2: For all x_{0} ∈ X there is a winning strategy σ_{x_{0}} for I in X^{ω} \ G_{x}. Then a winning strategy τ for II in the original game G can be defined by: τ(x_{0}, x_{1}, …, x_{2n}) = σ_{x_{0}}(x_{1}, …, x_{2n}). If II plays according to τ with resulting sequence (x_{0}, x_{1}, x_{2}, …) then the sequence (x_{1}, x_{2}, …) is a play in X^{ω} \ G_{x_{0}} in which I plays according to σ_{x_{0}}. Since σ_{x_{0}} is a winning strategy, (x_{1}, x_{2}, …) ∉ G_{x_{0}}, and (x_{0}, x_{1}, x_{2}, …) ∉ G. Hence σ is a winning strategy for I. qed

Remarks: 1. Case 2 of the proof uses a mild form of AC to choose the winning strategies σ_{x_{0}} for countably many different x_{0} ∈ X. Such principles follow from the full axiom of determinacy AD, see next theorem.

2. One can view the above proof as deciding the game at the second move by asking the players to play complete winning strategies. This idea will be very prominent in the later proof of Borel determinacy.

Theorem 5.2 (ZF) AD implies that every countable sequence (A_{n}) of nonempty sets of reals has a choice function.

Proof: Consider the game G where first I plays some natural number x_{0} and afterwards II plays a real numberthat every countable sequence (A_{n}) of non-empty sets of reals has a choice function. (x_{1}, x_{2}, …). II wins the game (x_{0}, x_{1}, x_{2}, …), iff (x_{1}, x_{2}, …) ∈ A_{x_{0}}. By AD, the game G is determined.

(1) There is no winning strategy for I in the game. Proof: Consider a strategy σ for I. σ chooses a fixed initial move x_{0} for I. The set A_{x_{0}} is non-empty, and II can play some (x_{1}, x_{2}, …) ∈ A_{x_{0}}. Then I has lost the game, and σ is not a winning strategy. qed(1) By AD, II has a winning strategy τ. By the definition of G, τ is basically a choice function for the given sequence of sets. qed

Remarks: 1. We cannot hope for “longer” choice functions, since this would lead to non-regular sets of reals.

2. The choice principle proved here is not quite strong enough for the usual requirements of infinitesimal calculus. However:

6 OPEN/CLOSED DETERMINACY: THE GALE-STEWART THEOREM17

Theorem 5.3 (ZF) Assume that every countable sequence of nonempty sets of reals has a choice function. Then the smallest uncountable cardinal ℵ_{1} is regular.

Proof: Assume that ℵ_{1} has cofinality ω. Let (α_{n}) be a cofinal sequence of ordinals in ℵ_{1}. For n < ω let A_{n} be the set of reals which code a well-ordering of ordertype α_{n}. By the previous theorem, we can pick a real a_{n} ∈ A_{n} for each n < ω. The sequence (a_{n}) can be used to construct a surjection from ω onto ℵ_{1}. Contradiction. qed Remark: The conclusion of the theorem can not be proved in ZF, indeed one can construct models of ZF in which ℵ_{1} has cofinality ω (reference). The theorem is a weak indication that AD implies the largeness of certain ordinals, in this case of ℵ_{1}.

5.2 Some Complexities Associated to Determinacy

We determine some complexities of sets which occur naturally in the theory of determinacy. The set P of plays in the game G_{2}^{∗}(A) is arithmetical: P = {X ⊆ H_{ω}|H_{ω} ⊧ X is a function defined on the natural numbers, whose values at even numbers are elements of 2^{<ω} and whose values at odd numbers are elements of {0, 1}}. The set S of strategies can be presented arithmetically as S = {σ ⊆ H_{ω}|σ is a function}. If σ is a strategy then the set of plays P^{σ} in which player I uses the strategy σ is arithmetical: P^{σ} = {X|X ∈ P and ∀n X(2n) = σ(X ↾ 2n)}. The set of 0-1-sequences B generated by a strategy for player I in the game G_{2}^{∗}(A) is analytical: B = {Z ∈ 2^{ω}|∃X ∈ P Z is the concatenation of all elements of X}.

6 Open/Closed Determinacy: The Gale-Stewart Theorem

Theorem 6.1 (Gale and Stewart, ZFC) Let X be an arbitrary set. If the game G ⊆ X^{ω} is closed or open in the usual topology then G is determined.

Proof: By a previous theorem, we only need to consider the open case. If s ∈ ω^{<ω}, let G_{s} = {z ∈ ω^{ω}|sˆ z ∈ G}. We call a finite sequence s ∈ ω^{<ω} a winning position for I, if s is of even length, and if I wins the game G_{s}. Assume that ∅ is not a winning position for I. We prove the theorem by defining a winning strategy τ for II: Consider a finite sequence (s_{0}, s_{1}, …, s_{2n−1}, s_{2n}) of moves. If (s_{0}, s_{1}, …, s_{2n−1}) is a winning position for I we let τ(s_{0}, s_{1}, …, s_{2n−1}, s_{2n}) be some arbitrary move. If (s_{0}, s_{1}, …, s_{2n−1}) is not a winning position for I there must be some s_{2n+1} ∈ X such that (s_{0}, s_{1}, …, s_{2n−1}, s_{2n}, s_{2n+1}) is not a winning position for I. Let τ(s_{0}, s_{1}, …, s_{2n−1}, s_{2n}) be some such _{2n+1} (Choice!). Consider a play p = (s_{0}, s_{1}, s_{2}, …) in which II plays according to τ. We can prove inductively that for all n < ω, p ↾ 2n is not a winning position for I. Assume, however, that p ∈ G. Since G is open, there must be some n_{0} < ω such that every play q with q ↾ 2n_{0} = p ↾ 2n_{0} satisfies q ∈ G. But then p ↾ 2n_{0} trivially is a winning position for I, contradiction. Therefore p ∉ G, and II has won the game. qed

Remarks: 1. If we do not want to invoke the previous theorem on dual determinacy, we can also carry out a dual proof here for the closed case.

2. The definition of the winning strategy for II requires some choice. We have to verify in the situations that enough choice holds.

3. Exercise: Over ZF, the fact that every open or closed game is determined is equivalent to the Axiom of Choice (Hint: see the above proof of a choice principle from AD).

We consider an example of a closed game which will be used in the proof of analytic determinacy from a measurable cardinal: Assume that D : ω^{<ω} → V is a function satisfying:

• D(s) is a linear ordering of some set of |s| integers;

• if s ⊆ t then D(s) is a subordering of D(t).

With D we can associate the game or set G = {x ∈ ℝ| ⋃_{n<ω} D(x ↾ n) is a well-order} ⊆ ℝ. We shall see that every Π_{1}^{1}-set can be represented in this form. We now define an associated game G̃ on a larger domain which is closed. Fix a sufficiently large ordinal θ for the following. I and II alternately play a sequence x = (x_{0}, x_{1}, x_{2}, …) ∈ ω^{ω} as usual. Moreover, player I is required to play a sequence (e_{0}, e_{2}, e_{4}, …) of maps e_{2n} : field(D(x_{0}, …, x_{2n−1}) → κ. So a play in G̃ looks like

((x_{0}, e_{0}), x_{1}, (x_{2}, e_{2}), x_{3}, …).

I wins this play iff

• each e_{2n} maps D(x_{0}, …, x_{2n−1}) order-preservingly in the well-order of the ordinals;

• e_{2n+2} extends e_{2n}.

These “rules” make G̃ a closed game on the appropriate domain. It is therefore determined. Assume that I has a winning strategy σ̃ in G̃. We can derive a strategy σ for I in G from this by “hiding” the auxiliary moves e_{0}, e_{2}, …: define by recursion:

σ(∅) = x_{0}, where σ̃(∅) = (x_{0}, e_{0}); σ(x_{0}, x_{1}) = x_{2}, where σ̃(∅) = (y_{0}, e_{0}) and σ̃((x_{0}, e_{0}), x_{1}) = (x_{2}, e_{2}); etc.

If x = (x_{0}, x_{1}, x_{2}, …) is a play on ω in which I plays according to σ then we can extend this to a play x̃ = ((x_{0}, e_{0}), x_{1}, (x_{2}, e_{2}), …) in the augmented game in which I plays according to σ̃. Since σ̃ is a winning strategy, the e_{2n} form an increasing chain of orderpreserving embeddings into the ordinals. Hence: ⋃_{n<ω} e_{2n} : ⋃_{n<ω} field(D(x ↾ 2n) → κ is a well-defined, order-preserving map. Therefore ⋃_{n<ω} D(x ↾ 2n) is a well-ordering, and by definition of G, x ∈ G. So σ is a winning strategy for I in G. Dealing with the case when II has a winning strategy τ̃ in G̃ is much more involved and in general necessarily transcends the possibilities of the system ZFC. To obtain a winning strategy τ for II in G from the strategy τ̃ we have to provide τ̃ with appropriate “virtual moves” e_{0}, e_{2}, . . .. In this way we shall be able to simulate a play in G̃ which is consistent with the play in G. The technicalities of such a simulation can be solved by the use of measurable cardinals, and we shall choose κ to be such a cardinal.

6.1 Borel-Determinacy

Borel-determinacy can be proved in ZFC, but the proof (by T. Martin) is involved and we shall defer it towards the end of this course. The argument uses auxiliary clopen games as in the previous example which will be obtained by requiring the players to play whole strategies in one move. It was shown by H. Friedman, that to prove Borel determinacy, it is necessary to apply a transfinite iteration of the powerset axiom which is quite unusual in ordinary mathematical proofs. Thus Borel determinacy uses a large part of the resources of ZFC and it points towards stronger principles which are unprovable in ZFC:

7 Analytic Sets

One can show that analytic determinacy can not be proved in ZFC (unless the system ZFC is inconsistent). We shall later, however, complete the above preview with the help of a measurable cardinal. The proof of analytic determinacy from a measurable cardinal is due to T. Martin. By generalizations which are far beyond the present course the proof of analytic determinacy can be lifted to a proof of projective determinacy (T. Martin und J. Steel).

7.1 A First Normal Form

We show that the second-order definition of an analytic set can be normalized to a very specific form which is useful for further applications.

Theorem 7.1 If A ⊆ 𝔓(H_{ω}) is analytic then there is a quantifier-free formula χ and some P_{1}, …, P_{n} ⊆ H_{ω} such that

A = {P_{0}|(H_{ω}, ∈) ⊧ ∃U∀v⃗∃w⃗ χ[P_{0}, P_{1}, …, P_{n}]}.

Proof: Let us start by constructing a similar normalization for first-order formulas. So let ψ(U_{1}, …, U_{m−1}, u_{0}, …, u_{n−1}) be a first-order formula, where all (including bound) variables of ψ are mentioned. Given parameters P_{1}, …, P_{m−1} ⊆ H_{ω} we can give a recursive Tarskian truth definition for ψ as follows: Let ψ_{0} = ψ, ψ_{1}, …, ψ_{s} list all subformulas of ψ. Define truth sets T_{0}, …, T_{s} ⊆ H_{ω}, T_{i} = {(x_{0}, …, x_{n−1}) ∈ H_{ω}|(H_{ω}, ∈) ⊧ ψ[P_{1}, …, P_{m−1}, x_{0}, …, x_{n−1}]}. That the second order variables V_{0}, …, V_{s} are these truth sets can be characterized by a list of ∀v⃗∃w⃗-formulas θ_{0}, …, θ_{s}. The atomic cases are trivial: If ψ_{r} ≡ u_{i} = u_{j} then let θ_{r} ≡ ∀u⃗(V_{r}(u⃗) ⟺ u_{i} = u_{j}). If ψ_{r} ≡ u_{i} ∈ u_{j} then let θ_{r} ≡ ∀u⃗(V_{r}(u⃗) ⟺ u_{i} ∈ u_{j}).

If ψ_{r} ≡ U_{i}(u⃗′) then let θ_{r} ≡ ∀u⃗(V_{r}(u⃗) ⟺ U_{i}(u⃗′)). If ψ_{r} ≡ ψ_{r_{1}} ∧ ψ_{r_{2}} then let θ_{r} ≡ ∀u⃗(V_{r}(u⃗) ⟺ V_{r_{1}}(u⃗) ∧ V_{r_{2}}(u⃗)). Similarly for the other propositional connectives. If ψ_{r} ≡ ∃u_{i}ψ_{r_{0}} then let θ_{r} ≡ ∀u⃗(V_{r}(u⃗) ⟺ ∃w V_{r_{0}}(u⃗\frac{w}{u_{i}})). Now the following logical equivalence holds: ψ(U⃗, u⃗) ⟺ ∃V_{0}, …, V_{s} (θ_{0} ∧ … ∧ θ_{s} ∧ V_{0}(u⃗)). The formulas θ_{i} are of ∀∃-complexity at the most, and we can pull all these first-order quantifiers to the front: if θ′_{i} are the quantifier-free remainders of the formulas θ_{i}: ψ(U⃗, u⃗) ⟺ ∃V_{0}, …, V_{s} ∀v⃗∃w⃗ (θ′_{0} ∧ … ∧ θ′_{s} ∧ V_{0}(u⃗)). We can now contract the sequence ∃V_{0}, …, V_{s} into one quantifier ∃V which is intended to have the various V_{i} as sections: V_{i}(u⃗) ⟺ V (u⃗, i). This equivalence allows to substitute each V_{i} by V in the formulas θ′_{j}; let θ′′_{i} be the result of that substitution. We then obtain the desired normal form: ψ(U⃗, u⃗) ⟺ ∃V (θ′′_{0} ∧ … ∧ θ′′_{s} ∧ V_{0}(u⃗)). The desired normal form for analytic sets A is then obtained by: ∃U_{0} ψ(U⃗, u⃗) ⟺ ∃U_{0}∃V (θ′′_{0} ∧ … ∧ θ′′_{s} ∧ V_{0}(u⃗)), and again the quantifiers ∃U_{0}∃V can be contracted into one. q.e.d.

7.2 Tree Representations for Analytic Sets

We should work with characteristic functions instead of subsets. Then we do not need to carry the V_{n} along!

The normal forms of the previous theorems are the basis for other normal forms for analytic sets.

Theorem 7.2 If A ⊆ 𝔓(H_{ω}) is analytic then there is a relation R on H_{ω} such that P ∈ A iff there exists a sequence (a_{0}, b_{0})R(a_{1}, b_{1})R(a_{2}, b_{2}), … such that P = ⋃_{n<ω} a_{n}.

Proof: According to the previous theorem, consider an analytic set

Collision between secondorder variable V_{n} and von Neumann levels!

A = {P |(H_{ω}, ∈) ⊧ ∃U∀v⃗∃w⃗ χ[P, P_{1}, …, P_{n}]}

with P_{1}, …, P_{n} ⊆ H_{ω}. Let the relation R be defined on the set {(p, (V_{m}, u))|m < ω ∧ p ⊆ V_{m} ∧ u ⊆ V_{m}} by (p, (V_{m}, u))R(q, (V_{n}, v)) iff m < n, p = q ∩ V_{m}, u = v ∩ V_{m}, and

∀v⃗ ∈ V_{m}∃w⃗ ∈ V_{n} (V_{n}, ∈) ⊧ χ[q, P_{1} ∩ V_{n}, …, P_{n} ∩ V_{n}, v].

So the field of R consists of potential assignments for the second-order variables in the definition of A, and (p, (V_{m}, u)), (q, (V_{n}, v)) are R-related if V_{n} contains witnesses for the ∀v⃗∃w⃗ quantifiers for points v⃗ from V_{m}. Consider P ∈ A. There is U ⊆ H_{ω} such that

(H_{ω}, ∈) ⊧ ∀v⃗∃w⃗ χ[P, P_{1}, …, P_{n}, U].

There is a sequence n_{0} < n_{1} < n_{2} … < ω such that for every i < ω:

(H_{ω}, ∈) ⊧ ∀v⃗ ∈ V_{n_{i}}∃w⃗ ∈ V_{n_{i+1}} χ[P, P_{1}, …, P_{n}, U],

and

∀v⃗ ∈ V_{n_{i}}∃w⃗ ∈ V_{n_{i+1}} (V_{n_{i+1}} ⊧ χ[P ∩V_{n_{i+1}}, P_{1} ∩V_{n_{i+1}}, …, P_{n} ∩V_{n_{i+1}}, U ∩V_{n_{i+1}}].

Then (a_{i}, b_{i}) = (P ∩V_{n_{i}}, (V_{n_{i}}, U ∩V_{n_{i}})) defines a strictly increasing R-sequence whose union of first coordinates is P.

Conversely, let (a_{0}, b_{0})R(a_{1}, b_{1})R(a_{2}, b_{2}), … and P = ⋃_{n<ω} a_{n} ⊆ H_{ω}. For i < ω let (a_{i}, b_{i}) be of the form (P ∩V_{n_{i}}, (V_{n_{i}}, u_{i})), and let U = ⋃_{i<ω} u_{i} ⊆ H_{ω}. By definition of R,

∀v⃗ ∈ V_{n_{i}}∃w⃗ ∈ V_{n_{i+1}} (V_{n_{i+1}} ⊧ χ[P ∩V_{n_{i+1}}, P_{1} ∩V_{n_{i+1}}, …, P_{n} ∩V_{n_{i+1}}, U ∩V_{n_{i+1}}].

Since the formula χ is quantifier-free,

(H_{ω}, ∈) ⊧ ∀v⃗ ∈ V_{n_{i}}∃w⃗ ∈ V_{n_{i+1}} χ[P, P_{1}, …, P_{n}, U],

and so

(H_{ω}, ∈) ⊧ ∀v⃗∃w⃗ χ[P, P_{1}, …, P_{n}, U].

Therefore P ∈ A. qed

The relation R can be turned into a tree (T , ⊆) of finite sequences such that an ascending sequence (a_{0}, b_{0})R(a_{1}, b_{1})R(a_{2}, b_{2}), … corresponds to an infinite branch in that tree: Let

T = {f ∈ H_{ω}^{<ω}|f ≠ ∅ → (f(0) = (∅, (∅, ∅))∧∀i+1 ∈ dom(f) f(i)Rf(i+1))}.

For any P ⊆ H_{ω} we associate the subtree T_{P} of nodes compatible with P: T_{P} = {f ∈ T |∀i ∈ dom(f) ∀p, v, u (f(i) = (p, (v, u)) → p = P ∩ v)} Then the above theorem becomes:

Theorem 7.3 If A ⊆ 𝔓(H_{ω}) is analytic then there is a tree (T , ⊆) of finite sequences as above such that P ∈ A iff T_{P} possesses an infinite branch. The latter is equivalent to: (T_{P} , ⊇) is not well-founded.

Note that the set [T ] of infinite branches of T is a closed subset of H_{ω}^{<ω}. The analytic set A is the image of [T ] under the map

((a_{0}, b_{0}), (a_{1}, b_{1}), (a_{2}, b_{2}), …) ↦ a_{0} ∪ a_{1} ∪ a_{2} ∪ ….

The map is continuous, and we have reproved the standard theorem:

Theorem 7.4 A set A ⊆ 𝔓(H_{ω}) is analytic iff it is the continuous image of a closed set.

Our next aim is a representation of analytic sets in terms of well-orders. This will be obtained by “linearizing” the trees above.

Definition 7.1 (a) Define a well-ordering <_{ω} of H_{ω} by recursion: x <_{ω} y ↔ ∃z ∈ y \ x ∀w (w <_{ω} z → (w ∈ x ↔ w ∈ y)).

(b) Define the Kleene-Brouwer order <_{KB} on H_{ω}^{ω} by: s <_{KB} t ↔ (s ⊇ t ∧ s ≠ t) ∨ (∃i ∈ dom(s) ∩ dom(t) (s ↾ i = t ↾ i ∧ s(i) <_{ω} t(i)).

The Kleene-Brouwer order is a linear order. Its crucial property is expressed by the following theorem:

Theorem 7.5 Let (T , ⊇) be a subtree of (H_{ω}^{<ω}, ⊇). Then (T , ⊇) is wellfounded iff <_{KB} wellorders T .

Proof: An infinite branch through T trivially yields an infinite descending chain in <_{KB}. For the converse, consider an infinite chain s_{0} >_{KB} s_{1} >_{KB} s_{2} . . .. Define an infinite path t_{0}, t_{1}, …, t_{n} = (a_{0}, …, a_{n−1}) in T as well as some auxiliary numbers N(n) ∈ ω by recursion. Set t_{0} = ∅ and N(0) = 0. Let t_{n} = (a_{0}, …, a_{n−1}) ∈ T and N(n) be defined such that ∀i > N(n) t_{n} = (a_{0}, …, a_{n−1}) ⊊ s_{i}. All such s_{i} have length > n, so D_{n} = {s_{i}(n)|i > N(n)} is non-empty. Let a_{n} be <_{ω}-minimal in D_{n}. Then t_{n+1} = (a_{0}, …, a_{n−1}, a_{n}) ∈ T . Choose some N(n + 1) > N(n) such that s_{N(n+1)}(n) = a_{n}. We have to check the side-condition of the recursion: If i > N(n + 1) then s_{i} <_{KB} s_{N(n+1)} ⊇ (a_{0}, …, a_{n−1}, a_{n}). By the successive minimal choices for a_{0}, …, a_{n} we must have that s_{i}(0) = a_{0}, …, s_{i}(n) = a_{n}, and so t_{n+1} ⊊ s_{i}. So the recursion works and provides us with the infinite branch t_{0} ⊊ t_{1} ⊊ t_{2} ⊊ … through T . qed Theorem 7.6 Let A ⊆ 𝔓(H_{ω}) be analytic. Then there is a map L : H_{ω} → H_{ω} such that:

• for all x ∈ H_{ω} the value L(x) is a finite linear order;

• L is an increasing function: x ⊆ y → L(x) ⊆ L(y);

• ∀P ⊆ H_{ω} P ∈ A ⟺ ⋃_{n<ω} L(χ_{P} ↾ V_{n}) is ill-founded

Proof: Let T be the tree associated to A as in the theorem before. For a characteristic function g : V_{n} → {0, 1} define T_{g} as above: T_{g} = {f ∈ T |∀i ∈ dom(f)∀p, u (f(i) = (p, u) → p ⊆ g)}. Since g is finite, the tree T_{p} is finite. Then define L(g) =<_{KB}↾ T_{g}. If g ∈ H_{ω} is not of this form set L(g) = ∅. Then L has the required properties. qed We can refine the system L with a view towards the game for a Π_{1}^{1}-set which was considered after the Gale-Stewart theorem.

Theorem 7.7 Let A ⊆ 𝔓(H_{ω}) be analytic. Then there is a map D : H_{ω} → H_{ω} such that:

• for all x : V_{n} → {0, 1} the value D(x) is a linear order, whose domain consists of n natural numbers;

• D is an increasing function: x ⊆ y → D(x) ⊆ D(y);

• ∀P ⊆ H_{ω} P ∈ A ⟺ ⋃_{n<ω} D(χ_{P} ↾ V_{n}) is ill-founded

Proof: Let L be the function given by the previous theorem for A. Let EVEN be the set of even natural numbers, and let ν : (H_{ω}^{<ω}, <_{KB}) ≅ (EVEN, ≺) be an isomorphism. Extend the ordering (EVEN, ≺) to (ω, ≺) by putting all odd numbers in their natural (well-)order after the even numbers. For x : V_{n} → {0, 1} define the value D(x) by recursion on n: for n = 0 set D(x) = D(∅) = ∅. Consider x : V_{n+1} → {0, 1} and assume that D(x ↾ V_{n}) is defined to be suborder of ≺ whose domain contains n elements so that dom(D(x ↾ V_{n})) ∩ EVEN ⊆ ν[dom(L(x ↾ V_{n}))]. We distinguish two cases: If ν[dom(L(x))] ≠ dom(D(x ↾ V_{n})) ∩ EVEN then let D(x) be the ordering ≺ restricted to the set dom(D(x ↾ V_{n})) ∪ {k} where k is the smallest element of ν[dom(L(x))] \ dom(D(x ↾ V_{n})). Otherwise, letD(x) be the ordering ≺ restricted to the set dom(D(x ↾ V_{n})) ∪ {k} where k is the smallest odd number not in dom(D(x ↾ V_{n})).

Let us check the illfoundedness criterion: Let P ⊆ H_{ω}. By the construction of D, ν induces an isomorphism between ⋃_{n<ω} L(χ_{P} ↾ V_{n}) and ⋃_{n<ω} D(χ_{P} ↾ V_{n}), restricted to the even natural numbers. Since the “odd” part of ≺ is wellfounded, we have that ⋃_{n<ω} D(χ_{P} ↾ V_{n}) is ill-founded iff ⋃_{n<ω} L(χ_{P} ↾ V_{n}) is ill-founded iff P ∈ A. qed

Theorem 7.8 Let A ⊆ ω^{ω} be analytic. Then there is a map D : ω^{<ω} → H_{ω} such that:

• for all x : n → ω the value D(x) is a linear order, whose domain consists of n natural numbers;

• D is an increasing function: x ⊆ y → D(x) ⊆ D(y);

• ∀P ∈ ω^{ω} P ∈ A ⟺ ⋃_{n<ω} D(P ↾ n) is ill-founded.

7.3 The Boundedness Theorem

The following theorem plays an important role in arguments about the influence of determinacy assumptions on the ordinals.

Definition 7.2 (a) WF = {P ⊆ H_{ω}|P is a well-founded relation}.

(b) (a) WO = {P ⊆ H_{ω}|P is a well-ordering}.

Note, that we can define these notions without any coding machinery since we are working over the rich domain H_{ω}. Both WF and WO are easily seen to be Π_{1}^{1}. The boundedness theorem shows that they cannot be Σ_{1}^{1}.

Theorem 7.9 Let A ⊆ WO be an analytic set. Then there is an ordinal θ < ω_{1} such that otp(P) < θ for every P ∈ A.

In this proof, and some other places, we mix sets and characteristic function, unfortunately.

Proof: By Theorem 6.3(???) there is a quantifier-free formula χ and parameters P_{1}, …, P_{l} ⊆ H_{ω} such that

A = {P_{0}|(H_{ω}, ∈) ⊧ ∃U∀v⃗∃w⃗ χ[P_{0}, P_{1}, …, P_{l}]}.

We define a partial order which attempts to capture descending sequences in the well-orders contained in A: let D = {(p, u, a)|∃n, k < ω (p : V_{n} → {0, 1} ∧ u : V_{n} → {0, 1} ∧ a : k → V_{n} ∧∀i+1 < k p((a(i+1), a(i))) = 1)}. The elements of D can be understood as approximations to some P ∈ A, some witness U for this fact, and a descending chain in P. In view of Theorem 6.3 we define a strict relation < on D by: (q, v, b) < (p, u, a) iff q ⊋ p ∧ v ⊋ u ∧ b ⊋ a ∧ ∀v⃗ ∈ dom(p)∃w⃗ ∈ dom(q)(V_{n}, ∈) ⊧ χ[q, P_{1} ∩ V_{n}, …, P_{l} ∩ V_{n}, v], where V_{n} = dom(q).

(1) (D, <) is well-founded. Proof: Assume that (p_{0}, u_{o}, a_{0}) > (p_{1}, u_{1}, a_{1}) > … is a descending chain in D. Let P = ⋃_{i<ω} p_{i}, U = ⋃_{i<ω} u_{i}, and a = (a(0), a(1), …) = ⋃_{i<ω} a_{i}. By the particular definition of the <-relation, U witnesses that P ∈ A, and ∀i < ω (a(i + 1), a(i)) ∈ P. But then P ∉ WO, contradiction. qed(1) Let θ be the rank of (D, <). Since D is a countable set, θ < ω_{1}. We show that θ satisfies the theorem. Assume for a contradiction, that there is some P ∈ A such that otp(P) ≥ θ. Let U ⊆ H_{ω} witness this fact:

(H_{ω}, ∈) ⊧ ∀v⃗∃w⃗ χ[P, P_{1}, …, P_{l}, U].

We define an infinite descending sequence (p_{0}, u_{o}, a_{0}) = (∅, ∅, ∅) > (p_{1}, u_{1}, a_{1}) > (p_{2}, u_{2}, a_{2}) > … in D, a_{i} = (a(0), …, a(i − 1)), p_{i} ⊆ P, u_{i} ⊆ U by recursion. Let (p_{i}, u_{i}, a_{i}) = (P ↾ V_{m}, U ↾ V_{m}, (a(0), …, a(i − 1))) already be defined, such that for j < i the height of a(j) in the well-order P is equal to the rank of (p_{j}, u_{j}, a_{j}) in the well-founded relation (D, <). Let δ be the rank of (p_{i}, u_{i}, a_{i}) = (P ↾ V_{m}, U ↾ V_{m}, (a(0), …, a(i − 1))) in (D, <). Let a(i) be the δ^{th} element of P. Since (p_{i}, u_{i}, a_{i}) < (p_{i−1}, u_{i−1}, a_{i−1}) we have a(i) P a(i − 1). Choose n, m < n < ω such that a(i) ∈ V_{n} and

(H_{ω}, ∈) ⊧ ∀v⃗ ∈ V_{m}∃w⃗ ∈ V_{n} χ[P, P_{1}, …, P_{l}, U].

This implies that (p_{i+1}, u_{i+1}, a_{i+1}) = (P ↾ V_{n}, U ↾ V_{n}, (a(0), …, a(i))) < (p_{i}, u_{i}, a_{i}), and we can continue the recursion. But this contradicts (1). qed

7.4 Solovay Unfolding

To make the most out of a given determinacy hypothesis, one has to design appropriate games and calculate their complexities carefully.

Theorem 7.10 If Det(Σ_{n}^{1}) holds then every Σ_{n+1}^{1}-set has the perfect subset property.

Proof: Let A = {X ⊆ H_{ω}|∃Y H_{ω} ⊧ ϕ(X, Y, P⃗ , p⃗)} be a Σ_{n+1}^{1}-set with ϕ being Π_{n}^{1}. Consider the following game G:

\begin{matrix}I & (s_{0}, y_{0}) & & (s_{2}, y_{2}) & & … \\ II & & k_{1} & & k_{3} & & … \end{matrix}

The rules of this game are: s_{2n} ∈ 2^{<ω}, y_{2n} ∈ H_{ω}, k_{2n+1} ∈ 2^{1}. Player I wins the above play iff H_{ω} ⊧ ϕ(s_{0}ˆ k_{1}ˆ s_{2}ˆ k_{3}ˆ …, {y_{0}, y_{2}, …}, P⃗ , p⃗). So the task of player I is to make the infinite concatenation s_{0}ˆ k_{1}ˆ s_{2}ˆ k_{3}ˆ … ∈ A and to produce a witness {y_{0}, y_{2}, …} for this fact. Making player I to produce the existence for the second-order existential quantifier reduces the projective complexity of the game:

(1) G is Π_{n}^{1}. Proof: The rules of the game are obviously arithmetical, so the condition that I wins the game because II first violates a rule is arithmetical. In case all the rules are kept, ((s_{0}, y_{0}), k_{1}, (s_{2}, y_{2}), k_{3}, …) is a win for I iff ∀X, Y (X = s_{0}ˆ k_{1}ˆ s_{2}ˆ k_{3}ˆ … and Y = {y_{0}, y_{2}, …} ⇒ H_{ω} ⊧ ϕ(X, Y, P⃗ , p⃗). By the closure properties of Π_{n}^{1}, this condition is Π_{n}^{1}. qed(1) By our assumption, G is determined. Case1: σ^{∗} is a winning strategy for I in G. Then we obtain a winning strategy for I in the original ∗-game G_{2}^{∗}(A) by simply hiding the auxiliary moves y_{0}, y_{2}, … of I. By the results on the ∗-game, A contains a non-empty perfect subset. Case2: τ^{∗} is a winning strategy for II in G. We imitate the argument for the ∗-game in the new situation. Let X ∈ A. Choose Y ⊆ H_{ω} such that H_{ω} ⊧ ϕ(X, Y, P⃗ , p⃗). We may assume without loss of generality that Y ≠ ∅ and that Y = {y_{0}, y_{2}, …} is an enumeration of Y, possibly with repetitions. Since X ∈ A, X cannot be the “result” of a play in which the rules are kept, in which I plays y_{0}, y_{2}, … as auxiliary moves, and in which II follows his winning strategy τ^{∗}. Thus there must be a some initial play Z_{0} = ((s_{0}, y_{0}), k_{1}, (s_{2}, y_{2}), k_{3}, …, (s_{2n}, y_{2n}), k_{2n+1}) in which the rules are kept, in which I plays y_{0}, y_{2}, … as auxiliary moves, and in which II follows his winning strategy τ^{∗} but which cannot be extended further with these properties. But then the whole of X is determined by the initial play Z_{0}: For i > i_{0} = length(s_{0}ˆ k_{1}ˆ s_{2}ˆ k_{3}ˆ …ˆ s_{2n}ˆ k_{2n+1}), the binary digit X(i) must be incompatible with the strategy τ^{∗}, and so

X(i) = 1 − τ^{∗}((s_{0}, y_{0}), k_{1}, (s_{2}, y_{2}), k_{3}, …, (s_{2n}, y_{2n}), k_{2n+1}, X ↾ (i − i_{0})).

Since there are at most countably many such initial plays, the set A is at most countable and A satisfies the perfect subset property. qed Remark: The Covering Game considered in the context of Lebesgue-measurability can be “unfolded” in a similar way, so that Π_{n}^{1}-determinacy implies that all Σ_{n+1}^{1}-sets (and hence all Π_{n+1}^{1}-sets) are Lebesgue-measurable. Similarly the ∗∗-game adequate for Baire-measurability can be unfolded. Exercises: 1. Show the following normal form result for an analytic set A ⊆ ω^{ω}: There is a system (ρ_{st}|s ⊆ t ∈ ω^{<ω}) of maps such that:

• ρ_{st} : (|s|, <) → (|t|, <) is an order-preserving map, for s ⊆ t ∈ ω^{<ω};

• if s ⊆ t ⊆ u then ρ_{su} = ρ_{tu} ∘ ρ_{st};

• if P ∈ ω^{ω} then P ∈ A iff the direct limit of the subsystem (ρ_{st}|s ⊆ t ⊆ P) is not wellfounded.

8 Closed Unbounded Filters

In this chapter we introduce some infinitary combinatorics relevant to the large cardinal aspect of determinacy. We shall later show that under the assumption of AD the closed unbounded filter on ω_{1} is an ultrafilter, hence ω_{1} is a measurable cardinal.

Definition 8.1 Let κ be an infinite limit ordinal.

(a) The cofinality of κ is defined as cof(κ) = min{λ|∃f(f : λ → κ ∧ ¬∃κ̄ < κ f : λ → κ̄)}.

(b) κ is regular if cof(κ) = κ. κ is singular if cof(κ) < κ.

Under the axiom of choice (AC), ω_{1} is a regular cardinal. This is also true under the axiom of determinacy (see above). The regularity of a cardinal is a largeness criterion; the cardinal is not easily accessible from below. This implies particular combinatorial properties for regular cardinals.

Definition 8.2 Let κ be a regular uncountable cardinal.

(a) A set C ⊆ κ is closed in κ if ∀γ < κ(∀α < γ∃β < γ(β ∈ C ∧ α < β) → γ ∈ C).

(b) A set C ⊆ κ is unbounded in κ if ∀α < κ∃β(β ∈ C ∧ α < β).

(c) A set C ⊆ κ is closed unbounded in κ if it satisfies (a) and (b).

(d) Let CUB_{κ} denote the set of all X ⊆ κ which possess a subset which is closed unbounded in κ.

(d) A set S ⊆ κ is stationary in κ if ∀C ∈ CUB_{κ} S ∩ C ≠ ∅).

We have the following theorem:

Theorem 8.1 (ZFC) Let κ be a regular uncountable cardinal.

(a) CUB_{κ} is a non-trivial filter on κ.

(b) CUB_{κ} is < κ-closed, i.e., if δ < κ and (X_{ξ})_{ξ<δ} is a family of elements of CUB_{κ} then ⋂_{ξ<δ} X_{ξ} ∈ CUB_{κ}.

(c) CUB_{κ} is normal, i.e., if (X_{ξ})_{ξ<κ} is a family of elements of CUB_{κ} then the diagonal intersection △_{ξ<κ}X_{ξ} = {ζ < κ|∀ξ < ζ ζ ∈ X_{ξ}} ∈ CUB_{κ}.

Proof: Exercise. Take notice of those places where the axiom of choice is used. qed

Theorem 8.2 (ZF) Let λ < κ be infinite regular cardinals. Then the set {ξ < κ|cof(ξ) = λ} is stationary in κ.

Proof: Exercise. qed This indicates some restriction for CUB_{κ} to be an ultrafilter on κ: If κ > ω_{1} and ω_{1} is regular, then there are (at least) two infinite regular cardinals below κ, and the sets {ξ < κ|cof(ξ) = ω} and {ξ < κ|cof(ξ) = ω_{1}} are stationary in κ. If CUB_{κ} were an ultrafilter on κ then both these sets would have to lie in the ultrafilter, since they intersect every set in the ultrafilter non-empty. But this is absurd since the two sets are disjoint. So for the ultrafilter property we shall concentrate on the case κ = ω_{1}.

Theorem 8.3 (Fodor’s Theorem, AC) Let κ be an uncountable regular cardinal and let S be stationary in κ. Let f : S → κ be regressive, i.e., ∀α ∈ S f(α) < α. Then there is some ξ < κ and a stationary set T ⊆ S such that f[T] = {ξ}.

Proof: Assume not. So for every ξ < κ, the set f^{−1}[{ξ}] is not stationary in κ and X_{ξ} = κ \ f^{−1}[{ξ}] ∈ CUB_{κ}. This set satisfies: ∀ζ ∈ X_{ξ} f(ζ) ≠ ξ. The diagonal intersection X = △_{ξ<κ}X_{ξ} is closed unbounded. Since S is stationary, X ∩ S ≠ ∅. Let ζ ∈ X ∩ S. ∀ξ < ζ ζ ∈ X_{ξ}, so ∀ξ < ζ f(ζ) ≠ ξ. Therefore f(ζ) ≥ ζ, which contradicts the regressivity of f. qed Under the axiom of choice, the filters CUB_{κ} are actually very far from ultrafilters. We prove a special case of Solovay’s stationary splitting theorem for κ = ℵ_{1}:

Theorem 8.4 (AC) Let S ⊆ ℵ_{1} be stationary in ω_{1}. Then there is a family (S_{ξ})_{ξ<ω_{1}} of pairwise disjoint stationary subsets of S.

Proof: We assume that all ordinals α ∈ S are infinite. By the axiom of choice choose for α ∈ S a surjective function f_{α} : ω → α.

(1) ∃n < ω ∀η < ω_{1} ({α ∈ S|f_{α}(n) > η} is stationary in ω_{1}). Proof: Assume not. So for all n < ω there is η_{n} < ω_{1} and some X_{n} ∈ CUB_{ω_{1}} such that ∀α ∈ S ∩ X_{n} f_{α}(n) ≤ η_{n}. By the regularity of ω_{1} take η < ω_{1} such that ∀n < ω η_{n} < η. Define X = ⋂_{n<ω} X_{n}; X ∈ CUB_{ω_{1}}. Take α ∈ S ∩ X such that α > η. Then ∀n < ω f_{α}(n) ≤ η_{n} < η, i.e., η is not in the image of f_{α}, and f_{α} is not surjective. Contradiction. qed(1) Take n < ω satisfying (1). Define sequences (η_{ξ})_{ξ<ω_{1}}, (ν_{ξ})_{ξ<ω_{1}} and (S_{ξ})_{ξ<ω_{1}} by recursion: Set η_{ξ} = sup_{ζ<ξ}ν_{ζ}. By (1): {α ∈ S|f_{α}(n) > η_{ξ}} is stationary in ω_{1}. By Fodor’s theorem: take ν_{ξ} > η_{ξ} minimal such that S_{ξ} = {α ∈ S|f_{α}(n) = ν_{ξ}} is stationary in ω_{1}. Then (S_{ξ})_{ξ<ω_{1}} is a family of stationary pairwise disjoint subsets of S. qed

9 Measurable Cardinals from AD

Theorem 9.1 (Solovay, ZF) If the axiom of determinacy AD holds then the filter CUB_{ω_{1}} is an ultrafilter on ω_{1}.

Proof: Let Y ⊆ ω_{1}. We have to show that Y or its complement contain a closed unbounded subset of ω_{1}. Consider the following game G_{Y} on H_{ω}:

\begin{aligned}G_{Y}: & I & a_{0} & & a_{1} & & a_{2} & & … \\ & II & & b_{0} & & b_{1} & & b_{2} & & … \end{aligned}

After this play, player I has produced a set A = {a_{i}|i < ω} ⊆ H_{ω}; for n < ω this determines sets A_{n} = {x|(x, n) ∈ A}. Similarly player II has produced a set B = {b_{i}|i < ω} ⊆ H_{ω}; for n < ω this determines sets B_{n} = {x|(x, n) ∈ B}. The winning conditions are as follows: If there is some n < ω such that A_{m} is a wellordering for m ≤ n and B_{m} is a wellordering for m < n and B_{n} is not a wellordering then I wins. If all A_{n} and B_{n} are wellorderings then I wins iff the supremum of the ordertypes of all these wellorderings is an element of Y. In all other cases, II wins. By AD, one of the players possesses a winning strategy in this game. Assume that I has a winning strategy σ. We show that in this case Y contains a closed unbounded subset. A rough motivation for the argument goes as follows. If player II plays (the elements of a set B which code) countable wellorders like above then the winning strategy for player I will also output wellorders, and the supremum of all ordertypes will be in Y. The application of a winning strategy is a kind of bounded operation and it should be possible to bound the answers of σ to a given set of wellorders. Then II has great control over the common supremum and thereby can steer it into the set Y. The required bounding is achieved through the bounding theorem for analytic sets. Let α < ω_{1}. For n < ω consider all sets A_{n} which σ produces in responce to player II playing sets B which code wellorders B_{0}, B_{1}, … of ordertype < α; let O ⊆ H_{ω} be a wellorder of ordertype α. The above mentioned set of A_{n}’s is: W = {W ⊆ H_{ω}|∃(a_{0}, b_{0}, a_{1}, b_{1}, …)(∀m < ω {b|∃i(b, m) = b_{i}} is a wellorder of ordertype < α and (a_{0}, b_{0}, a_{1}, b_{1}, …) is a playing according to σ and W = {w|∃i(w, n) = a_{i}}}. Since σ is a winning strategy for I, all elements of this set are wellorders. The set W is analytic, since the property “{b|∃i(b, m) = b_{i}} is a wellorder of ordertype < α” can be expressed equivalently by saying that there is an order-preserving embedding into the parameter O. By the bounding theorem, there is a bound b(α, n) for the ordertype of wellorders in W. Define a closed unbounded set C = {ν < ω_{1}|ν is a limit ordinal and ∀α < ν∀n < ω b(α, n) < ν}. We claim that C ⊆ Y. Let ν ∈ C. Let ν_{0}, ν_{1}, … be a set of ordinals with supremum ν. Choose B ⊆ H_{ω} such that ∀n < ω otp(B_{n}) = ν_{n}. Let B = {b_{0}, b_{1}, …} and let (a_{0}, b_{0}, a_{1}, b_{1}, …) be a play in which player one uses the strategy σ agains II’s moves b_{0}, b_{1}, . . .. Player I wins, and we let μ_{0}, μ_{1}, … be the ordertypes of wellorders produced by σ. Since ν is in the specific set C, ν = sup(ν_{i}|i < ω) is also equal to the supremum of all of μ_{0}, μ_{1}, …, ν_{0}, ν_{1}, …, which is an element of Y by the winning condition for I. Hence C ⊆ Y. The game considered is basically symmetric, and so if II has a winning strategy, this is analogous to I having a winning strategy for the set ω_{1} \ Y, which then contains a closed unbounded subset. qed Of course this result was obtained in a “choiceless” situation but some of the combinatorial strength of the closed unbounded filter can also be proved in this situation:

Theorem 9.2 (AD) The ultrafilter CUB_{ω_{1}} is countably closed, i.e., it is < ω_{1}-closed.

Proof: Let (X_{n})_{n<ω} be a family of elements of CUB_{ω_{1}}. For every n < ω let S_{n} = {σ|σ is a winning strategy for player I in the game G_{X_{n}}}, where the games G_{X_{n}} were defined in the previous proof. Since X_{n} ∈ CUB_{ω_{1}} the sets S_{n} are nonempty. (S_{n})_{n<ω} is a countable family of nonempty sets of reals, and the axiom of determinacy implies the existence of a choice function: there is a sequence (σ_{n})_{n<ω} of winning strategies for player I. We have seen in the previous proof that every σ_{n} determines a closed unbounded C_{n} ⊆ X_{n}. The set C = ⋂_{n<ω} C_{n} is closed unbounded (this can be shown without the axiom of choice) and so the set X = ⋂_{n<ω} X_{n} ⊇ C is an element of CUB_{ω_{1}}. qed

Definition 9.1 A cardinal κ is a measurable cardinal if it is uncountable and there exists a non-principal < κ-closed ultrafilter U ⊆ 𝔓(κ). Such an ultrafilter is called a measure on κ.

Remark: Note that the axiom of choice implies the existence of non-principal < ω-closed ultrafilters U ⊆ 𝔓(ω), so that ω can be considered to be a countable measurable cardinal. The strength of this notion is due to the countable completeness which we can only have for uncountable κ. So we have proved:

Theorem 9.3 (Solovay) If the axiom of determinacy holds then ω_{1} is a measurable cardinal.

There is an alternative route to the countable completeness of the closed unbounded filter on ω_{1}:

Theorem 9.4 If the axiom of determinacy holds then every ultrafilter on ω is principal.

Proof: Assume that U ⊆ 𝔓(ω) is an ultrafilter on ω. Define a game G on H_{ω}:

\begin{aligned}G: & I & m_{0} & & m_{1} & & m_{2} & & … \\ & II & & n_{0} & & n_{1} & & n_{2} & & … \end{aligned}

in which each player has to observe the rule: m_{0} < n_{0} < m_{1} < n_{1} < … < ω. Player I wins the play (m_{0}, n_{0}, m_{1}, n_{1}, …) iff A = ⋃_{i<ω}(m_{i} \ n_{i−1}) ∈ U, where we set n_{−1} = 0. Note that B = ⋃_{i<ω}(n_{i} \ m_{i}) is the complement of A, and exactly one of A or B is an element of the ultrafilter. The following argument exploits the symmetry of the situation, some technicalities are due to the marginal asymmetry of the roles of I and II. Case 1: I has a winning strategy σ in G. Define a play p = (m_{0}, n_{0}, m_{1}, n_{1}, …) by:

m_{0} = σ(∅)  m_{1} = σ(m_{0}, n_{0}) m_{2} = σ(m_{0}, n_{0}, m_{1}, n_{1})  …
n_{0} = m_{0} + 1 n_{1} = σ(m_{0}, m_{1}) n_{2} = σ(m_{0}, m_{1}, n_{1}, m_{2})

In p, I follows σ so that A = ⋃_{i<ω}(m_{i} \ n_{n−1} ∈ U. Define a modified play p′ = (m_{0}, m_{1}, n_{1}, m_{2}, …):

m_{0} = σ(∅)  n_{1} = σ(m_{0}, m_{1}) n_{2} = σ(m_{0}, m_{1}, n_{1}, m_{2})  …

m_{1} = σ(m_{0}, n_{0}) m_{2} = σ(m_{0}, n_{0}, m_{1}, n_{1}) n_{2} = σ(m_{0}, m_{1}, n_{1}, m_{2})

In p′, player I follows σ, hence A′ = m_{0} ∪ (n_{1} \ m_{1}) ∪ (n_{2} \ m_{2}) ∪ … = m_{0}∪⋃_{1≤i<ω}(n_{i}\m_{i}) ∈ U. By the above-mentioned complementarity, A∩A′ = A ∩ m_{0} = m_{0} ∈ U. So U contains a finite set and is principal. Case 2: II has a winning strategy τ for G. Define a play p = (m_{0}, n_{0}, m_{1}, n_{1}, …), where

m_{0} = 0  m_{1} = τ(n_{0})  m_{2} = σ(m_{0}, n_{0}, m_{1}, n_{1})  …
n_{0} = τ(m_{0}) n_{1} = τ(m_{0}, n_{0}, m_{1}) n_{2} = σ(m_{0}, m_{1}, n_{1}, m_{2})

In p, II follows τ, so B = ⋃_{i<ω}(n_{i} \ m_{i}) ∈ U. Define a modified play p′ = (n_{0}, m_{1}, n_{1}, m_{2}, …):

n_{0}  n_{1}  n_{2}  …

m_{1} = τ(n_{0}) m_{2} = τ(n_{0}, m_{1}, n_{1}) m_{2} = τ(n_{0}, m_{1}, n_{1}, m_{2}, n_{2})

In this play, player II follow τ, hence B′ = ⋃_{1≤i<ω}(m_{i} \ n_{i−1}) = ⋃_{i<ω}(m_{i} \ n_{i−1}) ∈ U. But B ∩ B′ = ∅, contradiction. qed

Theorem 9.5 (AD) Every non-principal ultrafilter is countably complete.

Proof: Assume for a contradiction, that U is a non-principal ultrafilter which is not countably complete. Take a sequence (X_{n})_{n<ω} ⊆ U such that X = ⋂_{n<ω} X_{n} ∉ U. Define a sequence (Y_{n})_{n<ω} of disjoint sets by: Y_{n} = X_{n} \ (X_{0} ∪ … ∪ X_{n−1}). Define U^{∗} ⊆ 𝔓(ω) by: A ∈ U^{∗} iff ⋃_{n∈A} Y_{n} ∈ U. It is straightforward to check that U^{∗} is a non-principal ultrafilter on ω, contradiction to the previous theorem. qed In the next chapter we shall study measurable cardinals under the assumption of the axiom of choice. They will turn out to be powerful large cardinals. This is not quite the case in our AD situation. Let us note the following combinatorial facts:

Theorem 9.6 If κ is a measurable cardinal then κ is regular.

Proof: Let U be a measure on κ. For all α < κ: {α} ∉ U. By the < κ-closure of U: ∀β < κ β = ⋃_{α<β}{α} ∉ U. Consider δ < κ and (β_{i})_{i<δ} ⊆ κ a sequence of ordinals < κ. By the < κ-closure of U: sup_{i<δ}β_{i} = ⋃_{i<δ} β_{i} ∉ U. Then sup_{i<δ} ≠ κ and sup_{i<δ} < κ. Therefore κ is regular. qed One can say much more about measurable cardinals under AD but at the moment most proofs are beyond our techniques: e.g., under AD, ω_{2} is a measurable cardinal, and ω_{n} is a singular cardinal for cofinality ω_{2} for 3 ≤ n < ω.

10 Measurable Cardinals under AC

In this chapter we study measurable cardinals under the assumption of the full axiom of choice. Fix a measurable cardinal κ with a non-principal < κclosed measure U ⊆ 𝔓(κ).

10.1 Ultrapowers

The strength of a measurable cardinals under AC will become apparent by the formation of an ultrapower of the set theoretical universe V by U:

Definition 10.1 (a) V^{κ} = {f|f : κ → V }.

(b) Define a relation =^{U} on V^{κ}: f =^{U} g iff {α|f(α) = g(α)} ∈ U.

(c) Define a relation ∈^{U} on V^{κ}: f ∈^{U} g iff {α|f(α) ∈ g(α)} ∈ U.

(d) Let V^{U} be the class-sized first-order structure (V^{κ}, =^{U}, ∈^{U}).

Theorem 10.1 (Ło’s Theorem) For any first-order ∈-formula ϕ(v_{1}, …, v_{n}) and functions f_{1}, …, f_{n} ∈ V^{κ}: V^{U} ⊧ ϕ[f_{1}, …, f_{n}] iff {α|(V, =, ∈) ⊧ ϕ[f_{1}(α), …, f_{n}(α)]} ∈ U.

Proof: By induction on the complexity of ϕ: For atomic ϕ this is just the previous definition. Consider ϕ = ¬ψ: By inductive assumption and the ultrafilter properties: V^{U} ⊧ ϕ[f_{1}, …, f_{n}] iff V^{U} |̸= ψ[f_{1}, …, f_{n}] iff {α|(V, =, ∈) ⊧ ψ[f_{1}(α), …, f_{n}(α)]} ∉ U iff {α|(V, =, ∈) ⊧ ϕ[f_{1}(α), …, f_{n}(α)]} ∈ U. Consider ϕ = ψ∧χ: V^{U} ⊧ (ψ∧χ)[f_{1}, …, f_{n}] iff V^{U} ⊧ ψ[f_{1}, …, f_{n}] and V^{U} ⊧ χ[f_{1}, …, f_{n}] iff {α|(V, =, ∈) ⊧ ψ[f_{1}(α), …, f_{n}(α)]} ∈ U and {α|(V, =, ∈) ⊧ χ[f_{1}(α), …, f_{n}(α)]} ∈ U iff {α|(V, =, ∈) ⊧ (ψ ∧ χ)[f_{1}(α), …, f_{n}(α)]} ∈ U. Consider ϕ = ∃v_{0}ψ: Assume V^{U} ⊧ ∃v_{0}ψ[f_{1}, …, f_{n}]. Take f_{0} ∈ V^{κ} such that V^{U} ⊧ ψ[f_{0}, f_{1}, …, f_{n}]. By inductive assumption: {α|(V, =, ∈) ⊧ ψ[f_{0}(α), f_{1}(α), …, f_{n}(α)]} ∈ U. Then {α|(V, =, ∈) ⊧ ∃v_{0}ψ[v_{0}, …, f_{n}(α)]} ∈ U. Conversely assume that {α|(V, =, ∈) ⊧ ∃v_{0}ψ[v_{0}, …, f_{n}(α)]} ∈ U. By the axiom of choice we can take a function f_{0} ∈ V^{κ} such that {α|(V, =, ∈) ⊧ ψ[f_{0}(α), f_{1}(α), …, f_{n}(α)]} ∈ U. By inductive assumption: V^{U} ⊧ ∃v_{0}ψ[f_{1}, …, f_{n}]. qed This theorem implies in particular, that V^{U} satisfies the first-order theory of (V, ∈). Since (V, =, ∈) satisfies the equality axioms, =^{U} satisfies the equality axioms in V^{U}. So we can factor the structure V^{U} by =^{U}. Since we want to deal with the collection of all equivalence classes we have to present them by sets. This is achieved by “Scott’s trick”: an equivalence class is represented by its members of lowest von Neumann rank.

Definition 10.2 (a) For f ∈ V^{κ} let f_{U} = {g ∈ V^{κ}|∃ν ∈ Ord(g ∈ V_{ν} ∧ g =^{U} f ∧ ∀μ < ν∀h ∈ V_{μ} ¬h =^{U} f)}.

(b) Let V_{U} = {f_{U}|f ∈ V^{κ}}.

(c) Define a relation ∈_{U} on V_{U} by f_{U} ∈_{U} g_{U} iff f ∈^{U} g.

(d) We also denote the first-order structure (V_{U}, ∈_{U}) by V_{U}.

Then the Ło’s Theorem becomes the following:

Theorem 10.2 (Ło’s Theorem) For any first-order ∈-formula ϕ(v_{1}, …, v_{n}) and f_{U}^{1}, …, f_{U}^{n} ∈ V_{U}: V_{U} ⊧ ϕ[f_{U}^{1}, …, f_{U}^{n}] iff {α|(V, =, ∈) ⊧ ϕ[f^{1}(α), …, f^{n}(α)]} ∈ U.

There is a natural embedding from V into V_{U}:

Theorem 10.3 For x ∈ V define const_{x} : κ → V by const_{x}(α) = x. Define an embedding j : V → V_{U} by: j(x) = (const_{x})_{U}. By the Ło’s theorem j is welldefined and elementary, i.e., for any first-order ∈-formula ϕ(v_{1}, …, v_{n}) and x_{1}, …, x_{n} ∈ V_{U}: (V, ∈) ⊧ ϕ[x_{1}, …, x_{n}] iff V_{U} ⊧ ϕ[j(x_{1}), …, j(x_{n})].

We shall employ the Mostowski Isomorphism Theorem to collapse V_{U} to a transitive structure.

Theorem 10.4 (a) The relation ∈_{U} on V_{U} is extensional.

(b) The relation ∈_{U} is strongly wellfounded, i.e., it is wellfounded and for every f_{U} ∈ V_{U} the collection {g_{U} ∈ V_{U}|g_{U} ∈_{U} f_{U}} is a set. The latter is sometimes phrased as “∈_{U} is set-like”.

Proof: (a) is immediate by some previous remarks.

(b) We show that ∈_{U} is wellfounded. Assume for a contradiction that (V_{U}, ∈_{U}) is not wellfounded. By the axiom of choice take a descending sequence f_{U}^{0} ∋_{U} f_{U}^{1} ∋_{U} f_{U}^{2} ∋_{U} . . .. Define, for n < ω: X_{n} = {α|f^{n}(α) ∋ f^{n+1}(α)}. By Wosch’s Theorem: X_{n} ∈ U. By the countable completeness of U: ⋂_{n<ω} ∈ U. Take α ∈ ⋂_{n<ω}. Then f^{0}(α) ∋ f^{1}(α) ∋ f^{2}(α) …, contradiction. We show that ∈_{U} is set-like. Consider f_{U} ∈ V_{U}. Take ν ∈ Ord such that f ∈ V_{ν}. We show that {g_{U} ∈ V_{U}|g_{U} ∈_{U} f_{U}} ⊆ V_{ν+1}. Consider g_{U}, g_{U} ∈_{U} f_{U}. A = {α < κ|g(α) ∈ f(α)} ∈ U. Define a function g′ : κ → V by: g′(α) = g(α), if α ∈ A and g′(α) = 0, else. Then g′ =^{U} g and ∀α g′(α) ∈ ⋃ range(f) ∪ {0} ⊆ V_{ν}. Then g′ ∈ V_{ν+1} and g_{U} ⊆ V_{ν+1}. qed By the previous theorem we can apply the Mostowski Isomorphism Theorem to the structure V_{U}:

Definition 10.3 Let Ult(V, U) and σ_{U} be the unique classes such that Ult(V, U) is transitive and σ_{U} : (V_{U}, ∈_{U}) ≅ Ult(V, U). We call Ult(V, U) the ultrapower of V by U. The embedding j_{U} = σ_{U} ∘ j : (V, ∈) → (ULT(V, U), ∈) is elementary and is called the ultrapower map.

10.2 Combinatorial Consequences

Fix the situation j_{U} =: (V, ∈) → (ULT(V, U), ∈) and write M = ULT(V, U). We shall look at the combinatorial consequences of this construction.

Theorem 10.5 (a) κ is the critical point of j, i.e., j ↾ κ = id ↾ κ and j(κ) > κ.

Proof:

(1) ∀α < κ j(α) = α. Proof: By induction on α. Consider β < α. By the inductive assumption: j(α) > j(β) = β. Hence j(α) ≥ α. Conversely consider γ < j(α). Let γ = σ_{U}(g_{U}) for some g ∈ V^{κ}. Then σ_{U}(g_{U}) < j(α) = σ_{U}((const_{α})_{U}), g ∈^{U} const_{α}. By the Ło’s theorem: {ν < κ|g(ν) < const_{α}(ν) = α} ∈ U. By the < κ-completeness of U there is some β < α such that {ν < κ|g(ν) <= β} ∈ U. Then g =_{U} const_{β}, and by the inductive assumption: γ = σ_{U}(g_{U}) = σ_{U}((const_{β})_{U}) = j(β) = β < α. qed(1)

(2) j(κ) > κ. Proof: Define id : κ → κ: id(ν) = ν. Consider α < κ. Since U is non-principal and < κ-complete: {ν < κ|id(ν) > const_{α}(ν)} = {ν < κ|ν > α} ∈ U. By the Ło’s theorem and (1): σ_{U}(id_{U}) > σ_{U}((const_{α})_{U}) = j(α) = α. Hence σ_{U}(id_{U}) ≥ κ. Obviously, {ν < κ|id(ν) < κ} ∈ U. By the Ło’s theorem: σ_{U}(id_{U}) < σ_{U}((const_{κ})_{U} = j(κ). Then j(κ) > σ_{U}(id_{U}) ≥ κ. qed(2)

Theorem 10.6 The measurable cardinal κ is strongly inaccessible, and there are κ strongly inaccessible cardinals below κ.

Proof:

(1) κ is regular. Proof: Consider δ < κ and a function h : δ → κ. By the elementarity of j and the previous theorem: j(h) : j(δ) = δ → j(κ). Consider α < δ. Since the elementary map j distributes over set theoretical operations: h(α) = j(h(α)) = j(h)(j(α)) = j(h)(α). Hence the functions are equal: h = j(h). (M, ∈) ⊧ j(h) : δ → κ < j(κ). (M, ∈) ⊧ ∃θ < j(κ) j(h) : δ → θ. By the elementarity of j: (V, ∈) ⊧ ∃θ < κ h : δ → θ. qed(1)

(2) κ is a strong limit cardinal, i.e., ∀λ < κ 2^{λ} < κ. Proof: Consider λ < κ. Assume for a contradiction that μ = 2^{λ} ≥ κ. Take a bijective map h : μ → 𝔓(λ). Then (M, ∈) ⊧“j(h) : j(μ) → 𝔓(λ) is bijective”. The set a = j(h)(κ) is a subset of λ. Take some γ < μ such that a = h(γ). By the previous theorem: j(γ) ≠ κ . j(h)(κ) = a = j(a) = j(h(γ)) = j(h)(j(γ)), which contradicts the injectivity of j(h). qed(2)

(3) The set {λ < κ|κ is strongly inaccessible} is cofinal in κ. Proof: Consider β < κ. Since κ is strongly inaccessible in V, it is strongly inaccessible in (M, ∈). (M, ∈) ⊧“∃γ(β < γ < j(κ) ∧ γ is strongly inaccessible”. By the elementarity of j: (V, ∈) ⊧“∃γ(β < γ < κ ∧ γ is strongly inaccessible”. qed The ultrapower construction can be used to derive a normal measure on κ from a measure on κ.

Definition 10.4 A measure D on a cardinal κ is normal if it is closed relative to diagonal intersections: if (X_{ξ})_{ξ<κ} is a family of elements of D then the diagonal intersection △_{ξ<κ}X_{ξ} = {ζ < κ|∀ξ < ζ ζ ∈ X_{ξ}} ∈ D.

Theorem 10.7 Define U^{∗} = {X ⊆ κ|κ ∈ j(X)}. Then U^{∗} is a normal measure on κ.

Proof: (1) U^{∗} is an ultrafilter on κ. Proof: Consider X ⊆ Y ⊆ κ, X ∈ U^{∗}. Then κ ∈ j(X) ⊆ j(Y) and Y ∈ U^{∗}. Consider X ∈ U^{∗} and Y ∈ U^{∗}. Then κ ∈ j(X), κ ∈ j(Y), and κ ∈ j(X) ∩ j(Y) = j(X ∩ Y). Hence X ∩ Y ∈ U^{∗}. Consider X ⊆ κ. Then κ ∈ j(κ) = j(X) ∪ j(κ \ X). So exactly one of X and κ \ X is an element of U^{∗}. qed(1)

(2) U^{∗} is non-principal. Proof: Consider α < κ. κ ∉ {α} = j({α}) and so {α} ∉ U^{∗}. qed(2)

(3) U^{∗} is < κ-complete. Proof: Consider θ < κ and a sequence (X_{ξ})_{ξ<θ} ⊆ U^{∗} of elements of U^{∗}. Then κ ∈ ⋂_{ξ<θ} j(X_{ξ}) = j(⋂_{ξ<θ} X_{ξ}) and ⋂_{ξ<θ} X_{ξ} ∈ U^{∗}. qed(3)

(4) U^{∗} is normal. Proof: Consider a sequence (X_{ξ})_{ξ<κ} ⊆ U^{∗} of elements of U^{∗}. Then ∀ζ < κ κ ∈ j(X_{ζ}) = j((X_{ξ})_{ξ<κ})(ζ) and κ ∈ △_{ζ<j(κ)}j((X_{ξ})_{ξ<κ})(ζ) = j(△_{ζ<κ}(X_{ξ})_{ξ<κ}(ζ)). So △_{ζ<κ}X_{ζ} = △_{ζ<κ}(X_{ξ})_{ξ<κ}(ζ) ∈ U^{∗}. qed

10.3 The Rowbottom Theorem

Measurable cardinals are “large” cardinals which may be characterized by strong partition properties. These are higher-dimensional versions of pigeonhole principles.

Definition 10.5 Let κ, λ, μ be cardinals and n < ω.

(a) For any set X let [X]^{n} = {a ⊆ X|card(a) = n} and [X]^{<ω} = {a ⊆ X|card(a) < ω}.

(b) Let f : [X]^{n} → μ. Then Z ⊆ X is homogeneous for f if card(f[[Z]^{n}]) ≤ 1.

(c) Let g : [X]^{<ω} → μ. Then Z ⊆ X is homogeneous for g if Z is homogeneous for every g ↾ [X]^{n}, n < ω.

(d) κ → (λ)_{μ}^{n} denotes the property: every f : [κ]^{n} → μ has a homogeneous set Z with card(Z) ≥ λ.

(e) κ → (λ)_{μ}^{<ω} denotes the property: every g : [κ]^{<ω} → μ has a homogeneous set Z with card(Z) ≥ λ.

(f) κ is called a Rowbottom cardinal iff κ → (κ)_{2}^{<ω}.

A corollary to the following theorem is that a measurable cardinal is a Rowbottom cardinal.

Theorem 10.8 (The Rowbottom Theorem) Let U be a normal measure on a measurable cardinal κ and μ < κ Then every g : [κ]^{<ω} → μ has a homogeneous set Z ∈ U.

Proof: Since U is countably complete it suffices to prove the following by induction on n:

(1) Every g : [κ]^{n} → μ has a homogeneous set Z ∈ U. Proof: For n = 1 this is just the < κ-completeness of U. Assume the claim for n and consider a function g : [κ]^{n+1} → μ. For ν < κ define a function f_{ν} : [κ]^{n} → μ, f_{ν}(b) = g({ν} ∪ b) if ν < min(b), and f_{ν} = 0, else. By the inductive assumption, we can choose, for every ν < κ, a homogeneous set X_{ν} ∈ U and an ordinal δ_{ν} < λ such that f_{ν}[[X_{ν}]^{n}] = {δ_{ν}}. Using the claim for the initial case 1 we can take Y ∈ U and an ordinal δ < λ such that ∀ν ∈ Y δ_{ν} = δ. Define Z = Y ∩ △_{ν<κ}X_{ν} ∈ U. We show that Z is homogeneous for g. Let a ∈ [Z]^{n+1}. Let ν = min(a) and b = a \ {ν}. Note that b ∈ [X_{ν}]^{n} and δ_{ν} = δ. Then g(a) = g({ν} ∪ b) = f_{ν}(b) = δ_{ν} = δ, irrespective of the choice of a. Hence Z is homogeneous. qed 11 ANALYTIC DETERMINACY FROM A MEASURABLE CARDINAL40

11 Analytic Determinacy from a Measurable Cardinal

Theorem 11.1 (T. Martin) If there is a measurable cardinal then every Π_{1}^{1}-set is determined.

Proof: Let κ be a measurable cardinal with normal measure U. Let G ⊆ ω^{ω} be Π_{1}^{1}. By Theorem 7.7, there is a map D : ω^{<ω} → H_{ω} such that:

• for all x : n → ω the value D(x) is a linear order, whose domain consists of n natural numbers;

• D is an increasing function: x ⊆ y → D(x) ⊆ D(y);

• ∀P ∈ ω^{ω} P ∈ G ⟺ ⋃_{n<ω} D(P ↾ n) is well-founded.

Define an auxiliary, rule-based game G̃ as follows:

\begin{matrix}I & (x_{0}, e_{0}) & & (x_{2}, e_{2}) & & … \\ II & & x_{1} & & x_{3} & & … \end{matrix}

The rules of this game are:

• each e_{2n} maps D(x_{0}, …, x_{2n}) order-preservingly into the ordinals < κ;

• e_{2n+2} extends e_{2n}.

Player I wins every play in which all rules are kept. Therefore G̃ is a closed game. By the Gale-Stewart theorem, G̃ is determined. Case 1: Player I has a winning strategy σ̃ in G̃. Then player I can win the original game G by simply “hiding” the auxiliary moves e_{2n}. Case 2: Player II has a winning strategy τ̃ in G̃. To turn this into a winning strategy τ in G player II has to “simulate” the auxiliary moves of I in order to apply his strategy. On the other hand, the play should be independent of the specific virtual moves. This will be accomplished by taking virtual moves out of an appropriate homogeneous set in the ultrafilter U. Define τ(s) for s = (x_{0}, x_{1}, …, x_{2n}) as follows: D(s) is a linear order of size 2n + 1. Define a function f_{s} : [κ]^{2n+1} → ω, for a ∈ [κ]^{2n+1} let e_{2n} be the uniquely defined orderpreserving embedding of D(s) into (a, <). For m < n let e_{2m} = e_{2n} ↾ D(s ↾ (2m + 1)) and set f_{s}(a) = τ̃(x_{0}, e_{0}, x_{1}, x_{2}, e_{2}, …, x_{2n}, e_{2n}). By the Rowbottom theorem choose a homogeneous set Z_{s} ∈ U for the function f_{s}, let f_{s}[[Z_{s}]^{2n+1} = {n_{s}}, n_{s} ∈ ω. Then set τ(s) = n_{s}. We show that τ is a winning strategy for II. Let P = (x_{0}, x_{1}, x_{2}, x_{3}, …) ∈ ω^{ω} be a play according to τ. Assume for a contradiction that P ∈ G. We shall construct a fitting play P̃ in the game G̃ in which player II applies the strategy τ̃. Let Z = ⋂_{n<ω} Z_{P ↾2n+1} be the intersection of the homogeneous sets defined in the construction of τ. Since U is countably complete, Z ∈ U. Let D = ⋃_{n<ω} D(P ↾ n). Since P ∈ G, the linear order D is a wellorder. Take an orderpreserving embedding e : D → (Z, <). For n < ω define e_{2n} = e ↾ D(P ↾ (2n + 1)). By construction, the play

\begin{matrix}I & (x_{0}, e_{0}) & & (x_{2}, e_{2}) & & … \\ II & & x_{1} & & x_{3} & & … \end{matrix}

follows the rules of G̃, i.e., it is a win for player I. For n < ω and s = (x_{0}, x_{1}, …, x_{2n}): x_{2n+1} = τ(s) is the unique element of f_{s}[[Z_{s}]^{2n+1}] and range(e_{2n}) ∈ [Z_{s}]^{2n+1}. Therefore x_{2n+1} = f_{s}(range(e_{2n})) = τ̃(x_{0}, e_{0}, x_{1}, x_{2}, e_{2}, …, x_{2n}, e_{2n}). This means that player II applies the strategy τ̃ in the above play which, therefore, cannot be a winning strategy for II. This is a contradiction to the assumption of this case. Hence τ is a winning strategy for II in G. qed Using Solovay’s unfolding technique we get some immediate corollaries like:

Theorem 11.2 If there is a measurable cardinal, then every Σ_{2}^{1} set has the perfect subset property.

12 Borel-Determinacy

We follow the proof in Kechris, Classical …, 20.C.

13 Some Combinatorial Principles Related to Borel Determinacy

In this section we want to discuss inocuously looking principles which possess combinatorial strengths comparable to Borel determinacy (H. Friedman).