Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Congruences, polynomials, T-matrices, term condition, higher commutator, Day terms

Definition
HigherComm_defs

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

commutator-theorycongruence-modularday-termsmodel-theoryuniversal-algebra

Congruence M: equivalence relation compatible with all operations, ordered by inclusion; Congruence.iSup (join = intersection of all upper bounds), sup, ker f, comap f (preimage), map f (congruence generated by the image). cubeEval t a b f: the polynomial t∈t\int∈ L.Term ((Σ i : Fin k, Fin (r i)) ⊕ M) (blocks of arbitrary arity, constants via Sum.inr) evaluated at the cube vertex f∈{0,1}kf\in\{0,1\}^kf∈{0,1}k (ai\mathbf a_iai​ where f(i)=0f(i)=0f(i)=0, bi\mathbf b_ibi​ where f(i)=1f(i)=1f(i)=1). IsTMatrix T m: mmm is a TTT-matrix (ai≡θibi\mathbf a_i\equiv_{\theta_i}\mathbf b_iai​≡θi​​bi​). LineRel, SupportingRel, PivotRel: the (j)(j)(j)-line at fff, all supporting (j)(j)(j)-lines, the pivot (j)(j)(j)-line are δ\deltaδ-pairs. CentralAt T j δ =C(T;j;δ)=C(T;j;\delta)=C(T;j;δ); higherCommAt T j =[T]j=[T]_j=[T]j​, the intersection of all δ\deltaδ with C(T;j;δ)C(T;j;\delta)C(T;j;δ); higherComm T =[θ0,…,θk+1]=[T]k+1=[\theta_0,\dots,\theta_{k+1}]=[T]_{k+1}=[θ0​,…,θk+1​]=[T]k+1​ (at least two congruences). TwoTermCentral T δ =Ctt(T;δ)=C_{tt}(T;\delta)=Ctt​(T;δ). IsDayTerms M m: Day's identities hold in MMM.

Definition code
import Mathlib.ModelTheory.Semantics
import Mathlib.Algebra.Group.Nat.Even

/-!
# Higher commutators in algebras with Day terms (Moorhead, arXiv:1610.07087, §2)

Setting, built on Mathlib's first-order model theory (same shape as the `UAVariety` setting):

* An *algebra* is a type `M` with an `L.Structure`; theorems assume `[L.IsAlgebraic]`.
* `Congruence M`: an equivalence relation compatible with the basic operations.
  `φ ≤ ψ` means `φ ⊆ ψ` as relations.  `Congruence.iSup γ` is the join `⋁ᵢ γᵢ` in `Con(M)`
  (the smallest congruence containing every `γᵢ`, i.e. the meet of all upper bounds).
* *Polynomials* (`Pol(M)`, term operations with constants from `M`) in `k` blocks of
  variables, block `i` having arity `r i`, are the terms `L.Term ((Σ i : Fin k, Fin (r i)) ⊕ M)`;
  a variable `Sum.inr c` is the constant `c`.
* `cubeEval t a b f` evaluates the polynomial `t(z₀,…,z_{k-1})` at the vertex `f ∈ 2^k`
  of the cube: block `i` gets the tuple `aᵢ` if `f i = false` and `bᵢ` if `f i = true`.
  The function `f ↦ cubeEval t a b f` is the `T`-matrix labelled by `(t, ((aᵢ, bᵢ))ᵢ)`
  (paper Defs 2.7–2.8), and `IsTMatrix T m` says `m ∈ M(T)`.
* Lines in direction `j` are indexed by `f : Fin k → Bool` (the value `f j` is ignored): the
  line at `f` is the pair `(m (update f j false), m (update f j true))`.  The *pivot line* is the
  one at the all-`true` function; all others are *supporting lines* (Def 2.11).
* `CentralAt T j δ` is `C(T; j; δ)` (Def 2.12; Def 2.1 unfolded): for every polynomial and all
  pairs of tuples `aᵢ ≡_{θᵢ} bᵢ`, if every supporting `(j)`-line is a `δ`-pair, then so is the
  pivot `(j)`-line.
