Cdtrjyty

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

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

• 
  Рефлексивность: ∀x:xRx{displaystyle forall x:xRx};


• 
  Антисимметричность: ∀x,y:xRy∧yRx⇒x=y{displaystyle forall x,y:xRyland yRxRightarrow x=y};


• 
  Транзитивность: ∀x,y,z:xRy∧yRz⇒xRz{displaystyle forall x,y,z:xRyland yRzRightarrow xRz}.

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

Варианты |

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

∀x∀y(xRy∨yRx){displaystyle forall xforall y(xRylor yRx)}.

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

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

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

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

∀x¬(xRx){displaystyle forall xneg (xRx)},

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

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

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

R≼=R∪{(x,x)|x∈X}{displaystyle R_{preccurlyeq }=Rcup {(x,x)|xin X}} — рефлексивный порядок

R≺=R∖{(x,x)|x∈X}{displaystyle R_{prec }=Rsetminus {(x,x)|xin X}} — строгий порядок.

Примеры |

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


• Отношение делимости на множестве целых чисел являются отношением нестрогого порядка.

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

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

История |

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

См. также |

• Бинарное отношение


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


• Линейно упорядоченное множество


• Предпорядок


• Теорема Шпильрайна

Ссылки |

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