Recent searches
Search options
Here @buster demonstrates a somewhat surprising fact.
Take 3 variables a,b,c and start multiplying them. Suppose multiplication is associative and 𝑥² = 𝑥, where 𝑥 is anything you build up from these letters.
Since 𝑥² = 𝑥, you can simplify the stuff you get by removing repetitions, e.g.
abcbca
simplifies to
abca
But there is not a unique way to simplify an expression as much as possible!
bacbcabc
and
bacbabc
are both as simplified as they can get... but they're equal!
(1/2)
In math jargon, we say the process of simplifying words by removing repetitions is
'terminating' (since it always stops) but not 'confluent' (since it doesn't always stop at the same place: the final result depends on your choices).
This example comes from page 31 here:
• Jean Berstel and Christophe Reuteneur, Square-free words and idempotent semigroups, in Combinatorics on Words, ed. M. Lothaire, Addison-Wesley, Reading, Massachusetts, 1983. Available at http://www.math.ucla.edu/~pak/hidden/Courses/Lothaire-Ch2.pdf
(2/2)
@johncarlosbaez It reminds me a bit of the algebraic integer rings that don't have unique prime factorization.
Only... the other way around, in a sense.
@mattmcirvin - it's the explanation of this seeming 'paradox': there are infinitely many square-free words on 3 letters, but the free idempotent monoid on 3 generators has just finitely many elements: 160 in fact.
@mattmcirvin @johncarlosbaez yep! The "divisibility" relation is well-founded on noetherian rings!
@mattmcirvin @johncarlosbaez "noetherian" is sometimes used as a synonym for "well-founded" for this reason!