AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_lex_profiles_prefix_stabilize

theoremverified

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
Used by 1

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.

  1. 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.

    lines 4–5

      classical
      intro k
  2. The 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).

    lines 6–9

    uses prioritized_borel_lex_restrict_monotone

      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)
  3. 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.

    line 10

    uses WellFoundedGT.monotone_chain_condition

      obtain ⟨N, hN⟩ := WellFoundedGT.monotone_chain_condition ⟨f, hf⟩
  4. 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.

    lines 11–14

    uses congrArg, congrFun, ofLex

      refine ⟨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 α.

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

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
See it in the graphDiscuss this resultChallenge it