Presentation of a monoid

<h2 id="construction">Construction</h2>
The relations are given as a (finite) <a href="/facts/Binary_relation/r9BwGgaK">binary relation</a> R on Σ∗. To form the quotient monoid, these relations are extended to <a href="/facts/Monoid_congruence/TV3njpqF">monoid congruences</a> 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 <a href="/facts/Bicyclic_monoid/GehG9bj5">bicyclic monoid</a>, 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 <a href="/facts/Plactic_monoid/7fgg8jyj">plactic monoid</a> 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.

<h2 id="inverse-monoids-and-semigroups">Inverse monoids and semigroups</h2>
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 <a href="/facts/Free_monoid_with_involution/aXJEUAmY">free monoid with involution</a> 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 <a href="/facts/Binary_function/lAtbyPRG">binary</a> relation between words. We denote by 
 
 
 
 
 T
 
 
 e
 
 
 
 
 
 {\displaystyle T^{\mathrm {e} }}
 
 (respectively 
 
 
 
 
 T
 
 
 c
 
 
 
 
 
 {\displaystyle T^{\mathrm {c} }}
 
) the <a href="/facts/Equivalence_relation/1MQ5rtkW">equivalence relation</a> (respectively, the <a href="/facts/Congruence_relation/TV3njpqF">congruence</a>) 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 <a href="/facts/Wagner_congruence/gz4ezaRq">Wagner congruence</a> 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}.}

<h2 id="notes">Notes</h2>

<ul><li>John M. Howie, Fundamentals of Semigroup Theory (1995), Clarendon Press, Oxford <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-19-851194-9</li>
<li>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, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 3-11-015248-7.</li>
<li><a href="/facts/Ronald_V._Book/owKGbE8t">Ronald V. Book</a> and Friedrich Otto, String-rewriting Systems, Springer, 1993, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-387-97965-4, chapter 7, "Algebraic Properties"</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Book and Otto, Theorem 7.1.7, p. 149 <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
</ol>

Presentation of a monoid open-in-new

Presentation of a monoid