Отношение порядка

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Варианты[править | править вики-текст]

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

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

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

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

Строгий порядок[править | править вики-текст]

Если условие рефлексивности заменить на условие антирефлексивности:

\forall x \neg(xRx),

то получим определение строгого, или антирефлексивного частичного порядка (обозначается обычно символом \prec).

В общем случае, если R — транзитивное, антисимметричное отношение, то

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

Примеры[править | править вики-текст]

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

Размерность Душника — Миллера[править | править вики-текст]

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

История[править | править вики-текст]

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

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]

  1. Yannakakis, Mihalis (1982), «The complexity of the partial order dimension problem», SIAM Journal on Algebraic and Discrete Methods 3 (3): 351—358