is_word_run_of_constant
For any constant word y on Fin n with 1 ≤ n, the full interval [0, n) is a run of y.
Statement
theorem is_word_run_of_constant {n : ℕ} {α : Type*} (y : Fin n → α) (hconst : is_constant_word y) (hn : 1 ≤ n) : is_word_run y 0 n
- Source
- folklore
- Verified
- 12 Nov 2026
- Axioms
Quot.soundpropext- Built on 2
- is_word_runA pair of indices 0 ≤ a < b ≤ n forms a run [a, b) of a word y : Fin n → α if all symbols y i for a ≤ i < b are equal, and the block…
- is_constant_wordA word y on the finite index set Fin n is constant if all its symbols are equal, that is, y i = y j for all i and j in Fin n.
- Used by 1
- is_longest_word_run_of_constantFor any constant word y on Fin n with 1 ≤ n, the interval [0, n) is a longest run of y.
Read back from the Lean
For any natural number $n$ and type $\alpha$, let $y : \text{Fin } n \to \alpha$. If $y$ is a constant word (i.e., $y(i) = y(j)$ for all $i, j : \text{Fin } n$) and $1 \le n$, then the interval from $0$ to $n$ is a run of $y$ (is_word_run y 0 n).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem shows that for any non-empty constant word y on Fin n, the full interval [0, n) forms a run. Unpacking the definition of a run, the length bound 0 < n is given by 1 ≤ n, the upper bound n ≤ n holds by reflexivity, and the boundary maximality conditions hold trivially since the interval already spans the entire domain [0, n). Finally, the required constancy on [0, n) follows directly from the hypothesis that y takes identical values everywhere.
The run conditions for the full interval [0, n) reduce to showing that y(i) = y(0) for all indices i in [0, n).
The definition of a word run `is_word_run y 0 n` requires five conditions: 0 < n, n ≤ n, constancy of y on [0, n), and boundary maximality at both endpoints (meaning the interval cannot be extended to the left or right). We instantiate the existential quantifier and conjunction using `refine`: the condition 0 < n is supplied by the assumption hn (1 ≤ n); n ≤ n is proved by reflexivity of ≤ (`le_rfl`); and the boundary conditions hold trivially via `Or.inl rfl` because the start index is 0 and the end index is n. This leaves only the subgoal that y(i) = y(0) for all i in [0, n).
uses
le_rfl,Or.inl,rflrefine ⟨hn, le_rfl, ?_, Or.inl rfl, Or.inl rfl⟩
Every index i in the interval satisfies y(i) = y(0), completing the proof.
We introduce an arbitrary index i and the hypothesis that 0 ≤ i < n. By the assumption `hconst` that y is constant, y(i) = y(j) for all indices i, j in Fin n. Applying this to i and the index 0 (represented as ⟨0, hn⟩) establishes y(i) = y(0), closing the goal.
intro i hi exact hconst i ⟨0, hn⟩
le_rfl- Every element in a preorder is less than or equal to itself: a ≤ a.
Or.inl- Derives a disjunction a ∨ b from a proof of its left disjunct a.
rfl- Reflexivity of equality: proves a = a for any term a.
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 any constant word on Fin n with 1 ≤ n, the full interval [0, n) is a run. -/theorem is_word_run_of_constant {n : ℕ} {α : Type*} (y : Fin n → α) (hconst : is_constant_word y) (hn : 1 ≤ n) : is_word_run y 0 n := by refine ⟨hn, le_rfl, ?_, Or.inl rfl, Or.inl rfl⟩ intro i hi exact hconst i ⟨0, hn⟩