block_insertion_residual_cost_bound_of_le
Given a type α with decidable equality, a cost function c : α → NNReal, a natural number k : ℕ, a bundle B : Finset α with k ≤ B.card, and a bundle E : Finset α disjoint from B with E.card ≤ k such that c e ≤ c b for all e ∈ E and b ∈ B, the k-chore residual cost chore_residual_cost c k (B ∪ E) is at most ∑ b ∈ B, c b.
Statement
theorem block_insertion_residual_cost_bound_of_le {α : Type*} [DecidableEq α] (c : α → NNReal) (k : ℕ) (B E : Finset α) (hdisj : Disjoint B E) (hkB : k ≤ B.card) (hrk : E.card ≤ k) (h_cost : ∀ e ∈ E, ∀ b ∈ B, c e ≤ c b) : chore_residual_cost c k (B ∪ E) ≤ ∑ b ∈ B, c b
- Source
- arXiv:2611.07468 Lemma B.1
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- chore_residual_costGiven a type α with decidable equality, a cost function c : α → NNReal taking values in the non-negative reals, a natural number k : ℕ,…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 1
- block_insertion_residual_cost_boundGiven a type α with decidable equality, a cost function c : α → NNReal, a natural number k : ℕ with 1 ≤ k, a bundle B : Finset α with k ≤…
Read back from the Lean
Given a type α with decidable equality, a cost function c : α → ℝ≥0, a natural number k, and two finite subsets B, E : Finset α, assume that:
1. B and E are disjoint (Disjoint B E);
2. k ≤ B.card;
3. E.card ≤ k; and
4. for every e ∈ E and every b ∈ B, c e ≤ c b.
Then the chore_residual_cost of B ∪ E with parameter k is at most the total cost of B:
chore_residual_cost c k (B ∪ E) ≤ ∑ b ∈ B, c b.
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
To bound the k-chore residual cost of B ∪ E, the proof first establishes a helper lemma: if |s| ≤ |t| and every element of s costs at most every element of t, then the sum of costs over s is at most that over t. For any candidate removed bundle T ⊆ B ∪ E of size k, decomposing T and E shows that |E \ T| ≤ |B ∩ T|. Applying the helper lemma ensures the leftover chores from E cost no more than the chores from B absorbed into T. Recombining with the leftover chores B \ T bounds the residual cost by the total cost of B, and taking the supremum over T completes the result.
If s is empty, then ∑ x ∈ s, c x ≤ ∑ y ∈ t, c y holds trivially.
We case split on whether s is empty or nonempty. When s = ∅, the sum over s is 0, which is at most the sum over t because all values of the cost function c are non-negative.
rcases s.eq_empty_or_nonempty with rfl | hs · simp
When s is nonempty, t is also nonempty and there exists an element x₀ ∈ s attaining the maximum cost on s.
Since |s| ≤ |t| and s is nonempty, |t| cannot be 0, so t is nonempty. Because s is finite and nonempty, the set of values c(s) has a well-defined maximum, which is achieved at some x₀ ∈ s.
uses
Finset.nonempty_iff_ne_empty,Finset.card_empty,Finset.card_eq_zero.mp,Finset.max'_mem,Finset.mem_image.mp· have ht : t.Nonempty := by rw [Finset.nonempty_iff_ne_empty] rintro rfl rw [Finset.card_empty] at hcard have : s.card = 0 := by omega exact hs.ne_empty (Finset.card_eq_zero.mp this) have hsc : (s.image c).Nonempty := hs.image c obtain ⟨x₀, hx₀, hx₀m⟩ : ∃ x ∈ s, c x = (s.image c).max' hsc := by have hm_mem := Finset.max'_mem (s.image c) hsc rcases Finset.mem_image.mp hm_mem with ⟨x₀, hx₀, heq⟩ exact ⟨x₀, hx₀, heq⟩
For nonempty s, ∑ x ∈ s, c x ≤ ∑ y ∈ t, c y.
Every x ∈ s satisfies c(x) ≤ c(x₀), so ∑ x ∈ s, c(x) ≤ |s| • c(x₀). By assumption, every y ∈ t satisfies c(x₀) ≤ c(y), so |t| • c(x₀) ≤ ∑ y ∈ t, c(y). Since |s| ≤ |t|, multiplying by c(x₀) gives |s| • c(x₀) ≤ |t| • c(x₀). Chaining these three bounds yields the desired inequality.
uses
Finset.sum_le_sum,Finset.le_max',Finset.mem_image_of_mem,Finset.sum_const,nsmul_eq_mulhave h1 : ∑ x ∈ s, c x ≤ (s.card : NNReal) * c x₀ := by have : ∑ x ∈ s, c x ≤ ∑ x ∈ s, c x₀ := by refine Finset.sum_le_sum ?_ intro x hx rw [hx₀m] exact Finset.le_max' (s.image c) (c x) (Finset.mem_image_of_mem c hx) rwa [Finset.sum_const, nsmul_eq_mul] at this have h2 : (t.card : NNReal) * c x₀ ≤ ∑ y ∈ t, c y := by have : ∑ y ∈ t, c x₀ ≤ ∑ y ∈ t, c y := by refine Finset.sum_le_sum ?_ intro y hy exact hle x₀ hx₀ y hy rwa [Finset.sum_const, nsmul_eq_mul] at this have h3 : (s.card : NNReal) * c x₀ ≤ (t.card : NNReal) * c x₀ := by gcongr exact h1.trans (h3.trans h2)
To bound the residual cost chore_residual_cost c k (B ∪ E) by ∑ b ∈ B, c b, it suffices to show that for any subset T ⊆ B ∪ E of cardinality k, the remaining cost ∑ x ∈ (B ∪ E) \ T, c x is at most ∑ b ∈ B, c b.
The residual cost is defined as the supremum of remaining costs over all subsets T ⊆ B ∪ E of size min(k, |B ∪ E|). Since k ≤ |B| ≤ |B ∪ E|, this size is exactly k. By the universal property of the supremum, it suffices to prove the bound for an arbitrary such subset T.
uses
ciSup_le',Finset.card_le_card,Finset.subset_union_left,Nat.min_eq_leftunfold chore_residual_cost refine ciSup_le' ?_ rintro ⟨T, hTsub, hTcard⟩ have hkBE : k ≤ (B ∪ E).card := hkB.trans (Finset.card_le_card Finset.subset_union_left) have hTcard' : T.card = k := by rw [Nat.min_eq_left hkBE] at hTcard exact hTcard
The subset T partitions into (B ∩ T) ∪ (E ∩ T), which implies |E \ T| ≤ |B ∩ T|.
Since T ⊆ B ∪ E, every element of T is in B or E, so T decomposes into the disjoint union of B ∩ T and E ∩ T, giving |T| = |B ∩ T| + |E ∩ T|. Similarly, E decomposes into the disjoint union of E \ T and E ∩ T, so |E \ T| + |E ∩ T| = |E|. Since |E| ≤ k = |T|, linear arithmetic yields |E \ T| ≤ |B ∩ T|.
uses
Finset.mem_union,Finset.mem_inter,Or.inl,Or.inr,Finset.inter_subset_left,Finset.card_union_of_disjoint,Finset.card_sdiff_add_card_interhave hT_decomp : T.card = (B ∩ T).card + (E ∩ T).card := by have hT : T = (B ∩ T) ∪ (E ∩ T) := by ext x simp only [Finset.mem_union, Finset.mem_inter] constructor · intro hx have := hTsub hx simp only [Finset.mem_union] at this rcases this with h | h · exact Or.inl ⟨h, hx⟩ · exact Or.inr ⟨h, hx⟩ · rintro (⟨-, hx⟩ | ⟨-, hx⟩) <;> exact hx have hd : Disjoint (B ∩ T) (E ∩ T) := hdisj.mono Finset.inter_subset_left Finset.inter_subset_left conv_lhs => rw [hT] rw [Finset.card_union_of_disjoint hd] have hE_decomp : (E \ T).card + (E ∩ T).card = E.card := Finset.card_sdiff_add_card_inter E T have hcard_le : (E \ T).card ≤ (B ∩ T).card := by omega
The remaining chores from E cost at most the chores from B included in T: ∑ x ∈ E \ T, c x ≤ ∑ x ∈ B ∩ T, c x.
Any element x ∈ E \ T is in E, and any y ∈ B ∩ T is in B. By the hypothesis that elements of E cost at most elements of B, c(x) ≤ c(y) for all such pairs. Since |E \ T| ≤ |B ∩ T|, the helper lemma applies directly to yield the sum inequality.
uses
Finset.mem_sdiff.mp,Finset.mem_inter.mp,block_insertion_residual_cost_bound_of_le_sum_le_sum_of_card_le_of_lehave hcost_le : ∀ x ∈ E \ T, ∀ y ∈ B ∩ T, c x ≤ c y := by intro x hx y hy have hx_mem : x ∈ E := Finset.mem_sdiff.mp hx |>.1 have hy_mem : y ∈ B := Finset.mem_inter.mp hy |>.1 exact h_cost x hx_mem y hy_mem have hsum_le : ∑ x ∈ E \ T, c x ≤ ∑ x ∈ B ∩ T, c x := block_insertion_residual_cost_bound_of_le_sum_le_sum_of_card_le_of_le c (E \ T) (B ∩ T) hcard_le hcost_le
The remaining cost over (B ∪ E) \ T is at most ∑ b ∈ B, c b, completing the proof.
Disjointness of B and E allows (B ∪ E) \ T to split into (B \ T) ∪ (E \ T), so its sum of costs is ∑ x ∈ B \ T, c(x) + ∑ x ∈ E \ T, c(x). Replacing the second sum by ∑ x ∈ B ∩ T, c(x) gives at most ∑ x ∈ B \ T, c(x) + ∑ x ∈ B ∩ T, c(x), which recombines into the total cost ∑ b ∈ B, c(b).
uses
Finset.union_sdiff_distrib,Finset.sum_union,Finset.sdiff_subset,Finset.sum_sdiff,Finset.sdiff_inter_self_lefthave hdec1 : ∑ x ∈ (B ∪ E) \ T, c x = (∑ x ∈ B \ T, c x) + ∑ x ∈ E \ T, c x := by rw [Finset.union_sdiff_distrib, Finset.sum_union] exact hdisj.mono Finset.sdiff_subset Finset.sdiff_subset have hdec2 : (∑ x ∈ B \ T, c x) + ∑ x ∈ B ∩ T, c x = ∑ x ∈ B, c x := by have := Finset.sum_sdiff (f := c) (s₁ := B ∩ T) (s₂ := B) Finset.inter_subset_left rw [Finset.sdiff_inter_self_left] at this exact this rw [hdec1, ← hdec2] gcongr
block_insertion_residual_cost_bound_of_le_sum_le_sum_of_card_le_of_le- If |s| ≤ |t| and every element of s has cost at most every element of t, then the sum of costs over s is at most the sum of costs over t.
ciSup_le'- If every element of an indexed family is at most a, then their supremum is at most a.
Finset.card_empty- The cardinality of the empty set is 0.
Finset.card_eq_zero.mp- If the cardinality of a finite set is 0, the set is empty.
Finset.card_le_card- If s ⊆ t, then |s| ≤ |t|.
Finset.card_sdiff_add_card_inter- For any finite sets s and t, |s \ t| + |s ∩ t| = |s|.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.inter_subset_left- The intersection s₁ ∩ s₂ is a subset of s₁.
Finset.le_max'- Every element of a nonempty finite linearly ordered set is at most the set's maximum element.
Finset.max'_mem- The maximum element of a nonempty finite linearly ordered set belongs to the set.
Finset.mem_image.mp- An element is in the image of a set under f if and only if it is the value of f at some element of the set.
Finset.mem_image_of_mem- The image of an element of s under f belongs to the image of s under f.
Finset.mem_inter- An element belongs to s₁ ∩ s₂ if and only if it belongs to s₁ and s₂.
Finset.mem_inter.mp- If an element belongs to s₁ ∩ s₂, then it belongs to s₁ (and to s₂).
Finset.mem_sdiff.mp- If an element belongs to s \ t, then it belongs to s (and not to t).
Finset.mem_union- An element belongs to s ∪ t if and only if it belongs to s or t.
Finset.nonempty_iff_ne_empty- A finite set is nonempty if and only if it is not equal to the empty set.
Finset.sdiff_subset- The set difference s \ t is a subset of s.
Finset.sdiff_inter_self_left- Subtracting s ∩ t from s is equal to subtracting t from s.
Finset.subset_union_left- A set is a subset of its union with another set.
Finset.sum_const- The sum of a constant b over a finite set s is |s| • b.
Finset.sum_le_sum- If f(i) ≤ g(i) for all i ∈ s, then the sum of f over s is at most the sum of g over s.
Finset.sum_sdiff- If s₁ ⊆ s₂, the sum over s₂ \ s₁ plus the sum over s₁ equals the sum over s₂.
Finset.sum_union- The sum over the union of two disjoint finite sets is the sum of the sums over each set.
Finset.union_sdiff_distrib- Set difference distributes over union: (s₁ ∪ s₂) \ t = (s₁ \ t) ∪ (s₂ \ t).
Nat.min_eq_left- If a ≤ b, then min(a, b) = a.
nsmul_eq_mul- Scalar multiplication by a natural number n in a semiring equals multiplication by n cast into the semiring.
Or.inl- A proposition a implies the disjunction a ∨ b.
Or.inr- A proposition b implies the disjunction a ∨ b.
- Linear arithmetic on Finset cardinalities is automated by `omega` in establishing |E \ T| ≤ |B ∩ T|.
- The final algebraic inequality is discharged by `gcongr` using the monotonicity of addition.
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.
lemma block_insertion_residual_cost_bound_of_le_sum_le_sum_of_card_le_of_le {α : Type*} [DecidableEq α] (c : α → NNReal) (s t : Finset α) (hcard : s.card ≤ t.card) (hle : ∀ x ∈ s, ∀ y ∈ t, c x ≤ c y) : ∑ x ∈ s, c x ≤ ∑ y ∈ t, c y := by rcases s.eq_empty_or_nonempty with rfl | hs · simp · have ht : t.Nonempty := by rw [Finset.nonempty_iff_ne_empty] rintro rfl rw [Finset.card_empty] at hcard have : s.card = 0 := by omega exact hs.ne_empty (Finset.card_eq_zero.mp this) have hsc : (s.image c).Nonempty := hs.image c obtain ⟨x₀, hx₀, hx₀m⟩ : ∃ x ∈ s, c x = (s.image c).max' hsc := by have hm_mem := Finset.max'_mem (s.image c) hsc rcases Finset.mem_image.mp hm_mem with ⟨x₀, hx₀, heq⟩ exact ⟨x₀, hx₀, heq⟩ have h1 : ∑ x ∈ s, c x ≤ (s.card : NNReal) * c x₀ := by have : ∑ x ∈ s, c x ≤ ∑ x ∈ s, c x₀ := by refine Finset.sum_le_sum ?_ intro x hx rw [hx₀m] exact Finset.le_max' (s.image c) (c x) (Finset.mem_image_of_mem c hx) rwa [Finset.sum_const, nsmul_eq_mul] at this have h2 : (t.card : NNReal) * c x₀ ≤ ∑ y ∈ t, c y := by have : ∑ y ∈ t, c x₀ ≤ ∑ y ∈ t, c y := by refine Finset.sum_le_sum ?_ intro y hy exact hle x₀ hx₀ y hy rwa [Finset.sum_const, nsmul_eq_mul] at this have h3 : (s.card : NNReal) * c x₀ ≤ (t.card : NNReal) * c x₀ := by gcongr exact h1.trans (h3.trans h2)/-- When |E| ≤ k, the k-chore residual cost of B ∪ E is at most c(B). -/theorem block_insertion_residual_cost_bound_of_le {α : Type*} [DecidableEq α] (c : α → NNReal) (k : ℕ) (B E : Finset α) (hdisj : Disjoint B E) (hkB : k ≤ B.card) (hrk : E.card ≤ k) (h_cost : ∀ e ∈ E, ∀ b ∈ B, c e ≤ c b) : chore_residual_cost c k (B ∪ E) ≤ ∑ b ∈ B, c b := by unfold chore_residual_cost refine ciSup_le' ?_ rintro ⟨T, hTsub, hTcard⟩ have hkBE : k ≤ (B ∪ E).card := hkB.trans (Finset.card_le_card Finset.subset_union_left) have hTcard' : T.card = k := by rw [Nat.min_eq_left hkBE] at hTcard exact hTcard have hT_decomp : T.card = (B ∩ T).card + (E ∩ T).card := by have hT : T = (B ∩ T) ∪ (E ∩ T) := by ext x simp only [Finset.mem_union, Finset.mem_inter] constructor · intro hx have := hTsub hx simp only [Finset.mem_union] at this rcases this with h | h · exact Or.inl ⟨h, hx⟩ · exact Or.inr ⟨h, hx⟩ · rintro (⟨-, hx⟩ | ⟨-, hx⟩) <;> exact hx have hd : Disjoint (B ∩ T) (E ∩ T) := hdisj.mono Finset.inter_subset_left Finset.inter_subset_left conv_lhs => rw [hT] rw [Finset.card_union_of_disjoint hd] have hE_decomp : (E \ T).card + (E ∩ T).card = E.card := Finset.card_sdiff_add_card_inter E T have hcard_le : (E \ T).card ≤ (B ∩ T).card := by omega have hcost_le : ∀ x ∈ E \ T, ∀ y ∈ B ∩ T, c x ≤ c y := by intro x hx y hy have hx_mem : x ∈ E := Finset.mem_sdiff.mp hx |>.1 have hy_mem : y ∈ B := Finset.mem_inter.mp hy |>.1 exact h_cost x hx_mem y hy_mem have hsum_le : ∑ x ∈ E \ T, c x ≤ ∑ x ∈ B ∩ T, c x := block_insertion_residual_cost_bound_of_le_sum_le_sum_of_card_le_of_le c (E \ T) (B ∩ T) hcard_le hcost_le have hdec1 : ∑ x ∈ (B ∪ E) \ T, c x = (∑ x ∈ B \ T, c x) + ∑ x ∈ E \ T, c x := by rw [Finset.union_sdiff_distrib, Finset.sum_union] exact hdisj.mono Finset.sdiff_subset Finset.sdiff_subset have hdec2 : (∑ x ∈ B \ T, c x) + ∑ x ∈ B ∩ T, c x = ∑ x ∈ B, c x := by have := Finset.sum_sdiff (f := c) (s₁ := B ∩ T) (s₂ := B) Finset.inter_subset_left rw [Finset.sdiff_inter_self_left] at this exact this rw [hdec1, ← hdec2] gcongr