Відношення порядку

Означення 1.3.14. Бінарне відношення R називають відношенням строгого порядку, коли воно антисиметричне і транзитивне. Позначають: або .

Отже R – відношення строгого порядку, якщо:

1) ;

2) .

Наприклад, розташування символів у довільному скінченному алфавіті означує відношення строгого лексикографічного порядку, яке лежить в основі впорядкування словників, енциклопедій, індексів, довідників, списків, таблиць тощо.

Означення 1.3.15. Якщо відношення порядку є рефлексивним (), то його називають відношенням часткового (нестрогого) або квазіпорядку. Позначають: або .

Наприклад, у числових множинах N, Q, R встановлено відношення строгого () і нестрогого () порядку.

Множину M, на якій задано відношення порядку, називають впорядкованою, аелементи a, b Î M – порівнюваними за відношенням R, якщо виконується або . Запис означає, що у множині відношення порядку .

Впорядковану множину M, в якій будь-які різні два елементи є порівнюваними між собою, називають лінійно впорядкованою множиною або ланцюгом. Відповідне відношення R (як строге, так і нестроге), задане на лінійно впорядкованій множині, називають лінійним (досконалим) порядком.

Очевидно, відношення рівності є відношенням часткового порядку на будь-якій множині M, цей порядок називають тривіальним.

Теорема 1.3.3. Якщо – відношення строгого (нестрогого) порядку, то обернене відношення – теж відношення строгого (нестрогого) порядку.

Нехай M частково впорядкована множина і A деяка непорожня підмножина множини M.

Означення 1.3.16. Верхньою гранню підмножини A Í M в множині M називається елемент b Î M такий, що a £ b всіх a Î A. Елемент b називається найбільшим елементом множини M, якщо b – верхня грань множини M. Відповідно, елемент c частково впорядкованої множини M називається нижньою гранню підмножини A Í M, якщо c £ a для будь-якого a Î A. Елемент c – найменший в множині M, якщо c – нижня грань самої множини M.

Означення 1.3.17. Елемент x Î M називається максимальним в множині M, якщо не існує елемента a Î M такого, що x < a. Відповідно, елемент n Î M називається мінімальним у множині M, якщо не існує елемента a Î M такого, що a < n.

У лінійно впорядкованій множині поняття найбільшого і максимального (найменшого і мінімального) елементів збігаються.

Дата добавления: 2014-10-17