Отношение порядка
Эту статью следует викифицировать. |
Бинарное отношение на множестве называется отношением нестрогого частичного порядка (отношением порядка, отношением рефлексивного порядка), если имеют место
Множество , на котором введено отношение частичного порядка, называется частично упорядоченным. Отношение нестрогого частичного порядка часто обозначают знаком .
ВариантыПравить
Отношение частичного порядка называется линейным порядком, если выполнено условие
- .
Множество , на котором введено отношение линейного порядка, называется линейно упорядоченным, или цепью.
Отношение , удовлетворяющее только условиям рефлексивности и транзитивности, называется предпорядком, или квазипорядком.
Строгий порядокПравить
Если условие рефлексивности заменить на условие антирефлексивности:
- ,
то получим определение строгого, или антирефлексивного частичного порядка (обозначается обычно символом ).
Замечание. Одновременная антирефлексивность и транзитивность отношения влечёт асимметричность, которое является более сильным условием, чем антисимметричность. Поэтому отношение является отношением строгого порядка тогда и только тогда, когда оно антирефлексивно и транзитивно.
В общем случае, если — транзитивное, антисимметричное отношение, то
- — рефлексивный порядок
- — строгий порядок.
ПримерыПравить
- На множестве вещественных чисел отношения «больше» и «меньше» являются отношениями строгого порядка, а «больше или равно» и «меньше или равно» — нестрогого.
- Отношение делимости на множестве натуральных чисел является отношением нестрогого порядка.
Размерность Душника — МиллераПравить
Размерность Душника — Миллера (иногда называемая просто размерность) частичного порядка — это наименьшее количество отношений линейного порядка, пересечение которых равно данному частичному порядку. Задача распознавания того, превосходит ли размерность данного конечного частичного порядка число принадлежит к классу P при но является NP-полной при [1]
ИсторияПравить
Знаки и изобретены Хэрриотом.
См. такжеПравить
СсылкиПравить
- ↑ Yannakakis, Mihalis (1982), «The complexity of the partial order dimension problem», SIAM Journal on Algebraic and Discrete Methods 3 (3): 351—358
Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её. |