Действие полугруппы

Действие или акт полугруппы на множестве

В алгебре и теоретической информатике действие или акт полугруппы на множестве — это правило, которое сопоставляет каждому элементу полугруппы преобразование множества таким образом, что произведение двух элементов полугруппы (с использованием операции полугруппы ) сопоставляется с композитом двух соответствующих преобразований. Терминология передает идею о том, что элементы полугруппы действуют как преобразования множества. С алгебраической точки зрения действие полугруппы является обобщением понятия группового действия в теории групп . С точки зрения информатики действия полугруппы тесно связаны с автоматами : множество моделирует состояние автомата, а действие моделирует преобразования этого состояния в ответ на входные данные.

Важным частным случаем является действие моноида или акт , в котором полугруппа является моноидом , а единичный элемент моноида действует как тождественное преобразование множества. С точки зрения теории категорий моноид — это категория с одним объектом, а акт — это функтор из этой категории в категорию множеств . Это немедленно дает обобщение на моноидные акты на объектах в категориях, отличных от категории множеств.

Другим важным частным случаем является полугруппа преобразований . Это полугруппа преобразований множества, и, следовательно, она имеет тавтологическое действие на этом множестве. Это понятие связано с более общим понятием полугруппы аналогом теоремы Кэли .

(Замечание о терминологии: терминология, используемая в этой области, различается, иногда значительно, у разных авторов. Подробности см. в статье.)

Формальные определения

Пусть S — полугруппа. Тогда (левое) полугрупповое действие (или акт ) S — это множество X вместе с операцией • : S × X → X , которая совместима с полугрупповой операцией ∗ следующим образом:

• для всех s , t из S и x из X , s • ( t • x ) = ( s ∗ t ) • x .

Это аналог в теории полугрупп (левого) группового действия , и он эквивалентен гомоморфизму полугруппы в множество функций на X. Правые полугрупповые действия определяются аналогичным образом с помощью операции • : X × S → X, удовлетворяющей ( x • a ) • b = x • ( a ∗ b ) .

Если M — моноид, то (левое) моноидное действие (или акт ) M — это (левое) полугрупповое действие M с дополнительным свойством:

• для всех x в X : e • x = x

где e — единичный элемент M . Соответственно, это дает гомоморфизм моноида. Правые действия моноида определяются аналогичным образом. Моноид M с действием на множестве также называется операторным моноидом .

Действие полугруппы S на X можно превратить в моноидное действие , присоединив тождество к полугруппе и потребовав, чтобы оно действовало как тождественное преобразование на X.

Терминология и обозначения

Если S — полугруппа или моноид, то множество X , на котором S действует, как указано выше (скажем, слева), также известно как (левый) S -акт , S -множество , S -действие , S -операнд или левый акт над S. Некоторые авторы не различают действия полугруппы и моноида, считая аксиому тождества ( e • x = x ) пустой, когда нет элемента тождества, или используя термин унитарный S -акт для S -акта с тождеством. ^[1]

Определяющее свойство действия аналогично ассоциативности полугрупповой операции и означает, что все скобки можно опустить. Распространенной практикой, особенно в информатике, является также опускание операций, так что и полугрупповая операция, и действие обозначаются сопоставлением. Таким образом, строки букв из S действуют на X , как в выражении stx для s , t в S и x в X.

Также довольно часто приходится работать с правыми актами, а не с левыми. ^[2] Однако каждый правый S-акт можно интерпретировать как левый акт над противоположной полугруппой , которая имеет те же элементы, что и S, но где умножение определяется путем обращения множителей, s • t = t • s , так что эти два понятия по сути эквивалентны. Здесь мы в первую очередь принимаем точку зрения левых актов.

Деяния и преобразования

Часто бывает удобно (например, если рассматривается более одного акта) использовать букву, например , для обозначения функции ${\displaystyle T}$

${\displaystyle T\colon S\times X\to X}$

определяя -действие и, следовательно, записывая вместо . Тогда для любого в , мы обозначаем через ${\displaystyle S}$ ${\displaystyle T(s,x)}$ ${\displaystyle s\cdot x}$ ${\displaystyle s}$ ${\displaystyle S}$

