betaFeedback

WorksMathematics

Loose Inductive Set Theories

Abstract

We prove that KP, with Full Set Induction, is neither solid nor tight. More generally, every consistent theory obtained from KPC by adding a quantifier bounded set of sentences has a model with a parameter-free definable class surjection from its natural numbers onto its universe. Using such enumerations to define generic extensions by relative interpretations, we show that theories with the stable definable ground property are not tight. Ground definability over MOST and continuum coding over ZFC^{Π_3} yield applications to weak inductive set theories with large cardinals and forcing axioms. Finally, solidity for quantifier bounded extensions of MOST with Full Set Induction implies a Ground Axiom formulated using a fixed finite level of genericity; under the same solidity hypothesis, the corresponding extension of full ZFC proves the ordinary Ground Axiom.

We thank Ali Enayat and Farmer Schlutzenberg for helpful comments and correspondence, especially concerning the results on theories of bounded-complexity consequences.

Contents

  1. Background definitions 4

  1. KPKP is neither solid nor tight 5

2.1. Solidity failure 5

2.2. Tightness failure 13

2.3. Some generalizations 16

  1. Quantifier bounded theories generally aren’t tight 19

  1. The Definable Countable Enumeration Lemma 21

4.1. Tableau proof systems: building models by approximation 22

4.2. Modifying the tableaux 24

4.3. Building models 29

4.4. Main proof 37

  1. Geology with little hammers 37

5.1. Ground model definability in a weak set theory 39

5.2. A uniquely definable ground theorem 43

  1. Applications 49

6.1. Large cardinals beyond LL and other extensions 49

6.2. The inexpressibility of V=HODV = HOD in quantifier bounded set theories 54

6.3. Solidity and the ground axiom 54

References 58

It’s well known that no theory with an infinite model that is articulated in first order logic can be categorical: compactness says there will always be a bigger model. However, in recent years logicians have studied a number of properties that a theory can possess which appear to, in some sense, approximate categoricity [8]. As a rule of thumb, the kinds of theories that have categoricity proofs in second order logic tend to satisfy these properties when they are converted into first order theories using schematic techniques. For example, the second-order versions of PA\mathit{PA} and ZFC\mathit{ZFC} are respectively categorical and quasi-categorical,1 and both PA\mathit{PA} and ZFC\mathit{ZFC} possess these new properties [35, 7].

Our broad goal in this paper is to investigate set theories that only use bounded versions of the Separation, Collection and Replacement schemas while remaining fully inductive in the sense that they satisfy the Full Set Induction schema; i.e., any definable nonempty class has an ∈\in-minimal element. The main upshot of this paper is that these approximate categoricity properties fail for broad classes of such theories. This places our results in the program of identifying natural set and class theories that fail to be tight or solid. Freire and Hamkins [2020] showed that Zermelo set theory and ZFC\mathit{ZFC} without Powerset are not tight. Freire and Williams [2025] established corresponding failures for fragments of Kelley-Morse set theory and second-order arithmetic.

This paper extends results of Enayat and Lelyk [2024]. In particular, they show that for any n∈ωn \in\omega, the Πn\Pi_n-consequences of ZF\mathit{ZF} are neither solid nor tight.2 The results of this paper improve this in two directions. First, we include Full Set Induction in our theories. Second, we do not limit ourselves to sub-theories of ZF\mathit{ZF}, but rather, show that an open ended collection of theories extending a weak base theory are neither solid nor tight. In particular, we will show that for a natural class of these theories, solidity implies that the theory proves a version of the Ground Axiom.

Aside from the main results, this paper makes use of a couple of strange techniques that are worth discussing. First, we show that some models of these bounded theories are capable of defining generics over their posets and the generic extensions based on those generics.3 This runs counter to the orthodox pedagogy of set theory where one learns that generic sets must exist outside their models and thus, generic extensions are not within the purview of relative interpretation. The key to this counterintuitive approach is the ability to find models of these bounded theories that are able to see that they are countable, in the sense that they can define a surjection from the natural numbers onto their entire domain. For sub-theories of ZF\mathit{ZF}, we can exploit well known fine-structural results to obtain such enumerations in models of V=LV=L using the natural well-ordering of LL.4 But for theories incompatible with LL this technique is not available. As such, we prove a very general lemma showing that our bounded theories are always consistent with the existence of a definable countable enumeration of the universe. This is the most novel result of the paper and, as such, it takes up the most space.

