In
algebra
Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics.
Elementary a ...
, a presentation of a monoid (or a presentation of a semigroup) is a description of 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 ...
(or a
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'', ...
) in terms of a set of generators and a set of relations on 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 ...
(or the free semigroup ) generated by . The monoid is then presented as the
quotient
In arithmetic, a quotient (from lat, quotiens 'how many times', pronounced ) is a quantity produced by the division of two numbers. The quotient has widespread use throughout mathematics, and is commonly referred to as the integer part of a ...
of the free monoid (or the free semigroup) by these relations. This is an analogue of a
group presentation
In mathematics, a presentation is one method of specifying a group. A presentation of a group ''G'' comprises a set ''S'' of generators—so that every element of the group can be written as a product of powers of some of these generators—and ...
in
group theory
In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups.
The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ...
.
As a mathematical structure, a monoid presentation is identical to a
string rewriting system
In theoretical computer science and mathematical logic a string rewriting system (SRS), historically called a semi- Thue system, is a rewriting system over strings from a (usually finite) alphabet. Given a binary relation R between fixed strings ov ...
(also known as a semi-Thue system). Every monoid may be presented by a semi-Thue system (possibly over an infinite alphabet).
[Book and Otto, Theorem 7.1.7, p. 149]
A ''presentation'' should not be confused with a ''
representation''.
Construction
The relations are given as a (finite)
binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
on . To form the quotient monoid, these relations are extended to
monoid congruence
In abstract algebra, a congruence relation (or simply congruence) is an equivalence relation on an algebraic structure (such as a group, ring, or vector space) that is compatible with the structure in the sense that algebraic operations done ...
s as follows:
First, one takes the symmetric closure of . This is then extended to a symmetric relation by defining if and only if = and = for some strings with . Finally, one takes the reflexive and transitive closure of , which then is a monoid congruence.
In the typical situation, the relation is simply given as a set of equations, so that
. Thus, for example,
:
is the equational presentation for the
bicyclic monoid 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 m ...
, and
:
is the
plactic monoid In mathematics, the plactic monoid is the monoid of all words in the alphabet of positive integers modulo Knuth equivalence. Its elements can be identified with semistandard Young tableaux. It was discovered by (who called it the tableau algebra ...
of degree 2 (it has infinite order). Elements of this plactic monoid may be written as
for integers ''i'', ''j'', ''k'', as the relations show that ''ba'' commutes with both ''a'' and ''b''.
Inverse monoids and semigroups
Presentations of inverse monoids and semigroups can be defined in a similar way using a pair
:
where
is the
free monoid with involution 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, considere ...
on
, and
:
is a
binary
Binary may refer to:
Science and technology Mathematics
* Binary number, a representation of numbers using only two digits (0 and 1)
* Binary function, a function that takes two arguments
* Binary operation, a mathematical operation that t ...
relation between words. We denote by
(respectively
) the
equivalence relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.
Each equivalence relation ...
(respectively, the
congruence) generated by ''T''.
We use this pair of objects to define an inverse monoid
:
Let
be the
Wagner congruence 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 ...
on
, we define the inverse monoid
:
''presented'' by
as
:
In the previous discussion, if we replace everywhere
with
we obtain a presentation (for an inverse semigroup)
and an inverse semigroup
presented by
.
A trivial but important example is the free inverse monoid (or free inverse semigroup) on
, that is usually denoted by
(respectively
) and is defined by
:
or
:
Notes
References
* John M. Howie, ''Fundamentals of Semigroup Theory'' (1995), Clarendon Press, Oxford
* M. Kilp, U. Knauer, A.V. Mikhalev, ''Monoids, Acts and Categories with Applications to Wreath Products and Graphs'', De Gruyter Expositions in Mathematics vol. 29, Walter de Gruyter, 2000, .
*
Ronald V. Book
Ronald Vernon Book (March 5 1937 – May 28, 1997 in Santa Barbara, California) was a theoretical computer scientist. He published more than 150 papers in scientific journals.
His papers are of great impact for computational complexity theory
In ...
and Friedrich Otto, ''String-rewriting Systems'', Springer, 1993, , chapter 7, "Algebraic Properties"
{{DEFAULTSORT:Presentation Of A Monoid
Semigroup theory