AFTD Auto-Formalizing Theoretical Domains

submod_biUnion_le_sum

theoremverified

A monotone submodular set function with v(empty) = 0 is subadditive over a finite family of sets.

Statement

theorem submod_biUnion_le_sum {m n : ℕ} (v : Finset (Fin m) → ℝ) (hmono : Monotone v)
    (hsub : is_submodular v) (h0 : v ∅ = 0) (K : Finset (Fin n)) (B : Fin n → Finset (Fin m)) :
    v (K.biUnion B) ≤ ∑ j ∈ K, v (B j)
Source
step towards mxs_fair_imp_prop1_fair_of_submodular (open problem 3 of arXiv:2502.02815 v3, Sec. 6)
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • is_submodularA set function is submodular: for S inside T and j outside T, the marginal value of j over T is at most its marginal value over S.
  • submod_union_marginal_leFor a monotone submodular set function and S inside T, adding a set U gains at most as much on top of T as on top of S.
Used by 2

Lean source view module on GitHub

/-- A monotone submodular set function with `v ∅ = 0` is subadditive over a family of sets. -/theorem submod_biUnion_le_sum {m n : ℕ} (v : Finset (Fin m) → ℝ) (hmono : Monotone v)    (hsub : is_submodular v) (h0 : v ∅ = 0) (K : Finset (Fin n)) (B : Fin n → Finset (Fin m)) :    v (K.biUnion B) ≤ ∑ j ∈ K, v (B j) := by  induction K using Finset.induction_on with  | empty => simp [h0]  | insert a K ha ih =>    rw [Finset.biUnion_insert, Finset.sum_insert ha]    have h := submod_union_marginal_le v hmono hsub (Finset.empty_subset (B a)) (K.biUnion B)    rw [Finset.empty_union, h0] at h    linarith
See it in the graphDiscuss this resultChallenge it