Presentation av en monoid

I algebra är en presentation av en monoid (eller en presentation av en halvgrupp ) en beskrivning av en monoid (eller en halvgrupp ) i termer av en uppsättning Σ av generatorer och en uppsättning relationer på den fria monoiden Σ ^∗ (eller den fria halvgrupp Σ ⁺ ) genererad av Σ . Monoiden presenteras sedan som kvoten av den fria monoiden (eller den fria halvgruppen) av dessa relationer. Detta är en analog till en grupppresentation i gruppteori .

Som en matematisk struktur är en monoid presentation identisk med ett strängomskrivningssystem (även känt som ett semi-Thue-system). Varje monoid kan presenteras av ett semi-Thue-system (möjligen över ett oändligt alfabet).

En presentation ska inte förväxlas med en representation .

Konstruktion

Relationerna ges som en (ändlig) binär relation R på Σ ^∗ . För att bilda kvoten monoid, utvidgas dessa relationer till monoid kongruenser enligt följande:

Först tar man den symmetriska stängningen R ∪ R ⁻¹ av R . Detta utökas sedan till en symmetrisk relation E ⊂ Σ ^∗ × Σ ^∗ genom att definiera x ~ _E y om och endast om x = sut och y = svt för några strängar u , v , s , t ∈ Σ ^∗ med ( u , v ) ∈ R ∪ R ⁻¹ . Slutligen tar man den reflexiva och transitiva stängningen av E , som då är en monoid kongruens.

I den typiska situationen ges relationen R helt enkelt som en uppsättning ekvationer, så att $R=\{u_{1}=v_{ 1},\ldots ,u_{n}=v_{n}\}$ . Sålunda har t.ex.

$\langle p,q\,\vert \;pq=1\rangle$

är ekvationspresentationen för den bicykliska monoiden , och

$\langle a,b\,\vert \;aba=baa,bba=bab\rangle$

är den plastiska monoiden av grad 2 (den har oändlig ordning). Element av denna plastiska monoid kan skrivas som $a^{i}b^{j}(ba)^{k}$ för heltal i , j , k , som relationerna visa att ba pendlar med både a och b .

Omvända monoider och semigrupper

Presentationer av inversa monoider och semigrupper kan definieras på liknande sätt med hjälp av ett par

$(X;T)$

var

$(X\cup X^{-1})^{*}$

är den fria monoiden med involution på $X$ , och

$T\subseteq (X\cup X^{-1})^{*}\times (X\cup X^{- 1})^{*}$

är en binär relation mellan ord. Vi betecknar med $T^{\mathrm {e} }$ (respektive $T^{\mathrm {c} }$ ) ekvivalensrelationen ( respektive kongruensen ) som genereras av T .

Vi använder detta par av objekt för att definiera en invers monoid

$\mathrm {Inv} ^{1}\langle X|T\rangle .$

Låt $\rho _{X}$ vara Wagner-kongruensen på $X$ , vi definierar den inversa monoiden

$\mathrm {Inv} ^{1}\langle X|T\rangle$

presenteras av $(X;T)$ som

$\mathrm {Inv} ^{1}\langle X|T\rangle =(X\cup X^{-1})^{*}/(T\cup \rho _{X})^{\ mathrm {c} }.$

I föregående diskussion, om vi ersätter överallt $({X\cup X^{-1}})^{*}$ med $({X\cup X^{-1}})^{+}$ får vi en presentation (för en invers halvgrupp) $(X;T)$ och en invers halvgrupp $\mathrm {Inv} \langle X|T\rangle$ presenterad av $(X;T)$ .

Ett trivialt men viktigt exempel är den fria inversa monoiden (eller den fria inversa halvgruppen ) på ${\displaystyle X} ,$ som vanligtvis betecknas med ${\displaystyle \mathrm {FIM} (X)} ($ respektive $\mathrm {FIS} (X)$ ) och definieras av

$\mathrm {FIM} (X)=\mathrm {Inv} ^{1}\langle X|\varnothing \rangle =({X\cup X^{-1}})^{*}/\rho _{X},$

eller

$\mathrm {FIS} (X)=\mathrm {Inv} \langle X|\varnothing \rangle =({X\cup X^{-1}})^{+}/\rho _{X} .$

Anteckningar

•   John M. Howie, Fundamentals of Semigroup Theory (1995), Clarendon Press, Oxford ISBN 0-19-851194-9
•   M. Kilp, U. Knauer, AV 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 och Friedrich Otto, String-rewriting Systems , Springer, 1993, ISBN 0-387-97965-4 , kapitel 7, "Algebraic Properties"