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

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

Пусть Х – произвольное множество. Отношение Ф на множестве называют отношением частичного порядка, если оно обладает следующими свойствами:

· рефлексивности – х Ф х;

· антисимметричности – отношения х Ф у и у Ф х выполняются только при х = у;

· транзитивности – если х Ф у и у Ф z, то х Ф z.

Отношение частичного порядка обозначают символом «≤» При этом элементами x, y и z могут быть объекты любой природы: числа, геометрические фигуры, слова и т.д. Например, упорядочивание слов, терминов,понятий в различных словарях осуществляется в соответствии с отношением частичного порядка и называется лексикографическим порядком.

Содержательный смысл частичной упорядоченности означает предшествование одного элемента множества относительно другого.

Если бинарное отношение Ф на множестве Х антирефлексивно и транзитивно, то оно называется отношением строгой упорядоченности и обозначается символом «<». Доказано, что для отношения строгого порядка определяющими свойствами являются его антирефлексивность и транзитивность, а антисимметричность следует из этих двух свойств. Таким образом, отношение строгого порядка всегда антисимметрично.

В качестве отношений частичного порядка можно привести следующие примеры.

1. Отношение на множестве действительных чисел R. Так как действительные числа являются расширением множества Z целых чисел, то это отношение является частичным и для Z.

2. Схема организации подчинения в учреждении представляет отношение частичного порядка на множестве должностей. Так, например, между преподавателями кафедр установлен частичный порядок, поскольку среди них может быть по нескольку ассистентов, доцентов и профессоров.

Примерами отношений строгого порядка являются:

1. Отношение х < y на множестве R.

2. Расположение спортсменов или команд в турнирной таблице на множестве всех мест (на одном месте не могут находиться более одного спортсмена или команды).

Последний пример наталкивает на размышления о том, что итоговая турнирная таблица не всегда однозначно определяет силу спортсменов или команд. Ниже расположенный в турнирной таблице спортсмен не обязательно слабее выше расположенного. Более того, часто ниже стоящий спортсмен в личных встречах побеждал выше стоящего. Это говорит о том, что упорядочивание на множествах не ограничивается двумя рассмотренными видами отношений порядка.

Очевидно, что, комбинируя свойства отношений, можно получать различной степени порядки на множествах. Так, например, говорят об отношении квазипорядка (квази – почти), когда отношение транзитивно и рефлексивно. В общей теории множеств существуют и другие виды отношений порядка. Но их рассмотрение выходит за рамки данного учебного пособия.