§5, p. 10 — M_BLP+Aff is a minion: minors of objects are objects, minors compose, the identity minor is trivial
ProvedPCSPBLPAff.Characterization.minion_lawsminionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1promise-csp
Let be finite sets, and , and let be an object of with coordinate set : , , , and . With the minor (and likewise for ), the following hold:
- is again an object of ;
- and ;
- and .
This is the claim, stated after Definition 6, that is indeed a minion (Definition 5). Item 1 is what makes the minion homomorphism condition meaningful.
Formalization Note Coordinate sets are arbitrary finite types rather than only ; the free structure uses objects indexed by and by tuples.
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Characterization_Setting
Formal statement
namespace PCSPBLPAff.Characterization
/-- §5, p. 10: `M_BLP+Aff` is a minion. The minor of an object is an object (in particular
`w(i) = 0 ⟹ r(i) = 0` is preserved), minors compose, `((w, r)_{/π})_{/σ} = (w, r)_{/σ ∘ π}`,
and the minor along the identity is the identity. -/
theorem minion_laws {ι κ μ : Type} [Fintype ι] [Fintype κ] [Fintype μ]
[DecidableEq ι] [DecidableEq κ] [DecidableEq μ]
(π : ι → κ) (σ : κ → μ) (w : ι → ℚ) (r : ι → ℤ) (h : IsBLPAffObj w r) :
IsBLPAffObj (minorQ π w) (minorZ π r) ∧
minorQ σ (minorQ π w) = minorQ (σ ∘ π) w ∧ minorZ σ (minorZ π r) = minorZ (σ ∘ π) r ∧
minorQ id w = w ∧ minorZ id r = r := by sorry
end PCSPBLPAff.Characterization
Source
arXiv:1907.04383v3, §5, p. 10, sentence after Definition 6 ("It is easy to check this indeed defines a minion")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.