Analytic Determinacy from a Measurable

The goal of this post is to prove analytic determinacy form the hypothesis that a measurable cardinal exists. This hypothesis is not optimal, but it is much less technical than the optimal hypothesis. Furthermore, the proof we will give is the “base case” for the inductive proof of projective determinacy from Woodin cardinals.

Definition: For a set X, an ultrafilter \mathcal{U} over X is a collection of subsets of X with the following properties:

  1. X\in \mathcal{U};
  2. If A,B\in\mathcal{U}, then A\cap B\in\mathcal{U};
  3. If A\in \mathcal{U}, and B\supseteq A, then B\in\mathcal{U};
  4. For every A\subseteq X, either A\in \mathcal{U}, or X\setminus A\in\mathcal{U}.

The first three conditions define a filter, whereas the fourth condition is what makes a filter into an ultrafilter. Given a cardinal \kappa, we say that an ultrafilter \mathcal{U} is \kappa-complete if for every \gamma<\kappa, \mathcal{U} is closed under intersections of length \gamma. An ultrafilter \mathcal{U} is non-principal if it contains no singletons.

Definition: An uncountable cardinal \kappa is measurable if there exists a \kappa-complete, non-principal ultrafilter \mathcal{U} over \kappa.

The name measurable comes from the fact that such an ultrafilter determines a nontrivial, \kappa-additive, binary measure over all of \kappa. For more on the measure problem, and the history thereof, the reader may consult Kanamori’s “The Higher Infinite”. It is relatively easy to check that a measurable cardinal is strongly inaccessible, directly from the definition. What is less apparent is that there are many inaccessible cardinals below \kappa, and in fact there are stationary many measurable cardinals below \kappa. The argument for this uses the fact that taking the ultrapower by V with respect to \mathcal{U} gives us an elementary embedding j:V\to M with critical point of j being \kappa. For now, I will push this material to the side, and focus on the combinatorial properties of measurable cardinals.

Definition: Let \mathcal{U} be an ultrafilter over a cardinal \kappa.  Such an ultrafilter is uniform if every element of \mathcal{U} has cardinality \kappa. We say that an ultrafilter \mathcal{U} over a cardinal \kappa is normal if for every function f:\kappa\to\kappa such that \{\alpha<\kappa :f(\alpha)<\kappa\}\in\mathcal{U}, there is an ordinal \beta<\kappa such that \{\alpha<\kappa : f(\alpha)=\beta\}\in\mathcal{U}.

Lemma: If \kappa is a measurable, then there exists a uniform, normal ultrafilter over \kappa.

Definition: Let X be a set, and let \kappa\leq|X| be a cardinal. We define the set [X]^\kappa=\{Y\subseteq X : |Y|=\kappa\}.

Theorem (Ramsey): Let \mathcal{U} be a uniform, normal ultrafilter over a cardinal \kappa, then for every n<\omega, and every Z\subseteq [\kappa]^n, there is some X\in\mathcal{U} such that either [X]^n\subseteq Z, or [X]^n\cap Z=\emptyset.

Using the above theorem of Ramsey, we may define, for any n\in\omega, an ultrafilter \mathcal{U}^{[n]} over [\kappa]^n by

Z\in \mathcal{U}^{[n]}\iff (\exists X\in \mathcal{U})([X]^n\subseteq Z).

Note that if n\geq 1, then each \mathcal{U}^{[n]} is \kappa-complete and non-principal.

We will be black-boxing the above results, but the proofs are fairly standard affair, and can be found in Jech or Kanamori. The main idea here is that we will use these Ramsey ultrafilters to define a tree of ultrafilters that correspond to some analytic subset A\subseteq[T]. Using this tree of measures, we can then show that the game G(A;T) is determined. We will now attempt to make this notion of correspondence more precise by introducing the notion of homogeneously Suslin sets, and homogeneous trees. We will be following the presentation in Martin’s unpublished monograph on determinacy. We begin by fixing some notation.

If p, q are finite sequences of the same length, then we define the sequence

\langle | p,q|\rangle = \langle\langle p(n), q(n)\rangle : n<lh(p)\rangle.

If T is a game tree, and p is a finite sequence, define

T[p]=\{q : \langle| p,q|\rangle\in T\}.

If T is a game tree, and if x is an infinite sequence, define

T(x)=\bigcup_{n\in\omega} T[x\upharpoonright n].

