Классы эквивалентности, фактор-множество

Определение. Пусть ~ - произвольное отношение экви­валентности на множестве X и а Î X. Тогда классом   эквивалентности ~ с порождающим элементом а называется множество всех элементов x Î X, эквивалентных элементу а, т.е.

.

Классы эквивалентности обладают следующими свойствами:

1. Порождающий элемент а принадлежит классу .

2. Если , то   т. е. любой элемент из класса эквивалентности может быть выбран в качестве порождающего элемента.

3. Для любых элементов а, b Î X

.

Другими словами, классы эквивалентности совпадают, тогда и только тогда, когда их порождающие элементы эквивалентны.

4. Любые два класса эквивалентности либо равны, либо не имеют общих элементов. Это свойство, очевидно, равно­ сильно следующему:

" a, b Î X (  ¹ Æ ® ).

5.    Множество X, на котором задано некоторое отноше­ние эквивалентности, равно объединению всех классов этой эквивалентности, т.е.

.

Доказательство.

Первое свойство, очевидно, следует из рефлексивности отношения ~.

Свойство 2. Пусть . Покажем, что .

Пусть   Тогда x ~ b. В то же время из сле­дует b ~ а. Теперь из x ~ b и b ~ а по свойству транзитив­ности отношения эквивалентности получим x ~ a и, значит, . Этим доказано включение .

Обратно, пусть . Тогда x ~ а. Поскольку b ~ а, то в силу симметричности а ~ b, откуда ввиду x ~ а и свойства транзитивности следует x ~ b, т. е. .Таким образом, . Следовательно, .

Свойство 3. Импликация  очевидна ввиду свойства 2.

Обратно, если а ~ b, то , откуда по свойству 2 вытекает равенство .

Свойство 4. Пусть  ¹ Æ для некоторых a, b Î X. Тогда существует элемент с Î X такой, что   и одновременно.

Из принадлежности по свойству 2 имеем . Аналогично из   получим .   Следовательно, .

Свойство 5. Из свойства 1 следует, что каждый элемент множества X содержится в некотором классе эквивалентности. Это означает, что .

С другой стороны, очевидно, что  , поскольку каждый класс   включается в X. Будем говорить, что семейство подмножеств  образует разбиение этого множества на классы   если:

1) все подмножества (классы) не пусты;

2) любые два различных подмножества и  не пере­секаются (т.е.  ¹ Æ);

3) объединение всех таких подмножеств есть множество X, т.е. .

Например, множество А = {1,2,3,4,5} можно разбить на классы , , ; множество це­лых чисел Z можно разбить на классы нечетных чисел и четных чисел .

Следующая теорема указывает на важную связь между понятиями "эквивалентность" и "разбиение".

Теорема 3. Классы любой эквивалентности на множестве X образуют разбиение этого множества. Обрат­но, для каждого разбиения на множестве можно определить эквивалентность на этом множестве так, что ее классы образуют исходное разбиение.

Доказательство.

I. Пусть на множестве X задана эквивалентность ~. Покажем, что все различные классы этой эквивалентности образуют разбиение множества X.

Действительно, свойство 1) разбиения вытекает из свойства 1 классов эквивалентности.

Свойство 2) разбиения выполняется ввиду свойства 4 дляклассов эквивалентности.

И, наконец, свойство 3) разбиения имеет место в силу свойства 5 для классов эквивалентности.

Итак, первое утверждение теоремы доказано.

Обратно, пусть на множестве X задано разбиение, т. е семейство подмножеств множества X, удовлетворяющих условиям 1) - 3).

Определим на множестве X бинарное отношение F поправилу: х Fу тогда и только тогда, когда элементы принадлежат одному и тому же подмножеству данного разбиение

Другими словами, .

Легко проверяется, что отношение F является эквива­лентностью.

Покажем теперь, что классы этой эквивалентности есть в точности подмножества данного разбиения.

Пусть  - какой-нибудь класс эквивалентности F. Тогда, по определению, существует подмножество  данного разбиения такое, что . Это означает, что любой элемент находится в отношении F с элементом а и, значит, .

Обратно, пусть . Тогда х Fа, откуда, по определе­нию, элементы x и а принадлежат одновременно некоторому подмножеству данного разбиения.

