Отношение порядка
 |
Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей.
|
- Рефлексивность: <math>\forall x: xRx</math>;
- Антисимметричность: <math>\forall x, y: x R y \land y R x \Rightarrow x = y</math>;
- Транзитивность: <math>\forall x,y,z: x R y \land y R z \Rightarrow x R z</math>.
Множество <math>X</math>, на котором введено отношение частичного порядка, называется частично упорядоченным. Отношение нестрогого частичного порядка часто обозначают знаком <math>\preccurlyeq</math>.
Содержание
Варианты
Отношение частичного порядка <math>R</math> называется линейным порядком, если выполнено условие
- <math>\forall x \forall y (x R y \lor y R x)</math>.
Множество <math>X</math>, на котором введено отношение линейного порядка, называется линейно упорядоченным, или цепью.
Отношение <math>R</math>, удовлетворяющее только условиям рефлексивности и транзитивности, называется квазипорядком, или предпорядком.
Строгий порядок
Если условие рефлексивности заменить на условие антирефлексивности:
- <math>\forall x \neg(xRx)</math>,
то получим определение строгого, или антирефлексивного частичного порядка (обозначается обычно символом <math>\prec</math>).
Замечание. Одновременная антирефлексивность и антисимметричность отношения эквивалентна асимметричности:
- <math>\forall x,\;y\in M(xRy\Rightarrow\neg(yRx))</math>.
При этом из асимметричности автоматически вытекает антисимметричность. Таким образом, антисимметричность есть следствие антирефлексивности и транзитивности. Поэтому отношение является отношением строгого порядка тогда и только тогда, когда оно антирефлексивно и транзитивно.
В общем случае, если <math>R</math> — транзитивное, антисимметричное отношение, то
- <math>R_{\preccurlyeq} = R \cup \{(x, x) | x \in X\}</math> — рефлексивный порядок
- <math>R_{\prec} = R \setminus \{(x, x) | x \in X\}</math> — антирефлексивный порядок.
Примеры
- На множестве вещественных чисел отношения «больше» и «меньше» являются отношениями строгого порядка, а «больше или равно» и «меньше или равно» — нестрогого.
- Отношение делимости на множестве целых чисел являются отношением нестрогого порядка.
Размерность Душника — Миллера
Размерность Душника — Миллера (англ.) (иногда называемая просто размерность) частичного порядка — это наименьшее количество отношений линейного порядка, пересечение которых равно данному частичному порядку. Задача распознавания того, превосходит ли размерность данного конечного частичного порядка число <math>k,</math> принадлежит к классу P при <math>k<3,</math> но является NP-полной при <math>k \geqslant 3.</math>[1]
История
Знаки <math><</math> и <math>></math> изобретены Хэрриотом.
См. также
- Бинарное отношение
- Частично упорядоченное множество
- Линейно упорядоченное множество
- Предпорядок
- Теорема Шпильрайна
Напишите отзыв о статье "Отношение порядка"
Ссылки
- ↑ Yannakakis, Mihalis (1982), «The complexity of the partial order dimension problem», SIAM Journal on Algebraic and Discrete Methods 3 (3): 351—358
|
Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её. |
Отрывок, характеризующий Отношение порядка
Первое время своего приезда Николай был серьезен и даже скучен. Его мучила предстоящая необходимость вмешаться в эти глупые дела хозяйства, для которых мать вызвала его. Чтобы скорее свалить с плеч эту обузу, на третий день своего приезда он сердито, не отвечая на вопрос, куда он идет, пошел с нахмуренными бровями во флигель к Митеньке и потребовал у него счеты всего. Что такое были эти счеты всего, Николай знал еще менее, чем пришедший в страх и недоумение Митенька. Разговор и учет Митеньки продолжался недолго. Староста, выборный и земский, дожидавшиеся в передней флигеля, со страхом и удовольствием слышали сначала, как загудел и затрещал как будто всё возвышавшийся голос молодого графа, слышали ругательные и страшные слова, сыпавшиеся одно за другим.
– Разбойник! Неблагодарная тварь!… изрублю собаку… не с папенькой… обворовал… – и т. д.
Потом эти люди с неменьшим удовольствием и страхом видели, как молодой граф, весь красный, с налитой кровью в глазах, за шиворот вытащил Митеньку, ногой и коленкой с большой ловкостью в удобное время между своих слов толкнул его под зад и закричал: «Вон! чтобы духу твоего, мерзавец, здесь не было!»
Митенька стремглав слетел с шести ступеней и убежал в клумбу. (Клумба эта была известная местность спасения преступников в Отрадном. Сам Митенька, приезжая пьяный из города, прятался в эту клумбу, и многие жители Отрадного, прятавшиеся от Митеньки, знали спасительную силу этой клумбы.)
Жена Митеньки и свояченицы с испуганными лицами высунулись в сени из дверей комнаты, где кипел чистый самовар и возвышалась приказчицкая высокая постель под стеганным одеялом, сшитым из коротких кусочков.
Молодой граф, задыхаясь, не обращая на них внимания, решительными шагами прошел мимо них и пошел в дом.
Графиня узнавшая тотчас через девушек о том, что произошло во флигеле, с одной стороны успокоилась в том отношении, что теперь состояние их должно поправиться, с другой стороны она беспокоилась о том, как перенесет это ее сын. Она подходила несколько раз на цыпочках к его двери, слушая, как он курил трубку за трубкой.
На другой день старый граф отозвал в сторону сына и с робкой улыбкой сказал ему:
– А знаешь ли, ты, моя душа, напрасно погорячился! Мне Митенька рассказал все.
«Я знал, подумал Николай, что никогда ничего не пойму здесь, в этом дурацком мире».
– Ты рассердился, что он не вписал эти 700 рублей. Ведь они у него написаны транспортом, а другую страницу ты не посмотрел.
– Папенька, он мерзавец и вор, я знаю. И что сделал, то сделал. А ежели вы не хотите, я ничего не буду говорить ему.
– Нет, моя душа (граф был смущен тоже. Он чувствовал, что он был дурным распорядителем имения своей жены и виноват был перед своими детьми но не знал, как поправить это) – Нет, я прошу тебя заняться делами, я стар, я…
– Нет, папенька, вы простите меня, ежели я сделал вам неприятное; я меньше вашего умею.
