5. Отношение порядка

5.1. Упорядоченность

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

1. х  у (рефлексивность);

2. х  у  у  z  х  z (транзитивность);

3. х  у  у  х  х=у (антисимметричность).

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

В общем случае может оказаться, что для некоторых пар (х, у) ни одно из соотношений х  у и у  х не имеет места (такие эле­менты называют несравнимыми). Тогда говорят, что множество частично упорядочено. Типичными примерами частичного порядка являются включение, отношение «быть делителем» и т. п. Так, отно­шение включения на множестве подмножеств некоторого универсу­ма рефлексивно, транзитивно и антисимметрично, но среди всевозможных подмножеств имеются такие, что ни одно из соотношений ХY и Y Х для них не имеет места. Аналогично не все пары элементов из множества целых чисел находятся в отно­шении «быть делителем».

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

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

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

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

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

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