Loop Lemma
ProvedBKAbsorption.loop_lemmais a signature without relation symbols. A finite algebra lies in a Taylor variety: it is idempotent ( for every basic operation) and satisfies the identities of a fixed Taylor term of arity : for each , with , , . ( absorbs ): is a subuniverse and some term operation gives whenever all but at most one lie in ; proper means ; : is nonempty, absorbs , and no proper subalgebra of absorbs . Let be a subuniverse of such that the digraph is smooth (every vertex has an incoming and an outgoing edge) and has algebraic length (some vertex is joined to itself by an oriented path with one more forward than backward edge). Then for some . Moreover, if a nonempty absorbing subuniverse of lies in a weak component of algebraic length , then there are and with .
import Definitions.Def_BKAbsorption_defs universe u v w w' open FirstOrder FirstOrder.Language
namespace BKAbsorption
variable {L : FirstOrder.Language.{u, v}} [L.IsAlgebraic]
/-- Barto–Kozik, Theorem 3.6 (Loop Lemma). Let `A` be a finite algebra in a Taylor variety and
let `G = (A, E)` be a smooth digraph of algebraic length `1` such that `E` is a subuniverse of
`A²`. Then `G` contains a loop. Moreover, if there is a (nonempty) absorbing subuniverse `I`
of `A` contained in a weak component of `G` of algebraic length `1`, then the loop can be found
in some `J` with `J ⊴⊴ A`. -/
theorem loop_lemma {A : Type w} [L.Structure A] [Finite A] (T : TaylorDatum L)
(hA : IsTaylorAlg T A) (E : L.Substructure (A × A)) (hsm : Smooth (E : Set (A × A)))
(hlen : ∃ a, Walk (E : Set (A × A)) a a 1) :
(∃ a, (a, a) ∈ E) ∧
(∀ I : Set A, IsAbsorbing L I → I.Nonempty →
(∃ a, Walk (E : Set (A × A)) a a 1 ∧ ∀ x ∈ I, ∃ z, Walk (E : Set (A × A)) a x z) →
∃ J : Set A, MinAbsorbing L J ∧ ∃ a ∈ J, (a, a) ∈ E) := by sorry
end BKAbsorptionRead-back
What the Lean code literally says, in plain math · claude-opus-5-5
Let be a finite algebra that is idempotent and satisfies the Taylor identities of a datum . Let be a subalgebra of (coordinatewise), regarded as the edge set of a digraph on , such that:
- is smooth: every vertex has an out-edge and an in-edge;
- some vertex admits a closed oriented walk from to of algebraic length , where algebraic length (number of edges traversed forwards) (number traversed backwards); vertices and edges may repeat.
Then:
- has a loop: for some ; and
- for every nonempty absorbing subuniverse of such that there is a vertex carrying a closed walk of algebraic length with every reachable from by some oriented walk (of any algebraic length), there are a minimal absorbing subuniverse of and some with .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.