Дискретная математика

36 Таким образом, отображение гр; А В сохраняет операцию. Но это отображение не является изоморфным, так как различные матрицы могут иметь одинаковый определитель. Итак, g j - гомоморфизм А на В. § 5. Алгебра с одной операцией Самой простой алгеброй является непустое множество G с одной двуместной (бинарной) операцией, т.е. для любых а.Ье G определен результат операции а°Ь е G. Множество с одной двуместной операцией называют группоидом. Полугруппа - это множество G, на котором введена одна ассоциативная двуместная (бинарная) операция, т.е. для Va,b,ce G: a °(b°c)= (a°b)°c. Таким образом, полугруппа это группоид, в котором операция ассоциативна. Рассмотрим примеры. 1. Пусть Я - алфавит. Множество всевозможных слов в алфавите обозначим через Л". Если Р ш Q - слова в алфавите ^4, то их сцепка (конкатенация) PQ тоже слово в алфавите А. Ясно, что множество слов Л образует полугруппу относительно операции конкатенации. 2. Пусть Р - множество полиномов вида ао+а/х+агХ^+.-Ла^", где Л; — любые действительные числа (0<г ^п, п >0). Тогда множество Р является полугруппой относительно, например, сложения полиномов или относительно умножения полиномов. Моноид - это полугруппа с единицей; Эе(е е G), что для Va из G: е°а=а°е-а. Рассмотрим примеры. 1. Пусть множество слов в алфавите А. Введем пустое слово (слово без букв) jf и положим Л''=А*и {г}. Тогда с Операцией конкатенации слов образует моноид. Роль единицы играет пустое слово. 2. Пусть Г - множес1во некоторых переменных. Полстацонкон, или заменой переменных, называется множество пар G={lk/vk^, Результатом применения подстановки к переменной будет выражение, полученное заменой на 1 </ <г. Композицией подстановок G; и Gj называется последовательное применение сначала G;, затем Множество подстановок с операцией композицией подстановок образует моноид, единицей которого является тождественная подстановка, в которой вместо ti- подставляется ^ (\ </ й-,). Теорема 2.2. Единица моноида единственна