Let T be a game tree, Y be a set, and U be a tree on field(T)\times Y. We say that the T-projection of U is the set \{x\in [T] : [U(x)]\neq\emptyset\}. Given an infinite cardinal \kappa, and a game tree T, we say that a set A\subseteq [T] is \kappa-Suslin if it is the T-projection of a tree U on field(T)\times \kappa. That is, for x\in [T], we have that x\in A if and only if [U(x)]\neq\emptyset. I want to point out that the version of \kappa-Suslin is slightly different, but equivalent, to the one that is normally found in texts on descriptive set theory. The reason I’m using this definition is that it’s a bit easier to work with for what I want to do, and it makes the connection to \kappa-homogenously Suslin sets more apparent.

We claim that every coanalytic set is \kappa-homogeneously Suslin for every uncountable cardinal \kappa. In order to see this, we need a more useful, but slightly more complicated representation of coanalytic sets.

Theorem (Representations of {\bf \Pi}^1_1 sets): Let T be a game tree, then A\subseteq[T] is {\bf \Pi}^1_1 if and only if there is a function p\mapsto (lh(p);<_p) with domain T such that the following hold.

  1. For each t\in T, (lh(t);<_t) is a linear order with greatest element 0;
  2. If s,t\in T are such that s\subseteq t, then <_s = <_{t\upharpoonright lh(s)};
  3. For each x\in[T], x\in A if and only if <_x=\bigcup_{n\in\omega}<_{x\upharpoonright n} is a well-ordering of \omega.

The above theorem is a less techincal version of a result attributed to Lusin, Sierpinski, and Kleene, a corollary of which is that the pointclass {\bf \Pi}^1_1 is normed. The existence of a norm on a pointclass gives us some fairly nice closure properties (among other things), and the question of which pointclasses are normed turns out to be closely related to determinacy. Maybe I’ll take the time to discuss normed pointclasses and the First Periodicity Theorem once I’ve finished this project of working through the proof of projective determinacy from Woodins.

The above representation theorem is basically the reason we are working with {\bf \Pi}^1_1 sets, as it allows us to show that they have quite a few nice properties.

Lemma (Shoenfield): Let T be a game tree. If A\subseteq [T] is {\bf \Pi}^1_1, then A is \kappa-Suslin for every uncountable cardinal \kappa.

Proof: Fix an uncountable cardinal \kappa. Since A is coanalytic, we may fix functions p\mapsto <_p and x\mapsto <_x as given by the above representation theorem. Using this, we can define the desired tree U by setting

U=\{\langle | p,q |\rangle : p\in T and s embeds (lh(p); <_p) into (\kappa; <) \}.

Here, (\kappa; <) denotes the usual well order on \kappa. So, the idea is that, given some p\in T, we know that <_p is a linear order of lh(p) with greatest element 0. So, we can thank of an embedding of (lh (p); <_p) into (\kappa; <) as finite sequence s consisting of elements from \kappa of length lh(p) such that s(i) < s(j) if and only if i <_p j.

Now let x\in [T]. If g\in [U(x)], then g embeds (\omega; <_x) into (\kappa, <), which witnesses that <_x is a well order of \omega. Thus, x\in A. If we now fix some x\in A, we have that (\omega; <_x) is a well-order, and so there must be some g\in {}^\omega \kappa embedding (\omega; <_x) into (\kappa; <). Such a g must be in [U(x)] be construction. Therefore, for x\in [T],  x\in A if and only if [U(x)], and so A is the T-projection of U a tree on field(T)\times \kappa.

In the presence of a measurable cardinal, we can strengthen the above lemma. In particular, we can show that the coanalytic sets are \kappa-Suslin as witnessed by a tree U over field(T) \times \kappa that is homogeneous in the sense that it corresponds to a system of ultrafilters that “fit” well together. This homogeneity allows us to show that, in the presence of a measurable, coanalytic games are determined. The precise nature of this homogeneity will come from the Ramsey ultrafilters we defined earlier.

Definition: Let T be a tree, and U be a tree over field(T)\times Y for some set Y. Given two sequences p\subseteq q\in T, define the projection of U[q] to U[p], \chi_{q,p} : U[q]\to U[p] by \chi_{q,p}(s)=s\upharpoonright lh(p). Given two countably complete ultrafilters \mathcal{U}_p and \mathcal{U}_q over U[p] and U[q] respectively, we can use the defined projection to define a notion of compatibility between \mathcal{U}_p and \mathcal{U}_q. We say that \mathcal{U}_q projects to \mathcal{U}_p if, for every X\in \mathcal{U}_p, the set \{x\in U[q] : \chi_{q,p} (x)\in X\}\in \mathcal{U}_q. Given a system of ultrafilters \langle \mathcal{U}_p : p\in T\rangle, we say that the ultrafilters \mathcal{U}_p are compatible if, whenever p\subseteq q\in T, \mathcal{U}_q projects to \mathcal{U}_p.

