AFTD Auto-Formalizing Theoretical Domains

block_insertion_residual_cost_bound_of_le

theoremverified

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
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.

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

    lines 7–8

      rcases s.eq_empty_or_nonempty with rfl | hs
      · simp
  2. 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.

    lines 9–19

    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⟩
  3. 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.

    lines 20–35

    uses Finset.sum_le_sum, Finset.le_max', Finset.mem_image_of_mem, Finset.sum_const, nsmul_eq_mul

        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)
  4. 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.

    lines 43–49

    uses ciSup_le', Finset.card_le_card, Finset.subset_union_left, Nat.min_eq_left

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

    lines 50–69

    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_inter

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

    lines 70–76

    uses Finset.mem_sdiff.mp, Finset.mem_inter.mp, block_insertion_residual_cost_bound_of_le_sum_le_sum_of_card_le_of_le

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

    lines 77–85

    uses Finset.union_sdiff_distrib, Finset.sum_union, Finset.sdiff_subset, Finset.sum_sdiff, Finset.sdiff_inter_self_left

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

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

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