AFTD Auto-Formalizing Theoretical Domains

Nat.segment_range_val

theoremverifiedformalizationimported Lean

For a strictly monotonic function f : ℕ → ℕ, all k satisfying f m ≤ k < f (m + 1) has segment f k = m.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Function Set in
variable {f : ℕ → ℕ} in
theorem Nat.segment_range_val (hm : StrictMono f) {m k : ℕ}
    (hl : f m ≤ k) (hu : k < f (m + 1)) : segment f k = m
Formalizes
CSLib, `Nat.segment_range_val`
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 5
  • Nat.strictMono_infiniteAny strictly monotonic function f : ℕ → ℕ has an infinite range.
  • Nat.segmentThe f-segment of k, where f : ℕ → ℕ will be assumed to be at least StrictMono.
  • Nat.nth_of_strictMonoFor a strictly monotonic function f : ℕ → ℕ, f n is exactly the n-th element of the range of f.
  • 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.
  • Nat.segment_idemFor a strictly monotonic function f : ℕ → ℕ, the segment of f k is k.

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 : ℕ → ℕ`, all `k` satisfying `f m ≤ k < f (m + 1)` has `segment f k = m`. -/theorem Nat.segment_range_val (hm : StrictMono f) {m k : ℕ}    (hl : f m ≤ k) (hu : k < f (m + 1)) : segment f k = m := by  classical  obtain (rfl | hu') := show f m = k ∨ f m < k by omega  · exact segment_idem hm m  · obtain ⟨j, h_j, rfl⟩ : ∃ j < f (m + 1) - f m - 1, k = j + f m + 1 := ⟨k - f m - 1, by omega⟩    induction j    case zero =>      #adaptation_note      /-- A grind regression found moving to nightly-2026-03-31 (changes from lean#13166) -/      have := strictMono_range_gap hm (show f m < f m + 1 by grind)      have : count (· ∈ range f) (f m + 1 + 1) = count (· ∈ range f) (f m + 1) := by grind      have := nth_of_strictMono hm m      have := count_succ (· ∈ range f)      simp_all only [segment, mem_range]      split      · grind [count_nth_of_infinite (strictMono_infinite hm) m]      · grind    case succ j _ =>      have := strictMono_range_gap hm (show f m < j + 1 + f m     by grind)      have := strictMono_range_gap hm (show f m < j + 1 + f m + 1 by grind)      grind
See it in the graphDiscuss this resultChallenge it