Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
< и <-1 = > на натуральном ряде не перестановочны. Отношение равенства, определенное на множестве A7
часто обозначают символом іЛ. Оно состоит из всех диагональных пар (а, а), а ? А. Если множество А заранее фиксировано, то вместо іА пишут і. Легко убедиться, что для любого бинарного отношения а, определенного на множестве А,
см-а = ід«. (5)
Однако пример (4) показывает, что равенство аа'1 = і для некоторых отношений а может оказаться и неверным.
Исходя из определений произведения и обращения отношений, легко убедиться, что для произвольных отношений a, ?, у имеют место тождества
a (?v) - (a?) у, (6)
(a?)-1 = ?-ia-i. (7)
При этом, если отношения рассматриваются на парах различных множеств, то тождества (6), (7) следует понимать так, что из определенности левой или правой частей равенства вытекают определенность и другой части равенства и совпадение значений обеих частей.
Помимо тождеств (6), (7), относящихся к операциям умножения и обращения отношений, существует ряд тождеств, связывающих эти операции с булевыми операциями U , Pl1'- Например, для любых отношений a, ?, у, определенных на произвольном множестве А,
(Ct-I)' = («')-!, (8)
(a U ?)"1 = a-1 U ?"1, (а П ?)"1 = er1 П ?~\ (9) a (?Uv) = a?Uav, (? U Y) a = ?a U Ya- (W) Отметим, что аналог формул (10) для Г) неверен.
3* 20
ОБЩИЕ ПОНЯТИЯ
[Гл. I
Система, состоящая из совокупности всех бинарных отношений, определенных на каком-нибудь множестве А, и операций Ui П і ¦> "1I производимых над этими отношениями, называется алгеброй отношений на А. Тождества (6) — (10), а также булевы тождества Б1—Б7 из п. 1.1 являются примерами тождеств, имеющих место на произвольных алгебрах отношений. Задача нахождения полной системы тождеств, истинных на алгебрах отношений, оказалась более сложной, чем, например, для алгебр Буля подмножеств.
1.3. Отображения. Отношение а, определенное на паре множеств А, В, называется отображением А ъ В, если для каждого а Є А существует один и только один элемент Ъ ? В, удовлетворяющий отношению ааЪ. Элемент b называется образом элемента а при отображении а и обозначается через аа или аа. Если Ь — аа, то элемент а называется прообразом элемента Ъ при отображении а. Совокупность всех прообразов элемента Ъ в А при данном отображении а называется полным прообразом этого элемента в А.
Отображение иногда удобно задавать таблицей, состоящей из двух строк. В верхней строке в произвольной последовательности пишутся обозначения элементов множества А, а под ними записываются обозначения их образов в множестве В. Например, таблица
/1 5 3 4\ a=43 4 13j
определяет отображение множества {1, 5, 3, 4} в себя, при котором Ia - 3, 5« = 4, 3a = 1, 4а = 3.
Пусть а — отображение А в В, ? — отображение В в С. Тогда произведение отношений a? будет отображением і в С, и для любого X Є А справедливо соотношение
X (a?) = (ха) ?.
В самом деле, пусть х (a?) = с. Тогда для подходящего у Z В имеем ха у, г/?c, откуда ха — у, и потому с = (ха) ?. Обратно, из с = (ха) ? вытекает (xa) ? с. Так как X a (ха), то х (a?) с, т. е. с = х (a?). ОТНОШЕНИЯ И ОТОБРАЖЕНИЯ-
21
Умножение отображений, заданных таблицами, производится по способу, непосредственно видному из следующего примера:
/1 2 3 4W ab с d\ /1 2 3 4\
\а b с d)\x у и v) \х у и v) '
Отображение а множества А в множество В называется отображением А на В, если каждый элемент b ? В имеет в А хотя бы один прообраз, т. е. если уравнение ха = b для любого Ъ ? В имеет хотя бы одно решение X 6 А.
Отображение а множества А на множество В называется взаимно однозначным, если обратное отношение aявляется отображением В на А. Для того чтобы отображение, заданное таблицей, было взаимно однозначным, необходимо и достаточно, чтобы каждый элемент из В встречался в нижней строке один и только один раз. Делая нижнюю строку верхней, а верхнюю нижней, получим таблицу обратного отображения.
Так, из таблиц
/1 2 3 4\ /1 2 3 4\
\2 3 1 Aj1 \2 4 2 3/
первая определяет взаимно однозначное отображение множества {1, 2, 3, 4} на себя, а вторая нет.
Пусть а — какое-нибудь отображение множества А в себя и аа ~ Ъ. Тогда говорят, что отображение а переводит точку а в точку Ъ. Если аа = а, то а называется неподвижной точкой отображения а. Все точки множества А являются неподвижными точками тождественного отображения 1А.
Рассмотрим какое-нибудь взаимно однозначное отображение а А на В. Ясно, что в этом случае обратное отношение а-1 будет взаимно однозначным отображением В на А. Так как для любых a Q A1 b ? В имеем (аа) а-1 = = а,. (&а-1) а = Ь, то
аа-1 = iA, а-1а = iB. (1)
В частности, если а — взаимно однозначное отображение А на А, то
«от1 = W-1Cf = і, (2) 22
ОБЩИЕ ПОНЯТИЯ
[Гл. I
Равенства (1), (2) дают повод высказать следующую теорему.
Теорема 1. Для того чтобы отношение а, определенное на паре множеств А, В, было взаимно однозначным отображением А на В, необходимо и достаточно, чтобы отношения а и а~х удовлетворяли соотношениям (1).
