Prezentacja monoidu

W algebrze prezentacja monoidy (lub prezentacji półgrupy ) jest opisem monoidy ( lub półgrupy ) w kategoriach zbioru Σ generatorów i układu relacji na wolnym monoidzie Σ ^∗ (lub wolnym półgrupa Σ ⁺ ) generowana przez Σ . Monoid jest następnie przedstawiany jako iloraz wolnego monoidu (lub wolnej półgrupy) na podstawie tych relacji. Jest to odpowiednik prezentacji grupowej w teorii grup .

Jako struktura matematyczna prezentacja monoidowa jest identyczna z systemem przepisywania ciągów (znanym również jako system pół-Thue). Każdy monoid może być przedstawiony w systemie semi-Thue (prawdopodobnie w nieskończonym alfabecie).

Prezentacji nie należy mylić z przedstawieniem .

Budowa

Relacje są podane jako (skończona) relacja binarna R na Σ ^∗ . Aby utworzyć iloraz monoidowy, relacje te rozszerza się na kongruencje monoidowe w następujący sposób:

Najpierw przyjmuje się symetryczne domknięcie R ∪ R ^-1 R . Jest to następnie rozciągane na relację symetryczną E ⊂ Σ ^∗ × Σ ^∗ poprzez zdefiniowanie x ~ _E y wtedy i tylko wtedy, gdy x = sut i y = svt dla niektórych ciągów u , v , s , t ∈ Σ ^∗ z ( u , v ) ∈ R ∪ R ^-1 . Na koniec przyjmujemy domknięcie zwrotne i przechodnie E , które jest wówczas kongruencją monoidalną.

W typowej sytuacji relację R podaje się po prostu jako zbiór równań, tak że ${\ displaystyle R = \ {u_ {1} = v_ { 1},\ldots,u_{n}=v_{n}\}}$ . Zatem na przykład

${\ Displaystyle \ langle p, q \, \ pion \; pq = 1 \ rangle}$

jest równaną prezentacją bicyklicznego monoidu i

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

jest monoidem plastycznym stopnia 2 (ma nieskończony porządek). Elementy tego monoidu plactycznego można zapisać jako relacje za ${\ displaystyle a ^ {i} b ^ {j} (ba) ^ {k}}$ liczb całkowitych i , jot , k pokazać, że ba dojeżdża zarówno z a jak i b .

Monoidy odwrotne i półgrupy

Prezentacje odwrotnych monoidów i półgrup można zdefiniować w podobny sposób za pomocą pary

${\ displaystyle (X; T)}$

Gdzie

${\ Displaystyle (X \ Puchar X ^ {-1}) ^ {*}}$

jest wolnym monoidem z inwolucją i . ${\ displaystyle X}$

${\ Displaystyle T \ subseteq (X \ Puchar X ^ {-1}) ^ {*} \ razy (X \ Puchar X ^ {- 1})^{*}}$

jest binarną relacją między słowami. Oznaczamy przez (odpowiednio $)$ relację równoważności ( $\ operatorname {e}$ { \ displaystyle T }

Używamy tej pary obiektów do zdefiniowania odwrotnego monoidu

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

Niech $kongruencją$ Wagnera na $odwrotny$ monoid _

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

przedstawiony przez ${\ Displaystyle (X; T)}$ jako

${\ Displaystyle \ operatorname {Inv} ^ {1} \ langle X | T \ rangle = (X \ kubek X ^ {-1}) ^ {*} / (T \ kubek \ rho _ {X}) ^ {\ matematyka {c} }.}$

W poprzedniej dyskusji, jeśli zastąpimy wszędzie ${\ Displaystyle ({X \ puchar X ^ {-1}}) ^ {*}}$ z ${\ displaystyle ({X\cup X^{-1}})^{+}}$ otrzymujemy prezentację (dla odwrotnej półgrupy) ${\ displaystyle (X; T)}$ i odwrotnej półgrupy ${\ Displaystyle \ operatorname {Inv} \ langle X | T \ rangle}$ przedstawione przez ${\ Displaystyle (X; T)}$ .

Trywialnym, ale ważnym przykładem jest wolny odwrotny monoid (lub swobodna odwrotna półgrupa $)$ na , który jest zwykle oznaczany przez ( odpowiednio $displaystyle \ operatorname {FIM} (X)}$${\ Displaystyle \ operatorname {FIS} (X)}$ ) i jest zdefiniowany przez

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

Lub

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

Notatki

•   John M. Howie, Podstawy teorii półgrup (1995), Clarendon Press, Oxford ISBN 0-19-851194-9
•   M. Kilp, U. Knauer, AV Mikhalev, Monoidy, akty i kategorie z zastosowaniami do produktów wieńcowych i wykresów , De Gruyter Expositions in Mathematics tom. 29, Walter de Gruyter, 2000, ISBN 3-11-015248-7 .
•   Ronald V. Book i Friedrich Otto, String-rewriting Systems , Springer, 1993, ISBN 0-387-97965-4 , rozdział 7, „Właściwości algebraiczne”