AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_lex_restrict_monotone

theoremverified

Restricting lexicographically ordered infinite binary profiles to any fixed finite prefix preserves their order.

Statement

theorem prioritized_borel_lex_restrict_monotone (k : ℕ) (p q : ℕ → Bool)
    (hpq : toLex p ≤ toLex q) :
    toLex (fun i : Fin k => p i) ≤ toLex (fun i : Fin k => q i)
Source
arXiv:2611.10136, Section 5.2.2; lexicographic priority profiles
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 1

The proof, explained

The proof proceeds by contradiction. If the restriction of p to the first k coordinates were strictly greater lexicographically than that of q, there would be a first index i < k where they differ, with q(i) < p(i) and agreement on all j < i. Since any index j < i is also strictly less than k, this same index i witnesses that q < p on the full infinite profiles. This directly contradicts the assumption that p ≤ q.

  1. To show that the prefix restriction of p is lexicographically at most that of q, it suffices to assume for contradiction that the restriction of q is strictly less than that of p.

    By `le_of_not_gt`, in a linear order, a ≤ b follows from ¬(b < a). We assume for contradiction that the restriction of q to the first k coordinates is strictly lexicographically less than that of p (`hgt`).

    lines 4–6

    uses le_of_not_gt

      classical
      apply le_of_not_gt
      intro hgt
  2. There exists an index i < k where the prefix restrictions first differ, with q(j) = p(j) for all j < i and q(i) < p(i).

    By definition of the strict lexicographical order (`Pi.Lex`) on the domain Fin k, the strict inequality `hgt` yields a witness index i : Fin k such that q(j) = p(j) for all earlier indices j < i (`hprev`) and q(i) < p(i) at index i itself (`hbit`).

    lines 7–8

    uses Pi.Lex

      change Pi.Lex (· < ·) (· < ·) (fun i : Fin k => q i) (fun i : Fin k => p i) at hgt
      obtain ⟨i, hprev, hbit⟩ := hgt
  3. The full infinite profile q is strictly lexicographically less than p.

    To show q < p lexicographically (`Pi.Lex`), we use the natural number i as the witness. For any index j < i, transitivity (`lt_trans`) with i < k yields j < k, which means j falls inside the prefix. Therefore, agreement before index i (`hprev`) ensures q(j) = p(j). Combined with q(i) < p(i) (`hbit`), this proves that q < p on the full domain (`hfull`).

    lines 9–14

    uses Pi.Lex, lt_trans

      have hfull : toLex q < toLex p := by
        change Pi.Lex (· < ·) (· < ·) q p
        refine ⟨i.val, ?_, hbit⟩
        intro j hj
        have hjk : j < k := lt_trans hj i.isLt
        simpa using hprev ⟨j, hjk⟩ hj
  4. A contradiction is reached, completing the proof.

    The initial hypothesis that p ≤ q (`hpq`) implies ¬(q < p) by `not_lt_of_ge`. This contradicts the fact just established that q < p (`hfull`).

    line 15

    uses not_lt_of_ge

      exact (not_lt_of_ge hpq) hfull
le_of_not_gt
In a linear order, if b is not strictly less than a, then a ≤ b.
Pi.Lex
The strict lexicographical ordering on dependent functions or sequences: f is strictly less than g if there is an index i such that f(i) < g(i) and f(j) = g(j) for all j < i.
lt_trans
Transitivity of strict inequality: if a < b and b < c, then a < c.
not_lt_of_ge
In a preorder, if a ≤ b, then b cannot be strictly less than a (¬ b < 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_restrict_monotone (k : ℕ) (p q : ℕ → Bool)    (hpq : toLex p ≤ toLex q) :    toLex (fun i : Fin k => p i) ≤ toLex (fun i : Fin k => q i) := by  classical  apply le_of_not_gt  intro hgt  change Pi.Lex (· < ·) (· < ·) (fun i : Fin k => q i) (fun i : Fin k => p i) at hgt  obtain ⟨i, hprev, hbit⟩ := hgt  have hfull : toLex q < toLex p := by    change Pi.Lex (· < ·) (· < ·) q p    refine ⟨i.val, ?_, hbit⟩    intro j hj    have hjk : j < k := lt_trans hj i.isLt    simpa using hprev ⟨j, hjk⟩ hj  exact (not_lt_of_ge hpq) hfull
See it in the graphDiscuss this resultChallenge it