Частично упорядоченное множество

---

Части́чно упоря́доченное мно́жество (сокр. ЧУМ) — математическое понятие, которое формализует интуитивные идеи упорядочения, расположения элементов в определённой последовательности. Неформально, множество частично упорядочено, если указано, какие элементы следуют за какими (какие элементы больше каких). В общем случае может оказаться так, что некоторые пары элементов не связаны отношением «следует за».

В качестве абстрактного примера можно привести совокупность подмножеств множества из трёх элементов ${\displaystyle \left\{x,y,z\right\}}$ (булеан данного множества), упорядоченную по отношению включения.

Отношением порядка, или частичным порядком, на множестве ${\displaystyle M}$ называется бинарное отношение ${\displaystyle \varphi }$ на ${\displaystyle M}$ (определяемое некоторым множеством ${\displaystyle R_{\varphi }\subset M\times M}$), удовлетворяющее следующим условиям^[1]:

Множество ${\displaystyle M}$, на котором задано отношение частичного порядка, называется частично упорядоченным. Если быть совсем точным^[2], то частично упорядоченным множеством называется пара ${\displaystyle \langle M,\varphi \rangle }$, где ${\displaystyle M}$ — множество, а ${\displaystyle \varphi }$ — отношение частичного порядка на ${\displaystyle M}$.

Размерность частично упорядоченного множества ${\displaystyle \langle M,\varphi \rangle }$ равна максимальной численности совокупности линейных порядков ${\displaystyle <_{i}}$ (${\displaystyle i\in I}$). В основе этого определения находится свойство продолжаемости частичного порядка до линейного.

Отношение частичного порядка обычно обозначают символом ${\displaystyle \leqslant }$, по аналогии с отношением «меньше либо равно» на множестве вещественных чисел. При этом, если ${\displaystyle a\leqslant b}$, то говорят, что элемент ${\displaystyle a}$ не превосходит ${\displaystyle b}$, или что ${\displaystyle a}$ подчинён ${\displaystyle b}$.

---