Метки: Отношение порядка определение, отношение порядка упорядоченные множества, отношение порядка и предпорядка, отношение порядка на множестве рациональных чисел, отношение порядка между множествами, отношение порядка предпорядка, отношение порядка как по-английски.
Бинарное отношение на множестве называется отношением порядка, или отношением частичного порядка, если имеют место
Множество , на котором введено отношение частичного порядка, называется частично упорядоченным.
Отношение , удовлетворяющее условиям рефлексивности, транзитивности, антисимметричности также называют нестрогим, или рефлексивным частичным порядком и обычно обозначают символом . Если условие рефлексивности заменить на условие антирефлексивности:
то получим определение строгого, или антирефлексивного частичного порядка, обозначаемое обычно символом . В общем случае, если — транзитивное, антисимметричное отношение, то
Отношение частичного порядка называется линейным порядком, если выполнено условие
Множество , на котором введено отношение линейного порядка, называется линейно упорядоченным, или цепью.
Отношение , удовлетворяющее только условиям рефлексивности и транзитивности, называется квазипорядком, или предпорядком.
Содержание |
Размерность Душника — Миллера (англ.) (иногда называемая просто размерность) частичного порядка — это наименьшее количество отношений линейного порядка, пересечение которых равно данному частичному порядку. Задача распознавания того, превосходит ли размерность данного конечного частичного порядка число принадлежит к классу P при но является NP-полной при [1]
Знаки и изобретены Хэрриотом.
| Это заготовка статьи по математике. Вы можете помочь проекту, исправив и дополнив её. |
Tags: Отношение порядка определение, отношение порядка упорядоченные множества, отношение порядка и предпорядка, отношение порядка на множестве рациональных чисел, отношение порядка между множествами, отношение порядка предпорядка, отношение порядка как по-английски.