- Source: Presentation of a monoid
In algebra, a presentation of a monoid (or a presentation of a semigroup) is a description of a monoid (or a semigroup) in terms of a set Σ of generators and a set of relations on the free monoid Σ∗ (or the free semigroup Σ+) generated by Σ. The monoid is then presented as the quotient of the free monoid (or the free semigroup) by these relations. This is an analogue of a group presentation in group theory.
As a mathematical structure, a monoid presentation is identical to a string rewriting system (also known as a semi-Thue system). Every monoid may be presented by a semi-Thue system (possibly over an infinite alphabet).
A presentation should not be confused with a representation.
Construction
The relations are given as a (finite) binary relation R on Σ∗. To form the quotient monoid, these relations are extended to monoid congruences as follows:
First, one takes the symmetric closure R ∪ R−1 of R. This is then extended to a symmetric relation E ⊂ Σ∗ × Σ∗ by defining x ~E y if and only if x = sut and y = svt for some strings u, v, s, t ∈ Σ∗ with (u,v) ∈ R ∪ R−1. Finally, one takes the reflexive and transitive closure of E, which then is a monoid congruence.
In the typical situation, the relation R is simply given as a set of equations, so that
R
=
{
u
1
=
v
1
,
…
,
u
n
=
v
n
}
{\displaystyle R=\{u_{1}=v_{1},\ldots ,u_{n}=v_{n}\}}
. Thus, for example,
⟨
p
,
q
|
p
q
=
1
⟩
{\displaystyle \langle p,q\,\vert \;pq=1\rangle }
is the equational presentation for the bicyclic monoid, and
⟨
a
,
b
|
a
b
a
=
b
a
a
,
b
b
a
=
b
a
b
⟩
{\displaystyle \langle a,b\,\vert \;aba=baa,bba=bab\rangle }
is the plactic monoid of degree 2 (it has infinite order). Elements of this plactic monoid may be written as
a
i
b
j
(
b
a
)
k
{\displaystyle a^{i}b^{j}(ba)^{k}}
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
(
X
;
T
)
{\displaystyle (X;T)}
where
(
X
∪
X
−
1
)
∗
{\displaystyle (X\cup X^{-1})^{*}}
is the free monoid with involution on
X
{\displaystyle X}
, and
T
⊆
(
X
∪
X
−
1
)
∗
×
(
X
∪
X
−
1
)
∗
{\displaystyle T\subseteq (X\cup X^{-1})^{*}\times (X\cup X^{-1})^{*}}
is a binary relation between words. We denote by
T
e
{\displaystyle T^{\mathrm {e} }}
(respectively
T
c
{\displaystyle T^{\mathrm {c} }}
) the equivalence relation (respectively, the congruence) generated by T.
We use this pair of objects to define an inverse monoid
I
n
v
1
⟨
X
|
T
⟩
.
{\displaystyle \mathrm {Inv} ^{1}\langle X|T\rangle .}
Let
ρ
X
{\displaystyle \rho _{X}}
be the Wagner congruence on
X
{\displaystyle X}
, we define the inverse monoid
I
n
v
1
⟨
X
|
T
⟩
{\displaystyle \mathrm {Inv} ^{1}\langle X|T\rangle }
presented by
(
X
;
T
)
{\displaystyle (X;T)}
as
I
n
v
1
⟨
X
|
T
⟩
=
(
X
∪
X
−
1
)
∗
/
(
T
∪
ρ
X
)
c
.
{\displaystyle \mathrm {Inv} ^{1}\langle X|T\rangle =(X\cup X^{-1})^{*}/(T\cup \rho _{X})^{\mathrm {c} }.}
In the previous discussion, if we replace everywhere
(
X
∪
X
−
1
)
∗
{\displaystyle ({X\cup X^{-1}})^{*}}
with
(
X
∪
X
−
1
)
+
{\displaystyle ({X\cup X^{-1}})^{+}}
we obtain a presentation (for an inverse semigroup)
(
X
;
T
)
{\displaystyle (X;T)}
and an inverse semigroup
I
n
v
⟨
X
|
T
⟩
{\displaystyle \mathrm {Inv} \langle X|T\rangle }
presented by
(
X
;
T
)
{\displaystyle (X;T)}
.
A trivial but important example is the free inverse monoid (or free inverse semigroup) on
X
{\displaystyle X}
, that is usually denoted by
F
I
M
(
X
)
{\displaystyle \mathrm {FIM} (X)}
(respectively
F
I
S
(
X
)
{\displaystyle \mathrm {FIS} (X)}
) and is defined by
F
I
M
(
X
)
=
I
n
v
1
⟨
X
|
∅
⟩
=
(
X
∪
X
−
1
)
∗
/
ρ
X
,
{\displaystyle \mathrm {FIM} (X)=\mathrm {Inv} ^{1}\langle X|\varnothing \rangle =({X\cup X^{-1}})^{*}/\rho _{X},}
or
F
I
S
(
X
)
=
I
n
v
⟨
X
|
∅
⟩
=
(
X
∪
X
−
1
)
+
/
ρ
X
.
{\displaystyle \mathrm {FIS} (X)=\mathrm {Inv} \langle X|\varnothing \rangle =({X\cup X^{-1}})^{+}/\rho _{X}.}
Notes
References
John M. Howie, Fundamentals of Semigroup Theory (1995), Clarendon Press, Oxford ISBN 0-19-851194-9
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, ISBN 3-11-015248-7.
Ronald V. Book and Friedrich Otto, String-rewriting Systems, Springer, 1993, ISBN 0-387-97965-4, chapter 7, "Algebraic Properties"
Kata Kunci Pencarian:
- Masalah kata untuk grup
- Presentasi grup
- Presentation of a monoid
- Monoid
- Semi-Thue system
- Presentation of a group
- Generating set of a group
- Rewriting
- Knuth–Bendix completion algorithm
- Plactic monoid
- Modular group
- Eckmann–Hilton argument
