04. Операции на множествах и их свойства

Алгебры. Функцию типа J : будем называть П-арной операцией на множестве М; П называется Арностью Операции J. Множество М вместе с заданной на нем совоКУпностью операций , т. е. система называется Алгеброй; М называется Основным, или несущим, Множеством (или просто носителем) алгебры А. Вектор Арностей операций алгебры называется ее типом, совокупность операций W — сигнатурой.

Множество называется ЗАмкнутым относительно N-арной операции J на М, если , т. Е. Если значения J на аргументах из М' принадлежат М'. Если М' замкнуто относительно всех операций алгебры A, то система Называется Подалгеброй А (при этом рассматриваются как операции на М').

Пример 1.

1) Алгебра называется Полем действительных чисел. Обе операции — бинарные, поэтому тип этой алгебры (2, 2). Все конечные подмножества R, кроме {0}, не замкнуты относительно обеих операций. Подалгеброй этой алгебры является, например, поле рациональных чисел.

2) Пусть Nр = {0, 1, 2, ..., Р-1}. Определим на Nр Операции Å («сложение по модулю Р») и Ä («умножение по модулю Р») следующим образом: Где С и D — остатки от деления на Р чисел А + B и А × B Соответственно. Например, если Р = 7, ТО Nр= {0, 1, ..., 6}, 3 Ä 4 = 5, 4 Å 6 = 3. Часто операции Å и Ä обозначают как Если Р — простое число, то алгебра называется Конечным полем характеристики р.

3) Пусть задано множество U. Множество всех его подмножеств называется Булеаном U и обозначается через Алгебра называется Булевой алгеброй множеств над U, ее тип (2, 2, 1). Элементами основного множества этой алгебры являются множества (подмножества U). Для любого Является подалгеброй В. Например, если То основное множество алгебры В содержит 16 элементов; алгебра — подалгебра В; ее основное множество содержит четыре элемента.

4) Множество F одноместных функций на R, т. Е. Функций F : R ® R, вместе с операцией дифференцирования является алгеброй. Элементы основного множества — функции типа R ® R, единственной операцией этой алгЕБры служит дифференцирование — унарная операция типа (производной функции на R является снова функция на R). Множество элементарных функций (см. пример 10, П. 1.2.) замкнуто относительно дифференцирования — производные элементарных функций элементарны — и, СледоваТельно, образуют подалгебру данной алгебры.

5) Рассмотрим квадрат с вершинами в точках и повороты квадрата вокруг центра (против часовой стрелки), переводящие вершины в вершины. Таких поворотов — бесконечное множество: на углы однако, они задают всего четыре различных отображения множества вершин в себя, соответствующих первым четырем поворотам. Таким образом, получаем алгебру с основным множеством и четырьмя унарными операциями . Их можно задать таблицей 1, в которой на пересечении, например, строки и столбца G написано значение функции .

Операция A, отображающая любой элемент в себя, называется тождественной операцией. Она соответствует нулевому повороту. Подалгебр в этой алгебре нет.

6) Множество отображений вершин в себя из предыдущего примера вместе с бинарной операцией ◦ композиции отображений (см. п. 1.2) образует алгебру . Элементами множества О являются отображения (повороты). Композиция отображений — это последовательное выполнение двух поворотов. Она задается таблицей 2 (в ней на пересечении строки A и столбца G написан результат композиции ).

Такая таблица, задающая бинарную операцию, называется таблицей Кэли. Множество , т. е. повороты 0, P, образует подалгебру алгебры .

Свойства бинарных алгебраических операций. Для того чтобы последующие соотношения выглядели более привычно условимся результат применения бинарной операции J К элементам А, B записывать не в функциональном Виде , а в виде АJ B, так, как это принято для Арифметических операций.

Операция J называется Ассоциативной, если для любыХ ЭлЕМентов А, B, с

Выполнение этого условия (свойства ассоциативности) оЗНачает, что скобки в выражении можно не расставлять. Сложение и умножение чисел ассоциативны, что и позволяет не ставить скобки в выражениях А + B + С и АBс. Пример неассоциативной операции — возведение в степень Правда запись считается допустимой, но служит сокращением выражения , а не Которое равно более компактному выражению

Важным примером ассоциативной операции является композиция отображений.

Операция J называется Коммутативной, если для любых элементов А, B

Сложение коммутативно («от перемены мест слагаемых сумма не меняется»), так же как и умножение; вычитание и деление некоммутативны. Некоммутативным является умножение матриц, например

но

Операция J называется Дистрибутивной слева относительно операции F , если для любых А, B, с

И Дистрибутивной справа относительно F, если

Дистрибутивность разрешает раскрывать скобки. НАПример, умножение дистрибутивно относительно сложения слева и справа. Возведение в степень дистрибутивно относительно умножения справа: но не слева: Сложение не дистрибутивно относительно умноЖЕния: Как будет показано позднее, операциИ пересечения и объединения множЕств дистрибутивны относительно друг друга слева и справа.

