1.6.1. Операции на множествах
Частным случаем функции является операция, т.е. функциональное отображение вида:Mn М, гдезнак отображения. Такая функция называетсяn-арной операцией, в ней области определения аргументов и область значений функции совпадают,n- местная операция поnэлементам множества определяет (n+1)-й элемент этого же множества.
АлгебройА называется совокупность<>множества М с заданными на нем операциямиS={11,12,...1n1,21,...2n2,m1,m2, ...mnm}, А=<м,S>, где множество м - носитель,S- сигнатура алгебры. Первый каждый индекс у идентификатора операции указывает ее местность.
Алгебра типа <м,2>, т.е. алгебра с бинарной операцией, называетсягруппоидом.
Рассмотрим квадрат с вершинами с точках а1,а2,а3,а4, пронумерованных против часовой стрелки, а повороты квадрата вокруг центра также против часовой стрелки, переводящие вершины в другие вершины. Таких поворотов бесконечное множество: на углы 0,,, 3, 2, 5, ..., однако они задают всего четыре различных отображения множества вершин в себя, соответствующих первым четырем поворотам.
Можно сказать, что задана алгебра А=<м,1>с основным множеством М={а1,а2,а3,а4}и четырьмя унарными операциями ММ, которые обозначим буквами,,,. Зададим эти операции таблицей 1.1.
Табл.1.1. Унарные операции алгебры
поворотов квадрата
-
а1
а1
а2
а3
а4
а2
а2
а3
а4
а1
а3
а3
а4
а1
а2
а4
а4
а1
а2
а3
0
3
Можно интерпретировать такие операции также циклическими сдвигами вида:
а1а2а3а4.
Множество 0={,,,}отображений вершин в себя вместе с бинарной операцией 020 последовательного выполнения отображений (выполнения поворота за поворотом, композиции поворотов), которую обозначим символом о, образует алгебру с бинарной операцией<0,о>. Она задается таблицей 1.2, в которой на пересечении строкиiи столбцаjзаписан результат операцииioj.
Табл.1.2. Бинарные операции 020 алгебры
композиций поворотов квадрата
-
i
j
ioj
Такая таблица 1.2, задающая бинарную операцию, называется таблицей Кэли.
Можно представить бинарной операцией, например, смешивание красок, когда из двух цветов получается третий, входящий, однако во множество всех цветов.
Пусть А=<М,2>- группоид, обозначим как и в предыдущем примере2какo.
Тогда элемент nМ называется правым нейтральным элементом группоида А, если для всякого mМ выполняется равенствоmoc=m.
Для левого нейтрального элемента выполняется равенство nom=m.
В дальнейшем для краткости вместо слов "все", "всякий" будем использовать символ (перевернутая буква А - первая буква английского словаAll- все, этот символ называется еще квантором общности; квантор существования обозначаетсяи означает "существует", "имеется", "есть").
Элемент n, являющийся одновременно и левым, и правым нейтральным элементом, называют двухсторонним нейтральным элементом или просто нейтральным элементом.
Для смешивания красок нейтральный элемент - бесцветный лак.
Если группоид <М,о>мультипликативный, т.е. его бинарная операция о имеет тип умножения (х), то нейтральный элемент называетсяединицейи обозначается 1, если группоид аддитивный, т.е. бинарная операция о имеет тип сложения (+), то нейтральный элемент называетсянулеми обозначается 0. Нейтральный элемент в группоиде всегда единственный.
Коммутативный группоид, т.е. группоид, в котором
(х,yМ)(хоy=yох),
называется коммутативнымилиабелевым.
Группоид, в котором выполняется закон ассоциативности
(х,y,zМ)(хо(yоz)=(xоy)оz),
называется ассоциативнымили полугруппой.
Полугруппа с единицей называется моноидом. В алгебре поворотов квадрата (табл.1.2) единицей служит поворот на нулевой угол ().
Группойназывается полугруппа с единицей, в которой для каждого элемента а существует элемент а-1, называемый обратным и удовлетворяющий условию аоа-1=а-1оа=n.
В алгебре поворотов квадрата (табл.1.2), являющейся группой обратным к данному повороту является поворот, дополняющий его до 2:
-1=,-1=,-1=.
Группа, все элементы которой являются степенями одного элемента а, называется циклической. Циклическая группа всегда абелева.
Множество рациональных чисел, не содержащее нуля, с операцией умножения является абелевой группой. Обратным к элементу а является элемент .