The paper is divided up as follows. In the next section we give proper definitions of our target properties and explain why they are interesting. In Section 2, we show that KP\mathit{KP} satisfies neither of these properties. To achieve this, we develop the theory of definable forcing over Lω1CKL_{\omega_1^{CK}} and then generalize this further. Aside from the fact that KPKP is a theory of obvious foundational interest, this setting provides a convenient location to explain the underlying ideas of the paper in a setting that is likely to be familiar to its readers. Section 3 then provides the framework for a substantial generalization of these results to theories that are bounded extensions of a weak sub-theory of ZFCZFC that includes Full Set Induction. This gives us a theorem template (Theorem 31) that allows us to show that when such theories possess a crucial property (Definition 29) they can never be tight. The theorem template is then demonstrated on the basis of a lemma that we prove in the following section. The Definable Countable Enumeration Lemma (Lemma 30) is then proved in Section 4. This is the most original and unusual contribution of the paper. In order to set up for applications of this template, we need tools from set-theoretic geology. Section 5 starts from Schlutzenberg’s ground-model definability theorem over the weak theory MOSTMOST [Schlutzenberg, 2022].5 We adapt it to use a smaller parameter and then code that parameter into the continuum function, so that the ground can be recovered without parameters. The small-parameter argument works over MOSTMOST; the coding construction is carried out over ZFCΠ3ZFC\Pi_3. Finally, in Section 6, we bring these results to bear on a variety of natural examples.

Background definitions

Let us start by introducing the property of tightness.

Definition 1. [7] Say that a theory TT is tight if any pair of bi-interpretable extensions of TT are the same theory (in the sense that they have the same deductive closure).

Informally, a theory is tight if it cannot be extended in distinct, but equivalent ways. To get more of a feel for this, let’s contrast a non-tight theory with a tight one. For a non-tight theory, let Empty be the empty theory of binary relations articulated in LEmpty={R}\mathcal{L}_{Empty}=\{R\}. Now consider the extensions S0S_0 and S1S_1 of Empty that say that RR is, respectively, reflexive and irreflexive. S0S_0 and S1S_1 are clearly bi-interpretable, indeed, they are definitionally equivalent. From a graph theoretic perspective, we add loops in one direction and remove the loops in the other direction. But they are not the same theory. We might say that Empty is, unsurprisingly, insufficiently specific to be tight.

For a contrast, we observe that PAPA is tight [35]. So PAPA appears to be more specific than Empty. To make more sense of this, let’s try to pull on some intuitions. We know that PAPA has an intended model, N=⟨ω,0,s,+,×⟩\mathbb{N}=\langle\omega,0,s,+,\times\rangle, and we also know that PAPA is incomplete, so PA⊈Th(N)PA\nsubseteq Th(\mathbb{N}). Now imagine, for a moment, that PAPA was not tight and that this was witnessed by another theory S⊇PAS\supseteq PA that was bi-interpretable with Th(N)Th(\mathbb{N}). This would be a strange situation. Since SS would be distinct from Th(N)Th(\mathbb{N}), we’d have another way of understanding 0,s,+,×0,s,+,\times that was distinct from the standard interpretation and yet still satisfied the axioms of PAPA. There would, thus, be an arithmetic sentence true in one interpretation and false in the other; and little, if any, good reason to choose between them. Such a situation would attest to a different kind of incompleteness in PAPA. Fortunately, we know this cannot occur. Indeed, we don’t need to go as far as the true theory of arithmetic. Any pair of bi-interpretable extensions of PAPA, true or not, must determine the same theory.

Solidity is a more technical notion that was uncovered by Enayat in an effort to identify the model theoretic core of tightness.

Definition 2. [7] A theory TT is solid if for all models M0,N\mathcal{M}_0,\mathcal{N} and M1\mathcal{M}_1 of TT, whenever we have

M0▹parN▹parM1\mathcal{M}_0 \triangleright_{\mathrm{par}} \mathcal{N} \triangleright_{\mathrm{par}} \mathcal{M}_1

and an isomorphism f:M0≅M1f:\mathcal{M}_0 \cong\mathcal{M}_1 that is (parametrically) definable over M0\mathcal{M}_0, then there is another isomorphism g:M0≅Ng:\mathcal{M}_0 \cong\mathcal{N} that is (parametrically) definable over M0\mathcal{M}_0.

