prioritized_borel_lex_restrict_monotone
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- TotalPreorderA total preorder: a preorder where
- Used by 1
- prioritized_borel_lex_profiles_prefix_stabilizeEvery lexicographically nondecreasing sequence of infinite binary profiles eventually stabilizes on each finite prefix.
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.
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`).
uses
le_of_not_gtclassical apply le_of_not_gt intro hgt
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`).
uses
Pi.Lexchange Pi.Lex (· < ·) (· < ·) (fun i : Fin k => q i) (fun i : Fin k => p i) at hgt obtain ⟨i, hprev, hbit⟩ := hgt
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`).
uses
Pi.Lex,lt_transhave 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
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`).
uses
not_lt_of_geexact (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).
- In line 14, `simpa` handles the formal identification between the natural number index `j` (with `j < k`) and its representation as an element of `Fin k`.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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