AFTD Auto-Formalizing Theoretical Domains

additive_valuation_erase_of_mem

theoremverified

Removing a good belonging to a finite bundle subtracts exactly its item value from the additive value of that bundle.

Statement

theorem additive_valuation_erase_of_mem {m : ℕ} (u : Fin m → ℝ) (S : Finset (Fin m)) (g : Fin m) (hg : g ∈ S) :
    additive_valuation u (S.erase g) = additive_valuation u S - u g
Source
Helper for efx_four_agents_additive_exists (OP-7), campaign session IN-404, 2026-11-01.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
Used by 4
  • efx_exists_of_two_universal_small_goods_irLet m and n be natural numbers with n positive. There are m+2 goods with nonnegative real additive values for n agents. Each agent values…
  • is_efx_goods_iff_bundle_totalsFor real additive valuations, EFX is equivalent to the following total-value inequalities: for every pair of distinct agents i,j and each…
  • is_efx_goods_insert_of_unenvied_of_minAdding a good to an unenvied agent preserves EFX if every other agent values the new good no more than every old good in that recipient's…
  • is_efx_goods_nat_cast_iffFor natural-number item values, EFX after casting values to the reals is equivalent to all natural-number inequalities comparing each…

The proof, explained

The additive valuation of a bundle is defined as the sum of the valuations of its constituent items. Because the item $g$ belongs to $S$, the sum over $S$ decomposes into the sum over $S \setminus \{g\}$ plus the value $u(g)$. Rearranging this additive relation by subtracting $u(g)$ from both sides gives the desired formula.

  1. $\text{additive\_valuation}(u, S \setminus \{g\}) = \text{additive\_valuation}(u, S) - u(g)$

    By definition, the additive valuation is the finite sum $\sum_{j \in S} u(j)$. Because $g \in S$, `Finset.sum_erase_add` establishes that summing over $S \setminus \{g\}$ and adding $u(g)$ yields the total sum over $S$. Applying `eq_sub_iff_add_eq.mpr` rearranges this additive equality $a + c = b$ into $a = b - c$, directly completing the proof.

    line 5

    uses eq_sub_iff_add_eq.mpr, Finset.sum_erase_add

      exact eq_sub_iff_add_eq.mpr (Finset.sum_erase_add S u hg)
eq_sub_iff_add_eq.mpr
If $a + c = b$, then $a = b - c$.
Finset.sum_erase_add
For any finite set $s$, function $f$, and element $a \in s$, the sum of $f$ over $s \setminus \{a\}$ plus $f(a)$ equals the sum of $f$ over $s$.

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

open Function Finsettheorem additive_valuation_erase_of_mem {m : ℕ} (u : Fin m → ℝ) (S : Finset (Fin m)) (g : Fin m) (hg : g ∈ S) :    additive_valuation u (S.erase g) = additive_valuation u S - u g := by  exact eq_sub_iff_add_eq.mpr (Finset.sum_erase_add S u hg)
See it in the graphDiscuss this resultChallenge it