${\displaystyle T_{s}\colon X\to X}$

преобразование определяется ${\displaystyle X}$

${\displaystyle T_{s}(x)=T(s,x).}$

По определяющему свойству -акта удовлетворяет ${\displaystyle S}$ ${\displaystyle T}$

${\displaystyle T_{s*t}=T_{s}\circ T_{t}.}$

Далее рассмотрим функцию . Это то же самое, что (см. Каррирование ). Поскольку является биекцией, действия полугруппы могут быть определены как функции , которые удовлетворяют ${\displaystyle s\mapsto T_{s}}$ ${\displaystyle \operatorname {curry} (T):S\to (X\to X)}$ ${\displaystyle \operatorname {curry} }$ ${\displaystyle S\to (X\to X)}$

${\displaystyle \operatorname {curry} (T)(s*t)=\operatorname {curry} (T)(s)\circ \operatorname {curry} (T)(t).}$

То есть является полугрупповым действием на тогда и только тогда, когда является полугрупповым гомоморфизмом из в полный моноид преобразований . ${\displaystyle T}$ ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle \operatorname {curry} (T)}$ ${\displaystyle S}$ ${\displaystyle X}$

С-гомоморфизмы

Пусть X и X ′ — S -полигоны. Тогда S -гомоморфизм из X в X ′ — это отображение

${\displaystyle F\colon X\to X'}$

такой что

${\displaystyle F(sx)=sF(x)}$для всех и . ${\displaystyle s\in S}$ ${\displaystyle x\in X}$

Множество всех таких S -гомоморфизмов обычно записывается как . ${\displaystyle \mathrm {Hom} _{S}(X,X')}$

M -гомоморфизмы M -полигонов, для M — моноида, определяются точно так же.

С-Действуй иМ-Действовать

Для фиксированной полугруппы S левые S -полигоны являются объектами категории, обозначаемой S -Act, морфизмы которой являются S -гомоморфизмами. Соответствующая категория правых S -полигонов иногда обозначается как Act- S . (Это аналогично категориям R -Mod и Mod- R левых и правых модулей над кольцом .)

Для моноида M категории M -Act и Act- M определяются одинаково.

Примеры

• Любая полугруппа имеет действие на , где . Свойство действия выполняется в силу ассоциативности . ${\displaystyle (S,*)}$ ${\displaystyle S}$ ${\displaystyle \cdot =*}$ ${\displaystyle *}$
• В более общем случае для любого гомоморфизма полугруппы полугруппа имеет действие на , заданное формулой . ${\displaystyle F\colon (S,*)\rightarrow (T,\oplus )}$ ${\displaystyle (S,*)}$ ${\displaystyle T}$ ${\displaystyle s\cdot t=F(s)\oplus t}$
• Для любого множества пусть будет множеством последовательностей элементов из . Полугруппа имеет действие на заданное формулой (где обозначает повторные числа). ${\displaystyle X}$ ${\displaystyle X^{*}}$ ${\displaystyle X}$ ${\displaystyle (\mathbb {N} ,\times )}$ ${\displaystyle X^{*}}$ ${\displaystyle n\cdot s=s^{n}}$ ${\displaystyle s^{n}}$ ${\displaystyle s}$ ${\displaystyle n}$
• Полугруппа имеет правое действие , заданное формулой . ${\displaystyle (\mathbb {N} ,\times )}$ ${\displaystyle (\mathbb {N} ,\cdot )}$ ${\displaystyle x\cdot y=x^{y}}$

Полугруппы преобразований

Ниже описывается соответствие между полугруппами преобразований и действиями полугрупп. Если ограничить его точным действием полугрупп, то оно обладает хорошими свойствами.

Любая полугруппа преобразований может быть превращена в действие полугруппы с помощью следующей конструкции. Для любой полугруппы преобразований определите действие полугруппы на как для . Это действие является точным, что эквивалентно тому, что оно является инъективным . ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle T}$ ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle T(s,x)=s(x)}$ ${\displaystyle s\in S,x\in X}$ ${\displaystyle curry(T)}$

Обратно, для любого действия полугруппы на , определим полугруппу преобразований . В этой конструкции мы «забываем» множество . равно образу . Обозначим как для краткости. Если инъективно , то это изоморфизм полугруппы из в . Другими словами, если точно, то мы ничего важного не забываем. Это утверждение уточняется следующим наблюдением: если мы вернемся к действию полугруппы на , то для всех . и «изоморфны» посредством , т. е. мы по сути восстановили . Таким образом, некоторые авторы [ ^3] не видят различия между точными действиями полугрупп и полугруппами преобразований. ${\displaystyle T}$ ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle S'=\{T_{s}\mid s\in S\}}$ ${\displaystyle S}$ ${\displaystyle S'}$ ${\displaystyle curry(T)}$ ${\displaystyle curry(T)}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle S}$ ${\displaystyle S'}$ ${\displaystyle T}$ ${\displaystyle S'}$ ${\displaystyle T'}$ ${\displaystyle S'}$ ${\displaystyle X}$ ${\displaystyle T'(f(s),x)=T(s,x)}$ ${\displaystyle s\in S,x\in X}$ ${\displaystyle T}$ ${\displaystyle T'}$ ${\displaystyle f}$ ${\displaystyle T}$

