Propositional Logics for the Lawvere Quantale

Giorgio Bacci, Radu Mardare, Prakash Panangaden, Gordon PlotkinarXiv 2023 · arXiv

This paper, presented at MFPS 2023, explores the intersection of category theory, metric spaces, and formal logic. It provides a rigorous logical foundation for "quantitative reasoning"—moving beyond Boolean true/false to reason about distances and degrees of truth.

TL;DR

The authors develop three new propositional logics interpreted over the Lawvere quantale (the set of non-negative reals $[0, \infty]$). They provide sound and complete natural deduction systems for these logics, using powerful tools from linear algebra, like Farkas’ Lemma, to bridge the gap between syntactic proofs and geometric inequalities.

What Problem Does This Paper Address?

Traditional logic is binary: a statement is either true or false. However, many modern fields—such as probabilistic robotics, neurosymbolic AI, and program verification—need to reason about "how close" two things are.

In the 1970s, William Lawvere showed that generalized metric spaces can be viewed as categories "enriched" over the non-negative reals $[0, \infty]$. While this provided a deep mathematical connection, we lacked a dedicated propositional logic to perform deductions within this framework. Existing fuzzy logics typically operate on the $[0, 1]$ interval. Moving to $[0, \infty]$ (the "Lawvere quantale") requires different connectives—like addition instead of multiplication—and presents unique challenges for proving that a proof system is actually "complete" (i.e., that every true statement can be proven).

Methods

The authors introduce three nested logics:

  1. $\mathbb{L}$ (Basic): Includes standard connectives like conjunction ($\wedge$), disjunction ($\vee$), and "tensor" ($\otimes$, which represents addition in this context), plus linear implication ($\multimap$, which acts as truncated subtraction).
  2. $\mathbb{L}_1$: Adds a constant for the value $1$, allowing the logic to express integer values.
  3. $\mathbb{L}^*$: Adds scalar multiplication by non-negative reals, allowing for general affine combinations of variables.

The core of their approach is a Normalization Algorithm. They show that any judgement in these logics can be reduced to a "normal form" that looks like a linear inequality (e.g., a sum of variables is greater than or equal to a constant).

To prove completeness, they turn to linear algebra. They demonstrate that proving a logical statement is equivalent to showing that one linear inequality is a consequence of others. They use the Motzkin transposition theorem and Farkas’ Lemma—fundamental results in optimization and geometry—as the "engines" for their completeness proofs.

Datasets

Not discussed in the paper. As a theoretical work in mathematical logic, the "evaluation" consists of formal proofs and theorems rather than empirical testing on datasets.

Key Insights and Ideas

  • Linear Algebra as Logic: The most striking insight is the literal use of linear algebraic theorems as completeness results. Usually, these theorems are used to find optimal solutions in economics or engineering; here, they serve as the bridge between syntactic deduction and semantic truth.
  • The Exponential Bridge: The authors show that their logics are related to traditional "Product Logics" on $[0, 1]$ via the mapping $e^{-x}$. However, the $[0, \infty]$ perspective is more natural for "additive" reasoning (like distances) than the "multiplicative" reasoning of probability.
  • Failure of the Deduction Theorem: In classical logic, if you can prove $B$ assuming $A$, then you can prove "If $A$, then $B$." The authors highlight that this fails in their quantitative setting because there is no "cancellation" (you can't always undo an addition in a world with a "bottom" value of $\infty$).
  • Decidability: Despite the continuous nature of the values ($[0, \infty]$), the authors prove that determining if a statement is satisfiable or consistent is decidable using Fourier-Motzkin elimination.

Key Results

  • Soundness and Completeness: They successfully developed natural deduction systems that are complete for all finitely-axiomatized theories.
  • Complexity: They established that checking if a logical consequence holds is co-NP complete, while checking consistency is NP-complete, placing these quantitative logics in the same complexity class as classical propositional logic.
  • Encoding Quantitative Algebra: They showed that "Quantitative Equational Logic" (a framework for reasoning about metric effects in algebra) can be fully embedded into their third logic, $\mathbb{L}^*$.

Limitations and Future Work

  • Strong Completeness: The authors acknowledge that "strong completeness" (the ability to handle infinite sets of assumptions) does not hold in general. They provide a restricted version ("approximate completeness") but only for models that avoid the value $\infty$.
  • Propositional Only: The current work is limited to propositional logic. A major next step is extending this to First-Order Logic (adding quantifiers like "for all" and "there exists"), which would significantly increase its expressive power for AI applications.
  • Polynomial Inequalities: The authors suggest that adding a "product" connective (multiplication of two variables) would be useful. This would move the math from linear algebra to real algebraic geometry, requiring even more sophisticated tools like the Positivstellensatz.

Summary updated

Abstract

Lawvere showed that generalised metric spaces are categories enriched over $[0, \infty]$, the quantale of the positive extended reals. The statement of enrichment is a quantitative analogue of being a preorder. Towards seeking a logic for quantitative metric reasoning, we investigate three $[0,\infty]$-valued propositional logics over the Lawvere quantale. The basic logical connectives shared by all three logics are those that can be interpreted in any quantale, viz finite conjunctions and disjunctions, tensor (addition for the Lawvere quantale) and linear implication (here a truncated subtraction); to these we add, in turn, the constant $1$ to express integer values, and scalar multiplication by a non-negative real to express general affine combinations. Quantitative equational logic can be interpreted in the third logic if we allow inference systems instead of axiomatic systems. For each of these logics we develop a natural deduction system which we prove to be decidably complete w.r.t. the quantale-valued semantics. The heart of the completeness proof makes use of the Motzkin transposition theorem. Consistency is also decidable; the proof makes use of Fourier-Motzkin elimination of linear inequalities. Strong completeness does not hold in general, even (as is known) for theories over finitely-many propositional variables; indeed even an approximate form of strong completeness in the sense of Pavelka or Ben Yaacov -- provability up to arbitrary precision -- does not hold. However, we can show it for theories axiomatized by a (not necessarily finite) set of judgements in normal form over a finite set of propositional variables when we restrict to models that do not map variables to $\infty$; the proof uses Hurwicz's general form of the Farkas' Lemma.
BibTeX
@misc{bacci2023propositional,
  author = {Giorgio Bacci and Radu Mardare and Prakash Panangaden and Gordon Plotkin},
  title = {{Propositional Logics for the Lawvere Quantale}},
  year = {2023},
  eprint = {2302.01224},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2302.01224},
}
Figure