Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Algebras, term algebras, products, congruences, the operators H, S, P, varieties, identities and free algebras

Definition
UAVariety_defs

by Alien60 · Nov 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

equational-logicfree-algebrasmodel-theoryuniversal-algebravarieties

Alg L: bundled LLL-structures on types in Type u. termStructure: the term algebra T(α)T(\alpha)T(α) (operations build terms, no relations). piStructure: direct products with coordinatewise operations. Congruence M: an equivalence relation on MMM compatible with all operations (and relations); φ.Quot is the quotient algebra M/φM/\varphiM/φ with Mathlib's quotient structure. H K, S K, P K: homomorphic images, algebras embeddable in, and algebras isomorphic to products (index type in Type u, possibly empty) of members of KKK. IsVariety K: closed under HHH, SSS, PPP; V K: intersection of all varieties containing KKK. Satisfies A (p, q): A⊨p≈qA\models p\approx qA⊨p≈q; Mod E and Id K for identities over N\mathbb NN. freeCong K X =θK(X)=\theta_K(X)=θK​(X), the intersection of all congruences φ\varphiφ on T(X)T(X)T(X) with T(X)/φ∈S(K)T(X)/\varphi\in S(K)T(X)/φ∈S(K); freeAlg K X =T(X)/θK(X)=T(X)/\theta_K(X)=T(X)/θK​(X), with freeMk (class of a term) and freeGen (class of a variable).

Definition code
import Mathlib.ModelTheory.Bundled
import Mathlib.ModelTheory.Quotients

/-!
# Varieties, identities and free algebras (Burris–Sankappanavar, Ch. II §§9–11)

Setting for Birkhoff's HSP theorem, built on Mathlib's first-order model theory.

* An *algebra* of signature `L` is a bundled `L.Structure` on a type in the fixed universe
  `Type u` (`Alg L`).  Statements about algebras assume `[L.IsAlgebraic]` (no relation
  symbols), as in B&S; the definitions themselves make sense for any `L`.
  Unlike B&S, empty carriers are allowed (Mathlib convention).
* `L.Term α` carries the *term algebra* structure (B&S Def 10.4), and `∀ i, M i` the
  *direct product* structure (B&S Def 7.1).
* `Congruence M` is an equivalence relation compatible with the operations (B&S Def 5.1),
  and `Congruence.Quot φ` is the quotient algebra `M/φ`, with the structure from Mathlib's
  `Prestructure`/`quotientStructure`.
* The class operators `H`, `S`, `P` of B&S Def 9.1 have closure under isomorphism (`I`)
  built in: `H K` = homomorphic images, `S K` = algebras isomorphic to a subalgebra,
  `P K` = algebras isomorphic to a direct product (indexed by any `ι : Type u`, the empty
  product included) of members of `K`.
* `IsVariety K` (B&S Def 9.3) and `V K` = the smallest variety containing `K` (Def 9.4).
* `Satisfies A (p, q)` = `A ⊨ p ≈ q` (Def 11.1); `Mod E` = the class of models of a set `E`
  of identities in the variables `ℕ` (Def 11.7); `Id K` = the identities over `ℕ` true in
  every member of `K`.
* `freeCong K X` = `θ_K(X)` = the intersection of all congruences `φ` on the term algebra
  `T(X)` with `T(X)/φ ∈ IS(K)`, and `freeAlg K X` = `F_K(X̄) = T(X)/θ_K(X)` (B&S Def 10.9),
  generated by `freeGen K X x = x̄`.
-/

universe u v

namespace UAVariety

open FirstOrder FirstOrder.Language FirstOrder.Language.Structure

variable {L : FirstOrder.Language.{u, v}}

/-- An algebra (more generally an `L`-structure) with carrier in `Type u`. -/
abbrev Alg (L : FirstOrder.Language.{u, v}) := CategoryTheory.Bundled.{u} L.Structure

/-- Bundle a structure as an `Alg L`. -/
abbrev Alg.of (M : Type u) [L.Structure M] : Alg L := CategoryTheory.Bundled.of M

/-! ### Term algebra and direct products -/

