Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
[A -U Af & В -U В'] => [AB U А'В'].
Обозначим через Mi множество образов всевозможных элементов M при отображении ф. Рассмотрим следующее отношение SR на М: A1SIA2 тогда и только тогда, когда A1 и A2 имеют один и тот же образ. Это отношение — эквивалентность; оно дает разбиение множества M на непересекающиеся классы. Обозначим через A, В, С, ... классы элементов А, В, С, ... соответственно. Очевидно, что существует естественное отображение ф множества M на M/SR, сопоставляющее каждому А є M его класс Д.
Кроме того, существует взаимно однозначное соответствие между множеством M/SR и множеством Mi образов элементов М. Классу A всех элементов, образом которых является А', отвечает сам элемент А', и обратно.
Возьмем в классе А, состоящем из_элементов, имеющих образ А', два элемента Ai и A2, и в классе Я, состоящем из элементов с образом В', — два элемента ?i и B2. Поскольку ф — гомоморфизм, имеем
Ф(Л,0,) = Ф(Л,)Ф(В,) = Л'В' =
= ф(Л2)ф(В2) = ф(Л2В2).
Результаты композиции AiBi и A2B2 имеют один и тот же образ и, следовательно, принадлежат одному и тому же классу относительно SR. Класс, которому принадлежит результат композиции Двух элементов, зависит только от классов этих элементов. Итак, Доказана204
Часть III. Алгебраический подход
Теорема. Всякому гомоморфизму ср полугруппы с единицей M на или в другую полугруппу с единицей можно поставить в соответствие конгруэнцию Si, определяемую совпадением образов.
Конгруэнция Si приводит нас к ситуации, описанной_в п. 13.1.2: существует естественный гомоморфизм M на M/Зі = М, где M — также полугруппа с единицей.
Взаимно однозначное соответствие 9 между M и Mj (множеством образов) перестановочно с операциями композиции:
L е-1 е-1 IL е-1
Таким образом, 9 является изоморфизмом.
В итоге мы получаем следующую схему:
м
13.1.4. Классификация гомоморфизмов
Сохраним здесь обозначения, введенные в предыдущем пункте. Рассмотрим отображение ср более подробно; имеются следующие возможности:
1) ф не сюръективно. Если существуют элементы множества M', не являющиеся образами никаких элементов из М, то мы имеемГ л. XIII. Г омоморфизм полугрупп
205
строгое включение:M'с= M', MiфMi. Тогда о <р следует говорить как о гомоморфизме множества M строго в M'. В качестве иллюстрации этой ситуации см. следующий рисунок:
2) ф сюръективно. Если всякий элемент M' есть образ какого-либо элемента М, то M' = Mi, и ф есть гомоморфизм M на M' или, короче, эпиморфизм:
3) ф инъективно. Если образ А' всякого элемента А является образом только этого элемента, говорят, что ф — мономорфизм M в M':206
Часть III. Алгебраический подход
4) ф биективно (взаимно однозначно). Если всякий элемент множества M' является образом одного и только одного элемента множества М, говорят, что ф — изоморфизм M на M':
Примеры. 1. M — свободная полугруппа над алфавитом Я и M' — полугруппа (в данном случае — группа), состоящая из двух элементов {р, і} и определяемая следующей таблицей:
+ P і
P P і
і I P
Отображая цепочки четной длины на р, а цепочки нечетной длины на і, мы получим эпиморфизм.
2. M — полугруппа целых неотрицательных чисел относительно сложения; M' — свободная полугруппа над {а,Ь}. Отображая нуль в пустую цепочку, 1—в а, 2 — в аа, п — в ап, мы получим мономорфизм.
Случай совпадения M с M'. Когда гомоморфизм ф отображает полугруппу M в (возможно, на) себя, ф называется эндоморфизмом; если при этом ф — изоморфизм, он называется автоморфизмом.
Однако взаимно однозначное отображение множества M на его собственное подмножество, перестановочное с композицией, называют по-прежнему мономорфизмом. Заметим сразу же, что такие мономорфизмы существуют.
Пример. М — свободная полугруппа с единицей над {а, Ь}. Каждой цепочке ставится в соответствие цепочка, получаемая і двоением каждой буквы: а-*аа, ab-*aabb, abb -^aabbbb и т. д. Это отображение взаимно однозначно и перестановочно с конкатенацией.
13.1.5. Ядро гомоморфизма
Будем считать, что полугруппы M и M' обладают каждая единичным элементом E и E' соответственно (быть может, после добавления такового). Пусть ф — гомоморфизм множества M в (возможно, на) M'; положим ф(?) = E1.Г л. XIII. Г омоморфизм полугрупп
207
Тогда
ф(?Л) = Ф(?)Ф(Л) = ?,Ф(Л);
Ф(Л?) = Ф(Л)Ф(?) = Ф(Л)?,,
Далее, EA = AE = А (поскольку E — единичный элемент); следовательно,
?1ф(Л) = фМ)?, = ф(Л).
Таким образом, Ei является единицей для полугруппы Mi — множества образов; однако из этого без дополнительных предположений еще не следует, что Ei = ?', т. е. что Ei — единица полугруппы M'.
Можно утверждать, что Ei = ?', если известно, что E' є Mt (в частности, если гомоморфизм является эпиморфизмом). В самом деле, в Mi имеем
EfEi = Ei в силу того, что E' — единица;
EfEi = E' в силу того, что Ei — единица; отсюда Ei = ?'.
В дальнейшем всюду, если не оговорено противное, мы будем считать, что Ei = ?'.
В теории групп ядром гомоморфизма ф, отображающего группу G в (возможно, на) группу G', называют множество H элементов группы G, имеющих в качестве образа единичный элемент группы G'. Классический результат теории групп гласит, что ядро является подгруппой группы G' и его задание полностью определяет гомоморфизм.