Бинарные отношения. Разбиение множества

Между элементами множества могут быть установлены некоторые отношения, при этом указывается, какие элементы этого множества, взятые в определенномпорядке, состоят в данном отношении, а какие – нет. Например, во множестве R действительных чисел можно ввести следующее отношение . Очевидно, что это отношение определяется как подмножество прямого произведения R R, т.е.

.

Бинарным отношением на множестве A называется всякое подмножество . Если , то пишут .

Аналогично определяется n -парное отношение на множестве А:

Рассмотрим некоторые важные свойства бинарных отношений:

отношение на A называется рефлексивным, если

.

Отношение на A называется симметричным, если

.

Отношение - транзитивно, если

и .

Симметричное, рефлексивное и транзитивное отношение называется отношением эквивалентности. Для обозначения отношения эквивалентности используют знак ~.

Пример. Отношение на множестве R являются отношением эквивалентности, что очевидно:

1) ,

2) если ,

3) если , то .

Отношение эквивалентности на произвольном множестве связано с понятием разбиения этого множества. Разбиение множества A на подмножества (классы) называется представлением A в виде объединения непересекающихся подмножеств .

Пусть Æ разбито на классы . Рассмотрим бинарное отношение на множестве лишь тогда и только тогда, когда элементы x и y принадлежат одному классу .

Проверкой нетрудно убедиться, что введенное отношение является отношением эквивалентности. Таким образом, всякое разбиение множества определяет некоторое отношение эквивалентности на этом множестве. Верно и обратное.

Теорема. Всякое отношение эквивалентности ~ на множестве A определяет разбиение множества A на классы эквивалентности.

Действительно, каждому сопоставим ={ у, где ~ }. Тогда:

1) каждый класс Æ, т.к. x~x,

2) если и , то ~ , что очевидно: ~ , ~ , т.е. ~ , то в силу транзитивности ~ ,

3) если ~ , то . Действительно: ~ , где ~ , то ~ , т.е. , аналогично . Значит .

4) элементы разных классов не эквивалентны, что очевидно по пункту 3,

5) разные классы не пересекаются, что очевидно, в противном случае не выполнялся бы пункт 4.

Таким образом, A есть объединение всех классов. Новое множество, состоящее из полученных классов, называется факторпространством.