/-- The term algebra `T(α)` (B&S Def 10.4): operations build terms; no relations hold. -/
instance termStructure (α : Type*) : L.Structure (L.Term α) where
  funMap f ts := Term.func f ts
  RelMap _ _ := False

/-- The direct product of a family of structures (B&S Def 7.1): operations act
coordinatewise; a relation holds iff it holds in every coordinate. -/
instance piStructure {ι : Type*} (M : ι → Type*) [∀ i, L.Structure (M i)] :
    L.Structure (∀ i, M i) where
  funMap f xs i := funMap f (fun j => xs j i)
  RelMap r xs := ∀ i, RelMap r (fun j => xs j i)

/-! ### Congruences and quotient algebras -/

/-- A congruence on `M` (B&S Def 5.1): an equivalence relation compatible with every
basic operation (and with every relation symbol, which is vacuous for algebras). -/
structure Congruence (M : Type*) [L.Structure M] extends Setoid M where
  fun_compat : ∀ {n : ℕ} (f : L.Functions n) (x y : Fin n → M),
    (∀ i, r (x i) (y i)) → r (funMap f x) (funMap f y)
  rel_compat : ∀ {n : ℕ} (R : L.Relations n) (x y : Fin n → M),
    (∀ i, r (x i) (y i)) → (RelMap R x ↔ RelMap R y)

instance Congruence.prestructure {M : Type*} [L.Structure M] (φ : Congruence (L := L) M) :
    L.Prestructure φ.toSetoid where
  toStructure := inferInstance
  fun_equiv x y h := φ.fun_compat _ x y h
  rel_equiv x y h := propext (φ.rel_compat _ x y h)

/-- The quotient algebra `M/φ` (B&S Def 5.3). -/
abbrev Congruence.Quot {M : Type*} [L.Structure M] (φ : Congruence (L := L) M) : Type _ :=
  Quotient φ.toSetoid

/-! ### Class operators and varieties (B&S §9) -/

/-- `H K`: homomorphic images of members of `K`. -/
def H (K : Set (Alg L)) : Set (Alg L) :=
  {B | ∃ A ∈ K, ∃ f : A →[L] B, Function.Surjective f}

/-- `S K`: algebras isomorphic to a subalgebra of a member of `K`. -/
def S (K : Set (Alg L)) : Set (Alg L) :=
  {B | ∃ A ∈ K, Nonempty (B ↪[L] A)}

/-- `P K`: algebras isomorphic to a direct product of a family (indexed by a type in
`Type u`, possibly empty) of members of `K`. -/
def P (K : Set (Alg L)) : Set (Alg L) :=
  {B | ∃ (ι : Type u) (A : ι → Alg L), (∀ i, A i ∈ K) ∧ Nonempty (B ≃[L] ∀ i, A i)}

/-- A variety (B&S Def 9.3): a class closed under `H`, `S` and `P`.  (Closure under the
empty product makes every variety nonempty.) -/
def IsVariety (K : Set (Alg L)) : Prop :=
  H K ⊆ K ∧ S K ⊆ K ∧ P K ⊆ K

/-- `V K`: the variety generated by `K`, the intersection of all varieties containing `K`
(B&S Def 9.4). -/
def V (K : Set (Alg L)) : Set (Alg L) :=
  ⋂₀ {W | IsVariety W ∧ K ⊆ W}

/-! ### Identities (B&S §11) -/

/-- `A ⊨ p ≈ q` (B&S Def 11.1): the two terms agree under every assignment of the
variables in `A`. -/
def Satisfies {α : Type*} (A : Alg L) (e : L.Term α × L.Term α) : Prop :=
  ∀ v : α → A, e.1.realize v = e.2.realize v

/-- `Mod E` (B&S Def 11.7, `M(Σ)`): the algebras satisfying every identity in `E`. -/
def Mod (E : Set (L.Term ℕ × L.Term ℕ)) : Set (Alg L) :=
  {A | ∀ e ∈ E, Satisfies A e}

