AFTD Auto-Formalizing Theoretical Domains

bool_sum_eq_card_filter

theoremverified

A Boolean profile summed through toNat over a natural range counts exactly its true offsets in that range.

Statement

theorem bool_sum_eq_card_filter (N : ℕ) (b : ℕ → Bool) :
    (range N).sum (fun a => (b a).toNat) = ((range N).filter (fun a => b a = true)).card
Source
Uniform full-root-gap and current-scale fullness reduction for OP-205 / RT-1 following arXiv:2610.15635. The reusable finite ordered-cover classification formalizes the deficiency-one structure described in arXiv:1103.3693 Corollary 2.5.6. Explicit full-class or middle-fullness hypotheses remain structural assumptions where used; optimal original counts have not been shown to imply them. No graph covering value or research advance is claimed.
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 3

The proof, explained

The cardinality of the subset of indices where $b(a) = \mathrm{true}$ is expressed as a sum of 1s, which is then rewritten as a sum of indicator values (1 if true, 0 if false) over the entire range. Congruence of sums reduces the equality to showing pointwise that $(b(a)).\mathrm{toNat}$ equals this indicator value for each index $a$. Finally, a case analysis on whether $b(a)$ is true or false confirms that both sides evaluate to 1 or 0 respectively.

  1. The goal is transformed into showing that $\sum_{a \in \mathrm{range}(N)} (b(a)).\mathrm{toNat} = \sum_{a \in \mathrm{range}(N)} (\text{if } b(a) = \mathrm{true} \text{ then } 1 \text{ else } 0)$.

    By `card_eq_sum_ones`, the cardinality of the filtered range is rewritten as the sum of 1 over the elements where $b(a) = \mathrm{true}$. Then, by `sum_filter`, this sum over the filtered subset is rewritten as a sum over the entire range $\mathrm{range}(N)$ with a conditional term returning 1 when $b(a) = \mathrm{true}$ and 0 otherwise.

    line 7

    uses card_eq_sum_ones, sum_filter

      rw [card_eq_sum_ones, sum_filter]
  2. It suffices to show that for every $a \in \mathrm{range}(N)$, $(b(a)).\mathrm{toNat} = (\text{if } b(a) = \mathrm{true} \text{ then } 1 \text{ else } 0)$.

    Applying `sum_congr` with identical index sets (by reflexivity) reduces the equality of the two sums over $\mathrm{range}(N)$ to the pointwise equality of their summands for an arbitrary element $a \in \mathrm{range}(N)$.

    lines 8–9

    uses sum_congr

      apply sum_congr rfl
      intro a ha
  3. Pointwise equality holds for every index $a$: $(b(a)).\mathrm{toNat} = (\text{if } b(a) = \mathrm{true} \text{ then } 1 \text{ else } 0)$.

    Case split on the Boolean value $b(a)$. If $b(a) = \mathrm{false}$, then $\mathrm{false}.\mathrm{toNat} = 0$ and the conditional evaluates to $0$. If $b(a) = \mathrm{true}$, then $\mathrm{true}.\mathrm{toNat} = 1$ and the conditional evaluates to $1$. In both cases, the two sides are definitionally equal.

    line 10

      cases b a <;> rfl
card_eq_sum_ones
The cardinality of a finite set equals the sum of 1 over all its elements.
sum_filter
Summing a function over a filtered subset is equivalent to summing an indicator (if-then-else) function over the whole set.
sum_congr
Two sums over the same finite set are equal if their terms agree on every element of the set.

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

open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem bool_sum_eq_card_filter (N : ℕ) (b : ℕ → Bool) :    (range N).sum (fun a => (b a).toNat) = ((range N).filter (fun a => b a = true)).card := by  rw [card_eq_sum_ones, sum_filter]  apply sum_congr rfl  intro a ha  cases b a <;> rfl
See it in the graphDiscuss this resultChallenge it