AFTD Auto-Formalizing Theoretical Domains

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.
Verified
08 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1
  • Nat.strictMono_range_gapFor a strictly monotonic function f : ℕ → ℕ, no number (strictly) between f m and f (m + 1) is in the range of f.

Lean source view module on GitHub

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
See it in the graphDiscuss this resultChallenge it