A projection-closed family containing contains every dictator
ProvedSymBoolPCSP.PolChar.dictator_mem_of_projectionClosedgalois-correspondencepolymorphismspromise-cspuniversal-algebra
Let be a family of functions over a domain (for each arity , a set of functions ). Suppose is projection-closed, i.e. of arity implies for every with , and suppose . Then for every arity and every the dictator
belongs to .
This is the step in the proof of Lemma 6.7 of Brakensiek–Guruswami that gives for the canonical promise relation; more generally it says that projection-closed families containing the identity contain all projections, as polymorphism families always do.
Formalization Note The arity is positive automatically because exists. ProjectionClosed and ContainsId are the platform definitions from SymBoolPCSP_PolChar_Basic.
Preamble
import Mathlib import Definitions.Def_SymBoolPCSP_PolChar_Basic
Formal statement
namespace SymBoolPCSP.PolChar
/-- A projection-closed family of functions containing the unary identity contains every
dictator `y ↦ y_j` of every arity `R`. -/
theorem dictator_mem_of_projectionClosed {D : Type} (F : FunFamily D)
(hpc : ProjectionClosed F) (hid : ContainsId F) {R : ℕ} (j : Fin R) :
(fun y : Fin R → D => y j) ∈ F R := by sorry
end SymBoolPCSP.PolChar
Source
J. Brakensiek, V. Guruswami, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, arXiv:1704.01937v2, §6.2, proof of Lemma 6.7, pp. 29–30