Skip to content
Preprint

Trace-Tree Magmas: Proof-Producing Infinite Countermodels and 28 New Order-Five Austin Classifications

Sep 2026 · 0 citations · 33 references
Computer Science Mathematics

TL;DR

To the best of this audit, this is the first automated system to synthesize this trace-tree model family, generate well-founded inversion proofs, and emit self-contained Lean 4 certificates.

Abstract

Finite model finders cannot witness an Austin law: an identity whose finite models are all trivial but which has a nontrivial infinite model. We introduce rank-decreasing sparse trace-tree magmas, finitely presented total operations on a countably infinite constructor-tree carrier. The default product pairs its arguments; finitely many positive Horn clauses define exceptions. Our main procedure derives clauses from symbolic evaluation traces. For every model found, it proves functionality of the exceptional relation by descent on constructor size, proves the identity by exhaustive symbolic case analysis, and emits a self-contained Lean 4 certificate. A least simultaneous fixed point gives an implementation-independent semantics, so bounded search may miss models but cannot invalidate certified results. On ETP's 96 order-five Austin candidates, we discover and Lean-verify infinite countermodels for 28 identities with no prior public classification in our audit. They form 14 duality classes and establish 28 new Austin classifications. Four ALPS-known cases bring the total to 32 certified candidates. On Canonical-4187, the deduplicated union of Order5-130 and the 4,141-row ALPS pool, a fresh trace run produces 636 certificates, all accepted by Judge v3. At equal resource limits, Vampire 5.0.1, E 3.5.1, and complete Twee 2.6.1 jointly prove implications in 94 canonical classes. Only Twee returns trusted counter-satisfiable outcomes, for 18 classes; independent finite-side certificates force 16 to be infinite. None of these ATPs emits an explicit model or Lean certificate, and none decides the 28 new classifications. To the best of our audit, this is the first automated system to synthesize this trace-tree model family, generate well-founded inversion proofs, and emit self-contained Lean 4 certificates.

View source

Similar papers

Preprint Oct 2026

Proving at Scale for Universal Algebra

We introduce SemiBase, a project that computes and formally certifies finite identity bases for small semigroups. Deciding finite basability is undecidable for finite algebras and remains open for finite semigroups. The task requires a proof that a candidate basis is complete, or a proof that none exists, rather than a...

João Araújo, Jan Hůla, Mikoláš Janota et al. · 0 citations
#artificial intelligence Preprint Aug 2026

Verification abundance, adjudication scarcity: what happens to mathematical knowledge when proof checking becomes free

It is argued that machine checking produces verification abundance while leaving adjudication scarce, and proposes a six-category taxonomy of representational mismatch, a disclosure schema for machine-generated mathematical claims, and implications for software, cryptography, and regulated decision systems.

Maher Kallel, Mohamed El Louadi · 0 citations
#machine learning Preprint Sep 2026

Characterizing Language Generation in the Limit: Finite Witnesses and a Separation-Width Hierarchy

This work describes language generation in the limit for arbitrary families over a countable universe and describes the characterization and full width hierarchy, including the simplified normalization and a direct diagonal capture lemma.

Xiao-Yu Li, Andi Han, Jiao-Jiao Jiang et al. · 1 citation · ⚡1
Sep 2026

Efficient Branch-and-Bound Testing and Verification of zkVMs

ZEBRA is a fully automated verification and bug-detection framework that reduces zkVM verification to a solution-set cardinality problem over a canonical trace space, where redundancies such as null-row padding and non-deterministic permutations are eliminated prior to counting.

Hideaki Takahashi, Suman Jana, Junfeng Yang · 0 citations

Checking Leakage Witnesses versus Certifying Bounded Non-Leakage

When a language-model audit finds no leak, what is needed to certify non-leakage? We study guarantees over a declared prompt domain under an executable leakage criterion and decoding rule. For general bounded polynomial-time evaluators, a supplied leaking execution is polynomial-time checkable, while leak existence is...

Chao Feng, Burkhard Stiller · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.