Определение 8. Бинарное отношение r на множестве A называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.
Обычно отношение эквивалентности обозначается одним из символов: ~, , =, @, º, º(mod r). Используя вместо записи (a, b) Î r запись a b , можно придать определению 8.8 следующий вид.
Определение 8 ¢ . Бинарное отношение на множестве A называется отношением эквивалентности, если
1) "(aÎA) [a a],
2) "(a, b ÎA) [a b Þ b a],
3) "(a, b, c ÎA) [(a b) & (b c) Þ a c].
(Символ a b читается: "a эквивалентно b по отношению .)
Примеры. 1. Пусть A - множество прямых какой-нибудь плоскости. Рассмотрим отношение параллельности прямых, считая, что прямые a и b параллельны (a || b), если они лежат в одной и той же плоскости и либо совпадают, либо не пересекаются.
На основе данного определения и теорем школьной математики доказывается, что
1) "(aÎA) [a|| a],
2) "(a, b ÎA) [a|| b Þ b|| a],
3) "(a, b, c ÎA) [(a|| b) & (b|| c) Þ a|| c].
Таким образом, отношение параллельности прямых есть отношение эквивалентности на множестве A.
2. Пусть R - множество действительных чисел, m - фиксированное действительное число ¹ 0. Будем говорить, что числа a, b ÎR сравнимы по модулю m,и писать a º b(mod m), если существует такое целое число k, что a - b = k × m .
Так как a - a = 0×m , то a º a (mod m) для любого a Î R.
Пусть a º b(mod m). По определению сравнимости a - b = k × m, где k Î Z. Отсюда b - a = -k × m, где -k есть целое число. Следовательно, по определению сравнимости b º a (mod m).
Пусть a º b(mod m) и b º c(mod m). По определению сравнимости a-b = k1× m и b - c = k2× m,где k1, k2 Î Z. Отсюда a-c = (a-b) + (b-c) = k1× m + k2× m = (k1+ k2)× m, где k1+ k2 Î Z. Следовательно, по определению сравнимости a º c (mod m).
Таким образом, отношение сравнимости по mod m есть отношение эквивалентности на множестве R.
3. По теореме 2 отношение равенства множеств есть отношение эквивалентности на произвольной совокупности A множеств.
Также отношениями эквивалентности являются отношение равенства и отношение подобия треугольников плоскости.
4. Бинарное отношение r = {(a , b)½a , b ÎA, a - b делится на 3} на множестве A = {1, 2, 3, 4, 5, 6, 7} есть также отношение эквивалентности. Граф этого отношения изображен на рис. 1.9. Таблица отношения изображена ниже.
Граф, представляющий отношение эквивалентности, обладает свойствами:
1. Каждая вершина графа имеет петлю (рефлексивность).
Каждое ребро графа не ориентировано (симметричность).
2. Для каждой пары ребер, идущих от a к b и от b к c, имеется замыкающее ребро, идущее от a к c (транзитивность).
Таблица (матрица) отношения эквивалентности обладает свойствами:
1. Отмечены все клетки главной диагонали (рефлексивность).
2. Отмеченные клетки симметричны относительно главной диагонали (симметричность).
3.При надлежащей нумерации строк и столбцов, отмеченные клетки таблицы заполняют попарно непересекающиеся квадраты, главные диагонали которых составляют главную диагональ таблицы.
Упражнения: 1. Показать, что отношениям эквивалентности являются отношение подобия треугольников.
2. Привести примеры бинарных отношений, которые удовлетворяют двум из свойств рефлексивности, антирефлексивности, симметричности, антисимметричности, транзитивности, а не удовлетворяют остальным.
3. Перечислить все отношения эквивалентности на множествах {1, 2} и {1 ,2, 3}.
4. Является ли обратное отношение для отношения эквивалентности отношением эквивалентности.
5. Доказать, что пересечение отношений эквивалентности на множестве A, есть отношением эквивалентности на A.
6. Доказать теорему 1.