le_knapsack_opt
Every budget-feasible subset S of C achieves value at most OPT(C).
Statement
theorem le_knapsack_opt {m : ℕ} (v : Fin m → ℝ) (s : Fin m → ℝ) (b : ℝ)
(C : Finset (Fin m)) (S : Finset (Fin m)) (hSC : S ⊆ C)
(hSb : additive_valuation s S ≤ b) :
additive_valuation v S ≤ knapsack_opt v s b C- Source
- arXiv:2611.12740 Section 3.1
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- knapsack_optFor an item subset C and budget b, OPT(C) is the maximum additive value v(S) over all subsets S ⊆ C with total size s(S) ≤ b.
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
Read back from the Lean
For any natural number $m$, item values $v : \text{Fin } m \to \mathbb{R}$, item sizes $s : \text{Fin } m \to \mathbb{R}$, capacity bound $b : \mathbb{R}$, candidate item set $C : \text{Finset } (\text{Fin } m)$, and subset $S : \text{Finset } (\text{Fin } m)$: if $S \subseteq C$ and the additive valuation of $S$ under $s$ is at most $b$ (i.e., $\sum_{j \in S} s(j) \le b$), then the additive valuation of $S$ under $v$ is at most the optimal knapsack value $\text{knapsack\_opt}(v, s, b, C)$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The knapsack optimum OPT(C) is defined as the supremum of valuations over all budget-feasible subsets of C. Because the universe of items is finite, the collection of such subsets is finite. Since S is budget-feasible and contained in C, it belongs to this collection, so its valuation is at most the supremum by Finite.le_ciSup.
By definition of knapsack_opt, it suffices to show that the valuation of S is at most the supremum over all budget-feasible subsets of C.
We enable classical logic and unfold the definition of knapsack_opt, which is defined as the supremum (⨆) of additive_valuation v T over all subsets T ⊆ C satisfying additive_valuation s T ≤ b.
classical rw [knapsack_opt]The subtype of budget-feasible subsets of C is finite.
Because the universe Fin m is finite, its power set Finset (Fin m) is finite. The subtype of subsets satisfying the inclusion and budget constraints is therefore also finite, which Lean synthesizes automatically via typeclass inference.
haveI : Finite {T : Finset (Fin m) // T ⊆ C ∧ additive_valuation s T ≤ b} := by infer_instanceThe valuation of S is at most knapsack_opt v s b C.
Since S satisfies S ⊆ C and additive_valuation s S ≤ b, it witnesses an element ⟨S, hSC, hSb⟩ of the feasible subtype. By Finite.le_ciSup, the value of additive_valuation v at this element is at most the supremum over all feasible subsets.
uses
Finite.le_ciSupexact Finite.le_ciSup (fun T : {T : Finset (Fin m) // T ⊆ C ∧ additive_valuation s T ≤ b} => additive_valuation v T.val) ⟨S, hSC, hSb⟩
Finite.le_ciSup- For any function f from a finite index type to a conditionally complete lattice, the value f(i) at any index i is at most the supremum ⨆ j, f(j).
- On paper, finiteness of the set of feasible subsets is taken for granted, but Lean requires an explicit `Finite` instance to invoke `Finite.le_ciSup` on a conditionally complete lattice like ℝ.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Every budget-feasible subset of C achieves value at most OPT(C). -/theorem le_knapsack_opt {m : ℕ} (v : Fin m → ℝ) (s : Fin m → ℝ) (b : ℝ) (C : Finset (Fin m)) (S : Finset (Fin m)) (hSC : S ⊆ C) (hSb : additive_valuation s S ≤ b) : additive_valuation v S ≤ knapsack_opt v s b C := by classical rw [knapsack_opt] haveI : Finite {T : Finset (Fin m) // T ⊆ C ∧ additive_valuation s T ≤ b} := by infer_instance exact Finite.le_ciSup (fun T : {T : Finset (Fin m) // T ⊆ C ∧ additive_valuation s T ≤ b} => additive_valuation v T.val) ⟨S, hSC, hSb⟩