Отношение строгого порядка
Слово «порядок» часто применяют в самых различных вопросах. Офицер дает команду: «По порядку номеров рассчитайся», арифметические действия выполняются в определенном порядке, спортсмены становятся по росту, существует порядок выполнения операций при изготовлении детали, порядок слов в предложении.
Что же общего во всех случаях, когда говорится о порядке? В том, что в слово «порядок» вкладывается такой смысл: оно означает, какой элемент того или иного множества за каким следует (или какой элемент какому предшествует).
Отношение «х следует за у» транзитивно: если «х следует за у» и «у следует за z», то «x следует за z». Кроме того, это отношение должно быть антисимметричным: для двух различных х и у, если х следует за у, то у не следует за х.
Определение. Отношение R на множестве X называют отношением строгого порядка, если оно транзитивно и антисимметрично.
Выясним особенности графа и графика отношений строгого порядка.
Рассмотрим пример. На множестве X = {5, 7, 10, 15, 12} задано отношение R: «х < у». Зададим это отношение перечислением пар
R = {(5, 7), (5, 10), (5, 15), (5, 12), (7, 10), (7, 15), (7, 12), (10, 15), (10, 12), (12, 15)}.
Построим его граф. Мы видим, что граф данного отношения не имеет петель. На графе нет двойных стрелок. Если из х идет стрелка в у, а из у – в z, то из х идет стрелка в z (рис. 8).
Построенный граф позволяет расположить элементы множества X в таком порядке:
{5, 7, 10, 12, 15}.
На рис.6 (§ 6 этой главы) графы VII, VIII – это графы отношений строгого порядка.
Отношение нестрогого порядка
Отношению «меньше» в множестве действительных чисел противоположно отношение «не меньше». Оно уже не является отношением строгого порядка. Дело в том, при х = у, выполняются отношения х ³ у и у ³ х, т.е. отношение «не меньше» обладает рефлексивностью.
Определение. Отношение R на множестве X называют отношением нестрогого порядка, если оно рефлексивно, антисимметрично и транзитивно.
Такие отношения являются объединениями отношения строгого порядка с отношением тождества.
Рассмотрим отношение «не больше» (£) для множества
X = {5, 7, 10, 15, 12}. Построим его граф (рис. 9).
Граф отношения нестрогого порядка, в отличие от графа отношения строгого порядка, в каждой вершине имеет петли.
На рис. 6 (§ 6 этой главы) графы V, VI – это графы отношений нестрогого порядка.
Упорядоченные множества
Множество может оказаться упорядоченным (говорят также полностью упорядоченным) некоторым отношением порядка, другое же неупорядоченным или частично упорядоченным таким отношением.
Определение. Множество X называют упорядоченным некоторым отношением порядка R, если для любых двух элементов х, у из Х:
(х, у) Î R или (у, х) Î R.
Если R – отношение строгого порядка, то множество Х упорядочено этим отношением при условии: если х, у любые два неравных элемента множества Х, то (х, у) Î R или (у, х) Î R, или любые два элемента х, у множества Х равны.
Из школьного курса математики известно, что числовые множества N, Z, Q, R упорядочены отношением «меньше» (<).
Множество подмножеств некоторого множества не упорядочено введением отношения включения (Í), или строгого включения (Ì) в указанном выше смысле, т.к. существуют подмножества ни одно из которых не включается в другое. В этом случае говорят, что данное множество частично упорядочено отношением Í (или Ì).
Рассмотрим множество X = {1, 2, 3, 4, 5, 6} и в нем два отношения «меньше» и «делится на». Легко проверить, что оба эти отношения являются отношениями порядка. Граф отношения «меньше» можно изобразить в виде луча.
1 2 3 4 5 6
Граф отношения «делится на» можно изобразить лишь на плоскости.
Кроме того, на графе второго отношения есть вершины, не соединенные стрелкой. Например, нет стрелки, соединяющей числа 4 и 5 (рис. 10).
Первое отношение «х < у» называется линейным. Вообще, если отношение порядка R (строгого и нестрогого) на множестве X обладает свойством: для любых х, у Î Х либо хRy, либо yRx, то его называют отношением линейного порядка, а множество X – линейно упорядоченным множеством.
Если множество X конечно, и состоит из n элементов, то линейное упорядочивание Х сводится к нумерации его элементов числами 1,2,3, ..., n.
Линейно упорядоченные множества обладают рядом свойств:
1°. Пусть а, в, с – элементы множества X, упорядоченного отношением R. Если известно, что aRв и вRс, то говорят, что элемент в лежит между элементами а и с.
2°. Множество X, линейно упорядоченное отношением R, называется дискретным, если между любыми двумя его элементами лежит лишь конечное множество элементов этого множества.
3°. Линейно упорядоченное множество называется плотным, если для любых двух различных элементов этого множества существует элемент множества, лежащий между ними.