AFTD Auto-Formalizing Theoretical Domains

with_top_nat_lex_add_binary_le_iff

theoremverified

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.

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.

  1. 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).

    lines 5–7

    uses ne_top_of_lt, lt_of_le_of_lt, WithTop.coe_lt_top

      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))
  2. 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).

    lines 8–14

    uses WithTop.add_right_inj, congrFun

      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]
  3. 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).

    lines 15–29

    uses Pi.Lex, congrArg, Pi.add_apply, WithTop.add_lt_add_iff_right, WithTop.add_right_inj

      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)
  4. 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.

    lines 30–31

    uses toLex_inj, ofLex_inj

      have h_eq : (toLex (ofLex u + e) = toLex (ofLex v + e)) ↔ u = v := by
        rw [toLex_inj, h_eq_fun, ofLex_inj]
  5. 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).

    lines 32–39

    uses le_iff_lt_or_eq, Or.inl, Or.inr

      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)
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.

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

/-- 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)
See it in the graphDiscuss this resultChallenge it