Barto–Kozik Thm 4.2, simple case (Claims 4.6–4.14)
ProvedBKAbsorption.cyclic_simple_corecspcyclic-termsuniversal-algebra
Let be a finite algebra in a Taylor variety (given by a Taylor datum ) and let be a prime. Assume
- is simple: every congruence of is the identity or the full relation, and
- every proper subalgebra of has a -ary cyclic term operation.
Then has a -ary cyclic term operation.
This is the core of the proof of Theorem 4.2 for a minimal counterexample: a cyclic subdirect subpower without constant tuples is ruled out by proving properties (P1) and (P2) by induction on (Claims 4.6–4.12) and applying the Loop Lemma (Theorem 3.6) to the digraph on (Claims 4.13–4.14).
Formalization note. A congruence is an equivalence relation r compatible with all basic operations; proper subalgebras are substructures with carrier different from .
Preamble
import Definitions.Def_BKAbsorption_defs universe u v w w' open FirstOrder FirstOrder.Language
Formal statement
namespace BKAbsorption
variable {L : FirstOrder.Language.{u, v}} [L.IsAlgebraic]
/-- Barto–Kozik, proof of Theorem 4.2 for a minimal counterexample (Claims 4.6–4.14, using the
Loop Lemma 3.6). Let `A` be a finite algebra in the Taylor variety of `T` and `p > |A|` a prime.
Assume `A` is simple (every congruence is trivial or full) and every proper subalgebra of `A` has
a `p`-ary cyclic term operation. Then `A` has a `p`-ary cyclic term operation. -/
theorem cyclic_simple_core {A : Type w} [L.Structure A] [Finite A] (T : TaylorDatum L)
(hA : IsTaylorAlg T A) (p : ℕ) (hp : p.Prime) (hpA : Nat.card A < p)
(hsimple : ∀ r : A → A → Prop, Equivalence r →
(∀ (n : ℕ) (f : L.Functions n) (x y : Fin n → A), (∀ i, r (x i) (y i)) →
r (Structure.funMap f x) (Structure.funMap f y)) →
(∀ a b, r a b → a = b) ∨ ∀ a b, r a b)
(hsub : ∀ S : L.Substructure A, (S : Set A) ≠ Set.univ → HasCyclicTermOp L S p) :
HasCyclicTermOp L A p := by sorry
end BKAbsorption
Source
Barto–Kozik, Absorbing subalgebras, cyclic terms and the constraint satisfaction problem, LMCS 8(1:07) 2012, arXiv:1201.0557, Section 4, proof of Theorem 4.2, Claims 4.6–4.14 (p. 21–24).