subsemigroup of a cyclic semigroup
It is a well-known fact that the subgroup of a cyclic group is cyclic. Is this true for semigroups? The answer is clearly no. For example, take the cyclic semigroup of positive integers under addition, and the subsemigroup generated by, say, 7 and 17. If it were cyclic, generated by some positive integer , then must divide both 7 and 17, which implies that . But there are no positive integers and such that , and the result follows. However, the following does hold:
Every subsemigroup of a cyclic semigroup is finitely generated.
Let be a cyclic semigroup. The result is obvious if is finite. So assume that is infinite. Since every infinite cyclic semigroup is isomorphic to the semigroup of positive integers under addition, we may as well assume that . Let be a subsemigroup of . Since is well-ordered, so is . Take the least element of . If , then we are done. Otherwise, is non-empty, and thus has a least element . So by the Euclidean algorithm, , where . If , then we are done. Otherwise, continue this process. Along the way, we collect the quotients , as well as the remainders . We make the following observations:
Since , the quotients are non-decreasing: . For if , then
which is a contradiction.
Elements of are pairwise distinct, for if for , then
Since by the first observation, lies in the subsemigroup generated by and , contradicting the construction of .
Since the remainders are integers between and , the set of remainders can not be infinite. Suppose the set has elements. Then we must have . Otherwise, we may continue the process and find , and . This means that is among one of . But by the second observation, this means that after all. ∎
The following result is immediate:
Any submonoid of a cyclic monoid is finitely generated.
As an application to formal language theory, we have the following:
The Kleene star of a language over is just a submonoid of the cyclic monoid , and hence is generated by some finite set by the proposition above. Since every finite set is regular, so is . ∎
- 1 A. Salomaa, Formal Languages, Academic Press, New York (1973).
|Title||subsemigroup of a cyclic semigroup|
|Date of creation||2013-03-22 19:01:48|
|Last modified on||2013-03-22 19:01:48|
|Last modified by||CWoo (3771)|