§6.1 remark — P′ ⊆ P ⊆ Q ⊆ Q′ makes (P′, Q′) ppp-definable from (P, Q)
ProvedSymBoolPCSP.Galois.sandwichgalois-correspondencep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1polymorphismspromise-csp
Let be a finite domain and let and be relations of the same arity on . If
then the promise relation is ppp-definable from the one-relation family .
This is the basic way of weakening a promise relation within the ppp-definable closure: shrinking the -side and enlarging the -side never leaves it. It is the last step of the proof of Theorem 6.1, applied to .
Formalization Note "From " is the one-relation family single P, single Q on the symbol ().
Preamble
import Mathlib import Definitions.Def_SymBoolPCSP_Galois_Basic
Formal statement
namespace SymBoolPCSP.Galois
open PCSPBLPAff.Symmetric
/-- §6.1, p. 27 (after Definition 6.2): if `(P, Q)` and `(P', Q')` have the same arity `k` and
`P' ⊆ P ⊆ Q ⊆ Q'`, then `(P', Q')` is ppp-definable from the one-relation family `{(P, Q)}`. -/
theorem sandwich {D : Type} [Fintype D] [DecidableEq D] {k : ℕ}
(P Q P' Q' : Set (Fin k → D)) (hP' : P' ⊆ P) (hPQ : P ⊆ Q) (hQ' : Q ⊆ Q') :
PPPDefinable (single P) (single Q) P' Q' := by sorry
end SymBoolPCSP.Galois
Source
J. Brakensiek, V. Guruswami, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, arXiv:1704.01937v2, p. 27, §6.1, remark after Definition 6.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.