Гомоморфизм и изоморфизм. Алгебры с разными типами, очевидно, имеют существенно различное строение. Если же алгебры имеют одинаковый тип, то наличие у них сходства характеризуется с помощью вводимых ниже понятий гомоморфизма и изоморфизма.

Пусть даны две алгебры и одинакового типа. Гомоморфизмом алгебры А в алгебру В НАзывается отображение Г: , удовлетворяющее условию

(1)

Для всех [ — Арность операций и , которая у них по условию одинакова] и всех Смысл условия (1) в том, что, независимо от того, выполнена ли сначала операция в А и затем произведено отображение Г либо сначала произведено отображение Г, а затем в В выполнена соответствующая операция , результат будет одинаков.

Изоморфизмом алгебры А на алгебру В наЗЫвается взаимнооднозначный гомоморфизм. В этом случае существует обратное отображение Г-1 : , также взаимно-однозначное. Пусть Тогда Заменим в условии (1) левые части этих равенств на правые и применим Г-1 к обеим частям получившегося равенства. Так как Г-1Г является тождественным отображением: то получим:

(2)

Равенство (2) — это то же равенство (1) с заменой Г на Г-1 элементов К на элементы М и переменой местами и ; иначе говоря, Г-1 — это изоморфизм В на А. Итак, еслИ существует изоморфизм А на В, то существует изоморфизм В на А; при этом алгебры А и В называются ИзоМорфными. Мощности основных множеств изоморфных алгебр равны (при гомоморфизме это равенство может не выПолНяться). Если А = В, то изоморфизм называется изоморфизмом на себя, или автоморфизмом; если то изоморфизм называется изоморфизмом в себя.

Пример 2.

1) Пусть — множество всех целых чисел, — множество всех четных чисел. Алгебры и изоморфны; изоморфизмом является отображение причем условие (1) здесь имеет вид Поскольку то Г2N — изоморфизм в себя. ОтображенИЕ является для алгебры автоморфизмом; условие (1) имеет вид Для алгебры не является автоморфизмом, так КАк

2) Рассмотрим алгебры и (см. пример 1) и определим отображение , следующим образом: Г(N) равно остатку от деления П на 7; иначе говоря, если то Пусть Проверим условие (1). Для сложения имеем Для умножения имеем Таким образом, условие (1) выполнено и Г7 — гомоморфизм. Очевидно, Г7 не является изоморфизмом, так как нет взаимной однозначности. Этот пример показывает, что возможен Гомофорфизм Бесконечной алгебры (т. Е. алгебры с бесконечным основным множеством) в конечную алгебру. При этом N разбивается на семь классов эквивалентности по отношению если и только если

3) Изоморфизмом между алгебрами и , Где — положительная часть R, является отображение Условие (1) имеет вид равенства

3) Рассмотрим алгебры и , где а бинарные операции J и F Заданы следующими таблицами (таблица 3, а, б):

Отображение Г: является изоморфизмом.

Буквальная проверка условия (1) состоит в следующем: в клетках (во внутренней части) таблицы J заменяем На в соответствии с Г и получаем левую часть (1), т. е. таблицу функции во внешней части таблицы F заменяем на и получаем правую часть (1); сравнением полученных двух таблиц убеждаемся, что они задают одну и ту же функцию. В действительности достаточно в таблице J переименовать все в и сравнить полученную таблицу с F.

Заметим, что можно было бы рассматривать алгебры и , где в таблице F все заменены на (с тем же индексом). Тогда отображение Г: также является изоморфизмом.

5) Рассмотрим булевы алгебры (см. пример 1), образованные двумя различными множествами U, U' одинаковой мощности. Эти две алгебры изоморфны: операции у них просто одинаковы, а отображением Г может служить любое взаимно-однозначное соответствие между U и U'.

Отношение изоморфизма является отношением эквивалентности на множестве алгебр. Рефлексивность его очевидна, симметричность следует из существования обратного изоморфизма, а транзитивность устанавливается следующим образом: если — изоморфизм А на В, Г2 — изоморфизм B на С, то изоморфизмом А на С будет композиция и . Классами эквивалентности в разбиении по отношению изоморфизма являются классы изоморфных между сОБой алгебр.

Понятие изоморфизма является одним из важнейших понятий в математике. Его существо, как видно из последних двух примеров, можно выразить следующим образом: если алгебры А и В изоморфны, то элементы и операции В Можно переименовать так, что В совпадет с А. Из условия (1) изоморфизма следует, что любое эквивалентное соотношение в алгебре А сохраняется в любой изоморфной ей алгебре А'. Это позволяет, получив такие соотношения в алгебре А, автоматически распространить их на все алгебры, изоморфные А. Распространенное в математике выражение «рассматривать объекты с точностью до изоморфизма» означает, что рассматриваются только те свойства объектов, которые сохраняются при изоморфизме, т. е. являются общими для всех изоморфных объектов. В частности, изоморфизм сохраняет ассоциативность, коммутативность и дистрибутивность.

< Предыдущая		Следующая >