prioritized_borel_lex_profiles_prefix_stabilize
Every lexicographically nondecreasing sequence of infinite binary profiles eventually stabilizes on each finite prefix.
Statement
theorem prioritized_borel_lex_profiles_prefix_stabilize (profiles : ℕ → ℕ → Bool) (hmono : Monotone (fun n => toLex (profiles n))) : ∀ k, ∃ N, ∀ n ≥ N, ∀ i < k, profiles n i = profiles N i
- Source
- arXiv:2611.10136, Section 5.2.2; lexicographic priority profiles
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- prioritized_borel_lex_restrict_monotoneRestricting lexicographically ordered infinite binary profiles to any fixed finite prefix preserves their order.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - Pi.Lex.finiteA dependent product of finite, indexed by finite, is a finite.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 1
- prioritized_borel_lex_profiles_limitA lexicographically nondecreasing sequence of infinite binary profiles has a coordinatewise limit, with uniform eventual agreement on each…
The proof, explained
To show that a lexicographically monotone sequence of infinite binary profiles eventually stabilizes on its first k coordinates, we restrict each profile to its length-k prefix. This restriction preserves monotonicity, producing a nondecreasing sequence in the finite lexicographically ordered set of boolean sequences of length k. Since any finite poset satisfies the ascending chain condition, this sequence of prefixes must eventually become constant, yielding the desired stabilization index N.
Fix an arbitrary prefix length k.
We enable classical logic and introduce the prefix length k on which the infinite profiles are required to stabilize.
classical intro kThe sequence of length-k prefixes f(n) is monotone in the lexicographic order.
For each profile index n, we define f(n) as the restriction of profile n to the indices below k, considered in the lexicographic order Lex (Fin k → Bool). Given a ≤ b, because the sequence of full profiles is monotone, prioritized_borel_lex_restrict_monotone shows that their length-k restrictions satisfy f(a) ≤ f(b).
uses
prioritized_borel_lex_restrict_monotonelet f : ℕ → Lex (Fin k → Bool) := fun n => toLex (fun i => profiles n i) have hf : Monotone f := by intro a b hab exact prioritized_borel_lex_restrict_monotone k (profiles a) (profiles b) (hmono hab)
The sequence of prefixes f eventually becomes constant from some index N onward.
Because Fin k → Bool is a finite set, its lexicographic ordering satisfies the ascending chain condition (WellFoundedGT). Applying WellFoundedGT.monotone_chain_condition to the monotone sequence f yields an index N such that f(N) = f(m) for all m ≥ N.
uses
WellFoundedGT.monotone_chain_conditionobtain ⟨N, hN⟩ := WellFoundedGT.monotone_chain_condition ⟨f, hf⟩For all n ≥ N and all i < k, profiles n i = profiles N i.
We choose N as the stabilization index. For any n ≥ N and i < k, the equality f(N) = f(n) yields an equality of prefix functions after unwrapping with congrArg ofLex. Evaluating both sides at the index i using congrFun gives profiles N i = profiles n i, and taking the symmetric equality completes the proof.
uses
congrArg,congrFun,ofLexrefine ⟨N, ?_⟩ intro n hn i hi have h := congrFun (congrArg ofLex (hN n hn)) (⟨i, hi⟩ : Fin k) simpa [f] using h.symm
prioritized_borel_lex_restrict_monotone- If two infinite binary sequences are lexicographically ordered, their restrictions to a prefix of length k are also lexicographically ordered.
WellFoundedGT.monotone_chain_condition- In a partially ordered set with no infinite strictly ascending chains, every monotone sequence indexed by ℕ eventually becomes constant.
congrFun- If two functions are equal, then their values at any argument are equal.
congrArg- If two values are equal, applying any function to both produces equal results.
ofLex- The canonical identity equivalence unpacking an element of Lex α back to α.
- The fact that the finite lexicographical order Lex (Fin k → Bool) satisfies the ascending chain condition (WellFoundedGT) is inferred automatically by Lean's typeclass resolution when applying WellFoundedGT.monotone_chain_condition.
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_prefix_stabilize (profiles : ℕ → ℕ → Bool) (hmono : Monotone (fun n => toLex (profiles n))) : ∀ k, ∃ N, ∀ n ≥ N, ∀ i < k, profiles n i = profiles N i := by classical intro k let f : ℕ → Lex (Fin k → Bool) := fun n => toLex (fun i => profiles n i) have hf : Monotone f := by intro a b hab exact prioritized_borel_lex_restrict_monotone k (profiles a) (profiles b) (hmono hab) obtain ⟨N, hN⟩ := WellFoundedGT.monotone_chain_condition ⟨f, hf⟩ refine ⟨N, ?_⟩ intro n hn i hi have h := congrFun (congrArg ofLex (hN n hn)) (⟨i, hi⟩ : Fin k) simpa [f] using h.symm