Metric Equational Theories

Radu Mardare, Neil Ghani, Eigil Rischel · 2025

Read Metric Equational Theories by Radu Mardare, Neil Ghani, Eigil Rischel (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-14094.txt.

Introduction

Radu Mardare, Neil Ghani, and Eigil Rischel build proof systems for metric algebra in a 2025 logic paper. Quantitative equational theories let equations carry distances. Two terms are not just equal but equal up to a tolerance. That suits systems where approximate equality is the honest notion. Their operations, however, only accept finite arities.

Metric equational theories remove that limit. Operation arities are now countable metric spaces, an extension inspired by enriched Lawvere theories. A subtlety appears, since a term's validity can no longer be certified apart from the equations. The authors solve exactly that problem. Adapting the sound and complete proof system known for the quantitative theories, they deliver deduction rules for the metric setting. The rules are both trustworthy and complete, exploiting the special structure of metric spaces.

Catalog record

CREATORRadu Mardare, Neil Ghani, Eigil Rischel
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE62 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-14094

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Metric Equational Theories Radu Mardare, Neil Ghani, Eigil Rischel Abstract This paper proposes appropriate sound and complete proof systems for algebraic structure over metric spaces by combining the development of Quantitative Equational Theories (QET) with the Enriched Lawvere Theories. We extend QETs to Metric Equational Theories (METs) where operations no longer have finite sets as arities (as in QETs and in the general theory of universal algebras), but arities are now drawn from countable metric spaces. This extension is inspired by the theory of Enriched Lawvere Theories which suggests that the arities of operations should be the λ \lambda -presentable objects of the underlying λ \lambda -accessible category. In this setting, the validity of terms in METs can no longer be guaranteed independently of the validity of equations, as it is the case with QET. We solve this problem, and adapt the sound and complete proof system for QETs to these more general METs, taking advantage of the specific structure of metric spaces. 1 Introduction Recently, Mardare et al [ 16 , 17 ] introduced Quantitative Algebra (QA) and Quantitative Equational Theories (QETs) to extend one of the central pillars of modern mathematics, namely universal algebra (UA), from the exact world to the approximate world. Central to their work was the introduction of approximate equations s=_{\epsilon}t (for a positive real \epsilon ), formalising the intuition that \epsilon measures the behavioural similarity between terms s and t . The generality of this new idea —replacing Boolean reasoning within equational logic with a more refined approximate form of reasoning— gives us a new paradigm which supports a rigorous logical framework for a proper approximation theory, where bounds can be handled, convergences proven, and limits approximated. Quantitative Equational Theories [ 16 ] have been used to provide simple axiomatic presentations of well-behaved metrics for several fundamental computational structures, e.g. the Kantorovich-Wasserstein metrics (resp. Hausdorff metrics) arise from convex structures (resp. semi-lattices). Further, Quantitative Algebra and Quantitative Equational Theories have been shown to have good meta-theoretic properties. For example, variety and quasi-variety results have been proven for Quantitative Algebra [ 17 ] , revealing new insights of approximated reasoning. Similarly, compositionality principles have been studied for Quantitative Algebra, providing a formal tool to control the error propagation when computational systems interact [ 6 , 7 ] . Further work was done in the direction of developing products and coproducts, and tensors of QETs [ 8 ] . Conway and iteration theories have also been generalised to the quantitative case, to cover not only exact fixed-points x=f(x) , but also approximate fixed-points x=_{\epsilon}f(x) [ 18 ] . However, there remains a fundamental unanswered question: What is the natural format/foundation for presenting algebraic structure in a metric setting? In the setting of traditional universal algebra, there are strong results which (when adapted to the metric setting) form desiderata for any answer to the above question. These include: (i) every equational theory supports a sound and complete proof system inducing a congruence between terms; (ii) every such theory induces a finitary monad on the category of \mathsf{Set} which generates free algebras from generator sets; (iii) the models of an equational theory are the Eilenberg-Moore algebras of the associated finitary monad; and (iv) every finitary monad on \mathsf{Set} arises via this construction. Unfortunately, QETs fail these desiderata. For example, the monad mapping a metric space to its Cauchy completion does not arise from a QET —we discuss this example in section 7 . However, the above desiderata may be framed in terms of enriched Lawvere Theories, following [ 21 ] , while turning from the case of sets with algebraic structures to metric spaces with algebraic structures. But there is a fundamental problem in doing so: the category \mathsf{Met} of extended metric spaces is not locally finitely presentable but countably presentable. This means that the arities of operators and equations will not be finite sets (as for traditional algebraic theories), nor countable (discrete) metric spaces, and we will have to consider countably-presentable monads in the desiderata above. The good news is that, once these changes have been made, the work of [ 10 , 21 ] seems to give us exactly what we need. That is i) a notion of algebraic theory consisting of operations and equations; ii) free algebras for such algebraic theories correspond to countably presentable enriched monads on \mathsf{Met} such that the models of the former are the Eilenberg-Moore algebras of the latter; and iii) a notion of Lawvere theory giving a syntax-free presentation of algebraic theories. The bad news is that the presentations one gets from this framework, while theoretically elegant, are very cumbersome to the point of being of little practical use. In particular, given a countably presentable monad, the associated algebraic theory has as operators of a given arity all elements of the monad applied to that arity. In the case of the Cauchy completion, where we would like one operator, we get a countably infinite number of operators. A further limitation of the enriched Lawvere theories is that they don’t cover sound and complete proof systems. This paper, therefore, starts from the premise of wanting the best of both worlds, i.e., the theoretical clarity of Lawvere theories and the concise presentations and proof systems of QETs. Thus, we introduce Metric Equational Theories which extend QETs by allowing operators to have countable metric spaces as arities. This allows us to cover, for example, the countable presentable Cauchy Completion monad. This generalisation, however, creates a difficulty. In both traditional equation theories and QETs, one can first define the terms and then use the terms in equations. This is no longer possible with METs, as metric arities require the use of equations in defining the terms, as some terms might only be defined given that their subterms satisfy certain equations. However, once we devise mechanisms for handling this increased complexity in METs, we will indeed get all of the above desiderata when suitably generalised to \mathsf{Met} , together with sound and complete proof systems for deriving the equality between terms. Outline of the paper. In section 2 we present aspects of the category theory of metric spaces, and the theory of enriched Lawvere theories as it specializes to this case. In section 3 we introduce the Metric Equational Theories, their categories of models, and proving basic properties of these. In section 4 , we construct a free-forgetful adjunction for each MET, and prove that these correspond to enriched Lawvere theories. In section 5 , we carry out the other direction, constructing for each enriched Lawvere theory \mathcal{T} over \mathsf{Met} an MET whose category of models is equivalent to Mod(\mathcal{T}) . Finally, we prove a completeness theorem for METs in section 6 , discuss the MET of Cauchy completeness in section 7 , and consider some special classes of METs and study their corresponding monads in section 8 —in particular, we characterize the class of monads axiomatized by ordinary QETs. The paper includes an Appendix containing details proof os some of the results presented. 2 Enriched Lawvere theories in \mathsf{Met} Our focus is on the category \mathsf{Met} where the objects are extended metric spaces , i.e., sets X equipped with a metric d:X\times X\to[0,\infty] ;

Read the complete text