Отношение порядка | это... Что такое Отношение порядка? (original) (raw)

Бинарное отношение на множестве называется отношением порядка, или отношением частичного порядка, если имеют место

Множество , на котором введено отношение частичного порядка, называется частично упорядоченным.

Отношение , удовлетворяющее условиям рефлексивности, транзитивности, антисимметричности также называют нестрогим, или рефлексивным частичным порядком и обычно обозначают символом $\leqslant$ . Если условие рефлексивности заменить на условие антирефлексивности:

$\forall x \neg(xRx)$ ,

то получим определение строгого, или антирефлексивного частичного порядка, обозначаемое обычно символом . В общем случае, если — транзитивное, антисимметричное отношение, то

$R_{\leqslant} = R \cup \{(x, x) | x \in X\}$ — рефлексивный порядок

$R_{<} = R \setminus \{(x, x) | x \in X\}$ — антирефлексивный порядок.

Отношение частичного порядка называется линейным порядком, если выполнено условие

$\forall x \forall y (x R y \lor y R x)$

Множество , на котором введено отношение линейного порядка, называется линейно упорядоченным, или цепью.

Отношение , удовлетворяющее только условиям рефлексивности и транзитивности, называется квазипорядком, или предпорядком.

Примеры

На множестве вещественных чисел отношения «больше» и «меньше» являются отношениями строгого порядка, а «больше или равно» и «меньше или равно» — нестрогого.
Отношение делимости на множестве целых чисел являются отношением нестрогого порядка.

Размерность Душника — Миллера

Размерность Душника — Миллера (англ.) (иногда называемая просто размерность) частичного порядка — это наименьшее количество отношений линейного порядка, пересечение которых равно данному частичному порядку. Задача распознавания того, превосходит ли размерность данного конечного частичного порядка число принадлежит к классу P при k<3, но является NP-полной при $k \geqslant 3.$ [1]

История

Знаки и изобретены Хэрриотом.

См. также

Ссылки

↑ Yannakakis, Mihalis (1982), "The complexity of the partial order dimension problem", SIAM Journal on Algebraic and Discrete Methods 3 (3): 351–358