§6, p. 354 (after (27)) — X̄ is the smallest set of 𝒞 containing X; X̄ ∪ Ȳ = (X ∪ Y)‾ and X̄ ∩ Ȳ ⊇ (X ∩ Y)‾
ProvedSchrijverSFM.Ring.closure_union_interclosurelatticep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1ring-family
Let be a finite set and a ring family on with . For let be the intersection of all sets of containing . Then:
- for every , , , and for every with ; that is, is the smallest set in containing ;
- for all ,
These closure identities are the parenthetical remark that justifies the last two steps of display (27).
Formalization Note Item 1 is the defining property "the smallest set in containing " of p. 354, stated for the Finset.inf encoding of the closure; it needs so that some set of contains .
Preamble
import Mathlib import Definitions.Def_NonmonotoneSubmod_Shared_Submodular import Definitions.Def_SchrijverSFM_Ring_Setting
Formal statement
namespace SchrijverSFM.Ring
theorem closure_union_inter {V : Type} [Fintype V] [DecidableEq V]
(C : Set (Finset V)) (hC : IsRingFamily C) (huniv : Finset.univ ∈ C) :
(∀ X : Finset V, closure C X ∈ C ∧ X ⊆ closure C X ∧
∀ Y ∈ C, X ⊆ Y → closure C X ⊆ Y) ∧
∀ X Y : Finset V, closure C X ∪ closure C Y = closure C (X ∪ Y) ∧
closure C (X ∩ Y) ⊆ closure C X ∩ closure C Y := by sorry
end SchrijverSFM.Ring
Source
Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time, J. Combin. Theory Ser. B 80 (2000), p. 354, §6, definition of X̄ before (26) and parenthetical remark after (27)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.