Let $S$ be a finite noncommutative semigroup(without identity) with a subset $M$ such that $\langle M \rangle =S$. If every element of $M$ is indecomposable in $M$, i.e. for any $a \in M$, there are not elements $b,c \in M\backslash \{ a\}$ such that $a=bc$. Could we get $\operatorname{rank}(S)=\lvert M\rvert$? Here the rank of a semigroup means the minimal cardinality of a generating subset.

$\begingroup$ Is your monoid commutative? Must M generate S? In any event in the free monoid on a,b the set $M$ of elements of the form $a^ib$ with i>0 is indecomposable and freely generates a free monoid of countable rank but the rank of the ambient monoId is 2. so you should clarify. I presume you want M to generate. $\endgroup$ – Benjamin Steinberg May 17 '20 at 1:53

$\begingroup$ @Benjamin Steinberg Thank you for your counterexample. Acutally, I need that $S$ is a finite semigroup and $M$ generates $S$. I have reedited my question. $\endgroup$ – Li Debiao May 17 '20 at 3:19

3$\begingroup$ Does "could we get" mean "is it possible" (i.e., does it sometimes happen) or "is it necessary" (i.e., does it always happen)? I guess the latter, but it may be a good idea to reword. $\endgroup$ – LSpice May 17 '20 at 3:42

1$\begingroup$ I see the question now excludes an identity. So in by íntegers mod 10 example adjoin an absorbing element z and a new element x which multiplies all other elements to zero in either side. Then 5,6,x is an indecomposable generating set and the rank is 2 $\endgroup$ – Benjamin Steinberg May 17 '20 at 12:43

1$\begingroup$ My example with the absorbing element has no identity. x multiplied by an element is the absorbing element, which I would not have called zero to avoid confusion with the zero in Z/10. $\endgroup$ – Benjamin Steinberg May 17 '20 at 13:11
Take the semigroup with presentation
$\langle x,y,a\mid a^7=a,xy=x=x^2,yx=y=y^2,xa=ax=ay=ya=xa^2=a^2x\rangle$.
It has 9 elements, is noncommutative and has no identity. Clearly it has rank 3. But $a^3,a^4,x,y$ is an indecomposable generating set. So the answer is no. Also notice my generating set is minimal with respect to inclusion which is stronger than what you ask.
This is the disjoint union of a cyclic group of order 6 and a 2element left zero semigroup and an absorbing element such that the above two semigroups have all products the absorbing element. The presentation describes a free product of the 6 element cyclic group generated by $a$ with the two element left zero semigroup consisting of $x,y$ modulo the ideal of all words of syllable length 2 or more in free product normal form (taking some short cuts to remove redundant relations).

$\begingroup$ I modified to make noncommutative $\endgroup$ – Benjamin Steinberg May 17 '20 at 13:52


$\begingroup$ While I'm sure you're right about all these facts, I don't know how to prove them! (Equalities in a presented semigroup should be comparatively easy, but it seems to me that proving inequalities is likely to be tough.) Is there some algorithm that verifies, for example, that the 9 elements are distinct, or is it just clever but familiartoanexpert proofs? $\endgroup$ – LSpice May 17 '20 at 14:31

1$\begingroup$ @LSpice, It is pretty easy. There is an obvious map to the semigroup I described taking a to the generator of the cyclic group of order 6 and x,y to the two left zeroes and ask the guys in the big equality to the absorbing element. So there are at most 9 elements. But it is easy to check the long list of equalities at the end make $ax$ an absorbing element of $a,x,y$ using $x,y$ are idempotent. $\endgroup$ – Benjamin Steinberg May 17 '20 at 14:52

1$\begingroup$ @LSpice alternatively you can see this as the presentation of the free product of the two semigroups above (a cyclic group of order 6 and a two element left zero semigroup) by the congruence identifying all element of syllable length at least two (which is obviously an ideal). Then I took some short cuts to remove redundant relations since once you know for example xaa=xa there is know need to do xaaa=xa. Actually my relation xaxa=xa is redundant since xaxa=xxaa=xaa=xa so I will remove it. $\endgroup$ – Benjamin Steinberg May 17 '20 at 15:06