Отсюда, поскольку по определению разбиения каждый эле­мент множества X принадлежит только одному подмноже­ству разбиения и , то   и, значит, . Таким образом, показано, что каждый класс эквивалентности F совпадает с некоторым подмножеством данного разбиения.

Обратно, взяв произвольное подмножество  дан­ного разбиения множества X, мы замечаем, что для любого фиксированного элемента . Повторяя теперь до­словно предыдущие рассуждения, получим, что .

Теорема доказана.

Определение. Фактор - множеством множества X по отношению эквивалентности F называется множество, каждый элемент которого является одним из классов эквивалент­ности. Обозначается фактор - множество символом Х / F.

Пример. Пусть . Отношение на множестве X определим по правилу:

, тогда и только тогда, если .

Тогда фактор - множество Х/ F можно рассматривать как множество рациональных чисел. При этом рациональное число определяется как класс эквивалентности , т.е. семейство , где при  две пары    и   определяют одно и то же рациональное число.

§ 11. Операции на множестве

Рассмотрим конечное множество  и зададим отображение множества А в А с помощью следующей таблицы:    

a	b	c	d	e
e	c	a	b	d

Приведенная таблица устанавливает соответствие между элементами множества А. В верхней строке ее записаны эле­менты множества А, а под каждым из них в нижней строке находится его образ. В этом случае говорят, что на множестве А задана унарная операция.

В алгебре часто изучаются операции, связывающие пары чисел с третьим числом. Такие операции называются бинар­ными. Примерами бинарных операций являются: сложение, умножение на множестве R действительных чисел и другие.

Определение 1. Бинарной операцией на множестве А называется произвольное отображение

.

Таким образом, бинарная операция каждой упорядоченной паре (а, b) элементов множества А ставит в соответствия третий элемент с этого же множества, а именно, образ пары при отображении T, т.е. . В практике последняя запись встречается редко. Как правило, вместо нее пишут:

и читают: "элемент с есть результат операции Т над элементами а и b". Вместо символа Г часто используется один из знаков " + " (сложение) или " × " (умножение). В первом случае говорят об использовании аддитивной терминологий, во втором - мультипликативной.

Результат операции называется, соответственно, суммой или произведением.

Примеры:

1. Сложение и умножение на каждом из множеств N, Z, Q, R, где N, Z, Q, R обозначают, соответственно, множество натуральных, целых, рациональных и действительных чисел.

2. Возведение в степень на множестве натуральных чисел.

3. Объединение и пересечение на множестве подмножеств некоторого множества.

Контрпримеры:

1. Вычитание на множестве N не является бинарной опера­цией, т.к. при вычитании из меньшего числа большего полу­чаем число, не принадлежащее множеству N.

2. Умножение во множестве иррациональных чисел Ω = R \ Q также не является бинарной операцией, т.к., напри­мер, и число 2 ¹ Ω.

Пусть Е - множество с бинарной операцией Т и F Í Е. Тогда, если результат операции над любыми двумя элемента­ми из F также принадлежит F, то множество F называется замкнутым относительно рассматриваемой операции Т.

Например, множество  четных целых чисел является замкнутым подмножеством относительно сло­жения и умножения на множестве Z, а множество иррациональных чисел Ω Í R не является замкнутым подмножеством относительно операции умножения на множестве R.

По аналогии с понятием п - арного отношения (гл.II,§6) можно обобщить определение операции на любое число аргу­ментов:

пусть А- множество и п - фиксированное натуральное число. Тогда п - арной операцией на множестве А называется произвольное отображение   ( - декартово произведение п сомножителей, равных А).

Таким образом, всякая п - арная операция Т произвольному упорядоченному набору из п элементов данного множества А ставит в соответствие единственный элемент этого множества.

Очевидно, что при п = 1 операция Т становится унарной, а при   п = 2 - бинарной. Используется также термин 0 - арная операция. Говорят, что на множестве определена 0 –арная операция, если на этом множестве зафиксирован некоторый элемент е.

Заметим, что  вместо фразы " Т является п -арной операцией "иногда говорят, что "арность операции Т равна n ".

Например, арность любой бинарной операции равна 2, унарной - 1 и т.д.

Аналогичное соглашение имеет место и для п - арных отношений.

Свойства бинарной операции

Ассоциативность. Бинарная операция Т называется ассоциативной, если для любых элементов а, b, с Î A.

