2

This question is inspired by this one:

Can you do math without knowing how to count?

Let $M_2$ be the set of words constructed by concatenation of the letters $a_1$ and $a_2$, with :

(*) : for any $x$ word of $M_2$ $xx = x$.

Is it true $card(M_2)=card(\mathbb N) $?

If not, is it true $\exists n \in \mathbb N, card(M_n)=card(\mathbb N) $?

The condition (*) comes from the hypothesis that we assume that we do not know how to count.

YCor
  • 60,149
Dattier
  • 3,759
  • 1
  • 15
  • 40
  • Sorry, just to get your (*) condition: what you mean is that you identify also subwords? I mean: $abbc$ and $abc$ are the same word for every $a,b,c\in M_2$? – Alessandro Della Corte Apr 20 '21 at 09:36
  • Yes................ – Dattier Apr 20 '21 at 09:38
  • 5
    Doesn't it follow that the only six elements of $M_2$ are $a_1$, $a_2$, $a_1a_2$, $a_2a_1$, $a_2a_1a_2$ and $a_1a_2a_1$? – shane.orourke Apr 20 '21 at 09:41
  • 5
    For $n\ge 3$ there are infinitely many square-free words. See this (and references therein) : https://oeis.org/A006156. – Alessandro Della Corte Apr 20 '21 at 09:42
  • @shan why?. '... – Dattier Apr 20 '21 at 09:45
  • 1
    Take any element of $M_2$, write it using as few letters as possible using (*). If it has length $\geq 4$, its initial subword of length three must be one of the words I've listed above. But then there must be a reduction when one of these words is concatenated with a further $a_1$ or $a_2$: e.g. $(a_1a_2a_1)a_2=(a_1a_2)(a_1a_2)=a_1a_2$. – shane.orourke Apr 20 '21 at 09:49
  • Thanks. @A.DellaCorte Is there an algorithm to enumerate an infinity set of distincts ternary words square free? – Dattier Apr 20 '21 at 10:00
  • 1
    @Dattier See here – Wojowu Apr 20 '21 at 10:12
  • Thanks. Well, even if we don't know how to count, we can have an infinite number of symbols. – Dattier Apr 20 '21 at 10:20
  • 1
    This flavour of problem (at least more general forms) seems to be a restricted version of the Burnside problem for semigroups. – Carl-Fredrik Nyberg Brodda Apr 20 '21 at 11:45
  • 1
    There are uncountably many squarefree ternary words (of infinite length) $x_1 x_2 \cdots$. In fact, let $w=x_1x_2\cdots$ be a word in the four symbols $0,1,2,$, such that no matter how we replace each $$ with either 0, 1, or 2, a squarefree word results. Then the maximum possible density of the $*$'s is exactly $3/16$. See https://www.worldscientific.com/doi/abs/10.1142/S0129054118420078. – Richard Stanley Apr 20 '21 at 13:52
  • 6
    Perhaps surprisingly, even though there are infinitely many square-free words on three letters, the assumption that $xx=x$ for all words $x$ still reduces them to finitely many. I don't have the reference handy, but here's an example of what's involved. $abcbabc=abcbabcbc=abcbc=abc$ even though both $abcbabc$ and $abc$ are square-free. (In fancy language:The variety of idempotent semigroups is locally finite.) – Andreas Blass Apr 20 '21 at 18:35
  • @AndreasBlass What about the second question? Can you give a justification? – Dattier Apr 20 '21 at 20:00

1 Answers1

10

I'm upgrading my comment to an answer, because I've found the source for the result asserted in the comment: For every $n$, the semigroup $M_n$, presented by $n$ generators subject to the relations $xx=x$ for all words $x$, is finite. The reference is

Green, J. A.; Rees, D. On semi-groups in which x^r=x. Proc. Cambridge Philos. Soc. 48 (1952), 35–40,

and its Mathematical Reviews number is MR0046353.

LSpice
  • 11,423
Andreas Blass
  • 72,290
  • 1
    Note for other readers: semigroups in which every element is idempotent are often called bands. A proof of this result of Green and Rees, along with some of the other basic theory of bands, can be found in Howie's Introduction To Semigroup Theory – Yemon Choi Apr 21 '21 at 00:08