Many reasoning problems are about how much rather than whether: how far apart two items are, what a chain of steps costs, how badly a constraint is violated. A clean logic for this already exists at the propositional level. Bacci, Mardare, Panangaden and Plotkin built logics whose truth values are distances in $[0,\infty]$, the "Lawvere quantale." A quantale is a complete lattice with an associative "tensor" that distributes over suprema; here the tensor is addition and the order is reversed $\geq$. They proved these logics complete. Their proofs are checkable certificates of linear inequalities in the style of Farkas' lemma. Deciding consequence is co-NP complete (Propositional Logics for the Lawvere Quantale). They list first-order quantifiers as the main open extension. Strong completeness already fails there in the presence of $\infty$, and so does the deduction theorem.
This note proposes the first-order extension. The approach is to establish its proof theory, not merely to define a semantics. A universal quantifier is read as a supremum of distances over the domain and an existential as an infimum. The central result we aim for is a Herbrand–Farkas theorem. It says that a first-order distance judgement in a suitable fragment holds exactly when some finite set of ground instances admits a linear-inequality certificate. A ground instance is a copy of the formula with quantified variables replaced by concrete terms.
Such a theorem would give three things at once. It would yield a semi-decision procedure that can be implemented. It would give a precise measure of proof size, namely the number of instances times the size of the certificate. And it would mark a sharp boundary. Outside the fragment, infima over infinite domains need not be attained, and we expect validity to climb the arithmetical hierarchy. The arithmetical hierarchy is computability theory's scale of how many alternating unbounded searches a problem needs. Degree theory then becomes the right tool for stating exactly how incomplete any finite proof system must be.
Core Claim
Define first-order Lawvere logic (FOL-$\mathbb{L}^*$) as the connectives of $\mathbb{L}^*$ (meet, join, tensor $\otimes$ = addition, linear implication $\multimap$ = truncated subtraction, rational scalars, unit) plus $\forall,\exists$ over a domain of individuals. Predicates take values in $[0,\infty]$. Judgements have the form $\Gamma \vdash \varphi \le r$ with $r$ rational. Our claims come in three tiers.
First, consider the universal, $\infty$-guarded fragment. Here quantifiers occur in prenex universal position on the goal side, and every atom is bounded by a finite rational in the premises. For this fragment we conjecture a Herbrand–Farkas theorem. A judgement holds in all models iff there exist finitely many ground terms $t_1,\dots,t_k$ such that the following implication holds:
$$\textstyle\bigwedge_{i\le k} \Gamma[t_i] \;\Rightarrow\; \varphi[t_1,\dots,t_k] \le r,$$
and this implication has a Motzkin-transposition certificate of the kind Bacci et al. use propositionally. In the display, $\Gamma[t_i]$ is the premise set instantiated at $t_i$, and $\varphi[t_1,\dots,t_k]$ is the corresponding finite join of goal instances.
It follows that valid judgements of this fragment form a $\Sigma^0_1$ set, meaning they can be listed by a single unbounded search. The minimal $k$ and the certificate's bit-size give a natural proof-length measure.
Second, for the full logic with quantifier alternation, we conjecture that validity is $\Pi^0_2$-hard. The intuition is that a judgement $\inf_x \sup_y \psi \le r$ can hold only "in the limit" without any finite witness, which is the first-order shadow of the $\infty$-failures Bacci et al. found propositionally. We also conjecture that the $\infty$-avoiding approximate consequence relation sits strictly lower in the hierarchy. If both hold, strong completeness cannot be recovered by any recursively axiomatized calculus. That is a degree-theoretic explanation of the propositional pathology.
Third, we aim to prove cut admissibility for a sequent calculus of the guarded fragment. In this calculus, cut corresponds to adding two inequalities with Farkas multipliers. The proof would follow the elementary ordinal-measure method that A Short and Readable Proof of Cut Elimination for Two First-Order Modal Logics adapted from Brighton. That paper obtained cut elimination for $M^3$ and $ML^3$ by induction on $\omega^2 \cdot C + \omega \cdot RR + m$, where $C$ is formula complexity, $RR$ is a reducibility rank and $m$ is derivation height. Its argument depends on a syntactic restriction (no free variables under the box). We expect our analogue to be the $\infty$-guard. The prediction is testable: cut should fail to be admissible once unguarded $\infty$ is allowed.
Relation to Prior Work
Bacci et al. supply the method we lift: normal forms as systems of linear inequalities, Motzkin/Farkas certificates, and Fourier–Motzkin elimination. They also motivate the work by naming the first-order gap. We differ from them by adding quantifiers and by replacing their co-NP analysis with a hierarchy analysis. Coarse complexity classes stop applying once domains are infinite.
Gao and Tourlakis supply the template for an elementary, readable cut-elimination proof. They also constrain us, since their technique is known to break without its syntactic restriction. We are betting that the $\infty$-guard plays that role here.
The degree-theory side supplies methods. Bazhenov, Kalociński and Wrocławski built priority-style ("pushing-to-the-right") constructions that place degree spectra strictly between the c.e. and $\Delta_2$ degrees (Intrinsic Complexity of Recursive Functions on Natural Numbers with Standard Order). Kalociński, San Mauro and Wrocławski showed that computable structures can lack primitive-recursive copies (Punctual Presentability in Certain Classes of Algebraic Structures). Both studies treat only discrete $\{0,1\}$-valued structures. We reuse their construction style for the lower bounds, and as a secondary question we ask whether computable Lawvere models with a computable distance relation always have punctual copies. Answering it requires confronting the tension that sup/inf evaluation involves search.
Applied neuro-symbolic systems motivate the work. Logic-LM (Logic-LM), LINC (LINC) and Logical-SAGE (Logical-SAGE) all call classical provers, and Logical-SAGE names metric and fuzzy domains as its expressivity ceiling. We do not build a language-model pipeline. We build the target logic and prover such pipelines would need.
Mature first-order many-valued logics exist outside this file, notably Łukasiewicz and continuous logic. We treat them as alternatives to beat, not as settled ground (see below).
Research Program
The theoretical work has four parts. We first fix a semantics with $[0,\infty]$-valued predicates and prove soundness of the lifted $\mathbb{L}^*$ rules. We then prove the Herbrand–Farkas theorem for the guarded universal fragment. The proof strategy is compactness for linear systems over the rationals: a finitely unsatisfiable system of inequalities has a finite infeasible subsystem. This is combined with a term-model construction.
Next we prove the hierarchy bounds. The upper bounds come from the procedure. The $\Pi^0_2$-hardness comes from encoding "this program halts on infinitely many inputs" into an $\inf\sup$ distance judgement. Finally we give the elementary cut-admissibility proof and a counterexample to admissibility outside the guarded fragment.
The engineering part is a prover. It interleaves Herbrand instance generation, guided by which atoms the current infeasible core uses, with an exact rational linear-programming feasibility check. Whenever it succeeds it emits a Farkas certificate that can be checked independently.
Baselines
The naive reference point is to discard the quantities. We threshold every distance to $\{0,\infty\}$, so that "within budget" becomes true and "over" becomes false, and run Prover9 as the classical pipelines do. This tells us how much the quantitative semantics changes the answers. Beating it means agreeing with exact gold labels on problems where thresholding flips the answer.
The strongest existing competitor is Z3 with quantified linear real arithmetic. We encode each predicate as a real-valued function with range constraints, encode sup and inf through universally quantified bounds, and let Z3 instantiate the quantifiers. This is a serious threat because it is mature and handles exactly this arithmetic. To make the comparison fair, both systems get identical problem files, the same per-instance timeout, the same hardware, and an equal tuning budget for Z3's instantiation options. Beating it means one or more of three things: fewer timeouts on the infinite-domain problem families, a comparable solved rate with machine-checkable certificates that Z3 does not produce, or provably correct "unknown" answers where Z3 returns unsound "sat" through incomplete instantiation.
A third baseline is full grounding. Over the Herbrand universe truncated at term depth $d$, we generate all instances and solve one large linear program. This isolates the value of exactly solving finite approximations.
The key ablation removes core-guided instance selection from our prover. Instances are then added breadth-first by term depth. This ablation isolates whether the Herbrand–Farkas structure, rather than the linear-programming backend, is responsible for any gains.
No reported result was found on Lacuna for any quantitative or metric first-order reasoning benchmark. The only nearby figures concern classical natural-language pipelines on FOLIO: Logic-LM with GPT-4 at 78.1% accuracy and human experts at 96% (FOLIO). Those figures measure translation from natural language, which we bypass, so they are context rather than a target.
Why not just…?
Why not just use first-order Łukasiewicz or product fuzzy logic via $e^{-x}$? Bacci et al. show that the exponential bridge sends the additive Lawvere structure to product logic, which suits multiplicative probabilities rather than additive costs. They also show that quantitative equational reasoning embeds directly into $\mathbb{L}^*$. That said, bounded Łukasiewicz logic does share truncated addition. If FOL-$\mathbb{L}^*$ restricted to finite values reduces cheaply to first-order Łukasiewicz logic, much of the hierarchy work could be inherited. We will try to build that reduction early. If it succeeds, the contribution narrows to the $\infty$-guarded Herbrand–Farkas theorem and the certificates. The unbounded value $\infty$ and its failure of cancellation are what no bounded logic can express.
Why not just encode everything in Z3 with real arithmetic? On finite domains this may well match us, and the experiments are designed to show whether it does. Its quantifier instantiation is heuristic, though. It yields no linear-inequality certificate, and it carries no account of which judgements have finite proofs at all. The infinite-domain families and the certificate-check experiment below settle whether that difference matters in practice.
Why not just state co-NP or PSPACE bounds, as Bacci et al. did, and skip degree theory? Once quantifiers range over infinite domains, consequence is not decidable at all, so polynomial-time classes stop discriminating. The open question becomes how undecidable consequence is, and which fragments admit finite proofs. That is exactly what hierarchy levels and degrees measure, and it is the form a precise negative answer about strong completeness must take.
Proposed Experiments
We will build two benchmark suites. The first, Metric-ProofWriter, takes ProofWriter's synthetic rule theories at depths 0 to 5 and attaches rational costs to facts and rules. Conclusions become questions of the form "is the derived cost at most $r$?". Gold labels come from exact shortest-path and linear-programming computation over the finite ground theory. The second suite contains infinite-domain variants, where function symbols generate unbounded term universes. On these, gold labels are known by construction for a subset that carries a planted finite witness.
The first decisive check is conservativity. We run the prover on FOLIO's expert gold first-order annotations embedded at $\{0,\infty\}$, and it must agree with the formal-prover labels on every item. Any disagreement falsifies soundness or completeness of the embedding.
The second check is predictive. Across Metric-ProofWriter depth, the minimal number of Herbrand instances the prover finds should track reasoning depth roughly linearly. Each hop should need one new instance, because Horn-style rules unfold one step at a time. Superlinear growth would indicate that the measure does not capture proof length.
The third check is a boundary test. On deliberately unguarded problems involving $\infty$, the prover should fail to produce certificates exactly where the theory predicts non-admissibility of cut. If Z3 instead "solves" such problems, we will check those answers against hand-derived ground truth.
Metrics are agreement with gold labels, solved rate under timeout, median time, certificate bit-size, and independent certificate-check success. Theory and system succeed together if the Herbrand–Farkas prover matches or beats Z3 on the guarded families while certifying every answer, and if the predicted failures appear exactly at the fragment boundary.
References
- Propositional Logics for the Lawvere Quantale
- A Short and Readable Proof of Cut Elimination for Two First-Order Modal Logics
- Intrinsic Complexity of Recursive Functions on Natural Numbers with Standard Order
- Punctual Presentability in Certain Classes of Algebraic Structures
- Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoning
- LINC: A Neurosymbolic Approach for Logical Reasoning by Combining Language Models with First-Order Logic Provers
- Logical-SAGE: A Logical Socratic Architecture for Guided Evolution in Neuro-Symbolic Reasoning
- FOLIO: Natural Language Reasoning with First-Order Logic