3.9. Отношение порядка. Диаграммы Хассе

Пусть А – непустое множество.

Определение 3.26. Отношение Р  А² называется предпорядком (квазипорядком), если оно рефлексивно и транзитивно.

Пример 3.17. Пусть А = a, b, c, d. Отношение Р = (a, a), (a, b), (a, c), (a, d), (b, b), (c, a), (c, b), (c, c), (c, d), (d, d) на множестве А является предпорядком (рис. 3.6).

З

b

аметим, что симметричный предпорядок является отношением эквивалентности.

Определение 3.27. Отношение Р  А² называется частичным порядком, если оно рефлексивно, транзитивно и антисимметрично. Таким образом, частичный порядок представляет собой антисимметричный предпорядок. Частичный порядок обозначается символом , а обратное ему отношение  ^-1 – символом  .

Определение 3.28. Отношение   А² называется строгим порядком, если оно определяется по следующему правилу: ( x, y  A) х  у  х  у и х  у.

Отношение строгого порядка не является частичным порядком, так как оно не рефлексивно.

Пример 3.18. Отношение из примера 3.17 не является частичным порядком, а отношение делимости на множестве целых чисел – является. 

Определение 3.29. Пусть   А² и х, у  А. Элементы х и у называются несравнимыми, если нельзя сказать, что х  у или у  х.

Пример 3.19. Пусть А = a, b, c, d. Отношение включения  на булеане P(A) является частичным порядком. Элементы B = {a, c} и C = {b, d} из P(A) являются несравнимыми, так как (B, C)   и (C, B)  . 

Определение 3.30. Частичный порядок   А² называется линейным порядком, если ( х, у  А) х  у или у  х.

Определение 3.31. Пусть А   и  – частичный (линейный) порядок на А. Упорядоченная пара  А,  > называется частично (линейно) упорядоченным множеством.

Другими словами, частично (линейно) упорядоченным множеством является непустое множество А, на котором зафиксирован некоторый частичный (линейный) порядок .

Пример 3.20. Пара  Z,  >, где  – отношение делимости на множестве Z, является частичным, но не линейным порядком. Пары  N,  > ,  R,  > с обычными отношениями  образуют линейно упорядоченные множества. 

Определение 3.32. Элемент а  А частично упорядоченного множества

 А,   называется максимальным (минимальным), если (хА) а  х (х  а) 

 х = а.

Определение 3.33. Элемент а  А частично упорядоченного множества

 А,   называется наибольшим (наименьшим), если ( х  А) х  а (а  х).

Наибольший (наименьший) элемент частично упорядоченного множества  А,   (если он существует) обозначается через max A (min А). Наибольший элемент часто называют единицей, а наименьший – нулем множества  А,  .

Теорема 3.11. Пусть  А,   является частично упорядоченным множеством, где А – непустое и конечное множество. Тогда  А,   содержит хотя бы один минимальный элемент, и если он является единственным, то он также является и наименьшим. Аналогично,  А,   содержит хотя бы один максимальный элемент, и если он является единственным, то он также является наибольшим. 

Пример 3.21. Частично упорядоченное множество  А,  , где

А = a, b, c, d, а граф отношения  изображен на рис. 3.7, имеет единственный минимальный и он же наименьший элемент a, максимальные элементы c и d, но не имеет наибольшего элемента. 

Пример 3.22. Частично упорядоченное множество  B,  , где

B = 1, 2, 3, 4, а граф отношения  изображен на рис. 3.8, имеет минимальные элементы 1 и 2, единственный максимальный и он же наибольший элемент 4, но не имеет наименьшего элемента. 

c

4

d

Замечание 3.6. Всякий наибольший элемент частично упорядоченного множества является максимальным, а всякий наименьший элемент – минимальным. Обратное утверждение, вообще говоря, неверно (см. примеры 3.21 и 3.22). 

Определение 3.34. Пусть  А,   – частично упорядоченное множество и В  А. Элемент а  А называется верхней (нижней) гранью подмножества В, если ( b  В) b  a (a  b).

Пример 3.23. Рассмотрим частично упорядоченное множество  R,   и

В = [0;1). Тогда любое число х  1 является верхней гранью В, а любое число

х  0 – нижней гранью В. 

Определение 3.35. Пусть  А,   – частично упорядоченное множество и В  А. Точной верхней (нижней) гранью подмножества В называется наименьшая верхняя (наибольшая нижняя) грань множества В.

Точная верхняя грань подмножества В обозначается через sup B (супремум), а точная нижняя грань – через inf B (инфимум).

Пример 3.24. В условиях примера 3.21 имеем, что sup В = 1, inf B = 0. 

Определение 3.36. Линейный порядок  на множестве А называется полным, если каждое непустое подмножество множества А имеет наименьший элемент.

Определение 3.37. Пусть  – полный порядок на непустом множестве А. Упорядоченная пара  А,  > называется вполне упорядоченным множеством.

Пример 3.25. Упорядоченная пара  N,   является вполне упорядоченным множеством, а  1;1,   не является, так как, например, полуинтервал (0;1, являющийся подмножеством -1;1, не содержит наименьшего элемента. 

Пусть  А,   – частично упорядоченное множество и x, y  А. Говорят, что элемент у покрывает элемент х, если х  у и не существует такого элемента z А, что х  z  y. Если А – любое конечное множество, то частично упорядоченное множество  А,   можно представить в виде схемы, в которой каждый элемент изображается точкой на плоскости, и если элемент у покрывает элемент х, то точки, изображающие элементы х и y, соединяют отрезком, причем точку, соответствующую элементу х, располагают ниже точки, соответствующей элементу у. Такие схемы называются диаграммами Хассе.

Пример 3.26. Диаграммы Хассе частично упорядоченных множеств

 А,   из примера 3.21 и  B,   из примера 3.22 изображены соответственно на рис.3.9 и 3.10.

Пример 3.27. а) Рассмотрим частично упорядоченное множество

 Р(А),  , где А = a, b, c, d и Р(А) = , a, b, c,a, b,b, c,a, c,

a, b, c. На рис. 3.11 изображена диаграмма Хассе, соответствующая

 Р(А),  . б) Пусть B = 1, 2, 3, 4, 5 , 6, 8 и  – обычное отношение порядка на множестве натуральных чисел, не превосходящих восьми. Диаграмма Хассе,

соответствующая линейно упорядоченному множеству  B,  , изображена на

рис. 3.12.

Рис. 3.11 Рис. 3.12