Порядковость
Порядковость — свойство множества, связанное с наличием на нём отношения порядка. Формально говорят, что на множестве A задано отношение ≤, которое является частичным порядком, если выполняются свойства рефлексивности, антисимметричности и транзитивности: \(\forall x\in A\; (x\le x)\), \(\forall x,y\in A\; (x\le y \land y\le x \Rightarrow x=y)\), \(\forall x,y,z\in A\; (x\le y \land y\le z \Rightarrow x\le z)\). Если дополнительно любые два элемента сравнимы (то есть для любых x, y выполняется либо x ≤ y, либо y ≤ x), такое отношение называется линейным (тотальным) порядком: \(\forall x,y\in A\; (x\le y \lor y\le x)\). Понятие «порядковость» часто понимают как характеристику того, насколько множество можно упорядочить при помощи подходящего отношения.
Порядковость используется в самых разных разделах математики и информатики: при сортировке данных, при анализе частично упорядоченных множеств (poset), в теории графов и комбинаторике (например, при разбиении на цепи и антицепи), а также в теории решёток и алгебраических структурах. На упорядоченных множествах вводят понятия минимального и максимального элементов, наименьшего и наибольшего элемента; минимальность элемента x формулируется как условие: \(\forall y\in A\; (y\le x \Rightarrow y=x)\). Понимание порядка позволяет строить диаграммы Хассе () и применять алгоритмы поиска экстремумов в дискретных структурах.
Примеры. 1) Множество натуральных чисел N с обычным сравнением ≤ образует линейный порядок: любые два числа сравнимы, поэтому это иллюстрация полной порядковости. 2) Множество всех подмножеств множества X с включением ⊆ — частично упорядоченное множество: не все пары подмножеств сравнимы (есть несравнимые элементы), поэтому это пример частичной порядковости; такое множество удобно изображать диаграммой Хассе (). 3) На небольшом множестве A = {a,b,c} можно задать отношение порядка, в котором, например, a ≤ b, a ≤ c и никакие другие сравнения не выполняются; это даёт частичный порядок, где a — минимальный элемент, а b и c составляют антицепь (взаимно несравнимы). Такие простые примеры помогают развить интуицию о том, что значит «порядковость» множества и как она проявляется на практике.