prioritized_borel_eventually_antitone_rank_stabilizes
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.
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.
let f : ℕ → ℕ := fun n => r (N+n)
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).
uses
antitone_nat_of_succ_le,Nat.add_assochave 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
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.
uses
WellFoundedLT.antitone_chain_conditionobtain ⟨K, hK⟩ := WellFoundedLT.antitone_chain_condition hmonoThe 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).
uses
Nat.add_sub_of_lerefine ⟨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.
- Linear inequalities on natural numbers ($N + n \ge N$, $N \le n$, and $K \le n - N$) are discharged automatically by the linear arithmetic tactic omega.
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
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.
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