AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_eventually_antitone_rank_stabilizes

theoremverified

An eventually nonincreasing sequence of natural-number ranks eventually stabilizes.

Statement

theorem prioritized_borel_eventually_antitone_rank_stabilizes (r : ℕ → ℕ) (N : ℕ)
    (hstep : ∀ n ≥ N, r (n+1) ≤ r n) :
    ∃ K ≥ N, ∀ n ≥ K, r n = r K
Source
Filed by the prover as a step towards another result
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

To show that the eventually nonincreasing sequence r stabilizes, we shift it by N to define a sequence f(n) = r(N + n) that is nonincreasing on all of ℕ. Since the natural numbers are well-founded under <, any nonincreasing sequence of natural numbers eventually stabilizes (the descending chain condition), yielding an index K where f becomes constant. Shifting back, r is constant for all n ≥ N + K.

  1. Define the shifted sequence f : ℕ → ℕ by f(n) = r(N + n).

    Shifting indices by N re-indexes the sequence so that the nonincreasing behavior holds starting at 0.

    line 4

      let f : ℕ → ℕ := fun n => r (N+n)
  2. The shifted sequence f is antitone (nonincreasing).

    By antitone_nat_of_succ_le, it suffices to show that f(n+1) ≤ f(n) for all n. Since N + n ≥ N, the hypothesis hstep gives r((N+n)+1) ≤ r(N+n). Reassociating the addition with Nat.add_assoc shows that r(N + (n + 1)) ≤ r(N + n), which is f(n+1) ≤ f(n).

    lines 5–9

    uses antitone_nat_of_succ_le, Nat.add_assoc

      have hmono : Antitone f := by
        apply antitone_nat_of_succ_le
        intro n
        have h := hstep (N+n) (by omega)
        simpa [f, Nat.add_assoc] using h
  3. There exists an index K such that f(m) = f(K) for all m ≥ K.

    Because the strict order on ℕ is well-founded, every antitone sequence in ℕ satisfies the descending chain condition and eventually stabilizes, as stated by WellFoundedLT.antitone_chain_condition.

    line 10

    uses WellFoundedLT.antitone_chain_condition

      obtain ⟨K, hK⟩ := WellFoundedLT.antitone_chain_condition hmono
  4. The original sequence r stabilizes at N + K: N + K ≥ N, and r(n) = r(N + K) for all n ≥ N + K.

    We choose N + K as the stabilization witness; clearly N + K ≥ N. For any n ≥ N + K, we have N ≤ n and K ≤ n - N. Applying the stabilization of f to m = n - N gives f(K) = f(n - N), which unfolds to r(N + K) = r(N + (n - N)). Using Nat.add_sub_of_le, N + (n - N) simplifies to n, so r(n) = r(N + K).

    lines 11–17

    uses Nat.add_sub_of_le

      refine ⟨N+K, by omega, ?_⟩
      intro n hn
      have hstart : N ≤ n := by omega
      have hi : K ≤ n-N := by omega
      have h := hK (n-N) hi
      change r (N+K) = r (N+(n-N)) at h
      simpa [Nat.add_sub_of_le hstart] using h.symm
antitone_nat_of_succ_le
A sequence on ℕ into a preorder is antitone (nonincreasing) if each step is nonincreasing: f(n+1) ≤ f(n) for all n.
Nat.add_assoc
Addition of natural numbers is associative: (n + m) + k = n + (m + k).
WellFoundedLT.antitone_chain_condition
Any antitone sequence into a well-founded partial order eventually stabilizes: there exists an index n such that f(n) = f(m) for all m ≥ n.
Nat.add_sub_of_le
For natural numbers a and b with a ≤ b, a + (b - a) = b.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem prioritized_borel_eventually_antitone_rank_stabilizes (r : ℕ → ℕ) (N : ℕ)    (hstep : ∀ n ≥ N, r (n+1) ≤ r n) :    ∃ K ≥ N, ∀ n ≥ K, r n = r K := by  let f : ℕ → ℕ := fun n => r (N+n)  have hmono : Antitone f := by    apply antitone_nat_of_succ_le    intro n    have h := hstep (N+n) (by omega)    simpa [f, Nat.add_assoc] using h  obtain ⟨K, hK⟩ := WellFoundedLT.antitone_chain_condition hmono  refine ⟨N+K, by omega, ?_⟩  intro n hn  have hstart : N ≤ n := by omega  have hi : K ≤ n-N := by omega  have h := hK (n-N) hi  change r (N+K) = r (N+(n-N)) at h  simpa [Nat.add_sub_of_le hstart] using h.symm
See it in the graphDiscuss this resultChallenge it