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

Антисимметричное транзитивное отношение называется отношением Порядка. Отношение порядка может быть рефлексивным, и тогда оно называется отноше­нием Нестрогого порядка. Отношение порядка может быть антирефлексивным, и тогда оно называется отношением Строгого порядка. Отношение порядка мо­жет быть полным (линейным), и тогда оно называется отношением Полного, Или Линейного порядка. Отношение порядка может не обладать свойством полноты (линейности), и тогда оно называется отношением Частичного порядка. Обычно отношение строгого порядка (полного или частичного) обозначается знаком <, а отношение нестрогого порядка — знаком ≤. Отношение порядка в общем случае обозначается знаком. Бинарное отношение, которое только рефлексивно и транзитивно, называется Отношением предпорядка.

Пример 1.Отношение < на множестве чисел является отношением строгого полного поряд­ка. Отношение ≤ на множестве чисел является отношением нестрогого полного порядка.

Пример 2.Рассмотрим множество {1,2,3} и отношение R = {(1,1), (1,2), (1,3), (2,2), (3,1), (3,2), (3,3)}. Это отношение рефлексивно, так как здесь присутствуют элементы (1,1), (2,2), (3,3). Это отношение транзитивно, так как из присутствия элементов (х, у),

(у, z) следует присутствие элемента (х, z). В самом деле, у нас есть (1,3), (3,2), и есть (1,2). Также имеются элементы (3,2), (2,2) и есть элемент (3,2). Аналогично и для элементов (3,1), (1,2) есть (3,2), для (1,2), (2,2) — элемент (1,2). Следовательно, R есть отношение предпорядка.

Пример 3.Теперь рассмотрим множество Х1× Х2 и попробуем задать на этом множестве отношение порядка, т. е. введем сравнение между парами элементов из Х1 и 1 Х2 . При этом пусть <Х1,R1> и <Х2, R2> — упорядоченные множества.

Это можно сделать, например, так. Определим отношение П условием: (a1,a2)П(b1,b2) ↔a1R1b1 ,a2R2b2 . Получится отношение порядка на Х1× Х2.

Такое отношение рефлексивно, так как a1R1a1 ,a2R2a2 и, следовательно, (a1,a2)П(a1,a2).

Далее П антисимметрично, так как (a1,a2)П(b1,b2) , (a1,a2) П (a1,a2) следует (a1,a2) = (b1,b2). В самом деле, из a1R1b1, b1R1a1 получаем a1= b1, а из a2R2b2, b2R2a2 следует a2 = b2.

Это отношение также и транзитивно. Пусть (a1,a2)П(b1,b2), (b1,b2)П(c1,c2).

Отсюда (a1,a2)П(c1,c2), так как a1R1b1, b1R1c1 влечет a1R1c1, а a2R2b2, b2R2c2 – a2R2c2.

Такое отношение порядка называется Отношением Парето.

Множество, на котором определено отношение частичного порядка, называется Частично упорядоченным. Множество, на котором определено отношение полного порядка, называется Вполне упорядоченным.

Пример. Множество чисел упорядочено линейно, а булеан упорядочен частично.

Элемент Х Множества М С отношением порядка называется Минимальным, Если не существует меньших элементов: УϵМ у х & у≠х.

Элемент аϵМ называется Максимальным в упорядоченном множестве М, если из аХ следует х = а. Всякий наибольший элемент является максимальным. Обратное неверно.

Пример. Пустое множество Ø является минимальным элементом булеана по включению.

Теорема. Во всяком конечном непустом частично упорядоченном множестве существует минимальный элемент.

Доказательство.

От противного. Пусть (Х ϵ М У ϵМ у Х).

ТогдаXϵМYϵMyX(ui)i=1∞Iui+1<ui&ui+1 ≠ui .

Поскольку |M| <∞, имеемI, ji<j&ui= uj.

Но по транзитивностиuiUi+1…UjUi+1 Uj = ui.

Таким образом, ui+1Ui&ui+1UiUi+1= ui – противоречие.

Вполне упорядоченное конечное множество содержит один минимальный элемент, а в произвольном конечном частично упорядоченном множестве их может быть несколько.

Теорема. Всякий частичный порядок на конечном множестве может быть до­полнен до линейного.

< Предыдущая		Следующая >