Научная литература
booksshare.net -> Добавить материал -> Лингвистика -> Гросс М. -> "Теория формальных грамматик " -> 69

Теория формальных грамматик - Гросс М.

Гросс М., Лантен А. Теория формальных грамматик — М.: Мир, 1971. — 296 c.
Скачать (прямая ссылка): teoriyaformalnihgrammatik1971.djvu
Предыдущая << 1 .. 63 64 65 66 67 68 < 69 > 70 71 72 73 74 75 .. 101 >> Следующая


[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' и его задание полностью определяет гомоморфизм.
Предыдущая << 1 .. 63 64 65 66 67 68 < 69 > 70 71 72 73 74 75 .. 101 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed