Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Absorption, linked relations, Taylor term data, smooth digraphs, cyclic terms

Definition
BKAbsorption_defs

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

absorptionconstraint-satisfactioncyclic-termsmodel-theorytaylor-varietyuniversal-algebra

prodStructure: coordinatewise operations on A×BA\times BA×B. IsIdempotent L A: f(a,…,a)=af(a,\dots,a)=af(a,…,a)=a for every basic operation. IsSubuniverse L S: SSS closed under basic operations. IsAbsorbing L B (B⊴AB\trianglelefteq AB⊴A): a subuniverse with a term ttt such that t(a)∈Bt(a)\in Bt(a)∈B whenever all aia_iai​ but at most one are in BBB. MinAbsorbing L B (B⊴ ⁣ ⁣⊴AB\trianglelefteq\!\!\trianglelefteq AB⊴⊴A): nonempty, absorbing, no proper nonempty absorbing subset of BBB. HasProperAbsorbing L A: an absorbing BBB with ∅≠B≠A\emptyset\neq B\neq A∅=B=A. Subdirect R: both projections onto. LinkStep R a a': common RRR-neighbour; Linked R: any two elements of the first projection are joined by LinkStep-chains. LinkAdj R: adjacency of the bipartite graph of RRR on A⊕BA\oplus BA⊕B; InMinAbs L x: xxx lies in a minimal absorbing subuniverse of AAA or of BBB. TaylorDatum L: a kkk-ary term with patterns σj,τj∈{x,y}k\sigma_j,\tau_j\in\{x,y\}^kσj​,τj​∈{x,y}k (false=x=x=x), σj(j)=x\sigma_j(j)=xσj​(j)=x, τj(j)=y\tau_j(j)=yτj​(j)=y; IsTaylorAlg T A: idempotent and t(σj)≈t(τj)t(\sigma_j)\approx t(\tau_j)t(σj​)≈t(τj​) for all jjj. Smooth E: every vertex has an outgoing and an incoming edge. Walk E a b z: an oriented path from aaa to bbb of algebraic length zzz. HasCyclicTermOp L A k: an idempotent kkk-ary term operation invariant under x↦x∘x\mapsto x\circx↦x∘finRotate k. IsSubpower L R: R⊆AkR\subseteq A^kR⊆Ak closed coordinatewise; IsCyclicRel R: closed under rotation.

Definition code
import Mathlib.ModelTheory.Substructures
import Mathlib.ModelTheory.Semantics
import Mathlib.Logic.Equiv.Fin.Rotate
import Mathlib.Data.Nat.Prime.Defs
import Mathlib.SetTheory.Cardinal.Finite

/-!
# Absorbing subalgebras and cyclic terms (Barto–Kozik, LMCS 8(1:07) 2012, arXiv:1201.0557)

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

* An *algebra* of signature `L` is a type `A` with an `L.Structure`; theorems assume
  `[L.IsAlgebraic]`.  Term operations (`Clo(A)`) are the maps `a ↦ t.realize a` for
  `t : L.Term (Fin n)`.
* `IsSubuniverse L S`: `S` is closed under every basic operation (it may be empty).
  The product `A × B` carries the coordinatewise structure `prodStructure`, so a subuniverse
  of `A × B` is an `L.Substructure (A × B)`, and `↥R` is the algebra `R` (Mathlib's induced
  structure).  Subuniverses of the power `A^k` are sets of tuples `Fin k → A` closed under
  coordinatewise basic operations (`IsSubpower L`).
* `IsAbsorbing L B` (paper Def 2.1, `B ⊴ A`): `B` is a subuniverse and some term operation `t` (of positive arity)
  satisfies `t(a₀,…,a_{n-1}) ∈ B` whenever all `aᵢ` except at most one lie in `B`.
  `MinAbsorbing L B` (Def 2.14, `B ⊴⊴ A`): `B` is a nonempty absorbing subuniverse and no proper
  subalgebra of `B` absorbs `A`.  `HasProperAbsorbing L A`: `A` has an absorbing subuniverse
  `B` with `∅ ≠ B ≠ A`.
* `Subdirect R` (`R ≤_S A × B`), `Linked R` (Def 2.2, via the relation `a ~ a'` iff `a, a'`
  have a common `R`-neighbour), and `LinkAdj R`, the adjacency of the bipartite graph of `R` on
  `A ⊕ B` (used for linking elements of `A` and `B`); `InMinAbs L x` for `x : A ⊕ B` says that
  `x` lies in a minimal absorbing subuniverse of `A` (if `x ∈ A`) or of `B` (if `x ∈ B`).
