with_top_nat_lex_add_binary_le_iff
Pointwise addition of a binary shift sequence e : ℕ → {0, 1} strictly preserves and reflects the lexicographic order on WithTop ℕ streams.
Statement
theorem with_top_nat_lex_add_binary_le_iff
(u v : Lex (ℕ → WithTop ℕ)) (e : ℕ → WithTop ℕ) (he : ∀ t, e t ≤ 1) :
u ≤ v ↔ (toLex (ofLex u + e)) ≤ (toLex (ofLex v + e))- Source
- step towards swf_anonymous_stationary_monotone_upper_lower_dominance_exists
- Verified
- 03 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
The proof, explained
Pointwise addition of a binary sequence e : ℕ → {0, 1} preserves and reflects the lexicographic order on streams in WithTop ℕ. Because each coordinate e(t) ≤ 1 < ⊤, adding e(t) is strictly monotone and cancellative at every index. Consequently, the condition defining strict lexicographic precedence—agreement up to a first index where strict inequality holds—is invariant under shifting by e. Decomposing the non-strict order into strict inequality or equality then completes the equivalence.
For every index t, the shift term e(t) is finite (e(t) ≠ ⊤).
Since e(t) ≤ 1 by hypothesis and 1 < ⊤ in WithTop ℕ (via WithTop.coe_lt_top), transitivity (lt_of_le_of_lt) gives e(t) < ⊤. An element strictly below ⊤ cannot be ⊤ (ne_top_of_lt).
uses
ne_top_of_lt,lt_of_le_of_lt,WithTop.coe_lt_tophave he_ne_top : ∀ t, e t ≠ ⊤ := by intro t exact ne_top_of_lt (lt_of_le_of_lt (he t) (WithTop.coe_lt_top 1))
Pointwise addition by e preserves and reflects equality of the underlying sequences: u + e = v + e ↔ u = v.
The reverse implication is immediate by substitution. For the forward implication, two sequences are equal if they agree at every index t. Evaluating u + e = v + e at t gives u(t) + e(t) = v(t) + e(t). Because e(t) ≠ ⊤, right-cancellation (WithTop.add_right_inj) yields u(t) = v(t).
uses
WithTop.add_right_inj,congrFunhave h_eq_fun : (ofLex u + e = ofLex v + e) ↔ (ofLex u = ofLex v) := by constructor · intro h ext t exact (WithTop.add_right_inj (he_ne_top t)).1 (by simpa using congrFun h t) · intro h rw [h]
Pointwise addition by e preserves and reflects the strict lexicographic order: u < v ↔ u + e < v + e.
By definition of lexicographic ordering on sequences (Pi.Lex), u < v means there is a first index i where u(i) < v(i), with u(j) = v(j) for all j < i. In the forward direction, adding e(j) preserves equality at all j < i (by congrArg), while at index i, right addition by e(i) ≠ ⊤ preserves strict inequality (WithTop.add_lt_add_iff_right). In the reverse direction, at each j < i right-cancellation (WithTop.add_right_inj) restores u(j) = v(j), and at index i, right addition by e(i) ≠ ⊤ reflects strict inequality (WithTop.add_lt_add_iff_right), recovering u(i) < v(i).
uses
Pi.Lex,congrArg,Pi.add_apply,WithTop.add_lt_add_iff_right,WithTop.add_right_injhave h_lt : u < v ↔ toLex (ofLex u + e) < toLex (ofLex v + e) := by change Pi.Lex (· < ·) (· < ·) (ofLex u) (ofLex v) ↔ Pi.Lex (· < ·) (· < ·) (ofLex u + e) (ofLex v + e) constructor · rintro ⟨i, hi, hlt⟩ refine ⟨i, ?_, ?_⟩ · intro j hj simpa using congrArg (fun x => x + e j) (hi j hj) · simpa only [Pi.add_apply] using (WithTop.add_lt_add_iff_right (he_ne_top i)).2 hlt · rintro ⟨i, hi, hlt⟩ refine ⟨i, ?_, ?_⟩ · intro j hj exact (WithTop.add_right_inj (he_ne_top j)).1 (by simpa using hi j hj) · exact (WithTop.add_lt_add_iff_right (he_ne_top i)).1 (by simpa using hlt)
The shifted sequences are equal in the lexicographically ordered type if and only if u = v.
Equality in the lexicographic type synonym Lex reduces to equality of the underlying sequences via `toLex_inj` and `ofLex_inj`, which was already shown to be equivalent to u = v.
uses
toLex_inj,ofLex_injhave h_eq : (toLex (ofLex u + e) = toLex (ofLex v + e)) ↔ u = v := by rw [toLex_inj, h_eq_fun, ofLex_inj]
Pointwise addition of e preserves and reflects the non-strict lexicographic order: u ≤ v ↔ u + e ≤ v + e.
In any partial order, x ≤ y is equivalent to x < y ∨ x = y (le_iff_lt_or_eq). Applying this to both sides, the forward and backward directions follow directly by matching the strict inequality branch using the strict order equivalence (with Or.inl) and the equality branch using the equality equivalence (with Or.inr).
uses
le_iff_lt_or_eq,Or.inl,Or.inrrw [le_iff_lt_or_eq, le_iff_lt_or_eq] constructor · rintro (hlt | heq) · exact Or.inl (h_lt.mp hlt) · exact Or.inr (h_eq.mpr heq) · rintro (hlt | heq) · exact Or.inl (h_lt.mpr hlt) · exact Or.inr (h_eq.mp heq)
ne_top_of_lt- If an element is strictly less than another, it cannot equal the top element ⊤.
lt_of_le_of_lt- Transitivity of order: if a ≤ b and b < c, then a < c.
WithTop.coe_lt_top- Any standard natural number coerced into `WithTop ℕ` is strictly less than ⊤.
WithTop.add_right_inj- Right addition by a non-top element is cancellative: x + z = y + z if and only if x = y.
congrFun- Equal functions yield equal values on every input.
Pi.Lex- The lexicographic order on sequences: f < g if they agree at all coordinates before an index where f is strictly less than g.
congrArg- Applying a function to equal arguments produces equal results.
Pi.add_apply- Function addition is defined pointwise: (f + g)(i) = f(i) + g(i).
WithTop.add_lt_add_iff_right- Right addition by an element other than ⊤ strictly preserves and reflects strict inequality: x + z < y + z if and only if x < y.
toLex_inj- The type equivalence `toLex` is injective.
ofLex_inj- The type equivalence `ofLex` is injective.
le_iff_lt_or_eq- In a partial order, a ≤ b if and only if a < b or a = b.
Or.inl- Left introduction for disjunction: a implies a ∨ b.
Or.inr- Right introduction for disjunction: b implies a ∨ b.
- The type synonyms `toLex` and `ofLex` are Lean artifacts used to equip the sequence space `ℕ → WithTop ℕ` with the lexicographic order rather than the default pointwise order; mathematically, `u`, `v`, and their shifts are simply sequences.
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.
/-- Coordinate-wise addition of a {0, 1}-valued binary sequence preserves and reflects lexicographic order on sequences in WithTop ℕ (Claim 1 of Dubey et al. 2026). -/theorem with_top_nat_lex_add_binary_le_iff (u v : Lex (ℕ → WithTop ℕ)) (e : ℕ → WithTop ℕ) (he : ∀ t, e t ≤ 1) : u ≤ v ↔ (toLex (ofLex u + e)) ≤ (toLex (ofLex v + e)) := by have he_ne_top : ∀ t, e t ≠ ⊤ := by intro t exact ne_top_of_lt (lt_of_le_of_lt (he t) (WithTop.coe_lt_top 1)) have h_eq_fun : (ofLex u + e = ofLex v + e) ↔ (ofLex u = ofLex v) := by constructor · intro h ext t exact (WithTop.add_right_inj (he_ne_top t)).1 (by simpa using congrFun h t) · intro h rw [h] have h_lt : u < v ↔ toLex (ofLex u + e) < toLex (ofLex v + e) := by change Pi.Lex (· < ·) (· < ·) (ofLex u) (ofLex v) ↔ Pi.Lex (· < ·) (· < ·) (ofLex u + e) (ofLex v + e) constructor · rintro ⟨i, hi, hlt⟩ refine ⟨i, ?_, ?_⟩ · intro j hj simpa using congrArg (fun x => x + e j) (hi j hj) · simpa only [Pi.add_apply] using (WithTop.add_lt_add_iff_right (he_ne_top i)).2 hlt · rintro ⟨i, hi, hlt⟩ refine ⟨i, ?_, ?_⟩ · intro j hj exact (WithTop.add_right_inj (he_ne_top j)).1 (by simpa using hi j hj) · exact (WithTop.add_lt_add_iff_right (he_ne_top i)).1 (by simpa using hlt) have h_eq : (toLex (ofLex u + e) = toLex (ofLex v + e)) ↔ u = v := by rw [toLex_inj, h_eq_fun, ofLex_inj] rw [le_iff_lt_or_eq, le_iff_lt_or_eq] constructor · rintro (hlt | heq) · exact Or.inl (h_lt.mp hlt) · exact Or.inr (h_eq.mpr heq) · rintro (hlt | heq) · exact Or.inl (h_lt.mpr hlt) · exact Or.inr (h_eq.mp heq)