Отношение эквивалентности. Определение свойств бинарного отношения по его матрице

Решение.

Определение свойств бинарного отношения по его матрице

Отношение транзитивно тогда и только тогда, когда любые две вершины графа соединены одним и только одним ребром.

Отношение транзитивно тогда и только тогда, когда вместе с каждой парой ребер и граф содержит ребро.

Отношение антисимметрично тогда и только тогда, когда вместе с каждым ребром граф не содержит ребра. Граф антисимметричного отношения может содержать петли.

Замечание 2. Антисимметричность не совпадает с несимметричностью: например, отношение на множестве несимметрично, так как, а, и не антисимметрично, поскольку и, но. Диагональ непустого множества А () является примером симметричного и антисимметричного отношения. Вообще, любое подмножество обладает одновременно свойствами симметричности и антисимметричности.

Def: Отношение P называется транзитивным на А, если.

Пример 9. Отношение параллельности на множестве всех прямых плоскости, отношение включения на булеане непустого множества.

Def: Отношение P называется связным на А, если.

Пример 10. Отношение «меньше» на любом числовом множестве.

Пример 11. Определить свойства отношения Р по его графу.

1. Главная диагональ матрицы рефлексивного отношения P всегда состоит из одних единиц, так как, если.

P рефлексивно тогда и только тогда, когда главная диагональ матрицы || P || со- держит только единицы.

2. P – симметрично, тогда и только тогда, когда.

P симметрично тогда и только тогда, когда матрица симметрична относительно главной диагонали.

3. P – антисимметрично, тогда и только тогда, когда в матрице все элементы вне главной диагонали являются нулевыми.

P антисимметрично тогда и только тогда, когда матрица вне главной диагонали содержит только нули.

4. P – транзитивно, тогда и только тогда, когда.

P транзитивно тогда и только тогда, когда, где,.

Пример 12. Пусть,,,.

Изобразить графы отношений и, найти матрицу. Проверить с помощью матрицы, является ли отношение рефлексивным, симметричным, транзитивным.

def. Бинарное отношение на множестве А называется отношением эквивалентности на А, если оно рефлексивно, симметрично и транзитивно (на А).

Отношение эквивалентности часто обозначают символами ~ или ≡.

Пример 13. 1) Отношение равенства на любом множестве чисел.

2) Отношение параллельности на множестве прямых на плоскости.

3) Отношение подобия на множестве треугольников данной плоскости.

Пусть R - отношение эквивалентности на множестве А и.

def. Классом эквивалентности, порождённым элементом, называется множество.

То есть класс эквивалентности, порожденный элементом есть множество всех таких, что. Класс эквивалентности, порождённого элемента, обозначается через / R. Совокупность всех классов эквивалентности отношения R на множестве А обозначается через А/R.

def. Любой элемент класса эквивалентности называется представителем этого класса.

Пусть А - непустое множество.

def. Фактор-множеством множества А по отношению эквивалентности R называется множество A/R всех классов эквивалентности.

def. Разбиением множества А называется такое семейство его непустых подмножеств, объединение которых совпадений с множеством А, а пересечение любых двух различных из них пусто.

Теорема 2 (прямая теорема). Пусть R – отношение эквивалентности на (непустом) множестве А. Тогда фактор – множество A/R является разбиением множества А.