prioritized_borel_lex_profile_le_limit
Each member of a lexicographically nondecreasing binary profile sequence is at most its coordinatewise limit.
Statement
theorem prioritized_borel_lex_profile_le_limit (profiles : ℕ → ℕ → Bool) (limit : ℕ → Bool) (hmono : Monotone (fun n => toLex (profiles n))) (hlim : ∀ k, ∃ N, ∀ n ≥ N, ∀ i < k, profiles n i = limit i) : ∀ n, toLex (profiles n) ≤ toLex limit
- Source
- arXiv:2611.10136, Section 5.2.2; lexicographic priority profiles
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
- Used by 2
- prioritized_borel_finite_lex_limit_stabilizesA lexicographically nondecreasing sequence of binary profiles with a coordinatewise limit having finite support is eventually equal to…
- prioritized_borel_lex_strict_changes_infinite_limitIf a lexicographically nondecreasing sequence of binary profiles has strict increases arbitrarily late, its coordinatewise limit contains…
The proof, explained
The proof proceeds by contradiction: we fix an index n and assume that the limit sequence is lexicographically strictly smaller than the n-th profile sequence. By definition of the lexicographical order, the two sequences must first differ at some coordinate i, where the limit has a strictly smaller bit. By coordinatewise convergence, all profiles beyond some index N agree with the limit on all coordinates up to i. Choosing j = max(n, N), monotonicity implies that profile n is at most profile j, yet profile j matches the limit through index i and is therefore strictly smaller than profile n, a contradiction.
Suppose, for contradiction, that the limit is lexicographically strictly less than the n-th profile, and let i be the first coordinate where they differ.
To show that toLex (profiles n) ≤ toLex limit for an arbitrary index n, we proceed by contradiction using the linearity of the order (`le_of_not_gt`), assuming instead that toLex limit < toLex (profiles n) (hypothesis `hgt`). By definition of the strict lexicographical order (`Pi.Lex`), there exists a coordinate index i such that limit k = profiles n k for all k < i (hypothesis `hprev`), while limit i < profiles n i (hypothesis `hbit`).
uses
le_of_not_gt,Pi.Lexclassical intro n apply le_of_not_gt intro hgt change Pi.Lex (· < ·) (· < ·) limit (profiles n) at hgt obtain ⟨i, hprev, hbit⟩ := hgt
There is an index j ≥ n such that profile j agrees with the limit on all coordinates up to i, and toLex (profiles n) ≤ toLex (profiles j).
From the convergence hypothesis `hlim` applied at coordinate length i + 1, we obtain an index N such that for all j ≥ N, profiles j matches limit on all coordinates strictly less than i + 1. Setting j = max n N, we have n ≤ j by `le_max_left`. By the assumed monotonicity of the profile sequence (`hmono`), this implies toLex (profiles n) ≤ toLex (profiles j) (hypothesis `hcmp`).
uses
le_max_leftobtain ⟨N, hN⟩ := hlim (i+1) let j := max n N have hcmp := hmono (show n ≤ j from le_max_left _ _)
toLex (profiles j) < toLex (profiles n).
We show that profile j is lexicographically strictly smaller than profile n by using i as the witness in `Pi.Lex`. Since j ≥ N by `le_max_right`, the convergence property `hN` applies to j at all coordinates up to i. First, for every k < i, we have profiles j k = limit k, which equals profiles n k by `hprev`. Second, at coordinate i, profiles j i = limit i, which is strictly less than profiles n i by `hbit`. Hence, profile j matches profile n before index i and is strictly smaller at index i.
uses
Pi.Lex,le_max_righthave hlt : toLex (profiles j) < toLex (profiles n) := by change Pi.Lex (· < ·) (· < ·) (profiles j) (profiles n) refine ⟨i, ?_, ?_⟩ · intro k hk rw [hN j (le_max_right _ _) k (by omega)] exact hprev k hk · rw [hN j (le_max_right _ _) i (by omega)] exact hbit
Contradiction: toLex (profiles j) cannot be both at least and strictly less than toLex (profiles n).
From `hcmp`, toLex (profiles n) ≤ toLex (profiles j). By `not_lt_of_ge`, this implies that toLex (profiles j) < toLex (profiles n) cannot hold, which directly contradicts `hlt`.
uses
not_lt_of_geexact (not_lt_of_ge hcmp) hlt
le_of_not_gt- in a linear order, if b is not strictly less than a, then a ≤ b
Pi.Lex- the strict lexicographical relation on index-dependent functions, holding when two functions agree on all coordinates preceding the first index where the first function is strictly smaller
le_max_left- in a linear order, an element a is less than or equal to max(a, b)
le_max_right- in a linear order, an element b is less than or equal to max(a, b)
not_lt_of_ge- in a preorder, if a ≤ b, then b is not strictly less than a
- The integer inequalities k < i + 1 (given k < i) and i < i + 1 in lines 18 and 20 are proved automatically by the `omega` Presburger arithmetic 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_lex_profile_le_limit (profiles : ℕ → ℕ → Bool) (limit : ℕ → Bool) (hmono : Monotone (fun n => toLex (profiles n))) (hlim : ∀ k, ∃ N, ∀ n ≥ N, ∀ i < k, profiles n i = limit i) : ∀ n, toLex (profiles n) ≤ toLex limit := by classical intro n apply le_of_not_gt intro hgt change Pi.Lex (· < ·) (· < ·) limit (profiles n) at hgt obtain ⟨i, hprev, hbit⟩ := hgt obtain ⟨N, hN⟩ := hlim (i+1) let j := max n N have hcmp := hmono (show n ≤ j from le_max_left _ _) have hlt : toLex (profiles j) < toLex (profiles n) := by change Pi.Lex (· < ·) (· < ·) (profiles j) (profiles n) refine ⟨i, ?_, ?_⟩ · intro k hk rw [hN j (le_max_right _ _) k (by omega)] exact hprev k hk · rw [hN j (le_max_right _ _) i (by omega)] exact hbit exact (not_lt_of_ge hcmp) hlt