Congruences, polynomials, T-matrices, term condition, higher commutator, Day terms
DefinitionHigherComm_defsCongruence 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 L.Term ((Σ i : Fin k, Fin (r i)) ⊕ M) (blocks of arbitrary arity, constants via Sum.inr) evaluated at the cube vertex ( where , where ). IsTMatrix T m: is a -matrix (). LineRel, SupportingRel, PivotRel: the -line at , all supporting -lines, the pivot -line are -pairs. CentralAt T j δ ; higherCommAt T j , the intersection of all with ; higherComm T (at least two congruences). TwoTermCentral T δ . IsDayTerms M m: Day's identities hold in .
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting: a first-order language, an -structure.
- Congruence : equivalence relation on compatible with every function symbol and (for relation symbols) preserving RelMap in both directions. Nothing else.
- : . Only an
LEinstance. - iSup (algebraic ): relates iff every congruence for all relates . Empty family gives equality.
- cubeEval : term over variables (, ) and constants from ; variable if , if .
- IsTMatrix : , , with for all and cubeEval for all .
- LineRel : .
- SupportingRel : LineRel for every having some with .
- PivotRel : .
- CentralAt : every -matrix with SupportingRel has PivotRel.
- higherCommAt : relates iff every with CentralAt relates them.
- higherComm ( Con, so at least two congruences): higherCommAt at the last index .
- Congruence.sup : the iSup of the two-element family : relates iff every congruence containing both and relates them.
- Congruence.ker (for a homomorphism ): .
- Congruence.comap (for a congruence of ): .
- Congruence.map (congruence of ): iff every congruence of with for all relates ; i.e. the congruence of generated by . No surjectivity or kernel condition is built in.
- TwoTermCentral (for Con): for all -matrices , if for every other than , then .
- IsDayTerms : in , for all elements: (all ); ; ; even : ; odd : .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.