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.CommunicationComplexity.Internal.card_nat_in_Ico← CommunicationComplexity.Internal.card_nat_in_Ico (TCSlib/CommunicationComplexity/NewmanTheorem/PrivateCoinApproximation.lean:177): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- CommunicationComplexity.Internal.uniformApprox_approxUniform approximation error bound. Let $p$ be a probability mass function on $\mathrm{Fin}\,m$ with $m \ge 1$, and let $n \ge 1$ be an…
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.
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