Proving at Scale for Universal Algebra
João Araújo, Jan Hůla, Mikoláš Janota, Edmond W. H. Lee, Bartosz Naskręcki
cs.LO
Oct 1, 2026 · v2
math.GR
TL;DR
LLM agents generate Lean 4 proofs certifying finite identity bases or non-finite-basability for all semigroups of order at most 6, kernel-checked in a final audit.
Abstract
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 single first-order validity query. LLM-guided agents search for these proofs; a referee agent rebuilds them from source, and the Lean kernel checks the resulting corpus in a final audit. Humans choose targets and approve final outcomes. We certify every semigroup of order at most 6: all 1309 semigroups of order at most 5 and all 15973 of order 6, including proofs that the four known nonfinitely based semigroups have no finite basis. The bases for order 6 define 505 distinct varieties, whose inclusion order Vampire determines except for four pairs. The resulting catalogue is a machine-checked account of results scattered across the literature and a tested foundation for order 7.
Problem
Tarski's finite basis problem asks whether all identities of a finite algebra follow from finitely many. It is undecidable for general finite algebras and open for finite semigroups. No machine-checked catalogue of finite bases for small semigroups existed.
Approach
Codex worker and coordinator agents, together with a Claude referee agent, search for candidate identity bases and counter-models. They then write completeness proofs or non-finite-basis proofs in Lean 4. A scripted deterministic pipeline settled 94% of classes, and agents handled the remaining 984. The referee rebuilds proofs from source, the Lean kernel audits the whole corpus, and humans only choose targets and approve pushes.
Results
All 1,309 semigroups of order at most 5 and all 15,973 of order 6 are certified. This includes Lean proofs that the four known nonfinitely based order-6 semigroups have no finite basis. The order-6 bases define 505 varieties, whose inclusion order Vampire determines except for four pairs.
| Order | Semigroups | Nilpotent | 3-nilpotent |
|---|
| 4 | 126 | 10 | 8 |
| 5 | 1,160 | 93 | 84 |
| 6 | 15,973 | 2,813 | 2,660 |
| 7 | 836,021 | 616,830 | 609,797 |
Number of distinct semigroups per order and nilpotent counts