Definition: Let T be a game tree, Y a set,  and \mathcal{U} a game tree over field(T)\times Y. We say that U is homogeneous for T if there exists a system of ultrafilters \langle \mathcal{U}_p : p\in T \rangle such that the following hold.

  1. Each \mathcal{U}_p is a countably complete ultrafilter over U[p];
  2. The ultrafilters \mathcal{U}_p are compatible;
  3. Given x\in [T], and a sequence \langle Z_n : n\in\omega \rangle with Z_n\in \mathcal{U}_{x\upharpoonright n} for each n\in \omega, then [U(x)]\neq\emptyset if and only if there is some function f\in {}^\omega Y such that, for each n\in\omega, f\upharpoonright n\in Z_n.

Additionally, we say that such a tree U is \kappa-homogeneous for an infinite cardinal \kappa if each \mathcal{U}_p is \kappa-complete.

The idea here is that, in order for this system to satisfy the third condition, it must be homogeneous in some sense. In particular, it tells us that each sequence x\in T corresponds to a direct system of elementary embeddings, the direct limit of which is well-founded if and only if [U(x)]\neq\emptyset. For now, discussing elementary embeddings would take us too far afield, but this does tell us that the system of ultrafilters associated to the T-projection of U fit well together.

Definition: Let T be a  game tree, and  A\subseteq [T]. We say that A is homogeneously Suslin if there exists a tree U over field(T)\times Y for some set Y such that U is homogeneous for T and A is the T projection of U. For an infinite cardinal \kappa, we say that A is \kappa-homogeneously Suslin if  it is the T projection of a \kappa-homogeneous tree.

We note that, our definition of \kappa-homogeneously Suslin says nothing about how large the set Y is. So, it may be the case that a set is \kappa-homogeneously Suslin without being \kappa-Suslin. The reason here is that we want a \kappa-homogeneously Suslin set to be \lambda-homogeneously Suslin for each cardinal \lambda <\kappa.

Theorem (Martin-Steel): For any game tree T, all |T|^+-homogeneously Suslin games in T are determined. That is, if A\subseteq[T] is |T|^+-homogeneously Suslin, then the game G(A;T) is determined.

Proof:  Let T be a game tree, and let A\subseteq [T] be |T|^+-homogeneously Suslin. Let Y be a set and U a  game tree on field(T)\times Y that is |T|^+-homogeneously Suslin for T, and such that A=\{x\in [T] : [U(x)]\neq\emptyset\}. Fix a system \langle \mathcal{U}_p : p\in T\rangle that witnesses the |T|^+-homogeneity of U. We will now define an auxiliary game tree T^* by describing the plays in T^*, and a set A^*\subseteq[T^*] that is closed in [T^*], such that the determinacy of G(A^*; T^*) gives us the determinacy of G(A:T). With that said, let T^* be the game tree in which plays are as follows:

I: \langle a_0, b_0\rangle \qquad \langle a_2, b_1\rangle \qquad \langle a_4, b_2\rangle \qquad \ldots \qquad \langle a_{2n}, b_n\rangle \qquad \ldots

II: \qquad \quad a_1 \qquad \qquad a_3 \qquad \qquad \ldots \qquad a_{2n-1}\qquad \quad \ldots

where for each i\in \omega,  \langle a_n : n\leq i\rangle\in T, and b_i\in Y. Let A^*\subseteq [T^*] be the collection of all plays \langle \langle a_0, b_0 \rangle, a_1,\langle a_2, b_1 \rangle,\ldots \rangle such that \langle \langle a_n, b_n \rangle : n<i \rangle\in U for each i\in\omega. By definition, A^* is closed in [T^*], and thus the game G(A^*;T^*) is determined. At this point, we want to translate winning strategies for certain players in this auxiliary game to winning strategies for those same players in the original game.

