💻 computer science

Compact Quantitative Theories of Convex Algebras

This paper introduces the concept of compact quantitative equational theories, proving that the theory of interpolative barycentric algebras is compact and using this result to derive other compact theories that axiomatize distances on finitely supported probability distributions.

Original authors: Matteo Mio

Published 2026-03-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Matteo Mio

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a judge in a courtroom where the laws of physics are slightly fuzzy. In this world, things aren't just "equal" or "not equal." Instead, two things can be "almost equal," or "very close," or "somewhat different." This is the world of Quantitative Algebra.

In this paper, the author, Matteo Mio, tackles a specific problem: How do we write down rules for this fuzzy world so that we can prove things without getting stuck in an infinite loop?

Here is the story of the paper, broken down into simple concepts and analogies.

1. The Problem: The Infinite Ladder

In normal math (like high school algebra), if you want to prove that $A = B$ , you write down a finite list of steps. It's like climbing a ladder with a fixed number of rungs. Once you reach the top, you're done.

But in this "fuzzy" world, things are trickier. Sometimes, to prove that two things are "close enough" (say, within a distance of 0), you might need to check if they are within 0.1, then 0.01, then 0.001, and so on, forever.

The Analogy: Imagine trying to prove a car is parked exactly at the curb. You check if it's within 1 meter. Then 10 centimeters. Then 1 millimeter. To prove it's exactly at the curb, you might feel like you need to check an infinite number of smaller and smaller distances.
The Issue: In computer science, we love finite things because computers can't handle infinite loops. If a proof requires an infinite ladder, a computer can't verify it.

2. The Solution: "Compact" Theories

The author introduces a special kind of rulebook called a Compact Quantitative Theory.

The Metaphor: Think of a "Compact" theory as a magic shortcut. Even though the rules of the fuzzy world allow for infinite steps, a "Compact" theory guarantees that for any true statement, there is a finite way to prove it. You don't need the infinite ladder; you can jump straight to the top using a clever shortcut.

The paper asks: Are there useful rulebooks for this fuzzy world that are "Compact"?

3. The Star Character: The "Mixing" Machine

The paper focuses on a specific type of structure called Convex Algebras.

The Analogy: Imagine a machine that takes two ingredients (like red paint and blue paint) and mixes them together.
- If you mix 50% red and 50% blue, you get purple.
- If you mix 90% red and 10% blue, you get a reddish-purple.
- This machine can mix any amount.
The Application: This isn't just about paint. It's about Probability Distributions. Imagine you have a bag of marbles. You can describe the bag as "50% red, 50% blue." You can mix two bags together to make a new bag. The math of mixing these bags is what the paper studies.

4. The Big Discovery: The "Kantorovich" Bridge

The author proves that the rules for mixing these probability bags (specifically, the Interpolative Convex Algebras) are Compact.

The Story:
1. We have a way to measure how "different" two bags of marbles are. This is called the Kantorovich distance (or Wasserstein distance). Think of it as the "cost" of moving marbles from one bag to another to make them look the same.
2. Usually, calculating this cost involves looking at every possible way to move the marbles (couplings) and finding the cheapest one. This sounds like it could be an infinite calculation.
3. The Breakthrough: The author shows that even though the math looks like it needs an infinite search, the rules of the game are so well-behaved that you can always find the answer with a finite proof.
4. Why? Because the set of all possible ways to move the marbles forms a "compact" shape (in the mathematical sense, like a closed, bounded box). In such a shape, the "cheapest" move is always a real, reachable point, not a ghostly limit that you can never quite touch.

5. The Family of Solutions

The paper doesn't just stop at the standard mixing rule. The author generalizes this to create a whole family of compact theories.

The Analogy: Imagine you have a standard recipe for mixing paint (50/50). The author shows you can change the recipe to:
- The "Max" Recipe: The color of the mixture is determined by the strongest color present (like a light switch).
- The "Power" Recipe: The mixture follows a specific curve (like $k$ -Wasserstein distance), useful for different types of data.
- The "Log" Recipe: Useful for things like log-probabilities in computer science.
The Result: For all these different "mixing recipes," the author proves that the rulebooks are Compact. You can always prove things about them using finite steps.

Summary: Why Should You Care?

This paper is like finding a universal key for a very complex lock.

For Mathematicians: It proves that a huge class of fuzzy, probabilistic systems are "tame" and can be reasoned about logically.
For Computer Scientists: It means we can build software tools (like automated theorem provers) to verify programs that deal with probabilities, randomness, and uncertainty, because we know the proofs won't get stuck in infinite loops.

In a nutshell: The author took a messy, potentially infinite world of fuzzy math, found a specific, well-behaved corner of it (mixing probabilities), and proved that you can navigate that corner using only finite, manageable steps. This makes it possible for computers to understand and verify complex probabilistic systems.

1. Problem Statement

The paper addresses a fundamental limitation in Quantitative Algebra, a field extending universal algebra to structures equipped with a metric or fuzzy relation.

