Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
Утверждение aab иногда записывают в виде а = b (а) и говорят, что а сравнимо с & по а. Согласно сказанному эквивалентность а = b (а) в множестве А равносильна равенству [а] = \Ь\ в фактор-множестве Ala,
X. *у
Рис. 1. ОТНОШЕНИЯ И ОТОБРАЖЕНИЯ-
25
Отметим еще, что каноническое отображение A Alo тогда и только тогда взаимно однозначно, когда эквивалентность о совпадает с отношением равенства і. Каждый смежный класс А по і состоит лишь из одного элемента. Отождествляя элемент и множество, состоящее только из этого элемента, мы отождествим множество А с фактор-множеством Ak.
Рассмотрим какое-нибудь отображение а множества А на множество В. Определим на А бинарное отношение о, полагая CL1Oa2 (at, а2 ? ^4) истинным
тогда и только тогда, когда а1 = а%. I I _.
Ясно, что отношение ст есть экви- I—I валентность на А. Смежные классы
А по ст суть просто полные прообразы aA ; | -
в А элементов множества В. Ставя 2
каждому элементу В в соответствие __.
его полный прообраз в А, получим |_| #
взаимно однозначное отображение
множества В на фактор-множество Рис- 2.
А/о. Это отображение называется
каноническим, а эквивалентность о называется ядерной эквивалентностью для отображения a. Ha рис. 2 множество А состоит из точек всех квадратов, а множество В есть совокупность точек, находящихся в правом столбце. Все точки каждого квадрата отображаются в одну и ту же точку, стоящую справа. Квадраты и будут смежными классами ядерной эквивалентности.
В заключение спросим себя, относительно каких операций из числа рассмотренных выше будет замкнута совокупность всех эквивалентностей на произвольном множестве? Ясно, конечно, что совокупность всех эквивалентностей замкнута относительно операции обращения отношений, так как для любой эквивалентности а-1 = а. Столь же очевидна и
Теорема 1. Пересечение любой (безразлично — конечной или бесконечной) системы эквивалентностей на множестве А есть эквивалентность на А.
Пусть заданы, например, две эквивалентности а, ?. По условию і ^ а, і g ?, Следовательно, і ^ af|?-Аналогично
(«И ?)-1 = a_1 П ?"1 = «n?. 26
ОБЩИЕ ПОНЯТИЯ
[Гл. I
Таким образом, отношение а П ? рефлексивно и симметрично. Будет ли оно транзитивно? Пусть а (а П ?) b и Ь (а П ?) с истинны. Это значит, что истинны отношения
aab, a?b, bac, 6?c.
Из первого и третьего следует аас, из второго и четвертого следует a?c. Таким образом, а (а П ?) с истинно, что и требовалось.
Дополнение отношения эквивалентности не содержит і и потому не есть эквивалентность.
Теорема 2. Произведение эквивалентностей а, ? тогда и только тогда есть эквивалентность, когда а и ? перестановочны.
Действительно, если a? — эквивалентность, то a? = = (a?)-1, откуда
a? = ?-1«"1 = ?a.
Обратно, пусть a? — ?a. Так как хах & х$х =ф ха$х, то отношение a? рефлексивно. Из
(a?)-1 = ?-1a_1 = ?a = a? следует, что a? симметрично. Наконец, равенства (a?)2 = a?a? = aa?? = a?
показывают, что a? транзитивно.
Теорема 3. Объединение a U ? эквивалентностей a, ? тогда и только тогда является эквивалентностью, когда пересечение любого смежного класса по а с любым смежным классом по ? или совпадает с одним из этих классов, или пусто. Если a IJ ? — эквивалентность, то a IJ ? = a?.
Действительно, пусть существуют смежный класс по а и смежный класс по ?, имеющие общий элемент а, и ни один из этих классов не лежит в другом. Тогда найдутся элементы Ь, с такие, что baa, c?a, &?'a, ca'a. Пары (b, а) и (a, с) содержатся в a U ?. Если бы отношение a U ? было эквивалентностью, то пара (b, с) также содержалась бы BaU ?i чт0 невозможно, так как bac & baa =ф
саа и &?c&c?a^o?a. Остальные утверждения теоремы 3 доказываются аналогичным путем, ОТНОШЕНИЯ И ОТОБРАЖЕНИЯ-
27
Теорема 4. Произведение a? эквивалентностей а, ? содержит а и ? и содержится в любой эквивалентности у, содержащей а и ?.
В самом деле,
aab (aab & &?&) aa?&, a?b =# (aaa & a?o) =#> aa?o, aa?o=^ & x$b) =Ф & жуЬ) =Ф ayo,
что и требовалось.
Следствие. Если эквивалентности a, ? перестановочны, то их произведение a? является наименьшей эквивалентностью, содержащей а и ?.
Теоремы 1—4 показывают, что ни одна из операций алгебры отношений не позволяет по произвольно заданным эквивалентностям a, ? найти эквивалентность, содержащую а и ?. Поэтому представляет интерес еще одна операция — операция эквивалентного замыкания, в какой-то мере восполняющая этот пробел.
Пусть а — какое-нибудь бинарное отношение, заданное на произвольном множестве А. Множество O = AxA есть самое «большое» отношение на А. Оно одновременно является и наибольшей эквивалентностью на А, содержащей в себе, в частности, и заданное отношение а. Обозначим через ае пересечение всех эквивалентностей, определенных на Л и содержащих в себе отношение а. Согласно теореме 1 отношение а® есть эквивалентность. Это наименьшая эквивалентность из эквивалентностей, содержащих в себе отношение а. Она называется эквивалентным замыканием отношения а. Если а есть эквивалентность, то ae = а. Из определения эквивалентного замыкания вытекает, что для любого отношения а имеем
