Ставлення еквівалентності є узагальненням відносини рівності: еквівалентні елементи вважаються «рівними». Узагальненням звичайного відносини служать відносини порядку.
Відношення називається предпорядка або квазіпорядком, якщо R рефлексивно і транзитивне.
на безлічі X = є предпорядка.
Рефлексивне, антисиметричною, транзитивне відношення називається ставленням несуворого порядку і позначається символом.
Антирефлексивне, антисиметричною, транзитивне відношення називається ставленням суворого порядку і позначається символом. Відносини суворого і несуворого порядків інакше називають відносинами впорядкованості. Ставлення, зворотне відношенню впорядкованості, також є відношенням упорядкованості, тобто () =.
1. Нехай Y - деякий безліч, тоді відношення включення на безлічі всіх підмножин P (Y) є відношенням нестрогого порядку.
2. Ставлення «х старше у» на деякій множині людей є відношенням строгого порядку.
Безліч Х з заданим в ньому відношенням порядку називається впорядкованим цим ставленням. Якщо будь-які два елементи х і у безлічі Х знаходяться між собою в відношенні порядку, то безліч Х називається лінійно впорядкованим або ланцюгом, інакше безліч Х називається частково упорядкованим. У частково впорядкованій множині можна виділити ланцюг. Ланцюг з повторюваними елементами називається мультіцепью. Якщо між елементами х і у встановлено відношення порядку, то вони називаються порівнянними, інакше - непорівнянні. Антіцепью (сімейством Шпернера) називається підмножина частково впорядкованої множини, в якому будь-які два елементи непорівнянні. Спеціальним типом частково впорядкованої множини є інтервал | x, y] = (замкнутий) або (x, y) P = (відкритий).
Двоїстим до частково впорядкованого безлічі називається частково впорядкована множина, певне на тому ж носії за допомогою зворотного відносини. Це поняття лежить в основі принципу подвійності, який часто формулюють у вигляді: якщо деяке твердження справедливо для частково впорядкованих множин, то справедливо і двоїсте твердження, тобто твердження, що стосується подвійних частково впорядкованих множин.
Розглянемо безліч Х із заданим на ньому відношенням часткового порядку.
Кажуть, що елемент y покриває елемент x. якщо х у й не існує ніякого елемента zX. такого що х z у. Таким чином, у покриває х тоді і тільки тоді, коли х у й [х, у] = х, у>. Будь-яке частково впорядкована множина можна представити у вигляді схеми. Діаграмою Хассе частково впорядкованої множини Х називаючи-ється граф, вершинами якого є елементи множини X. а пара (х, у) утворює ребро, якщо елемент у покриває елемент х. і такий що, якщо ху. то у малюють з більшою вертикальної координатою ніж х.
Приклад. Ставлення включення на булеані Р (Х), де Х = а, b, с>. Воно є частково впорядкованим безліччю. Безліч Р (Х) містить вісім елементів: <. a>, b>, c>, a, b>, a, c>, b, c>, a, b, c >>. Діаграма Хассе для цього відносини матиме вигляд (рис. 2.2).
Правило читання діаграм Хассе полягає в тому, що ху. якщо можна пройти з точки х в точку у. слідуючи уздовж висхідних відрізків з'єднують точки. Зміна напряму руху дозволяється лише в точках діаграми.
Приклад. Нехай А =. Розглянемо відношення часткового порядку ≤ на цій множині, що задається за правилом: x ≤yy ділиться на x. Діаграма Хассе зображена на рис.2.3.
Зауважимо, що діаграми Хассе цих двох відносин збігаються
Нехай Х і Y два частково впорядкованих множини. Якщо їх діаграми Хассе збігаються, то ці частково впорядковані множини мають однакову структуру.
Приклад. На рис. 2.4 зображена діаграма Хассе лінійно впорядкованої множини Х = зі звичайним відношенням порядку (≤) на безлічі натуральних чисел, що не перевершують восьми.
Нехай задано частково впорядкована множина X. Для елементів х і у з безлічі Х їх верхньою межею називається будь-який елемент Zх такий, що і. а їх нижньою гранню - будь-який елемент tX. такий, що х і tу. Мовою діаграм Хассе ху означає, що існує шлях з x в y; верхня межа x і y - це вершина, в яку є шлях з x і y; нижня межа x і y - це вершина з якої є шлях і в x і в y. У загальному випадку для деяких елементів верхня і нижня межа може не існувати або бути неєдиним, причому різні верхні (або нижні) грані можуть бути непорівнянні.
Приклад. На рис. 2.5 а) зображена діаграма Хассе безлічі. у якого елементи не мають верхньої межі, а елементи - нижньої межі. На рис. 2.5 б) зображена діаграма Хассе безлічі у якого всі елементи мають верхні і нижні межі, проте, наприклад, і мають дві незрівнянні верхні межі.