И порядка. Фактор-множество.

 

В данном параграфе будут рассмотрены некоторые виды бинарных отношений. Рассмотрим непустое множество и зададим на нём бинарное отношение . Отношение называется диагональю множества и определяет отношение равенства элементов множества .

Определение 1: Бинарное отношение называется рефлексивным, если для всякого элемента выполняется условие: , т. е. диагональ должна принадлежать отношению . Иначе можно записать: - элемент находится в отношении с самим собой.

Граф рефлексивного бинарного отношения содержит петли около каждой своей вершины.

 

Определение 2: Бинарное отношение называется антирефлексивным, если для всякого элемента выполняется условие: .

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

Определение 3: Бинарное отношение называется симметричным, если для произвольных элементов выполняется условие: , или иначе .

Каждая дуга симметричного графа обязательно имеет двойную стрелку (ребро). Если хотя бы для одной пара условие определения не выполняется, т. е. , то отношение симметричным не является.

Определение 4: Бинарное отношение называется антисимметричным, если для произвольных элементов и выполняется условие:

и , то .

Граф такого отношения имеет петли.

Определение 5: Бинарное отношение называется транзитивным, если для любых элементов выполняется следующее условие:

и , то .

Иначе можно написать: и , то . Читается: если находится в отношении с , а находится в отношении с , то находится в отношении с .

Определение 6: Бинарное отношение называется связным, если для любых справедливо утверждение:

.

Приведём примеры. Пусть рассматривается множество натуральных чисел. Зададим бинарное отношение на декартовом квадрате этого множества следующим образом: (элемент находится в отношении с элементом тогда и только тогда, когда делится на ). Проверим свойства отношения делимости натуральных чисел.

1) - рефлексивность выполняется, т. к. любое число делится без остатка само на себя.

2) из того, что не следует, что - симметричность не выполняется (например, , но ).

3) выполняется антисимметричность: если и , то .

4) выполняется транзитивность: если и , то .

5) связность не выполняется: если , то отсюда не следует, что и .

Таким образом, отношение делимости, заданное на множестве натуральных чисел, рефлексивно, антисимметрично и транзитивно.

 

Определение 7: Бинарное отношение называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Примеры: 1) отношение равенства на любом числовом множестве является отношением эквивалентности, т. к. каковы бы ни были числа a, b, c имеют место следующие утверждения:

а) ; б) ; в) .

2) отношение параллельности на множестве прямых плоскости – это отношение эквивалентности, так как для любых прямых справедливы следующие положения:

а) ||; б) ||, то ||; в) ||и ||, то ||.

3) отношение подобия на множестве всех треугольников также является рефлексивным, симметричным и транзитивным, а значит, является отношением эквивалентности.

Определение 8: Пусть - непустое множество, - множество всех подмножеств множества . Пусть - некоторая система подмножеств множества , т. е. . Система подмножеств называется разбиением множества , если выполняются следующие условия:

1) среди множеств системы нет ;

2) два различных множества из системы не пересекаются;

3) объединение всех множеств системы даёт множество .

Пример: Пусть , где и являются числовыми промежутками: , . Тогда система является разбиением для множества действительных чисел, т. к. выполнены все требования определения.

Определение 9: Пусть , - отношение эквивалентности на множестве , - произвольный элемент множества . Множество называется классом эквивалентности, порожденным элементом .

Определение 10: Множество всех классов эквивалентности по отношению эквивалентности называется фактор-множеством множества по отношению . Обозначают: . Согласно определению:

.

Примеры:

1) Для примера рассмотрим отношение сравнения на множестве целых чисел . Целые числа и называются сравнимыми по модулю , если их разность делится на без остатка. Обозначают: . Кратко это определение можно представить в виде:

.

Не сложно показать, что отношение сравнения является отношением эквивалентности, т. е. рефлексивно, симметрично и транзитивно. Найдём все классы эквивалентности и фактор-множество для случая .

а) рассмотрим элемент и . Класс эквивалентности, порождённый нулём, состоит из всех целых чисел, делящихся на 5 без остатка (0 – это остаток при делении на 5). Таким образом, имеем класс .

б) элемент порождает класс эквивалентности, состоящий из целых чисел, которые при делении на 5, дают в остатке 1. Имеем класс: .

в) аналогично рассуждая, получаем классы, порождённые элементами 2, 3, 4:

, , .

г) Класс, порождённый элементом 5, совпадает с классом, порождённым нулём:

.

Все найденные классы эквивалентности образуют фактор-множество:

, где - отношение сравнения по модулю 5.

2) Подобные конструкции встречаются и в школьной математике чрезвычайно часто. Известно, например, что фигурой на плоскости называется некоторое множество точек плоскости. Введем во множестве всех плоских фигур отношение эквивалентности, считая две фигуры эквивалентными, если их можно совместить движением. Фактор-множество по этому отношению эквивалентности состоит из классов таких, что любые две фигуры одного класса можно совместить движением. Отождествляя все фигуры одного класса, мы говорим, например, о равенстве фигур.

Теорема 1: Пусть , - отношение эквивалентности на множестве , тогда фактор-множество является разбиением множества .

Доказательство: Для доказательства достаточно показать, что фактор-множество удовлетворяет всем условиям определения разбиения множества.

1) Множество состоит из классов эквивалентности. Пусть - некоторый элемент фактор-множества. По условию теоремы, отношение - рефлексивно, значит , следовательно .

2) Нужно показать, что два различных класса не пересекаются. Пусть - такие классы эквивалентности, что . Покажем, что классы и не пересекаются. Допустим противное. Предположим, что , тогда найдётся элемент , который принадлежит этим двум классам: .

Пусть - произвольный элемент из класса , т. е. . Тогда и . Отсюда в силу симметричности отношения : и . Тогда, в силу транзитивности отношения : . Применяем те же рассуждения: и . Значит, , т. к. - транзитивно. Из последней записи видно, что . Таким образом, доказано включение: . Рассуждая аналогично, можно показать, что . Следовательно, , а это противоречит тому, что . Противоречие возникло из неверного допущения: . Значит, доказано, что два различных класса не пересекаются.

3) Доказательство последнего пункта определения разбиения можно получить непосредственно из определения фактор-множества. Теорема доказана.