list_lex_ofFn_of_exists_lt
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.
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.
uses
Fin.elim0induction m with | zero => exact Fin.elim0 t
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.
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 hltWhen 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.
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
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.
uses
Fin.succ_lt_succ_iff.mprapply 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
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.
/-- 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