Measurable cardinals under Axiom of Determinacy - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T15:52:18Z http://mathoverflow.net/feeds/question/33468 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/33468/measurable-cardinals-under-axiom-of-determinacy Measurable cardinals under Axiom of Determinacy Ricky Demer 2010-07-27T04:19:18Z 2010-10-13T20:48:51Z <p>I seem to remember reading somewhere that ZF+AD proves that omega-1 and omega-2 are measurable cardinals.</p> <p>Is that right?</p> <p>If so, can someone [point me to or give here] a [sketch or proof] of these results?</p> http://mathoverflow.net/questions/33468/measurable-cardinals-under-axiom-of-determinacy/33473#33473 Answer by John Stillwell for Measurable cardinals under Axiom of Determinacy John Stillwell 2010-07-27T05:40:19Z 2010-07-27T08:25:26Z <p>Solovay proved that ZF+AD implies that $\omega_1$ and $\omega_2$ are measurable, in the mid-1960s, but his proofs were not published at the time. Simpler proofs were given by other people. A proof for $\omega_1$ may be found in Moschovakis's <em>Descriptive Set Theory</em>, the 2nd edition of which is available for free <a href="http://www.math.ucla.edu/~ynm/books.htm" rel="nofollow">here</a>.</p> <p>Both results are in Jech's <em>Set Theory</em>, 3rd edition, pp. 633--636.</p> http://mathoverflow.net/questions/33468/measurable-cardinals-under-axiom-of-determinacy/33474#33474 Answer by Stefan Geschke for Measurable cardinals under Axiom of Determinacy Stefan Geschke 2010-07-27T05:45:43Z 2010-07-27T05:45:43Z <p>For $\omega_1$ the argument is as follows: Consider the filter generated by all closed and unbounded subsets of $\omega_1$. Under AD, this filter is an ultrafilter (this is due to Solovay). The filter witnesses measurability.</p> http://mathoverflow.net/questions/33468/measurable-cardinals-under-axiom-of-determinacy/33480#33480 Answer by alephomega for Measurable cardinals under Axiom of Determinacy alephomega 2010-07-27T07:07:40Z 2010-07-27T07:14:32Z <p>Like Stefan mentions, under AD every ultrafilter is $\omega_1$-complete. Then the proof that the c.u.b filter on $\omega_1$ is an ultrafilter proof goes through Solovay's game where players play codes for well-orderings. The players choose countable ordinals $\alpha_i$ for $i &lt; \omega$. Player I wins if $sup${$\alpha_i:i&lt;\omega$} $\in Y \subset \omega_1$ for some $Y \subset \omega_1$ over which the game is played. </p> http://mathoverflow.net/questions/33468/measurable-cardinals-under-axiom-of-determinacy/33546#33546 Answer by Andreas Blass for Measurable cardinals under Axiom of Determinacy Andreas Blass 2010-07-27T16:45:10Z 2010-07-27T16:45:10Z <p>An alternative proof for <code>$\omega_1$</code> goes via the set $D$ of Turing degrees (also known as degrees of unsolvability). $D$ is upward directed by the ordering $\leq_T$ of Turing reducibility, so the cones <code>$C_d=\{p\in D:d\leq_Tp\}$</code> generate a filter on $D$. The axiom of determinacy implies that this filter is an ultrafilter, i.e., that every subset $X$ of $D$ either includes a cone or is disjoint from a cone. (Proof: Define a game where the two players alternately choose natural numbers, producing an infinite sequence $x$; player 1 wins iff the Turing degree of $x$ is in $X$. Any strategy for either player, being a function from finite sequences of natural numbers to natural numbers, can be coded as a sequence $s$ of natural numbers. Any Turing degree $p$ in the cone $C_s$ [pedantically, the subscript should be the degree of $s$] is the degree of some play in which the player who has strategy $s$ uses it, because the other player can play any sequence of degree $p$ and then the overall play will also have degree $p$. So, if $s$ is a winning strategy for player 1 (resp. player 2), then all (resp. none) of the degrees in $C_s$ must be in $X$.) So AD gives an ultrafilter on $D$, called the cone ultrafilter. It's non-principal (because there is no highest Turing degree) and countably complete (because AD implies that all ultrafilters are countably complete --- this follows from the fact that there are, under AD, no non-principal ultrafilters on $\omega$). </p> <p>To get from $D$ to <code>$\omega_1$</code>, use the function $f$ assigning to each Turing degree $d$ the ordinal usually called <code>$\omega^{CK}(d)$</code>, the first ordinal that is not the order-type of an ordering of $\omega$ of degree $\leq_Td$. The image of the cone ultrafilter under this map $f$ is again a countably complete ultrafilter, now on <code>$\omega_1$</code>. It is non-principal because $f$ takes arbitrarily large countable ordinals as values on any cone.</p> <p>The ultrafilter obtained in this way is actually the same as the club filter mentioned in other answers, but the proof via Turing cones needs somewhat less recursion theory than Solovay's proof (which used Kleene's boundedness theorem for <code>$\Sigma^1_1$</code> sets).</p> <p>One can also prove the measurability of <code>$\omega_2$</code> by projecting the cone filter from $D$ to <code>$\omega_2$</code> via a suitable map. (I don't remember right now whether the suitable map sends a degree $d$ to the successor cardinal in $L[d]$ of (genuine) <code>$\omega_1$</code> or to the next Silver-indiscernible over $d$ after (genuine) <code>$\omega_1$</code>; maybe both of them work.)</p> http://mathoverflow.net/questions/33468/measurable-cardinals-under-axiom-of-determinacy/42061#42061 Answer by Tanmay Inamdar for Measurable cardinals under Axiom of Determinacy Tanmay Inamdar 2010-10-13T20:13:09Z 2010-10-13T20:13:09Z <p>For a different proof of the measurability of $\omega_1$ under AD, you could look at Eugene Kleinberg's book Infinitary Combinatorics and the Axiom of Determinateness. He shows it using the strong partition relation on $\omega_1$(that any function colouring the $\omega_1$-cardinality subsets of $\omega_1$ into 2 colours has a homogeneous subset of size $\omega_1$), showing that the filter of $\omega$-closed unbounded sets of $\omega_1$ is actually a normal ultrafilter. The only issue is that proving the strong partition relation is slightly involved. </p> <p>P.S. Could someone please tell me how to get the arrow notation for representing partition relations right? I have absolutely no idea. Also, please correct me if I'm wrong above; it's my first post on Math Overflow!</p>