AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_lex_profile_le_limit

theoremverified

Each member of a lexicographically nondecreasing binary profile sequence is at most its coordinatewise limit.

Statement

theorem prioritized_borel_lex_profile_le_limit (profiles : ℕ → ℕ → Bool) (limit : ℕ → Bool)
    (hmono : Monotone (fun n => toLex (profiles n)))
    (hlim : ∀ k, ∃ N, ∀ n ≥ N, ∀ i < k, profiles n i = limit i) :
    ∀ n, toLex (profiles n) ≤ toLex limit
Source
arXiv:2611.10136, Section 5.2.2; lexicographic priority profiles
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 2

The proof, explained

The proof proceeds by contradiction: we fix an index n and assume that the limit sequence is lexicographically strictly smaller than the n-th profile sequence. By definition of the lexicographical order, the two sequences must first differ at some coordinate i, where the limit has a strictly smaller bit. By coordinatewise convergence, all profiles beyond some index N agree with the limit on all coordinates up to i. Choosing j = max(n, N), monotonicity implies that profile n is at most profile j, yet profile j matches the limit through index i and is therefore strictly smaller than profile n, a contradiction.

  1. Suppose, for contradiction, that the limit is lexicographically strictly less than the n-th profile, and let i be the first coordinate where they differ.

    To show that toLex (profiles n) ≤ toLex limit for an arbitrary index n, we proceed by contradiction using the linearity of the order (`le_of_not_gt`), assuming instead that toLex limit < toLex (profiles n) (hypothesis `hgt`). By definition of the strict lexicographical order (`Pi.Lex`), there exists a coordinate index i such that limit k = profiles n k for all k < i (hypothesis `hprev`), while limit i < profiles n i (hypothesis `hbit`).

    lines 5–10

    uses le_of_not_gt, Pi.Lex

      classical
      intro n
      apply le_of_not_gt
      intro hgt
      change Pi.Lex (· < ·) (· < ·) limit (profiles n) at hgt
      obtain ⟨i, hprev, hbit⟩ := hgt
  2. There is an index j ≥ n such that profile j agrees with the limit on all coordinates up to i, and toLex (profiles n) ≤ toLex (profiles j).

    From the convergence hypothesis `hlim` applied at coordinate length i + 1, we obtain an index N such that for all j ≥ N, profiles j matches limit on all coordinates strictly less than i + 1. Setting j = max n N, we have n ≤ j by `le_max_left`. By the assumed monotonicity of the profile sequence (`hmono`), this implies toLex (profiles n) ≤ toLex (profiles j) (hypothesis `hcmp`).

    lines 11–13

    uses le_max_left

      obtain ⟨N, hN⟩ := hlim (i+1)
      let j := max n N
      have hcmp := hmono (show n ≤ j from le_max_left _ _)
  3. toLex (profiles j) < toLex (profiles n).

    We show that profile j is lexicographically strictly smaller than profile n by using i as the witness in `Pi.Lex`. Since j ≥ N by `le_max_right`, the convergence property `hN` applies to j at all coordinates up to i. First, for every k < i, we have profiles j k = limit k, which equals profiles n k by `hprev`. Second, at coordinate i, profiles j i = limit i, which is strictly less than profiles n i by `hbit`. Hence, profile j matches profile n before index i and is strictly smaller at index i.

    lines 14–21

    uses Pi.Lex, le_max_right

      have hlt : toLex (profiles j) < toLex (profiles n) := by
        change Pi.Lex (· < ·) (· < ·) (profiles j) (profiles n)
        refine ⟨i, ?_, ?_⟩
        · intro k hk
          rw [hN j (le_max_right _ _) k (by omega)]
          exact hprev k hk
        · rw [hN j (le_max_right _ _) i (by omega)]
          exact hbit
  4. Contradiction: toLex (profiles j) cannot be both at least and strictly less than toLex (profiles n).

    From `hcmp`, toLex (profiles n) ≤ toLex (profiles j). By `not_lt_of_ge`, this implies that toLex (profiles j) < toLex (profiles n) cannot hold, which directly contradicts `hlt`.

    line 22

    uses not_lt_of_ge

      exact (not_lt_of_ge hcmp) hlt
le_of_not_gt
in a linear order, if b is not strictly less than a, then a ≤ b
Pi.Lex
the strict lexicographical relation on index-dependent functions, holding when two functions agree on all coordinates preceding the first index where the first function is strictly smaller
le_max_left
in a linear order, an element a is less than or equal to max(a, b)
le_max_right
in a linear order, an element b is less than or equal to max(a, b)
not_lt_of_ge
in a preorder, if a ≤ b, then b is not strictly less than a

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_profile_le_limit (profiles : ℕ → ℕ → Bool) (limit : ℕ → Bool)    (hmono : Monotone (fun n => toLex (profiles n)))    (hlim : ∀ k, ∃ N, ∀ n ≥ N, ∀ i < k, profiles n i = limit i) :    ∀ n, toLex (profiles n) ≤ toLex limit := by  classical  intro n  apply le_of_not_gt  intro hgt  change Pi.Lex (· < ·) (· < ·) limit (profiles n) at hgt  obtain ⟨i, hprev, hbit⟩ := hgt  obtain ⟨N, hN⟩ := hlim (i+1)  let j := max n N  have hcmp := hmono (show n ≤ j from le_max_left _ _)  have hlt : toLex (profiles j) < toLex (profiles n) := by    change Pi.Lex (· < ·) (· < ·) (profiles j) (profiles n)    refine ⟨i, ?_, ?_⟩    · intro k hk      rw [hN j (le_max_right _ _) k (by omega)]      exact hprev k hk    · rw [hN j (le_max_right _ _) i (by omega)]      exact hbit  exact (not_lt_of_ge hcmp) hlt
See it in the graphDiscuss this resultChallenge it