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

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

Пример 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 Х₂ . При этом пусть <Х₁,R₁> и <Х₂, R₂> — упорядоченные множества.

Это можно сделать, например, так. Определим отношение П условием: (a₁,a₂)П(b₁,b₂) ↔a₁R₁b₁ ,a₂R₂b₂ . Получится отношение порядка на Х₁× Х₂.

Такое отношение рефлексивно, так как a₁R₁a₁ ,a₂R₂a₂ и, следовательно, (a₁,a₂)П(a₁,a₂).

Далее П антисимметрично, так как (a₁,a₂)П(b₁,b₂) , (a₁,a₂) П (a₁,a₂) следует (a₁,a₂) = (b₁,b₂). В самом деле, из a₁R₁b₁, b₁R₁a₁ получаем a₁= b₁, а из a₂R₂b₂, b₂R₂a₂ следует a₂ = b₂.

Это отношение также и транзитивно. Пусть (a₁,a₂)П(b₁,b₂), (b₁,b₂)П(c₁,c₂).

Отсюда (a₁,a₂)П(c₁,c₂), так как a₁R₁b₁, b₁R₁c₁ влечет a₁R₁c₁, а a₂R₂b₂, b₂R₂c₂ – a₂R₂c_2.

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

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

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

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

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

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

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

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

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

ТогдаxϵМyϵMyx(u_i)_i=1^∞iu_i+1<u_i&u_i+1 ≠u_i .

Поскольку |M| <∞, имеемi,ji<j&u_i= u_j.

Но по транзитивностиu_iu_i+1…u_ju_i+1 u_j = u_i.

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

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

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