Shehzad Ahmed – Coanalytic determinacy and sharps

Shehzad is my most recent student, having completed his M.S. thesis on May last year. He is currently pursuing his PhD at Ohio University. His page is here, and he also keeps a blog.

Shehzad Ahmed


His thesis, \mathbf \Pi^1_1-determinacy and sharps, is a survey of the Harrington-Martin theorem, showing the equivalence between a definable fragment of determinacy, and a large cardinal hypothesis.

After the fold, I review the basic notions, and give the tiniest of hints of what the theorem is and how its proof goes. Since the material is technical, the post is not really self-contained.

Baire space \omega^\omega is the set of all (infinite) sequences of natural numbers, that is, the set of all functions f:\mathbb N\to\mathbb N (as customary, we identify \mathbb N with the ordinal \omega). We can consider Baire space as a topological space by giving \omega the discrete topology, and \omega^\omega the product topology. This is a completely metrizable topology, with metric given by d(f,f)=0 and, if f\ne g, then d(f,g)=1/(n+1) iff n is least such that f(n)\ne g(n).

A subset of Baire space is coanalytic, or \mathbf \Pi^1_1, iff its complement is the image of Baire space under a continuous function.

Given a set A\subseteq\omega^\omega,  the Gale-Stewart game associated to A is the infinite game between two players I and II that alternate playing natural numbers in each turn, with I playing first. At the end of a run of the game, the two players have collaborated to produce an element f of Baire space, and player I wins the game iff f\in A. We say that A (or the associated game) is determined iff one of the players has a winning strategy.

(This can be readily generalized: Given A\subseteq X^\omega, we can consider the similar game where the players now play elements of X rather than natural numbers.)

Coanalytic determinacy is the statement that all \mathbf \Pi^1_1 sets are determined. Although one can prove in \mathsf{ZF}+\mathsf{DC} that all Borel games are determined, \mathsf{ZFC} is not enough to prove the same result for all coanalytic games.

Tony Martin proved in 1970 that coanalytic determinacy holds as long as we assume the existence of mild large cardinals, see

Specifically, Martin showed this from the assumption that there is a measurable cardinal. Recall that \kappa is measurable iff it is the critical point of a nontrivial elementary embedding j:V\to M from the universe V into some transitive class M. It is a classical result of Gale and Stewart that all closed games (on any X^\omega, where again X is discrete and X^\omega carries the product topology) are determined.

What Martin did was to associate to each coanalytic set A a closed set \hat A in a (much) larger space in such a way that the corresponding games are equivalent, in the sense that either player has a winning strategy in one iff the same player has a winning strategy in the other, and in fact there is a translation procedure that associates strategies in one game with strategies in the other.

Very roughly speaking, what Martin does is to take advantage of the fact that coanalytic sets admit a nice representation: A set A\subseteq\omega^\omega is coanalytic iff it is \omega_1-Suslin, that is, there is a tree T on \omega\times\omega_1 such that for all x in Baire space, x\in A iff there is some f\in {\omega_1}^\omega such that (x\upharpoonright n,f\upharpoonright n)\in T for all n (that is x is in the first-coordinate projection of the closed set {}[T] of infinite branches through the tree T).

Given such a tree T, a point x is not in A iff the corresponding tree T_x of attempts to find a “witness” f is well-founded. This is the tree on \omega_1 whose elements are finite sequences b of countable ordinals such that if n is the length of b, then (x\upharpoonright n, b)\in T. This means that the tree T_x admits a rank function, that associates to each b\in T_x an ordinal \alpha_b in such a way that if c properly extends b, then \alpha_c<\alpha_b.

What Martin does is to use the ultrafilter associated to the measurable cardinal \kappa to select “typical” ordinals that “anticipate” the values of the ranking function.

Actually, analysis of the proof shows that the measurable is an overkill, and the assumption that all elements of Baire space admit sharps suffices (in the published paper, Martin uses that there is a Ramsey cardinal). Given a point x\in\omega^\omega, the assertion that the sharp for x exists is (equivalent to) the statement that there is a nontrivial elementary embedding j:L[x]\to L[x]. This provides us with an L[x]-ultrafilter that suffices to carry out the ranking argument hinted at above.

Leo Harrington showed in 1978 that the use of sharps is necessary, in the paper

What Leo did was to identify an assumption that implies the existence of sharps, and then show that the determinacy of certain games implies this assumption. Specifically, to prove that 0^\sharp exists it suffices to establish that there is a point x in Baire space such that, for all (sufficiently large) countable ordinals \alpha, if L_\alpha[x] is admissible, then \alpha is a cardinal of L. Here, a structure M is admissible iff it is a model of \mathsf{KP}, a weak fragment of set theory that allows us to carry out basic recursive arguments.

Assuming coanalytic determinacy, Leo proceeds to find such a point x using the winning strategy of the following game G: As usual, I and II alternate playing natural numbers. The moves of I code a binary relation R on \omega, and the moves of II code another binary relation E . Player I loses unless R is a well-ordering of \omega. If it is a well-ordering, let \beta be its order type. In that case, Player II wins iff (\omega,E) is a model of extensionality that end-extends (L_\beta,\in). One needs to verify of course that the payoff set of G is indeed \Pi^1_1 and that player I does not have a winning strategy. The determinacy assumption then gives us that there is a winning strategy \tau for player II. We can identify \tau with a point x in Baire space.

Given a countable ordinal \alpha with L_\alpha[x] admissible, Harrington then uses Steel’s forcing over L_\alpha[x] to argue that \alpha must be a cardinal in L. Essentially, if this is not the case, then a collapsing map witnessing that \alpha is not a cardinal can be identified “too quickly” (using a generic for Steel’s forcing), contradicting the admissibility of L_\alpha[x].

Shehzad presentation of sharps is “classic”. For a presentation in terms of mice, I recommend Ralf Schindler‘s recent book.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: