AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_lex_strict_changes_infinite_limit

theoremverified

If a lexicographically nondecreasing sequence of binary profiles has strict increases arbitrarily late, its coordinatewise limit contains true entries arbitrarily late.

Statement

theorem prioritized_borel_lex_strict_changes_infinite_limit (profiles : ℕ → ℕ → Bool)
    (limit : ℕ → Bool)
    (hmono : Monotone (fun n => toLex (profiles n)))
    (hlim : ∀ k, ∃ N, ∀ n ≥ N, ∀ i < k, profiles n i = limit i)
    (hstrict : ∀ N, ∃ n ≥ N, toLex (profiles n) < toLex (profiles (n+1))) :
    ∀ K, ∃ i ≥ K, limit i = true
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

We argue by contradiction: suppose that beyond some coordinate K, the limit profile is identically false. By coordinatewise convergence, the profiles must eventually agree with the limit on all coordinates before K. Combined with the fact that each profile is lexicographically bounded above by the limit, this forces every profile to equal the limit from that stage onward. This eventual constancy contradicts the hypothesis that strict lexicographic increases occur arbitrarily late in the sequence.

  1. Assume, for contradiction, that no index at or beyond K has limit value true.

    We introduce an arbitrary coordinate bound K and suppose the contrary: that for every index i ≥ K, the limit value is not true.

    lines 7–10

      classical
      intro K
      by_contra h
      push_neg at h
  2. For all coordinates i ≥ K, the limit is identically false.

    Because Boolean values are either true or false, the assumption that limit i ≠ true for all i ≥ K forces limit i = false for every such coordinate.

    lines 11–14

      have hzero : ∀ i ≥ K, limit i = false := by
        intro i hi
        have := h i hi
        cases hbit : limit i <;> simp_all
  3. There exists a stage N after which all profiles agree with the limit on every index strictly less than K.

    By coordinatewise convergence (hlim) applied at K, there is an index N such that profiles n i = limit i for all n ≥ N and all i < K.

    line 15

      obtain ⟨N, hN⟩ := hlim K
  4. If a profile at or after stage N differs from the limit, there is a first coordinate where it is strictly smaller than the limit.

    We claim profiles n = limit for all n ≥ N. If not, since profiles n ≤ limit holds lexicographically by prioritized_borel_lex_profile_le_limit, the inequality is strict by lt_of_le_of_ne. Expanding the definition of the lexicographical order (Pi.Lex) provides a minimal index i at which profiles n i < limit i.

    lines 16–23

    uses prioritized_borel_lex_profile_le_limit, lt_of_le_of_ne, Pi.Lex

      have heq : ∀ n ≥ N, profiles n = limit := by
        intro n hn
        have hle := prioritized_borel_lex_profile_le_limit profiles limit hmono hlim n
        by_contra hne
        have hne' : toLex (profiles n) ≠ toLex limit := by simpa using hne
        have hlt : toLex (profiles n) < toLex limit := lt_of_le_of_ne hle hne'
        change Pi.Lex (· < ·) (· < ·) (profiles n) limit at hlt
        obtain ⟨i, _, hbit⟩ := hlt
  5. The first differing coordinate i cannot be strictly less than K.

    If i < K, then profiles n i = limit i by the choice of N. Substituting this into profiles n i < limit i yields limit i < limit i, contradicting the irreflexivity of strict inequality (lt_irrefl).

    lines 24–27

    uses lt_irrefl

        by_cases hi : i < K
        · have hh := hN n hn i hi
          rw [hh] at hbit
          exact (lt_irrefl _ hbit)
  6. The first differing coordinate i cannot be at or beyond K, concluding that all profiles from stage N onward equal the limit.

    If i ≥ K, then limit i = false. But false is the minimum Boolean element (Bool.false_le), so no value can be strictly less than false (not_lt_of_ge), contradicting profiles n i < false. Since neither i < K nor i ≥ K is possible, profiles n = limit for all n ≥ N.

    lines 28–30

    uses Bool.false_le, not_lt_of_ge

        · have hh := hzero i (by omega)
          rw [hh] at hbit
          exact (not_lt_of_ge (Bool.false_le (profiles n i))) hbit
  7. A contradiction is reached, completing the proof.

    By the strict changes hypothesis (hstrict), there is some n ≥ N where profiles n < profiles (n + 1) in lexicographic order. Since both n and n + 1 are at least N, both profiles equal the limit, giving limit < limit, which contradicts the irreflexivity of strict inequality (lt_irrefl).

    lines 31–33

    uses lt_irrefl

      obtain ⟨n, hn, hlt⟩ := hstrict N
      rw [heq n hn, heq (n+1) (by omega)] at hlt
      exact (lt_irrefl _ hlt)
Bool.false_le
The Boolean value false is less than or equal to any Boolean value x.
not_lt_of_ge
In a preorder, if a ≤ b then it is not the case that b < a.
lt_irrefl
Strict inequality is irreflexive: for any element a in a preorder, it is not the case that a < a.
lt_of_le_of_ne
In a partial order, if a ≤ b and a ≠ b, then a < b.
Pi.Lex
The lexicographical order relation on function types: f < g if at the minimal index where they differ, the value of f is strictly less than the value of g.
prioritized_borel_lex_profile_le_limit
If a sequence of binary profiles is lexicographically monotone and converges coordinatewise to a limit, then every profile in the sequence is lexicographically less than or equal to the limit.

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_strict_changes_infinite_limit (profiles : ℕ → ℕ → Bool)    (limit : ℕ → Bool)    (hmono : Monotone (fun n => toLex (profiles n)))    (hlim : ∀ k, ∃ N, ∀ n ≥ N, ∀ i < k, profiles n i = limit i)    (hstrict : ∀ N, ∃ n ≥ N, toLex (profiles n) < toLex (profiles (n+1))) :    ∀ K, ∃ i ≥ K, limit i = true := by  classical  intro K  by_contra h  push_neg at h  have hzero : ∀ i ≥ K, limit i = false := by    intro i hi    have := h i hi    cases hbit : limit i <;> simp_all  obtain ⟨N, hN⟩ := hlim K  have heq : ∀ n ≥ N, profiles n = limit := by    intro n hn    have hle := prioritized_borel_lex_profile_le_limit profiles limit hmono hlim n    by_contra hne    have hne' : toLex (profiles n) ≠ toLex limit := by simpa using hne    have hlt : toLex (profiles n) < toLex limit := lt_of_le_of_ne hle hne'    change Pi.Lex (· < ·) (· < ·) (profiles n) limit at hlt    obtain ⟨i, _, hbit⟩ := hlt    by_cases hi : i < K    · have hh := hN n hn i hi      rw [hh] at hbit      exact (lt_irrefl _ hbit)    · have hh := hzero i (by omega)      rw [hh] at hbit      exact (not_lt_of_ge (Bool.false_le (profiles n i))) hbit  obtain ⟨n, hn, hlt⟩ := hstrict N  rw [heq n hn, heq (n+1) (by omega)] at hlt  exact (lt_irrefl _ hlt)
See it in the graphDiscuss this resultChallenge it