Изменения

== Определения =={{Определение|definition =[[Бинарное отношение]] <mathtex>R</mathtex> на [[Множества|множестве]] <mathtex>X</mathtex> называется '''отношением частичного порядка''', или (англ. '''отношением частичного порядка'partial order relation''), если имеют местооно обладает следующими свойствами:* ''[[Рефлексивное_отношениеРефлексивное отношение|Рефлексивность]](англ. ''reflexivity''): <mathtex>\forall x (xRx)a \in X: aRa</mathtex>.* ''[[Транзитивное_отношениеАнтисимметричное отношение|ТранзитивностьАнтисимметричность]](англ. ''antisymmetry''): <mathtex>\forall x a, b \forall y \forall z (x R y \land y R z \Rightarrow x R z)in X:</tex> если <tex>aRb</tex> и <tex>bRa</tex>, то <tex> a = b </mathtex>;.* ''[[Антисимметричное_отношениеТранзитивное отношение|АнтисимметричностьТранзитивность]](англ. ''transitivity''): <mathtex>\forall x a, b, c \forall y (x R y \land y R x \Rightarrow x = y)in X:</tex> если <tex>aRb</tex> и <tex>bRc</tex>, то <tex>aRc</tex>.}}Множество <tex>X</mathtex>, на котором введено отношение частичного порядка, называется '''частично упорядоченным'''.

Отношение частичного порядка также называют '''нестрогим порядком''' (англ. ''non-strict order'').{{Определение|definition =[[Бинарное отношение]] <tex>R</tex> на множестве <tex>X</tex> называется '''строгим отношением частичного порядка''' (англ. ''strict order relation''), если оно обладает следующими свойствами:* [[Рефлексивное отношение|Антирефлексивность]] (англ. ''irreflexivity''): <tex>\forall a \in X: aRa </tex> — не выполняется.* [[Антисимметричное отношение|Антисимметричность]] (англ. ''antisymmetry''): <tex>\forall a, b \in X:</tex> если <tex>aRb</tex> и <tex>bRa</tex>, то <tex> a = b </tex>.* [[Транзитивное отношение|Транзитивность]]: (англ. ''transitivity'') <tex>\forall a, b, c \in X:</tex> если <tex>aRb</tex> и <tex>bRc</tex>, то <tex>aRc</tex>.}}{{Определение|definition =[[Бинарное отношение]] <tex>R</tex> на множестве <tex>X</tex> называется '''отношением линейного порядка''' (англ. ''total order relation''), если оно является отношением частичного порядка и обладает следующим свойством: <tex>\forall a \in X \forall b \in X</tex> либо <tex>aRb</tex>, либо <tex>bRa</tex>.}}Множество <tex>X</tex>, на котором введено отношение линейного порядка, называется '''линейно упорядоченным''' (англ. ''total order'').{{Определение|definition =[[Бинарное отношение]] <tex>R</tex> на множестве <tex>X</tex> называется '''отношением полного порядка''' (англ. ''well-order relation''), если оно является отношением линейного порядка и обладает следующим свойством: <tex>\forall Y \subset X \exists a \in Y \forall b \in Y: aRb</tex>.}}Множество <mathtex>X</mathtex>, на котором введено отношение частичного полного порядка, называется '''частично полностью упорядоченным'''(англ. ''well-order'').

Отношение <math>R</math>, удовлетворяющее условиям рефлексивности, транзитивности, антисимметричности также называют ''нестрогим'', или ''рефлексивным частичным порядком'' и обычно нестрогого порядка обозначают символом <mathtex>\leqslant</mathtex>. Если условие рефлексивности заменить на условие антирефлексивности:: Запись вида <mathtex>a \forall x \neg(xRx)leqslant b</mathtex>,то получим определение ''строгого'', или ''антирефлексивного частичного порядка'', обозначаемое обычно символом <math><</math>.В общем случае, если читают как «<mathtex>Ra</mathtex> — транзитивное, антисимметричное отношение, то: меньше либо равно <mathtex>R_{\leqslant} = R \cup \{(x, x) | x \in X\}</math> — рефлексивный порядок: <math>R_{<} = R \setminus \{(x, x) | x \in X\}b</mathtex> — антирефлексивный порядок».

Отношение частичного строгого порядка обозначают символом <mathtex>R<</tex>. Запись вида <tex>a < b</mathtex> называется ''линейным порядком'', если выполнено условие: читают как «<mathtex>\forall x \forall y (x R y \lor y R x)a</mathtex>Множество меньше <mathtex>Xb</mathtex>, на котором введено отношение линейного порядка, называется '''линейно упорядоченным''', или ''цепью''».

== Примеры == * На множестве вещественных чисел отношения «больше» и «меньше» являются отношениями строгого порядка, а «больше или равно» и «меньше или равно» — нестрогого, причем линейного порядка, но не полного.* Отношение <math>R</math>«является делителем» на множестве натуральных чисел является отношением частичного порядка.* Отношение «меньше или равно» является отношением полного порядка на множестве натуральных чисел.* Отношение «лексикографически не меньше» на множестве всех возможных слов, составленных из букв русского алфавита, является отношением полного порядка.* Отношение «состоит в подчинении» на множестве работников компании является отношением нестрогого порядка. * Можно рассмотреть отношение «не младше» на множестве некоторой группы людей. Для соблюдения всех тонкостей скажем, что их даты рождения различны. Это отношение транзитивно (если ''человек A'' не младше ''человека B'', удовлетворяющее только условиям рефлексивности и транзитивностиа ''человек B'' не младше ''человека C'', называется то ''человек A''не младше 'квазипорядком'человека C''), или антисимметрично (если ''человек A'' не младше ''человека B'' и ''человек B'' не младше ''предпорядкомчеловека A'', то это один и тот же человек) и рефлексивно (каждый человек не младше самого себя). Из этого следует, что данное отношение является отношением частичного линейного порядка. * Отношение «является делителем» на множестве целых чисел не является отношением частичного порядка. Это легко видеть на следующем примере: <tex> 2 </tex> делится на <tex> -2 </tex>, а <tex> -2 </tex> делится на <tex> 2 </tex>. Однако <tex> 2 \neq -2</tex>.* Отношение «больше или равно по модулю» на множестве комплексных чисел не является отношением порядка. Из равенства модулей не следует равенство самих чисел, тем самым нарушается антисимметричность. Это демонстрирует данный пример: модули комплексных чисел <tex> 3 + 4i </tex> и <tex> 4 + 3i </tex> равны, но сами числа разные. ==См. также==* [[Бинарное_отношение|Бинарное отношение]]* [[Композиция_отношений|Композиция отношений]]* [[Отношение_эквивалентности|Отношение эквивалентности]]

== Примеры Источники информации ==* На множестве вещественных чисел отношения «больше» и «меньше» являются отношениями строгого порядкаНовиков Ф. А. {{---}} Дискретная математика для программистов: Учебник для вузов. 3-е изд. {{---}} СПБ.: Питер, а «больше или равно» и «меньше или равно» — нестрогого2009 {{---}} 50 с.* [https://en.wikipedia.org/wiki/Total_order Wikipedia {{---}} Total order]* [https://ru.wikipedia.org/wiki/%D0%9E%D1%82%D0%BD%D0%BE%D1%88%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BA%D0%B0 Википедия {{---}} Отношение Делимость|делимости на множестве целых чисел являются отношением нестрогого порядка]* [http://ru.math.wikia.com/wiki/%D0%9E%D1%82%D0%BD%D0%BE%D1%88%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BA%D0%B0 Wikia {{---}} Отношение порядка] [[Категория: Дискретная математика и алгоритмы]][[Категория: Отношения]]