The first published description of this object was given by Evgenii Lyapin in 1953. Alfred H. Clifford and Gordon Preston claim that one of them, working with David Rees, discovered it independently at some point before 1943.
Construction
There are at least three standard ways of constructing the bicyclic semigroup, and various notations for referring to it. Lyapin called it P; Clifford and Preston used ; and most recent papers have tended to use B. This article will use the modern style throughout.
The bicyclic semigroup is the free semigroup on two generators p and q, under the relation pq = 1. That is, each semigroup element is a string of those two letters, with the proviso that the subsequence "pq" does not appear. The semigroup operation is concatenation of strings, which is clearly associative. It can then be shown that all elements of B in fact have the form qapb, for some natural numbersa and b. The composition operation simplifies to
The way in which these exponents are constrained suggests that the "p and q structure" can be discarded, leaving only operations on the "a and b" part. So B is the semigroup of pairs of natural numbers, with operation This is sufficient to define B so that it is the same object as in the original construction. Just as p and q generated B originally, with the empty string as the monoid identity, this new construction of B has generators and, with identity.
From functions
It can be shown that any semigroup S generated by elements e, a, and b satisfying the statements below is isomorphic to the bicyclic semigroup.
ae = ea = a
be = eb = b
ab = e
ba ≠ e
It is not entirely obvious that this should be the case—perhaps the hardest task is understanding that S must be infinite. To see this, suppose that a does not have infinite order, so ak + h = ah for some h and k. Then ak = e, and so which is not allowed—so there are infinitely many distinct powers of a. The full proof is given in Clifford and Preston's book. Note that the two definitions given above both satisfy these properties. A third way of deriving B uses two appropriately-chosen functions to yield the bicyclic semigroup as a monoid of transformations of the natural numbers. Let α, β, and ι be elements of the transformation semigroup on the natural numbers, where
ι = n
α = n + 1
β = 0 if n = 0, and n − 1 otherwise.
These three functions have the required properties, so the semigroup they generate is B.
Properties
The bicyclic semigroup has the property that the image of any homomorphism φ from B to another semigroup S is either cyclic, or it is an isomorphic copy of B. The elements φ, φ and φ of S will always satisfy the conditions above with the possible exception that φ φ might turn out to be φ. If this is not true, then φ is isomorphic to B; otherwise, it is the cyclic semigroup generated by φ. In practice, this means that the bicyclic semigroup can be found in many different contexts. The idempotents of B are all pairs, where x is any natural number. Since these commute, and B is regular, the bicyclic semigroup is an inverse semigroup. Every ideal of B is principal: the left and right principal ideals of are
B = and
B =.
Each of these contains infinitely many others, so B does not have minimal left or right ideals. In terms of Green's relations, B has only one D-class, and hence has only one J-class. The L and R relations are given by
This implies that two elements are H-related if and only if they are identical. Consequently, the only subgroups of B are infinitely many copies of the trivial group, each corresponding to one of the idempotents. The egg-box diagram for B is infinitely large; the upper left corner begins: Each entry represents a singleton H-class; the rows are the R-classes and the columns are L-classes. The idempotents of B appear down the diagonal, in accordance with the fact that in a regular semigroup with commuting idempotents, each L-class and each R-class must contain exactly oneidempotent. The bicyclic semigroup is the "simplest" example of a bisimple inverse semigroup with identity; there are many others. Where the definition of B from ordered pairs used the class of natural numbers, another set with appropriate properties could appear instead, and the "+", "−" and "max" operations modified accordingly.