Measurable cardinals under Axiom of Determinacy

Question

I seem to remember reading somewhere that ZF+AD proves that $\omega_1$ and $\omega_2$ are measurable cardinals.

Is that right?

If so, can someone [point me to or give here] a [sketch or proof] of these results?

Answer 1

An alternative proof for $\omega_1$ 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 $C_d=\{p\in D:d\leq_Tp\}$ 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$).

To get from $D$ to $\omega_1$, use the function $f$ assigning to each Turing degree $d$ the ordinal usually called $\omega^{CK}(d)$, 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 $\omega_1$. It is non-principal because $f$ takes arbitrarily large countable ordinals as values on any cone.

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 $\Sigma^1_1$ sets).

One can also prove the measurability of $\omega_2$ by projecting the cone filter from $D$ to $\omega_2$ 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) $\omega_1$ or to the next Silver-indiscernible over $d$ after (genuine) $\omega_1$; maybe both of them work.)

Answer 2

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.

Answer 3

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 < \omega$. Player I wins if $\sup\{\alpha_i:i<\omega\} \in Y \subset \omega_1$ for some $Y \subset \omega_1$ over which the game is played.

Answer 4

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 Descriptive Set Theory, the 2nd edition of which is available for free here.

Both results are in Jech's Set Theory, 3rd edition, pp. 633--636.

Answer 5

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.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!