6
$\begingroup$

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

$\endgroup$
4
+50
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Max Dec 14 '16 at 18:55
  • $\begingroup$ @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$.) $\endgroup$ – Noah Schweber Dec 14 '16 at 19:05
  • $\begingroup$ I'm sorry I may be a bit tired but how would you do it with projective definability ? $\endgroup$ – Max Dec 14 '16 at 19:12
  • $\begingroup$ @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. $\endgroup$ – Noah Schweber Dec 14 '16 at 19:18
  • $\begingroup$ 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. $\endgroup$ – Noah Schweber Dec 14 '16 at 19:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.