Support is Search
summary
The gist
Sandqvist’s base-extension semantics for intuitionistic propositional logic defines a support relation parametrised by atomic bases…
In short
The paper investigates Sandqvist's base-extension semantics for intuitionistic propositional logic by showing that support in a fixed base corresponds exactly to proof-search in a second-order hereditary Harrop logic program. This provides a constructive and computationally transparent interpretation, meaning support is precisely equivalent to searching for a proof within the logic program.
Key concepts
- Base-extension semantics
- This is the original semantic framework used to define validity in intuitionistic propositional logic by considering how formulas behave when extended with new atomic bases. The authors show that this complex semantic idea can be understood constructively through computation.
- Logic-programming goals encoding
- The paper translates logical formulas into specific 'goals' within a logic programming language. This encoding allows the abstract semantics of support to be directly mapped onto the concrete operational steps of searching for a solution in a program.
- Proof-search correspondence
- This is the core finding: support in any fixed base is identical to performing a search procedure on an encoded logic program. Instead of abstract set theory, validity becomes an executable task—finding a proof by systematically searching through the defined rules.
Terminology used across episodes
This episode discusses
The paper
Support is Search · Read on arXiv
University of Southampton · University College London
For intuitionistic propositional logic, Sandqvist's base-extension semantics 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 hereditary Harrop logic program with a quantifier over atoms, via an encoding of formulae as logic programming goals. The encoding is a variant of the Russell-Prawitz translation of the connectives, with quantification restricted to atoms, and it is obtained by reading the semantic clauses in continuation-passing style. So read, the universal quantifiers over base extensions and atoms in those clauses need not range over a completed totality: they are eigenvariables under a standard freshness discipline. Base-extension semantics thereby acquires an explicit computational content: support is proof-search. The result complements Sandqvist's global theorem with a local correspondence and makes the constructive character of the framework explicit.
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Support is Search".
Jane: Here's the gist of the paper. 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 <ref:2603.13018
Abstract: >.
Tom: This paper addresses the local question: given a fixed base, what does support in that base correspond to?
Jane: <ref:2603.13018
Abstract: > 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 <ref:2603.13018
Abstract: >.
Tom: 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 domainranging quantifiers over a completed totality, but eigenvariables governed by a standard freshness discipline <ref:2603.13018
Abstract: >.
Paper summary: Tom: So wrapping up "Support is Search," the core idea they push is that support in a fixed base corresponds to uniform proof search within a second-order hereditary Harrop logic program.
Jane: They really nail the local question, showing that for any fixed base B, you can precisely characterize what support means by looking at B ⊢ O J phi K.
Lu: The paper vindicates the anti-realist foundations of base-extension semantics by showing that the clauses don't need to range over completed infinite sets but are given a constructive interpretation internal to the proof search framework.
Meng: From an engineering standpoint, this means we have a computationally transparent interpretation where support is just running a search algorithm against those encoded goals.
Lalam: And they show that there's an explicit procedure for executing these goals that finds a witnessing uniform derivation whenever the support holds, meaning it’s not just possible to verify but actually searchable in practice.
Tom: The authors also explore what happens when you restrict this to first-level production rules, suggesting that for classical logic, the computational link breaks down because you lose the continuation-passing encoding.
Jane: So the implication is that while this works beautifully for intuitionistic logic under these specific conditions, we still have an open problem about finding a search-based account of support in the classical setting.
Lu: The paper suggests a broader research program where support should reduce to proof search in a suitable logic programming language, depending on what kind of atomic systems you are working with.
Meng: So if you're building something, this paper points toward using logic programming as the engine for finding proofs when your underlying logic is set up correctly.
Lalam: That's the main point: support is not just analogous to logic program execution—it is logic-program execution, and that depends on having those higher-level rules in your atomic systems.
Conclusion: Tom: So, "Support is Search" is the title of this paper, and it’s by Sandqvist and others.
Jane: It basically says that support in these systems isn't just some abstract concept; it actually maps directly to a search procedure in a logic program.
Tom: Right, so we’re talking about how proof search works when you have these base extensions.
Jane: They show that for any fixed set of atomic rules, like a specific logic base B, the support relation is exactly what happens when you run an operational judgment on that program against B.
Tom: It sounds like they’re making the semantics computationally transparent, which is a big deal for understanding how these systems actually work.
Jane: Exactly. They get away from just saying "this means that" and show the actual procedure for finding a proof, which is much more concrete.
Tom: So it moves support from being a theoretical property to something we can actually search for on a computer.
Jane: Right, and they handle the tricky part about those universal quantifiers—they interpret them constructively, not as just some abstract completed totality.
Tom: That’s where they push back against the older anti-realist critiques by showing how the framework remains coherent when we look at it practically.
Jane: It suggests that support is fundamentally proof search under certain conditions, which means if you build a system that has higher-level rules, you get a very clear path to finding those proofs.
Tom: So for someone just listening, it means that instead of thinking about complex sets of possibilities for a proof existing somewhere, you can actually run an algorithm to find the proof.
Jane: And this opens up some interesting questions about what this really means for classical logic and other systems where these rules are different.
More episodes
- 2507.14812-A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
- 2507.15448-Frames over finite fields with respect to the Galois inner product and their connections to self-orthogonal and LCD codes
- 2508.21572-NewsReX: An Open-Source Multi-Framework for Neural News Recommendation
- 2509.17028-Impact of Packetization on Network Calculus Analysis
- 2510.17342-AoA Services in 5G Networks: A Framework for Real-World Implementation and Systematic Testing
- 2511.04088-Efficient and rate-optimal list-decoding in the presence of minimal feedback
- 2511.17264-Notes on Stack Machines and Quantum Stack Machines
- 2601.15318-On the closest balanced game
- 1905.10490-Finding new routes for integrating Multi-Agent Systems using Apache Camel
- 2401.10816-Co-Pilot for Health: Personalized Algorithmic AI Nudging to Improve Health Outcomes