Bicyclic semigroup

Last updated December 20, 2022

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.

History

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.

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 ${\mathcal {C}}$ ; and most recent papers have tended to use B. This article will use the modern style throughout.

From a free semigroup

The bicyclic semigroup is the quotient of the free monoid on two generators p and q by the congruence generated by the relation pq = 1. Thus, 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 q^ap^b, for some natural numbers a and b. The composition operation simplifies to

(q^ap^b) (q^cp^d) = q^{a + c− min{b, c}}p^{d + b− min{b, c}}.

From ordered pairs

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^[1]

(a, b) (c, d) = (a + c− min{b, c}, d + b− min{b, c}).

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

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 (say) does not have infinite order, so a^{k + h} = a^h for some h and k. Then a^k = e, and

b = eb = a^kb = a^{k - 1}e = a^{k - 1},

so

ba = a^k = e,

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
α(n) = n + 1
β(n) = 0 if n = 0, and n− 1 otherwise.

These three functions have the required properties, so the semigroup they generate is B.^[2]

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 φ(a), φ(b) and φ(e) of S will always satisfy the conditions above (because φ is a homomorphism) with the possible exception that φ(b) φ(a) might turn out to be φ(e). If this is not true, then φ(B) is isomorphic to B; otherwise, it is the cyclic semigroup generated by φ(a). In practice, this means that the bicyclic semigroup can be found in many different contexts.

The idempotents of B are all pairs (x, x), where x is any natural number (using the ordered pair characterisation of B). Since these commute, and B is regular (for every x there is a y such that xyx = x), the bicyclic semigroup is an inverse semigroup. (This means that each element x of B has a unique inverse y, in the "weak" semigroup sense that xyx = x and yxy = y.)

Every ideal of B is principal: the left and right principal ideals of (m, n) are

(m, n) B = {(s, t) : s ≥ m} and
B (m, n) = {(s, t) : t ≥ n}.

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 (it is bisimple), and hence has only one J-class (it is simple). The L and R relations are given by

(a, b) R (c, d) if and only if a = c; and
(a, b) L (c, d) if and only if b = d.^[3]

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:

(0, 0)	(1, 0)	(2, 0)	...
(0, 1)	(1, 1)	(2, 1)	...
(0, 2)	(1, 2)	(2, 2)	...
...	...	...	...

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 one idempotent.

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 (which is not only an additive semigroup, but also a commutative lattice under min and max operations), another set with appropriate properties could appear instead, and the "+", "−" and "max" operations modified accordingly.

Notes

↑ Hollings (2007), p. 332
↑ Lothaire, M. (2011). Algebraic combinatorics on words. Encyclopedia of Mathematics and Its Applications. Vol. 90. With preface by Jean Berstel and Dominique Perrin (Reprint of the 2002 hardback ed.). Cambridge University Press. p. 459. ISBN 978-0-521-18071-9. Zbl 1221.68183.
↑ Howie p.60

Related Research Articles

In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0.

In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it.

<span class="mw-page-title-main">Generating set of a group</span> Abstract algebra concept

In abstract algebra, a generating set of a group is a subset of the group set such that every element of the group can be expressed as a combination of finitely many elements of the subset and their inverses.

In abstract algebra, a magma, binar, or, rarely, groupoid is a basic kind of algebraic structure. Specifically, a magma consists of a set equipped with a single binary operation that must be closed by definition. No other properties are imposed.

In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero elements, often called the empty string and denoted by ε or λ, as the identity element. The free monoid on a set A is usually denoted A^∗. The free semigroup on A is the subsemigroup of A^∗ containing all elements except the empty string. It is usually denoted A⁺.

In algebra and theoretical computer science, an action or act of a semigroup on a set is a rule which associates to each element of the semigroup a transformation of the set in such a way that the product of two elements of the semigroup is associated with the composite of the two corresponding transformations. The terminology conveys the idea that the elements of the semigroup are acting as transformations of the set. From an algebraic perspective, a semigroup action is a generalization of the notion of a group action in group theory. From the computer science point of view, semigroup actions are closely related to automata: the set models the state of the automaton and the action models transformations of that state in response to inputs.

In mathematics, Green's relations are five equivalence relations that characterise the elements of a semigroup in terms of the principal ideals they generate. The relations are named for James Alexander Green, who introduced them in a paper of 1951. John Mackintosh Howie, a prominent semigroup theorist, described this work as "so all-pervading that, on encountering a new semigroup, almost the first question one asks is 'What are the Green relations like?'". The relations are useful for understanding the nature of divisibility in a semigroup; they are also valid for groups, but in this case tell us nothing useful, because groups always have divisibility.

In mathematics, the Grothendieck group, or group of differences, of a commutative monoid $M$ is a certain abelian group. This abelian group is constructed from $M$ in the most universal way, in the sense that any abelian group containing a homomorphic image of $M$ will also contain a homomorphic image of the Grothendieck group of $M$ . The Grothendieck group construction takes its name from a specific case in category theory, introduced by Alexander Grothendieck in his proof of the Grothendieck–Riemann–Roch theorem, which resulted in the development of K-theory. This specific case is the monoid of isomorphism classes of objects of an abelian category, with the direct sum as its operation.

