1.2. Бинарные отношения, их свойства. Отношения эквивалентности и порядка

Определение 1. Бинарным отношением на множестве называется любое подмножество. Условимся писать, если.

Пример 1. На множестве рассмотрим отношение порядка

.

Пример 2. На множестве натуральных чисел рассмотрим отношение делимости. Будем считать, что, еслиделится на. Например,.

Пример 3. Пусть имеется функция , заданная на. Длябудем считать, что, если. Множество всехявляется графиком функции.

Пример 4. На множестве матриц размерас действительными коэффициентами рассмотрим бинарное отношение:

, если .

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

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

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

Определение 5. Бинарное отношение на множественазывается транзитивным, если всегда, когдаи, паратакже принадлежит.

Определение 6. Бинарное отношение , обладающее свойствами рефлексивности, симметричности и транзитивности, называется отношением эквивалентности. Для элементамножествоназывается смежным классом отношения, содержащим.

Определение 7. Бинарное отношение , обладающее свойствами рефлексивности, антисимметричности и транзитивности, называется отношением порядка. Множество с заданным на нём отношением порядка называется частично упорядоченным. Два элемента, состоящие в отношении, называются сравнимыми.

Отметим, что отношения являются рефлексивными. Отношениеявляется рефлексивным только в случае. Отношение– симметрично, а– нет. Отношениесимметрично только в том случае, когда. Этому условию удовлетворяет, например, функция

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

Пример 5. Рассмотрим множество всех непрерывных функций на отрезке. Будем считать, что. Тогда множествобудет частично упорядоченным.

Определение 8. Частично упорядоченное множество , в котором любые два элемента сравнимы, называется линейно упорядоченным.

Множество действительных чисел с обычным отношением порядка является линейно упорядоченным, а множествоиз примера 5 – нет.

Определение 9. Разбиением множества называется любое семейство подмножеств, обладающее двумя свойствами

1) ;

2) .

Предложение. Пусть – отношение эквивалентности на множестве. Тогда семейство всех его смежных классов является разбиением множества.

Обратно. Для любого разбиения множества существует единственное отношение эквивалентностина множестве, для которого каждое из подмножеств разбиения является смежным классом отношения.

Доказательство. Пусть – отношение эквивалентности на множестве. Поскольку, то объединение всех смежных классов отношениядаст. Осталось только показать, что любые два смежных класса либо не пересекаются, либо совпадают.

Рассмотрим и. Допустим, что. Покажем, что. Действительно, пустьи. Тогда. Таким образом,. Аналогично,, откуда.

Обратно. Пусть имеется разбиение множества. Определимследующим образом:ипринадлежат одному и тому же подмножествуданного разбиения. Очевидно, отношениеобладает свойствами рефлексивности, симметричности и транзитивности и, значит, является отношением эквивалентности. Единственность отношениятакже очевидна.

Предложение доказано.

Определение 10. Пусть имеется множество , на котором задано отношение эквивалентности. Тогда можно образовать новое множество, элементами которого будут являться классы эквивалентности отношения. Это множество будет называться фактор-множеством множествапо отношениюи обозначаться.

Пример 6. Пусть – множество целых чисел. Зададим отношениеследующим образом. Длябудем считать, что, еслиделится на 5. Несложно проверить, чтобудет отношением эквивалентности. Фактор-множествобудет состоять из пяти элементов. Одним из элементов будет являться множество всех целых чисел, делящихся на 5. Другой элемент будет образовывать множество целых чисел, которые при делении на 5 дают в остатке 1 и т.д.