Subsemigroups of the bicyclic monoid

Luis Descalço

Universidade de Aveiro, Portugal

Introduction

The bicyclic monoid is one of the most fundamental semigroups. It is one of the main ingredients in the Bruck-Reilly extensions (see [8]), and also the basis of several generalizations; see [1,2,6,7]. In [9, Sec 3.4] references are given to a number of applications of the bicyclic monoid to topics outside semigroup theory. The bicyclic monoid is known to have several remarkable properties, one of which is that it is completely determined by its lattice of subsemigroups; see [11] and [12]. Also, in [10] the authors study properties of a specific subsemigroup of B. Slightly surprisingly, there seems to be little other work in literature regarding the subsemigroups of B. We give a description of all subsemigroups of B and then we use it to prove several properties of the subsemigroups.

Description of the subsemigroups

The bicyclic monoid B, is defined by the monoid presentation $\langle b,c\ \vert\ bc=1 \rangle$. A natural set of unique normal forms for B is $\{c^i b^j: i,j \ge 0\}$ and we identify B with this set. The normal forms multiply according to the following rule:

$$c^i b^j c^k b^l = \left\{ \begin{array}{ll} c^{i-j+k} b^l ... ...e k \\ c^i b^{j-k+l} \mbox{ if } j > k. \end{array} \right.$$

We show that there are essentially five different types of subsemigroups. One of them is the degenerate case of subsets of $\{c^i b^i: i \ge 0\}$, and the remaining four split in two groups of two, linked by the obvious anti-isomorphism $\ \widehat {}\ : c^i b^j \mapsto c^j b^i$ of B. Each subsemigroup is characterized by a certain collection of parameters. The description can be easily explained with pictures on the egg-box of unique regular $\mbox{$\mathcal{D}$}$-class of B.

Corollaries

Using our description we determine which are the regular, simple and bisimple subsemigroups of B. If we call special a subsemigroup $M$ of $\mathbb{N}_0$ $M$ of the from $M = \{n: n \ge k\}$ for some $k$ we have:


Theorem. A subsemigroup of B is:

1. Regular if and only if it is obtained by adjoining successively finitely many identities to a finite union of copies of B.
2. Simple if and only if it is a finite union of copies of B and special subsemigroups of $\mathbb{N}_0$.
3. Bisimple if and only if it is isomorphic to B.

Computation of parameters

We will briefly present algorithms to compute the parameters appearing in our description, given a finite generating set for the subsemigroup. The description of the subsemigroups, corollaries and computation of the parameters can be found in [5].

Properties of the subsemigroups

We will give necessary and sufficient conditions for a subsemigroup of B to be finitely generated. Then we show that all finitely generated subsemigroups of B are automatic and finitely presented. Finally we determine the residually finite subsemigroups of B. These proofs will be in [4]. All proofs, several examples and an implementation of the algorithms in GAP, can be found in [3].