💻 computer science

Case Study: Saturations as Explicit Models in Equational Theories

This paper presents a method to transform saturated clause sets from automated theorem provers into explicit, verifiable infinite countermodels for the unit equational fragment, implements this approach in the Vampire and E provers, and demonstrates its effectiveness on the Equational Theories Project.

Original authors: Mikoláš Janota, Michael Rawson, Stephan Schulz

Published 2026-02-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mikoláš Janota, Michael Rawson, Stephan Schulz

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

The Big Picture: The "Black Box" Problem

Imagine you have a super-smart robot mathematician (called an Automated Theorem Prover or ATP). You give it a puzzle: "If I have these rules, does this new statement follow?"

Sometimes, the robot says, "Yes!" and hands you a long, detailed proof. That's great.

But often, the robot says, "No!" (meaning the statement is false). In the past, when it said "No," it would just hand you a giant, messy pile of notes called a "saturated set."

The Problem: This pile of notes is like a "black box." It proves the statement is false, but it's so complex and opaque that a human (or even a mathematician) can't look at it and say, "Ah, I see! Here is a specific example where the rule breaks." It's like being told a bridge is unsafe because a computer ran a simulation, but the computer won't show you the cracked beam.

The Solution: Turning "Notes" into a "Recipe"

This paper introduces a clever trick to turn that messy pile of notes into something useful: an explicit model.

Think of the "saturated set" not as a proof of failure, but as a recipe for a new world.

The Old Way: The robot says, "I can't prove this bridge is safe." (Useless for understanding why).
The New Way: The robot says, "Here is a recipe. If you build a bridge using these specific instructions, it will definitely collapse."

This "recipe" is called a Rewrite System. It's a set of rules that tells you how to simplify any object you build. If you follow the rules, everything eventually turns into a "standard shape" (a normal form). If two things turn into different standard shapes, they are not equal.

The Analogy: The "Sorting Machine"

Imagine a magical factory with a conveyor belt.

The Input: You throw a weird, complicated machine part onto the belt.
The Rules (The Rewrite System): The belt has a series of robots.
- Robot A says: "If you see a red gear next to a blue gear, swap them."
- Robot B says: "If you see three small springs, replace them with one big spring."
- Robot C says: "If you see a square wheel, turn it into a circle."
The Output: The part travels down the belt, getting simplified over and over until it reaches the end. It can't be simplified any further. This is the Normal Form.

How this solves the math problem:
If you have two different starting parts, and you run them through this factory:

If they both come out as the exact same "Circle," they were actually the same thing deep down.
If one comes out as a "Circle" and the other as a "Triangle," they are definitely different.

The paper shows that the messy "saturated set" the robot mathematician generates is actually just the instruction manual for this factory.

The Real-World Test: The "Equational Theories Project"

The authors tested this idea on a massive project called the Equational Theories Project (ETP).