* `higherCommAt T j = [T]_j = ⋀{δ : C(T;j;δ)}` (Def 2.13), and `higherComm T = [θ₀,…,θ_{k+1}]`
  is the commutator of Def 2.2 (arity `k + 2 ≥ 2`, as in the paper), i.e. `[T]_j` for the last
  coordinate `j = k + 1` (Def 2.1 puts the centralized congruence last).
* `Congruence.sup φ ψ = φ ∨ ψ`; for a homomorphism `f : M →[L] N`, `Congruence.ker f`,
  `Congruence.comap f ψ = f⁻¹(ψ)`, and `Congruence.map f θ = f(θ)`, the congruence of `N`
  generated by the image of `θ` (§5).
* `TwoTermCentral T δ` is the two-term condition `C_tt(T; δ)` (Def 6.3).
* `IsDayTerms M m`: the 4-ary terms `m 0, …, m n` satisfy Day's identities (paper Prop 2.3)
  *in the algebra `M`* (for all elements of `M`).
-/

universe u v w

namespace HigherComm

open FirstOrder FirstOrder.Language FirstOrder.Language.Structure

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

/-- A congruence on `M`: 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)

variable {M : Type w} [L.Structure M]

/-- Inclusion of congruences: `φ ≤ ψ` iff `φ ⊆ ψ`. -/
instance : LE (Congruence (L := L) M) :=
  ⟨fun φ ψ => ∀ x y, φ.r x y → ψ.r x y⟩


