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:

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. ∎

The following result is immediate:

Corollary 1.

Any submonoid of a cyclic monoid is finitely generated.

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