Reflection principles in set theory without powerset

PDF   Bibtex

V. Gitman, “Reflection principles in set theory without powerset,” Manuscript, 2025.

The Reflection principle is the scheme of assertions that every formula is reflected by a transitive set, namely that for every formula $\varphi(x,a)$, with parameter $a$, there is a transitive set $S$ containing $a$ such that for all $s\in S$, $\varphi(s,a)$ holds if and only if it holds in $S$. The Reflection principle follows from ${\rm ZFC}$, with the witnessing sets being elements of the $V_\alpha$-hierarchy. Given a formula $\varphi$, the reflecting $V_\alpha$ is constructed as the union of a sequence $V_{\alpha_0}\subseteq V_{\alpha_1}\subseteq \cdots V_{\alpha_n}\subseteq\cdots$ of length $\omega$, where each $V_{\alpha_{n+1}}$ is a closure of $V_{\alpha_n}$ under witnesses for all existential sub-formulas of $\varphi$, and so reflects $\varphi$ by the Tarski-Vaught test. Since the argument uses only the existence of the $V_\alpha$-hierarchy together with Replacement to verify that desired $\alpha$ exists, it goes through in ${\rm ZF}$ as well.

The definition of the $V_\alpha$-hierarchy requires the existence of powersets, so it is natural to ask whether the Reflection principle continues to hold in set theories without powersets. Since some naturally equivalent versions of the ${\rm ZFC}$ axioms stop being equivalent once the Powerset axiom is removed, we end up with several versions of set theory without powersets. Without the Powerset axiom, the Replacement and Collection schemes are no longer equivalent and neither are the versions of the Axiom of Choice which we use interchangeably [1]. For instance, ${\rm ZFC}$ without the Powerset axiom, with the Collection scheme instead of Replacement, although it has ${\rm AC}$, does not imply that every set can be well-ordered. Let ${\rm ZFC}-$ be the theory consisting of the axioms of ${\rm ZFC}$ (with Replacement) and the assertion that every set can be well-ordered. The theory ${\rm ZFC}-$ exhibits many undesirable behaviors. It can have models in which $\omega_1$ is a countable union of countably many sets, in which $\omega_1$ exists, but every set of reals is countable, or where the Łoś theorem can fail for ultrapowers [2]. All these issues can be eliminated by instead taking the theory ${\rm ZFC}^-$, where we replace the Replacement scheme with Collection, suggesting that this is the more natural version of set theory without powersets. The most common set-theoretic structures encountered by set theorists in which the Powerset axiom fails are $H_{\kappa^+}$, the collection of all sets whose transitive closure has size at most $\kappa,$ and these indeed satisfy ${\rm ZFC}^-$.

The Reflection principle clearly implies Collection over the other axioms of ${\rm ZFC}^-$. In ${\rm ZFC}^-$, every set can be closed under witnesses for existential sub-formulas of a given formula, but after that it appears that some class version of dependent choice is required to iterate this construction $\omega$-many times. Recall that the ${\rm DC}_\omega$-scheme is the class version of dependent choice which asserts that we can make $\omega$-many dependent choices along any definable relation without terminal nodes. More formally, the ${\rm DC}_\omega$-scheme is a scheme of assertions for every formula $\varphi(x,y,a)$, with parameter $a$, that if for every $x$, there is $y$ such that $\varphi(x,y,a)$ holds, then there is a sequence $\{b_n\mid n\lt\omega\}$ such that for every $n\lt\omega$, $\varphi(b_n,b_{n+1},a)$ holds. (In a personal communication, Freund has observed that over the axioms ${\rm ZFC}^-$ without Collection, the ${\rm DC}_\omega$-scheme is equivalent to the principle of induction along definable well-founded relations.) It is easy to see that ${\rm ZFC}^-$ together with the ${\rm DC}_\omega$-scheme imply the Reflection principle and indeed ${\rm ZFC}^-$ together with the Reflection principle imply the ${\rm DC}_\omega$-scheme because we can reflect the relation and the assertion that it has no terminal nodes to a transitive set and then use ${\rm AC}$ to construct the sequence of dependent choices. It is shown in [3] that the theory ${\rm ZFC}^-$ does not prove the ${\rm DC}_\omega$-scheme, and so it does not prove the Reflection principle.

In this article, we consider a family of partial Reflection principles and examine their status in models of ${\rm ZFC}^-$. Given a set or class $A$, let the partial Reflection Principle for $A$ be the scheme of assertions for every formula $\varphi(a)$, with parameter $a\in A$, that if $\varphi(a)$ holds, then it holds in some transitive set. We will abbreviate the partial Reflection principle for $V$, where any set can be used as a parameter, as just the partial Reflection principle and at the other extreme, we will also call the partial Reflection principle for $\emptyset$, where no parameters are allowed, the parameter-free Reflection principle. Note that if we remove the requirement of transitivity from the parameter-free Reflection principle, then it is provable in ${\rm ZFC}^-$ by standard proof-theoretic arguments. Freund considered some partial Reflection principles in [4]. He showed that, over the axioms of ${\rm ZFC}^-$ without Collection, the parameter-free Reflection principle is equivalent to the principle of induction along $\Delta_1$-definable well-founded relations and that the partial Reflection principle for $\mathbb R$ is equivalent to the principle of induction along $\Delta_1$-definable with real parameters well-founded relations [4]. Partial reflection in the context of Zermelo set theory was studied by Lévy and Vaught, who showed that Zermelo set theory together with the partial Reflection principle do not imply Replacement [5]. More recently, Bokai Yao studied the partial Reflection principle in set theories with urelements [6].

Models of ${\rm ZFC}^-$ in which the ${\rm DC}_\omega$-scheme fails, being the only candidates in which the partial Reflection principles can fail, are notoriously hard to construct. There are currently only two known models of ${\rm ZFC}^-$ in which the ${\rm DC}_\omega$-scheme fails. Both are constructed as submodels 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. The poset $\mathbb J$ has the ccc and adds a unique generic real that is $\Pi^1_2$-definable as a singleton [7]. In $L$, we can appropriately define finite iterations $\mathbb J_n$ of $\mathbb J$ of length $n$. These also have the ccc and add a unique $n$-length generic sequence of reals that is $\Pi_2^1$-definable (see [8] and [3]). Again working in $L$, given a set or class tree $T$ of height $\omega$, a tree iteration $\mathbb P(\mathbb J,T)$ of $\mathbb J$ along $T$ is a poset whose elements are functions $p$ from a finite subtree $D_p$ of $T$ to $\bigcup_{n\lt\omega}\mathbb J_n$ such that if $t$ is a node on level $n$ of $D_p$, then $p(t)\in \mathbb J_n$ and whenever $s\leq t$ in $T$, then $p(s)=p(t)\upharpoonright \text{len}(s)$. The functions $p$ are ordered so that $q\leq p$ whenever $D_p\subseteq D_q$ and for every $t\in D_p$, $q(t)\leq p(t)$. An $L$-generic $G\subseteq \mathbb P(\mathbb J,T)$ adds a tree $T^G$ isomorphic to $T$ whose nodes on level $n$ are generic $n$-length sequences for $\mathbb J_n$ and the sequences extend according to the tree order. For certain sufficiently homogeneous trees, such as $T=\omega^{\lt\omega}$ or $T=\omega_1^{\lt\omega}$, the forcing $\mathbb P(\mathbb J,T)$ has the ccc and the uniqueness of generics property that the only $L$-generic filters for $\mathbb J_n$ in $L[G]$ are the nodes of $T^G$ on level $n$. Also, the collection of all $n$-generic sequences for $\mathbb J_n$ over all $n\lt\omega$, namely the elements of $T^G$, is $\Pi^1_2$-definable [3]. The class forcing $\mathbb P(\mathbb J,{\rm Ord}^{\lt\omega})$ along the class tree ${\rm Ord}^{\lt\omega}$ has all the same properties as well [9]. Since the forcing $\mathbb P(\mathbb J,{\rm Ord}^{\lt\omega})$ has the ccc, it is easily seen to be pretame. It follows that the forcing relation for $\mathbb P(\mathbb J,{\rm Ord}^{\lt\omega})$ is definable and the forcing extension satisfies ${\rm ZFC}^-$ [10]. The extension has all the same cardinals as $L$, but since we added class many reals, powerset of $\omega$ does not exist. The first model of ${\rm ZFC}^-$ in which the ${\rm DC}_\omega$-scheme fails is constructed in a forcing extension $L[g]$ by $\mathbb P(\mathbb J,\omega_1^{\lt\omega})$ as the $H_{\omega_1}$ of an appropriately chosen symmetric submodel $N$ satisfying ${\rm ZF}+{\rm AC}_\omega$ [3]. We will refer to $H_{\omega_1}^N$ as $M_{\rm{small}}^g$. The second model of ${\rm ZFC}^-$ in which the ${\rm DC}_\omega$-scheme fails is constructed as a submodel of a forcing extension $L[G]$ by $\mathbb P(\mathbb J,{\rm Ord}^{\lt\omega})$ [9]. Given a set subtree $T$ of ${\rm Ord}^{\lt\omega}$, let $G_T$ be the restriction of $G$ to $\mathbb P(\mathbb J,T)$, which is easily seen to be $L$-generic for it. In $L[G]$, we let $N$ be the union of $L[G_T]$, where $T$ is a well-founded set subtree of ${\rm Ord}^{\lt\omega}$. It is shown in [9] that $N$ satisfies ${\rm ZFC}^-$, but the ${\rm DC}_\omega$-scheme fails. We will refer to the model $N$ as $M_{\rm{large}}^G$.

In this article, we show:

Theorem: Suppose $g\subseteq \mathbb P(\mathbb J,\omega_1^{\lt\omega})$ and $G\subseteq \mathbb P(\mathbb J,{\rm Ord}^{\lt\omega})$ are $L$-generic.

  1. The partial Reflection principle holds in $M_{\rm{small}}^g$.
  2. The partial Reflection principle for $\{\omega_1\}$ fails in $M_{\rm{large}}^G$. Consequently, the partial Reflection principle fails in $M_{\rm {large}}^G$.
  3. The partial Reflection principle for $\mathbb R$ holds in $M_{\rm{large}}^G$. Consequently, the parameter-free Reflection principle holds in $M_{\rm{large}}^G$.

Corollary: Over ${\rm ZFC}^-$, the Reflection principle is not equivalent to the partial Reflection principle.

Corollary: Over ${\rm ZFC}^-$, the partial Reflection principle is not equivalent to the partial Reflection principle for $\mathbb R$.

References

  1. 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.
  2. 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.
  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. A. Freund, “Set-theoretic reflection is equivalent to induction over well-founded classes,” Proc. Amer. Math. Soc., vol. 148, no. 10, pp. 4503–4515, 2020. Available at: https://doi.org/10.1090/proc/15103
  5. A. Lévy and R. Vaught, “Principles of partial reflection in the set theories of Zermelo and Ackermann,” Pacific J. Math., vol. 11, pp. 1045–1062, 1961. Available at: http://projecteuclid.org/euclid.pjm/1103037137
  6. B. Yao, “Axiomatization and Forcing in Set Theory with Urelements,” To appear in the Journal of Symbolic Logic, 2024.
  7. 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.
  8. 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
  9. 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
  10. S. D. Friedman, Fine structure and class forcing, vol. 3. Walter de Gruyter & Co., Berlin, 2000, p. x+221.