Фактор-множество. Упорядоченное множество
Определение 1. Отношениеrна A есть отношение эквивалентности, еслионо рефлексивно, симметрично и транзитивно. Отношение эквивалентности arb часто обозначается: a ~ b.
Пример 1. Отношение равенства на множестве целых чисел есть отношение эквивалентности на множестве людей X.
Пример 2.Пусть ¢ - множество целых чисел. Назовем два числа x и y из ¢ сравнимыми по модулю m (mÎ¥) и запишем , если равны остатки этих чисел от деления их на m, т.е. разность (x-y) делится на m.
Отношение «сравнимых по модулю m целых чисел» есть отношение эквивалентности на множестве целых числе ¢. В самом деле:
это отношение рефлексивно, т.к. для "x΢ имеем x-x=0, и, следовательно, оно делится на m;
это отношение симметрично, т.к. если (x-y) делится на m, то и (y-x) тоже делится на m;
это отношение транзитивно, т.к. если (x-y) делится на m, то для некоторого целого t1 имеем , а если (y-z) делится на m, то для некоторого целого t2 имеем , отсюда , т.е. (x-z) делится на m.
Определение 2. Отношение r на A есть отношение частичного порядка, если оно рефлексивно, антисимметрично и транзитивно и обозначается символом °.
Частичный порядок важен в тех ситуациях, когда мы хотим как-то охарактеризовать старшинство. Иными словами, решить при каких условиях считать, что один элемент множества превосходит другой.
Пример 3. Отношение x£y на множестве действительных чисел есть отношение частичного порядка.
Пример 4. Во множестве подмножеств некоторого универсального множества U отношение AÍB есть отношение частичного порядка.
Пример 5. Схема организации подчинения в учреждении есть отношение частичного порядка на множестве должностей.
Прообразом отношения частичного порядка является интуитивное понятие отношения предпочтения (предшествования). Отношение предпочтения выделяет класс задач, которые можно объединить, как задача о проблеме выборанаилучшего объекта.
Формулировка задачи: пусть имеется совокупность объектов A и требуется сравнить их по предпочтительности, т.е. задать отношение предпочтения на множестве A и определить наилучшие объекты.
Отношение предпочтения P, которое можно определить как «aPb, a, bÎA Û объект a не менее предпочтителен, чем объект b» является по смыслу рефлексивным и антисимметричным (каждый объект не хуже самого себя, и, если объект a не хуже b и b не хуже a, то они одинаковы по предпочтительности). Естественно считать, что отношение P транзитивно (хотя в случае, когда, например, предпочтения обсуждаются группой лиц с противоположными интересами, это свойство может быть нарушено), т.е. P – отношение частичного порядка.
Один из возможных способов решения задачи сравнения объектов по предпочтительности – ранжирование, т.е. упорядочение объектов в соответствии с убыванием их предпочтительности или равноценности. В результате ранжирования мы выделяем «наилучшие» или «наихудшие» с точки зрения отношения предпочтения объекты.
Области применения задачи о проблеме выбора наилучшего объекта: теория принятия решений, прикладная математика, техника, экономика, социология, психология.