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

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

Donald A. Martin. Measurable cardinals and analytic games. Fund. Math., 66 (3), (1969/1970), 287–291. MR0258637 (41 #3283).

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

Leo Harrington. Analytic determinacy and $0^\sharp$ . J. Symbolic Logic, 43 (4), (1978), 685–693. MR0518675 (80b:03065).

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.

This entry was posted on Monday, January 12th, 2015 at 7:58 pm and is filed under Students. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Leave a Reply Cancel reply

Enter your comment here...

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

Email (required) (Address never made public)

Name (required)

Website

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

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

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

Cancel

Connecting to %s

Categories

Mathoverflow

Convergence of $\sum(n^3\sin^2n)^{-1}$ May 14, 2010

I saw a while ago in a book by Clifford Pickover, that whether the Flint Hills series $\displaystyle \sum_{n=1}^\infty\frac1{n^3\sin^2 n}$ converges is open. I would think that the question of its convergence is really about the density in $\mathbb N$ of the sequence of numerators of the standard convergent approximations to $\pi$ (which, in itself, seems li […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Well known theorems that have not been proved February 3, 2023

I am not sure whether this qualifies as "well-known". Anyway, in set theory, in the study of the partition calculus (transfinite generalizations of Ramsey's theorem), effort centered for a while in studying relations of the form $$ \omega^m\to(\omega^n,k)^2 $$ for $m,n,k$ positive integers. Here, exponentiation is in the ordinal sense. This re […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Where is the Erdős–Rado theorem stated in Erdős and Rado's Bull AMS paper? December 23, 2014

This is Theorem 39 in the paper (see Theorem 4.(i) for a user-friendly preview). But the fact that $(2^\kappa)^+\to(\kappa^+)^2_\kappa$ is older (1946) and due to Erdős, see here: Paul Erdős. Some set-theoretical properties of graphs, Univ. Nac. Tucumán. Revista A. 3 (1942), 363-367 MR0009444 (5,151d). (Anyway, it is probably easier to read a more modern pre […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for The Erdős-Turán conjecture or the Erdős' conjecture? June 3, 2013

One of the best places to track these things down is The mathematical coloring book, by Alexander Soifer, Springer 2009. Chapter 35 is on "Monochromatic arithmetic progressions", and section 35.4, "Paul Erdős’s Favorite Conjecture", is on the problem you ask about. As far as I can tell, the question is sometimes called the Erdős-Turán con […]

Andrés E. Caicedo

Relative densities September 12, 2013

Throughout the question, we only consider primes of the form $3k+1$. A reference for cubic reciprocity is Ireland & Rosen's A Classical Introduction to Modern Number Theory. How can I count the relative density of those $p$ (of the form $3k+1$) such that the equation $2=3x^3$ has no solutions modulo $p$? Really, even pointers on how to say anything […]

Andrés E. Caicedo

Math.StackExchange

Does $|X|^m\cdot n^{|X|}\le (n+m)^{|X|}$ hold without choice? February 16, 2023

As we learned in this question, provably in $\mathsf{ZF}$, if $X$ is infinite then $|X|^n\le(n+1)^{|X|}$ for any natural number $n$, and this is optimal in the sense that, in general, $n+1$ cannot be replaced with $n$. A naïve inductive attempt to show the inequality suggests that perhaps we can actually prove that $|X|\cdot n^{|X|}\le(n+1)^{|X|}$, although […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Transfinite derivatives December 5, 2013

In Ralph P. Boas's A primer of real functions, page 118, this is discussed in the following way: The derivative of infinite order of $f$ is defined on an interval $I$ iff the sequence $(f^{(n)})$ converges uniformly on $I$ (it is enough to require uniform convergence on compact subsets of $I$). Call $L$ the limit of this sequence, so $L$ is continuous a […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for cardinals such that $\alpha < \alpha ^ \beta$ January 31, 2023

Recall that the beth ($\beth$) numbers are defined by transfinite recursion as $\beth_0=0$, $\beth_{\alpha+1}=2^{\beth_\alpha}$ and $\beth_\lambda=\sup_{\alpha

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Prove that Baire space $\omega^\omega$ is completely metrizable? November 30, 2013

The point here is that two functions are close iff they agree on an initial segment, that is, $d(f,g)\le 1/(n+1)$ iff $f(0)=g(0),f(1)=g(1),\dots,f(n-1)=g(n-1)$. Now, if $(f_n)_n$ is a Cauchy sequence, then, for each $n$, there is $N_n$ such that for all $m,k>N_n$ we have $d(f_m,f_k)\le1/(n+1)$. That is, all functions $f_m$ with $m>N_n$ agree on their f […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Is it possible for a function to be smooth everywhere, analytic nowhere, yet Taylor series at any point converges in a nonzero radius? January 7, 2014

No, this is not possible. Dave L. Renfro wrote an excellent historical Essay on nowhere analytic $C^\infty$ functions in two parts (with numerous references). See here: 1 (dated May 9, 2002 6:18 PM), and 2 (dated May 19, 2002 8:29 PM). As indicated in part 1, in Zygmunt Zahorski. Sur l'ensemble des points singuliers d'une fonction d'une variab […]

Andrés E. Caicedo

	ปั่นสล็อต on 414/514 The theorems of Rieman…
	Richard Kimberly Hec… on Woodin’s proof of the se…
	Is there a Borel-mea… on 414/514 Examples of Baire clas…
	Simple bijectiveness… on 580 -Some choiceless results…
	Schur’s theore… on 580 -III. Partition calcu…
	Uncountable linearly… on 403/503 – Homework …
	What is a non-constr… on On strong measure zero se…
	function from Nmathb… on Hindsight
	Cauchy Schwarz Inequ… on 275 -Positive polynomials
	What is a Cantor-sty… on 580 -Some choiceless results…
	Question about Gener… on 580 -Some choiceless results…
	Set has Measure Zero… on On strong measure zero se…
	Non-measurable subse… on 580 -Cardinal arithmetic …
	hmeng1 on 414/514 The theorems of Rieman…
	580 -Cardinal arithm… on 580 -Cardinal arithmetic …

A kind of library