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

Означення 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-12-22; просмотров: 1596;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.007 сек.