Support is Search

arXiv:2603.13018 · cs.LO, math.LO · Submitted 2026-03-13 · Read on arXiv

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

Where the paper says it

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?

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]. 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]. Base-extension semantics thereby admits a fully constructive and computationally transparent interpretation: support is proof-search ref:2603.13018[Abstract].

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

Where the paper says it

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.

13018[Theorem 4. p. 0
Where the paper says it

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?

p. 0
Where the paper says it

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?

p. 0
Where the paper says it

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?

6]>. This result complements Sandqvist’s global result with a local correspondence that characterizes exactly what support in a given base ref:2603.13018[Contribution]. The proof involves simultaneous induction on the structure of φ, utilizing monotonicity properties of support under base extension (Proposition 3. p. 7
Where the paper says it

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.

3) and monotonicity of ⊢O under program extension (Lemma 2. p. 9
Where the paper says it

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.

9) <ref:2603. p. 0
Where the paper says it

proof-theoretic semantics, base-extension semantics, intuitionistic propositional logic, logic programming, hereditary Harrop formulae, uniform proofs. 1 arXiv:2603.

13018[Theorem 4.6]>.

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

Where the paper says it

The paper is organised as follows. Section 2 develops the framework of atomic systems and hereditary Harrop programs, including the second-order extension.

p. 2
Where the paper says it

The paper is organised as follows. Section 2 develops the framework of atomic systems and hereditary Harrop programs, including the second-order extension.

p. 2
Where the paper says it

The paper is organised as follows. Section 2 develops the framework of atomic systems and hereditary Harrop programs, including the second-order extension.

The encoding of formulae as logic-programming goals is defined by clauses JφK that systematically turn formulae into clauses using their definitions <ref:2603. p. 8
Where the paper says it

[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.

13018[Definition 4. p. 1
Where the paper says it

[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.

p. 1
Where the paper says it

[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.

1]>. The main result, Theorem 4. p. 2
Where the paper says it

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.

6, explicitly identifies support in a fixed base with uniform proof-search in a second-order hereditary Harrop logic program <ref:2603. p. 0
Where the paper says it

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.

13018[Theorem 4.6]>. This provides a computationally transparent interpretation of the semantics ref:2603.13018[Abstract].

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

Where the paper says it

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.

13018[Definition 2. p. 1
Where the paper says it

[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.

p. 1
Where the paper says it

[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.

p. 1
Where the paper says it

[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.

p. 1
Where the paper says it

[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.

p. 1
Where the paper says it

[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.

p. 1
Where the paper says it

[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.

5]>. The main result hinges on the property that JφK is a neutral formula, which allows for the generalized basic properties of the operational provability relation <ref:2603. p. 8
Where the paper says it

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.

13018[Lemma 4. p. 7
Where the paper says it

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.

p. 7
Where the paper says it

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.

4]>. This neutrality enables Lemma 4. p. 8
Where the paper says it

Indeed, by inspection on the definition of definite and goal formula, all ∪-free formulae are neutral. This observation enables the following: Lemma 4.

5, which shows that substitution preserves provability under certain conditions <ref:2603.13018[Lemma 4.5]>.

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

Where the paper says it

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 rules for this language are designed so that the logical structure of the goal drives a proof-search procedure, with the program consulted only when an atomic goal is reached <ref:2603. p. 4
Where the paper says it

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.

13018[Definition 2.5]>. This operational semantics expresses the idea that derivability in an atomic system coincides with operational resolution and derivability in the atomic system <ref:2603. p. 4
Where the paper says it

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.

13018[Example 2. p. 0
Where the paper says it

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.

6]>. The encoding of higher-level rules is inspired by Hallnäs and Schroeder-Heister, leading to a computational representation where systems of clauses can be read as defining a natural deduction system ref:2603.13018[Rules-as-Clauses].

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

Where the paper says it

The paper is organised as follows. Section 2 develops the framework of atomic systems and hereditary Harrop programs, including the second-order extension.

p. 2
Where the paper says it

The paper is organised as follows. Section 2 develops the framework of atomic systems and hereditary Harrop programs, including the second-order extension.

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. p. 5
Where the paper says it

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.

p. 5
Where the paper says it

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.

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. p. 5
Where the paper says it

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.

p. 5
Where the paper says it

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.

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].

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