It is not difficult to show that a solid theory must be tight.6 Indeed, proving solidity is the main pathway to establishing the tightness of a theory. However, the definition can also be given a more familiar mathematical gloss. The definition above is nicely understood as taking place in the class, mod⁡(T)\operatorname{mod}(T), of models of TT. The antecedent clauses of the definition require that M0\mathcal{M}_0 and M1\mathcal{M}_1 are “visibly” isomorphic to each other. Given this, we might as well treat them as “identical.” The arrangement of M0,N\mathcal{M}_0,\mathcal{N} and M1\mathcal{M}_1 then tells us that there is a way of interpreting a model N\mathcal{N} in M0\mathcal{M}_0 from which we can then interpret M0\mathcal{M}_0 (up to isomorphism) again. We thus, have a kind of structure preserving map, known as a retraction, from M0\mathcal{M}_0 to N\mathcal{N}. It preserves structure in the sense that M0\mathcal{M}_0 can still be recovered from N\mathcal{N} (up to isomorphism). Solidity then addresses whether such maps can be non-trivial; i.e., is the output, N\mathcal{N}, distinct from the input, M0\mathcal{M}_0 (up to isomorphism). If we can find an arrangement of models of TT where the output is distinct (up to isomorphism), TT is not solid. Thus, intuitively speaking, solidity tells us that mod⁡(T)\operatorname{mod}(T) has no non-trivial structure preserving self-interpretations.

KP is neither solid nor tight

Let’s move to our first batch of results. Let KPKP be the Kripke-Platek set theory using Full Set Induction.7 Our target theorem is the following.

Theorem 3. KPKP is neither solid nor tight.

Since solidity implies tightness, it would suffice for us to merely show that KPKP is not tight. However, given that the techniques used below are a little unorthodox, we have opted to give a detailed proof that KPKP is not solid first. Then we adapt that proof to the more general claim that KPKP is not tight. We think this will be helpful as the proof that KPKP is not solid takes place in the familiar world of the hyperarithmetic sets. By taking our time here and building some intuitions, we believe this will make things much easier for the rest of the paper. There are also techniques developed here that will be useful for the investigation of solidity (independent of tightness).

Solidity failure

We start by sketching the idea of the proof. Recall that Lω1CKL_{\omega_1^{CK}} is the smallest model of KPKP in the sense that it is the intersection of all ω\omega-models of that theory. To save a little clutter, let’s write NN instead of Lω1CKL_{\omega_1^{CK}}. We plan to show that NN can define a sufficiently generic Cohen real cc and, using that, a version of the corresponding generic extension, N[c]N[c]. Thus, it can be seen that we have

N▹N[c]▹LN[c].N \triangleright N[c] \triangleright L^{N[c]}.

Moreover, we shall ensure that NN is able to define an isomorphism η:N≅LN[c]\eta: N \cong L^{N[c]}, while, of course, N≇N[c]N \not\cong N[c]. Thus, we shall see that KPKP is not solid.

This ability to define a generic is a little unusual and warrants some discussion about what that means and how it will be done. First, observe that c⊆ωc \subseteq\omega must be defined as a proper class over NN rather than a set. Otherwise, we’d fall into the standard contradiction where the complement of the generic filter associated with cc is a dense set missed by the filter. Second, we note that in order to ensure this, the complexity of the definition of cc must be greater than that of the underlying Separation Axiom. To see this, note that in the presence of the full axiom of Separation, if cc is definable then it can be separated as a subset of ω\omega. Fortunately, we only have Δ1\Delta_1-Separation available in NN. Thirdly, in order to obtain a generic we wish to follow the standard Baire-Category strategy. As such, we want the dense sets of Add(ω,1)Add(\omega,1) to be definably countable so that we can run a version of the standard inductive argument. This rules out theories that satisfy full Replacement. Fortunately, we only have Σ1\Sigma_1-Collection in NN. Fourth and finally, note that in order for N[c]N[c] to satisfy KPKP, and in particular, Σ1\Sigma_1-Collection, an ordinary generic filter meeting all dense subsets of Add(ω,1)Add(\omega,1) that are elements of NN will not suffice.8 We shall thus introduce a stronger notion of genericity.

With the sketch complete, let us fix our convention for measuring the complexity of formulae. We use prenex formulae: all quantifiers are at the front, followed by a quantifier-free formula. We count alternating blocks of quantifiers, bounded or unbounded, as far as the last unbounded quantifier; any bounded quantifiers after it do not contribute to the count. Thus ∀x∃y∈z∀w ψ\forall x\exists y \in z\forall w\ \psi, with ψ\psi bounded, is Π3\Pi_3. A formula with only bounded quantifiers is Δ0\Delta_0. When obtaining a prenex formula, we first expand bounded quantifiers with their usual restrictions as necessary and then use ordinary logical equivalences. This respects empty bounds and requires no Collection. The classes Σk\Sigma_k and Πk\Pi_k below use this convention, with harmless padding by unused quantifiers allowed.