Например, сложение и умножение во множестве натуральных чисел N ассоциативно, а возведение в степень - не ассоциативно, поскольку равенство выполняется не для всех натуральных чисел. Например, .

Коммутативность. Бинарная операция T называется коммутативной, если

 для любых а, b Î А.

Регулярный элемент. Элемент а называется регуляр­ным относительно бинарной операции T, если для любых x, y Î А, равенства

аТх = аТу и хТа = уТа

  влекут х = y. В этом случае говорят, что равенства можно сократить на a.

Примеры:

1. Относительно сложения во множестве действительных чисел R любое число регулярно.

2. Относительно умножения во множестве R регулярным является всякое число, кроме нуля, так, например, 0×2 = 0×7, но 2 ¹7.

Нейтральный элемент. Пусть А - множество с бинарной операцией Т. Нейтральным элементом относительно операции Т называют такой элемент е Î А, что равенство еТх = хТе = х справедливо для любого х Î А.

Легко проверить, что если такой элемент существует, то он единственен. Нейтральный элемент, как видно из определения, регулярен.

Как правило, в аддитивной терминологии нейтральный элемент называют нулем, а в мультипликативной - единицей.

Например, во множестве целых чисел Z нейтральным эле­ментом относительно сложения является число 0, а число 1 служит нейтральным элементом относительно умножения.

Во множестве Р(А) всех подмножеств данного множества А пустое множество Æ выполняет роль нейтрального элемента относительно операции объединения.

Симметричные элементы. Пусть бинарная операция Т задана на множестве А, обладает нейтральным элементом е. Говорят, что элемент симметричен элементу а Î А, если

.                                         (1)

В аддитивной терминологии симметричный элемент назы­вается противоположным, а в мультипликативной - обрат­ным к данному.

Примеры:

1. Если а Î R, то число - а Î R, является симметричным (противоположным) элементом относительно сложения.

2. Если а Î R и а ¹ 0, то число является сим­метричным (обратным) элементом относительно умножения.

3. Если е - нейтральный элемент, то его симметричным элементом служит он сам, т.к. .

Из равенств (1) очевидным образом следует, что если эле­мент является симметричным к элементу а Î А, то а симметричен к , т.е. .

Следствие 1. Пусть А - множество с ассоциативной бинарной операцией Т и нейтральным элементом е. Тогда любой элемент а Î А не может иметь более одного симметричного элемента.

Доказательство. Пусть   и   - симметричные к а   элементы относительно бинарной операции Т. По определению, имеем

 

                                                   ;                            (2)

                                                   .                            (3)

 

Тогда, очевидно, , откуда . Отсюда, в силу ассоциативности операции Т, получим Теперь из (2) следует, что и, значит, .

Дистрибутивность. Пусть на множестве А определены две бинарные операции Т и ^. Говорят, что операция Т дистрибутивна относительно операции ^, если для любых а, b, с имеет место

.

Примеры:

1.    На множестве действительных чисел R умножение дистрибутивно относительно сложения:

.

Однако сложение не дистрибутивно относительно умножения.

2.    Для операций объединения и пересечения подмножеств произвольного универсального множества справедливы равен­ства:

;

.

Следовательно, каждая из этих операций дистрибутивна относительно другой.

§ 12. Понятие об алгебраической системе. Алгебры и модели. Классические примеры алгебр. Изоморфизм алгебр

Пусть А - произвольное множество. В дальнейшем это мно­жество будем называть основным или носителем (построенной) алгебраической системы. Зафиксируем на носителе А некоторые операции . и отношения (предикаты) .

Пусть  - арность операции   и - арность отношения . Положим далее и .

Определение. Тройка множеств  называется алгебраической системой типа . Множество , состоящее из символов операций и отношений , называют сигнатурой системы. При этом  называют функциональной,  - предикатной частью сигнатуры данной системы.

Сигнатура алгебраической системы может быть и беско­нечной (условие конечности в приведенном выше определении выбрано ради краткости).

Алгебраическая система - это множество (носитель) с на­бором (возможно бесконечным) операций и отношений, опре­деленных на этом множестве.

Алгебраическая система называется алгеброй, если пре­дикатная часть ее сигнатуры является пустым множест­вом ( =Æ).

