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:
- $\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).
- $\mathbb{L}_1$: Adds a constant for the value $1$, allowing the logic to express integer values.
- $\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