In group theory, an inverse semigroupS is a semigroup in which every element x in S has a unique inversey in S in the sense that x = xyx and y = yxy, i.e. a regular semigroup in which every element has a unique inverse. Inverse semigroups appear in a range of contexts; for example, they can be employed in the study of partial symmetries.

In algebra, a presentation of a monoid is a description of a monoid in terms of a set $Σ$ of generators and a set of relations on the free monoid $Σ *$ generated by $Σ$ . The monoid is then presented as the quotient of the free monoid by these relations. This is an analogue of a group presentation in group theory.

In mathematics, a regular semigroup is a semigroup S in which every element is regular, i.e., for each element a in S there exists an element x in S such that axa = a. Regular semigroups are one of the most-studied classes of semigroups, and their structure is particularly amenable to study via Green's relations.

In mathematics, a monogenic semigroup is a semigroup generated by a single element. Monogenic semigroups are also called cyclic semigroups.

In algebra, a transformation semigroup is a collection of transformations that is closed under function composition. If it includes the identity function, it is a monoid, called a transformationmonoid. This is the semigroup analogue of a permutation group.

In mathematics, particularly in abstract algebra, a semigroup with involution or a *-semigroup is a semigroup equipped with an involutive anti-automorphism, which—roughly speaking—brings it closer to a group because this involution, considered as unary operator, exhibits certain fundamental properties of the operation of taking the inverse in a group: uniqueness, double application "cancelling itself out", and the same interaction law with the binary operation as in the case of the group inverse. It is thus not a surprise that any group is a semigroup with involution. However, there are significant natural examples of semigroups with involution that are not groups.

In mathematics, a null semigroup is a semigroup with an absorbing element, called zero, in which the product of any two elements is zero. If every element of a semigroup is a left zero then the semigroup is called a left zero semigroup; a right zero semigroup is defined analogously. According to Clifford and Preston, "In spite of their triviality, these semigroups arise naturally in a number of investigations."

In abstract algebra, in semigroup theory, a Schutzenberger group is a certain group associated with a Green H-class of a semigroup. The Schutzenberger groups associated with different H-classes are different. However, the groups associated with two different H-classes contained in the same D-class of a semigroup are isomorphic. Moreover, if the H-class itself were a group, the Schutzenberger group of the H-class would be isomorphic to the H-class. In fact, there are two Schutzenberger groups associated with a given H-class and each is antiisomorphic to the other.

In mathematics, the four-spiral semigroup is a special semigroup generated by four idempotent elements. This special semigroup was first studied by Karl Byleen in a doctoral dissertation submitted to the University of Nebraska in 1977. It has several interesting properties: it is one of the most important examples of bi-simple but not completely-simple semigroups; it is also an important example of a fundamental regular semigroup; it is an indispensable building block of bisimple, idempotent-generated regular semigroups. A certain semigroup, called double four-spiral semigroup, generated by five idempotent elements has also been studied along with the four-spiral semigroup.

In mathematics, more precisely in formal language theory, the profinite words are a generalization of the notion of finite words into a complete topological space. This notion allows the use of topology to study languages and finite semigroups. For example, profinite words are used to give an alternative characterization of the algebraic notion of a variety of finite semigroups.

In mathematics, and more precisely in semigroup theory, a variety of finite semigroups is a class of semigroups having some nice algebraic properties. Those classes can be defined in two distinct ways, using either algebraic notions or topological notions. Varieties of finite monoids, varieties of finite ordered semigroups and varieties of finite ordered monoids are defined similarly.

In mathematics, and more precisely in semigroup theory, a nilsemigroup or nilpotent semigroup is a semigroup whose every element is nilpotent.

References

The algebraic theory of semigroups, A. H. Clifford and G. B. Preston. American Mathematical Society, 1961 (volume 1), 1967 (volume 2).
Semigroups: an introduction to the structure theory, Pierre Antoine Grillet. Marcel Dekker, Inc., 1995.
Canonical form of elements of an associative system given by defining relations, Evgenii Sergeevich Lyapin, Leningrad Gos. Ped. Inst. Uch. Zap.89 (1953), pages 45–54 [Russian].
Hollings, C.D. (2007). "Some First Tantalizing Steps into Semigroup Theory". Mathematics Magazine. Mathematical Association of America. 80: 331–344. JSTOR 27643058.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Hollings (2007), p. 332

[Lot459-2] Lothaire, M. (2011). Algebraic combinatorics on words. Encyclopedia of Mathematics and Its Applications. Vol. 90. With preface by Jean Berstel and Dominique Perrin (Reprint of the 2002 hardback ed.). Cambridge University Press. p. 459. ISBN 978-0-521-18071-9. Zbl 1221.68183.

[3] Howie p.60

[1]

[2]

[3]