* *Taylor varieties.*  The paper works with finite algebras in a fixed Taylor variety `V`
  (idempotent with a Taylor term).  A `TaylorDatum L` is a `k`-ary term `t` with, for each
  `j < k`, two patterns `σ j, τ j : Fin k → Bool` (`false = x`, `true = y`) with `σ j j = x` and
  `τ j j = y`.  `IsTaylorAlg T A`: `A` is idempotent (every basic operation satisfies
  `f(a,…,a) = a`) and satisfies the `k` Taylor identities `t(σ j) ≈ t(τ j)`.  The class of such
  `A` is the Taylor variety axiomatized by these identities, and every algebra of a Taylor
  variety lies in such a class; "finite algebras in a Taylor variety" = finite `A` (and `B`)
  with `IsTaylorAlg T` for one common datum `T`.
* Digraphs `G = (A, E)` with `E ≤ A²` (`E : L.Substructure (A × A)`): `Smooth E`;
  `Walk E a b z` means `a` is connected to `b` by an oriented path of algebraic length `z`
  (forward edges count `+1`, backward edges `-1`).  `G` has algebraic length `1` iff some
  vertex `a` has `Walk E a a 1`; the weak component of `a` is `{b | ∃ z, Walk E a b z}`.
* `HasCyclicTermOp L A k`: a `k`-ary idempotent term operation `t` with
  `t(x₀,…,x_{k-1}) = t(x₁,…,x_{k-1},x₀)`; `IsCyclicRel R` for `R ⊆ A^k` (Def 4.3).
-/

universe u v w w'

namespace BKAbsorption

open FirstOrder FirstOrder.Language FirstOrder.Language.Structure

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