Приложения к информатике

Полуавтоматы

Полугруппы преобразований имеют существенное значение для теории структур конечных автоматов в теории автоматов . В частности, полуавтомат — это тройка (Σ, X , T ), где Σ — непустое множество, называемое входным алфавитом , X — непустое множество, называемое множеством состояний , а T — функция

${\displaystyle T\colon \Sigma \times X\to X}$

называется функцией перехода . Полуавтоматы возникают из детерминированных автоматов путем игнорирования начального состояния и набора допустимых состояний.

Для данного полуавтомата пусть T _a : X → X , для a ∈ Σ, обозначает преобразование X, определяемое соотношением T _a ( x ) = T ( a , x ). Тогда полугруппа преобразований X, порождённая { T _a  : a ∈ Σ}, называется характеристической полугруппой или системой переходов (Σ, X , T ). Эта полугруппа является моноидом, поэтому этот моноид называется характеристическим или переходным моноидом . Иногда его также рассматривают как Σ ^∗ -действие на X , где Σ ^∗ — свободный моноид строк, порождённый алфавитом Σ, ^{[примечание 1]} , а действие строк расширяет действие Σ с помощью свойства

${\displaystyle T_{vw}=T_{w}\circ T_{v}.}$

Теория Крона–Роудса

Теория Крона–Роудса, иногда также называемая алгебраической теорией автоматов , дает мощные результаты разложения для конечных полугрупп преобразований путем каскадирования более простых компонентов.

Примечания

1. Моноидальная операция — конкатенация; единичный элемент — пустая строка.

Ссылки

1. Килп, Кнауэр и Михалев, 2000, страницы 43–44.
2. Килп, Кнауэр и Михалев, 2000.
3. Арбиб, Майкл А., ред. (1968). Алгебраическая теория машин, языков и полугрупп . Нью-Йорк и Лондон: Academic Press. стр. 83.

• AH Clifford и GB Preston (1961), Алгебраическая теория полугрупп , том 1. Американское математическое общество, ISBN 978-0-8218-0272-4 . 
• AH Clifford и GB Preston (1967), Алгебраическая теория полугрупп , том 2. Американское математическое общество, ISBN 978-0-8218-0272-4 . 
• Мати Килп, Ульрих Кнауэр, Александр В. Михалёв (2000), Моноиды, акты и категории: с приложениями к сплетенным произведениям и графам , Expositions in Mathematics 29 , Вальтер де Грюйтер, Берлин, ISBN 978-3-11-015248-7 . 
• Рудольф Лидл и Гюнтер Пильц, Прикладная абстрактная алгебра (1998), Springer, ISBN 978-0-387-98290-8