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

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

• Рефлексивность: $\forall x(xRx)$
• Транзитивность: $\forall x\forall y\forall z(xRy\land yRz\Rightarrow xRz)$;
• Антисимметричность: $\forall x\forall y(xRy\land yRx\Rightarrow x=y)$.

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

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

$\forall x\neg (xRx)$,

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

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

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

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

$\forall x\forall y(xRy\lor yRx)$

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

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

Примеры

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

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

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

История

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

См. также

• Бинарное отношение
• Частично упорядоченное множество
• Линейно упорядоченное множество
• Предпорядок
• Теорема Шпильрайна