/-- The join `⋁ᵢ γᵢ` in the congruence lattice of an algebra: `x` and `y` are related iff they
are related by every congruence containing all `γᵢ`. -/
def Congruence.iSup [L.IsAlgebraic] {ι : Sort*} (γ : ι → Congruence (L := L) M) :
    Congruence (L := L) M where
  r x y := ∀ φ : Congruence (L := L) M, (∀ i, γ i ≤ φ) → φ.r x y
  iseqv :=
    { refl := fun x φ _ => φ.iseqv.refl x
      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 R _ _ _ := isEmptyElim R

/-! ### Polynomials, `T`-matrices and centrality -/

/-- Evaluate the polynomial `t(z₀,…,z_{k-1})` (block `i` of arity `r i`; `Sum.inr c` is the
constant `c`) at the cube vertex `f ∈ 2^k`: block `i` is `aᵢ` if `f i = false`, `bᵢ` if
`f i = true`. -/
def cubeEval {k : ℕ} {r : Fin k → ℕ} (t : L.Term ((Σ i : Fin k, Fin (r i)) ⊕ M))
    (a b : (i : Fin k) → Fin (r i) → M) (f : Fin k → Bool) : M :=
  t.realize (Sum.elim (fun x => if f x.1 then b x.1 x.2 else a x.1 x.2) id)

/-- `m ∈ M(T)` (paper Def 2.8): `m : 2^k → M` is the `T`-matrix labelled by some polynomial `t`
and pairs of tuples `aᵢ ≡_{θᵢ} bᵢ` (componentwise), i.e. `m f = t(f)` for every vertex `f`. -/
def IsTMatrix {k : ℕ} (T : Fin k → Congruence (L := L) M) (m : (Fin k → Bool) → M) : Prop :=
  ∃ (r : Fin k → ℕ) (t : L.Term ((Σ i : Fin k, Fin (r i)) ⊕ M))
    (a b : (i : Fin k) → Fin (r i) → M),
    (∀ i p, (T i).r (a i p) (b i p)) ∧ ∀ f, m f = cubeEval t a b f

/-- The `(j)`-cross-section line of `m` at `f` (the value `f j` is ignored) is a `δ`-pair. -/
def LineRel {k : ℕ} (δ : Congruence (L := L) M) (m : (Fin k → Bool) → M) (j : Fin k)
    (f : Fin k → Bool) : Prop :=
  δ.r (m (Function.update f j false)) (m (Function.update f j true))

/-- Every `(j)`-supporting line of `m` (every line at an `f` with `f i = false` for some
`i ≠ j`) is a `δ`-pair. -/
def SupportingRel {k : ℕ} (δ : Congruence (L := L) M) (m : (Fin k → Bool) → M) (j : Fin k) :
    Prop :=
  ∀ f : Fin k → Bool, (∃ i, i ≠ j ∧ f i = false) → LineRel δ m j f

/-- The `(j)`-pivot line of `m` (the line at the all-`true` vertex) is a `δ`-pair. -/
def PivotRel {k : ℕ} (δ : Congruence (L := L) M) (m : (Fin k → Bool) → M) (j : Fin k) : Prop :=
  LineRel δ m j (fun _ => true)

/-- `C(T; j; δ)` (paper Def 2.12, = Def 2.1 with `θ_j` in the last place): in every
`T`-matrix, if all `(j)`-supporting lines are `δ`-pairs then so is the `(j)`-pivot line. -/
def CentralAt {k : ℕ} (T : Fin k → Congruence (L := L) M) (j : Fin k)
    (δ : Congruence (L := L) M) : Prop :=
  ∀ m, IsTMatrix T m → SupportingRel δ m j → PivotRel δ m j

/-- `[T]_j = ⋀{δ : C(T; j; δ)}` (paper Def 2.13). -/
def higherCommAt [L.IsAlgebraic] {k : ℕ} (T : Fin k → Congruence (L := L) M) (j : Fin k) :
    Congruence (L := L) M where
  r x y := ∀ δ : Congruence (L := L) M, CentralAt T j δ → δ.r x y
  iseqv :=
    { refl := fun x δ _ => δ.iseqv.refl x
      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 R _ _ _ := isEmptyElim R

/-- The higher commutator `[θ₀, …, θ_{k+1}] = ⋀{δ : C(θ₀,…,θ_{k+1}; δ)}` (paper Def 2.2, arity
`k + 2 ≥ 2`): the centralized congruence is the last one. -/
def higherComm [L.IsAlgebraic] {k : ℕ} (T : Fin (k + 2) → Congruence (L := L) M) :
    Congruence (L := L) M :=
  higherCommAt T (Fin.last (k + 1))

/-! ### Homomorphisms and the two-term condition -/

/-- The join `φ ∨ ψ` of two congruences. -/
def Congruence.sup [L.IsAlgebraic] (φ ψ : Congruence (L := L) M) : Congruence (L := L) M :=
  Congruence.iSup (fun b : Bool => cond b φ ψ)

/-- The kernel `ker f = {(x, y) : f x = f y}` of a homomorphism. -/
def Congruence.ker [L.IsAlgebraic] {N : Type*} [L.Structure N] (f : M →[L] N) :
    Congruence (L := L) M where
  r x y := f x = f y
  iseqv := ⟨fun _ => rfl, fun h => h.symm, fun h₁ h₂ => h₁.trans h₂⟩
  fun_compat g x y h := by
    simp only [Hom.map_fun]
    exact congrArg (funMap g) (funext fun i => h i)
  rel_compat R _ _ _ := isEmptyElim R

/-- The preimage `f⁻¹(ψ) = {(x, y) : (f x, f y) ∈ ψ}` of a congruence under a homomorphism. -/
def Congruence.comap [L.IsAlgebraic] {N : Type*} [L.Structure N] (f : M →[L] N)
    (ψ : Congruence (L := L) N) : Congruence (L := L) M where
  r x y := ψ.r (f x) (f y)
  iseqv :=
    { refl := fun x => ψ.iseqv.refl (f x)
      symm := fun h => ψ.iseqv.symm h
      trans := fun h₁ h₂ => ψ.iseqv.trans h₁ h₂ }
  fun_compat g x y h := by
    simp only [Hom.map_fun]
    exact ψ.fun_compat g _ _ h
  rel_compat R _ _ _ := isEmptyElim R

/-- The congruence `f(θ)` of `N` generated by the image `{(f x, f y) : (x, y) ∈ θ}`.  When `f` is
surjective and `ker f ≤ θ` this is exactly the image relation. -/
def Congruence.map [L.IsAlgebraic] {N : Type*} [L.Structure N] (f : M →[L] N)
    (θ : Congruence (L := L) M) : Congruence (L := L) N where
  r a b := ∀ ψ : Congruence (L := L) N, (∀ x y, θ.r x y → ψ.r (f x) (f y)) → ψ.r a b
  iseqv :=
    { refl := fun a ψ _ => ψ.iseqv.refl a
      symm := fun h ψ hψ => ψ.iseqv.symm (h ψ hψ)
      trans := fun h₁ h₂ ψ hψ => ψ.iseqv.trans (h₁ ψ hψ) (h₂ ψ hψ) }
  fun_compat g x y h ψ hψ := ψ.fun_compat g x y (fun i => h i ψ hψ)
  rel_compat R _ _ _ := isEmptyElim R

/-- `C_tt(T; δ)`, two-term centrality (paper Def 6.3): for all `T`-matrices `h, g`, if
`h f ≡_δ g f` at every vertex `f` except the all-`true` vertex, then also at that vertex. -/
def TwoTermCentral {k : ℕ} (T : Fin k → Congruence (L := L) M) (δ : Congruence (L := L) M) :
    Prop :=
  ∀ h g, IsTMatrix T h → IsTMatrix T g →
    (∀ f : Fin k → Bool, f ≠ (fun _ => true) → δ.r (h f) (g f)) →
      δ.r (h (fun _ => true)) (g (fun _ => true))

/-! ### Day terms -/

/-- `m 0, …, m n` (4-ary terms in the variables `0 = x, 1 = y, 2 = z, 3 = u`) are Day terms
for `M` (paper Prop 2.3): the following identities hold for all elements of `M`:
`mₑ(x,y,y,x) = x`, `m₀(x,y,z,u) = x`, `mₙ(x,y,z,u) = u`,
`mₑ(x,x,u,u) = mₑ₊₁(x,x,u,u)` for even `e`, `mₑ(x,y,y,u) = mₑ₊₁(x,y,y,u)` for odd `e`. -/
def IsDayTerms (M : Type w) [L.Structure M] {n : ℕ} (m : Fin (n + 1) → L.Term (Fin 4)) : Prop :=
  (∀ e (x y : M), (m e).realize ![x, y, y, x] = x) ∧
  (∀ x y z u : M, (m 0).realize ![x, y, z, u] = x) ∧
  (∀ x y z u : M, (m (Fin.last n)).realize ![x, y, z, u] = u) ∧
  (∀ e : Fin n, Even e.val → ∀ x u : M,
    (m e.castSucc).realize ![x, x, u, u] = (m e.succ).realize ![x, x, u, u]) ∧
  (∀ e : Fin n, Odd e.val → ∀ x y u : M,
    (m e.castSucc).realize ![x, y, y, u] = (m e.succ).realize ![x, y, y, u])

end HigherComm
Source
A. Moorhead, Higher commutator theory for congruence modular varieties, J. Algebra 513 (2018) 133-158, https://doi.org/10.1016/j.jalgebra.2018.07.026 (arXiv:1610.07087), Section 2 (Defs 2.1, 2.2, 2.7-2.13, Prop 2.3), Section 5, Def 6.3
Read-back

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

Setting: LLL a first-order language, MMM an LLL-structure.

  • Congruence φ\varphiφ: equivalence relation on MMM compatible with every function symbol and (for relation symbols) preserving RelMap in both directions. Nothing else.
  • φ≤ψ\varphi\le\psiφ≤ψ: ∀x,y (xφy⇒xψy)\forall x,y\,(x\mathrel{\varphi}y\Rightarrow x\mathrel{\psi}y)∀x,y(xφy⇒xψy). Only an LE instance.
  • iSup (algebraic LLL): ⋁iγi\bigvee_i\gamma_i⋁i​γi​ relates x,yx,yx,y iff every congruence φ≥γi\varphi\ge\gamma_iφ≥γi​ for all iii relates x,yx,yx,y. Empty family gives equality.
  • cubeEval t(a,b)(f)t(a,b)(f)t(a,b)(f): term ttt over variables (i,p)(i,p)(i,p) (i<ki<ki<k, p<rip<r_ip<ri​) and constants from MMM; variable (i,p)↦bi(p)(i,p)\mapsto b_i(p)(i,p)↦bi​(p) if f(i)=1f(i)=1f(i)=1, ai(p)a_i(p)ai​(p) if f(i)=0f(i)=0f(i)=0.
  • IsTMatrix T mT\,mTm: ∃ri\exists r_i∃ri​, ttt, ai,bi∈Mria_i,b_i\in M^{r_i}ai​,bi​∈Mri​ with ai(p)θibi(p)a_i(p)\mathrel{\theta_i}b_i(p)ai​(p)θi​bi​(p) for all i,pi,pi,p and m(f)=m(f)=m(f)= cubeEval(t,a,b)(f)(t,a,b)(f)(t,a,b)(f) for all f∈{0,1}kf\in\{0,1\}^kf∈{0,1}k.
  • LineRel δ m j f\delta\,m\,j\,fδmjf: m(f[j↦0])δm(f[j↦1])m(f[j\mapsto0])\mathrel\delta m(f[j\mapsto1])m(f[j↦0])δm(f[j↦1]).
  • SupportingRel δ m j\delta\,m\,jδmj: LineRel for every fff having some i≠ji\ne ji=j with f(i)=0f(i)=0f(i)=0.
  • PivotRel δ m j\delta\,m\,jδmj: m(1[j↦0])δm(1)m(\mathbf1[j\mapsto0])\mathrel\delta m(\mathbf 1)m(1[j↦0])δm(1).
  • CentralAt T j δT\,j\,\deltaTjδ: every TTT-matrix with SupportingRel has PivotRel.
  • higherCommAt T jT\,jTj: relates x,yx,yx,y iff every δ\deltaδ with CentralAt(T,j,δ)(T,j,\delta)(T,j,δ) relates them.
  • higherComm TTT (T:Fin(k+2)→T:\mathrm{Fin}(k+2)\toT:Fin(k+2)→ Con, so at least two congruences): higherCommAt at the last index k+1k+1k+1.
  • Congruence.sup φ∨ψ\varphi\vee\psiφ∨ψ: the iSup of the two-element family (φ,ψ)(\varphi,\psi)(φ,ψ): relates x,yx,yx,y iff every congruence containing both φ\varphiφ and ψ\psiψ relates them.
  • Congruence.ker fff (for a homomorphism f:M→Nf:M\to Nf:M→N): x∼y  ⟺  f(x)=f(y)x\sim y\iff f(x)=f(y)x∼y⟺f(x)=f(y).
  • Congruence.comap f ψf\,\psifψ (for ψ\psiψ a congruence of NNN): x∼y  ⟺  f(x)ψf(y)x\sim y\iff f(x)\mathrel\psi f(y)x∼y⟺f(x)ψf(y).
  • Congruence.map f θf\,\thetafθ (congruence of NNN): a∼ba\sim ba∼b iff every congruence ψ\psiψ of NNN with f(x)ψf(y)f(x)\mathrel\psi f(y)f(x)ψf(y) for all (x,y)∈θ(x,y)\in\theta(x,y)∈θ relates a,ba,ba,b; i.e. the congruence of NNN generated by {(fx,fy):xθy}\{(fx,fy):x\mathrel\theta y\}{(fx,fy):xθy}. No surjectivity or kernel condition is built in.
  • TwoTermCentral T δT\,\deltaTδ (for T:Fin k→T:\mathrm{Fin}\,k\toT:Fink→ Con): for all TTT-matrices h,gh,gh,g, if h(f)δg(f)h(f)\mathrel\delta g(f)h(f)δg(f) for every f∈{0,1}kf\in\{0,1\}^kf∈{0,1}k other than 1\mathbf11, then h(1)δg(1)h(\mathbf1)\mathrel\delta g(\mathbf1)h(1)δg(1).
  • IsDayTerms M mM\,mMm: in MMM, for all elements: me(x,y,y,x)=xm_e(x,y,y,x)=xme​(x,y,y,x)=x (all e≤ne\le ne≤n); m0(x,y,z,u)=xm_0(x,y,z,u)=xm0​(x,y,z,u)=x; mn(x,y,z,u)=um_n(x,y,z,u)=umn​(x,y,z,u)=u; even e<ne<ne<n: me(x,x,u,u)=me+1(x,x,u,u)m_e(x,x,u,u)=m_{e+1}(x,x,u,u)me​(x,x,u,u)=me+1​(x,x,u,u); odd e<ne<ne<n: me(x,y,y,u)=me+1(x,y,y,u)m_e(x,y,y,u)=m_{e+1}(x,y,y,u)me​(x,y,y,u)=me+1​(x,y,y,u).
Human review
  • Endorsed by Shuze Chen · Nov 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Alien60 · Nov 7, 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