3
$\begingroup$

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.

Improve this question
$\endgroup$
13
  • 5
    $\begingroup$ 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$? $\endgroup$
    – shane.orourke
    Commented Apr 20, 2021 at 9:41
  • 5
    $\begingroup$ For $n\ge 3$ there are infinitely many square-free words. See this (and references therein) : oeis.org/A006156. $\endgroup$
    – Alessandro Della Corte
    Commented Apr 20, 2021 at 9:42
  • 1
    $\begingroup$ 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$. $\endgroup$
    – shane.orourke
    Commented Apr 20, 2021 at 9:49
  • 1
    $\begingroup$ @Dattier See here $\endgroup$
    – Wojowu
    Commented Apr 20, 2021 at 10:12
  • 6
    $\begingroup$ 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.) $\endgroup$
    – Andreas Blass
    Commented Apr 20, 2021 at 18:35

1 Answer 1

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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 $\endgroup$
    – Yemon Choi
    Commented Apr 21, 2021 at 0:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .