prioritized_borel_finite_lex_limit_stabilizes
A lexicographically nondecreasing sequence of binary profiles with a coordinatewise limit having finite support is eventually equal to that limit.
Statement
theorem prioritized_borel_finite_lex_limit_stabilizes (profiles : ℕ → ℕ → Bool) (limit : ℕ → Bool) (hmono : Monotone (fun n => toLex (profiles n))) (hlim : ∀ k, ∃ N, ∀ n ≥ N, ∀ i < k, profiles n i = limit i) (K : ℕ) (hzero : ∀ i ≥ K, limit i = false) : ∃ N, ∀ n ≥ N, profiles n = limit
- Source
- Filed by the prover as a step towards another result
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- prioritized_borel_lex_profile_le_limitEach member of a lexicographically nondecreasing binary profile sequence is at most its coordinatewise limit.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
The proof, explained
We choose an index N such that all profiles from N onward agree with the limit on the first K coordinates. For any n ≥ N, monotonicity ensures that the n-th profile is lexicographically at most the limit. If a profile were not equal to the limit, there would be a first coordinate i where profiles n i < limit i. But i < K contradicts agreement on the initial segment, while i ≥ K contradicts the hypothesis that the limit is identically false from index K onward.
There exists an index N such that for all n ≥ N, the profile agrees with the limit on all coordinates below K.
By the coordinatewise convergence hypothesis `hlim` applied to K, there exists an index N from which all profiles agree with the limit on coordinates i < K. We instantiate the existential quantifier with this N.
classical obtain ⟨N, hN⟩ := hlim K refine ⟨N, ?_⟩
For any n ≥ N, assuming profiles n ≠ limit yields a coordinate i where profiles n i < limit i.
Fix n ≥ N. By the helper theorem `prioritized_borel_lex_profile_le_limit`, profiles n is lexicographically at most the limit. Assuming for contradiction that profiles n ≠ limit, this weak inequality strengthens to a strict lexicographic inequality by `lt_of_le_of_ne`. Unfolding the definition of lexicographic order on functions (`Pi.Lex`) provides a first index i where the two functions differ, satisfying profiles n i < limit i.
uses
prioritized_borel_lex_profile_le_limit,lt_of_le_of_neintro n hn have hle := prioritized_borel_lex_profile_le_limit profiles limit hmono hlim n by_contra hne have hne' : toLex (profiles n) ≠ toLex limit := by simpa using hne have hlt : toLex (profiles n) < toLex limit := lt_of_le_of_ne hle hne' change Pi.Lex (· < ·) (· < ·) (profiles n) limit at hlt obtain ⟨i, _, hbit⟩ := hlt
The first differing index i cannot satisfy i < K.
If i < K, the definition of N ensures that profiles n i = limit i. Substituting this equality into profiles n i < limit i yields limit i < limit i, contradicting the irreflexivity of strict inequality (`lt_irrefl`).
uses
lt_irreflby_cases hi : i < K · have heq := hN n hn i hi rw [heq] at hbit exact (lt_irrefl _ hbit)
The first differing index i cannot satisfy i ≥ K either, completing the contradiction.
If i ≥ K, the finite support hypothesis `hzero` implies limit i = false. Substituting this gives profiles n i < false. Since false is the least boolean value (`Bool.false_le`), no boolean can be strictly smaller than false (`not_lt_of_ge`). Since both cases lead to contradiction, profiles n = limit.
uses
Bool.false_le,not_lt_of_ge· have heq := hzero i (by omega) rw [heq] at hbit exact (not_lt_of_ge (Bool.false_le (profiles n i))) hbit
Bool.false_le- In the boolean ordering, false ≤ x for every boolean value x.
lt_irrefl- In a preorder, strict inequality is irreflexive: no element is strictly less than itself.
lt_of_le_of_ne- In a partial order, if a ≤ b and a ≠ b, then a < b.
not_lt_of_ge- In a preorder, if a ≤ b, then b is not strictly less than a.
prioritized_borel_lex_profile_le_limit- A lexicographically monotone sequence of binary profiles that converges coordinatewise is bounded above lexicographically by its coordinatewise limit.
- The strict lexicographic inequality is unfolded definitionally at line 14 to `Pi.Lex`, which directly yields the existence of the first differing coordinate.
- The arithmetic inequality $i \ge K$ from $\neg (i < K)$ in line 20 is discharged by the `omega` automation tactic.
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_finite_lex_limit_stabilizes (profiles : ℕ → ℕ → Bool) (limit : ℕ → Bool) (hmono : Monotone (fun n => toLex (profiles n))) (hlim : ∀ k, ∃ N, ∀ n ≥ N, ∀ i < k, profiles n i = limit i) (K : ℕ) (hzero : ∀ i ≥ K, limit i = false) : ∃ N, ∀ n ≥ N, profiles n = limit := by classical obtain ⟨N, hN⟩ := hlim K refine ⟨N, ?_⟩ intro n hn have hle := prioritized_borel_lex_profile_le_limit profiles limit hmono hlim n by_contra hne have hne' : toLex (profiles n) ≠ toLex limit := by simpa using hne have hlt : toLex (profiles n) < toLex limit := lt_of_le_of_ne hle hne' change Pi.Lex (· < ·) (· < ·) (profiles n) limit at hlt obtain ⟨i, _, hbit⟩ := hlt by_cases hi : i < K · have heq := hN n hn i hi rw [heq] at hbit exact (lt_irrefl _ hbit) · have heq := hzero i (by omega) rw [heq] at hbit exact (not_lt_of_ge (Bool.false_le (profiles n i))) hbit