AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_lex_profiles_limit

theoremverified

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

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.

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

    lines 4–7

    uses prioritized_borel_lex_profiles_prefix_stabilize

      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, ?_⟩
  2. 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).

    lines 8–10

      intro k
      refine ⟨N k, ?_⟩
      intro n hn i hi
  3. 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).

    lines 11–14

    uses le_max_left, le_max_right

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

    lines 15–16

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

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