/-- The product algebra `A × B`: operations (and relations) computed coordinatewise. -/
instance prodStructure (A : Type w) (B : Type w') [L.Structure A] [L.Structure B] :
    L.Structure (A × B) where
  funMap f x := (funMap f (fun i => (x i).1), funMap f (fun i => (x i).2))
  RelMap r x := RelMap r (fun i => (x i).1) ∧ RelMap r (fun i => (x i).2)

section algebra

variable (L) (M : Type w) [L.Structure M]

/-- Every basic operation is idempotent: `f(a, …, a) = a`. -/
def IsIdempotent : Prop :=
  ∀ (n : ℕ) (f : L.Functions n) (a : M), funMap f (fun _ => a) = a

variable {M}

/-- `S` is a subuniverse (closed under all basic operations; possibly empty). -/
def IsSubuniverse (S : Set M) : Prop :=
  ∀ (n : ℕ) (f : L.Functions n) (x : Fin n → M), (∀ i, x i ∈ S) → funMap f x ∈ S

/-- `B ⊴ M` (paper Def 2.1): `B` is a subuniverse absorbing `M` with respect to some term
operation `t ∈ Clo(M)` of positive arity. -/
def IsAbsorbing (B : Set M) : Prop :=
  IsSubuniverse L B ∧ ∃ (n : ℕ) (t : L.Term (Fin n)), 0 < n ∧
    ∀ (k : Fin n) (a : Fin n → M), (∀ i, i ≠ k → a i ∈ B) → t.realize a ∈ B

/-- `B ⊴⊴ M` (paper Def 2.14): `B` is a nonempty absorbing subuniverse and no proper
subalgebra of `B` absorbs `M`. -/
def MinAbsorbing (B : Set M) : Prop :=
  B.Nonempty ∧ IsAbsorbing L B ∧
    ∀ C : Set M, C.Nonempty → C ⊆ B → IsAbsorbing L C → C = B

variable (M) in
/-- `M` has a proper absorbing subuniverse `B` (`∅ ≠ B ≠ M`). -/
def HasProperAbsorbing : Prop :=
  ∃ B : Set M, IsAbsorbing L B ∧ B.Nonempty ∧ B ≠ Set.univ

end algebra

section relations

variable {A : Type w} {B : Type w'}

/-- `R ⊆ A × B` is subdirect: both projections are onto. -/
def Subdirect (R : Set (A × B)) : Prop :=
  Prod.fst '' R = Set.univ ∧ Prod.snd '' R = Set.univ

/-- `a ~ a'` iff `a` and `a'` have a common `R`-neighbour; its reflexive-transitive closure is
"`a, a'` are `R`-linked" (paper Def 2.2). -/
def LinkStep (R : Set (A × B)) (a a' : A) : Prop :=
  ∃ b, (a, b) ∈ R ∧ (a', b) ∈ R

/-- `R` is linked (paper Def 2.2): any two elements of the first projection are `R`-linked. -/
def Linked (R : Set (A × B)) : Prop :=
  ∀ a a', a ∈ Prod.fst '' R → a' ∈ Prod.fst '' R → Relation.ReflTransGen (LinkStep R) a a'

/-- Adjacency in the bipartite graph of `R` on the disjoint union `A ⊕ B`
(`a ∈ A` and `b ∈ B` are adjacent iff `(a, b) ∈ R`). -/
def LinkAdj (R : Set (A × B)) : A ⊕ B → A ⊕ B → Prop
  | Sum.inl a, Sum.inr b => (a, b) ∈ R
  | Sum.inr b, Sum.inl a => (a, b) ∈ R
  | _, _ => False

end relations

section minabsSum

variable (L) {A : Type w} {B : Type w'} [L.Structure A] [L.Structure B]

/-- An element of `A ⊕ B` lies in some minimal absorbing subuniverse of `A` (left summand) or
of `B` (right summand). -/
def InMinAbs : A ⊕ B → Prop
  | Sum.inl a => ∃ C : Set A, MinAbsorbing L C ∧ a ∈ C
  | Sum.inr b => ∃ D : Set B, MinAbsorbing L D ∧ b ∈ D

end minabsSum

section taylor

/-- A Taylor term datum: a `k`-ary term `t` and, for every `j < k`, an identity
`t(σ j) ≈ t(τ j)` in the variables `x` (`false`) and `y` (`true`), with `x` at position `j` on
the left and `y` at position `j` on the right. -/
structure TaylorDatum (L : FirstOrder.Language.{u, v}) where
  k : ℕ
  t : L.Term (Fin k)
  σ : Fin k → Fin k → Bool
  τ : Fin k → Fin k → Bool
  σ_self : ∀ j, σ j j = false
  τ_self : ∀ j, τ j j = true

/-- `A` lies in the Taylor variety given by `T`: `A` is idempotent and satisfies the Taylor
identities of `T`. -/
def IsTaylorAlg (T : TaylorDatum L) (A : Type w) [L.Structure A] : Prop :=
  IsIdempotent L A ∧ ∀ (j : Fin T.k) (x y : A),
    T.t.realize (fun i => cond (T.σ j i) y x) = T.t.realize (fun i => cond (T.τ j i) y x)

end taylor

section digraph

variable {A : Type w}

/-- The digraph `(A, E)` is smooth: every vertex has an outgoing and an incoming edge. -/
def Smooth (E : Set (A × A)) : Prop :=
  ∀ a, (∃ b, (a, b) ∈ E) ∧ (∃ b, (b, a) ∈ E)

/-- `Walk E a b z`: `a` is connected to `b` via an oriented path of algebraic length `z`
(number of forward edges minus number of backward edges). -/
inductive Walk (E : Set (A × A)) : A → A → ℤ → Prop
  | refl (a : A) : Walk E a a 0
  | fwd {a b c : A} {z : ℤ} : Walk E a b z → (b, c) ∈ E → Walk E a c (z + 1)
  | bwd {a b c : A} {z : ℤ} : Walk E a b z → (c, b) ∈ E → Walk E a c (z - 1)

end digraph

section cyclic

variable (L) (A : Type w) [L.Structure A]

/-- `A` has a `k`-ary cyclic term operation: an idempotent term operation `t` with
`t(x₀, x₁, …, x_{k-1}) = t(x₁, …, x_{k-1}, x₀)`. -/
def HasCyclicTermOp (k : ℕ) : Prop :=
  ∃ t : L.Term (Fin k), (∀ a : A, t.realize (fun _ => a) = a) ∧
    ∀ x : Fin k → A, t.realize x = t.realize (x ∘ finRotate k)

variable {A}

/-- `R ⊆ A^k` is a subuniverse of the power algebra `A^k` (closed under coordinatewise basic
operations). -/
def IsSubpower {k : ℕ} (R : Set (Fin k → A)) : Prop :=
  ∀ (n : ℕ) (f : L.Functions n) (x : Fin n → Fin k → A), (∀ i, x i ∈ R) →
    (fun j => funMap f (fun i => x i j)) ∈ R

/-- `R ⊆ A^k` is cyclic (paper Def 4.3): closed under the cyclic shift
`(a₀, …, a_{k-1}) ↦ (a₁, …, a_{k-1}, a₀)`. -/
def IsCyclicRel {k : ℕ} (R : Set (Fin k → A)) : Prop :=
  ∀ x ∈ R, x ∘ finRotate k ∈ R

end cyclic

end BKAbsorption
Source
L. Barto, M. Kozik, Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem, Logical Methods in Computer Science 8(1:07) 2012, https://doi.org/10.2168/LMCS-8(1:7)2012 (arXiv:1201.0557), Sections 1-4 (Defs 2.1, 2.2, 2.14, 4.3; Section 3.1)
Read-back

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

Throughout, LLL is a first-order language (relation symbols allowed in the definitions; the theorems assume none), and an algebra is a type with an LLL-structure.

Product. A×BA\times BA×B gets the coordinatewise structure: f(x0,…,xn−1)=(fA(π1x0,… ), fB(π2x0,… ))f(x_0,\dots,x_{n-1})=(f^A(\pi_1x_0,\dots),\,f^B(\pi_2x_0,\dots))f(x0​,…,xn−1​)=(fA(π1​x0​,…),fB(π2​x0​,…)); a relation holds on a tuple of pairs iff it holds on both coordinate tuples.

Algebra notions. AAA is idempotent if fA(a,…,a)=af^A(a,\dots,a)=afA(a,…,a)=a for every basic symbol fff of every arity nnn, n=0n=0n=0 included. S⊆AS\subseteq AS⊆A is a subuniverse if it is closed under every basic operation (it may be empty). BBB is absorbing if it is a subuniverse and there is a term ttt of arity n≥1n\ge1n≥1 with tA(a0,…,an−1)∈Bt^A(a_0,\dots,a_{n-1})\in BtA(a0​,…,an−1​)∈B whenever ai∈Ba_i\in Bai​∈B for every iii except possibly one. BBB is minimal absorbing if it is nonempty and absorbing, and every nonempty absorbing C⊆BC\subseteq BC⊆B equals BBB. AAA has a proper absorbing subuniverse if some absorbing BBB satisfies ∅≠B≠A\emptyset\neq B\neq A∅=B=A.

Relations R⊆A×BR\subseteq A\times BR⊆A×B. RRR is subdirect if both projections are onto. a∼a′a\sim a'a∼a′ if some bbb has (a,b),(a′,b)∈R(a,b),(a',b)\in R(a,b),(a′,b)∈R. RRR is linked if any two elements of π1(R)\pi_1(R)π1​(R) are joined by a finite (possibly empty) ∼\sim∼-chain. The bipartite adjacency on A⊔BA\sqcup BA⊔B makes aaa and bbb adjacent (both orders) iff (a,b)∈R(a,b)\in R(a,b)∈R; there are no AAA–AAA or BBB–BBB edges. x∈A⊔Bx\in A\sqcup Bx∈A⊔B is in a minimal absorbing set if it lies in a minimal absorbing subuniverse of its own summand.

Taylor. A Taylor datum consists of k∈Nk\in\mathbb Nk∈N, a kkk-ary term ttt, and for each j<kj<kj<k two maps σj,τj:{0,…,k−1}→{false,true}\sigma_j,\tau_j:\{0,\dots,k-1\}\to\{\text{false},\text{true}\}σj​,τj​:{0,…,k−1}→{false,true} with σj(j)=false\sigma_j(j)=\text{false}σj​(j)=false and τj(j)=true\tau_j(j)=\text{true}τj​(j)=true. AAA satisfies the datum if AAA is idempotent and, for all j<kj<kj<k and all x,y∈Ax,y\in Ax,y∈A, tA(σj[x,y])=tA(τj[x,y])t^A(\sigma_j[x,y])=t^A(\tau_j[x,y])tA(σj​[x,y])=tA(τj​[x,y]), where false is replaced by xxx and true by yyy.

Digraphs. E⊆A2E\subseteq A^2E⊆A2 is smooth if every vertex has an out-neighbour and an in-neighbour. A walk of algebraic length zzz from aaa to bbb is built inductively: the empty walk at aaa has length 000; appending a forward edge (b,c)∈E(b,c)\in E(b,c)∈E adds 111; appending a backward edge ((c,b)∈E(c,b)\in E(c,b)∈E, traversed from bbb to ccc) subtracts 111.

Cyclic. AAA has a kkk-ary cyclic term operation if some kkk-ary term ttt satisfies tA(a,…,a)=at^A(a,\dots,a)=atA(a,…,a)=a and tA(x0,…,xk−1)=tA(x1,…,xk−1,x0)t^A(x_0,\dots,x_{k-1})=t^A(x_1,\dots,x_{k-1},x_0)tA(x0​,…,xk−1​)=tA(x1​,…,xk−1​,x0​). R⊆AkR\subseteq A^kR⊆Ak is a subpower if it is closed under coordinatewise basic operations, and cyclic if it is closed under the same shift.

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