Idempotent factorization of infinite words
Lax369799.WordFactorization · concepts/Lax369799/WordFactorization.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
An infinite word in a finite monoid has a nonempty initial block of value , followed by nonempty blocks of a common idempotent value , with . The increasing cuts are cofinal and every union of consecutive blocks after the first again has value .
Concept map
Lean source view on GitHub
| 1 | import Lax369799.InfiniteRamsey |
| 2 | import Mathlib.Algebra.BigOperators.Group.List.Basic |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Idempotent factorization of infinite words |
| 7 | type: theorem |
| 8 | --- |
| 9 | An infinite word in a finite monoid has a nonempty initial block of value |
| 10 | `a`, followed by nonempty blocks of a common idempotent value `e`, with |
| 11 | `a * e = a`. The increasing cuts are cofinal and every union of consecutive |
| 12 | blocks after the first again has value `e`. |
| 13 | -/ |
| 14 | namespace Lax369799.WordFactorization |
| 15 | |
| 16 | /-- Product of the half-open interval of letters [i,j). -/ |
| 17 | def block {M : Type} [Monoid M] (w : ℕ → M) (i j : ℕ) : M := |
| 18 | ((List.range' i (j - i)).map w).prod |
| 19 | |
| 20 | axiom factorization {M : Type} [Monoid M] [Finite M] (w : ℕ → M) : |
| 21 | ∃ (cut : ℕ → ℕ) (a e : M), StrictMono cut ∧ 0 < cut 0 ∧ |
| 22 | e * e = e ∧ a * e = a ∧ |
| 23 | (∀ i, block w 0 (cut i) = a) ∧ |
| 24 | (∀ i j, i < j → block w (cut i) (cut j) = e) |
| 25 | |
| 26 | end Lax369799.WordFactorization |
| 27 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments