# $\operatorname{AD}$ and the measurability of $\omega_1$

Are there proofs of the measurability of $\omega_1$ (under $\operatorname{AD}$) that do not use Turing degrees nor the $\Sigma_1^1$ boundedness lemma?

I've been struggling to find an "elementary" proof of this fact. Note that I consider the proof of "Assume $\operatorname{AD}$. Then every ultrafilter is $\sigma$-complete" to be elementary. The club filter on $\omega_1$ is thus readily seen to be a $\sigma$-complete filter, but the "ultra" part seems not to be so easy to prove (it's for an introductory course on $\operatorname{AD}$, without too much knowledge of recursivity etc.)

I'm not sure this will work for you, but there's a way to recast the Turing argument so that it avoids recursion theory; if this is the reason you want to avoid the Turing argument, this might be the way to go.

Namely, instead of working with Turing degrees, work with a coarser reducibility, which is easier to explain. For anything coarser than Turing reducibility, the cone property holds by the same argument, and we can define an analogous $f$ mapping reals to ordinals.

Specifically, here are the details for one particularly nice notion, relative projectiveness (or projective reducibility). Say a real $r$ is projective relative to a real $s$, and write $r\le_{p}s$, if there is a second-order sentence $\varphi(x, Y)$ in two variables with no parameters - where $x$ is a natural number variable and $Y$ is a set variable - such that $$r=\{n: \varphi(n, s)\}$$ holds. (There are many equivalent ways to phrase this.)

It's easy to check that this is, in fact, a reducibility (in particular, that it's transitive - this isn't hard, but it's worth doing explicitly), and so yields a degree structure $\mathcal{D}_p$. And by the same proof as in the Turing case, we have that any "$\equiv_p$-invariant" set of reals either contains or is disjoint from a cone in $\mathcal{D}_p$. So the "projective cone" filter on $\mathbb{R}$ is an ultrafilter. Moreover, by taking infinite joins, it's clear that this ultrafilter is countably closed.

Now we want to port it over to $\omega_1$. We'll use the same trick as in the Turing case: for a real $r$, let $f(r)$ be the least ordinal $\alpha$ such that $\alpha$ is not projectively definable in terms of $r$ (formally, there is no well-ordering of $\mathbb{N}$ of ordertype $\alpha$ which is projective relative to $r$); such a real exists, since there are only countably many projectively definable ordinals relative to a given real.

Note that this uses a small bit of choice - namely, that $\omega_1$ is regular. But this is provable in ZF+AD, so that's fine. Note that DC is not known to be provable in ZF+AD (although it does follow from ZF+AD+V=L$(\mathbb{R})$) so we can't use it here.

By the same argument as in the Turing case, the filter gotten by "porting over" the projective cone filter via $f$ is a measure on $\omega_1$.

Another natural reducibility to consider is relative constructibility. In many ways this is actually more natural than relative projectiveness; however, it makes things a bit trickier, since you have to show that $\omega_1$ is inaccessible from reals assuming AD.

However, this isn't hard - if $\omega_1^{L[r]}=\omega_1$ for some real $r$, then we have $\vert\mathbb{R}\cap L[r]\vert=\omega_1^{L[r]}=\omega_1$ (the first equaltiy since $L[r]$ satisfies condensation appropriately); but then $\mathbb{R}\cap L[r]$ is a counterexample to the perfect set property.

• And the fact that $f$ is well-defined comes from $\omega_1$'s inaccessibility to the reals. I guess this could work. I'll wait and see if other approaches are given but this seems fine. Dec 14 '16 at 18:55
• @Max Yes, that's a good point - I should have made that explicit in my answer. (Although, if you work with something narrower than constructibility, it can become trivial - so if your students have already seen e.g. projective definability, you could use the relative version of that and not have to prove anything about $\omega_1^V$.) Dec 14 '16 at 19:05
• I'm sorry I may be a bit tired but how would you do it with projective definability ? Dec 14 '16 at 19:12
• @Max Projective definability can be turned into a reducibility - a real $r$ is projectively reducible to a real $s$ if there is some projective (second-order) formula $\varphi(x, y)$ - where $x$ is a natural number variable and $y$ is a real variable and $\varphi$ has no other parameters - such that $s=\{n: \varphi(n, s)\}$. It's not hard to see that this is indeed a reducibility (in particular, it's transitive), and the usual proof of the cone theorem goes through; we now let $f$ map $r$ to the sup of the ordinals projectively definable from $r$, and it's immediate that this is countable. Dec 14 '16 at 19:18
• We could also use first-order definable, instead of projective: look at formulas in the language of arithmetic, augmented by a new unary predicate meant to stand for "$s$". But I suspect the projective version will be more natural, since the projective hierarchy already shows up in descriptive set theory. Dec 14 '16 at 19:19