bool_sum_eq_card_filter
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
- simple_graph_cycle_power_dyadic_class_model_vertex_layersFor an optimal (m+1)-layer dyadic cover, with ell(p) the unique layer covering the endpoint pair (p, p+2^m-1) and the class of p cut to…
- cycle_power_gap_sides_cardIf r is below g, g is at most D, and every selected offset of a radius-D profile is localized below absolute vertex g or at least D, its…
- cycle_power_gap_sides_pair_cardFor a profile rooted below g at most D, whose selected distance D-R pairs cross the two blocks, its pair count equals the number of…
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.
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.
uses
card_eq_sum_ones,sum_filterrw [card_eq_sum_ones, sum_filter]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)$.
uses
sum_congrapply sum_congr rfl intro a ha
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.
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
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.
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