Bicyclic semigroup

In mathematics, the bicyclic semigroup is an algebraic object important for the structure theory of semigroups. Although it is in fact a monoid, it is usually referred to as simply a semigroup. It is perhaps most easily understood as the syntactic monoid describing the Dyck language of balanced pairs of parentheses. Thus, it finds common applications in combinatorics, such as describing binary trees and associative algebras. In mathematics, the bicyclic semigroup is an algebraic object important for the structure theory of semigroups. Although it is in fact a monoid, it is usually referred to as simply a semigroup. It is perhaps most easily understood as the syntactic monoid describing the Dyck language of balanced pairs of parentheses. Thus, it finds common applications in combinatorics, such as describing binary trees and associative algebras. 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 (without publication) at some point before 1943. 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 C {displaystyle {mathcal {C}}} ; 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 p q = 1. That is, each semigroup element is a string of those two letters, with the proviso that the subsequence 'p q' 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 qa pb, for some natural numbers a 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 (including zero), 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 (1, 0) and (0, 1), with identity (0, 0). 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. 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 (say) does not have infinite order, so ak + h = ah for some h and k. Then ak = e, and