prioritized_borel_lex_profiles_limit
A lexicographically nondecreasing sequence of infinite binary profiles has a coordinatewise limit, with uniform eventual agreement on each finite prefix.
Statement
theorem prioritized_borel_lex_profiles_limit (profiles : ℕ → ℕ → Bool) (hmono : Monotone (fun n => toLex (profiles n))) : ∃ limit : ℕ → Bool, ∀ k, ∃ N, ∀ n ≥ N, ∀ i < k, profiles n i = limit i
- 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_profiles_prefix_stabilizeEvery lexicographically nondecreasing sequence of infinite binary profiles eventually stabilizes on each finite prefix.
- 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
By a previous theorem, every finite prefix of a lexicographically monotone sequence of binary profiles eventually stabilizes. We define the limit profile pointwise by setting its i-th coordinate to the value at stage N(i+1), where the prefix of length i+1 has stabilized. To verify that any prefix of length k agrees with the limit from stage N(k) onwards, we compare the value at stage n to the limit value via a common future stage j = max(N(k), N(i+1)), where both stabilization guarantees hold simultaneously.
There is a candidate limit profile whose value at coordinate i is the stabilized value profiles(N(i+1), i).
By the prefix stabilization theorem `prioritized_borel_lex_profiles_prefix_stabilize`, for every prefix length k there is an index past which the first k coordinates remain constant. Using the axiom of choice, we select a function N : ℕ → ℕ such that the prefix of length k stabilizes from stage N(k) onwards. We define the candidate limit profile by evaluating each coordinate i at the stage N(i+1) where the prefix up to i+1 has stabilized, and propose this limit as the existential witness.
uses
prioritized_borel_lex_profiles_prefix_stabilizeclassical choose N hN using prioritized_borel_lex_profiles_prefix_stabilize profiles hmono let limit : ℕ → Bool := fun i => profiles (N (i+1)) i refine ⟨limit, ?_⟩
To show prefix agreement, for any prefix length k, we choose N(k) as the threshold and consider any n ≥ N(k) and coordinate i < k.
Given an arbitrary prefix length k, we set the stabilization threshold to N(k). We then consider an arbitrary index n ≥ N(k) and any coordinate i < k, leaving the goal of showing profiles(n, i) = limit(i).
intro k refine ⟨N k, ?_⟩ intro n hn i hi
At the common stage j = max(N(k), N(i+1)), the value profiles(j, i) agrees with both profiles(N(k), i) and profiles(N(i+1), i).
Since n ≥ N(k) and i < k, stabilization gives profiles(n, i) = profiles(N(k), i). Introducing j = max(N(k), N(i+1)), we have j ≥ N(k) by `le_max_left`, so stabilization at length k also implies profiles(j, i) = profiles(N(k), i). Furthermore, j ≥ N(i+1) by `le_max_right` and i < i+1 (by linear arithmetic), so stabilization at length i+1 implies profiles(j, i) = profiles(N(i+1), i).
uses
le_max_left,le_max_righthave hfirst := hN k n hn i hi let j := max (N k) (N (i+1)) have hleft := hN k j (le_max_left _ _) i hi have hright := hN (i+1) j (le_max_right _ _) i (by omega)
profiles(n, i) = limit(i).
Unfolding the definition of limit(i) as profiles(N(i+1), i), we chain the equalities: profiles(n, i) = profiles(N(k), i) = profiles(j, i) = profiles(N(i+1), i) = limit(i).
dsimp [limit] exact hfirst.trans (hleft.symm.trans hright)
prioritized_borel_lex_profiles_prefix_stabilize- For any lexicographically monotone sequence of binary profiles, every finite prefix of length k eventually stabilizes permanently from some index onward.
le_max_left- In any linear order, an element is less than or equal to the maximum of itself and another element (a ≤ max a b).
le_max_right- In any linear order, an element is less than or equal to the maximum of another element and itself (b ≤ max a b).
- The proof invokes the axiom of choice (via `choose`) to select a sequence of stabilization thresholds $N(k)$ simultaneously for all prefix lengths $k$.
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_profiles_limit (profiles : ℕ → ℕ → Bool) (hmono : Monotone (fun n => toLex (profiles n))) : ∃ limit : ℕ → Bool, ∀ k, ∃ N, ∀ n ≥ N, ∀ i < k, profiles n i = limit i := by classical choose N hN using prioritized_borel_lex_profiles_prefix_stabilize profiles hmono let limit : ℕ → Bool := fun i => profiles (N (i+1)) i refine ⟨limit, ?_⟩ intro k refine ⟨N k, ?_⟩ intro n hn i hi have hfirst := hN k n hn i hi let j := max (N k) (N (i+1)) have hleft := hN k j (le_max_left _ _) i hi have hright := hN (i+1) j (le_max_right _ _) i (by omega) dsimp [limit] exact hfirst.trans (hleft.symm.trans hright)