decidable_is_constant_word
instanceoriginal
Decidability instance for the predicate that a word on Fin n over a type with decidable equality is constant.
Statement
instance decidable_is_constant_word {n : ℕ} {α : Type*} [DecidableEq α] (y : Fin n → α) : Decidable (is_constant_word y)
- Related work
- folklore
- Verified
- 11 Nov 2026
- Axioms
- none listed
- Built on 1
- 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 4
- op_1537_binary_length_two_one_deletionFor any nonconstant binary word y : Fin 2 → Fin 2 of length 2, there exists a longest run [a, b) of y and an immediately adjacent run [a',…
- op_1534_binary_length_two_one_deletionFor every binary word y of length 2 (y : Fin 2 → Fin 2), the one-deletion hinge sums at thresholds r = 1 and r = 2 satisfy…
- op_1537_ternary_length_two_one_deletionFor any nonconstant ternary word y : Fin 2 → Fin 3 of length 2, there exists a longest run [a, b) of y and an immediately adjacent run…
- op_1534_ternary_length_two_one_deletionFor every ternary word y of length 2 (y : Fin 2 → Fin 3), the one-deletion hinge sums at thresholds r = 1 and r = 2 satisfy…
Read back from the Lean
For any natural number $n$, any type $\alpha$ with decidable equality, and any function $y : \mathrm{Fin}\ n \to \alpha$, it is decidable whether $y$ is a constant word (i.e., whether is_constant_word y holds).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Decidability of the constant word predicate on a finite alphabet with decidable equality. -/ instance decidable_is_constant_word {n : ℕ} {α : Type*} [DecidableEq α] (y : Fin n → α) : Decidable (is_constant_word y) := Fintype.decidableForallFintype