Многообразие конечных полугрупп

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

Это понятие очень похоже на общее понятие разнообразия в универсальной алгебре.

Определение

Теперь даны два эквивалентных определения.

Алгебраическое определение

Многообразие V конечных (упорядоченных) полугрупп — это класс конечных (упорядоченных) полугрупп, который:

• закрыт под разделение .
• замкнуто относительно конечных декартовых произведений.

Первое условие эквивалентно утверждению, что V замкнуто относительно взятия подполугрупп и относительно взятия факторов. Второе свойство подразумевает, что пустое произведение, то есть тривиальная полугруппа из одного элемента, принадлежит каждому многообразию. Следовательно, многообразие обязательно непусто.

Разновидность конечных (упорядоченных) моноидов — это разновидность конечных (упорядоченных) полугрупп, элементами которых являются моноиды. То есть это класс (упорядоченных) моноидов, удовлетворяющих двум указанным выше условиям.

определение

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

Пусть A — произвольный конечный алфавит . Пусть А ⁺ быть его свободной полугруппой . Тогда пусть ${\hat {A}}$ множество бесконечных слов над A. — полугруппы Учитывая морфизм $\phi :A^{+}\to S$, позволять ${\hat {\phi }}:{\hat {A}}\to S$ быть единственным непрерывным продолжением $\phi$ к ${\hat {A}}$.

Проконечная идентичность — это пара u и v конечных слов полугруппа S . Говорят, что удовлетворяет проконечному тождеству u = v , если для каждого морфизма полугруппы $\phi :A^{+}\to S$, равенство ${\hat {\phi }}(u)={\hat {\phi }}(v)$ держит.

Разновидностью конечных полугрупп называется класс конечных полугрупп, удовлетворяющих множеству проконечных тождеств P .

Многообразие конечных моноидов определяется как многообразие конечных полугрупп с той разницей, что следует рассматривать морфизмы моноидов. $\phi :A^{*}\to M$ вместо морфизмов полугрупп $\phi :A^{+}\to M$.

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

Примеры

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

Дополнительные примеры приведены в статье Специальные классы полугрупп .

Использование конечных тождеств

• Самый тривиальный пример — многообразие S всех конечных полугрупп. Это многообразие определяется пустым множеством проконечных равенств. Легко видеть, что этот класс конечных полугрупп замкнут относительно подполугрупп, конечных произведений и факторов.
• Второй наиболее тривиальный пример — многообразие 1, содержащее только тривиальную полугруппу. Это многообразие определяется набором проконечных равенств { x = y }. Интуитивно это равенство означает, что все элементы полугруппы равны. Этот класс тривиально замкнут относительно подполугрупп, конечных произведений и факторов.
• Многообразие Com коммутативных конечных полугрупп определяется проконечным равенством xy = yx . Интуитивно это равенство означает, что каждая пара элементов полугруппы коммутирует.
• Многообразие идемпотентных конечных полугрупп определяется проконечным равенством xx = x .

В более общем смысле, учитывая бесконечное слово u и букву x , проконечное равенство ux = xu утверждает, что множество возможных изображений u содержит только элементы централизатора. Аналогично, ux = x утверждает, что множество возможных образов u содержит только левые тождества. Наконец, ux = u утверждает, что множество возможных образов u состоит из левых нулей.

Использование точных идентификаторов

Теперь приведены примеры использования проконечных слов, которые не являются конечными.

Учитывая длинное слово x , пусть $x^{\omega }$ обозначать $\lim _{n\to \infty }x^{n!}$. Следовательно, учитывая морфизм полугруппы $\phi :A^{+}\to S$, ${\hat {\phi }}(x^{\omega })$ единственная идемпотентная степень $\phi (x)$. Таким образом, в проконечных равенствах $x^{\omega }$ представляет собой произвольный идемпотент.

Класс G конечных групп — это многообразие конечных полугрупп. Обратите внимание, что конечную группу можно определить как конечную полугруппу с единственным идемпотентом, который, кроме того, является левым и правым тождеством. Как только эти два свойства будут переведены в термины проконечного равенства, можно увидеть, что многообразие G определяется набором проконечных равенств. $\{x^{\omega }=y^{\omega }{\text{ and }}x^{\omega }y=yx^{\omega }=y\}.$

