Barto–Kozik Lemma 3.3 + Claims 3.9–3.10: absorbing case of the Loop Lemma
ProvedBKAbsorption.loop_absorbing_stepThroughout, is a finite algebra, is a subuniverse (a digraph on compatible with the operations), and is a subuniverse such that the induced digraph is smooth (every vertex of has an in- and an out-neighbour in ). A walk of algebraic length counts forward edges minus backward edges. Absorption is relative: absorbs if is a subuniverse and some term of positive arity satisfies whenever all and all but at most one .
Assume is idempotent. Let lie on a closed walk of algebraic length in , and let be a nonempty set contained in the weak component of in which absorbs . Then there is a nonempty subuniverse that absorbs such that is smooth, weakly connected and of algebraic length (some lies on a closed walk of algebraic length in and reaches every vertex of ).
This is the first case of the paper's proof of Theorem 3.6: is the smooth part of for the longest initial segment of a fence with (Claim 3.9, Lemma 2.5, Proposition 3.2, Lemma 3.3), and Claim 3.10 shows it is connected of algebraic length 1.
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, Lemma 3.3 + Claims 3.9–3.10 (absorbing case of the Loop Lemma, relative form).
Let `A` be a finite idempotent algebra, `E ≤ A²` a subuniverse, and `S` a subuniverse of `A`
with `(S, E ∩ S²)` smooth. Let `a ∈ S` lie on a closed walk of algebraic length `1` in
`(S, E ∩ S²)`, and let `I ≠ S` be a nonempty subuniverse contained in the weak component of `a`
which absorbs `S` (relative absorption: some term `t` of positive arity sends every `S`-tuple with
all but at most one entry in `I` into `I`). Then there is a nonempty subuniverse `S' ⊊ S`
absorbing `S` such that `(S', E ∩ S'²)` is smooth, weakly connected and of algebraic length `1`. -/
theorem loop_absorbing_step {A : Type w} [L.Structure A] [Finite A] (hid : IsIdempotent L A)
(E : L.Substructure (A × A)) (S : Set A) (hS : IsSubuniverse L S)
(hsm : ∀ x ∈ S, (∃ y ∈ S, (x, y) ∈ E) ∧ ∃ y ∈ S, (y, x) ∈ E)
(a : A) (ha : a ∈ S) (hlen : Walk ((E : Set (A × A)) ∩ S ×ˢ S) a a 1)
(I : Set A) (hIne : I.Nonempty) (hIS : I ≠ S)
(hIc : ∀ x ∈ I, ∃ z, Walk ((E : Set (A × A)) ∩ S ×ˢ S) a x z)
(hIabs : IsSubuniverse L I ∧ ∃ (n : ℕ) (t : L.Term (Fin n)), 0 < n ∧
∀ (k : Fin n) (x : Fin n → A), (∀ i, x i ∈ S) → (∀ i, i ≠ k → x i ∈ I) →
t.realize x ∈ I) :
∃ S' : Set A, S' ⊂ S ∧ S'.Nonempty ∧
(IsSubuniverse L S' ∧ ∃ (n : ℕ) (t : L.Term (Fin n)), 0 < n ∧
∀ (k : Fin n) (x : Fin n → A), (∀ i, x i ∈ S) → (∀ i, i ≠ k → x i ∈ S') →
t.realize x ∈ S') ∧
(∀ x ∈ S', (∃ y ∈ S', (x, y) ∈ E) ∧ ∃ y ∈ S', (y, x) ∈ E) ∧
∃ b ∈ S', Walk ((E : Set (A × A)) ∩ S' ×ˢ S') b b 1 ∧
∀ x ∈ S', ∃ z, Walk ((E : Set (A × A)) ∩ S' ×ˢ S') b x z := by sorry
end BKAbsorption