/-- `Id K` (B&S Def 11.1, `Id_K(X)` with `X = ℕ`): the identities true in every member
of `K`. -/
def Id (K : Set (Alg L)) : Set (L.Term ℕ × L.Term ℕ) :=
  {e | ∀ A ∈ K, Satisfies A e}

/-! ### Free algebras (B&S Def 10.9) -/

/-- `θ_K(X)` (B&S Def 10.9): `p θ q` iff `p φ q` for every congruence `φ` on `T(X)` whose
quotient `T(X)/φ` lies in `IS(K)`.  It is again a congruence. -/
def freeCong (K : Set (Alg L)) (X : Type u) : Congruence (L := L) (L.Term X) where
  r p q := ∀ φ : Congruence (L := L) (L.Term X), Alg.of φ.Quot ∈ S K → φ.r p q
  iseqv :=
    { refl := fun p φ _ => φ.iseqv.refl p
      symm := fun h φ hφ => φ.iseqv.symm (h φ hφ)
      trans := fun h₁ h₂ φ hφ => φ.iseqv.trans (h₁ φ hφ) (h₂ φ hφ) }
  fun_compat f x y h φ hφ := φ.fun_compat f x y (fun i => h i φ hφ)
  rel_compat _ _ _ _ := Iff.rfl

/-- The free algebra `F_K(X̄) = T(X)/θ_K(X)` for `K` over `X̄` (B&S Def 10.9). -/
abbrev freeAlg (K : Set (Alg L)) (X : Type u) : Alg L :=
  Alg.of (freeCong K X).Quot

/-- The class `p̄ = p/θ_K(X)` of a term in the free algebra. -/
def freeMk (K : Set (Alg L)) (X : Type u) (p : L.Term X) : freeAlg K X :=
  Quotient.mk _ p

/-- The generators `x̄ = x/θ_K(X)` of the free algebra. -/
def freeGen (K : Set (Alg L)) (X : Type u) (x : X) : freeAlg K X :=
  freeMk K X (Term.var x)

end UAVariety
Source
S. Burris, H. P. Sankappanavar, A Course in Universal Algebra, Millennium Edition (2012), https://www.math.uwaterloo.ca/~snburris/htdocs/ualg.html, Ch. II: Def 9.1, 9.3, 9.4, 10.1, 10.4, 10.9, 11.1, 11.7; Ch. II Def 5.1 (congruences), 7.1 (products)
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Fix a first-order signature LLL with function symbols in universe uuu and relation symbols in universe vvv. An algebra (type Alg L) is a bundled LLL-structure whose carrier is a type in Type u\mathrm{Type}\ uType u (the same universe as the function symbols). Carriers may be empty; nothing in the definition forbids this. The definitions below are stated for arbitrary LLL (relation symbols allowed), but all later theorems additionally assume LLL has no relation symbols.

Term algebra. For any type α\alphaα, the set T(α)T(\alpha)T(α) of LLL-terms over variables α\alphaα is made an LLL-structure by fT(α)(t1,…,tn)=f(t1,…,tn)f^{T(\alpha)}(t_1,\dots,t_n)=f(t_1,\dots,t_n)fT(α)(t1​,…,tn​)=f(t1​,…,tn​) (the formal term), and every relation symbol is interpreted as the always-false relation.

Direct product. For a family of LLL-structures (Mi)i∈ι(M_i)_{i\in\iota}(Mi​)i∈ι​ (any index type), the product ∏iMi\prod_i M_i∏i​Mi​ (functions ι→⋃Mi\iota\to\bigcup M_iι→⋃Mi​ with x(i)∈Mix(i)\in M_ix(i)∈Mi​) has f∏Mi(x1,…,xn)(i)=fMi(x1(i),…,xn(i))f^{\prod M_i}(x_1,\dots,x_n)(i)=f^{M_i}(x_1(i),\dots,x_n(i))f∏Mi​(x1​,…,xn​)(i)=fMi​(x1​(i),…,xn​(i)), and a relation RRR holds of (x1,…,xn)(x_1,\dots,x_n)(x1​,…,xn​) iff for every iii, RMi(x1(i),…,xn(i))R^{M_i}(x_1(i),\dots,x_n(i))RMi​(x1​(i),…,xn​(i)) holds (so for empty ι\iotaι every relation holds).

