Propositional Logics for Lawvere Quantale

Tools

Bacci, Giorgio and Mardare, Radu and Panangaden, Prakash and Plotkin, Gordon D.; (2023) Propositional Logics for Lawvere Quantale. In: 39th Conference on Mathematical Foundations of Programming Semantics MFPS XXXIX. Proceedings - Symposium on Logic in Computer Science . EPI SCP, USA.

[thumbnail of Propositional Logics for Lawvere Quantale]
Preview
 Text. Filename: Propositional_Logics_for_Lawvere_Quantale.pdf
Final Published Version
License: Creative Commons Attribution 4.0 logo
Download (256kB)| Preview

Abstract

Lawvere showed that generalised metric spaces are categories enriched over [0,∞], 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 (closely related) many-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. Propositional Boolean logic can already be interpreted in the first of these logics; Łukasiewicz logic can be interpreted in the second; Ben Yaacov's continuous propositional logic can be interpreted in the third; and quantitative equational logic can be interpreted in the third 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 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 for theories over finitely-many propositional variables; indeed even an approximate form of strong completeness in the sense of Ben Yaacov -- provability up to arbitrary precision -- does not hold. However, we can show it for such theories having only models never mapping variables to ∞; the proof uses Hurwicz's general form of the Farkas lemma.

CORE (COnnecting REpositories)