Reflection principles in set theory without powersets

In a ${\rm ZFC}$ universe $V$, given any formula $\varphi(x,a)$ with parameter $a$, there is a transitive set containing $a$ such that the formula $\varphi(x,a)$ is absolute between the set and the entire universe. Namely, the set reflects the universe with respect to the formula $\varphi(x,a)$. The scheme of assertions that every formula (with parameters) is reflected in this way down to some transitive set is called the Reflection principle. To prove the Reflection principle, we will crucially utilize the von Neumman $V_\alpha$-hierarchy. Choose some $V_{\alpha_0}$ containing $a$. Given $V_{\alpha_n}$, choose $V_{\alpha_{n+1}}$ such that for any subformula $\psi$ of $\varphi$ and parameters $\bar b$ from $V_{\alpha_n}$, if $V$ satisfies $\exists y\,\psi(y,\bar b)$, then $V_{\alpha_{n+1}}$ already has some such $y$. Let $\alpha$ be the supremum of the $\alpha_n$ for $n\lt\omega$. By the Tarski-Vaught test, $V_\alpha$ reflects $V$ for the formula $\varphi(x,a)$. Let's think more carefully now about which axioms of ${\rm ZFC}$ we used to carry out our argument. The existence of the von Neumann hierarchy uses the Powerset axiom together with the Replacement scheme. We also use Replacement to conclude that given a $V_{\alpha_n}$, the required $V_{\alpha_{n+1}}$ exists. Notice that the argument does not make use of the Axiom of Choice and so the Reflection principle holds in ${\rm ZF}$ as well. In fact, it is not difficult to show that Replacement, Collection, and Reflection are all eqiuvalent over Zermelo set theory (${\rm ZF}$ without Replacement). But what happens if we work in a set theory where powersets are not available?

First, we need to discuss what a set theory without powersets looks like. It is tempting to say that it is simply the axioms of ${\rm ZFC}$ with the Powerset axiom removed. But the issue is that without powersets, we need to be more careful about some of the other axiom choices we make among axioms that are equivalent in the presence of powersets. For instance, the Replacement and Collection schemes are not equivalent without the Powerset axiom around. If we take the version of ${\rm ZFC}$ with Replacement minus Powerset, then we get a very unpleasant set theory where Collection can fail, $\omega_1$ can be a countable union of countably many sets, every set of reals can be countable while $\omega_1$ exists, where Łoś's theorem can fail for ultrapowers, etc. [1] This can be fixed if we replace Replacement by Collection, but even then another issue arises with the usually equivalent versions of the Axiom of Choice. As is well known, over the other axioms of ${\rm ZFC}$, ${\rm AC}$, the assertion that every family of sets has choice function, is equivalent to Zorn's Lemma, the assertion that every partial order which has an upper bound for every chain has at least one maximal element, and is in turn equivalent to the well-ordering principle, the assertion that every set can be well-ordered. All known proofs of the equivalences make a crucial use of the Powerset axiom. The theory consisting of ${\rm ZF}$ without Powerset, Collection, and ${\rm AC}$ does not prove the well-ordering principle and it is an open question whether the same theory with ${\rm AC}$ replaced by Zorn's Lemma implies ${\rm AC}$ [2]. Taking all these subtleties into account leads us to conclude that the most robust set theory without powersets is ${\rm ZFC}^-$, the theory consisting of the axioms of ${\rm ZFC}$ without Powerset, with Collection, and with the well-ordering principle. The theory ${\rm ZFC}^-$ has many natural models. If $\kappa$ is a regular cardinal, then $H_{\kappa^+}$, the collection of all sets whose transitive closure has size at most $\kappa$ is a model of ${\rm ZFC}^-$. Class forcing extensions by pretame forcing, although they may fail to have powersets, also satisfy ${\rm ZFC}^-$. The theory ${\rm ZFC}-$, where we keep Replacement, but take the well-ordering principle as the choice axiom still has all the unpleasantness described above, but provides an interesting variation on the no powersets theme.

