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

Определение 1. Отношениеrна A есть отношение эквивалентности, еслионо рефлексивно, симметрично и транзитивно. Отношение эквивалентности a r b часто обозначается: 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, то для некоторого целого t ₁ имеем , а если (y - z) делится на m, то для некоторого целого t ₂ имеем , отсюда , т.е. (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 – отношение частичного порядка.

Один из возможных способов решения задачи сравнения объектов по предпочтительности – ранжирование, т.е. упорядочение объектов в соответствии с убыванием их предпочтительности или равноценности. В результате ранжирования мы выделяем «наилучшие» или «наихудшие» с точки зрения отношения предпочтения объекты.

Области применения задачи о проблеме выбора наилучшего объекта: теория принятия решений, прикладная математика, техника, экономика, социология, психология.