Гомоморфизмы, конгруэнции и фактор полугруппы. Степени и фактор степени

  Рисунок 2: Произведение частных чипов. 2 Лекция 2: Примеры (продолжение), гомоморфизмы, конгруэнции и фактор полугруппы. Степени и фактор степени. 2.1 Основные примеры полугрупп (продолжение)                2.1.1 Чистяковой аналог полугруппы Брауэра.             Как мы уже видели, симметричная группа и полутрупа всех преобразований множества имеют естественные частичные аналоги - инверсную симметричную полутруп и полутрупами всех частичных преобразований множества. Хотя полутрупа Брауэра и не является полугруппы преобразований, однако нетрудно построить пруродный "частичный" аналог и для нее. мы назовем его частичный аналог полугруппы Брауэра , или полугруппы частичных чипов. Зафиксируем и обозначим   множество, элементами которой являются все возможные разбиения множества {1, 2 ,. . . , n, 1 ', 2' ,. . ., n' } на двo- и одноэлементные подмножества. Это и есть частичные чипы. Произведение частных чипов определяется аналогично произведения обычных чипов: сначала мы отождествляем штрихованные числа первого разбиения с соответствующими не штрихованными числами второго разбиения, если теперь просто забыть о отождествленых элементах, мы получим новое разбиение нашей множества на двух и одноэлементные подмножества, забывая о "мертвых циклах". Произведение частных чипов проиллюстрировано на Рисунке 2. Ассоциативность этой операции также легко следует из ее "предписывающего" интерпретации. содержит в качестве подполугруппы и имеет естественный нейтральный элемент, который является нейтральным элементом .   Рисунок 3: Произведение композиций. 2.1.2 Полугруппа композиций.             После частичных чипов следующее обобщение полугруппы Брауэра выглядит уже совершенно естественно. Зафиксируем  и обозначим  множество, элементами которой являются все возможные разбиения множества {1, 2 ,. . . , n, 1 ', 2' ,. . ., n'}   на подмножества. Определим "предписывающего" ассоциативную операцию на  так же, как это делалось в случае обычных и частичных чипов (см. также пример на Рисунке 3). называется полугруппой композиций , а ее элементы - композициями (или обобщенными чипами).  содержит как , так и  как подполугруппы и имеет естественный нейтральный элемент, который является нейтральным элементом . 2.1.3 Полугруппа двойных-стохастических матриц.             Еще один пример полугрупы происходит по теории вероятностей. Обозначим   множество всех п  n - матриц с неотъемлемыми действительными коэффициентами, сумма элементов которых в произвольном строке и столбце равна 1. Такие матрицы называют вдвойне (двояко) - стохастическими. Непосредственным вычислением легко проверяется, что обычный матричное произведение двух вдвойне-стохастических матриц снова является вдвойне-стохастической матрицей, а значит, полугруппа, единичным элементом которой является единичная матрица (которая, очевидно является вдвойне-стохастической). 2.2 Гомоморфизм полугрупп.                 Наха  и обозначают некоторые полугруппы. Отображение Т называется гомоморфизмом полугрупп , если  для произвольных . Если дополнительно S и Т являются моноидами и переводит нейтральный элемент S в нейтральный элемент Т, тогда называется гомоморфизмом моноидов. Биективный ( Иньективний, Сюрьективний) гомоморфизм называется изоморфизмом (Эпиморфизм , Мономорфизм). Например, отображение  является мономорфизмом с . Основное отличие полутруп от групп, как мы сейчас увидим, заключается в том, что понятие «ядро гомоморфизма» не играет привычной нам роли, и вообще не является корректно определенным, если вторая полутрупа вообще не содержит нейтрального элемента. Это приводит к тому, что для определения понятия фактор полугруппы нам понадобится вспомогательное понятие конгруэнции. 2.3 Конгруэнции на полугруппах.               Пусть обозначает некоторую полутруп. Конгруэнцией на S называется отношение екивалентности (то есть, разбиение S на подмножества - классы эквивалентности), инвариантно относительно левого и правого умножения на элементы S. Последнее означает, что для конгруэнции  на S и для произвольных элементов  с . следует  и  . Например, для полугруппы отношения "быть элементами одинаковой четности" является, как легко видеть, конгруэнция. Основным свойством конгруэнции является следующее свойство, необходимое для определения понятия фактора полугруппы. Лемма 6. Пусть обозначает некоторую конгруэнцию на полугруппе . Тогда с  и . следует ( ac, bd ) . Доказательство. Поскольку  является конгруэнцией, имеем: с  следует (ac, bc, с (с, d), следует (bc, bd ) . Следовательно (ас, bd ) , поскольку  транзитивно, как отношение эквивалентности.                2.4 Фактор полугруппы.               Пусть  обозначает некоторую конгруэнцию на некотором полугруппа . Рассмотрим множество S /   , которая состоит из классов эквивалентных элементов, и определим на ней операцию следующим образом:  , где  обозначает класс эквивалентности в , к которому принадлежит x. Лемма 7. Операцию   определено корректно, то есть она не зависит от выбора представителя в классе эквивалентности. Доказательство. Утверждение эквивалентно тому, что из и  следует , но это является содержанием Леммы 6.  Ассоциативность операции естественным образом вытекает из ассоциативности *. Итак,  образует полугруппу, которая называется фактор полугруппой полугруппы S по конгруэнцией . Основной нашей целью в данный момент является аналог теоремы о гомоморфизм для групп. Для формулировки подобного утверждения мы сначала определим на полугруппы каноническую конгруэнцию, связанную с гомоморфизмом ( "ядро гомоморфизма»). Пусть обозначает некоторое гомоморфизм полугрупп. Определим ядро гомоморфизма, как следующую конгруэнцию  тогда и только тогда, когда  f (а) = f (b). Утверждение 1. Пусть  обозначает некоторое гомоморфизм полугрупп, а  обозначает ядро f . Тогда полугруппа  изоморна образа f. Доказательство. Естественное отображение / с S / Pf к образу / очевидным образом корректно определено и биективно. Оно также наследуют свойство / быть гомоморфизмом, а потому изоморфизмом. □               Заметим несколько деталей: во-первых, фактор полугруппа моноида всегда будет моноидом, нейтральным элементом которого будет класс эквивалентности, содержащий нейтральный элемент начальной полугруппы; во-вторых, фактор полугруппы некоторой полугруппы без нейтрального элемента может сам уже содержать нейтральный элемент, например, если конгруэнция тривиальная и состоит из одного класса; в-третьих, фактор полугруппа полугруппы, не является группой, может сама уже быть группой, например, фактор полугруппа (N, +) по конгруэнцией "иметь одинаковую четность" очевидным образом изоморфна группе Z 2 . 2.5 Степень полугруппы.               Пусть  обозначает некоторую полутруп. Рассмотрим множество P(S) всех подмножеств множества S (так называемый булеан S) и продолжим на P(S) операцию естественным образом: для  положим А * В = {a * b | а А, b В}. Опять же, ассоциативность полученной операции очевидна и мы получаем полутруп, которая называется степенью полугруппы S. Полугруппа P(S) имеет очевидный присоединен нулевой элемент (это означает, что произведение двух ненулевых элементов в P(S) снова является ненулевым элементом, а следовательно , P(S)|{} является полугруппа). Если S имела нейтральный элемент, скажем е, тогда и P(S)будет нейтральный элемент {е}. 2.6 Фактор степени полугруппы преобразований.               Сейчас мы совместим приведенные выше понятия фактор полугруппы и степени для определения одной интересной конструкции для полугрупп преобразований. Пусть S является некоторой полугруппы (частичных) преобразований, действующая на некотором множестве X (то есть, S является подполугруппой (Х) или (Х)). Рассмотрим P(S)и определим на ней отношение эквивалентности ~ следующим образом: для  А,В  S положим А ~ В тогда и только тогда, когда для любого х  X множества А(х) = {а ( х)| аА} и В(х) = {b ( х) | b В } совпадают. Лемма 8. Отношение ~ является конгруэнцией на P(S). Доказательство. Для А,В  P(S)и для х  X имеем  = А(В(x)), не зависит от выбора представителя в классе эквивалентности, согласно определению ~.