XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 19
Текст из файла (страница 19)
Мы применили понятие нульарной операции, чтобы в обозначении алгебры отразить элементы со специальными свойствами. г. Все предыдущие примеры алгебр были алгебрами с конечной сигнатурой, т.е. с сигнатурой, состоящей из конечного 2.1. Оиерацни. Поиетие алгебраической структуры 119 числа операций. Однако несложно построить пример алгебры с бесконечной сигнатурой.
Например, алгебра Ае = (Ж, ('(". и ) 2)) на множестве действительных чисел Й с операцией )" возведения в натуральную степень п > 2 имеет счетпнрю сигнатуру. Далее будут приведены примеры алгебр и с несчетными сигнатурами. Определяя алгебру, следует помнить, что результат применения любой операции обязательно должен принадлежать тому же множеству, что и ее аргументы. Например, пару ю множества тэ всех свободных векторов в пространстве и операции скалярного умножения векторов нельзя рассматривать как алгебру, так как скалярное проюведение двух векторов не есть вектор. Заменив скалярное умножение векторным, получим алгебру.
Кроме того, нельзя забывать, что и-ариан операция, как и всякое отображение, должна быть определена для любого кортежа длины и элементов множества. Поэтому не является алгеброй множество всех матриц с операциями сложения и умножения матриц, так как эти операции определены не для любой упорядоченной пары матриц. Если же при тех же операциях ограничиться множеством квадратных матриц фиксированного порядка а, то получим алгебру. Точно так же множество действительных чисел Й с операцией: деления действительных чисел не является алгеброй, поскольку результат деления не определен прн нулевом делителе. Пара же (Ж'1(01, 1:)) есть алгебра. Договоримся, определяя конкретную алгебру, записывать ее сигнатуру без фигурных скобок, перечисляя после обозначения носителя все операции. Так, в примере 2А.а первая алгебра может быть записана как А1 = (2м,0,й,'1, э,,я,М).
Для алгебры А = (А, й) обозначим через й<"> подмножество сигнатуры й, состоящее из всех и-арных операций. Тогда й = 120 2. АЛГЕБРЫ: ГРУППЫ И КОЛЪЦА = („) Йд"). Так, для алгебры Ад в примере 2.4.а будем иметь: в)0 Й<0) (,д М) ЙОО =Г) Йд2) =1О,д'),'д,ь), Й(") = и при дд ) 2. Определение 2.3. Две алгебры Ад = (Ад, Йд) и Аз = = (Аз, Йз) называют одмоддднпнььми, если существует такая биекддия Йд на Йз, при которой дд-ариан операция из Йд для любого и переходит в и-арнудо из Йз. Пример 2.5.
Алгебра (2~, О, Г), Ед, М), заданнал на множестве всех подмножеств множества М, и алгебра Аз = = ()а, +,, О, 1) (см. пример 2.4.в), заданная на множестве действительных чисел, однотипны. Биекцию (взаимно однозначное соодввевдсвдвив) между их сигнатурами, которвл сохраняла бы арность операций, можно определить и так: О н +, Г) н, О н О, М н 1. Указанный способ задания биекции не единственный. Например, ее можно определить так: Он, Пн+, Ин1, МнО. Алгебра (2~, О, д'), И, М) и алгебра Ад в примере 2.4.а не являются однотипными, так как их сигнатуры состоят из разного числа операций и между ними установить взаимно однозначное соответствие нельзя. Не являются однотипными и алгебры (2~, ) и (Я, +), ибо в первой алгебре единственная операция ее сигнатуры является унарной, а во второй — бинарной. ф Нередко сигнатуры однотипных алгебр и элементы этих сигнатур — операции — обозначают одинаково. Так, мы пидпем (Ж, +,, О, 1) и Я, +,, О, 1), хотя первая алгебра задана на множестве всех действительных чисел, а вторвл — на множестве рациональных чисел, и, например, сложение в первой алгебре, строго говоря, не есть та же самая операция, что сложение во второй алгебре.
В общем случае мы часто будем 121 2.2. Ц>улявядм, полугруппм, грулпы говорить о различных (но однотипных) Й-алгебрах, заданных на разных носителях, понимая, что Й есть общее для всех этих влгебр обозначение их сигнатур. 2.2, Группоиды, полугруппы, группы Рассмотрим алгебры, сигнатпуры которых состоят из одной.
бинарной оперении. Эту операцию будем обозначать точкой ( ) и условно называть в этом случае умножением. Группоидом называют любую алгебру Д = (С, .), сигнатура которой состоит иэ одной бинарной операции. В группоиде на бинарную операцию нет никаких ограничений. Групцоид (С, ) называют полугруппоб, если его операция ассоииашивна, т.е. для любых элементов а, 6, с носищелл С выполняется равенство а.
(Ь. с) = (а Ь) . с. Пример 2.6. а. Множество 1~2 свободных векторов вместе с операцией векторного умножения является группоидом, но не полугруппой, так как векторное умножение не ассоциативно. б. Множество натуральных чисел вместе с операцией возведения в степень также будет только группоидом, так как (аь) ф а(ь ). в. Множество 2Я всех подмножеств множества А вместе с операцией 1 (раэностпь множеств) тоже только группоид, поскольку указанная операция не ассоциативна. г.
Множество натуральных чисел М вместе с операцией сложения будет полугруппой. ф Группоид 0 = (С, ) называют моноидом, если его операция ассоциативна и относительно операции существует нейтральный элементп. Его называют нейгпральным элеменпьом моноида Д или единицей моноида и обозначают 1. Таким образом, моноид Д = (С, ) есть полугруппа, в которой для любого а имеют место равенства а 1 = 1 а = а, где 1 — нейтральный элемент (единица) моноида. 122 2.
АЛГЕБРЫ: ГРУППЫ И КОЛЬЦА Поскольку нейтральный элемент относительно любой бинарной операции является единственным (см. 2.1), мы можем рассматривать моноид как алгебру (С,, 1), сигнатура которой состоит из двух операций: бинарной операции (умножение) и нульарной операиии 1 (нейтрального элемента). Введение 1 в сигнатуру моноида удобно тем, что зачастую при рассмотрении конкретных примеров моноидов целесообразно явно указать нейтральный элемент относительно его операции. Например, алгебра (2А"А, о, ЫА) есть моноид всех бинарных отношений на множестве А с операцией комнозииии бинарныя отношений, в котором нейтральным элементом является диагональ множества А. Среди полугрупп выделяют полугруппы с коммутативной операцией — коммутпатпиеные полуеруппы.
Пример 2.7. а. Множество всех бинарных отношений на произвольном множестве А с операцией композиции отношений будет моноидом, нейтральным элементом которого служит диагональ множества А, поскольку для любых бинарных отношений р, т и а на множестве А имеют место равенства (см. 1.4) р (т <т)=(р т) оиЫА р=р Ыл=р. б. Множество всех отображений некоторого множества А в себя по операции композиции отображений есть моноид. Напомним, что композиция отображений снова есть отображение и операция композиции имеет нейтральный элемент: щоэсдес~иеенное отиображение А на себя. Поскольку любое отображение множества А в себя можно рассматривать как бинарное отношение на этом множестве, а композицию отображений — как частный случай композиции отношений, требуемые свойства операции композиции отображений выполюпотся (см.
пример 2.7.а). При этом тождественному отображению соответствует диагонапь ЫА множества А. Этот моноид называют часто симметрическим моноидом или симметрической полугруппой множества А. 123 3.2. Цзушюилы, полугрупвы, группы в. Алгебра (1Чв, +), где носитель — множество 1Чв неотрицательных целых чисел, а сигнатура состоит ю одной операции сложения, есть коммутативный моноид, в котором нейтральный элемент — зто число О. Действительно, сумма двух натуральных чисел есть натуральное число, операция сложения ассоциативна, коммутативна и для любого натурального числа и имеет место равенство и+ О = и. Обратим внимание на то, что свойства нейтральных элементов и нулей ассоциируются со свойствами чисел 1 и О относительно операций умножения и сложения чисел. г.
Алгебра (Е, ), у которой носителем являетсл множество целых чисел, а сигнатура состоит ю одной операции умножения, есть коммутативный моноид. Нейтральным элементом этого моноида является число 1. д. Пусть А — конечное множество, а А" — множество кортежей длины и. На множестве всех кортежей А+ = Ц А" в)1 определим операцию соединения (коккажекацпк) корпзежеб следующим образом: (ам ..., а,в).
(Ь|, ..., Ьь) = (ам ..., ав„Ьм ..., Ьл). Можно видеть, что введенная операция ассоциативна, но не имеет нейтрального элемента. Таким образом, построена полугруппа,но не моноид. Чтобы превратить эту полугруппу в моноид, расширим носитель полугруппы, введя понятие нулеаок декарпзовоб суаекекп Ав произвольного множества А. Под Ав понимают одноэлементное множество 1Л), единственный элемент которого называют кусжььк корпзежем. Такое определение множества Ав объясняется следующим: мощность положительной декартовой степени А" конечного множества равна ~А~".
При и = О должно быть! А~~ = ~А~~ = 1, откуда заключаем, что А— одноэлементное множество. Обозначив А' = Ав 0 А+, по определению для любого х Е А' полагаем х Л = Л х = х. В результате получим алгебру 124 2. АЛГЕБРЫ: ГРУППЫ И КОЛЬЦА (А*, ), являющуюся моноидом, с нейтральным элементом Л.
Его называют свободным мопедом, порожденным множе- ством А. =р " рь = р " р)', а1 аз д1 д» 71 РЪ* где набор простых чисел рм ..., рь выбран одинаковым для всех трех чисел, а некоторые из показателей а;, Д и у;, 1 = 1, Ь, могут быть равными нулю. Тогда для чисел т и и имеем ПОКА ~ твх(сц лП пах(амдв) п~т р1 рь Таким образом, ассоциативность операции НОК сводится к ассоциативности операции п1ах вычисления наибольшего из двух натуральных чисел.
Ассоциативность последней вытекает из очевидного тождества шах(а,шах(Ь,с)) = шах(шах(а,Ь),с), верного для любых чисел а, Ь и с. Поскольку НОК(п,т) = НОК(т,п), операция НОК коммутативна, а так как для любого натурального числа справедливо равенство НОК(п, и) = и, то операция идемпотентна. в. Алгебра (г(, НОД), где НОД вЂ” операция вычисления наибольшего общего делителя двух целых чисел, также является полурешеткой. ф Полугруппу, операция которой коммутативна и идемпотентпна, называют полурешеткой. Пример 2.8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