Now we can get back to our question in a more formal fashion. Does the theory ${\rm ZFC}^-$ imply the Reflection principle? Because we have Collection, given any set, we can build a larger set with existential witnesses for some collection of formulas with parameters from the original set. But now now it should be clear that we need some version of dependent choice for definable relations in order to be able to repeat this construction $\omega$-many times. So let the ${\rm DC}$-scheme assert that we can make $\omega$-many dependent choices along any definable (with parameters) relation without terminal nodes. More formally the ${\rm DC}$-scheme is a scheme of assertions for every formula $\varphi(x,y,a)$ with parameter $a$ that if $\forall x\,\exists y\,\varphi(x,y,a)$ holds, then there is a sequence $\{x_n\mid n\lt\omega\}$ such that $\varphi(x_n,x_{n+1},a)$ holds for all $n\lt\omega$. Indeed, it turns out that over ${\rm ZFC}^-$, the Reflection principle is equivalent to the ${\rm DC}$-scheme because if the Reflection principle holds, then we can reflect the formula $\varphi(x,y,a)$ to a transitive set and then use ${\rm AC}$ to find the sequence of dependent choices. But alas, the ${\rm DC}$-scheme is independent of ${\rm ZFC}^-$, and so it immediately follows that the Reflection principle is as well [3]. We currently have two very different models of ${\rm ZFC}^-$ in which the ${\rm DC}$-scheme fails. Both are obtained as inner models of forcing extensions by a tree iteration of Jensen's forcing.

Jensen's forcing $\mathbb J$ is a subposet of Sacks forcing that is constructed in $L$ using the $\diamondsuit$-principle. Unlike the full Sacks forcing, $\mathbb J$ has the ccc ($\diamondsuit$ is used to seal maximal antichains). It adds a unique generic real whose singleton is $\Pi^1_2$-definable. [4] A finite $n$-length iteration $\mathbb J_n$ of Jensen's forcing also has the ccc and adds a unique $n$-length generic sequence of reals that is again $\Pi^1_2$-definable [5]. A tree iteration of Jensen's forcing along a tree $\mathcal T$ of height $\omega$, $\mathbb P(\mathbb J,\mathcal T)$, adds a tree isomorphic to $\mathcal T$ whose $n$-level nodes are $n$-length generic sequences for $\mathbb J_n$ that are coherent in the sense that if $s\leq t$ are two nodes on $\mathcal T$, then the sequence on node $s$ is the restriction of the sequence on node $t$. Crucially, for certain trees $\mathcal T$ such as $\omega^{\lt\omega}$ or $\omega_1^{\lt\omega}$, the poset $\mathbb P(\mathbb J,\mathcal T)$ has the ccc and in its forcing extension, the only $n$-length generic sequences of reals for $\mathbb J_n$ are those explicitly appearing on the nodes of the generic tree, and the tree itself is $\Pi^1_2$-definable [3]. The key theme with Jensen's forcing and its iterations is uniqueness of generics.

The first model is obtained by forcing over $L$ with $\mathbb P(\mathbb J,\omega_1^{\lt\omega})$. So let $G\subseteq \mathbb P(\mathbb J,\omega^{\lt\omega})$ be $L$-generic and let $L[G]$ be the resulting forcing extension. There is a symmetric submodel $W$ of $L[G]$ (satisfying ${\rm ZF})$ which has the tree of the generic sequences, but no branch through the tree, witnessing a $\Pi^1_2$-definable failure of ${\rm DC}_{\omega}$, but at the same time ${\rm AC}_\omega$ holds in $W$ [3]. It follows that $H_{\omega_1}^W$ satisfies ${\rm ZFC}^-$ (use ${\rm AC}_\omega$ in $W$ to conclude that choice holds), but fails the ${\rm DC}$-scheme. Note that this model of ${\rm ZFC}^-$ has $\omega$ as the largest cardinal. The second model is obtained by forcing over $L$ with the class tree iteration $\mathbb P(\mathbb J,{\rm Ord}^{\lt\omega})$, which we can argue also has both the ccc and the uniqueness of generics property [6]. So let $G\subseteq \mathbb P(\mathbb J,\omega^1_{\lt\omega})$ be $L$-generic and let $L[G]$ be the resulting forcing extension. The extension satisfies satisfies ${\rm ZFC}^-$ because class forcing with the ccc is pretame [7], but does not have powerset of $\omega$. In this case, we consider the inner model $M$ that is the union of the $L[G_T]$, where $T$ is a set-sized well-founded subtree of ${\rm Ord}^{\lt\omega}$ and $G_T=G\upharpoonright \mathbb P(\mathbb J,T)$. It is argued in [6] that $M$ satisfies ${\rm ZFC}^-$, but the ${\rm DC}$-scheme fails. The model $M$ has does not have powerset of $\omega$, but it does have unboundedly many cardinals, indeed all the same cardinals as $L$.

