Lemma 17 for M = M_BLP+Aff, p. 15 — F_{M_BLP+Aff}(A) → B iff M_BLP+Aff has a minion homomorphism to Pol(A, B)
ProvedPCSPBLPAff.Characterization.lemma_17free-structureminionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1polymorphism
Let be a promise template on finite domains. The following are equivalent:
- the free structure admits a homomorphism to ;
- there exists a minion homomorphism from to .
This is the fundamental property of free structures ([BBKO19, Lemma 4.4]) and the last step of the proof of Lemma 7.
Formalization Note The page states the lemma for an arbitrary minion ; this item is its specialization to , the only case the mission uses.
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Characterization_Setting
Formal statement
namespace PCSPBLPAff.Characterization
/-- Lemma 17 ([BBKO19, Lemma 4.4]), p. 15, for the minion `M = M_BLP+Aff`: for a promise
template `(𝔸, 𝔹)`, the free structure `F_{M_BLP+Aff}(𝔸)` has a homomorphism to `𝔹` iff
`M_BLP+Aff` admits a minion homomorphism to `Pol(𝔸, 𝔹)`. -/
theorem lemma_17 {τ : Type} {ar : τ → ℕ} {A B : Type} [Fintype A] [DecidableEq A] [Fintype B]
(𝔸 : PCSPBLPAff.Symmetric.RelStruct τ ar A) (𝔹 : PCSPBLPAff.Symmetric.RelStruct τ ar B) (hT : PCSPBLPAff.Symmetric.IsPromiseTemplate 𝔸 𝔹) :
(∃ σ : FreeDom A → B, PCSPBLPAff.Symmetric.IsHom (freeStruct 𝔸) 𝔹 σ) ↔ HasMinionHomToPol 𝔸 𝔹 := by sorry
end PCSPBLPAff.Characterization
Source
arXiv:1907.04383v3, Lemma 17, p. 15 (citing [BBKO19, Lemma 4.4]), specialized to M = M_BLP+Aff
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.