7
$\begingroup$

In this blog post by Gowers on Borel determinacy, Andres Caicedo says the following in a comment (slightly rephrased).

Let $\mathsf{ZFC^-}$ be $\mathsf{ZFC}$ without power set and $\mathsf{ZC^-}$ be $\mathsf{ZFC^-}$ without replacement, then working in $\mathsf{ZC^-}+\Sigma_1\text{-replacement}$ one can show that, if $\alpha$ is a recursive ordinal such that all $\Sigma_{\alpha+3}$-games on $\mathbb{N}^{<\mathbb{N}}$ are determined, then there is an ordinal $\beta_\alpha$ such that $L_{\beta_\alpha}\models\mathsf{ZFC^-}+\mathcal{P}^\alpha(\omega)\text{ exists}$, where $\mathcal{P}^\alpha(\omega)$ means the $\alpha$-th iteration of power set.

My questions are:

  1. Caicedo attributes this to unpublished work of Martin. Is there a published account now?

  2. $\Sigma_1\text{-replacement}$ is needed for basic theory of ordinals, and the result clearly fails in $\mathsf{ZC^-}$ because $V_{\omega+\omega}$ satisfies full Borel determinacy. Is it nevertheless possible to prove in $\mathsf{ZC^-}+\text{Borel Determinacy}$ the consistency of $\mathsf{ZFC^-}+\mathcal{P}^\alpha(\omega)\text{ exists}$ or something similar? What if $\mathsf{ZC^-}$ is further weakened to subsystems of second order arithemtic? I am aware of some results regarding lower levels like $\Delta^0_n$-determinacy for $n\approx 4$, but couldn't find anything about strength of full Borel determinacy. A natural question is whether we can define in $\mathsf{ZC^-}$ an $L$-like inner model in the first place; apparently we can.

$\endgroup$
1
  • 2
    $\begingroup$ In Martin's result, you need to assume $\Sigma^0_{\alpha+4}$-determinacy if $\alpha$ is finite. $\mathrm{ZFC^{-}}$ proves $\Sigma^0_3$-determinacy. $\endgroup$ Commented Sep 28, 2023 at 11:54

1 Answer 1

9
$\begingroup$

I don't know why you would want to work with $\mathrm{ZC}^{-}$, this is not a theory I would recommend to do math in. But as long as you only care about second order number theory, there is really no difference if you add $\Sigma_1-$Replacement. In fact, $\mathrm{ZC}^{-}+\Sigma_1-$Replacement is conservative over $\mathrm{Z}^-$ with respect to second order number theory. In particular one can prove the consistency result you are interested in in $\mathrm{Z}^{-}$ as long as you formalize everything correctly to make sense in that theory (note that you do not have access to cartesian products, etc.).

Let me sketch this fact that I mentioned. The main methods come from Mathias' paper

Mathias, A. R. D., The strength of Mac Lane set theory, Ann. Pure Appl. Logic 110, No. 1-3, 107-234 (2001). ZBL1002.03045.

Mathias shows that for any model of $\mathrm{Z}$ there is one of $\mathrm{Z}$+$\Sigma_1$-Replacement with the same $\mathcal P(\omega)$, we just have to check that the argument goes through without access to powerset. Powerset is indeed used in a few places, so we have to change a few things.

Let $M$ be a model of $\mathrm{Z}^{-}$. The idea is to add to $M$ all transitive isomorphs for extensional wellfounded relations. We do not necessarily have cartesian products, not even $\omega\times\omega$, so we might not literally have many of these. Instead let us consider subsets of $\omega$ which code such a relation with domain $\omega$ (in your favorite recursive fashion). Define an equivalence relation $\equiv$ on pairs $(n, r)$ where $n\in \omega$ and $r$ is such a code. This pair is supposed to represent $\pi(n)$ where $\pi\colon\omega\rightarrow X$ is the transitive collapse with respect to $r$ (which might not exist). So say $$(n, r)\equiv (m, s)$$ iff there is a subset of $\omega$ which codes a partial isomorphism $\phi:(\omega, \mathrm{decode}(r))\rightarrow (\omega, \mathrm{decode}(s))$ with $\phi(n)=m$. Replacing $=$ by $\in$ we define a binary relation $E$ in a similar fashion. The desired model is then $$N:=(C, E)/\equiv$$ where $C$ is the class of the tuples $(n, r)$. One can check that $N\models \mathrm{Z}^{-}$ and has the same $\mathcal P(\omega)$ as $M$, so $M, N$ believe the same second order number theory statements. We get the axiom of choice for free in $N$ as $N$ believes every set to be countable (as we only look at relations explicitly coded as a subset of $\omega$). The big advantage of $N$ over $M$ is that in $N$, every extensional wellfounded relation has a transitive isomorph (however axiom H considered by Mathias fails in $N$). Mathias infers $\mathrm{KP}$ through this axiom H, so we have to go down a different route. We can construct $L$ in $N$ as described in §4 of the linked paper. First let us show $L^N\models\mathrm{KP}$. There are two cases.

  • Case 1: $L^N$ has no largest cardinal. Then for a cardinal $\kappa$ of $L^N$, $L_\kappa^N$ suffices to collect witnesses for $\Delta_0$-formulas with parameters in $L_\kappa^N$.

  • Case 2: $L^N$ has a largest cardinal $\kappa$. We will show that over $L^N$, there is no $\Sigma_1$-definable cofinal map $f\colon \kappa\rightarrow\mathrm{Ord}$. Using the global wellorder of $L^N$ we could then define a sequence $\langle <_\alpha\mid \alpha<\kappa\rangle$ so that $<_\alpha$ is a wellorder on $\kappa$ of otp $\geq f(\alpha)$. Along a code $r\in M$ for a wellorder of length $\kappa$, we could then amalgamate to define (in $M$) a code for a wellorder of length $\sum_{\alpha<\kappa}\mathrm{otp}(<_\alpha)$,so $f$ was not cofinal after all.

Similarly, we see that $L[x]^N\models\mathrm{KP}$ for any set $x\in N$. Now we have enough of $\mathrm{ZFC}$ floating around to show $\mathrm{KP}$ in $N$ by an absoluteness argument: If $\varphi$ is some $\Delta_0$-formula, $p$ a real parameter and we are asked to collect witnesses $x$ to $\varphi(x, n, p)$ for each $n\in\omega$ then enough witnesses exist in $L[p]^N$ by (the proof of) $\Sigma^1_1$-absoluteness. So some initial segment of $L[p]^N$ witnesses the relevent instance of collection. As every set is countable in $N$, this suffices.

By the usual trick, $\Sigma_1$-Replacement follows from $\mathrm{KP}$, so we are done.

Here are a few final remarks: $\Sigma_1$-Replacement is the maximum amount that provably holds in $N$, $\Pi_1$-Replacement can fail if e.g. the ordinal height of $N$ "is $\aleph_\omega^{L^N}$". On the other hand, if a suitable version of global choice holds in $M$, for example there is a definable global wellorder, then $N$ is a model of full replacement.

Regarding your first question, Martin has not published the proof though it is available as excercise 2.3.3 with a detailed sketch in the draft of his book "Determinacy of Infinitely Long Games" available on his website.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .