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.

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.