Представление моноида

В алгебре представление моноида (или представление полугруппы ) — это описание моноида ( или полугруппы ) в терминах множества образующих Σ и набора отношений на свободном моноиде Σ. ^∗ (или свободная полугруппа Σ ⁺ ), порожденный Σ . Моноид затем представляется как фактор свободного моноида (или свободной полугруппы) по этим отношениям. Это аналог представления группы в теории групп .

По математической структуре моноидное представление идентично системе переписывания строк (также известной как система полу-Туэ). Каждый моноид может быть представлен системой полуТуэ (возможно, над бесконечным алфавитом).

Презентацию представлением путать с не следует .

Строительство

Отношения задаются как (конечное) бинарное отношение R на Σ ^∗ . Чтобы сформировать фактормоноид, эти отношения распространяются на моноидные сравнения следующим образом:

Сначала берется симметричное замыкание R ∪ R ⁻¹ Р. ​ ​Затем это расширяется до симметричного отношения E ⊂ Σ ^∗ × С ^∗ определив x ~ _E y тогда и только тогда, когда x = sut и y = svt для некоторых строк u , v , s , t ∈ Σ ^∗ с ( ты , v ) ∈ р ∪ р ⁻¹ . Наконец, берется рефлексивное и транзитивное замыкание E , которое тогда является моноидным сравнением.

В типичной ситуации отношение R просто задается в виде набора уравнений, так что $R=\{u_{1}=v_{1},\ldots ,u_{n}=v_{n}\}$. Так, например,

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

— эквациональное представление бициклического моноида , и

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

— пластический моноид степени 2 (имеет бесконечный порядок). Элементы этого пластического моноида можно записать как $a^{i}b^{j}(ba)^{k}$ для целых чисел i , j , k , поскольку соотношения показывают, что ba коммутирует как с a, так и с b .

Обратные моноиды и полугруппы

Представления обратных моноидов и полугрупп можно определить аналогичным образом с помощью пары

$(X;T)$

где

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

– свободный моноид с инволюцией на $X$, и

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

это бинарное отношение между словами. Обозначим через $T^{\mathrm {e} }$ (соответственно $T^{\mathrm {c} }$) отношение эквивалентности (соответственно конгруэнтность ), порожденное T .

Мы используем эту пару объектов для определения обратного моноида.

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

Позволять $\rho _{X}$ быть сравнением Вагнера на $X$, определим обратный моноид

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

представлено ​ $(X;T)$ как

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

В предыдущем обсуждении, если мы заменим везде $({X\cup X^{-1}})^{*}$ с $({X\cup X^{-1}})^{+}$ получаем представление (для инверсной полугруппы) $(X;T)$ и обратная полугруппа $\mathrm {Inv} \langle X|T\rangle$ представлено ​ $(X;T)$.

Тривиальный, но важный пример — свободный инверсный моноид (или свободная инверсная полугруппа ) на $X$, что обычно обозначается $\mathrm {FIM} (X)$ (соответственно $\mathrm {FIS} (X)$) и определяется

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

или

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

Ссылки

• Джон М. Хоуи, Основы теории полугрупп (1995), Clarendon Press, Оксфорд ISBN   0-19-851194-9
• М. Килп, У. Кнауэр, А. В. Михалев, Моноиды, действия и категории с приложениями к сплетениям и графам , Изложения Де Грюйтера по математике, том. 29, Вальтер де Грюйтер, 2000 г., ISBN   3-11-015248-7 .
• Рональд В. Бук и Фридрих Отто, Системы переписывания строк , Springer, 1993, ISBN   0-387-97965-4 , глава 7, «Алгебраические свойства».