Если же функциональная часть сигнатуры алгебраиче­ской системы пуста, т.е. = Æ, то эта система назы­вается моделью.

Отметим, что создателем теории алгебраических систем является выдающийся советский математик А. И. Мальцев (1909 - 1967). Читатель, желающий познакомиться с основ­ными идеями этой теории, может обратиться к книге [10].

Примеры:

Пусть символы и   обозначают, соответственно, опе­рации сложения и умножения на множестве N натуральных чисел, а Р- отношение ≤ ("меньше либо равно").

Тогда следующие три алгебраические системы

, ,

являются алгебрами. Первые две из них имеют тип , а тип третьей равен .

Алгебраическая система является моделью.

Алгебраическая система имеет тип , Она не является ни алгеброй, ни моделью.

Другие примеры будут приведены ниже.

Классические алгебры

1.    Алгебра с одной бинарной операцией называется груп­поидом.

Например, каждое из множеств N, Z, Q, R образует группоид относительно операции сложения либо умножения.

2.    Алгебра с одной бинарной ассоциативной операцией называется полугруппой.

Очевидно, все группоиды, указанные в предыдущем пункте, являются полугруппами. Однако в общем случае это утверждение не верно, т.е. класс группоидов более широк, чем класс полугрупп.

Например, целые числа относительно операции вычитания образуют неассоциативный группоид.

Приведем другой пример группоида, который не является полугруппой.

Пусть А = {а, b} - двухэлементное множество. Зададим операцию Т на множестве А следующими равенствами:

, , , .

Тогда . В то же время , и, значит, .

Следовательно, операция Т неассоциативна. Это означает, что группоид не является полугруппой.

Заметим, что операции T, построенной в предыдущем при­мере, соответствует следующая таблица:

T	a	b
a	b	a
b	b	a

 

Такие таблицы называются таблицами Кэли. Они используются, как правило, для задания бинарной операции на конечном множестве и устроены следующим образом.

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

В теории полугрупп важнейшую роль играют так называ­емые "полугруппы отображений множеств (в себя)".

Устроены они так:

Пусть А - произвольное фиксированное множество. В ка­честве носителя полугруппы выбирается множество М(А), состоящее из всех отображений множества А в себя:

 

.

Операцией на множестве М(А) служит композиция ото­бражений (гл. II, § 5).

Очевидно, что для любых f, g Î М(А) их композиция также является отображением множества А в себя и, следова­тельно, . Ассоциативность операции о компо­зиции гарантируется теоремой 1 (гл.II, §5).

Таким образом, - полугруппа для любого мно­жества А.

3. Полугруппа   называется группой, если она име­ет нейтральный элемент, относительно которого любой эле­мент a Î G имеет симметричный элемент.

Позже будет показано, что это определение "избыточно", т.е. можно некоторые требования в определении ослабить.

С этой целью сформулируем определение группы в муль­типликативной терминологии.

Группоид с операцией × умножения называется группой, если выполнены следующие условия:

1.  (ассоциативность операции умножения);

2.  (элемент е называют при этом правой единицей);

3.  (элемент b называется правым обратным для а).

Условия 1-3 называют аксиомами группы. Опираясь на них, можно доказать, что в группе существует только одна единица е, которая является одновременно и правой, и ле­вой. Никаких других единиц ни правых, ни левых не сущест­вует.

Аналогичное утверждение имеет место и для элемента, об­ратного к любому данному. В связи с этим элемент, обратный к элементу а, имеет стандартное обозначение .

Таким образом, последнее определение группы равносильно исходному, но оно содержит "меньше" требований (требуется наличие только правой единицы, и для каждого элемента - существование только правого обратного).

Для перевода определения группы на аддитивный язык до­статочно: знак умножения (×) заменить знаком сложения (+), слова "произведение", "единица" и "обратный", соответствен­но, - словами "сумма", "нуль" и "противоположный".

Аксиомы 1-3 будут выглядеть так:

;

;

.

Элемент, противоположный элементу а, обозначается через (- а).

Группа   называется коммутативной, либо абелевой,-, если групповая операция Т коммутативна, т. е.

Для абелевых групп, как правило, используется аддитивная терминология.

Примеры:

Каждое из множеств Z, Q и R образует группу относительно операции сложения.

