Corrigendum & Addendum to: Categoricity-like Properties in the First Order Realm
Ali Enayat, Mateusz Łełyk · 2026
Read Corrigendum & Addendum to: Categoricity-like Properties in the First Order Realm by Ali Enayat, Mateusz Łełyk (2026) 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-2603-06711.txt.
Introduction
Ali Enayat and Mateusz Łełyk offer a short note that corrects and extends their earlier work on categoricity-style traits in first-order logic. A corrigendum fixes points in the prior paper, while an addendum adds material that belongs with it. The prior paper appeared in the Journal for the Philosophy of Mathematics in 2024. Readers of that work should read this note with it, since it amends and completes the record.
Catalog record
| CREATOR | Ali Enayat, Mateusz Łełyk |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 23580 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.06711
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Corrigendum & Addendum to: Categoricity-like Properties in the First Order Realm Ali Enayat, Mateusz Łełyk Abstract 1 Introduction This note complements our paper 5 , which we assume the reader has at hand for ready reference. Sections 2 and 3 constitute the "Corrigendum” component; the former repairs the proof of Theorem 39 of 5 , while the latter presents a counterexample to one of the lemmata used in the proof of Theorem 77 of 5 . Section 3 is the "Addendum" component, in which we draw attention to relevant recent advances. 2 Correction to Theorem 39 of 5 The statement of Theorem 39 of 5 is correct, but the proof presented for it suffers from two defects. The more serious defect is that a stronger form of Lemma 40 of 5 is needed for the proof of the theorem to go through; this stronger result is Theorem 3 below; whose part (b) is crucial for the proof of Theorem 39 of 5 . The other defect, detected by Zachiri McKenzie, concerns the quantifier complexity of the axioms of the version of \mathsf{KP} (Kripke-Platek set theory) used in the proof: The correct complexity is \Pi_{3} , and not \Pi_{2} . 1 1 1 With the exception of \mathsf{Coll}(\Delta_{0}) (which is equivalent to \mathsf{Coll}(\Sigma_{1}) in the presence of Kuratowski pairing), all the other axioms of \mathsf{KP} can be expressed as \Pi_{2} -sentences; however, as shown by a recent result of McKenzie ( 13 , Theorem 4.9) , \mathsf{Coll}(\Delta_{0}) cannot even be expressed as set of \Sigma_{3} -sentences. Note that one can use a \Pi_{3} -satisfaction predicate for \Pi_{3} -formulae to show that \mathsf{KP} is axiomatized by a single \Pi_{3} -sentence, but we do not need this refinement here. For the benefit of the reader, the entire corrected proof of the theorem is presented below. Theorem 1 . If \mathsf{ZF} is consistent, then for each n\in\omega the following hold: (a) \mathsf{ZF}_{\Pi_{n}} is not solid. (b) \mathsf{ZF}_{\Pi_{n}} is not tight. Proof. Our proof strategy is similar to the one for Theorem 25 of 5 . Assuming the consistency of \mathsf{ZF} , by Gödel’s second incompleteness theorem, and Gödel’s relative consistency proof of \mathsf{ZF+V=L} , the theory \mathsf{ZF+V=L+\lnot Con_{ZF}} is consistent, and therefore by the arithmetized completeness theorem there is a countable model \mathcal{M}_{0} such that: (1) \mathcal{M}_{0}\models\mathsf{ZF+V=L+\lnot Con_{ZF}} , and (2) The elementary diagram of \mathcal{M}_{0} is definable in \mathbb{N} (the standard model of arithmetic); in particular, there is an interpretation \mathcal{I} such that \mathbb{N}\trianglerighteq^{\mathcal{I}}\mathcal{M}_{0}. As in the arithmetical case, given n\in\omega , let K_{n}(\mathcal{M}_{0}) be the submodel of \mathcal{M}_{0} whose universe consists of elements of \mathcal{M}_{0} that are definable in \mathcal{M}_{0} by a \Sigma_{n} -formula. At the heart of the proof of Theorem 1 is the following result, which is the set-theoretical analogue of Theorem 24 of 5 . Theorem 2 . Let \mathcal{M}_{0} and K_{n}(\mathcal{M}_{0}) be as above. The following statements hold for each n\geq 3 : (a) \mathbb{N} is bi-interpretable with K_{n}(\mathcal{M}_{0}). (b) \mathrm{Th}(\mathbb{N}) is bi-interpretable with \mathrm{Th}(K_{n}(\mathcal{M}_{0})). The proof of part (a) of Theorem 2 is based on Theorem 3 below, which is the set-theoretical analogue of a basic result in the model theory of arithmetic (Theorem 22 of 5 ). The proof of this set-theoretical analogue takes more effort to establish since in the arithmetical case the well-ordering < of the universe has a \Delta_{0} -graph, but in our context we need to rely on technical features of the well-ordering <_{\mathsf{L}} of the constructible universe \mathsf{L} . In part (c) of the theorem below, \mathsf{Coll}(\Sigma_{n+1}) is the collection scheme for \Sigma_{n+1} -formulae of set theory, whose instances are of the form: \left(\forall x\in a\ \exists y\ \sigma(x,y)\right)\rightarrow\left(\exists b\ \forall x\in a\ \exists y\in b~\sigma(x,y)\right), where \sigma is a \Sigma_{n+1} -formula whose parameters are suppressed. Also note that in the statement of the theorem below, \mathsf{ZF^{-}} denotes \mathsf{ZF\setminus\{Powerset\}} . It is well-known that the powerset axiom is not needed for the development of the basic properties of the constructible universe (see, e.g., Section 5 of Chapter II of 2 ). Theorem 3 . The following holds for any model \mathcal{M}\models\mathsf{ZF^{-}+V=L} , where n\geq 3 . 2 2 2 As pointed out by Zachiri McKenzie, in Lemmas 5.15 and 5.19 of 11 , Mathias established an internal version of Theorem 3 within models of certain fragments of \mathsf{ZF+V=L} . (a) K_{n}(\mathcal{M})\prec_{\Pi_{n}}\mathcal{M} , hence K_{n}(\mathcal{M})\models\mathrm{Th}_{\Pi_{n+1}}(\mathcal{M}). (b) K_{n}(K_{n}(\mathcal{M}))=K_{n}(\mathcal{M}) , i.e., every element of K_{n}(\mathcal{M}) is definable in K_{n}(\mathcal{M}) by some \Sigma_{n} -formula. 3 3 3 Note that in contrast with Theorem 22 of 5 , here there is no nonstandardness assumption. (c) K_{n}(\mathcal{M})\models\mathsf{ZF}_{\Pi_{n+1}}+\lnot\mathsf{Coll}(\Sigma_{n+1}). Proof of Theorem 3 . Let n\geq 3 , and \mathcal{M}\models\mathsf{ZF^{-}}+\mathsf{V}=\mathsf{L} . Also, let <_{\mathsf{L}} denote the usual well-ordering of the constructible universe, which is well-known to be definable by a \Sigma_{1} -formula within the theory \mathsf{ZF^{-}}+\mathsf{V}=\mathsf{L} . To show that K_{n}(\mathcal{M})\prec_{\Sigma_{n}}\mathcal{M} , by the Tarski-test for elementarity, and the availability of a \Delta_{0} -definable pairing function (such as Kuratowski’s) for coding finite tuples of elements as a single element, it suffices to show: Claim (\ast) . If c\in K_{n}(\mathcal{M}) , and \mathcal{M}\models\exists x\ \sigma(x,c) for some \Sigma_{n} -formula \sigma(x,y) , then there is some d\in K_{n}(\mathcal{M}) such that \mathcal{M}\models\sigma(c,d). To verify Claim (\ast) , suppose that c\in K_{n}(\mathcal{M}) , and \mathcal{M}\models\exists x\ \sigma(x,c) , where \sigma(x,c)=\exists y\ \pi(x,y,c) and \pi is a \Pi_{n-1} -formula. Thus we have: \mathcal{M}\models\exists x\ \exists y\ \pi(x,y,c). Using the Kuratowski pairing function \left\langle x,y\right\rangle=\{\{x\},\{x,y\}\} , we can write the above as: \mathcal{M}\models\exists z\ \pi(\left(z\right)_{0},\left(z\right)_{1},c)\text{,} where z=\left\langle\left(z\right)_{0},\left(z\right)_{1}\right\rangle . By invoking the fact that <_{\mathsf{L}} well-orders the universe within \mathcal{M} , we can conclude that for some d\in M , \mathcal{M}\models\psi(d,c)\wedge\exists!z\ \psi(z,c) , where: \psi(z,a):=\overset{\psi_{1}(z,c)}{\overbrace{\pi(\left(z\right)_{1},\left(z\right)_{2},c)}}\wedge\overset{\psi_{2}(z,c)}{\overbrace{\forall u<_{\mathsf{L}}z\ \lnot\pi(\left(u\right)_{1},\left(u\right)_{2},c)}}. • We will show that d is \Sigma_{n} -definable in the structure (\mathcal{M},c) by showing that \psi(z,c) is equivalent within \mathcal{M} to a \Sigma_{n} -formula \theta(z,c) with parameter c . This is sufficient to prove Claim (\ast) since we can then take advantage of the assumption that c\in K_{n}(\mathcal{M}) to eliminate the parameter c to obtain a paramater-free \Sigma_{n} -formula \psi^{\ast}(z) that defines d in \mathcal{M} . More specifically: \psi^{\ast}(z):=\exists v\left[\theta(v)\wedge\psi(z,v)\right], where \theta(v) is a \Sigma_{n} -formula that defines c in \mathcal{M} . The first conjunct \psi_{1}(z,c) of \psi(z,c) is equivalent to \exists w_{1}\ \exists w_{2}\ \left[w=\left(z\right)_{1}\wedge w=\left(z\right)_{2}\wedge\pi(\left(z\right)_{1},\left(z\right)_{2},c)\right], since w=\left(z\right)_{i} is a \Delta_{0} -formula for i\in\{0,1\}. By assumption \pi is a \Pi_{n-1} -formula, thus \psi_{1}(z,c) is equivalent in \mathcal{M} to a \Sigma_{n} -formula. Thus the proof will be complete once we verify that the second conjunct \psi_{2}(z,c) of \psi(z,c) is also equivalent to a \Sigma_{n} -formula in \mathcal{M} (with parameter c ). 4 4 4 Note that \psi_{2}(z,c) is readily expressible as \Pi_{n} -formula (when n\geq 3 ) since <_{\mathsf{L}} has a \Sigma_{1} -definition, but this fact does not help us here. Indeed, we will do better by showing that \psi(z,c) is equivalent to a \Sigma_{n-1} -formula in \mathcal{M} (with parameter c ). For this purpose, we need to revisit the specific way that the canonical well-ordering <_{\mathsf{L}} of the constructible universe \mathrm{L} was designed by Gödel. The following two facts are well-known, see pp. 188-190 of Jech’s textbook 10 for an exposition: (1) \mathsf{L:}=\bigcup\limits_{\alpha\in\mathsf{Ord}}L_{\alpha} , and <_{\mathsf{L}}\ :=\bigcup\limits_{\alpha\in\mathsf{Ord}}<_{\alpha} , where <_{\alpha} well-orders L_{\alpha} for each \alpha , and