AFTD Auto-Formalizing Theoretical Domains

list_lex_ofFn_of_exists_lt

theoremverified

If two vectors on Fin m agree on all coordinates before t and the first vector is strictly smaller at coordinate t, then their list representations are strictly ordered by List.Lex (<).

Statement

theorem list_lex_ofFn_of_exists_lt {m : ℕ} (f g : Fin m → ℕ)
    (t : Fin m)
    (heq : ∀ s : Fin m, s < t → f s = g s)
    (hlt : f t < g t) :
    List.Lex (· < ·) (List.ofFn f) (List.ofFn g)
Source
step towards round_robin_phi_lex_strict_increase
Verified
23 Oct 2026
Axioms
Quot.soundpropext

The proof, explained

The theorem is proved by induction on the vector length m. In the base case m = 0, the index t belongs to Fin 0, which is empty. For vectors of length m + 1, we case split on whether t = 0 or t = t'.succ: if t = 0, the list heads satisfy f 0 < g 0, which directly establishes the lexicographical order; if t = t'.succ, the heads agree and can be removed, reducing the goal to the tails, which are ordered by the induction hypothesis.

  1. The theorem holds vacuously when m = 0.

    We proceed by induction on the vector length m. When m = 0, the coordinate t belongs to the empty type Fin 0. Fin.elim0 produces a proof of the goal from this impossible hypothesis.

    lines 7–9

    uses Fin.elim0

      induction m with
      | zero =>
          exact Fin.elim0 t
  2. For vectors of length m + 1, if the mismatch index is t = 0, the first elements determine the lexicographical order.

    For the inductive step on m + 1, Fin.eq_zero_or_eq_succ decomposes t into either 0 or a successor t'.succ. When t = 0, both lists are unfolded with List.ofFn_succ into heads f 0 and g 0 followed by tails. Since f 0 < g 0 by assumption, List.Lex.rel concludes that the first list is lexicographically smaller than the second.

    lines 10–13

    uses Fin.eq_zero_or_eq_succ, List.ofFn_succ, List.Lex.rel

      | succ m ih =>
          rcases Fin.eq_zero_or_eq_succ t with rfl | ⟨t', rfl⟩
          · rw [List.ofFn_succ, List.ofFn_succ]
            exact List.Lex.rel hlt
  3. When t = t'.succ, the first elements of both lists are equal and can be stripped.

    Both lists are again expanded with List.ofFn_succ to expose their first elements f 0 and g 0. Because 0 < t'.succ by Fin.succ_pos, the agreement hypothesis heq implies f 0 = g 0. Rewriting f 0 to g 0 and applying List.Lex.cons reduces the problem to showing the tails are lexicographically ordered.

    lines 14–17

    uses List.ofFn_succ, Fin.succ_pos, List.Lex.cons

          · rw [List.ofFn_succ, List.ofFn_succ]
            have h0 : f 0 = g 0 := heq 0 (Fin.succ_pos t')
            rw [h0]
            apply List.Lex.cons
  4. The tails are lexicographically ordered by the induction hypothesis.

    We apply the induction hypothesis ih to the shifted functions f ∘ Fin.succ and g ∘ Fin.succ at index t'. For any s < t', Fin.succ_lt_succ_iff.mpr ensures s.succ < t'.succ, so heq gives f s.succ = g s.succ. Finally, the strict inequality f t'.succ < g t'.succ holds directly from hlt.

    lines 18–21

    uses Fin.succ_lt_succ_iff.mpr

            apply ih
            · intro s hs
              exact heq s.succ (Fin.succ_lt_succ_iff.mpr hs)
            · exact hlt
Fin.elim0
The principle of explosion for the empty type Fin 0: any term of Fin 0 proves any proposition.
Fin.eq_zero_or_eq_succ
Every element of Fin (n + 1) is either 0 or the successor j.succ of some j : Fin n.
List.ofFn_succ
The list representation of a function f on Fin (n + 1) expands to f 0 followed by the list representation of f ∘ Fin.succ.
List.Lex.rel
If the head of the first list is strictly smaller than the head of the second list under relation r, then the first list is lexicographically smaller than the second.
Fin.succ_pos
The successor of any element in Fin n is strictly positive (greater than 0).
List.Lex.cons
Prefixing the same head element to both lists preserves their lexicographical order.
Fin.succ_lt_succ_iff.mpr
Strict inequality is preserved by taking successors: if s < t, then s.succ < t.succ.

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

/-- For functions f, g on Fin m, if they agree on all indices before t and f t < g t, then List.ofFn f is strictly less than List.ofFn g in the lexicographic ordering List.Lex (· < ·). -/theorem list_lex_ofFn_of_exists_lt {m : ℕ} (f g : Fin m → ℕ)    (t : Fin m)    (heq : ∀ s : Fin m, s < t → f s = g s)    (hlt : f t < g t) :    List.Lex (· < ·) (List.ofFn f) (List.ofFn g) := by  induction m with  | zero =>      exact Fin.elim0 t  | succ m ih =>      rcases Fin.eq_zero_or_eq_succ t with rfl | ⟨t', rfl⟩      · rw [List.ofFn_succ, List.ofFn_succ]        exact List.Lex.rel hlt      · rw [List.ofFn_succ, List.ofFn_succ]        have h0 : f 0 = g 0 := heq 0 (Fin.succ_pos t')        rw [h0]        apply List.Lex.cons        apply ih        · intro s hs          exact heq s.succ (Fin.succ_lt_succ_iff.mpr hs)        · exact hlt
See it in the graphDiscuss this resultChallenge it