AFTD Auto-Formalizing Theoretical Domains

Nat.strictMono_range_gap

theoremverifiedformalizationimported Lean

For a strictly monotonic function f : ℕ → ℕ, no number (strictly) between f m and f (m + 1) is in the range of f.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Function Set in
variable {f : ℕ → ℕ} in
theorem Nat.strictMono_range_gap (hm : StrictMono f) {m k : ℕ}
    (hl : f m < k) (hu : k < f (m + 1)) : k ∉ range f
Formalizes
CSLib, `Nat.strictMono_range_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
Built on 3
  • Nat.nth_succ_gapThere is a gap between two successive occurrences of a predicate p : ℕ → Prop, assuming p (as a set) is infinite.
  • Nat.strictMono_infiniteAny strictly monotonic function f : ℕ → ℕ has an infinite range.
  • Nat.nth_of_strictMonoFor a strictly monotonic function f : ℕ → ℕ, f n is exactly the n-th element of the range of f.
Used by 1
  • Nat.segment_range_valFor a strictly monotonic function f : ℕ → ℕ, all k satisfying f m ≤ k < f (m + 1) has segment f k = m.

Lean source view module on GitHub

set_option autoImplicit true inset_option relaxedAutoImplicit true inopen Function Set invariable {f : ℕ → ℕ} in/-- For a strictly monotonic function `f : ℕ → ℕ`, no number (strictly) between `f m` and ` f (m + 1)` is in the range of `f`. -/theorem Nat.strictMono_range_gap (hm : StrictMono f) {m k : ℕ}    (hl : f m < k) (hu : k < f (m + 1)) : k ∉ range f := by  rw [nth_of_strictMono hm m] at hl  rw [nth_of_strictMono hm (m + 1)] at hu  have h_inf := strictMono_infinite hm  have h_gap := nth_succ_gap (p := (· ∈ range f)) h_inf m    (k - nth (· ∈ range f) m) (by omega) (by omega)  rw [(show k - nth (· ∈ range f) m + nth (· ∈ range f) m = k by omega)] at h_gap  exact h_gap
See it in the graphDiscuss this resultChallenge it