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.Nat.strictMono_range_gap← Nat.strictMono_range_gap (Cslib/Foundations/Data/Nat/Segment.lean:80): verbatim
- 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, assumingp(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 nis exactly the n-th element of the range off.
- Nat.nth_succ_gapThere is a gap between two successive occurrences of a predicate
- Used by 1
- Nat.segment_range_valFor a strictly monotonic function
f : ℕ → ℕ, allksatisfyingf m ≤ k < f (m + 1)hassegment f k = m.
- Nat.segment_range_valFor 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/-- 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