Задание отношений порядка

А. Пусть М – счетное множество (или последовательность), т.е. множество, элементы которого можно перенумеровать. Вообще, нумерация множества М – это взаимно однозначное отображение множества натуральных чисел на множество М. Тогда каждая нумерация множества индуцирует на нём линейный порядок, определяемый нумерацией.

Б. Пусть задано отображение f: M → R. Определим отношение p на М следующим образом:

х₁ p х₂ на М Û f(x₁) < f(x₂).

Проверим свойства этого отношения: а) иррефлексивность: неверно, что f(x) < f(x); б) антисимметричность: пусть х₁ p х₂ Þ f(x₁) < f(x₂) Þ (f(x₂) < f(x₁)) Þ (х₂ p х₁), т.е. отношение < антисимметрично; в) транзитивность: х₁ p х₂ & х₂ p х₃ означает f(x₁) < f(x₂) & f(x₂) < f(x₃) Þ f(x₁) < f(x₃) Þ х₁ p х₃.

Следовательно, это отношение строгого частичного порядка: несравнимые элементы – классы эквивалентности [x]_f; каждый класс по введённой терминологии является антицепью.

В. Заменим в предыдущем определении строгое неравенство на нестрогое.

Мы получим отношение а) рефлексивное: f(x) ≤ f(x) Þ х ´ х; б) транзитивное: х₁ ´ х₂ & х₂ ´ х₃ Þ f(x₁) ≤ f(x₂) & f(x₂) ≤ f(x₃) Þ f(x₁) ≤ f(x₃) Þ х₁ ´ х₃.

Таким образом, это отношение нестрогого квазипорядка (предпорядка). Внутри класса эквивалентности отношение симметрично, между элементами разных классов – антисимметрично. Если это отношение рассмотреть на классах эквивалентности, т.е. на фактор–множестве M/R_f, то мы получим отношение нестрогого линейного порядка.

И строгое отношение, и нестрогое, рассмотренные на фактор–множествах, являются отношениями линейного порядка. Это общее свойство биективных отображений – при которых классы эквивалентности вырождаются до одного элемента, как и в примере А.

Пусть есть два упорядоченных множества со своими отношениями порядка: (М₁, ´₁) и (М₂, ´₂). Отображение f: M₁ → М₂ называется монотонным, если из a ´ b следует f(a) ´ f(b).