The Task: There were over 22 million math puzzles about how a single operation (let's call it "Star") behaves.
The Challenge: Many of these puzzles had answers that were infinite.
- Analogy: Imagine trying to find a counter-example in a finite box (like a 20x20 grid). Sometimes, the answer doesn't fit in the box; it requires an infinite hallway.
- Previous tools could only find answers in the "finite box." If the answer was in the "infinite hallway," the tools would get stuck or give up.
The Result: The authors modified the robot mathematicians (Vampire and E) to output their "factory instructions" (the rewrite systems).
- They found 108 problems where the answer was an infinite model that no one could find before.
- They generated the "recipe" for these infinite worlds.

The "Trust" Factor: Certified Checkers

You might ask: "How do we know the robot didn't make a mistake in the recipe?"

The authors didn't just trust the robot. They took the generated recipes and fed them into independent, certified tools (like CSI and TTT2). These tools are like strict inspectors who verify:

Termination: "Does this factory ever get stuck in an infinite loop?" (No, it always finishes).
Confluence: "Does it matter which robot works first? Do we always get the same final shape?" (Yes, the result is consistent).

Because these independent tools passed the check, the "infinite models" are now trustworthy certificates.

Why This Matters

Transparency: Mathematicians can finally see why a rule fails. They aren't just told "it's false"; they are given a concrete example (the model) to study.
Infinite Worlds: It allows us to understand structures that are too big to fit in a computer's memory as a list, but easy to describe as a set of rules.
Collaboration: It bridges the gap between human mathematicians (who want to understand why) and AI (which is great at finding that something is true or false).

In short: The paper teaches us how to translate the robot's confusing "internal notes" into a clear, checkable "instruction manual" that explains exactly why a mathematical rule fails, even when the failure happens in an infinite universe.

1. Problem Statement

Automated Theorem Provers (ATPs) like Vampire and E are highly effective at disproving conjectures in first-order logic by saturating a set of clauses (deriving all logical consequences until no new non-redundant clauses can be found). However, when a conjecture is false, the resulting saturated set serves as an implicit certificate of satisfiability (a counter-model) but is often opaque and unwieldy for human interpretation.

The Gap: While finite counter-models can be generated by Finite Model Builders (FMB), many algebraic structures require infinite counter-models. Current ATPs do not emit explicit representations of these infinite models.
The Challenge: In the context of the Equational Theories Project (ETP), which classifies implications between universally quantified equalities, hundreds of cases were found to be non-theorems that admit only infinite counter-models. Existing tools could not provide a readable, explicit certificate for these cases, hindering mathematical classification and verification.

2. Methodology

The authors propose a method to extract an explicit, potentially infinite model directly from the saturated set of clauses produced by saturation-based ATPs, specifically within the unit equational fragment (universally quantified equations and ground disequations).

A. Theoretical Foundation

The method relies on the observation that a saturated set of equations in this fragment, derived using calculi based on unfailing completion or superposition, can be interpreted as a convergent (confluent and terminating) rewrite system.

Domain: The Herbrand universe (the set of all ground terms constructed from the signature).
Equality Relation: Two ground terms $s$ and $t$ are considered equal in the model if and only if they reduce to the same normal form under the rewrite system defined by the saturated set.
Normalisation: A computable function $\lfloor t \rfloor$ is defined to rewrite a term $t$ until a fixed point is reached. Since the underlying term ordering is well-founded, this process terminates.

B. Implementation

The authors implemented this extraction logic in two major ATPs: Vampire and E.

Modification: The provers were modified to output the saturated set as a set of rewrite rules ( $l \to r$ ) rather than just a list of clauses.
Pre-ordering Check: For the rewrite system to be directly usable, the equations must be "pre-ordered" (i.e., for every equation $l \approx r$ in the saturation, the internal term ordering must satisfy $l \succ r$ ). If this condition holds, the set forms a valid convergent rewrite system.

C. Verification Pipeline

To ensure the trustworthiness of the generated models, the authors established an external verification pipeline:

Extraction: The ATP outputs the rewrite system.
Confluence Check: The tool CSI checks if the system is confluent (ensuring unique normal forms).
Termination Check: The tool TTT2 checks if the system terminates.
Certificate Generation: Both tools generate certificates verifiable by CeTA (a certified tool based on the Isabelle/HOL library IsaFoR).

3. Key Contributions

Explicit Model Construction: The paper provides a full, detailed construction of how to read a saturated set of unit equations as an explicit, potentially infinite model, bridging the gap between opaque ATP output and human-readable mathematical objects.
Tool Implementation: The authors successfully integrated this extraction mechanism into Vampire and E, enabling them to emit these models.
Certified Verification: They demonstrated that these extracted models can be independently verified for confluence and termination using certified tools, providing a high degree of trust in the counter-examples.
Application to ETP: The method was applied to the Equational Theories Project, successfully handling cases where finite model builders failed.

4. Results

The authors applied their method to the Equational Theories Project (ETP), which involves over 22 million implications between equalities over a single binary operation.

Dataset Analysis:
- Out of 304 problems refuted only by saturation (where FMB failed), 196 were proven to have no finite counter-models (Infinox).
- The remaining 108 might have finite models, but none were found by FMB.
Extraction Success:
- Of the 304 saturation-only cases, 261 had "pre-ordered" equations, meaning the saturated set directly formed a valid rewrite system without needing re-orientation.
Verification Success:
- All 261 extracted rewrite systems were successfully verified by CSI (confluence) and TTT2 (termination).
- This yielded 261 fully certified, explicit counter-models for problems that previously had no explicit certificates.
Limitations:
- 43 cases had unoriented equations (where $l \not\succ r$ for some rules), making automatic verification of confluence/termination difficult with current tools, though a model could still theoretically be constructed.

5. Significance

Trust in ATPs: By converting opaque saturation sets into explicit, externally verifiable rewrite systems, the authors significantly increase the trustworthiness of ATP results, particularly for non-specialists (e.g., mathematicians) who need to understand why a conjecture fails.
Handling Infinite Structures: The work solves a critical bottleneck in algebraic classification where finite model builders are insufficient, and infinite models are required.
Reproducibility: The use of certified tools (CeTA) ensures that the counter-models are mathematically sound, independent of the internal complexity of the ATPs.
Future Directions: The paper suggests that this approach could be extended to richer logics (like Horn clauses) and that the resulting rewrite systems could potentially be used to construct large finite models or be exported to proof assistants like Lean for formal verification.

In summary, this paper transforms the "black box" output of saturation-based theorem provers into transparent, mathematically rigorous certificates, specifically enabling the classification of algebraic structures that require infinite counter-examples.