In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the bicyclic semigroup is an algebraic object important for the structure theory of
semigroup
In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it.
The binary operation of a semigroup is most often denoted multiplicatively: ''x''·''y'', or simply ''xy'', ...
s. Although it is in fact a
monoid
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.
Monoids ...
, it is usually referred to as simply a semigroup. It is perhaps most easily understood as the
syntactic monoid In mathematics and computer science, the syntactic monoid M(L) of a formal language L is the smallest monoid that recognizes the language L.
Syntactic quotient
The free monoid on a given set is the monoid whose elements are all the strings of zero ...
describing the
Dyck language
In the theory of formal languages of computer science, mathematics, and linguistics, a Dyck word is a balanced string of square brackets and The set of Dyck words forms the Dyck language.
Dyck words and language are named after the mathematici ...
of balanced pairs of parentheses. Thus, it finds common applications in
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...
, such as describing
binary tree
In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary t ...
s and
associative algebra
In mathematics, an associative algebra ''A'' is an algebraic structure with compatible operations of addition, multiplication (assumed to be associative), and a scalar multiplication by elements in some field ''K''. The addition and multiplic ...
s.
History
The first published description of this object was given by
Evgenii Lyapin in 1953.
Alfred H. Clifford
Alfred Hoblitzelle Clifford (July 11, 1908 – December 27, 1992) was an American mathematician born in St. Louis, Missouri who is known for Clifford theory and for his work on semigroups. He did his undergraduate studies at Yale and his PhD at ...
and
Gordon Preston claim that one of them, working with
David Rees David or Dai Rees may refer to:
Entertainment
* David Rees (author) (1936–1993), British children's author
* Dave Rees (born 1969), American drummer for SNFU and Wheat Chiefs
* David Rees (cartoonist) (born 1972), American cartoonist and televis ...
, 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
; 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 In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero eleme ...
on two generators ''p'' and ''q'' by the
congruence generated by the relation ''p'' ''q'' = 1. Thus, 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
In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement f ...
.
It can then be shown that all elements of ''B'' in fact have the form ''q''
''a'' ''p''
''b'', for some
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
s ''a'' and ''b''. The composition operation simplifies to
: (''q''
''a'' ''p''
''b'') (''q''
''c'' ''p''
''d'') = ''q''
''a'' + ''c'' − min ''p''
''d'' + ''b'' − min.
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
:(''a'', ''b'') (''c'', ''d'') = (''a'' + ''c'' − min, ''d'' + ''b'' − min).
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
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
to the bicyclic semigroup.
* ''a'' ''e'' = ''e'' ''a'' = ''a''
* ''b'' ''e'' = ''e'' ''b'' = ''b''
* ''a'' ''b'' = ''e''
* ''b'' ''a'' ≠ ''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'' = ''e'' ''b'' = ''a''
''k'' ''b'' = ''a''
''k'' - 1 ''e'' = ''a''
''k'' - 1,
so
:''b'' ''a'' = ''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 In algebra, a transformation semigroup (or composition semigroup) is a collection of transformations ( functions from a set to itself) that is closed under function composition. If it includes the identity function, it is a monoid, called a transf ...
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''.
Properties
The bicyclic semigroup has the property that the image of any
homomorphism
In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type (such as two groups, two rings, or two vector spaces). The word ''homomorphism'' comes from the Ancient Greek language: () meaning "same" ...
φ from ''B'' to another semigroup ''S'' is either
cyclic
Cycle, cycles, or cyclic may refer to:
Anthropology and social sciences
* Cyclic history, a theory of history
* Cyclical theory, a theory of American political history associated with Arthur Schlesinger, Sr.
* Social cycle, various cycles in s ...
, 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
idempotent
Idempotence (, ) is the property of certain operation (mathematics), operations in mathematics and computer science whereby they can be applied multiple times without changing the result beyond the initial application. The concept of idempotence ...
s 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 ''x'' ''y'' ''x'' = ''x''), the bicyclic semigroup is an
inverse semigroup In group theory, an inverse semigroup (occasionally called an inversion semigroup) ''S'' is a semigroup in which every element ''x'' in ''S'' has a unique ''inverse'' ''y'' in ''S'' in the sense that ''x = xyx'' and ''y = yxy'', i.e. a regular semig ...
. (This means that each element ''x'' of ''B'' has a unique inverse ''y'', in the "weak" semigroup sense that ''x'' ''y'' ''x'' = ''x'' and ''y'' ''x'' ''y'' = ''y''.)
Every
ideal
Ideal may refer to:
Philosophy
* Ideal (ethics), values that one actively pursues as goals
* Platonic ideal, a philosophical idea of trueness of form, associated with Plato
Mathematics
* Ideal (ring theory), special subsets of a ring considere ...
of ''B'' is principal: the left and right principal ideals of (''m'', ''n'') are
* (''m'', ''n'') ''B'' = and
* ''B'' (''m'', ''n'') = .
Each of these contains infinitely many others, so ''B'' does not have minimal left or right ideals.
In terms of
Green's relations 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. ...
, ''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
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bicondi ...
''a'' = ''c''; and
* (''a'', ''b'') ''L'' (''c'', ''d'') if and only if ''b'' = ''d''.
[Howie p.60]
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 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
Lattice may refer to:
Arts and design
* Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material
* Lattice (music), an organized grid model of pitch ratios
* Lattice (pastry), an orna ...
under min and max operations), another set with appropriate properties could appear instead, and the "+", "−" and "max" operations modified accordingly.
See also
*
Four-spiral semigroup 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 seve ...
*
Special classes of semigroups
In mathematics, a semigroup is a nonempty set together with an associative binary operation. A special class of semigroups is a class of semigroups satisfying additional properties or conditions. Thus the class of commutative semigroups consists o ...
Notes
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
ussian
* {{cite journal , last1=Hollings , first1=C.D. , year=2007 , title=Some First Tantalizing Steps into Semigroup Theory , journal=Mathematics Magazine , volume=80 , pages=331–344 , publisher=Mathematical Association of America , jstor=27643058
Semigroup theory