Let us say that a formula is BΣkB\Sigma_k if it is a finite Boolean combination of Σk\Sigma_k formulae. A subset of NN is BΣkB\Sigma_k if it is definable by such a formula, possibly using parameters from NN. Since this paper is focused on interpretability and thus on definability without parameters, whenever we say that an object is definable, we mean definable without parameters; we shall always say when parameters are required.

Definition 4. Let P\mathbb{P} be a poset. We say that G⊆PG \subseteq\mathbb{P} is BΣkB\Sigma_k-generic over NN if GG is a filter on P\mathbb{P} and for all BΣkB\Sigma_k dense subsets DD of P\mathbb{P}, G∩D≠∅G \cap D \ne\varnothing.

We adopt the common assumption that forcing posets have a greatest condition, which we denote as 11. We assume that ⊩\Vdash is the syntactic forcing relation used in [21]. Note that we cannot uniformly define the forcing relation for arbitrary formulae, since this would contradict Tarski’s theorem. For bounded formulae, forcing is uniformly Δ1\Delta_1-definable over KPKP. For higher formulae, we shall use a uniform finite bound. For k∈ωk \in\omega, let

b(k)=2k+3.b(k)=2k+3.

For each fixed kk, forcing for BΣkB\Sigma_k formulae is uniformly Δb(k)\Delta_{b(k)}-definable over KPKP. The definition is uniform in the formula code, the tuple of names, the condition and the forcing poset. We prove this bound below, after recalling the density lemma. The bound is chosen for convenience; we do not claim that it is optimal.

Using a suitably generic G⊆PG \subseteq\mathbb{P}, we can then define a generic extension of the ground model. However, given that our eventual goal is to use a definable generic and interpret the generic extension, we cannot use the familiar ValVal function since that construction would try (and fail) to collapse the generic extension in the ground model. As such, we shall use something like an ultrapower construction that interprets our generic extension as a pre-structure. Thus, we have a structure where the identity relation symbol, ==, is interpreted as the congruence relation ≈∗\approx^{*}.

Definition 5. For G⊆PG \subseteq\mathbb{P}, let NP/G=⟨N∗,∈∗,≈∗⟩\mathbb{N}^{\mathbb{P}}/G = \langle N^{*}, \in^{*}, \approx^{*}\rangle where:

  • N∗=NPN^{*} = N^{\mathbb{P}};

  • x˙∈∗y˙\dot{x} \in^{*} \dot{y} iff ∃p∈G p⊩x˙∈y˙\exists p \in G\ p \Vdash\dot{x} \in\dot{y}, for all x˙,y˙∈NP\dot{x},\dot{y} \in N^{\mathbb{P}}; and

  • x˙≈∗y˙\dot{x} \approx^{*} \dot{y} iff ∃p∈G p⊩x˙=y˙\exists p \in G\ p \Vdash\dot{x} = \dot{y}, for all x˙,y˙∈NP\dot{x},\dot{y} \in N^{\mathbb{P}}.

Note that ≈∗\approx^{*} is an equivalence relation that is a congruence for ∈∗\in^{*}.

Given that NN satisfies V=LV = L, we could also define this as a genuine structure by using LL-least witnesses. However, for our purposes this is more trouble than it’s worth. Observe that if we have such a GG definable over NN without parameters, then N∗N^{*}, ∈∗\in^{*} and ≈∗\approx^{*} are also all definable without parameters over NN. We may then prove a version of the truth lemma for BΣkB\Sigma_k formulae using a BΣb(k)B\Sigma_{b(k)}-generic filter. First we recall a standard, but very useful, fact about syntactic forcing.

Fact 6. Let φ\varphi be a fixed formula for which the syntactic forcing relation has been defined. Then KPKP proves, for every forcing poset P\mathbb{P} and every p∈Pp \in\mathbb{P}, that the following are equivalent:9

  1. p⊩φp \Vdash\varphi; and

  2. {q∈P∣q⊩φ}\{q \in\mathbb{P} \mid q \Vdash\varphi\} is dense below pp.

Lemma 7. (Uniform forcing bound.) For each fixed k∈ωk \in\omega, forcing for BΣkB\Sigma_k formulae is uniformly Δb(k)\Delta_{b(k)}-definable over KPKP. For bounded formulae alone, the uniform bound is Δ1\Delta_1.

