AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_finite_lex_limit_stabilizes

theoremverified

A lexicographically nondecreasing sequence of binary profiles with a coordinatewise limit having finite support is eventually equal to that limit.

Statement

theorem prioritized_borel_finite_lex_limit_stabilizes (profiles : ℕ → ℕ → Bool) (limit : ℕ → Bool)
    (hmono : Monotone (fun n => toLex (profiles n)))
    (hlim : ∀ k, ∃ N, ∀ n ≥ N, ∀ i < k, profiles n i = limit i)
    (K : ℕ) (hzero : ∀ i ≥ K, limit i = false) :
    ∃ N, ∀ n ≥ N, profiles n = limit
Source
Filed by the prover as a step towards another result
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

The proof, explained

We choose an index N such that all profiles from N onward agree with the limit on the first K coordinates. For any n ≥ N, monotonicity ensures that the n-th profile is lexicographically at most the limit. If a profile were not equal to the limit, there would be a first coordinate i where profiles n i < limit i. But i < K contradicts agreement on the initial segment, while i ≥ K contradicts the hypothesis that the limit is identically false from index K onward.

  1. There exists an index N such that for all n ≥ N, the profile agrees with the limit on all coordinates below K.

    By the coordinatewise convergence hypothesis `hlim` applied to K, there exists an index N from which all profiles agree with the limit on coordinates i < K. We instantiate the existential quantifier with this N.

    lines 6–8

      classical
      obtain ⟨N, hN⟩ := hlim K
      refine ⟨N, ?_⟩
  2. For any n ≥ N, assuming profiles n ≠ limit yields a coordinate i where profiles n i < limit i.

    Fix n ≥ N. By the helper theorem `prioritized_borel_lex_profile_le_limit`, profiles n is lexicographically at most the limit. Assuming for contradiction that profiles n ≠ limit, this weak inequality strengthens to a strict lexicographic inequality by `lt_of_le_of_ne`. Unfolding the definition of lexicographic order on functions (`Pi.Lex`) provides a first index i where the two functions differ, satisfying profiles n i < limit i.

    lines 9–15

    uses prioritized_borel_lex_profile_le_limit, lt_of_le_of_ne

      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
  3. The first differing index i cannot satisfy i < K.

    If i < K, the definition of N ensures that profiles n i = limit i. Substituting this equality into profiles n i < limit i yields limit i < limit i, contradicting the irreflexivity of strict inequality (`lt_irrefl`).

    lines 16–19

    uses lt_irrefl

      by_cases hi : i < K
      · have heq := hN n hn i hi
        rw [heq] at hbit
        exact (lt_irrefl _ hbit)
  4. The first differing index i cannot satisfy i ≥ K either, completing the contradiction.

    If i ≥ K, the finite support hypothesis `hzero` implies limit i = false. Substituting this gives profiles n i < false. Since false is the least boolean value (`Bool.false_le`), no boolean can be strictly smaller than false (`not_lt_of_ge`). Since both cases lead to contradiction, profiles n = limit.

    lines 20–22

    uses Bool.false_le, not_lt_of_ge

      · have heq := hzero i (by omega)
        rw [heq] at hbit
        exact (not_lt_of_ge (Bool.false_le (profiles n i))) hbit
Bool.false_le
In the boolean ordering, false ≤ x for every boolean value x.
lt_irrefl
In a preorder, strict inequality is irreflexive: no element is strictly less than itself.
lt_of_le_of_ne
In a partial order, if a ≤ b and a ≠ b, then a < b.
not_lt_of_ge
In a preorder, if a ≤ b, then b is not strictly less than a.
prioritized_borel_lex_profile_le_limit
A lexicographically monotone sequence of binary profiles that converges coordinatewise is bounded above lexicographically by its coordinatewise 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_finite_lex_limit_stabilizes (profiles : ℕ → ℕ → Bool) (limit : ℕ → Bool)    (hmono : Monotone (fun n => toLex (profiles n)))    (hlim : ∀ k, ∃ N, ∀ n ≥ N, ∀ i < k, profiles n i = limit i)    (K : ℕ) (hzero : ∀ i ≥ K, limit i = false) :    ∃ N, ∀ n ≥ N, profiles n = limit := by  classical  obtain ⟨N, hN⟩ := hlim K  refine ⟨N, ?_⟩  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 heq := hN n hn i hi    rw [heq] at hbit    exact (lt_irrefl _ hbit)  · have heq := hzero i (by omega)    rw [heq] at hbit    exact (not_lt_of_ge (Bool.false_le (profiles n i))) hbit
See it in the graphDiscuss this resultChallenge it