8
$\begingroup$

I'm sure this is just my google-fu failing me, but: what are sufficient, non-overkill large cardinal axioms which guarantee "Every (boldface) $\Pi^1_n$ set of (real codes for) countable ordinals contains or is disjoint from a club subset of $\omega_1$"? (I asked this question on math.stackexchange a couple weeks ago https://math.stackexchange.com/questions/1539202/clubbiness-of-pi1-n-sets, and received some attention but no answer.)

To clarify, I'm asking about the strength over ZFC.

Here's a very silly upper bound: suppose $L(\mathbb{R})$ is a model of AD, and moreover every $\Pi^1_n$-sentence with real parameters is absolute between $L(\mathbb{R})$ and $V$ (actually, I think this is already a consequence of "$L(\mathbb{R})\models AD$," but I'm not sure). Then let $A\in V$ be a $\Pi^1_n$-set of countable ordinals, via the formula (with real parameters) $\varphi$. By the absoluteness assumption, $\varphi^{L(\mathbb{R})}=A$, so $A\in L(\mathbb{R})$. And since $L(\mathbb{R})\models AD$, $L(\mathbb{R})$ thinks $A$ contains or is disjoint from a club. But inner models compute club-ness correctly, so we're done.

This seems massively overkill to me, though - what is the right bound?

$\endgroup$
  • 2
    $\begingroup$ Any $\Pi^1_n$ sentence with real parameters is absolute between $L(\mathbb R)$ and $V$ because the quantifiers in the sentence range only over reals, and $L(\mathbb R)$ contains all of the reals. $\endgroup$ – Andreas Blass Dec 3 '15 at 11:27
  • 4
    $\begingroup$ In view of my previous comment, it suffices to have enough determinacy to carry out, for $\Pi^1_n$ formulas, Solovay's proof that AD makes the club filter ultra. So you could check the complexity of the game that Solovay used, under the additional assumption that the target set is $\Pi^1_n$; presumably it will be be at worst a little higher than $\Pi^1_n$ in the projective hierarchy. So something in the neighborhood of $n$ Woodin cardinals would suffice. (I have no guess at the moment about whether significantly smaller cardinals will suffice; that's why this comment isn't an answer.) $\endgroup$ – Andreas Blass Dec 3 '15 at 11:32
  • 1
    $\begingroup$ Expanding Andreas' post, if the target set is $\bf\Pi^1_n$ with $n\geq 2$, then $\bf\Sigma^1_{n+1}$ determinacy suffices. $\endgroup$ – Cody Dance Dec 3 '15 at 22:10
  • 2
    $\begingroup$ What do we know about the strength of having a single club $C\subseteq\omega_1$ that decides (on a tail) every projectively definable set of countable ordinals? $\endgroup$ – Joel David Hamkins May 6 '16 at 1:04
4
$\begingroup$

An upper bound is an ineffable cardinal, which is weaker than $0^\#$. It is in the last few paragraphs of Harrington's paper "Analytic determinacy and $0^\#$".

$\endgroup$
4
$\begingroup$

Meanwhile, let me provide a lower bound. Your situation is not provable in ZFC; it is false in $L$, and it is incompatible with having a projective well-ordering of the reals. Furthermore, it implies that $\omega_1$ is inaccessible to reals.

Theorem. If there is a projectively definable $\omega_1$-sequence of distinct reals (for example, if there is a projectively definable well-ordering of the reals), then there is a projectively definable set of countable ordinals $S\subseteq\omega_1$, of the same complexity as the sequence, that is both stationary and co-stationary. (Thus, it neither contains nor omits a club.)

Proof. Assume that there is a projectively definable $\omega_1$-sequence of distinct reals $\langle z_\alpha\mid\alpha<\omega_1\rangle$, where $z_\alpha\subseteq\omega$. This situation occurs, for example, under $V=L$ or indeed, if there is a projectively definable well-ordering of the reals, since we can let $z_\alpha$ be the $\alpha^{\rm th}$ real in that well-ordering.

Let $S_n=\{\alpha\mid n\in z_\alpha\}$. This is a projectively definable set of ordinals, of the same complexity as the sequence. If it is not both stationary and co-stationary, then there is a club $C_n$ that contains or omits $S_n$. Let $C=\bigcap_n C_n$, which is a club subset of $\omega_1$. Note that if $\alpha\in C$, then $n\in z_\alpha$ is determined by whether $C_n$ contained or omitted $S_n$. Thus, the $z_\alpha$ for $\alpha\in C$ must all agree, contradicting our assumption that the reals were distinct. So one of the sets $S_n$ must be both stationary and co-stationary. QED

Corollary. If every projectively definable set of countable ordinals contains or omits a club, then $\omega_1$ is inaccessible to reals.

Proof. If $\omega_1$ is not inaccessible to reals, then $\omega_1=\omega_1^{L[x]}$ for some real $x$. In this case, there is an projectively $x$-definable $\omega_1$-sequence of distinct reals, and so there will be a projectively $x$-definable set $S\subseteq\omega_1$ that is both stationary and co-stationary.QED

$\endgroup$

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.