Бинарные отношения делятся на типы в зависимости от свойств, которыми они обладают.
Отношение R на множестве X называется отношением эквивалентности, если оно обладает свойствами рефлексивности, симметричности и транзитивности.
Важной особенностью отношений эквивалентности является то, то они разбивают все множество Х на непересекающиеся подмножества – классы эквивалентности.
Классом эквивалентности, порожденным элементом х Î X, называется подмножество [х] множества X, для элементов которого выполняется условие (х, у) Î R, yÎ X.
Таким образом, класс эквивалентности:
[х] = {у | y Î X; (x, y) Î R}.
Классы эквивалентности образуют систему непустых непересекающихся подмножеств множества X, в объединении дающую все множество X – т. е. образуют разбиение множества Р(Х).
Обозначим отношение эквивалентности символом º, тогда класс эквивалентности записывается в виде:
[х] = {у | y Î X; х º у}.
Из рассмотренных в примере отношений только отношение М является отношением эквивалентности.
Отношение М разбивает множество X = {1,2,3,4,5,6,7} на три класса эквивалентности:
[1] = {1,4,7}, [2] = {2,5}, [3] = {3,6}.
Классы, порожденные элементами 4, 5, 6 и 7 совпадают с этими классами:
[4] = [1], [5] = [2], [6] = [3], [7] = [1].
1.6. Отображения множеств
Пусть X и Y – два непустых множества. Закон G, согласно которому любому элементу х Î X ставится в соответствие элемент у Î Y, называется однозначным отображением X в Y. Отображение является обобщением понятия функции, определенной на X и принимающей значения на Y.
Используются следующие эквивалентные записи:
G: X ® Y
или
у = G(x); где х Î X, у Î Y.
В случае однозначного отображения элемент у называется образом элемента х, а х – прообразом у.
Возможна ситуация, когда каждому х Î X отображение G ставит в соответствие некоторое подмножество
G(x) Ì Y. Тогда образом элемента х будет подмножество G(x). Отображение G в этом случае будет являться многозначным отображением.
Отображение является, таким образом, всюду определенным отношением и определяется тройкой множеств (X, Y, G).
Интересным является случай, когда множества X и Y совпадают: X = Y. Отображение G: X ® X представляет собой отображение множества X самого в себя и определяется парой множеств (X, G), где G Ì X ´ X. Подробным изучением таких отображений занимается теория графов. Рассмотрим здесь лишь нескольких операций над ними.
Пусть G и Н – отображения множества X в X. Композицией этих отображений назовем отображение GH, которое определяется следующим образом:
GH(x) = G(H(x)).
В частном случае при Н = G получим отображения:
G2(x) = G(G(x)), G3(x) = G(G2(x)) и т. д.
Для произвольного S ³ 2 имеем: GS(x) = G(GS -1(x)).
Введем для общности соотношение: G0(x) = х. Тогда можно записать:
G0(x) = G(G-1(x)) = GG-1(x) = х.
Это означает, что G-1(x) представляет собой обратное отображение. Тогда G-2(x) = G-1(G-1(x)) и т. д.
Пример. Пусть X – множество людей. Для каждого человека х Î X обозначим через G(x) множество его детей. Тогда:
G2(x) – множество внуков х,
G3(x) – множество правнуков х,
G-1(х) – множество родителей х и т. д.
Изображая людей точками и рисуя стрелки, идущие из х в G(x), получим родословное, или генеалогическое дерево, представленное на рис. 1.10.
Рис. 1.10. Генеалогическое дерево