9
$\begingroup$

It is known that for $n\ge 1$, $\mathbf{\Delta}^1_{2n}$-Determinacy implies $\mathbf{\Pi}^1_{2n}$-determinacy, but as far as I know, this is a theorem in $\mathsf{ZFC}$. It brings the following first question:

Question. Does $\mathsf{Z}_2$ prove $\mathbf{\Delta}^1_{2n}$-Determinacy implies $\mathbf{\Pi}^1_{2n}$-determinacy?

It is not too hard to prove that $\mathbf{\Pi}^1_{2n}$-Determinacy implies $\mathbf{\Sigma}^1_{2n+1}\text{-}\mathsf{DC}_0$, and $\mathbf{\Delta}^1_{2n}$-Determinacy implies $\mathbf{\Sigma}^1_{2n}\text{-}\mathsf{DC}_0$. I do not see a way to reduce the gap, and it inspires the following question:

Question. Working over $\mathsf{RCA}_0$ or $\Sigma^1_{2n+2}\text{-}\mathsf{AC}_0$, are $\mathbf{\Pi}^1_{2n}$-determinacy and "$\mathbf{\Delta}^1_{2n}$-Determinacy + $\mathbf{\Sigma}^1_{2n+1}\text{-}\mathsf{DC}_0$" equivalent?

$\endgroup$

1 Answer 1

4
$\begingroup$

I think that for $n=1$, the answer to the first question is yes. Basically, the alternate proof of this due to Kechris and Solovay should work, after one establishes enough basic facts about models of the form $L[x]$ in the sense of our $Z_2$ universe. That is, one should first develop:

  • basic theory of well-orderings on $\omega$,

  • theory of $L$, and more generally, $L[x]$, for reals $x$, where the "ordinals" of $L$ or $L[x]$ are just the lengths of our well-orderings on $\omega$,

  • show (using our determinacy assumption) that, in the sense of our $Z_2$ universe, $L[x]$ models ZFC, and Shoenfield absoluteness holds between $L[x]$ and our $Z_2$ universe, and facts about $\Pi^1_1$ and wellfoundedness of trees, and

  • now run the Kechris-Solovay proof.

Here is the Kechris-Solovay argument: Fix a $\Sigma^1_2$ formula $\varphi$, and suppose there is no winning strategy for either player for $G_\varphi$; say player I wants to get in the $\Sigma^1_2$ side and player II in the $\Pi^1_2$ side. Then by Shoenfield absoluteness, for every real $z$, $L[z]\models$ "there is no winning strategy for player II in $G_\varphi$". Therefore, fixing say $N=10$, for each real $z$, there is a least ordinal $\gamma=\gamma(z)$ such that $L_\gamma[z]\models\mathrm{ZFC}_N$ + "there is no winning strategy for player II in $G_\varphi$". (Here $\mathrm{ZFC}_N$ is just ZFC with Separation/Collection restricted to $\Sigma_N$ formulas.)

Consider the following game $G_\varphi'$: player I plays a pair of reals $(z,x)$, player II plays a real $y$, and then player I wins iff $(x,y)\in L_{\gamma(z)}[z]$ and $L_{\gamma(z)}[z]\models \varphi(x,y)$.