Классы, не являющиеся разновидностями

Заметим, что класс конечных моноидов не является многообразием конечных полугрупп. Действительно, этот класс не замкнут относительно подполугрупп. Чтобы убедиться в этом, возьмем любую конечную полугруппу S , не являющуюся моноидом. Это подполугруппа моноида S ¹ формируется путем присоединения элемента идентичности.

Теорема Рейтермана

Теорема Рейтермана утверждает, что два приведенных выше определения эквивалентны. Приведена схема доказательства.

Учитывая разнообразие V полугрупп, как в алгебраическом определении, можно выбрать множество P проконечных тождеств как множество проконечных тождеств, которым удовлетворяет каждая полугруппа из V .

И наоборот, учитывая проконечное тождество u = v , можно заметить, что класс полугрупп, удовлетворяющих этому проконечному тождеству, замкнут относительно подполугрупп, факторов и конечных произведений. Таким образом, этот класс является многообразием конечных полугрупп. Кроме того, многообразия замкнуты относительно произвольного пересечения, поэтому для произвольного множества P проконечных тождеств u ^я = v ^я , класс полугрупп, удовлетворяющих P, является пересечением класса полугрупп, удовлетворяющих всем этим проконечным тождествам. То есть это пересечение многообразий конечных полугрупп, а это многообразие конечных полугрупп.

многообразия универсальной

Определение многообразия конечных полугрупп основано на понятии многообразия универсальных алгебр . Напомним определение многообразия в универсальной алгебре. Такое разнообразие эквивалентно:

• класс структур, замкнутых относительно гомоморфных образов, подалгебр и (прямых) произведений .
• класс структур, удовлетворяющих набору тождеств .

Теперь даются основные различия между двумя понятиями разнообразия. В этом разделе «многообразие (произвольных) полугрупп» означает «класс полугрупп как разновидность универсальной алгебры над словарем одного бинарного оператора». Из определений этих двух видов многообразий следует, что для любого многообразия V (произвольных) полугрупп класс конечных полугрупп V является многообразием конечных полугрупп.

Сначала мы приведем пример многообразия конечных полугрупп, не похожего ни на одно подмногообразие многообразия (произвольных) полугрупп. Затем мы даем разницу между двумя определениями, используя тождества. Наконец, мы приведем разницу между алгебраическими определениями.

Как было показано выше, класс конечных групп является разновидностью конечных полугрупп. Однако класс групп не является подмногообразием многообразия (произвольных) полугрупп. Действительно, $\langle \mathbb {Z} ,+\rangle$ моноид, являющийся бесконечной группой. Однако его субмоноид $\langle \mathbb {N} ,+\rangle$ это не группа. Поскольку класс (произвольных) групп содержит полугруппу и не содержит ни одной ее подполугруппы, он не является многообразием. Основное различие между конечным случаем и бесконечным случаем, когда рассматриваются группы, состоит в том, что субмоноид конечной группы является конечной группой. А бесконечные группы не замкнуты относительно субмоноидов.

Класс конечных групп является многообразием конечных полугрупп, но не является подмногообразием многообразия (произвольных) полугрупп. Таким образом, теорема Рейтермана показывает, что этот класс можно определить с помощью проконечных тождеств. А теорема Биркгофа HSP показывает, что этот класс нельзя определить с помощью тождеств (конечных слов). Это иллюстрирует, почему в определении множества конечных полугрупп используется понятие проконечных слов, а не понятие тождеств.

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

Ссылки

• Пин, Жан-Эрик (30 ноября 2016 г.). Математические основы теории автоматов (PDF) . стр. 141–160.
• Пин, Жан-Эрик (1986). Разновидности формального языка . Нью-Йорк: Plenum Publishing Corp.
• Эйленберг, С. (1976). Автоматы, языки и машины . Нью-Йорк: Издательство Harcourt Brace Jovanovich. стр. главы «Теорема о разложении в глубину» и «Сложность полугрупп и морфизмов».
• Алмейда, Дж (1994). Конечные полугруппы и универсальная алгебра . Ривер Эдж, Нью-Джерси: World Scientific Publishing Co. Inc.