WikiSort.ru - Не сортированное

Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей.

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

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

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

Варианты

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

${\displaystyle \forall x\forall y(xRy\lor yRx)}$ .

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

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

Строгий порядок

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

${\displaystyle \forall x\neg (xRx)}$ ,

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

Замечание. Одновременная антирефлексивность и транзитивность отношения влечёт асимметричность, которое является более сильным условием, чем антисимметричность. Поэтому отношение является отношением строгого порядка тогда и только тогда, когда оно антирефлексивно и транзитивно.

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

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

${\displaystyle R_{\prec }=R\setminus \{(x,x)|x\in X\}}$  — строгий порядок.

Примеры

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

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

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

История

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

См. также

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

Ссылки

Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её.