bundle_remove_k_value_le
Given a type of goods α with decidable equality, a valuation function v : Finset α → ℝ, a natural number k : ℕ, a bundle S : Finset α, and a sub-bundle X : Finset α satisfying X ⊆ S and X.card ≤ k, the value bundle_remove_k_value v k S is at most v (S \ X).
Statement
theorem bundle_remove_k_value_le {α : Type*} [DecidableEq α] (v : Finset α → ℝ) (k : ℕ) (S : Finset α) (X : Finset α) (hX1 : X ⊆ S) (hX2 : X.card ≤ k) : bundle_remove_k_value v k S ≤ v (S \ X)
- Source
- arXiv:2610.34625, Lemma 3.2
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- bundle_remove_k_valueGiven a type of goods α with decidable equality, a valuation function v : Finset α → ℝ, a natural number k : ℕ, and a bundle S : Finset α,…
- Used by 1
- eefx_bundle_imp_approx_efkLet n ≥ 3 and let σ be an allocation of m goods among n agents with nonnegative additive valuations u such that every agent's bundle is…
Read back from the Lean
For any type α with decidable equality, any function v : Finset α → ℝ, any natural number k, and any finite sets S, X : Finset α, if X ⊆ S and the cardinality of X is at most k, then bundle_remove_k_value v k S ≤ v (S \ X).
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
By definition, bundle_remove_k_value v k S is the infimum of v(S \ Y) over all sub-bundles Y ⊆ S of size at most k. The collection of all such sub-bundles is finite because it is a subset of the powerset of S, which ensures that the range of values is bounded below. Consequently, by the standard infimum bound in conditionally complete lattices, the infimum is bounded above by the value v(S \ X) attained at the particular sub-bundle X.
The subtype of sub-bundles Y ⊆ S with |Y| ≤ k is finite.
The set of all sub-bundles of S is identical to the powerset of S by `Finset.mem_powerset.symm`. Since S is a finite set (`Finset`), its powerset is finite (`Finset.finite_toSet`). The sub-bundles satisfying the cardinality constraint |Y| ≤ k form a subset of this powerset, and any subset of a finite set is finite. Therefore, the corresponding subtype is finite.
uses
Finset.mem_powerset.symm,Finset.finite_toSethave : Finite {X : Finset α // X ⊆ S ∧ X.card ≤ k} := by have h1 : {X : Finset α | X ⊆ S ∧ X.card ≤ k}.Finite := by have h2 : {X : Finset α | X ⊆ S}.Finite := by have : {X : Finset α | X ⊆ S} = (S.powerset : Set (Finset α)) := by ext; exact Finset.mem_powerset.symm rw [this] exact Finset.finite_toSet S.powerset exact h2.subset (fun Y hY => hY.1) exact h1.to_subtype
The set of values v(S \ Y) for sub-bundles Y ⊆ S with |Y| ≤ k is bounded below.
Since the indexing subtype of valid sub-bundles was just shown to be finite, the range of any function from it into ℝ is bounded below (`Finite.bddBelow_range`).
uses
Finite.bddBelow_rangehave h_bdd : BddBelow (Set.range (fun (Y : {X : Finset α // X ⊆ S ∧ X.card ≤ k}) => v (S \ Y.val))) := Finite.bddBelow_range _
The infimum bundle_remove_k_value v k S is at most v(S \ X).
Unfolding the definition, `bundle_remove_k_value v k S` is the infimum ⨅ Y, v(S \ Y) over all sub-bundles Y ⊆ S with |Y| ≤ k. The hypotheses X ⊆ S and |X| ≤ k give an element of this indexing subtype. Since the range is bounded below, the infimum is at most the value at X (`ciInf_le`).
uses
ciInf_leunfold bundle_remove_k_value exact ciInf_le h_bdd ⟨X, ⟨hX1, hX2⟩⟩
Finset.mem_powerset.symm- A finite set s is a subset of t if and only if s is an element of the powerset of t.
Finset.finite_toSet- The coercion of a `Finset` to a `Set` is finite.
Finite.bddBelow_range- The range of any function from a finite type into a preorder is bounded below.
ciInf_le- In a conditionally complete lattice, if the range of a function is bounded below, its infimum is at most its value at any point.
- In Lean's conditionally complete lattice library, the infimum inequality `ciInf_le` requires proving that the indexed set is bounded below (`BddBelow`). On paper this is immediate because the infimum is taken over a finite set, but formally it requires first proving that the indexing subtype of sub-bundles is `Finite`.
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.
/-- Removing any sub-bundle X of at most k goods from S leaves at least the value D^{(k)}(S). -/theorem bundle_remove_k_value_le {α : Type*} [DecidableEq α] (v : Finset α → ℝ) (k : ℕ) (S : Finset α) (X : Finset α) (hX1 : X ⊆ S) (hX2 : X.card ≤ k) : bundle_remove_k_value v k S ≤ v (S \ X) := by have : Finite {X : Finset α // X ⊆ S ∧ X.card ≤ k} := by have h1 : {X : Finset α | X ⊆ S ∧ X.card ≤ k}.Finite := by have h2 : {X : Finset α | X ⊆ S}.Finite := by have : {X : Finset α | X ⊆ S} = (S.powerset : Set (Finset α)) := by ext; exact Finset.mem_powerset.symm rw [this] exact Finset.finite_toSet S.powerset exact h2.subset (fun Y hY => hY.1) exact h1.to_subtype have h_bdd : BddBelow (Set.range (fun (Y : {X : Finset α // X ⊆ S ∧ X.card ≤ k}) => v (S \ Y.val))) := Finite.bddBelow_range _ unfold bundle_remove_k_value exact ciInf_le h_bdd ⟨X, ⟨hX1, hX2⟩⟩