additive_valuation_erase_of_mem
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.
$\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.
uses
eq_sub_iff_add_eq.mpr,Finset.sum_erase_addexact 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$.
- The definition of `additive_valuation` is definitionally the finite sum $\sum_{j \in S} u(j)$, so `Finset.sum_erase_add` applies directly without an explicit rewrite of the definition.
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.
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)