Let's argue that the weak Reflection principle holds in the small model $H_{\omega_1}^W$. Fix a formula $\varphi(x)$ and $a\in H_{\omega_1}^W$ such that $H_{\omega_1}^W\models\varphi(a)$. We can assume without loss of generality, by replacing $a$ with its transitive closure, that $a$ is transitive. The full forcing extension $L[G]$ can construct a countable submodel of $H_{\omega_1}^W$ satisfying $\varphi(a)$. The universe $L[G]$ then satisfies that there is a real coding a well-founded model with a transitive set $a'$ isomorphic to $a$ and satisfying $\varphi(a')$. This is a $\Sigma^1_2$-assertion about $a$, which must, by Shoenfield's absoluteness principle, be absolute between $L[G]$ and $W$. Thus, $W$ also has a countable well-founded model satisfying $\varphi(b)$ for some transitive in it set $b$ isomorphic to $a$. The collapse of this model is a countable transitive model containing $a$ because, by the transitivity assumption on $b$, it must get mapped to $a$, and satisfying $\varphi(a)$. But the collapsed model must be inside $H_{\omega_1}^W$ precisely because it is countable and transitive.

Now let's argue that the weak Reflection principle fails in the large model $M$. Let $a=H_{\omega_1}^L$ and consider the formula $\varphi(a)$ asserting that every $n$-length $L$-generic sequence for $\mathbb J_n$ can be extended to an $L$-generic $n+1$-length sequence for $\mathbb J_{n+1}$. We need the parameter $a$ for the definition of $\mathbb J_n$ and to check the $L$-genericity of the sequence. The class generic tree of the generic sequences for $\mathbb J_n$ is contained in $M$ and so $M$ satisfies $\varphi(a)$. The model $M$ is the union of the models $L[G_T]$, where $T$ is a well-founded subtree of ${\rm Ord}^{\lt\omega}$ and $G_T$ is the restriction of $G$ to $T$. The crucial fact here is that each $L[G_T]$ contains exactly the generic $n$-length sequences for $\mathbb J_n$ which occur in $T$ (the proof is similar to Theorem 3.1 in [8]). Suppose some set $A$ in $M$ contains $a$ and satisfies $\varphi(a)$. Then $A\in L[G_T]$ for some well-founded subtree $T$. The set $A$ is correct about a sequence being $n$-generic for $\mathbb J_n$ because this can be checked with $a$. But then because all the generic sequences in $A$ must come from $T$ we can use $A$ to construct a branch through $T$ contradicting that $T$ is well-founded.

The Reflection principle also implies Collection over ${\rm ZFC}-$. A natural question is then whether the weak Reflection principle implies Collection over ${\rm ZFC}-$. Currently there is no easy answer because every model of ${\rm ZFC}-$ which we have fundamentally fails the weak Reflection principle. To build any one of these models, we start out with a specially chosen forcing product $\mathbb P_\alpha$ of length $\alpha$. We then let our model $W$ be the union of the models $V[G_\xi]$ for $\xi\lt\alpha$. Because of the special properties of the chosen forcing, we can show that $W\models{\rm ZFC}-$, but Collection fails because we cannot collect the generics $G_\xi$. Thus, $W$ satisfies that every generic $G_\xi$ can be extended to a generic for a longer product, but this cannot hold true in any set in $W$ because all the sets are in some $V[G_\xi].$ Of course, we can ensure that our sets are correct about genericity by including the full powerset of the forcing in the set.

Now let's weaken our Reflection principle further by considering the sentence Reflection principle, where as the name suggests, we reflect only sentences. Does ${\rm ZFC}^-$ imply the sentence Reflection principle? If we don't ask that the reflecting set is transitive, then the answer is yes. If a model of ${\rm ZFC}^-$ satisfies a sentence $\varphi$, then it also satisfies $\text{Con}(\varphi)$ (Anton Freund convinced me of this). So we just need to argue that we can carry out the Henkin construction to build a model of $\varphi$, but thinking through it carefully, we can see that Replacement suffices to build a Henkin model. So what about a transitive set? We don't know the answer.

Meahwhile, let's argue that the large model $M$ satisfies the sentence Reflection principle. Suppose that some sentence $\varphi$ holds in $M$. Since the forcing $\mathbb P(\mathbb J, {\rm Ord}^{\lt\omega})$ is pretame, it has definable forcing relations. So there is a condition $p\in \mathbb P(\mathbb J,{\rm Ord}^{\lt\omega})$ forcing that (the definition of) $M$ satisfies $\varphi$. In $L$, we can obviously build a countable $\in$-model $N$ reflecting enough properties of forcing in general and the forcing $\mathbb P(\mathbb J,{\rm Ord}^{\lt\omega})$, in particular, together with the assertion that there is a condition $p$ forcing that $M$ satisfies $\varphi$. Let $L_\alpha$ be the collapse of $N$. Then the model $L_\alpha$ has a forcing $\mathbb Q$, the collapse of $\mathbb P(\mathbb J,{\rm Ord}^{\lt\omega})$, and a condition $q\in \mathbb Q$ forcing that a transitive submodel of the forcing extension satisfies $\varphi$. Let $g\subseteq \mathbb Q$ be some $L_\alpha$-generic filter in $L$. Then $L_\alpha[g]$ really does have a transitive submodel $m$ satisfying $\varphi$. Thus, $L$ has a transitive set $m$ satisfying $\varphi$ and $m$ is obviously in $M$. So as long as we construct our models failing the Reflection principle as inner models of forcing extensions, we don't have much hope of violating the sentence Reflection principle.

References

1. V. Gitman, J. D. Hamkins, and T. A. Johnstone, “What is the theory $\mathsf {ZFC}$ without power set?,” MLQ Math. Log. Q., vol. 62, no. 4-5, pp. 391–406, 2016.
2. A. Zarach, “Unions of ${\rm ZF}^{-}$-models which are themselves ${\rm ZF}^{-}$-models,” in Logic Colloquium ’80 (Prague, 1980), vol. 108, Amsterdam: North-Holland, 1982, pp. 315–342.
3. S.-D. Friedman, V. Gitman, and V. Kanovei, “A model of second-order arithmetic satisfying AC but not DC,” J. Math. Log., vol. 19, no. 1, pp. 1850013, 39, 2019.
4. R. Jensen, “Definable sets of minimal degree,” in Mathematical logic and foundations of set theory (Proc. Internat. Colloq., Jerusalem, 1968), North-Holland, Amsterdam, 1970, pp. 122–128.
5. U. Abraham, “A minimal model for $\neg{\rm CH}$: iteration of Jensen’s reals,” Trans. Amer. Math. Soc., vol. 281, no. 2, pp. 657–674, 1984. Available at: http://dx.doi.org.ezproxy.gc.cuny.edu/10.2307/2000078
6. V. Gitman and R. Matthews, “ZFC without power set II: reflection strikes back,” Fund. Math., vol. 264, no. 2, pp. 149–178, 2024. Available at: https://doi.org/10.4064/fm206-11-2023
7. S. D. Friedman, Fine structure and class forcing, vol. 3. Walter de Gruyter & Co., Berlin, 2000, p. x+221.
8. V. Gitman, “Parameter-free schemes in second-order arithmetic,” To appear in the Journal of Symbolic Logic, 2024.