The Context: In standard universal algebra (Birkhoff's system), proofs are finite trees, allowing for effective mechanization and enumeration. In contrast, the deductive system for quantitative algebras (introduced in [22] and generalized in [27]) relies on infinitary logic ( $L_{\omega_1, \omega}$ ).
The Issue: The proof system includes an infinitary rule (often called the Archimedean or continuity rule) that allows deriving a bound $\epsilon = \inf \{\epsilon_i\}$ from an infinite sequence of bounds $\epsilon_i$ . Consequently, proofs are generally infinite objects (well-founded trees with countable width).
The Challenge: Infinite proofs hinder mechanization and practical application. The paper asks: Are there specific, well-behaved quantitative theories where all semantic consequences can be derived using only finite proofs (i.e., without invoking the infinitary rule)? Such theories are termed compact.

2. Methodology

The author employs a rigorous algebraic and topological approach within the framework of fuzzy relations (generalizing metric spaces).

Framework: The work utilizes the generalized quantitative algebra apparatus from [27], where algebras are equipped with arbitrary fuzzy relations $d: A \times A \to [0, 1]$ rather than strict metrics.
Target Theory: The focus is on Interpolative Convex Algebras (ICA), which axiomatize the behavior of probability distributions and the Kantorovich (1-Wasserstein) metric.
Proof Strategy:
1. Soundness & Completeness: Establish that the syntactic consequence relation ( $\vdash$ ) corresponds to the semantic consequence ( $\models$ ) via the Kantorovich lifting of distances.
2. Lifting Mechanism: Define the distance between two probability distributions $\mu, \nu$ as an infimum over couplings (joint distributions): $K(d)(\mu, \nu) = \inf_{\gamma \in \Gamma(\mu, \nu)} V_d(\gamma)$ .
3. Compactness Argument: The core of the proof relies on topological compactness. The set of couplings $\Gamma(\mu, \nu)$ is shown to be a compact topological space. The evaluation function $V_d$ is continuous. By the Extreme Value Theorem, the infimum is always attained by an optimal coupling $\gamma^*$ .
4. Elimination of Infinitary Rules: Because the infimum is attained, one does not need an infinite sequence of approximations to derive the bound; a single finite proof using the optimal coupling suffices.

3. Key Contributions

A. Definition of Compact Quantitative Theories

The paper formally defines a compact quantitative equational theory as one where every derivable judgment $E \vdash \phi$ admits a finite proof (a proof tree that never uses the infinitary rule).

B. Proof of Compactness for Interpolative Convex Algebras (ICA)

The main result is the proof that the theory of Interpolative Convex Algebras is compact.

The Theory (ICA): Includes axioms for convex algebras (idempotency, skew-commutativity, skew-associativity) and interpolative axioms that relate the distance of convex combinations to the distances of their components.
The Result: The free ICA-algebra generated by a fuzzy relation $(A, d)$ is isomorphic to the algebra of finitely supported probability distributions $(D(A), K(d))$ , where $K(d)$ is the Kantorovich lifting.
Mechanism: The proof demonstrates that for any two terms $s, t$ , if the semantic distance $K(d)([s], [t]) \leq \epsilon$ , there exists a finite proof of $s =_\epsilon t$ . This is achieved by constructing a finite derivation based on the optimal coupling that achieves the infimum in the Kantorovich distance definition.

C. Generalization to a Family of Compact Theories

The author generalizes the result beyond the standard linear convex combination ( $x \oplus_p y = px + (1-p)y$ ).

Generalized Lifting: They define a family of theories $ICA^{\oplus_p}$ parameterized by an arbitrary convex algebra operation $\oplus_p$ on $[0, 1]$ .
Conditions for Compactness: The theory is compact if the operation $\oplus_p$ $\oplus_{p}$ satisfies:
1. Monotonicity.
2. A continuity-like limit condition: $\lim_{\lambda \to 0} (x+\lambda) \oplus_p (y+\lambda) \leq x \oplus_p y$ .
3. Existence of optimal couplings (guaranteed if the evaluation map is lower semicontinuous).
New Examples: This framework yields compact theories for:
- $k$ -Wasserstein distances (for $k \geq 1$ ).
- $\infty$ -Wasserstein distance (using the max operation).
- Log-probability distances (using the geometric mean operation $x^p y^{1-p}$ ).

4. Key Results

Theorem 4.14: The quantitative equational theory of Interpolative Convex Algebras (ICA) is compact.
Theorem 5.3: A generalized theory $ICA^{\oplus_p}$ is compact if the underlying convex algebra on $[0, 1]$ satisfies specific monotonicity, continuity, and optimality conditions.
Corollary 4.13: Completeness with respect to finite proofs holds for ICA. If the semantic distance is bounded by $\epsilon$ , a finite proof exists.
Isomorphism: The free quantitative algebra for these theories is isomorphic to the space of probability distributions equipped with the corresponding lifted distance (Kantorovich, Wasserstein, etc.).

5. Significance

Mechanization: By proving compactness, the paper establishes that these important quantitative theories (crucial for semantics of probabilistic programming, verification, and machine learning) can be mechanized. Finite proofs can be represented, manipulated, and checked by machines, unlike the general infinitary proofs of quantitative algebra.
Unification: It unifies various distance liftings (Kantorovich, Wasserstein $k$ , $\infty$ -Wasserstein, log-probability) under a single algebraic framework of compact theories.
Topological Insight: The work highlights a deep connection between algebraic compactness (finite provability) and topological compactness (existence of optimal couplings in compact spaces). It suggests that the "manageability" of these theories stems from the topological properties of the space of probability distributions.
Future Directions: The paper opens the door to investigating other compact theories (e.g., quantitative semilattices) and exploring the categorical conditions (e.g., on term monads) that guarantee compactness.

In summary, the paper resolves the tension between the necessity of infinitary rules in general quantitative logic and the practical need for finite proofs in specific, important applications, proving that for convex algebras and their generalizations, finite proofs are sufficient.