subsemigroup of a cyclic semigroup

It is a well-known fact that the subgroupMathworldPlanetmathPlanetmath of a cyclic groupMathworldPlanetmath is cyclic. Is this true for semigroups? The answer is clearly no. For example, take the cyclic semigroup of positive integers under additionPlanetmathPlanetmath, and the subsemigroup generated by, say, 7 and 17. If it were cyclic, generated by some positive integer n, then n must divide both 7 and 17, which implies that n=1. But there are no positive integers p and q such that 1=7p+17q, and the result follows. However, the following does hold:

Proposition 1.

Every subsemigroup of a cyclic semigroup is finitely generatedMathworldPlanetmath.


Let S be a cyclic semigroup. The result is obvious if S is finite. So assume that S is infiniteMathworldPlanetmath. Since every infinite cyclic semigroup is isomorphicPlanetmathPlanetmathPlanetmath to the semigroup of positive integers under addition, we may as well assume that S={1,2,}. Let T be a subsemigroup of S. Since S is well-ordered, so is T. Take the least element p1 of T. If p1=T, then we are done. Otherwise, T-p1 is non-empty, and thus has a least element p2. So by the Euclidean algorithmMathworldPlanetmath, p2=q1p1+r1, where 0<r1<p1. If p1,p2=T, then we are done. Otherwise, continue this process. Along the way, we collect the quotientsPlanetmathPlanetmath {q1,q2,}, as well as the remainders {r1,r2,}. We make the following observations:

  1. 1.

    Since p1<p2<, the quotients are non-decreasing: q1q2. For if qj+1<qj, then


    which is a contradictionMathworldPlanetmathPlanetmath.

  2. 2.

    Elements of {r1,r2,} are pairwise distinct, for if ri=rj for i<j, then


    Since qiqj by the first observation, pj+1 lies in the subsemigroup generated by pi+1 and p1, contradicting the construction of pj+1.

Since the remainders are integers between 0 and p1, the set {r1,r2,} of remainders can not be infinite. Suppose the set has k elements. Then we must have p1,p2,,pk+1=T. Otherwise, we may continue the process and find pk+2,qk+1, and rk+1. This means that rk+1 is among one of r1,,rk. But by the second observation, this means that pk+2p1,p2,,pk+1 after all. ∎

In fact, the above proof shows that there is an algorithmMathworldPlanetmath for finding a finite setMathworldPlanetmath of generatorsPlanetmathPlanetmathPlanetmath for the subsemigroup T.

The following result is immediate:

Corollary 1.

Any submonoid of a cyclic monoid is finitely generated.

As an application to formal languageMathworldPlanetmath theory, we have the following:

Corollary 2.

The Kleene star of any languagePlanetmathPlanetmath over a singleton alphabet is regularPlanetmathPlanetmath (


The Kleene star of a language L over {a} is just a submonoid of the cyclic monoid a={a}*, and hence is generated by some finite set F by the propositionPlanetmathPlanetmath above. Since every finite set is regular, so is F*=L*. ∎


  • 1 A. Salomaa, Formal Languages, Academic Press, New York (1973).
Title subsemigroup of a cyclic semigroup
Canonical name SubsemigroupOfACyclicSemigroup
Date of creation 2013-03-22 19:01:48
Last modified on 2013-03-22 19:01:48
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 6
Author CWoo (3771)
Entry type Result
Classification msc 20M99