Support is Search

Alexander V. Gheorghiu · 2026

Read Support is Search by Alexander V. Gheorghiu (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-13018.txt.

Introduction

Alexander Gheorghiu asks what support means in one fixed atomic base under Sandqvist's base-extension semantics. The global completeness theorem says which formulae are valid in every base. The local question is what support in a single base amounts to. He shows it coincides with proof-search inside a logic program of second-order hereditary Harrop type. Formulae are encoded as program goals in continuation-passing style. Quantifiers over base extensions act as fresh eigenvariables, not ranges over a totality. Support is thus proof-search, fully constructive in form.

Catalog record

CREATORAlexander V. Gheorghiu
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40513
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.13018

Browse the full library · About the Tower of Babel

Full text

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

Support is Search Alexander V. Gheorghiu Abstract . Sandqvist’s base-extension semantics for intuitionistic propositional logic defines a support relation parametrised by atomic bases, with validity identified as support in every base. Sandqvist’s completeness theorem answers the global question: which formulae are valid? This paper addresses the local question: given a fixed base, what does support in that base correspond to? We show that support in a fixed base coincides with proof-search in a second-order hereditary Harrop logic program, via an encoding of formulae as logic-programming goals. This encoding proceeds by reading the semantic clauses in continuation-passing style, revealing that the universal quantifiers over base extensions and atoms appearing in those clauses are not domain-ranging quantifiers over a completed totality, but eigenvariables governed by a standard freshness discipline. Base-extension semantics thereby admits a fully constructive and computationally transparent interpretation: support is proof-search. The result complements Sandqvist’s global theorem with a local correspondence, vindicates the anti-realist foundations of the framework on its own terms, and opens the way for implementing the semantics in modelling tasks. 2020 Mathematics Subject Classification 03B20, 68N17, 03F50 1. Introduction Schroeder-Heister dubbed the programme concerned with grounding the meaning of logical constants not in denotational or model-theoretic notions, but in inferential or proof-theoretic behaviour ‘proof-theoretic semantics’ (P-tS) [ 30 ] . The programme, developed in its modern form by Prawitz [ 22 , 23 ] , Dummett [ 3 , 1 , 2 ] , and Schroeder-Heister [ 27 , 28 , 30 ] , takes as its point of departure the anti-realist thesis that meaning must be publicly manifestable and therefore tied to what a speaker can in principle demonstrate, rather than to potentially verification-transcendent truth conditions. On this view, the meaning of a sentence is nothing over and above the capacity to recognise proofs of it. A particularly well-known realisation of this programme is the base-extension semantics (B-eS) for intuitionistic propositional logic due to Sandqvist [ 26 ] . The semantics takes as its primitive notion a base \mathcal{B} — a collection of rules governing atomic sentences. This has an intuitive notion of derivability; we write \vdash_{\mathcal{B}}p to denote that an atom p is derivable in \mathcal{B} . The meaning of the logical constants is given by an inductively defined relation called support with clauses for each of the connectives. For example, the clause for implication ( \to ) is: \Vdash_{\mathcal{B}}\varphi\to\psi\qquad\text{iff}\qquad\text{for every $\mathcal{C}\sqsupseteq\mathcal{B}$, if $\Vdash_{\mathcal{C}}\varphi$, then $\Vdash_{\mathcal{C}}\psi$,} where \mathcal{C}\sqsupseteq\mathcal{B} means that \mathcal{C} extends \mathcal{B} (i.e. contains at least all the rules of \mathcal{B} ). While this may be reminiscent of Kripke semantics for intuitionistic logic [ 12 ] , the analogy can be misleading. This is most clear in two place. First, taking the standard clause for disjunction, \Vdash_{\mathcal{B}}\varphi\lor\psi\qquad\text{iff}\qquad\Vdash_{\mathcal{B}}\varphi\text{ or }\Vdash_{\mathcal{B}}\psi, does not yield intuitionistic logic (see Piecha et al. [ 16 , 21 , 20 ] ), but rather general inquisitive logic (see Stafford [ 31 ] ). To get intuitionistic logic, Sandqvist [ 26 ] instead adopts the following clause: \begin{array}[]{ccc}\Vdash_{\mathcal{B}}\varphi\lor\psi&\text{iff}&\text{for every $\mathcal{C}\sqsupseteq\mathcal{B}$ and every atom $p$,}\\[4.0pt] &&\text{if }\varphi\Vdash_{\mathcal{C}}p\text{ and }\psi\Vdash_{\mathcal{C}}p\text{, then }\Vdash_{\mathcal{C}}p.\end{array} Secondly, what logic the semantics gives depends on precisely what is meant by base . Sandqvist [ 26 ] proved that \Vdash_{\mathcal{B}}\varphi\text{ for all $\mathcal{B}$}\qquad\text{iff}\qquad\varphi\textbf{ is intuitionistically valid} when \mathcal{B} are higher-level atomic systems. But Sandqvist [ 25 ] , Gheorghiu [ 9 ] , and Stafford et al. [ 17 ] have each shown that \Vdash_{\mathcal{B}}\varphi\text{ for all $\mathcal{B}$}\qquad\text{iff}\qquad\varphi\textbf{ is classically valid} when \mathcal{B} are first-level atomic systems. This change of logic comes without a change in the definition of the logical constants. Observe that in both cases, soundness and completeness concern global support. That is, they characterise the formulae supported in every base \mathcal{B} . In this paper, we consider the local question: what does \Vdash_{\mathcal{B}}\varphi correspond to for a fixed base \mathcal{B} ? The local question has received some attention previously. In particular, it is clear that it cannot be characterized by export : \Vdash_{\mathcal{B}}\varphi\qquad\text{is not equivalent to}\qquad\mathcal{B}^{\ast}\vdash\varphi, where \mathcal{B}^{\ast} is a natural representation of a base as a set of formulae. A telling counterexample involves disjunction: by the disjunction property, \mathcal{B}^{\ast}\vdash A\lor B is equivalent to \mathcal{B}^{\ast}\vdash A or \mathcal{B}^{\ast}\vdash B , but \Vdash_{\mathcal{B}}\varphi\lor\psi need not imply \Vdash_{\mathcal{B}}\varphi or \Vdash_{\mathcal{B}}\psi . The challenge for understanding \Vdash_{\mathcal{B}}\varphi is that the definition of support involves several quantification over bases and atoms and meta-level implications, as seen in the example clauses above. Read in a realist manner, with the meta-level ranging over a completed totality and no constructive content passed from \varphi to \psi , the semantics seemingly betrays its anti-realist foundations. Schroeder-Heister [ 29 ] has indeed been critical of some of these aspects of the semantics saying that despite its difference from model-theoretic semantics, proof-theoretic semantics still adheres to the ‘dogmas’ of standard semantics. But what alternative reading available? This paper provides an answer to these questions by giving a fully computational account of \Vdash_{\mathcal{B}}\varphi . We show that it corresponds to proof-search in a logic programming language. That is, we define an operational judgment relation \vdash_{O} and associate to each formula \varphi a formula \llbracket\varphi\rrbracket such that the following holds: \Vdash_{\mathcal{B}}\varphi\qquad\text{iff}\qquad\mathcal{B}\vdash_{O}\llbracket\varphi\rrbracket, The universal quantifiers in the support judgment are governed by an eigenvariable discipline in the operational semantics of \vdash_{0} . Accordingly, the meaning of the support judgment is given by a proof-search procedure. Support is search. Contribution. This paper contributes to the understanding of base-extension semantics the following: • Meta-theoretic commitments. The clauses of the support relation need not be regarded as ranging over completed infinite sets — a realist presupposition at odds with the anti-realist foundations of the programme — but are given a constructive interpretation internal to the proof-search framework, vindicating the coherence of the framework. • Computational content. We give an explicit procedure — executing \llbracket\varphi\rrbracket as a logic-programming goal against \mathcal{B} — that finds a witnessing uniform derivation whenever \Vdash_{\mathcal{B}}\varphi holds; support is not merely effectively verifiable in principle but searchable in practice. • Local soundness and completeness. For any fixed base \mathcal{B} , \Vdash_{\mathcal{B}}\varphi\qquad\mbox{iff}\qquad\mathcal{B}\vdash_{\mathcal{O}}\llbracket\varphi\rrbracket — complementing Sandqvist’s global result with a local correspondence that characterises exactly what support in a given base. Organization. The paper is organised as follows. Section 2 develops the framework of atomic systems and hereditary Harrop programs, including the second-order extension. Section 3 recalls Sandqvist’s base-extension semantics and establishes the relevant background results. Section 4 introduces the encoding of IPL formulae as logic-programming goals and proves the main soundness and completeness theorem. Section 5 discusses the implications of our result for the proof-theoretic semantics programme, and in particular for the question of what the universal quantifiers in B-eS mean. 2. Atomic Systems (Generalized) Higher-level Atomic Systems Atomic systems are the foundation of base-extension semantics. They are often presented within the framework of Gentzen-style natural deduction [ 32 ] . The notion was made explicit by Prawitz [ 22 , 23 ] . Definition 2.1 (First-level Atomic System) . A first-level atomic system \mathcal{S} is a system of production rules governing atomic propositions — rules of the form \frac{A_{1}\quad\cdots\quad A_{n}}{C} where A_{1},\ldots,A_{n} and C are all atomic propositions. Derivability in \mathcal{S} — denoted \vdash_{\mathcal{S}} —is defined compositionally (i.e., in the standard way but without substitutions of atoms). This

Read the complete text