prioritized_borel_lex_strict_changes_infinite_limit
If a lexicographically nondecreasing sequence of binary profiles has strict increases arbitrarily late, its coordinatewise limit contains true entries arbitrarily late.
Statement
theorem prioritized_borel_lex_strict_changes_infinite_limit (profiles : ℕ → ℕ → Bool) (limit : ℕ → Bool) (hmono : Monotone (fun n => toLex (profiles n))) (hlim : ∀ k, ∃ N, ∀ n ≥ N, ∀ i < k, profiles n i = limit i) (hstrict : ∀ N, ∃ n ≥ N, toLex (profiles n) < toLex (profiles (n+1))) : ∀ K, ∃ i ≥ K, limit i = true
- Source
- arXiv:2611.10136, Section 5.2.2; lexicographic priority profiles
- 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 argue by contradiction: suppose that beyond some coordinate K, the limit profile is identically false. By coordinatewise convergence, the profiles must eventually agree with the limit on all coordinates before K. Combined with the fact that each profile is lexicographically bounded above by the limit, this forces every profile to equal the limit from that stage onward. This eventual constancy contradicts the hypothesis that strict lexicographic increases occur arbitrarily late in the sequence.
Assume, for contradiction, that no index at or beyond K has limit value true.
We introduce an arbitrary coordinate bound K and suppose the contrary: that for every index i ≥ K, the limit value is not true.
classical intro K by_contra h push_neg at h
For all coordinates i ≥ K, the limit is identically false.
Because Boolean values are either true or false, the assumption that limit i ≠ true for all i ≥ K forces limit i = false for every such coordinate.
have hzero : ∀ i ≥ K, limit i = false := by intro i hi have := h i hi cases hbit : limit i <;> simp_all
There exists a stage N after which all profiles agree with the limit on every index strictly less than K.
By coordinatewise convergence (hlim) applied at K, there is an index N such that profiles n i = limit i for all n ≥ N and all i < K.
obtain ⟨N, hN⟩ := hlim KIf a profile at or after stage N differs from the limit, there is a first coordinate where it is strictly smaller than the limit.
We claim profiles n = limit for all n ≥ N. If not, since profiles n ≤ limit holds lexicographically by prioritized_borel_lex_profile_le_limit, the inequality is strict by lt_of_le_of_ne. Expanding the definition of the lexicographical order (Pi.Lex) provides a minimal index i at which profiles n i < limit i.
uses
prioritized_borel_lex_profile_le_limit,lt_of_le_of_ne,Pi.Lexhave heq : ∀ n ≥ N, profiles n = limit := by 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
The first differing coordinate i cannot be strictly less than K.
If i < K, then profiles n i = limit i by the choice of N. Substituting this 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 hh := hN n hn i hi rw [hh] at hbit exact (lt_irrefl _ hbit)
The first differing coordinate i cannot be at or beyond K, concluding that all profiles from stage N onward equal the limit.
If i ≥ K, then limit i = false. But false is the minimum Boolean element (Bool.false_le), so no value can be strictly less than false (not_lt_of_ge), contradicting profiles n i < false. Since neither i < K nor i ≥ K is possible, profiles n = limit for all n ≥ N.
uses
Bool.false_le,not_lt_of_ge· have hh := hzero i (by omega) rw [hh] at hbit exact (not_lt_of_ge (Bool.false_le (profiles n i))) hbit
A contradiction is reached, completing the proof.
By the strict changes hypothesis (hstrict), there is some n ≥ N where profiles n < profiles (n + 1) in lexicographic order. Since both n and n + 1 are at least N, both profiles equal the limit, giving limit < limit, which contradicts the irreflexivity of strict inequality (lt_irrefl).
uses
lt_irreflobtain ⟨n, hn, hlt⟩ := hstrict N rw [heq n hn, heq (n+1) (by omega)] at hlt exact (lt_irrefl _ hlt)
Bool.false_le- The Boolean value false is less than or equal to any Boolean value x.
not_lt_of_ge- In a preorder, if a ≤ b then it is not the case that b < a.
lt_irrefl- Strict inequality is irreflexive: for any element a in a preorder, it is not the case that a < a.
lt_of_le_of_ne- In a partial order, if a ≤ b and a ≠ b, then a < b.
Pi.Lex- The lexicographical order relation on function types: f < g if at the minimal index where they differ, the value of f is strictly less than the value of g.
prioritized_borel_lex_profile_le_limit- If a sequence of binary profiles is lexicographically monotone and converges coordinatewise to a limit, then every profile in the sequence is lexicographically less than or equal to the limit.
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_strict_changes_infinite_limit (profiles : ℕ → ℕ → Bool) (limit : ℕ → Bool) (hmono : Monotone (fun n => toLex (profiles n))) (hlim : ∀ k, ∃ N, ∀ n ≥ N, ∀ i < k, profiles n i = limit i) (hstrict : ∀ N, ∃ n ≥ N, toLex (profiles n) < toLex (profiles (n+1))) : ∀ K, ∃ i ≥ K, limit i = true := by classical intro K by_contra h push_neg at h have hzero : ∀ i ≥ K, limit i = false := by intro i hi have := h i hi cases hbit : limit i <;> simp_all obtain ⟨N, hN⟩ := hlim K have heq : ∀ n ≥ N, profiles n = limit := by 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 hh := hN n hn i hi rw [hh] at hbit exact (lt_irrefl _ hbit) · have hh := hzero i (by omega) rw [hh] at hbit exact (not_lt_of_ge (Bool.false_le (profiles n i))) hbit obtain ⟨n, hn, hlt⟩ := hstrict N rw [heq n hn, heq (n+1) (by omega)] at hlt exact (lt_irrefl _ hlt)