ПОЛУГРУППА, ассоциативная система

— множество S, в котором определена операция (обычно ее записывают как умножение), ставящая в соответствие каждой паре элементов х и у из S, расположенных в данном порядке, элемент из S — их «произведение». При этом в S предполагается выполнение ассоциативного закона: для любых элементов х, у и z из S. Если для любых элементов из , то такая П. наз. коммутативной (иногда — абелевой). В П. S может содержаться «единица» или «нуль» 0 — такие элементы, что для любого х из S. Однако в отличие от группы (см. Групп теория), наличие в П. единицы (а тем более — обратных элементов) не обязательно. Если какое-либо подмножество само является П. относительно действия, определенного в S (т. е., Т содержит произведение любых двух своих элементов), то Т наз. подполугруппой П. S. Т наз. идеалом П. S, если содержатся в Т, каковы бы ни были элементы .

Отдельные результаты, относящиеся к П., появились еще в начале 20 ст. Серьезное изучение П. началось в 20-х годах в работах сов. алгебраиста А. К. Сушкевича (1889—1961). П. S наз. П. с сокращением, если для любых ее элементов х, у и z из или следует Всякая группа и всякая подполугруппа группыявляется П. с сокращением. Всякую коммутативную П. с сокращением можно погрузить в некоторую абелеву группу. Существуют некоммутативные П. с сокращением, не вложимые в группу. Группы являются важным и наиболее изученным классом П.

Теория П. развивалась вначале как обобщение теории групп. Однако со временем теория Г. выделилась в самостоятельную ветвь общей алгебры, имеющую собственные задачи, методы и приложения. Обозначим через S (А) мн-во всех преобразований (отображений в

себя) какого-либо мн-ва A. S (А) является П. относительно операции суперпозиции преобразований если для любого элемента а из А. С более общей ситуацией мы сталкиваемся при изучении операции умножения бинарных отношений. Бинарное отношение на мн-ве А — это подмн-во декартова квадрата Отношение). Произведение а двух бинарных отношений на А определяется как множество таких пар , что для некоторого . Совокупность всех бинарных отношений на мн-ве А образует для так определенного умножения П. Обозначим через рггр и мн-ва всех элементов с и соответственно b из , для которых существует такой элемент а, что . Каждое бинарное отношение между элементами мн-ва можно рассматривать как отображение (вообще говоря, многозначное) мн-ва на , ставящее в соответствие каждому элементу некоторое подмн-во тогда и только тогда, когда ; обычно р наз. многозначным частичным преобразованием мн-ва А. Если то преобразование наз. полным. Для полных однозначных преобразований умножение бинарных отношений сводится к операции суперпозиции преобразований. Гомоморфизм (в частности, изоморфизм) Ф П. S на какую-нибудь подполугруппу всех преобразований некоторого мн-ва А наз. представлением П. S преобразованиями. Для каждой П. существует изоморфное представление преобразованиями некоторого мн-ва Л. В то же время П. S (Л) всех преобразований мн-ва А является подполугруппой П. Р(A) всех бинарных отношений между элементами мн-ва А (т. е. многозначных частичных преобразований мн-ва А). Поэтому теорию П. можно трактовать как абстрактное учение о суперпозиции самых общих преобразований — не обязательно обратимых, не обязательно однозначных и даже не всюду определенных.

Элемент s П. идемпотентом, если . В частности, если П. S содержит единицу или нуль 0, то они являются идемпотентами. П. регулярной, если для всякого ее элемента х существует такой элемент у, что . Регулярная П. S наз. инверсной, если Для любых ее идемпотентов . Инверсные П. и только они изоморфны П. обратимых (взаимно однозначных) частичных преобразований множеств. Как и для произвольных алгебраических структур, всякий гомоморфизм П. связан с некоторым отношением конгруэнтности. В отличие от групп, конгруэнтность П. не определяется каким-то одним ее классом. Идеалы П. и только они являются полными прообразами нуля при ее гомоморфизмах (если П. содержит нуль). Пусть М — подмн-во П. наименьшая подполугруппа П. S, содержащая если , то М наз. порождающим мн-вом S. П. S, содержащая порождающее множество, состоящее из одного элемента, наз. моногенной (циклической). Всякая бесконечная моногенная П. изоморфна П. всех целых положительных чисел относительно сложения. Если все моногенные подполугруппы П. конечны, то такая П. периодической. Если элементы порождающего мн-ва П. S, то равенство определяющим соотношением П. S. Если П. S с порождающим мн-вом М обладает лишь такими определяющими соотношениями, в которых то свободной П. над М. П., в которых имеется конечное порождающее мн-во, являются, в частности, объектами изучения алгоритмов теории.

С каждым абстрактным автоматом связывают, как известно, свободные П. над мн-вом ЗС, и 21 его входов, выходов и состояний. Кроме того, с автоматом А сопоставляется представление свободной П. ЗС преобразованиями мн-ва П. преобразований П. автомата Л. Если SA — П. многозначных преобразований (бинарных отношений), получается недетерминированный автомат; если однозначных преобразований, автомат Л — детерминированный. Если полных (соответственно, частичных) преобразований, то автомат А — полный (соответственно, частичный или неполный). Для любых подмн-в и В произвольной П. S обозначим через АВ мн-во всех произведений где . Относительно определенной таким образом операции мн-во всех подмн-в П. S образует глобальной П. для П. S. Если X— свободная П. над X, то элементы глобальной П. в теории автоматов наз. событиями, в лингвистике математической — языками, а в абстрактной теории кодирования — кодами (более подробно о применении П. в теории автоматов см. в Алгебраическая теория автоматов).

В различных приложениях встречаются упорядоченные и топологические П. Упорядоченная это П. S с отношением частичной упорядоченности таким, что для любых из а b следует топологической, если она является топологическим пространством и ф-ция непрерывна. Лит.: .