Congruence. For an LLL-structure MMM, a congruence φ\varphiφ is an equivalence relation on MMM such that (a) for every nnn-ary function symbol fff and tuples x,y∈Mnx,y\in M^nx,y∈Mn with xiφyix_i\mathrel{\varphi}y_ixi​φyi​ for all iii, we have fM(x)φfM(y)f^M(x)\mathrel{\varphi}f^M(y)fM(x)φfM(y); and (b) for every nnn-ary relation symbol RRR and such x,yx,yx,y, RM(x)  ⟺  RM(y)R^M(x)\iff R^M(y)RM(x)⟺RM(y). The quotient M/φM/\varphiM/φ is the set of φ\varphiφ-classes with the quotient LLL-structure from Mathlib's Prestructure: functions and relations are computed on chosen representatives, and well-definedness is guaranteed by (a),(b).

Class operators. For a class KKK of algebras:

  • H(K)H(K)H(K) is the class of algebras BBB for which there exist A∈KA\in KA∈K and a surjective LLL-homomorphism A→BA\to BA→B (homomorphisms preserve functions, and relations in the forward direction only).
  • S(K)S(K)S(K) is the class of algebras BBB for which there exist A∈KA\in KA∈K and an LLL-embedding B↪AB\hookrightarrow AB↪A (an injective map preserving functions and preserving and reflecting relations).
  • P(K)P(K)P(K) is the class of algebras BBB for which there exist a type ι:Type u\iota:\mathrm{Type}\ uι:Type u (possibly empty) and a family (Ai)i∈ι(A_i)_{i\in\iota}(Ai​)i∈ι​ of members of KKK with an LLL-isomorphism B≅∏i∈ιAiB\cong\prod_{i\in\iota}A_iB≅∏i∈ι​Ai​ (product structure as above).

A class KKK is a variety (IsVariety) iff H(K)⊆KH(K)\subseteq KH(K)⊆K, S(K)⊆KS(K)\subseteq KS(K)⊆K and P(K)⊆KP(K)\subseteq KP(K)⊆K. V(K)V(K)V(K) is the intersection of all classes WWW of algebras with WWW a variety and K⊆WK\subseteq WK⊆W.

Identities. For an algebra AAA and a pair e=(p,q)e=(p,q)e=(p,q) of terms over a variable type α\alphaα, Satisfies A eA\,eAe means: for every assignment v:α→Av:\alpha\to Av:α→A, pA[v]=qA[v]p^A[v]=q^A[v]pA[v]=qA[v]. For a set EEE of pairs of terms over the variable type N\mathbb NN, Mod(E)\mathrm{Mod}(E)Mod(E) is the class of algebras satisfying every pair in EEE. For a class KKK, Id(K)\mathrm{Id}(K)Id(K) is the set of pairs (p,q)(p,q)(p,q) of terms over N\mathbb NN such that every A∈KA\in KA∈K satisfies (p,q)(p,q)(p,q).

Free algebra. For a class KKK and a type X:Type uX:\mathrm{Type}\ uX:Type u, θK(X)\theta_K(X)θK​(X) is the relation on T(X)T(X)T(X) given by: pθK(X)qp\mathrel{\theta_K(X)}qpθK​(X)q iff for every congruence φ\varphiφ of the term algebra T(X)T(X)T(X) such that the quotient algebra T(X)/φT(X)/\varphiT(X)/φ (in the quotient structure) lies in S(K)S(K)S(K), pφqp\mathrel{\varphi}qpφq. This is shown (in the code) to be a congruence. The free algebra is FK(X)=T(X)/θK(X)F_K(X)=T(X)/\theta_K(X)FK​(X)=T(X)/θK​(X) with the quotient structure; pˉ\bar ppˉ​ denotes the class of a term ppp, and the generator of x∈Xx\in Xx∈X is xˉ=var(x)‾\bar x=\overline{\mathrm{var}(x)}xˉ=var(x)​.

Human review
  • Endorsed by Shuze Chen · Nov 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Alien60 · Nov 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me