Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
(a-1)8 = ае, (а2)е с= а".
Эквивалентным замыканием системы S отношений называется эквивалентное замыкание объединения отношений из S. В частности, эквивалентное замыкание пары отношений a, ?, которое мы временно обозначим через a (g) ?, определяется формулой
QS (е) ? = (a U ?)e. 28
ОБЩИЕ ПОНЯТИЯ
[Гл. I
Понятию эквивалентного замыкания можно дать следующее, в каком-то смысле более конструктивное определение.
Пусть S — некоторая совокупность отношений, заданных на каком-то множестве А. Вводим новое отношение еА на множестве А. полагая аеАЬ истинным в следующих случаях:
а) а = Ъ,
б) aab или baa для некоторого а ? S,
в) в Л существует конечная совокупность элементов dl, . . ., ап (п — 1, 2, . . .), связанных условиями
aOiau ^ct2CI3, . . ., anan+lb*)t (1)
где Oi или оч1 принадлежит S (г = 1, . . ., п-f 1).
Ясно, что отношение еА является искомым эквивалентным замыканием системы S. Действительно, из а) следует, что отношение еА рефлексивно; из б) следует, что еА содержит каждое отношение a ? S; из б) и в) следует, что еА симметрично и транзитивно. Таким образом, еА есть эквивалентность, содержащая в себе каждое отношение из S, а потому содержащее в себе и эквивалентное замыкание системы S. G другой стороны, если а — эквивалентное замыкание S, то из аеАЬ в каждом из случаев а), б), в) вытекает aab, т. е. еА с: а и, значит, еА = а.
Из указанного конструктивного определения эквивалентного замыкания непосредственно вытекает
Следствие 1. Эквивалентное замыкание Ct1 (е) а2 произвольных эквивалентностей ai, a2 на множестве А тогда и только тогда истинно для a, b ? А, когда в А существует конечная цепочка элементов U1, . . ., a3n+i> связанных соотношениями
aalaia2a2aia3a2 . . . аій2п+іаф. (2)
Для доказательства надо лишь убедиться, что в рассматриваемом случае каждое из условий а), б), в) влечет подходящее условие вида (2). Ясно, что условие а) влечет условие аа\аага вида (2), а условие б) влечет условие аа^ааф или условие aaiba2b. Так как отношения alt a2
*) Соотношения (1) будут записываться в виде • •
• •-апсгп+1Ь. —Прим. ред. ОТНОШЕНИЯ и отображения
29
симметричны, то в условии в) можно отбросить слова «или оТ1». Далее, если в цепочке (1) встретится отрезок аьа^ь-ио^Яй+а, т0 в силу транзитивности Gii (і = 1, 2) этот отрезок можно заменить отрезком afcaj?fc + a и т. д.
Рефлексивное и симметричное отношение называется псеедожвивалентностьюк Конструкция эквивалентного замыкания системы псевдоэквивалентностей допускает некоторые упрощения по сравнению с общим случаем. Эти упрощения мы сформулируем в виде особого следствия.
Следствие 2. Эквивалентное замыкание системы S псевдоэквивалентностей на множестве А тогда и только тогда истинно для элементов а, Ъ из А, когда в А существует конечная цепочка элементов at, . . ., ап, связанных отношениями
aaiai02a203 . . . anon+1b, где O1, . . ., Gn-ft — какие-то (возможно, повторяющиеся) отношения из S. Доказательство такое же, как и для следствия 1.
Конструкцию эквивалентного замыкания можно представить в иной форме, если воспользоваться следующими замечаниями.
Замечание 1. Произведение O1O2 ... Oh рефлексивных отношений O1, . . ., Ok рефлексивно и содержит в себе каждое из перемножаемых отношений.
Ввиду ассоциативности умножения отношений это замечание достаточно доказать лишь для двух множителей. Имеем
XOіУ =Ф (хОіУ & уо2у) =#• ж (O1O2) у, и потому O1 = O1O2. Аналогично из
хо2у (XO1X & хо2у) X (O1O2) у получаем CF2 ?= CF1Cr2. Наконец, для произвольного х
XO1X & XO2X =# X (C1O2) X,
что и требовалось.
Замечание 2° Каждая эквивалентность о, содержащая отношения Oi, . . ., ад, содержит и их произведение.
Снова достаточно рассмотреть лишь случай двух сомножителей. Но
х (gIO2) У 3z(z0jz & ZCT2T/) =ф 3 z(xoz & zoy) =ф XOOy => ха у, что и требовалось. зо
ОВЩиё йойЯТйй
[Гл. і
Теорема 5. Эквивалентное замыкание совокупности эквивалентностей оа совпадает с объединением а всевозможных произведений этих эквивалентностей.
Действительно, согласно замечанию 1, сг содержит все эквивалентности оа, а согласно замечанию 2, о содержится во всех эквивалентностях, содержащих оа.
1.5. Частичные и линейные порядки. Наряду с экви-валентностями важным типом бинарных отношений являются частичные порядки. Бинарное отношение р на множестве А называется частичным порядком, если оно рефлексивно, транзитивно (см. п. 1.4) и антисимметрично:
хру & урх X = у
для любых элементов X, у из А. Таким образом, бинарное отношение р на множестве А будет частичным порядком тогда и только тогда, когда оно обладает следующими тремя свойствами:
1 = р П P"1 ^ і, P2 != P-
Легко проверить, что эта система условий равносильна следующей:
ISp, P П P-1 — l) P2 = P-
Заметим, что для каждого частичного порядка р на множестве А обратное отношение р-1 также будет частичным порядком, который называется обычно двойственным к р.
Частичный порядок на множестве А часто обозначают символом и если a Ъ для некоторых элементов а, Ъ из А, то говорят, что а меньше или равно Ъ, а также что а содержится в Ъ или равно Ъ. Если а Ъ и а Ф Ъ, то пишут а < Ъ и говорят: а строго меньше Ъ или а строго содержится в Ъ.
