AFTD Auto-Formalizing Theoretical Domains

bundle_remove_k_value_le

theoremverified

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.

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

    lines 5–13

    uses Finset.mem_powerset.symm, Finset.finite_toSet

      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
  2. 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`).

    lines 14–15

    uses Finite.bddBelow_range

      have h_bdd : BddBelow (Set.range (fun (Y : {X : Finset α // X ⊆ S ∧ X.card ≤ k}) => v (S \ Y.val))) :=
        Finite.bddBelow_range _
  3. 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`).

    lines 16–17

    uses ciInf_le

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

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

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