subsemigroup of a cyclic semigroup
It is a wellknown 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 $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 generated^{}.
Proof.
Let $S$ be a cyclic semigroup. The result is obvious if $S$ is finite. So assume that $S$ is infinite^{}. Since every infinite cyclic semigroup is isomorphic^{} to the semigroup of positive integers under addition, we may as well assume that $S=\{1,2,\mathrm{\dots}\}$. Let $T$ be a subsemigroup of $S$. Since $S$ is wellordered, so is $T$. Take the least element ${p}_{1}$ of $T$. If $\u27e8{p}_{1}\u27e9=T$, then we are done. Otherwise, $T\u27e8{p}_{1}\u27e9$ is nonempty, and thus has a least element ${p}_{2}$. So by the Euclidean algorithm^{}, ${p}_{2}={q}_{1}{p}_{1}+{r}_{1}$, where $$. If $\u27e8{p}_{1},{p}_{2}\u27e9=T$, then we are done. Otherwise, continue this process. Along the way, we collect the quotients^{} $\{{q}_{1},{q}_{2},\mathrm{\dots}\}$, as well as the remainders $\{{r}_{1},{r}_{2},\mathrm{\dots}\}$. We make the following observations:

1.
Since $$, the quotients are nondecreasing: ${q}_{1}\le {q}_{2}\le \mathrm{\cdots}$. For if $$, then
$$ which is a contradiction^{}.

2.
Elements of $\{{r}_{1},{r}_{2},\mathrm{\dots}\}$ are pairwise distinct, for if ${r}_{i}={r}_{j}$ for $$, then
$${p}_{j+1}={q}_{j}{p}_{1}+{r}_{j}={q}_{j}{p}_{1}+{r}_{i}=({q}_{i}{p}_{1}+{r}_{i})+({q}_{j}{q}_{i}){p}_{1}={p}_{i+1}+({q}_{j}{q}_{i}){p}_{1}.$$ Since ${q}_{i}\le {q}_{j}$ by the first observation, ${p}_{j+1}$ lies in the subsemigroup generated by ${p}_{i+1}$ and ${p}_{1}$, contradicting the construction of ${p}_{j+1}$.
Since the remainders are integers between $0$ and ${p}_{1}$, the set $\{{r}_{1},{r}_{2},\mathrm{\dots}\}$ of remainders can not be infinite. Suppose the set has $k$ elements. Then we must have $\u27e8{p}_{1},{p}_{2},\mathrm{\dots},{p}_{k+1}\u27e9=T$. Otherwise, we may continue the process and find ${p}_{k+2},{q}_{k+1}$, and ${r}_{k+1}$. This means that ${r}_{k+1}$ is among one of ${r}_{1},\mathrm{\dots},{r}_{k}$. But by the second observation, this means that ${p}_{k+2}\in \u27e8{p}_{1},{p}_{2},\mathrm{\dots},{p}_{k+1}\u27e9$ after all. ∎
In fact, the above proof shows that there is an algorithm^{} for finding a finite set^{} of generators^{} 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 language^{} theory, we have the following:
Corollary 2.
The Kleene star of any language^{} over a singleton alphabet is regular^{} (http://planetmath.org/RegularLanguage).
Proof.
The Kleene star of a language $L$ over $\{a\}$ is just a submonoid of the cyclic monoid $\u27e8a\u27e9={\{a\}}^{*}$, and hence is generated by some finite set $F$ by the proposition^{} above. Since every finite set is regular, so is ${F}^{*}={L}^{*}$. ∎
References
 1 A. Salomaa, Formal Languages, Academic Press, New York (1973).
Title  subsemigroup of a cyclic semigroup 

Canonical name  SubsemigroupOfACyclicSemigroup 
Date of creation  20130322 19:01:48 
Last modified on  20130322 19:01:48 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  6 
Author  CWoo (3771) 
Entry type  Result 
Classification  msc 20M99 