Barto–Kozik Claim 3.11: non-absorbing case of the Loop Lemma
ProvedBKAbsorption.loop_nonabsorbing_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 lies in the Taylor variety given by a Taylor datum . Suppose is weakly connected and of algebraic length (witnessed by ), and no nonempty subuniverse absorbs . Then either has a loop at some vertex of , or there is a nonempty subuniverse such that is smooth and of algebraic length .
This is the second case of the paper's proof of Theorem 3.6: for the least with , Theorem 2.3 gives ; then is the smooth part of (Claim 3.11), and gives a loop.
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, Claim 3.11 (non-absorbing case of the Loop Lemma, relative form). Let `A` be a
finite algebra in the Taylor variety of `T`, `E ≤ A²` a subuniverse, and `S` a subuniverse of `A`
such that `(S, E ∩ S²)` is smooth, weakly connected and of algebraic length `1`, and such that
no nonempty proper subuniverse of `S` absorbs `S` (relative absorption). Then either
`E` has a loop in `S`, or there is a nonempty subuniverse `B ⊊ S` such that `(B, E ∩ B²)` is
smooth and of algebraic length `1`. -/
theorem loop_nonabsorbing_step {A : Type w} [L.Structure A] [Finite A] (T : TaylorDatum L)
(hA : IsTaylorAlg T 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)
(hconn : ∀ x ∈ S, ∃ z, Walk ((E : Set (A × A)) ∩ S ×ˢ S) a x z)
(hnoabs : ∀ C : Set A, C ⊆ S → C.Nonempty →
(IsSubuniverse L C ∧ ∃ (n : ℕ) (t : L.Term (Fin n)), 0 < n ∧
∀ (k : Fin n) (x : Fin n → A), (∀ i, x i ∈ S) → (∀ i, i ≠ k → x i ∈ C) →
t.realize x ∈ C) → C = S) :
(∃ x ∈ S, (x, x) ∈ E) ∨
∃ B : Set A, B ⊂ S ∧ B.Nonempty ∧ IsSubuniverse L B ∧
(∀ x ∈ B, (∃ y ∈ B, (x, y) ∈ E) ∧ ∃ y ∈ B, (y, x) ∈ E) ∧
∃ b ∈ B, Walk ((E : Set (A × A)) ∩ B ×ˢ B) b b 1 := by sorry
end BKAbsorption