Бинарные отношения делятся на типы в зависимости от свойств, которыми они обладают.
Отношение 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 совпадают с этими классами:
Пусть 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. Генеалогическое дерево
Контрольные вопросы и упражнения
1. Вставьте обозначения числовых множеств:
- множество натуральных чисел;
- множество целых чисел;
- множество рациональных чисел;
- множество действительных чисел.
2. Вставьте пропущенный знак Î или Ï: 117 ___ N; 22,4 ___ Z; 4/3___Q;
___ Q; ___ R; p ___ Z.
3. Принадлежит ли множеству корней уравнения
x2 - 5х + 6 = 0 число х = -3?
4. Какими способами можно задать множество?
5. Запишите множество действительных корней уравнения 3х + 4 = 0. Как записать ответ, если требуется найти множество целых корней этого уравнения?
6. Что такое подмножество данного множества? Какой символ используется для записи «множество А является подмножеством множества В»? Запишите его: А ____ В.
7. Вставьте пропущенный символ Î или Ì :
1 ___ {1,2,3}; {1} ____ {1,2,3};
Æ ___ {1,2,3}; {2,3} ____ {1,2,3}.
8. Вставьте пропущенные знаки операций на множествах:
{а,b,с} ____ {d,b,e} = {b};
{a,b,с} ____ {с, d} = {а,b,с,d};
{а,b,с} ____ {a,d} = {b,c}.
9. Что такое булеан множества X?
10. Является ли булеаном множества {а,b,с} система подмножеств {а}, {b}, {с} ?
11. Является ли разбиением множества {а,b,с} система подмножеств {a,b},{b,с},{а,с} ?
12. Нарисуйте диаграммы Эйлера для левой и правой частей закона де Моргана. Сравните их.
13. Запишите законы алгебры множеств. Запомните их названия.
14. Вставьте пропущенный знак = или ¹: {3,5} _____ {5,3}; (3,5) _____ (5,3).
15. Нарисуйте график декартова произведения X ´ Y, где X = {1,5}, Y = {2,3}. Совпадает ли он с графиком У ´ X?
16. Дайте определение бинарного отношения на множестве.
17. Обведите кружком номер правильного ответа. Областью определения бинарного отношения R называется множество
а) {(х, у)| (х, у) Î R};
б) {х| (х, у) Î R};
в) {у| (х, у) Î R}.
18. Какими способами можно задать бинарное отношение?
19. Какое отношение является рефлексивным?
20. Какой особенностью обладает матрица рефлексивного отношения? А матрица симметричного отношения?
множество натуральных чисел;
___ Q; 
___ R; p ___ Z.
Является ли булеаном множества {а,b,с} система подмножеств {а}, {b}, {с} ?
Является ли разбиением множества {а,b,с} система подмножеств {a,b},{b,с},{а,с} ?