Algebras, term algebras, products, congruences, the operators H, S, P, varieties, identities and free algebras
DefinitionUAVariety_defsAlg L: bundled -structures on types in Type u. termStructure: the term algebra (operations build terms, no relations). piStructure: direct products with coordinatewise operations. Congruence M: an equivalence relation on compatible with all operations (and relations); φ.Quot is the quotient algebra 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 . IsVariety K: closed under , , ; V K: intersection of all varieties containing . Satisfies A (p, q): ; Mod E and Id K for identities over . freeCong K X , the intersection of all congruences on with ; freeAlg K X , with freeMk (class of a term) and freeGen (class of a variable).
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Fix a first-order signature with function symbols in universe and relation symbols in universe . An algebra (type Alg L) is a bundled -structure whose carrier is a type in (the same universe as the function symbols). Carriers may be empty; nothing in the definition forbids this. The definitions below are stated for arbitrary (relation symbols allowed), but all later theorems additionally assume has no relation symbols.
Term algebra. For any type , the set of -terms over variables is made an -structure by (the formal term), and every relation symbol is interpreted as the always-false relation.
Direct product. For a family of -structures (any index type), the product (functions with ) has , and a relation holds of iff for every , holds (so for empty every relation holds).
Congruence. For an -structure , a congruence is an equivalence relation on such that (a) for every -ary function symbol and tuples with for all , we have ; and (b) for every -ary relation symbol and such , . The quotient is the set of -classes with the quotient -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 of algebras:
- is the class of algebras for which there exist and a surjective -homomorphism (homomorphisms preserve functions, and relations in the forward direction only).
- is the class of algebras for which there exist and an -embedding (an injective map preserving functions and preserving and reflecting relations).
- is the class of algebras for which there exist a type (possibly empty) and a family of members of with an -isomorphism (product structure as above).
A class is a variety (IsVariety) iff , and . is the intersection of all classes of algebras with a variety and .
Identities. For an algebra and a pair of terms over a variable type , Satisfies means: for every assignment , . For a set of pairs of terms over the variable type , is the class of algebras satisfying every pair in . For a class , is the set of pairs of terms over such that every satisfies .
Free algebra. For a class and a type , is the relation on given by: iff for every congruence of the term algebra such that the quotient algebra (in the quotient structure) lies in , . This is shown (in the code) to be a congruence. The free algebra is with the quotient structure; denotes the class of a term , and the generator of is .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.