AFTD Auto-Formalizing Theoretical Domains

le_knapsack_opt

theoremverified

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.

  1. 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.

    lines 6–7

      classical
      rw [knapsack_opt]
  2. 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.

    lines 8–9

      haveI : Finite {T : Finset (Fin m) // T ⊆ C ∧ additive_valuation s T ≤ b} := by
        infer_instance
  3. The 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.

    lines 10–13

    uses Finite.le_ciSup

      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⟩
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).

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

/-- 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⟩
See it in the graphDiscuss this resultChallenge it