# 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 $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,\ldots\}$. Let $T$ be a subsemigroup of $S$. Since $S$ is well-ordered, so is $T$. Take the least element $p_{1}$ of $T$. If $\langle p_{1}\rangle=T$, then we are done. Otherwise, $T-\langle p_{1}\rangle$ is non-empty, and thus has a least element $p_{2}$. So by the Euclidean algorithm, $p_{2}=q_{1}p_{1}+r_{1}$, where $0. If $\langle p_{1},p_{2}\rangle=T$, then we are done. Otherwise, continue this process. Along the way, we collect the quotients $\{q_{1},q_{2},\ldots\}$, as well as the remainders $\{r_{1},r_{2},\ldots\}$. We make the following observations:

1. 1.

Since $p_{1}, the quotients are non-decreasing: $q_{1}\leq q_{2}\leq\cdots$. For if $q_{j+1}, then

 $p_{j+2}=q_{j+1}p_{1}+r_{j+1}

2. 2.

Elements of $\{r_{1},r_{2},\ldots\}$ are pairwise distinct, for if $r_{i}=r_{j}$ for $i, 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}\leq 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},\ldots\}$ of remainders can not be infinite. Suppose the set has $k$ elements. Then we must have $\langle p_{1},p_{2},\ldots,p_{k+1}\rangle=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},\ldots,r_{k}$. But by the second observation, this means that $p_{k+2}\in\langle p_{1},p_{2},\ldots,p_{k+1}\rangle$ 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 $\langle a\rangle=\{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 SubsemigroupOfACyclicSemigroup 2013-03-22 19:01:48 2013-03-22 19:01:48 CWoo (3771) CWoo (3771) 6 CWoo (3771) Result msc 20M99