Characterizing Fragments of Collection in Set Theory by Model-Theoretic Properties

Junhong Chen · 2025

Read Characterizing Fragments of Collection in Set Theory by Model-Theoretic Properties by Junhong Chen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-16901.txt.

Introduction

Junhong Chen wrote this solo 2025 arXiv paper in mathematical logic, comparing two weak theories: one about sets, one about numbers. Weak theories matter because they show how little machinery a proof really needs. The paper studies a set theory with only basic collection strength and shows it can be translated back and forth with a classic weak arithmetic.

The new direction renders sets as finite rooted graphs without cycles, where a matching relation plays the role of equality. Every model of the set theory can also be grown taller, gaining a neat exact cover, much like models of the number theory. Chen then sorts fragments of the collection principle by splitting properties in the style of Gaifman. Two different growth methods are separated, one needing a strict resolution and one not. The work tightens the map of how set theory's weakest floors are built.

Catalog record

CREATORJunhong Chen
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE101 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-16901

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Characterizing Fragments of Collection in Set Theory by Model-Theoretic Properties Junhong Chen Abstract We compare the model theory of the weak set theory 𝖣𝖡 0 \mathsf{DB}_{0} with that of the algebraic theory 𝖯𝖠 − \mathsf{PA}^{-} . Every model of 𝖣𝖡 0 \mathsf{DB}_{0} has a proper taller* end extension with an exact transitive cover, paralleling the corresponding end-extension result for 𝖯𝖠 − \mathsf{PA}^{-} . More substantially, we prove that 𝖣𝖡 0 \mathsf{DB}_{0} and 𝖯𝖠 − \mathsf{PA}^{-} are mutually interpretable. The new direction interprets 𝖣𝖡 0 \mathsf{DB}_{0} in I ​ Δ 0 + Ω 1 I\Delta_{0}+\Omega_{1} by finite rooted acyclic graphs; bisimulation supplies equality, and bounded truth on the graphs supplies Δ 0 \Delta_{0} -Separation. We then characterize fragments of set-theoretic Collection by Gaifman-style splitting and cofinal elementarity. Finally, we separate two end-extension mechanisms. Without a resolution, Kaufmann’s construction characterizes the relevant Collection fragments for countable and locally for ℵ 1 \aleph_{1} -like models. With a strict transitive resolution, Power Set, Infinity, and strong Collection, a finite-strength Keisler–Morley construction gives Σ N \Sigma_{N} -elementary taller* end extensions whose output retains strong Σ N − 2 \Sigma_{N-2} -Collection. The proof is choice-free inside the model and also recovers the classical 𝖹𝖥 \mathsf{ZF} theorem. Keywords: collection; end extension; cofinal extension; Gaifman splitting; interpretability; weak arithmetic; weak set theory 1 Introduction Collection has parallel formulations in arithmetic and set theory. For a formula \varphi , an arithmetic instance has the form \forall v\forall p\bigl(\forall x<p\,\exists y\,\varphi(x,y,v)\longrightarrow\exists q\forall x<p\,\exists y<q\,\varphi(x,y,v)\bigr), whereas the corresponding set-theoretic instance replaces the initial segment p by the members of a set p : \displaystyle\forall v\forall p\bigl( \displaystyle\forall x\in p\,\exists y\,\varphi(x,y,v) \displaystyle\longrightarrow\exists q\forall x\in p\,\exists y\in q\,\varphi(x,y,v)\bigr). This formal analogy raises a structural question: how much of the model theory of weak arithmetic survives when bounded initial segments are replaced by sets? The answer depends sharply on the base theory. In arithmetic, \mathsf{PA}^{-} is an algebraic theory, substantially weaker than the induction theories I\Sigma_{n} , but it already supports robust coding and end-extension arguments. Mathias’s theory \mathsf{DB}_{0} plays a comparable role on the set-theoretic side: it has the elementary rudimentary operations and \Delta_{0} -Separation, but no Infinity, Power Set, Foundation, or Collection [ 13 ] . Gaifman’s splitting theorem says that if \mathcal{M}\preccurlyeq\mathcal{N} are models of \mathsf{PA} , then the substructure whose domain is \operatorname{sup}_{\mathcal{N}}(M)=\{b\in N:\exists a\in M\ (b<a)\} lies elementarily between them [ 5 ] . Kaye, and more recently Kurahashi and Minami, used variants of this property to characterize induction and collection schemes over weak arithmetic [ 9 , 12 ] . The set-theoretic analogue replaces the supremum by the membership hull M^{*}=\{b\in N:\exists a\in M\ (\mathcal{N}\vDash b\in a)\}. We develop corresponding characterizations over \mathsf{DB}_{0} . Strong \Sigma_{n+1} -Collection is exactly the assertion that the membership hull splits every suitable extension at level \Sigma_{n+1} . Ordinary \Sigma_{n+1} -Collection is recovered by combining a lower splitting condition with cofinal elementarity. At all finite levels these results yield the full Gaifman splitting property precisely when full Collection holds. Before turning to splitting, we make the comparison with weak arithmetic precise in two independent ways. First, every \mathsf{PA}^{-} -model and every \mathsf{DB}_{0} -model has a proper end extension satisfying the same base theory. The set-theoretic construction is external and in fact adds an exact transitive cover of the old universe. Second, and more substantially, we prove \mathsf{DB}_{0}\equiv_{\mathrm{int}}\mathsf{PA}^{-}. The difficult direction factors through I\Delta_{0}+\Omega_{1} . Its objects are finite rooted directed acyclic graphs with explicit padding bounds. Equality is bisimulation rather than equality of graph codes. This choice is essential: ordinary Ackermann coding would require the uniform existence of 2^{a} , while \Omega_{1} controls only fixed polynomials in the binary length of the input. Local satisfaction on the graphs then makes every translated \Delta_{0} -Separation instance arithmetically bounded. The final part concerns end extensions. The MacDowell–Specker theorem gives every model of \mathsf{PA} an elementary end extension [ 3 ] . Keisler and Morley proved the set-theoretic analogue for models of \mathsf{ZF} whose ordinals have countable cofinality [ 11 ] , and Kaufmann related partial elementary end extensions of weak set theories to fragments of Collection [ 8 ] . Two mechanisms should be kept separate. Kaufmann’s omitting-types argument needs no resolution and gives the countable, as well as an \aleph_{1} -like local, characterization. The Keisler–Morley construction uses rank stages as a resolution. We replace them by a definable strict transitive resolution and determine one explicit finite base theory sufficient for the construction. If N\geq 6 , the input theory is \mathsf{B}_{N}=\mathsf{DB}_{0}+\mathsf{PowerSet}+\mathsf{Infinity}+\mathsf{Coll}_{s}(\Sigma_{N}), and the resulting \Sigma_{N} -elementary model satisfies \mathsf{B}_{N-2} . The proof uses set-valued Skolem envelopes and the choice-free finite Erdős–Rado argument from Keisler and Morley’s appendix; it does not assume Choice inside the model. Section 2 fixes all common syntactic, interpretability, extension, and resolution terminology. Section 3 compares \mathsf{DB}_{0} with \mathsf{PA}^{-} by end extensions and interpretations. Section 4 proves the Gaifman-style characterizations. Section 5 first treats end extensions without resolutions and then proves the finite-strength Keisler–Morley theorem under a strict transitive resolution. Section 6 records the remaining questions. 2 Preliminaries We work in the language \mathcal{L}_{\in}=\{\in\} , with equality treated as logical. A quantifier is bounded if it has the form \exists x\in y or \forall x\in y . The classes \Delta_{0}=\Sigma_{0}=\Pi_{0} and \Sigma_{n},\Pi_{n} are the usual Levy hierarchy; finite tuples of parameters are allowed. Formula classes are understood up to provable equivalence over the displayed base theory. If \mathcal{M}\subseteq\mathcal{N} , then \mathcal{M}\preccurlyeq_{\Gamma}\mathcal{N} means that the two structures agree on all \Gamma -formulas with parameters from M . We omit the subscript for full elementarity. In the language \mathcal{L}_{\in}(M)=\mathcal{L}_{\in}\cup\{c_{a}:a\in M\} , the elementary diagram \operatorname{ElDiag}(\mathcal{M}) is the set of all sentences true in (\mathcal{M},a)_{a\in M} . We similarly write \operatorname{Diag}_{\Gamma}(\mathcal{M}) for its \Gamma -part. These conventions also fix the meaning of diagram notation used in the compactness arguments below. For theories T and U , we write T\triangleright U when T interprets U in the usual first-order sense: the interpretation may use a definable domain and a definable congruence for equality, followed by passage to the quotient. Fixed finite-dimensional interpretations are identified with one-dimensional interpretations by a standard tuple code. We write T\equiv_{\mathrm{int}}U for mutual interpretability; no definable isomorphism between the two composites and the identity interpretations is implicit in this notation. We use the usual languages for weak arithmetic, up to harmless definitional extensions. The theory \mathsf{Q} is Robinson arithmetic, and \mathsf{PA}^{-} is the theory of the nonnegative parts of discretely ordered commutative semirings. The theory I\Delta_{0} has induction for bounded formulas. If |x| denotes binary length, our version of \Omega_{1} asserts the totality of \omega_{1}(x)=2^{|x|^{2}}. We use the bounded bit predicate \operatorname{Bit}(a,i) and the standard partial relation \operatorname{Pow}_{2}(p,k) for p=2^{k} . These are conservative definitional devices: \operatorname{Pow}_{2}(p,k) can be expressed by a bounded doubling table once an \Omega_{1} bound is supplied. In particular, we never assume that the full exponential function is total. Following [ 13 , 14 , 12 ] , let \mathsf{DB}_{0} consist of Extensionality, Empty Set, Pairing, Union, Cartesian Product, and the \Delta_{0} -Separation scheme. For a formula \varphi(x,y,\bar{v}) , put \displaystyle\mathsf{Coll}_{s}(\varphi):\quad \displaystyle\forall\bar{v}\,\forall p\,\exists q\,\forall x\in p\bigl(\exists y\,\varphi(x,y,\bar{v})\leftrightarrow\exists y\in q\,\varphi(x,y,\bar{v})\bigr), \displaystyle\mathsf{Coll}(\varphi):\quad \displaystyle\forall\bar{v}\,\forall p\bigl(\forall x\in p\,\exists y\,\varphi(x,y,\bar{v})\longrightarrow\exists q\,\forall x\in p\,\exists y\in q\,\varphi(x,y,\bar{v})\bigr), \displaystyle\mathsf{Coll}_{w}(\varphi):\quad \displaystyle\forall\bar{v}\bigl(\forall x\,\exists y\,\varphi(x,y,\bar{v})\longrightarrow\forall p\,\exists q\,\forall x\in

Read the complete text