References

  1. [1]Jon Barwise. Admissible Sets and Structures. Springer-Verlag, Berlin, 1975.
  2. [2]James E. Baumgartner. Applications of the proper forcing axiom. In Kenneth Kunen and Jerry E. Vaughan, editors, Handbook of Set-Theoretic Topology, pages 913–959. North-Holland, Amsterdam, 1984.DOI
  3. [3]J.L. Bell. Set Theory: Boolean-Valued Models and Independence Proofs. Clarendon Press, 2005.
  4. [5]Sean D. Cox. Forcing axioms, approachability, and stationary set reflection. Journal of Symbolic Logic, 86(2):499–530, 2021. doi: 10.1017/jsl.2020.4.DOI
  5. [6]Keith J. Devlin. Constructibility. Springer-Verlag, Berlin, 1984.
  6. [7]Ali Enayat. Variations on a Visserian theme. In Jan van Eijck, Rosalie Iemhoff, and Joost J. Joosten, editors, Liber Amicorum Alberti: a tribute to Albert Visser, pages 99–110. College Publications, 2016.arxiv.org/abs/1702.07093
  7. [8]Ali Enayat and Mateusz Lelyk. Categoricity-like properties in the first order realm. Journal for the Philosophy of Mathematics, 1:63–98, Sep. 2024.DOI
  8. [10]Matthew Foreman, Menachem Magidor, and Saharon Shelah. Martin’s Maximum, saturated ideals, and nonregular ultrafilters. Part I. Annals of Mathematics, 127(1):1–47, 1988. doi: 10.2307/1971415.
  9. [14]Noam Greenberg and Benoit Monin. Higher randomness and genericity. Forum of Mathematics, Sigma, 5:1–41, 2017.DOI
  10. [15]Joel David Hamkins. Extensions with the approximation and cover properties have no new large cardinals. Fundamenta Mathematicae, 180(3):257–277, 2003.DOI
  11. [18]Bernhard König and Yasuo Yoshinobu. Fragments of Martin’s Maximum in generic extensions. Mathematical Logic Quarterly, 50(3):297–302, 2004. doi: 10.1002/malq.200410101.DOI
  12. [19]Jan Kruschewski and Farmer Schultzenberg. On a conjecture regarding the mouse order for weasels. The Journal of Symbolic Logic, 90(1):364–390, 2025.DOI
  13. [20]Kenneth Kunen. Set Theory: an introduction to independence proofs. Elsevier, Sydney, 2006.
  14. [21]Kenneth Kunen. Set Theory. College Publications, London, 2nd edition, 2011.
  15. [22]Paul Larson. Separating stationary reflection principles. Journal of Symbolic Logic, 65(1):247–258, 2000. doi: 10.2307/2586534.DOI
  16. [24]R. Mansfield and G. Weitkamp. Recursive aspects of descriptive set theory. Oxford logic guides. Oxford University Press, 1985.
  17. [25]A.R.D. Mathias. The strength of Mac Lane set theory. Annals of Pure and Applied Logic, 110(1):107–234, 2001.DOI
  18. [26]Toby Meadows. Revising carnap’s semantic conception of modality. Studia Logica, 100(3):497–515, 2012.DOI
  19. [27]Wolfram Pohlers. Proof Theory: The First Step into Impredicativity. Springer, Berlin, 2009.DOI
  20. [28]Graham Priest. An Introduction to Non-Classical Logic: From If to Is. Cambridge University Press, Melbourne, 2008.DOI
  21. [30]Greg Restall. Logic: an introduction. Routledge, New York, 2006.
  22. [32]Stewart Shapiro. Foundations without Foundationalism: a case for second order logic. OUP, Oxford, 1991.
  23. [33]Raymond M. Smullyan. First-Order Logic. Dover, New York, 1968.
  24. [34]Sue Toledo. Tableau Systems for First Order Number Theory and Certain Higher Order Theories. Springer-Verlag, Berlin, 1975.DOI
  25. [35]Albert Visser. Categories of theories and interpretations. In Ali Enayat, Iraj Kalantari, and Mojtaba Moniri, editors, Logic in Tehran. Proceedings of the workshop and conference on Logic, Algebra and Arithmetic, held October 18-22, 2003, volume 26, pages 284–341. ASL, Wellesley, Mass., 2006.

Paper details

vlnc:W_7w6j56vp
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents