Existential completions and Herbrand’s theorem

Joshua L. Wrigley · 2025

Read Existential completions and Herbrand’s theorem by Joshua L. Wrigley (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-2508-15518.txt.

Introduction

Joshua L Wrigley gives a leaner proof of Herbrand's theorem, a classic result in logic. The theorem links what can be proved about existence claims to concrete witness terms. A recent proof built a completion that adds both kinds of quantifiers to a logic system at once. His 2025 paper shows that adding only the existential kind is enough. He builds that free completion on a presheaf of distributive lattices, a structure that tracks logic across contexts.

From the explicit build, Herbrand's theorem for coherent logic drops out directly. Wrigley also treats two related settings handled by Trotta, where the base structures are weaker. The paper is a technical note with a clear payoff: a simpler route to a theorem that automated reasoning still uses.

Catalog record

CREATORJoshua L. Wrigley
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE86 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-15518

Browse the full library · About the Tower of Babel

Full text

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

Existential completions and Herbrand’s theorem This work has its origin in a question I asked Marco Abbadini at his talk at the Logic Colloquium 2025. I thank Marco for his stimulating talk as well as the conference organisers for the wonderful event. I acknowledge the support of Agence Nationale de la Recherche project ANR-23-CE48-0012-01. Joshua L. Wrigley Abstract Recently, Abbadini and Guffanti gave an algebraic proof of Herbrand’s theorem using a completion for Lawvere doctrines that freely adds existential and universal quantifiers. A more direct argument can be given by only completing with respect to existential quantifiers. We construct the free existential completion on a presheaf of distributive lattices, and deduce Herbrand’s theorem for coherent logic from the explicit description. We also discuss the cases involving presheaves of meet-semilattices, due to Trotta, and presheaves of frames. \mathrmdef Hom \mathbfdef Set keywords existential completion, doctrine, Herbrand’s theorem AMS 18C10 (Primary), 03G30, 08B20 (Secondary) † † address: Université Paris Cité, CNRS, IRIF, F-75013, Paris, France. † † email: [email protected] Introduction Background A classical result in proof theory, Herbrand’s theorem [ 14 ] , asserts that a universal first-order theory, i.e. one whose axioms avoid any use of existential quantification, can only admit ‘constructive proofs’ of existential statements. That is to say, if a universal (classical) theory \mathbb{T} proves that \top\vdash\exists x.\,\varphi(x) , where \varphi(x) is a quantifier-free formula, then there are a finite number of closed terms t_{1},\dots,t_{n} that witness the formula \varphi(x) , i.e. \mathbb{T} proves \top\vdash\varphi(t_{1})\lor\dots\lor\varphi(t_{n}) (in [ 4 , §2] , this is called the weak form of Herbrand’s theorem, but it is the only version we will consider in this paper). Most textbook accounts of Herbrand’s theorem employ cut elimination (see [ 5 , §2.5.1] for instance), a modern technique that was not available when Herbrand first proved the result. In a recent work [ 1 ] , Abbadini and Guffanti give an algebraic proof of Herbrand’s theorem phrased in the language of Lawvere doctrines . Doctrines à la Lawvere, introduced in [ 21 , 22 ] , are a predicate generalisation of the familiar Lindenbaum-Tarski algebras from propositional logic, an alternative to the polyadic algebras of Halmos [ 12 ] and the cylindric algebras of Tarski [ 13 ] . A recurring topic within doctrine theory is the study of completions : universally adding richer structure to the doctrine. For example, the quotient completion of a doctrine has been extensively studied [ 24 , 25 , 26 , 27 , 10 ] , paralleling the category-theoretic exact completion [ 7 , 9 , 8 ] and the ‘tripos-to-topos’ construction found in [ 15 , 28 , 29 ] . Recently, more focus has been given to completions that leave the base category of a doctrine unchanged and instead add structure to the fibres: Trotta builds the existential completion in [ 31 ] while the geometric completion is considered in [ 6 , 32 , 33 ] . Across a pair of papers [ 2 , 1 ] , Abbadini and Guffanti study the completion of a presheaf of Boolean algebras P\colon\mathcal{C}^{\rm op}\to\mathbf{BA} with respect to both universal and existential quantifiers. They were motivated to develop a doctrinal language in which to phrase problems of quantifier complexity, as sketched in a talk of Gehrke [ 11 ] . The quantifier completion P^{\forall\exists} of P , to arbitrary quantifier depth, is proven to exist via an abstract argument in [ 2 , Theorem 5.2] . In their follow-up paper [ 1 ] , Abbadini and Guffanti study the completion up to quantifier depth 1, denoted by P^{\forall\exists}_{1} , i.e. the free addition of existential and universal formulae to the quantifier-free ones. To understand the structure of P^{\forall\exists}_{1} , they identify the formulae of quantifier depth 1 as a subdoctrine of P^{\forall\exists} via a semantic condition (their notion of a universal ultrafilter [ 1 , Definition 3.3] ). A careful analysis of the order relation in P^{\forall\exists}_{1} recovers Herbrand’s theorem [ 1 , Theorem 4.9] . The idea is the following: the datum of a universal theory \mathbb{T} is essentially contained in a presheaf of Boolean algebras – the doctrine of quantifier-free formulae – and so its free completion is the doctrine of formulae of quantifier depth 1 modulo \mathbb{T} -provability. The order relation in the completed doctrine thus describes, algebraically, the statement of Herbrand’s theorem. Our contribution The purpose of this paper is to point out that a more direct doctrinal proof of Herbrand’s theorem is possible by only completing with respect to existential quantifiers, which in comparison is less involved than the completion with respect to both quantifiers constructed in [ 1 ] . The first observation to make is that a proof of Herbrand’s theorem for Horn logic is implicit in the construction of Trotta’s existential completion of a primary doctrine [ 31 ] . In [ 33 , Lemma IV.38] , it is shown how Trotta’s existential completion can be carved out of the topos-theoretic geometric completion found in [ 32 , 6 , 33 ] , similar to how the exact completion of a regular category is constructed in [ 20 ] . In a similar fashion (Remark 2 ), the geometric completion instructs us on how to modify Trotta’s construction in order to obtain the two novel completions presented in this paper: (i) the free existential completion on a doctrine interpreting \{\land,\lor,=\} , (ii) and the free existential completion on a doctrine interpreting \{\land,\bigvee,=\} . As a result of the explicit description of these completions we can deduce versions of Herbrand’s theorem for coherent logic and geometric logic, with the former subsuming the classical version of Herbrand’s theorem (see Remark 6 ). In contrast, it is not clear how the methods of [ 1 ] generalise beyond the classical setting. Overview We proceed as follows: (1) In Section 1 , we recall the theory of Lawvere doctrines and how this acts as an algebraic framework for studying first-order theories, including how existential quantification and the equality predicate are interpreted algebraically. (2) In Section 2 , we first recall the construction of Trotta’s existential completion for presheaves of meet-semilattices, i.e. doctrines interpreting only (finite) conjunction, and that this completion respects the interpretation of equality. Next, we construct the existential completion for presheaves of distributive lattices, and then for presheaves of frames. For the sake of narrative clarity, and because the proofs closely mirror those in [ 31 ] , we initially state the universal properties of our existential completions as fact. We include explicit proofs of the necessary properties in Section 4 . (3) In Section 3 , we explain how the explicit descriptions of the existential completions described in the previous section yield versions of Herbrand’s theorem for Horn, coherent, classical and geometric logic. (4) Finally, in Section 4 , we give explicit proofs that our construction does in fact yield the existential completion on a presheaf of distributive lattices. Explicit proofs that our construction describes the existential completion on a presheaf of frames can be obtained by easily modifying our argument. 1 Doctrines Lawvere doctrines, as introduced in [ 21 , 22 ] , come in many different flavours depending on the fragment

Read the complete text