Однако, натуральные числа не образуют ни по сложению ни по умножению.

Очевидно также, что если в качестве носителя выбрать одно из множеств , , , , где , обознача­ют множества положительных рациональных и действительных чисел, соответственно, то получим группу относительно умножения.

Важнейший класс в теории групп образуют так называе­мые "группы преобразований" или "группы подстановок".

Преобразованием множества А называется любое биек­тивное отображение множества А на себя.

Зафиксируем множество А, и через S(А) обозначим мно­жество всех биекций ,

.

Тогда нетрудно показать, что композиция любых двух ото­бражений f, g из S(А) снова является биекцией (см., напр., упр. 12, с. 47) и, следовательно, . Таким обра­зом, композиция является бинарной операцией на множестве S(А). Теперь уже легко установить, что алгебра   яв­ляется группой.

Действительно, ассоциативность операции вытекает из те­оремы 1 (гл.II, §5). В этой же теореме содержится утвержде­ние о том, что тождественное отображение множества А играет роль единицы при композиции отображений. Следова­тельно, композиция удовлетворяет аксиомам 1 и 2.

Проверим выполнимость третьей аксиомы. Пусть , тогда - биекция.

Тогда по признаку обратимости отображения существует отображение , обратное к f, т.е , Это означает, что - обратимо. Отсюда снова по той же теореме 2 получим, что  - биекция и, сле­довательно, .

Таким образом, и третья аксиома выполняется и, значит,  -группа.

Если А - конечное множество, то вместо термина "преобразование" используется его синоним "подстановка".

В этом случае, если множество А содержит п элементов, то вместо S (А) используется запись .

Группа   называется группой подстановок п -й степени или симметрической группой п-й степени. Нетрудно прове­рить, что она содержит n! элементов.

Пусть   и - группоиды.

Определение. Группоид   называется изоморфным группоиду , если существует биекция та­кая, что

                              (*)

Биекцию  в этом случае называют отображением, осу­ществляющим изоморфизм данных группоидов.

Заметим, что условие (*) в словесной формулировке часто выражают словами: "отображение  сохраняет групповую операцию Т ".

Из определения очевидным образом следует, что отноше­ние изоморфизма между группами обладает свойствами ре­флексивности, симметричности и транзитивности.

Запись G  L означает, что группоид   изоморфен' группоиду .

Нетрудно проверить, что в этом случае, если   явля­ется группой, то и   - также группа.

Примеры:

1. Пусть G = Z и Т - сложение. Ранее уже отмечалось, что - группа.

Пусть и F - умножение (на множестве L).

Легко проверить, что -группа.

Пусть   отображение, определяемое по правилу:   для любого k Î2.

Покажем, что f осуществляет изоморфизм Z  L.

Действительно, если , то одно из этих чисел мень­ше другого. Пусть, например, . Тогда, поскольку f - возрастающая функция, то , т.е.

.

Следовательно, f - инъективно. Сюрьективность отображения f очевидна, и, значит, f - биекция.

Проверим теперь, что отображение f удовлетворяет усло­вию (*).

Пусть . Тогда . Утверждение доказано.

2.  - множество положительных действительных чисел. Тогда, как уже отмечалось, является группой относи­тельно операции умножения.

Нетрудно проверить, что отображение , опре­деленное по правилу для любого , осу­ществляет изоморфизм между группой   и аддитивной группой .

Действительно, биективность  очевидна, а условие (*) выполняется в силу равенства  для любых  (т.е. ).

Понятие изоморфизма играет фундаментальную роль в математике. Из определения следует непосредственно, что изоморфные группоиды имеют одинаковое количество элемен­тов. Читатель без особого труда докажет, что "единица группы при изоморфизме переходит (отображается) в единицу дру­гой группы, элемент, обратный к данному, - в обратный к его образу" и т.д. Несколько больших усилий требуется для по­нимания и доказательства следующего (более общего) утверж­дения: "Если некоторая формула исчисления предикатов ис­тинна на одной из изоморфных между собой группах, то она истинна и на другой".

Другими словами, изоморфные группы имеют одинаковые алгебраические свойства (т.е. свойства, сформулированные в общелогических терминах и терминах операций, с помощью которых заданы данные группы).

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

Заметим, что если результат бинарной операции Т над элементами    и    записывать через , то усл