Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 73
Текст из файла (страница 73)
Таким образом, для 1,д е 5 результат операции 1 о д определяется как (1 о д)(а) = 1(д(а)) для всех а я А. Поскольку для 1,д,Ь Е 5 имеет место ((1од)сЬ)(а) = (Уо(дс"))(а) = 1(д(Ь(а))) для всех а е А, то (1 од) сЬ = 1 о(до 6), поэтому 5 — полугруппа. Далее функция 1; А — А, определенная как 1(а) = а для всех а е А, является единицей в 5 и, следовательно, 5 — моноид. П РАЗДЕЛ 9.2. Лолугруппы и полурешетки 399 ПРИМЕР 9.16. Пусть А — конечный набор символов. Такое множество символов называется алфавитом. Например, А могло бы быть подмножеством английского алфавита или просто множеством (О, Ц.
Строка или слово символов из множества А имеет вид агагаза4... а„, где а; Е А. Таким образом, если А = (О, Ц, то 1, 100, 101, 11011 и 0001 — возможные строки символов из множества А. Кроме того, определим пустую строку, которая обозначается Л и не содержит никаких символов. Пусть А' обозначает множество всех строк алфавита А. Введем бинарную операцию о, называемую конкатенацией на А', следуюшим образом: если а1агазаг...а„и ЬгбгЬз64...6 Е А', то а,агазаг... а„о ЬгЬгЬзЬг Ь = а|агазаг...
а„ЬгЬгЬзЬг .6 Например, если А = (О, Ц, то 11011 о 100010 = 11011100010. В частности, если ш — строка в А*, то Л о ш = ш о Л = ш, и это говорит о том, что если строке предшествует пустая строка или пустая строка следует за ней, то в результате конкатенации получаем ту же самую строку. ПУсть агаг...а„, 61Ьг...Ь и с|сг...ср Е А'. Тогда (а1 аз ... а„ о 616г ... Ь ) о с1 сг ... ср — †(а1 аз ... а„ о 616г ... Ь ) о с1 сг ... ср —— = а1аг...
а„ЬгЬг... Ь о с1сг... ср —— =а1аг...а„616г...Ь с1сг...ср —— = а1аг... а„о Ь|6г... 6 с1сг... ср —— = а|аг .. а„о (6|Ьг .. Ь,„о с1сг .. ср), и бинарная операция конкатенации ассоциативна на А*, так что множество А вместе с операцией конкатенации представляет собой полугруппу. Далее, поскольку Л вЂ” это единица, то А' — моноид.
Заметим, что этот моноид с очевидностью некоммутативен. Если А С А, то А — подполугруппа полугруппы А*. Полугруппа А'называется свободной полугруппой над алфавитом А. П ПРИМЕР 9.17. Пусть Я„= ([0], [1], [2],..., [и — 1]) — множество классов вычетов по модулю и (см. раздел 3.6). Согласно теореме 3.54 (Я„, +) и (У„, ) вполне определены. Предоставляем читателю доказать, что (Я„, +) и (У„,.) являются полугруппами. С) Пусть (Я,.) — полугруппа, и а Е Я. Определим а" рекурсивно, полагая ао = 1 и а" = а .
а" '. Отсюда непосредственно следует, что а' = а. Предлагаем читателю, используя метод индукции, показать, что а" . а = а~+ для всех целых чисел 1,т > О. Множество (а) = (а": и > О) = (1,а аг,а,...) является подполугруппой полугруппы Я. ОПРЕДЕЛЕНИЕ 9.18. Полугруппа (а) называется циклической полугруппой. Точнее, она называется циклической полугруппой, порожденной а.
400 ГЛАВА 9. Алгебраические структуры Доказательство следующей теоремы оставляем читателю. ТЕОРЕМА 9.19. Пусть (5, ) — полугруппа и а1,аз,аз,...,аь е 5. Пусть А = (а1,аз,аз,...,аь~ и А' = (а1,аз,аз,...,а1,.) — множество, состоящее из всех конечных произведений а1, а2, аз, аь. Тогда А' — полугруппа. Более того, А'— наименьшая подполугруппа полугруппы Я, содержащая А. ОПРЕДЕЛЕНИЕ 9.21. Пусть (5,.) и (Т,О) — полугруппы и У'; 5- Т вЂ” такая ФУНКЦИЯ, Чта Г"(г г') = Г"(г) с 1(г'). ФУНКЦИЯ )' НаЗЫВаЕтСЯ гОМОМОРфиЗМОМ из Я в Т. ТЕОРЕМА 9.22. Пусть (5,.) и (Т,О) — полугруппы и г": 5 — ~ Т вЂ” гомоморфизм из О в Т.
Если Я вЂ” подполугруппа полугруппы Я, то Г"(5) — подполугруппа полугруппы Т. ДОКАЗАТЕЛЬСТВО. Пусть т, 1' б ДЯ). Существуют такие г, з' Е Я, что )'(з) = 1 и у(з') = 1'. По определению полугруппы з.з' Е Я. По определению гомоморфизма Г"(з г') = Г"(з) о Г"(г') = 1. г', т.е. 2 г' Е Г'(О) и Г'(5) — полугруппа, Доказательство приведенной ниже теоремы оставляем читателю.
ТЕОРЕМА 9.23. Пусть (Я,.) и (Т, о) — полугруппы и г": Я вЂ” ~ Т вЂ” гомоморфизм из Я в Т. Если Т вЂ” подполугруппа полугруппы Т, то )' '(Т) — подполугруппа полугруппы Я. ОПРЕДЕЛЕНИЕ 9.24. Пусть (5, ) — полугруппа и  — отношение эквивалентности на Я. Если Л обладает свойством, что если з1йзз и ззВз4, то выполняется з1гзгсгзг4 для всех г1,гз,зз,г4 е 5, тогда Л называется отношением конг руан т наст и. ТЕОРЕМА 9.25.
Пусть (Я, ) и (Т, о) — полугруппы и )': 5 — Т вЂ” гомоморфизм из 5 в Т. Определим отношение Я на множестве 5 таким образом: зЛз', если г"(з) = г"(з'). Тогда отношение  — отношение конгруэнтности. ДОКАЗАТЕЛЬСТВО. Для всех г е Я г'(г) = г"(з), поэтому Л вЂ” рефлексивно. Если г"(з) = г"(з'), то )'(г') = )'(з), и  — симметрично. Если г'(з) = г"(з') и ((г') = ((гл), та 2 (З) = ((гл), ПОЭтОМу В траиэнтИВНО. ДОПуСтИМ, г1ВЗ2 И ЗЗЛЗ4, Следовательно, г"(з1) = г"(гз) и г"(гз) = г(з4).
Учитывая, что У вЂ” гомоморфизм, получаем 2 (з1. зз) = 2 (з1) О 2 (зз) и 1 (г1 зз) = 2 (г1) о 2 (зз) = 2 (г2) о 2 (з4) = 2 (г2 г4), поэТОму г1 ' ззлг2 ' з4 РАДЕЛ 9.2. Попуаруппы о попурешетки 401 ОПРЕДЕЛЕНИЕ 9.26. Коммутативная полугруппа (5, *) называется полурешеткой, если а *а = а для всех а е Я. Элемент а полугруппы называется идемлоглеипгом, если а*а = а. Таким образом, полурешетка — это коммутативная полугруппа, в которой каждый элемент является идемпотентом. Если (Я, *) — полурешетка и 5 С Я, то Я будет подполурешеткой полурешетки (Я, *), если * — бинарная операция на Я.
Эквивалентно, (Я,*) — подполурешетка полурешетки (Я, *), если Я С Я, и для всех а, Ь е о имеем а * Ь Е Я. Из теоремы 9.10 следует, что верхние и нижние полурешетки являются полу- решетками. Более того, каждую полурешетку можно рассматривать как верхнюю или как нижнюю полурешетку. ТЕОРЕМА 9.27. Пусть 5 — полурешетка. Определим на Я отношение < таким образом: а < Ь, если а *6 = Ь для а,6 е Я. Тогда (5, <) — это ЧУ-множество, и а * Ь вЂ” наименьшая верхняя грань для а и Ь. Следовательно, (5,*) — верхняя полурешетка.
Аналогично, (Я, *) можно рассматривать как нижнюю полурешетку. ДОКАЗАТЕЛЬСТВО. Поскольку а * а = а для всех а е Я, а < а, поэтому (5, <) рефлексивна. Если а < 6 и 6 < а, то а * Ь = Ь и а * 6 = Ь * а = а. Поэтому Ь = а и (5, <) антисимметрична. Допустим, что а < Ь и 6 < с. Имеем а * Ь = Ь и Ь к с = с. Получаем а*с= а*(Ьи с) = = (а*Ь) вс= =Ьвс= и а < с. Следовательно, (Я, <) транзитивна и является ЧУ-множеством.
Теперь покажем, что а*Ь вЂ” наименьшая верхняя грань для а и 6. Поскольку а*(а*Ь) = (а*а) *Ь= = а*6, то а < а*6. Точно так же, Ьв(аэЬ) =Ьч (Ьэа) = = (ЬкЬ) ко = =Ь*а= =ач Ь, так что Ь < а * Ь. Поэтому а*Ь вЂ” верхняя грань для а и Ь. Предположим, что с— тоже верхняя грань для а и 6, тогда а * с = с и Ь* с = с. Следовательно, (а*6) ч с = а* (Ь*с) = =акс = и а * 6 < с. Поэтому а * Ь вЂ” наименьшая верхняя грань для а и 6, и (Я, <)— верхняя полурешетка.
402 ГПАВА д. Алгебрвические структуры ° УПРАЖНЕНИЯ 1. Пусть (5, О) — полурешетка всех подмножеств множества (а, Ь, с) с операцией объединения. Найдите три разные подполурешетки полурешетки (5, О), 2. Пусть (5, ) — полурешетка на множестве всех матриц, элементы которых— вещественные числа, а операция — матричное умножение. Найдите пять подполугрупп полурешетки (5, ). 3. Докажите, что множество положительных целых чисел вида 4?с+ 1, где й— неотрицательное целое число, образует полугруппу с операцией умножения. 4. Найдите пять подполугрупп множества положительных рациональных чисел с операцией сложения.
5. Докажите, что (2„, +) и (2„, ) являются полугруппами для любого целого числа п > 1. 6. Докажите по методу индукции, что если 5 — полугруппа и а е 5, то а" а а~~ для всех целых чисел т, п > О. 7. Докажите теорему 9.!9. Пусть (5, ) — полугруппа и аыаз,аз,...,аь е 5. Пусть А = (аыае,аз,...,аь) и А* = (а„аз,аз,...,аь) — множество всех конечных произведений аг,аз,аз,аь.
Тогда А" — полугруппа. Более того, А* — наименьшая подполугруппа полугруппы 5, содержащая А. 8. Докажите теорему 9.23. Пусть (5,.) и (Т, о) — полугруппы, и 7: 5 — Т— гомоморфизм из 5 в Т. Если Т вЂ” подполугруппа полугруппы Т, то 7" '(Т)— подполугруппа полугруппы 5. 9. Пусть (5,о) — полугруппа всех функций на множестве А с операцией композиции. а) Покажите, что множество взаимно однозначных соответствий образует подполугруппу полугруппы 5.
б) Если г" а 5 — идемпотент, то 7' о 7' = 7". Такая функция называется ретракционнмм отображением. Образ г" называется ретрактором. Покажите, что ретракционное отображение является взаимно однозначным отображением на свой образ. в) Покажите, что функции у(х) = (х), д(х) = (х) и 6(х) = (х), заданные на множестве действительных чисел, являются ретракционными отображениями. Что представляют собой соответствующие ретракторы? г) Коммутируют ли функции из пункта (в)? Иначе, верно ли, что 7од = дс7"? д) Образуют ли функции из пункта (в) полурешетку? 10.
Пусть 5 — множество действительных чисел и * — бинарный оператор, определенный соотношением а * Ь = шах(а,6). Покажите, что (5,*) — полу- группа. Является ли (5,*) полурешеткой? 11. Пусть (5, *) — множество матриц размерности п х п с операцией умножения в качестве бинарной операции. Известно, что для (и х и)-матриц А и В выполняется бес(А) . (г)есВ) = г(ес(АВ). Используя этот факт, покажите, что матрицы, у которых бес Ф О, образуют моноид.
Что можно сказать о матрицах, у которых определитель равен О? 12. Приведите пример бинарной операции * на множестве вещественных чисел, относительно которой они не образуют полугруппу. РАЗДЕЛ 9.3. Решетки 403 13. Покажите, что единица в моноиде единственна в том смысле, что существует только один элемент, например, 1 такой, что а*1 = 1*а = а для всех а в моноиде. 14. Пусть Я вЂ” множество. Определим операцию * на Я таким образом: а*Ь = Ь для всех а, Ь Е Я.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
