AFTD Auto-Formalizing Theoretical Domains

chore_residual_cost_of_card_le

theoremverifiedformalization

Given a type α with decidable equality, a cost function c : α → NNReal, a natural number k : ℕ, and a bundle S : Finset α with S.card ≤ k, the k-chore residual cost chore_residual_cost c k S is 0.

Statement

theorem chore_residual_cost_of_card_le {α : Type*} [DecidableEq α]
    (c : α → NNReal) (k : ℕ) (S : Finset α) (h : S.card ≤ k) :
    chore_residual_cost c k S = 0
Formalizes
arXiv:2611.07468 Def. 2.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 : ℕ,…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…

Read back from the Lean

For any type α with decidable equality, any function c : α → ℝ≥0 (assigning a non-negative real cost to each element of α), any natural number k, and any finite subset S of α, if the cardinality of S is less than or equal to k (S.card ≤ k), then chore_residual_cost c k S = 0.

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, the k-chore residual cost of S is the supremum of ∑ x ∈ S \ T, c x over all subsets T ⊆ S of cardinality min(k, |S|). Because |S| ≤ k, the only candidate subset T is all of S, meaning that the remaining bundle S \ T is empty. Hence every term in the supremum is 0, and since values are non-negative, the supremum itself is 0.

  1. The goal is to show that the supremum ⨆ T, ∑ x ∈ S \ T, c x is equal to 0, where T ranges over subsets of S of size min(k, |S|).

    Unfolding the definition of chore_residual_cost expresses the residual cost as the supremum of chore costs remaining outside T across all subsets T ⊆ S of cardinality min(k, |S|).

    line 5

      unfold chore_residual_cost
  2. For every subset T ⊆ S of size min(k, |S|), the residual sum ∑ x ∈ S \ T, c x is 0.

    Given any candidate subset T, the hypothesis |S| ≤ k implies min(k, |S|) = |S| by Nat.min_eq_right, so |T| = |S|. Since T ⊆ S and |S| ≤ |T| (via le_of_eq), Finset.eq_of_subset_of_card_le implies T = S. Substituting T = S makes the difference S \ T empty, so the sum over it simplifies to 0.

    lines 6–12

    uses Nat.min_eq_right, Finset.eq_of_subset_of_card_le, le_of_eq

      have hone : ∀ T : {T : Finset α // T ⊆ S ∧ T.card = min k S.card},
          ∑ x ∈ S \ T.val, c x = 0 := by
        intro T
        have hcard : T.val.card = S.card := by
          rw [T.2.2, Nat.min_eq_right h]
        have hTS : T.val = S := Finset.eq_of_subset_of_card_le T.2.1 (le_of_eq hcard.symm)
        simp [hTS]
  3. The supremum over all such T is 0.

    By antisymmetry (le_antisymm), since costs in NNReal are always at least 0 (zero_le), it suffices to show that the supremum is at most 0. By ciSup_le', this reduces to showing that each term in the family is at most 0. Rewriting with the previous step (hone) turns each term into 0, leaving 0 ≤ 0, which holds reflexively.

    lines 13–15

    uses le_antisymm, ciSup_le', zero_le

      refine le_antisymm (ciSup_le' ?_) zero_le
      intro T
      rw [hone T]
Nat.min_eq_right
For natural numbers a and b, if b ≤ a, then min a b = b.
Finset.eq_of_subset_of_card_le
If a finite set s is a subset of t and the cardinality of t is at most that of s, then s = t.
le_of_eq
If a = b in a preorder, then a ≤ b.
le_antisymm
In a partial order, if a ≤ b and b ≤ a, then a = b.
ciSup_le'
In a conditionally complete linear order with a bottom element, the supremum ⨆ i, f i is at most a if f i ≤ a for all i.
zero_le
In an ordered structure with bottom element 0, 0 ≤ a holds for every a.

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

/-- If a bundle S contains at most k chores, its k-chore residual cost is 0. -/theorem chore_residual_cost_of_card_le {α : Type*} [DecidableEq α]    (c : α → NNReal) (k : ℕ) (S : Finset α) (h : S.card ≤ k) :    chore_residual_cost c k S = 0 := by  unfold chore_residual_cost  have hone : ∀ T : {T : Finset α // T ⊆ S ∧ T.card = min k S.card},      ∑ x ∈ S \ T.val, c x = 0 := by    intro T    have hcard : T.val.card = S.card := by      rw [T.2.2, Nat.min_eq_right h]    have hTS : T.val = S := Finset.eq_of_subset_of_card_le T.2.1 (le_of_eq hcard.symm)    simp [hTS]  refine le_antisymm (ciSup_le' ?_) zero_le  intro T  rw [hone T]
See it in the graphDiscuss this resultChallenge it