AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.Internal.card_nat_in_Ico

theoremverifiedimported Lean

Counting bound in a real interval. Fix $n \in \bbn$ and real numbers $a \le b$. Among the integers $j \in \{0, 1, \dots, n-1\}$, the number of those satisfying $a \le j < b$ is at most $b - a + 1$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open MeasureTheory in
open scoped ENNReal in
lemma CommunicationComplexity.Internal.card_nat_in_Ico (n : ℕ) (a b : ℝ) (hab : a ≤ b) :
    ((Finset.univ.filter (fun j : Fin n =>
      a ≤ (j : ℝ) ∧ (j : ℝ) < b)).card : ℝ) ≤ b - a + 1
Source
TCSlib, `CommunicationComplexity.Internal.card_nat_in_Ico`
Lean proof
By Lucy Horowitz, Timothe Kasriel, Mihir Singhal, from github.com/Shilun-Allan-Li/tcslib at c8a02591b1e5 (Copyright (c) 2026 Lucy Horowitz, Timothe Kasriel, and Mihir Singhal. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false inopen MeasureTheory inopen scoped ENNReal in/-- The number of naturals `j < n` in the real interval `[a, b)` is at most `b − a + 1`. **Proof sketch.** If the set is empty there is nothing to prove. Otherwise let `jlo` and `jhi` be its minimum and maximum; the set injects (via `Fin.val`) into the integer interval `[jlo, jhi]`, which has `jhi − jlo + 1` elements, and `a ≤ jlo`, `jhi < b`. -/lemma CommunicationComplexity.Internal.card_nat_in_Ico (n : ℕ) (a b : ℝ) (hab : a ≤ b) :    ((Finset.univ.filter (fun j : Fin n =>      a ≤ (j : ℝ) ∧ (j : ℝ) < b)).card : ℝ) ≤ b - a + 1 := by  by_cases hS : (Finset.univ.filter (fun j : Fin n =>      a ≤ (j : ℝ) ∧ (j : ℝ) < b)).card = 0  · simp [hS]; linarith  set S := Finset.univ.filter (fun j : Fin n => a ≤ (j : ℝ) ∧ (j : ℝ) < b)  have hne : S.Nonempty := Finset.card_pos.mp (Nat.pos_of_ne_zero hS)  set jlo := (S.min' hne : ℕ)  set jhi := (S.max' hne : ℕ)  have hlo_mem := Finset.min'_mem S hne  have hhi_mem := Finset.max'_mem S hne  have hlo_ge : a ≤ jlo := ((Finset.mem_filter.mp hlo_mem).2).1  have hhi_lt : (jhi : ℝ) < b := ((Finset.mem_filter.mp hhi_mem).2).2  have hle : jlo ≤ jhi := (Finset.min'_le S _ hhi_mem)  -- S maps injectively (via Fin.val) into Finset.Icc jlo jhi in ℕ  have hcard_le : S.card ≤ jhi - jlo + 1 := by    calc S.card        = (Finset.image Fin.val S).card :=          (Finset.card_image_of_injective _ Fin.val_injective).symm      _ ≤ (Finset.Icc jlo jhi).card := by          apply Finset.card_le_card          intro k hk          obtain ⟨j, hj, rfl⟩ := Finset.mem_image.mp hk          exact Finset.mem_Icc.mpr ⟨Finset.min'_le _ _ hj, Finset.le_max' _ _ hj⟩      _ = jhi - jlo + 1 := by simp; omega  calc (S.card : ℝ) ≤ (jhi - jlo + 1 : ℕ) := by exact_mod_cast hcard_le    _ = (jhi : ℝ) - (jlo : ℝ) + 1 := by        rw [Nat.cast_add, Nat.cast_sub hle]; simp    _ ≤ b - a + 1 := by linarith
See it in the graphDiscuss this resultChallenge it