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

Среди рассмотренных выше (§ 2) примеров отношений имеются такие, как «меньше», «больше» между числами, «предшествует», «следует за» между точками прямой; «старше», «моложе» между людьми. Эти отношения являются антирефлексивными, асимметрич­ными и транзитивными.

Эти и подобные им, т. е. обладающие такими же свойствами,отношения принадлежат другому важному классу отношений, также
находящих широкое применение, их называют отношениямипорядка. >i«;)

Всякое антирефлексивное, асимметричное и транзитивное отно­шение в некотором множестве А называется отношением порядка.

Иногда такое отношение называют отношением строгого порядка, чтобы отли­чить его от отношения нестрогого порядка, являющегося рефлексивным, антисим­метричным и транзитивным. >ч

Обратимся еще раз к примеру 2 (§ 2) отношения «меньше» в множестве Л = {1, 2, 3, 4).

Тот факт, что главная диагональ истинностной таблицы (идущая от левого верхнего угла к правому нижнему) содержит одни только Л, или ни одна вершина графа (рис. 6) не имеет петли, отражает свойство антирефлексивности отношения «меньше».

Если в одной клетке таблицы стоит И, то в симметричной ей относительно главной диагонали клетке стоит Л, или если от одной вершины графа к другой проведена стрелка, то от второй к первой стрелки нет. В этом отражается свойство асимметричности

отношения «меньше».

Более того, легко заметить, что любая клетка таблицы запол­нена (буквой И или Л), или любые две вершины графа сое­динены стрелкой. Это означает, что для любой пары (х, у)£А² различных чисел {хФу) либо х<у, либо у<х. В таком случае говорят , что множество А упорядочено отношением «меньше» и ^.записывается так, что на первом месте располагается имя элемента, ^; который меньше всех остальных, на втором — имя элемента, мень­шего остальных, кроме первого и т. д., т. е.

Л={1, 2, 3,.4}.

Таким же отношением «меньше» упорядочивается и множество всех натуральных чисел N={1, 2, 3, ...}, к изучению которого мы перейдем в следующей главе.

Исходя из такого интуитивного понимания упорядочивания мно-' жества е- помощью отношения порядка, приходим к следующему определению упорядоченного множества.

Множество А называется упорядоченным, если введено отно­шение порядка р — {Р, А, А) и для любой пары (х, у)£А², если хфу, то хру или урх (т. е. любые два различных элемента множе­ства А находятся в данном отношении порядка Р). В этом случае говорят также, что множество А упорядочено отношением порядка р.

Так, например, когда говорят «натуральный ряд чисел», имеют в виду множество N всех натуральных чисел, упорядоченное отно­шением порядка «меньше», т. е. N = {1, 2, 3, 4, 5, ...}.