Then $G_\varphi'$ is $\Delta^1_2$, so is determined. Suppose that player II wins, with strategy $\sigma$. Working in $L_{\gamma(\sigma)}[\sigma]$, we get a strategy for player II in $G_\varphi$, by using $\sigma$, and having player I play $z=\sigma$ in $G_\varphi'$; this is a contradiction. (If $x\in \mathbb{R}\cap L_{\gamma(\sigma)}[\sigma]$, and player I plays $x$ in $G_\varphi$, then our response is $y$, where $(\sigma,x)$ is played by I in $G_\varphi'$ and $y$ is player II's response using $\sigma$. Since we played $z=\sigma$, we have $\sigma,x\in L_{\gamma(\sigma)}[\sigma]$, so $(x,y)\in L_{\gamma(\sigma)}[\sigma]$, and since player II wins this run of $G_\varphi'$, therefore $L_{\gamma(\sigma)}[\sigma]\models\neg\varphi(x,y)$. But then player II won the run of $G_\varphi$ in $L_{\gamma(\sigma)}[\sigma]$, as desired.)

So player I wins $G_\varphi'$, say with strategy $\tau$. We get a strategy for player I for $G_\varphi$ in our $Z_2$ universe, by using $\tau$ and ignoring $z$. For suppose $(x,y)$ results from this. Say player I produces $(z,x)$ and player II produces $y$. Since player I won $G_\varphi'$, we have $(x,y)\in L_{\gamma(z)}[z]\models\varphi(x,y)$. But then since $\varphi$ is $\Sigma^1_2$ and by $\mathrm{ZFC}_N$, it follows that $\varphi(x,y)$ holds in our $Z_2$ universe, as desired.

So, the main thing is to see that each $L[x]$ models ZFC in the sense of our $Z_2$ universe. I suspect that one can in fact develop the theory of sharps for reals and show that every real has a sharp. But we don't quite need this much. With similar considerations, but a little less work, we can make use of the usual proof that $0^\sharp$ exists from $\bigcup_{n<\omega}\omega\cdot n\text{-}\Pi^1_1$-determinacy, to see that for every real $x$, $L[x]$ models ZFC. One needs a little extra effort to analyze the game in our $Z_2$ universe. But we get that player II, who has to supply the $L$-theory of the coded ordinals, has a winning strategy. We get the same for $L[x]$, for every real $x$. From this, let us observe that every $L[x]$ has no largest cardinal. For if some $L[x]$ had a largest cardinal, then some $L[y]$ would have that $\omega$ is the largest cardinal. The game for $y^\sharp$ produces ordinals $\gamma^0_0<\gamma^0_1<\gamma^0_2<\ldots$, with supremum $\gamma^0$, and then ordinals $\gamma^1_0<\gamma^1_1<\ldots$, with supremum $\gamma^1$, etc. The theory of $\gamma^0$ in $L[y]$ is determined explicitly by the strategy $\sigma$ for player II for the game. But whatever $\gamma^0$ is output in a run, it is countable in $L[y]$. Therefore, there is a least $\xi>\gamma_0$ such that $\rho_\omega^{L_\xi[y]}=\omega$, and so the theory of $L_\xi[y]$ in no parameters determines $\xi$. But having player I play $\gamma^0_0=\xi$, we get a run with $\xi<\gamma^0$, so $\xi$ cannot be determined in this way, contradiction. So for every real $x$, $L[x]$ has no largest cardinal.

Now let us deduce that every $L[x]$ models ZFC in the sense of our $Z_2$ universe. Suppose not; so there is some integer $N$ and a real $x$ and ordinal $\gamma$ such that $L[x]$ has a cofinal map from $\gamma$ into the ordinals which is $\Sigma_N$-definable over $L[x]$ from parameters. We may absorb the parameters and $\gamma$ into $x$, and hence assume the only parameter is $x$ itself, and $\gamma=\omega$. Let $f:\omega\to\mathrm{OR}$ be the cofinal function produced. Then the question of whether $\gamma^0<f(n)$ is encoded by our winning strategy for player II in the game for $x^\sharp$. But we can arrange that $\gamma^0$ is as high as we like, so we get $f(n)<\gamma^0$ for all $n$, impossible.

So every $L[x]$ models ZFC. From here Shoenfield absoluteness is basically as usual.

$\endgroup$
3
  • $\begingroup$ Thank you for your answer! I think the Kechris-Solovay argument part also works over $\mathsf{ACA}_0 + \mathbf{\Delta}^1_2\text{-}\mathsf{Det}$ since $\mathbf{\Delta}^1_2\text{-}\mathsf{Det}$ bootstraps the background theory to $\Pi^1_1\text{-}\mathsf{CA}_0$, which is enough to prove Shoenfield absoluteness. I guess the role of $\mathsf{ZFC}_N$ in your proof is to guarantee Shoenfield absoluteness, so we should replace it with $\Pi^1_1\text{-}\mathsf{CA}_0$. $\endgroup$ Commented Nov 18 at 17:14
  • $\begingroup$ I am a little lost in the second part of the proof. showing $L[a]$ is a model of $\mathsf{ZFC}$. The proof uses $\bigcup_{n<\omega}\omega\cdot n \text{-}\mathbf{\Pi}^1_1$-Determinacy, but does it follow from $\mathbf{\Delta}^1_2$-Determinacy even over $\mathsf{Z}_2$? $\endgroup$ Commented Nov 18 at 17:26
  • 2
    $\begingroup$ Yes, can't we just directly express the payoff in boldface-$\Sigma^1_2$ and in boldface-$\Pi^1_2$ form? (We can in fact do it for any countable length sequence in the difference hierarchy over boldface-$\Pi^1_1$. Given a sequence $\left<A_\alpha\right>_{\alpha<\beta}$, where $\beta$ is an ordinal of our $Z_2$ universe (that is, the sequence is coded by some real), player I wins a run $(x,y)$ iff there is an ordinal $\alpha<\beta$, which is even (or maybe odd, however one defines it...), $(x,y)\in A_\gamma$ for all $\gamma<\alpha$, and $(x,y)\notin A_\alpha$. $\endgroup$ Commented Nov 18 at 20:39

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.