We begin by defining the projection map \pi: T^* \to T by \pi(\langle \langle a_0, b_0 \rangle, a_1,\langle a_2, b_1 \rangle,\ldots a_{2n-1} \langle a_{2n}, b_n\rangle \rangle)=\langle a_0, a_1,\ldots, a_{2n-1}, a_{2n}\rangle. Note that this induces a continuous surjection, which we will also call \pi : [T^*]\to [T]. Now, suppose that G(A^*;T^*) is determined in favor of I, and let \sigma^* be a winning strategy witnessing this. Define a strategy \sigma for I in G(A;T) by simply removing the second coordinates from I‘s plays in the auxiliary game. That is, we define \sigma(\pi(t^*))=\pi (\sigma^*(t^*)). Let x=\langle a_0, a_1,\ldots, \rangle\in [T] be a play consistent with the strategy \sigma, then by definition, for each n\in\omega, there is some sequence \langle b_0,\ldots, b_{n-1}\rangle\in{}^n Y such that \langle \langle x(i), b_i \rangle : i< n \rangle\in U. Thus, [U(x)]\neq\emptyset, and therefore x\in A, which means that \sigma is winning for I in G(A;T).

Next, assume that the game G(A^*;T^*) is determined in favor of II. Let \tau^* be a winning strategy for II witnessing this. As before, we want to use this to define a winning strategy \tau for II in G(A;T), but this is a bit more delicate than in the previous case. Whenever I makes a play in the original game, II has to somehow pick a canonical play for I in the game G(A^*; T^*) and use that to inform her play in G(A;T). It is here that we use the fact that A is |T|^+-homogeneously Suslin. For each p=\langle a_i : i\leq 2n\rangle\in T, and each s\in {}^{n+1}Y, let

q^*(p,s)=\langle \langle a_0, s(0)\rangle, a_1, \ldots, \langle a_{2n}, s(n)\rangle \rangle.

Each q^*(p,s) is a position in T^*, and is such that \pi(q^*(p,s))=p. We now define a strategy \tau for II in G(A:T) by setting

\tau(p)=a\iff \{ s\in U[p\upharpoonright n+1] : \tau^*(q^*(p,s))=a\}\in \mathcal{U}_{p\upharpoonright n+1},

Where p\in T is of length 2n+1. The map \tau is well-defined since each \mathcal{U}_p is |T|^+-complete since, at worst, latex $\tau$ could attempt to map p to |T|-many different things. But, take the intersection of the witnesses, and it turns out that they agree on a set in the associated ultrafilter, so \tau was in fact not trying to take p to |T|-many different things. We claim that \tau is a winning strategy for II in G(A;T). To see this, suppose otherwise. That is, suppose by way of contradiction that there is some x\in A that is consistent with \tau. For each n\in\omega, set

Z_{n+1}= \{s\in U[x\upharpoonright n+1] : \tau^* (q^*( x\upharpoonright 2n+1, s)) =x(2n+1) \},

and Z_0=\{\emptyset\}. In other words, each Z_{n+1} witnesses that \tau (x\upharpoonright 2n+1)=x(2n+1) and is therefore in \mathcal{U}_{x\upharpoonright n+1}, while Z_0\in \mathcal{U}_{\emptyset} by definition. Therefore, since U is homogeneous, there is some f\in{}^\omega Y such that f\upharpoonright\in Z_n for each n\in\omega. This means that the play

x^*=\langle \langle x(0), f(0)\rangle, x_1, \langle x(2), f(1) \rangle, \ldots \rangle

is a play in T^* consistent with \tau^*. But by definition, that means that x^*\in A^*, which contradicts the fact that \tau^* is winning for II in G(A^*;T^*).

Theorem (Martin-Steel): Let T be a game tree. If there exists a measurable cardinal \kappa, then every {\bf\Pi}^1_1 subset A\subseteq [T] is \kappa-homogeneously Suslin as witnessed by a tree U on field(T)\times \kappa.

Proof: Let T be a game tree, \kappa be a measurable cardinal, \mathcal{U} be a uniform normal ultrafilter on \kappa, and A\subseteq [T] coanalytic. Using the representation theorem for {\bf \Pi}^1_1 sets, fix maps p\mapsto <_p and x\mapsto <_x as given by that theorem. We will define our tree U as we did when proving that {\bf Pi}^1_1 sets are \kappa-Suslin for every uncountable cardinal \kappa. That is, we define

U=\{\langle | p,q |\rangle : p\in T and s embeds (lh(p); <_p) into (\kappa; <) \}.

Let p\in T. For each v\in [\kappa]^{lh(p)}, there is a unique s^p_v: lh(p)\to v embeds (lh(p); <) into (\kappa; <) by way of (v; <), and thus such that \langle | p, s^p_n |\rangle\in U. We will use these embeddings and the Ramsey ultrafilters above to define the desired system of ultrafilters \langle \mu_p : p\in T\rangle. Recall that we defined, for each n\in\omega, a \kappa-complete ultrafilter \mathcal{U}^{[n]} over [\kappa]^n by

