Minimal absorbing subuniverses and linked relations
ProvedBKAbsorption.minabs_propertiesis a signature without relation symbols. and are finite algebras in one Taylor variety: both are idempotent and satisfy the identities of one fixed Taylor term. ( 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 . : is a subuniverse of (coordinatewise operations) with both projections onto. is linked: any two elements of its first projection are joined by a chain whose consecutive elements have a common -neighbour. Let . (i) If is linked and then is linked. (ii) If , and , then . (iii) If moreover is linked, then and . (iv) If is linked and , there is with . (v) If is linked, any two elements (each in or in ) lying in minimal absorbing subuniverses of or are joined by a path in the bipartite graph of all of whose vertices lie in minimal absorbing subuniverses of or .
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, Proposition 2.15. Let `A, B` be finite algebras in a Taylor variety (one Taylor
datum `T`) and `R ≤_S A × B`.
(i) If `R` is linked and `E ⊴ R`, then `E` is linked.
(ii) If `C ⊴⊴ A`, `D ⊴⊴ B` and `(C × D) ∩ R ≠ ∅`, then `(C × D) ∩ R ≤_S C × D` (its projections are `C` and `D`).
(iii) If `R` is linked, `C ⊴⊴ A`, `D ⊴⊴ B` and `(C × D) ∩ R ≠ ∅`, then `C × D ⊴⊴ R`
(in particular `C × D ⊆ R`).
(iv) If `R` is linked and `C ⊴⊴ A`, then there is `D ⊴⊴ B` with `C × D ⊆ R`.
(v) If `R` is linked and `c, d` (each in `A` or in `B`) lie in minimal absorbing subalgebras of
`A` or `B`, then `c` and `d` are linked via elements `c₀, …, c_j` each of which lies in some
minimal absorbing subalgebra of `A` or `B`. -/
theorem minabs_properties {A : Type w} {B : Type w'} [L.Structure A] [L.Structure B]
[Finite A] [Finite B] (T : TaylorDatum L) (hA : IsTaylorAlg T A) (hB : IsTaylorAlg T B)
(R : L.Substructure (A × B)) (hsd : Subdirect (R : Set (A × B))) :
(Linked (R : Set (A × B)) → ∀ E : Set R, IsAbsorbing L E →
Linked (Subtype.val '' E : Set (A × B))) ∧
(∀ (C : Set A) (D : Set B), MinAbsorbing L C → MinAbsorbing L D →
(C ×ˢ D ∩ (R : Set (A × B))).Nonempty →
Prod.fst '' (C ×ˢ D ∩ (R : Set (A × B))) = C ∧
Prod.snd '' (C ×ˢ D ∩ (R : Set (A × B))) = D) ∧
(Linked (R : Set (A × B)) → ∀ (C : Set A) (D : Set B), MinAbsorbing L C →
MinAbsorbing L D → (C ×ˢ D ∩ (R : Set (A × B))).Nonempty →
C ×ˢ D ⊆ (R : Set (A × B)) ∧ MinAbsorbing L {x : R | (x : A × B) ∈ C ×ˢ D}) ∧
(Linked (R : Set (A × B)) → ∀ C : Set A, MinAbsorbing L C →
∃ D : Set B, MinAbsorbing L D ∧ C ×ˢ D ⊆ (R : Set (A × B))) ∧
(Linked (R : Set (A × B)) → ∀ c d : A ⊕ B, InMinAbs L c → InMinAbs L d →
Relation.ReflTransGen
(fun x y => LinkAdj (R : Set (A × B)) x y ∧ InMinAbs L x ∧ InMinAbs L y) c d) := by sorry
end BKAbsorptionRead-back
What the Lean code literally says, in plain math · claude-opus-5-5
Let be finite algebras both idempotent and satisfying the Taylor identities of one datum , and let be a subalgebra with , . Then all five of the following hold.
- If is linked, then for every that is absorbing in the algebra (induced operations), , viewed as a subset of , is linked (any two elements of are joined by a chain of common-neighbour steps inside ).
- (No linkedness assumed.) If is minimal absorbing in , is minimal absorbing in and , then and .
- If is linked, are minimal absorbing in and , then and is a minimal absorbing subuniverse of the algebra .
- If is linked and is minimal absorbing in , there is minimal absorbing in with .
- If is linked, then for any in the disjoint union , each lying in some minimal absorbing subuniverse of its own algebra, there is a sequence () in with each consecutive pair adjacent in the bipartite graph of ( and adjacent iff ) and every lying in a minimal absorbing subuniverse of (if ) or of (if ).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.