Квазипорядок

Весовые функции

Отношение строгого порядка

Отношение, наделенное свойства­ми транзитивности и антирефлексивности (следствиями этих двух свойств являются также асимметричность и антисимметричность), называют отношением строгого порядка и обозначают символом <. Свойство антирефлексивности означает, что элемент множества не может сравниваться сам с собой (как в случае строгого неравенства или строгого включения). В отличие от него введенное в (5.1) отно­шение называют нестрогим порядком. Между отношениями строгого и нестрогого порядка имеют место соотношения: , где Е — тождественное отношение.

 

Пусть на множестве М определено ото­бражение (R - множество действительных чисел), ставя­щее в соответствие каждому объекту х из М некоторое действитель­ное число f(x). Это число называют весом, а отображение f - весо­вой функцией. Иногда понятие веса совпадает с буквальным смыс­лом этого слова (вес детали какого-либо механизма, атомный вес химического элемента и т.п.). Но весом может служить и любая числовая характеристика объекта (сопротивление резистора, объем тела, площадь участка, число баллов спортсмена и т. п.).

Если отображение f взаимно-однозначно, то на множестве М можно определить совершенно строгий порядок условием: х < у,если . Действительно, поскольку не существует объектов с равными значениями весовой функции, то для любой пары (х, у) справедливо либо , либо , т. е. все элементы сравнимы, и отношение антирефлексивно. В то же время оно транзитивно, т.к. как для элементов х, у, г Î М из f(x)<f(y) и f(y)< f(z) следует f(x) < f(z).

Примерами совершенно строгого упорядочения множества, на котором определено инъективное отображение (весовая функция) являются: периодическая система Менделеева, расположение спортсменов по совокупности полученных балловпри условии, что нет одинаковых результатов и т. п.

Если отображение не инъективно, т.е. два различных объекта х и у из М могут иметь равные веса , то отношение между ними не является антисимметричным и, следовательно, не удовлетворяет определению порядка. В то же время, как показано ранее, с отображением можно связать разбиение множества М на классы эквивалентности. Каждый из них объединяет различные эле­менты из М с равными весами, причем этот вес служит представи­телем соответствующего класса.

Теперь можно говорить об упорядочении совокупности классов эквивалентности некоторого множества М по их представителям. Так как система представителей не содержит одинаковых элементов (в противном случае соответствующие им классы объединились бы в общий класс эквива­лентности), то на этой системе как на множестве можно определить строгий порядок. Такое упорядочение отождествляет элементы множества М, принадлежащие к одному и тому же классу эквива­лентности, и определяет на этом множестве квазипорядок (псевдпорядок). Говорят также, что строгий порядок на множестве классов эквивалентности множества М индуцируется квази­порядком.

Квазипорядок удовлетворяет условиям рефлексивности и тран­зитивности, Он является обобщением эквивалентности (в определение не входит свойство симметричности) и нестрогого порядка (не обязательно свойство антисимметричности). Отношение, явля­ющееся одновременно эквивалентностью и нестрогим порядком, есть тождественное равенство. Можно также показать, что если А - квазипорядок, то - эквивалентность. Совершенный ква­зипорядок индуцирует и совершенно строгий порядок на мно­жестве классов эквивалентности. Классы эквивалентности множества М с квазипорядком, представляющие собой такие множества, где весо­вая функция принимает фиксированные значения, обычно называ­ются областями уровня.