Nat.nth_succ_gap
theoremverifiedformalizationimported Lean
There is a gap between two successive occurrences of a predicate p : ℕ → Prop, assuming p (as a set) is infinite.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Function Set in variable {f : ℕ → ℕ} in theorem Nat.nth_succ_gap {p : ℕ → Prop} (hf : (ofPred p).Infinite) (n : ℕ) : ∀ k < nth p (n + 1) - nth p n, k > 0 → ¬ p (k + nth p n)
- Formalizes
- CSLib, `Nat.nth_succ_gap`
- Lean proof
- By Ching-Tsun Chou, from github.com/leanprover/cslib at
3951377e5a3f(Copyright (c) 2025 Ching-Tsun Chou. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.33.0.Nat.nth_succ_gap← Nat.nth_succ_gap (Cslib/Foundations/Data/Nat/Segment.lean:48): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- Nat.strictMono_range_gapFor a strictly monotonic function
f : ℕ → ℕ, no number (strictly) betweenf mandf (m + 1)is in the range off.
- Nat.strictMono_range_gapFor a strictly monotonic function
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 autoImplicit true inset_option relaxedAutoImplicit true inopen Function Set invariable {f : ℕ → ℕ} in/-- There is a gap between two successive occurrences of a predicate `p : ℕ → Prop`, assuming `p` (as a set) is infinite. -/theorem Nat.nth_succ_gap {p : ℕ → Prop} (hf : (ofPred p).Infinite) (n : ℕ) : ∀ k < nth p (n + 1) - nth p n, k > 0 → ¬ p (k + nth p n) := by classical intro k h_k1 h_k0 h_p_k let m := count p (k + nth p n) have h_k_ex : nth p m = k + nth p n := by simp [m, nth_count h_p_k] have h_n_m : n < m := by apply (nth_lt_nth hf).mp; omega have h_m_n : m < n + 1 := by apply (nth_lt_nth hf).mp; omega omega