Z\in \mathcal{U}^{[n]}\iff (\exists X\in \mathcal{U})([X]^n\subseteq Z).

Given p\in T, we define the ultrafilter \mu_p on U[p] by

X\in \mu_p \iff \{ v\in [\kappa]^{lh(p)} : s^p_v\in X\}\in \mathcal{U}^{[lh(p)]}.

That is, a set X\subseteq U[p] is in the ultrafilter if and only if the ranges of the elements of X are in the corresponding Ramsey ultrafilter. We already have shown that A is the T-projection of U. Furthermore, the system \langle \mu_p : p\in T\rangle is a system of \kappa-complete ultrafilters as we discussed earlier. To see that the ultrafilters \mu_p are compatible, let p\subseteq q\in T, let X\in \mu_p, and let \bar{X}=\{ v\in [\kappa]^{lh(p)} : s^p_v\in X\}\in \mathcal{U}^{[lh(p)]} witness that X\in \mu_p. Then, there is some B\in \mathcal{U} such that [B]^{lh(p)}\subseteq \bar{X}. Now consider C=\{s^q_v \in U[q] : s^q_v\upharpoonright lh(p)\in X\}, and let \bar{C}=\{ v\in [\kappa]^{lh(q)} : s^q_v\in C\}. We then see that [B]^{lh(q)}\subseteq \bar{C}, which means that C\in\mu_q, thus verifying compatibility.

We only need to check the third condition in the definition of homogeneous trees. With that in mind, fix x\in [T], and let \langle Z_n : n\in\omega\rangle be such that Z_n\in\mu_{x\upharpoonright n} for each n\in\omega. For each Z_n, fix the witness \bar{Z}_n=\{v\in [\kappa]^n : s^{x\upharpoonright n}_v\in Z_n\}\in\mathcal{U}^{[n]} that Z_n\in\mu_{x\upharpoonright n}. For each n\in \omega we may, by definition of \mathcal{U}^{[n]}, fix X_n such that [X_n]^n\subseteq \bar{Z}_n. By \kappa-completeness of \mathcal{U}, let X=\bigcap_{n\in\omega} X_n\in\mathcal{U}. Of course, we also have that for each n\in\omega, [X]^n\subseteq \bar{Z}_n. Suppose that [U(x)]\neq\emptyset. Then, x\in A, and so (\omega;<_x) is a well-order. Let f\in{}^\omega \kappa embed (\omega; <_x) into (X; <). To see that f is the desired witness to homogeneity, let n\in\omega. By definition of X and f, we have that f\upharpoonright\in U[p], and that the range of f\upharpoonright n is in \bar{Z}_n for each n\in\omega. But then we immediately have that f\upharpoonright \in Z_n for every n\in\omega.

As an immediate corollary to the above two theorems, we have the famous result of Martin’s from 1975.

Theorem (Martin): Let T be a game tree. If there exists a measurable cardinal \kappa>|T|, then for every {\bf\Pi}^1_1 set A\subseteq [T], the game G(A;T) is determined.

Okay, so I’m giving a seminar talk about topological games over the real line in a couple of weeks. Because of that, I think the next entry I’m going to do would be about showing how one propagates regularity properties through the projective hierarchy.

Definition: Let \mathcal{X} be a Polish space, and let X\subseteq \mathcal{X}. We say that X has the perfect set property if either X is countable, or there exists a homeomorphic copy of the Cantor space in X. We say that X has the property of Baire if there exists some open U\subseteq \mathcal{X} such that X\triangle U is meagre.

In particular, I’d like to start working towards proving the following theorem.

Theorem: Suppose that all {\bf \Pi}^1_n games over countable branching trees of countable height are determined, then every {\bf\Sigma}^1_{n+1} set has the perfect set property, has the property of Baire, and is Lebesgue measurable.

In particular, a corollary is the classical result that in ZFC, the {\bf \Sigma}^1_1 sets have the previously mentioned regularity properties.

It can be shown that the above hypothesis is actually optimal, but that requires a bit of inner model theory. Though, I may sketch the result that, if V=L, then there exists a \Pi^1_1 subset of the real line that is uncountable, but contains no homeomorphic copy of the cantor space.


One thought on “Analytic Determinacy from a Measurable

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s