AFTD Auto-Formalizing Theoretical Domains

sum_le_card_mul_of_subset_Icc

theoremverified

If A is a subset of {1, ..., N} and B is a subset of A, then the sum of the elements of B is at most the cardinality of A multiplied by N.

Statement

theorem sum_le_card_mul_of_subset_Icc (N : ℕ) (A : Finset ℕ) (hA : A ⊆ Finset.Icc 1 N)
    (B : Finset ℕ) (hB : B ⊆ A) : B.sum id ≤ A.card * N
Source
arXiv:2610.34372, Proof of Lemma 2.1
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1
  • admissible_card_sq_add_five_leIf A is a nonempty admissible subset of {1, ..., N}, then the square of the cardinality of A plus 5 is at most 6 times N.

Read back from the Lean

For any natural number $N$, any finite set of natural numbers $A \subseteq \{1, \dots, N\}$ (the closed interval from 1 to $N$), and any finite set of natural numbers $B \subseteq A$, the sum of the elements of $B$ is less than or equal to $|A| \cdot N$ (the cardinality of $A$ multiplied by $N$).

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 sum of the elements in $B$, we first observe that each element of $B$ is at most $N$ because $B \subseteq A \subseteq \{1, \dots, N\}$, which bounds the sum by $|B| \cdot N$. Since $B \subseteq A$, the cardinality of $B$ is at most that of $A$, and multiplying this inequality by $N$ yields the final bound $|A| \cdot N$.

  1. Every element of $B$ is at most $N$.

    Given any element $x \in B$, chaining the inclusions $B \subseteq A$ and $A \subseteq \{1, \dots, N\}$ shows that $x \in \{1, \dots, N\}$. By the definition of a closed discrete interval (`Finset.mem_Icc.mp`), this means $1 \le x$ and $x \le N$, providing the upper bound $x \le N$.

    line 4

    uses Finset.mem_Icc.mp

      have h1 : ∀ x ∈ B, id x ≤ N := fun x hx => (Finset.mem_Icc.mp (hA (hB hx))).2
  2. The sum of the elements in $B$ is at most $|A| \cdot N$.

    Since every element of $B$ is at most $N$, `Finset.sum_le_card_nsmul` bounds the sum of elements in $B$ by $|B| \cdot N$. Furthermore, because $B \subseteq A$, the cardinality of $B$ is at most that of $A$ (`Finset.card_le_card`), so multiplying by $N$ gives $|B| \cdot N \le |A| \cdot N$ (`Nat.mul_le_mul_right`). Chaining these two bounds by transitivity completes the proof.

    line 5

    uses Finset.sum_le_card_nsmul, Nat.mul_le_mul_right, Finset.card_le_card

      exact (Finset.sum_le_card_nsmul B id N h1).trans (Nat.mul_le_mul_right N (Finset.card_le_card hB))
Finset.mem_Icc.mp
an element $x$ belonging to a closed interval $[a, b]$ satisfies $a \le x$ and $x \le b$
Finset.sum_le_card_nsmul
if every element $x$ in a finite set $s$ satisfies $f(x) \le n$, then the sum of $f$ over $s$ is at most $|s| \cdot n$
Nat.mul_le_mul_right
for natural numbers, if $n \le m$, then $n \cdot k \le m \cdot k$
Finset.card_le_card
if a finite set $s$ is a subset of $t$, then $|s| \le |t|$

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

/-- Every subset sum of a subset of {1, ..., N} of size m is at most m * N. -/theorem sum_le_card_mul_of_subset_Icc (N : ℕ) (A : Finset ℕ) (hA : A ⊆ Finset.Icc 1 N)    (B : Finset ℕ) (hB : B ⊆ A) : B.sum id ≤ A.card * N := by  have h1 : ∀ x ∈ B, id x ≤ N := fun x hx => (Finset.mem_Icc.mp (hA (hB hx))).2  exact (Finset.sum_le_card_nsmul B id N h1).trans (Nat.mul_le_mul_right N (Finset.card_le_card hB))
See it in the graphDiscuss this resultChallenge it