Support is Search
Listen
Radio episode about this paper
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.
University of Southampton · University College London
cs.LO, math.LO
Submitted: 2026-03-13
Updated: 2026-11-12
Comments: 24 pages
Journal ref: Journal of Logic and Computation 2026
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 92/100
The gist: Sandqvist’s base-extension semantics for intuitionistic propositional logic defines a support relation parametrised by atomic bases…
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
Summary
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]. This paper addresses the local question: given a fixed base, what does support in that base correspond to? p. 0 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?Where the paper says it
The Correspondence Between Semantics and Computation
The core finding establishes a local correspondence between the semantic notion of support in a fixed base and uniform proof-search within a logic programming framework ref:2603.13018[Abstract]. Specifically, the authors show that for any fixed base B, the judgment ⊩B φ corresponds exactly to B ⊢O JφK, where JφK is an encoding of the formula φ as a logic-programming goal ref:2603.13018[Abstract]. This correspondence is achieved by defining an operational judgment relation ⊢O and associating each formula φ with a formula JφK such that ⊩B φ iff B ⊢O JφK ref:2603.13018[Abstract]. The universal quantifiers in the support judgment are governed by an eigenvariable discipline in the operational semantics of ⊢0, meaning the meaning of the support judgment is given by a proof-search procedure ref:2603.13018[Abstract].
Meta-theoretic Commitments and Constructive Interpretation
The paper addresses critiques against base-extension semantics regarding its anti-realist foundations by providing a constructive interpretation for the universal quantifiers ref:2603.13018[Abstract]. The authors argue that the clauses of the support relation do not need to be regarded as ranging over completed infinite sets, but are given a constructive interpretation internal to the proof-search framework, which vindicates the coherence of the framework ref:2603.13018[Contribution]. Furthermore, they provide an explicit procedure—executing JφK as a logic-programming goal against B—that finds a witnessing uniform derivation whenever ⊩B φ holds, demonstrating that support is not merely effectively verifiable in principle but searchable in practice ref:2603.13018[Contribution].
Local Soundness and Completeness
The paper establishes local soundness and completeness for any fixed base B by proving Theorem 4.6, which states that ⊩B φ iff B ⊢O JφK <ref:2603. p. 1 We show that it
corresponds to proof-search in a logic programming language. That is, we define an
operational judgment relation ⊢O and associate to each formula φ a formula JφK
such that the following holds:
⊩B φ iff B ⊢O JφK,
The universal quantifiers in the support judgment are governed by an eigenvariable
discipline in the operational semantics of ⊢0. 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? 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? 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? That is,
⊢N φ
♭
iff ⊢ φ
These two together deliver global completeness:
⊩B φ for all B implies ⊩N φ
implies N ⊢O φ
♭
(†)
implies ⊢ φ (††)
The construction was generalized by Gheorghiu and Pym [8], where the flattening
operator (−)
♭
is made sensitive also to a base B in the sense that χ
♭ does not occur
in B. In this case, one gets the following simulation lemma:
⊩B φ iff N ∪ B ⊢O ψ
♭
This captures support locally, but at the cost of flattening φ entirely — all logical
structure is absorbed into the base N , leaving no direct correspondence between
the connectives of φ and the proof-search procedure. By definition of [−], F1∩F2 ∈ [P, F1∩F2] implies
Fi ∈ [P, F1 ∩ F2] for each i. Hence P, F1 ∩ F2, Fi ⊢O Fi by the induction hypothesis
(since Fi
is neutral and strictly smaller), and the result follows by monotonicity
(Lemma 2. proof-theoretic semantics, base-extension semantics, intuitionistic
propositional logic, logic programming, hereditary Harrop formulae, uniform proofs. 1
arXiv:2603.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Implications for Proof-Theoretic Semantics
The central result resolves the local question left open by Sandqvist’s global completeness theorem, showing that support in a fixed base corresponds to a uniform proof in a fragment of intuitionistic logic with second-order quantifiers over atoms ref:2603.13018[Discussion]. The authors argue that the universal quantifiers over base extensions and atoms in the semantic clauses do not range over a completed totality of inferential contexts, but receive a constructive interpretation internal to the proof-search framework ref:2603.13018[Discussion]. This vindicates the coherence of base-extension semantics on its own terms, showing that the semantics is not merely anti-realist in aspiration but in execution ref:2603.13018[Discussion]. The result suggests that support should again reduce to proof-search in a suitable logic-programming language whenever an appropriate analogue of higher-level atomic systems is available ref:2603.13018[Discussion].
Where the gains come from
The paper’s contribution lies in providing a fully computational account of ⊩B φ, which moves beyond merely being analogous to logic-program execution to being precisely logic-program execution <ref:2603.13018[Section 4]>. p. 2 The paper is organised as follows. Section 2 develops the framework
of atomic systems and hereditary Harrop programs, including the second-order
extension. The paper is organised as follows. Section 2 develops the framework
of atomic systems and hereditary Harrop programs, including the second-order
extension. The paper is organised as follows. Section 2 develops the framework
of atomic systems and hereditary Harrop programs, including the second-order
extension. [6] showed that conjunction can be understood in CPS:
⊩B φ ∧ ψ iff for any C ⊒ B and p ∈ At
if φ, ψ ⊩C p, then φ, ψ ⊩C p
This observation is useful as CPS is easy to express in logic programming. Therefore,
we can systematically turn formulae into clauses using their definitions. [21] have each shown that
⊩B φ for all B iff φ is classically valid
when B are first-level atomic systems. This change of logic comes without a change
in the definition of the logical constants. [21] have each shown that
⊩B φ for all B iff φ is classically valid
when B are first-level atomic systems. This change of logic comes without a change
in the definition of the logical constants. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
How the training signal is built
The encoding process involves defining clauses JφK for each formula φ, such as Jφ → ψK = JφK ⊃ JψK <ref:2603.13018[Definition 4.1]>. The operational semantics for logic programming is defined by rules such as Fact, Backchain, And, Or, and Augment <ref:2603. p. 4 The operational semantics relation ⊢O is
defined as follows:
• Fact: P ⊢O A if A ∈ [P]. • Backchain: P ⊢O A if there exists G ⊃ A ∈ [P] such that P ⊢O G. [21] have each shown that
⊩B φ for all B iff φ is classically valid
when B are first-level atomic systems. This change of logic comes without a change
in the definition of the logical constants. [21] have each shown that
⊩B φ for all B iff φ is classically valid
when B are first-level atomic systems. This change of logic comes without a change
in the definition of the logical constants. [21] have each shown that
⊩B φ for all B iff φ is classically valid
when B are first-level atomic systems. This change of logic comes without a change
in the definition of the logical constants. [21] have each shown that
⊩B φ for all B iff φ is classically valid
when B are first-level atomic systems. This change of logic comes without a change
in the definition of the logical constants. [21] have each shown that
⊩B φ for all B iff φ is classically valid
when B are first-level atomic systems. This change of logic comes without a change
in the definition of the logical constants. [21] have each shown that
⊩B φ for all B iff φ is classically valid
when B are first-level atomic systems. This change of logic comes without a change
in the definition of the logical constants. For any intuitionistic formula φ, its encoding JφK is neutral. The useful property of neutral formulae is that it allows us to generalized basic
properties of the operational provability relation:
Lemma 4. That is,
⊢N φ
♭
iff ⊢ φ
These two together deliver global completeness:
⊩B φ for all B implies ⊩N φ
implies N ⊢O φ
♭
(†)
implies ⊢ φ (††)
The construction was generalized by Gheorghiu and Pym [8], where the flattening
operator (−)
♭
is made sensitive also to a base B in the sense that χ
♭ does not occur
in B. In this case, one gets the following simulation lemma:
⊩B φ iff N ∪ B ⊢O ψ
♭
This captures support locally, but at the cost of flattening φ entirely — all logical
structure is absorbed into the base N , leaving no direct correspondence between
the connectives of φ and the proof-search procedure. That is,
⊢N φ
♭
iff ⊢ φ
These two together deliver global completeness:
⊩B φ for all B implies ⊩N φ
implies N ⊢O φ
♭
(†)
implies ⊢ φ (††)
The construction was generalized by Gheorghiu and Pym [8], where the flattening
operator (−)
♭
is made sensitive also to a base B in the sense that χ
♭ does not occur
in B. In this case, one gets the following simulation lemma:
⊩B φ iff N ∪ B ⊢O ψ
♭
This captures support locally, but at the cost of flattening φ entirely — all logical
structure is absorbed into the base N , leaving no direct correspondence between
the connectives of φ and the proof-search procedure. Indeed, by inspection on
the definition of definite and goal formula, all ∪-free formulae are neutral. This
observation enables the following:
Lemma 4.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Pruning redundant reasoning tokens
The paper systematically encodes the logical structure of intuitionistic propositional logic into a second-order logic-programming language, using hereditary Harrop formulae as the foundation <ref:2603.13018[Section 2]>. p. 2 The paper is organised as follows. Section 2 develops the framework
of atomic systems and hereditary Harrop programs, including the second-order
extension. The operational semantics of the logic programming language is a judgment
P ⊢O G expressing that the program P resolves the goal G. It is based on the idea
that the logical structure of the goal should drive a proof-search proceedure, with
the program consulted only when an atomic goal is reached. Gheorghiu and Pym [8] observed that the hierarchy of atomic systems above
corresponds exactly to the inductive depth of definite formulae: an nth-level atomic
system encodes precisely as a program whose definite formulae have nesting depth
n. When P and G are the representations of an atomic system S and an atom a
respectively, we have
P ⊢O G iff ⊢S a,
so that operational resolution and derivability in the atomic system coincide. 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 (→) is:
⊩B φ → ψ iff for every C ⊒ B, if ⊩C φ, then ⊩C ψ,
2020 Mathematics Subject Classification.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
The paper explores the implications for classical logic by noting that restricting to first-level production rules corresponds precisely to replacing hereditary Harrop formulae with Horn clauses, which is a logic-programming language without hypothetical goals ref:2603.13018[Discussion]. The loss of higher-level rules forecloses the continuation-passing encoding that drives the correspondence, suggesting that a computationally transparent, search-based account of support in the classical setting remains an open problem ref:2603.13018[Discussion]. This suggests a broader research programme where support should reduce to proof-search in a suitable logic-programming language for various logics ref:2603.13018[Discussion]. The authors leave the systematic identification of the right class of programs and encoding as future work ref:2603.13018[Discussion].
The paper’s framework is built upon a potential infinity for atomic sentences, which is admissible from an anti-realist standpoint because it does not presuppose any completed totality, only the open-ended availability of new resources as derivation proceeds <ref:2603.13018[Section 3]>. p. 2 The paper is organised as follows. Section 2 develops the framework
of atomic systems and hereditary Harrop programs, including the second-order
extension. The paper is organised as follows. Section 2 develops the framework
of atomic systems and hereditary Harrop programs, including the second-order
extension. From an anti-realist standpoint one cannot appeal to
arbitrary infinite sets as primitive: to do so would be to presuppose a completed
infinity whose existence outruns any manifestable warrant. Fortunately, one can restrict to using only infinite systems that are schematic in
some way. From an anti-realist standpoint one cannot appeal to
arbitrary infinite sets as primitive: to do so would be to presuppose a completed
infinity whose existence outruns any manifestable warrant. Fortunately, one can restrict to using only infinite systems that are schematic in
some way. In so doing, we have moved from requiring infinite systems/programs to finite ones. This use of the second-order quantifier is natural in the context of logic programming. In so doing, we have moved from requiring infinite systems/programs to finite ones. This use of the second-order quantifier is natural in the context of logic programming.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
The paper's framework is built upon a potential infinity for atomic sentences, which is admissible from an anti-realist standpoint because it does not presuppose any completed totality, only the open-ended availability of new resources as derivation proceeds <ref:2603.13018[Section 3]>. This use of infinite systems is restricted to schematic forms, such as those involving arbitrary substitutions of rules like (A ⊃ X) ∩ (B ⊃ X) ⊃ X <ref:2603.13018[Definition 2.7]>. This move from requiring infinite systems/programs to finite ones is natural in the context of logic programming, utilizing a second-order quantifier <ref:2603.13018[Definition 2.7]>. This approach successfully captures support locally while making the relevant structures explicit and direct ref:2603.13018[Discussion]. The paper's central result is that support is not merely analogous to logicprogram execution—it is logic-program execution <ref:2603.13018[Section 4]>. This confirms the anti-realist foundations of the framework on its own terms ref:2603.13018[Abstract]. The result depends essentially on the presence of higher-level rules in the atomic systems ref:2603.13018[Discussion]. This dependence is illuminating regarding the structure required for this correspondence ref:2603.13018[Discussion].
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
1
A system can be designed to determine if a logical formula is supported in a specific base by executing JphiK as a logic-programming goal against B, which corresponds to support is proof-search.
2
The AI system can utilize the encoding of IPL formulae as logic-programming goals where the universal quantifiers over base extensions and atoms are governed by an eigenvariable discipline, allowing for a fully constructive and computationally transparent interpretation of support.
3
The system can perform local soundness and completeness checks by verifying that support is not merely analogous to logicprogram execution — it is logic-program execution,
specifically checking that ⊩B φ iff B ⊢O JφK.
Abstract
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.
Related papers
- A Non-Dichotomy for CSPs of Stable omega-Categorical Structures
- A Deeper Look at Depth: Stable Generation Accounting for Quantifier Reasoning
- Formalizing Hyperspaces and Operations on Subsets of Polish Spaces over Abstract Exact Real Numbers
- A Diagrammatic Basis for Computer Programming
- Interpolation via Generalized Splitting
- Staying Productive Under the Palm Trees: On Graded Coeffect Typing in the Tropical Semiring