Universal algebra studies algebraic structures (groups, rings, lattices, modules, Boolean algebras, ...) through what they have in common: a set with finitely-ary operations. Its first structural theorem is Birkhoff's HSP theorem (Birkhoff 1935). It says that the classes of algebras that can be axiomatized by equations (groups, rings, lattices, but not fields or integral domains) are exactly the classes closed under three constructions: homomorphic images, subalgebras and direct products. This links syntax (identities) with semantics (closure properties). It is the base of equational logic, of the theory of varieties, and of later results such as Jónsson's lemma and Mal'cev conditions.
Timeline. Birkhoff (1935) proved the characterization and introduced free algebras relative to a class. Tarski (1946) showed that the variety generated by a class is obtained by applying the three operators once each, in the order . The textbook treatment that this mission follows is Burris–Sankappanavar (B&S), Ch. II §§9–11. The theorem has a machine-checked proof in Agda (DeMeo–Carette 2021), but there is none in Lean or Mathlib.
Fix a signature , a Mathlib first-order language L : Language.{u, v} with no relation symbols ([L.IsAlgebraic]). An algebra (Alg L) is a type in Type u with an L.Structure, i.e. an interpretation of each -ary function symbol as an -ary operation. A class of algebras is a K : Set (Alg L).
L.Term X) is the set of terms over variables . It is an algebra, the term algebra, where the operation for builds the term . A term is evaluated in under an assignment as p.realize v.Congruence A) is an equivalence relation that is compatible with every operation, and (φ.Quot) is the quotient algebra.Type u, the empty product included. Closure under isomorphism () is built into all three.IsVariety K) if , and . (V K) is the intersection of all varieties containing .Satisfies A (p, q)) means that and take the same value under every assignment. For a set of identities over the variables , (Mod E) is the class of algebras satisfying all of . (Id K) is the set of identities over true in every member of .freeCong K X) is the intersection of all congruences on with . The free algebra is (freeAlg K X). It has generators (freeGen K X x), and (freeMk K X p) is the class of a term .For every class of algebras,
This combines B&S Thm. 11.9 (equational classes are exactly the varieties) with Lemma 11.8 (a variety is axiomatized by its identities in countably many variables). The form with is the strongest natural one: it names the axioms explicitly instead of asserting that some set exists.
The milestones follow the proof in B&S Ch. II.
The result. The HSP theorem is the entry point of the theory of varieties. It makes "the variety of groups", "the variety generated by a finite algebra" and "the free algebra of a variety" precise and interchangeable, and it reduces questions about equational theories to closure properties of classes. Downstream results such as Jónsson's lemma for congruence-distributive varieties, Mal'cev characterizations of congruence permutability, and Birkhoff's subdirect representation all assume this framework.
Formalizing it. The theorem has been proved since 1935 and formalized in Agda, but Mathlib has no varieties, no class operators, no congruence lattices of general structures and no relatively free algebras. This mission supplies those foundations on top of Mathlib's ModelTheory library, so that later universal-algebra missions can import them rather than rebuild them.
The direction (⇐) is routine: identities survive images, subalgebras and products. The difficulty is (⇒): showing that an algebra satisfying every identity of a variety actually lies in . The naive idea, quotienting the term algebra by " proves ", does not by itself place the quotient in . One needs the free algebra in (M4), which needs a product indexed by a family of congruences, and a free algebra on enough generators to cover . There are also size issues: generators indexed by itself, terms over arbitrary variable types, and the reduction of identities over any variables to identities over because terms are finite. All of this has to be done in one universe so that the free algebra stays in Alg L. Tarski's (M2) needs explicit constructions, such as products of homomorphic images, which use choice, and products of products.
CategoryTheory.Bundled L.Structure in a single universe Type u, with L : Language.{u, v}, so terms over a type in Type u stay in Type u. All theorem statements assume [L.IsAlgebraic], as in B&S, where types are purely functional.Type u.Term, realize, homomorphisms →[L], embeddings ↪[L], equivalences ≃[L] and the quotient structure from Prestructure. It adds the term-algebra and product structures, Congruence, the operators, identities and free algebras. These are reusable beyond this mission. The congruence type is intended for reuse in congruence-lattice results (Jónsson's lemma, Mal'cev conditions).Congruence, the operator inequalities of Lemma 9.2, and renaming of variables in identities.MSKleene_Core) is not Mathlib-compatible and is not used here.namespace UAVariety
variable {L : FirstOrder.Language.{u, v}} [L.IsAlgebraic]
/-- Birkhoff's HSP theorem (B&S Thm 11.9 with Lemma 11.8): a class of algebras is a
variety iff it is the class of models of its own identities over countably many variables. -/
theorem birkhoff_hsp (K : Set (Alg L)) : IsVariety K ↔ K = Mod (Id K) := by sorry
end UAVariety is a signature without relation symbols; an algebra is a type in Type u with an -structure (Alg L), and is a class of algebras. , , are the classes of homomorphic images, of algebras embeddable in, and of algebras isomorphic to direct products (over any index type in Type u, possibly empty) of members of ; is a variety if it is closed under , and . means and agree under every assignment of the variables in ; is the class of algebras satisfying every identity in (identities over the variables ), and the set of identities over true in every member of . A class of algebras is a variety if and only if .
No open leaves. Every sub-goal is proved or awaiting decomposition.