Предварительный заказ

Эта статья о бинарных отношениях. Порядок упорядочения вершин графа см. в разделе Поиск в глубину . Заказы на покупку невыпущенных продуктов см. в разделе «Предварительный заказ» . Чтобы узнать о других значениях, см. Предварительный заказ (значения) .

«Квазиордер» перенаправляется сюда. О нерефлексивных транзитивных отношениях см. строгий порядок .

showТранзитивные   бинарные отношения
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Total, Semiconnex Anti- reflexive Equivalence relation Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Preorder (Quasiorder) ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Partial order ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ Total preorder ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ Total order ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ Prewellordering ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ Well-quasi-ordering ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ Well-ordering ✗ Y Y Y ✗ ✗ Y ✗ ✗ Lattice ✗ Y ✗ ✗ Y Y Y ✗ ✗ Join-semilattice ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ Meet-semilattice ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ Strict partial order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict weak order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict total order ✗ Y Y ✗ ✗ ✗ ✗ Y Y Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Definitions, for all $a,b$ and $S\neq \varnothing :$ ${\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}$ ${\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}$ ${\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}$ ${\begin{aligned}\min S\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}$ $aRa$ ${\text{not }}aRa$ ${\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}$
Y indicates that the column's property is always true the row's term (at the very left), while ✗ indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated by Y in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively. All definitions tacitly require the homogeneous relation $R$ be transitive: for all $a,b,c,$ if $aRb$ and $bRc$ then $aRc.$ A term's definition may require additional properties that are not listed in this table.

Диаграмма Хассе предпорядка x R y, определяемого как x // 4≤ y // 4 для натуральных чисел . Классы эквивалентности (наборы элементов, такие что x R y и y R x ) показаны вместе как один узел. Отношение на классах эквивалентности является частичным порядком .

В математике , особенно в теории порядка , предпорядок или квазипорядок — это бинарное отношение , которое является рефлексивным и транзитивным . Название preorder предполагает, что предварительные порядки — это почти частичные порядки , но не совсем, поскольку они не обязательно антисимметричны .

Естественным примером предзаказа является отношение деления «x делит y» между целыми числами, полиномами или элементами коммутативного кольца . Например, отношение деления является рефлексивным, поскольку каждое целое число делит само себя. Но отношение деления не является антисимметричным, потому что $1$ делит $-1$ и $-1$ делит $1$. Именно к этому предпорядку относятся «наибольший» и «наименьший» во фразах « наибольший общий делитель » и « наименьшее общее кратное » (за исключением того, что для целых чисел наибольший общий делитель также является наибольшим для естественного порядка целых чисел). ).

Предпорядки тесно связаны с отношениями эквивалентности и (нестрогими) частичными порядками. Оба они являются частными случаями предпорядка: антисимметричный предпорядок — это частичный порядок, а симметричный предпорядок — это отношение эквивалентности. Тем более предзаказ на набор $X$ можно эквивалентно определить как отношение эквивалентности на $X$, вместе с частичным порядком на множестве класса эквивалентности. Подобно частичному порядку и отношениям эквивалентности, предварительные порядки (на непустом множестве) никогда не являются асимметричными .

Предварительный порядок можно визуализировать как ориентированный граф , элементы которого соответствуют вершинам, а отношение порядка между парами элементов соответствует направленным ребрам между вершинами. Обратное неверно: большинство ориентированных графов не являются ни рефлексивными, ни транзитивными. Антисимметричный предварительный порядок больше не имеет циклов; это частичный порядок и соответствует ориентированному ациклическому графу . Симметричный предварительный порядок является отношением эквивалентности; это можно рассматривать как потерю маркеров направления на краях графа. В общем, соответствующий ориентированный граф предзаказа может иметь множество несвязных компонентов.

В качестве бинарного отношения предварительный порядок можно обозначить $\,\lesssim \,$ или $\,\leq \,$. На словах, когда $a\lesssim b,$ можно сказать, что b покрывает a , или что a предшествует b , или что b сводится к a . Иногда также используются обозначения ← или →.

Определение

Позволять $\,\lesssim \,$ быть бинарным отношением на множестве $P,$ так что по определению $\,\lesssim \,$ это какое-то подмножество $P\times P$ и обозначения $a\lesssim b$ используется вместо $(a,b)\in \,\lesssim .$ Затем $\,\lesssim \,$ называется предпорядком или квазипорядком , если он рефлексивен и транзитивен ; то есть, если оно удовлетворяет:

1. Рефлексивность : $a\lesssim a$ для всех $a\in P,$ и
2. Транзитивность : если $a\lesssim b{\text{ and }}b\lesssim c{\text{ then }}a\lesssim c$ для всех $a,b,c\in P.$

Набор, снабженный предзаказом, называется предупорядоченным набором (или просетом ).

Предварительные заказы как частичные заказы на разделы

Учитывая предзаказ $\,\lesssim \,$ на $S$ можно определить отношение эквивалентности $\,\sim \,$ на $S$ такой, что

$$a\sim b\quad {\text{ if and only if }}\quad a\lesssim b\;{\text{ and }}\;b\lesssim a.$$

Полученное соотношение $\,\sim \,$ является рефлексивным, поскольку предварительный заказ $\,\lesssim \,$ является рефлексивным; транзитивно, применяя транзитивность $\,\lesssim \,$ дважды; и симметричен по определению.

Используя это соотношение, можно построить частичный порядок на фактормножестве эквивалентности: $S/\sim ,$ который представляет собой множество всех эквивалентности классов $\,\sim .$ Если предзаказ обозначается $R^{+=},$ затем $S/\sim$ это набор $R$- циклов классы эквивалентности : $x\in [y]$ тогда и только тогда, когда $x=y$ или $x$ находится в $R$-цикл с $y$ В любом случае на $S/\sim$ можно определить $[x]\leq [y]$ тогда и только тогда, когда $x\lesssim y.$ То, что это четко определено, означает, что его определяющее условие не зависит от того, какие представители $[x]$ и $[y]$ выбираются, следует из определения $\,\sim .\,$ Легко проверить, что это дает частично упорядоченное множество.

И наоборот, из любого частичного порядка на разбиении множества $S,$ можно оформить предзаказ на $S$ сам. Между предзаказами и парами существует взаимно однозначное соответствие (раздел, частичный порядок).

Пример : Пусть $S$ быть формальной теорией , представляющей собой набор предложений с определёнными свойствами (подробности о которых можно прочитать в статье по теме ). Например, $S$ может быть теорией первого порядка (например, теорией множеств Цермело–Френкеля ) или более простой теорией нулевого порядка . Одно из многих свойств $S$ заключается в том, что оно замкнуто по логическим следствиям, так что, например, если предложение $A\in S$ логически подразумевает какое-то предложение $B,$ который будет записан как $A\Rightarrow B$ а также как $B\Leftarrow A,$ тогда обязательно $B\in S$ (по модусу поненсу ). Отношение $\,\Leftarrow \,$ это предзаказ на $S$ потому что $A\Leftarrow A$ всегда держится и когда угодно $A\Leftarrow B$ и $B\Leftarrow C$ оба держатся, то и то же самое $A\Leftarrow C.$ Более того, для любого $A,B\in S,$ $A\sim B$ тогда и только тогда, когда $A\Leftarrow B{\text{ and }}B\Leftarrow A$; то есть два предложения эквивалентны по отношению к $\,\Leftarrow \,$ тогда и только тогда, когда они логически эквивалентны . Это частное отношение эквивалентности $A\sim B$ обычно обозначается своим специальным символом $A\iff B,$ и вот этот символ $\,\iff \,$ может использоваться вместо $\,\sim .$ Класс эквивалентности предложения $A,$ обозначается $[A],$ состоит из всех предложений $B\in S$ которые логически эквивалентны $A$ (то есть все $B\in S$ такой, что $A\iff B$). Частичный заказ на $S/\sim$ вызванный $\,\Leftarrow ,\,$ который также будет обозначаться тем же символом $\,\Leftarrow ,\,$ характеризуется $[A]\Leftarrow [B]$ тогда и только тогда, когда $A\Leftarrow B,$ где условие правой части не зависит от выбора представителей $A\in [A]$ и $B\in [B]$ классов эквивалентности. Все, что было сказано о $\,\Leftarrow \,$ до сих пор можно сказать и об обратном отношении $\,\Rightarrow .\,$ Предзаказной набор $(S,\Leftarrow )$ является направленным множеством, потому что если $A,B\in S$ и если $C:=A\wedge B$ обозначает предложение, образованное логическим союзом $\,\wedge ,\,$ затем $A\Leftarrow C$ и $B\Leftarrow C$ где $C\in S.$ Частично упорядоченное множество $\left(S/\sim ,\Leftarrow \right)$ следовательно, также является направленным множеством. см. в алгебре Линденбаума – Тарского Соответствующий пример .

Отношение к

Если рефлексивность заменить на иррефлексивность (с сохранением транзитивности), то мы получим определение строгого частичного порядка на $P$. По этой причине термин строгий предварительный заказ иногда используется для обозначения строгого частичного порядка. То есть это бинарное отношение $\,<\,$ на $P$ что удовлетворяет:

1. Иррефлексивность или антирефлексивность: нет $a<a$ для всех $a\in P;$ то есть, $\,a<a$ ложно всех для $a\in P,$ и
2. Транзитивность : если $a<b{\text{ and }}b<c{\text{ then }}a<c$ для всех $a,b,c\in P.$

вызванный

Любой предзаказ $\,\lesssim \,$ приводит к строгому частичному порядку, определяемому $a<b$ тогда и только тогда, когда $a\lesssim b$ и не $b\lesssim a$.Используя отношение эквивалентности $\,\sim \,$ представленное выше, $a<b$ тогда и только тогда, когда $a\lesssim b{\text{ and not }}a\sim b;$ и поэтому справедливо следующее

$$a\lesssim b\quad {\text{ if and only if }}\quad a<b\;{\text{ or }}\;a\sim b.$$

Отношение $\,<\,$ является строгим частичным порядком , и каждый строгий частичный порядок может быть построен таким образом. Если предзаказ $\,\lesssim \,$ антисимметричен (и , следовательно, является частичным порядком), то эквивалентность $\,\sim \,$ равенство (т. е. $a\sim b$ тогда и только тогда, когда $a=b$) и поэтому в данном случае определение $\,<\,$ можно переформулировать как:

$$a<b\quad {\text{ if and only if }}\quad a\lesssim b\;{\text{ and }}\;a\neq b\quad \quad ({\text{assuming }}\lesssim {\text{ is antisymmetric}}).$$

Но важно то, что это новое условие не используется в качестве общего определения отношения (и не эквивалентно ему). $\,<\,$ (то есть, $\,<\,$ не определяется как : $a<b$ тогда и только тогда, когда $a\lesssim b{\text{ and }}a\neq b$) потому что если предзаказ $\,\lesssim \,$ не антисимметричен, то полученное соотношение $\,<\,$ не было бы транзитивным (подумайте, как соотносятся эквивалентные неравные элементы). Это причина использования символа « $\lesssim$" вместо символа "меньше или равно" $\leq$", что может вызвать путаницу в отношении предзаказа, который не является антисимметричным, поскольку может ввести в заблуждение предположение, что $a\leq b$ подразумевает $a<b{\text{ or }}a=b.$

вызванные строгим частичным

Используя приведенную выше конструкцию, несколько нестрогих предварительных заказов могут создать один и тот же строгий предварительный заказ. $\,<,\,$ поэтому без дополнительной информации о том, как $\,<\,$ было построено (такое знание отношения эквивалентности $\,\sim \,$ например), может быть невозможно восстановить исходный нестрогий предварительный порядок из $\,<.\,$ Возможные (нестрогие) предварительные заказы, которые вызывают данный строгий предварительный порядок $\,<\,$ включают следующее:

• Определять $a\leq b$ как $a<b{\text{ or }}a=b$ (то есть возьмем рефлексивное замыкание отношения). Это дает частичный порядок, связанный со строгим частичным порядком " $<$«посредством рефлексивного замыкания; в этом случае эквивалентностью является равенство $\,=,$ поэтому символы $\,\lesssim \,$ и $\,\sim \,$ не нужны.
• Определять $a\lesssim b$ как " ${\text{ not }}b<a$" (то есть взять обратное дополнение отношения), что соответствует определению $a\sim b$ как «ни $a<b{\text{ nor }}b<a$"; эти отношения $\,\lesssim \,$ и $\,\sim \,$ вообще не транзитивны; однако, если они есть, то $\,\sim \,$ является эквивалентностью; в таком случае" $<$« — строгий слабый порядок . Полученный предзаказ является связным (ранее назывался тотальным), то есть тотальным предзаказом .

Если $a\leq b$ затем $a\lesssim b.$ Верно обратное (т. е. $\,\lesssim \;\;=\;\;\leq \,$) тогда и только тогда, когда $a\neq b$ затем $a<b$ или $b<a.$

Примеры

Теория графов

• Отношение достижимости в любом ориентированном графе (возможно, содержащем циклы) порождает предварительный порядок, где $x\lesssim y$ существует путь от x до y в предпорядке тогда и только тогда, когда в ориентированном графе . И наоборот, каждый предварительный порядок — это отношение достижимости ориентированного графа (например, графа, который имеет ребро от x до y для каждой пары ( x , y ) с $x\lesssim y$). Однако многие разные графы могут иметь один и тот же предварительный порядок достижимости, что и друг друга. Точно так же достижимость ориентированных ациклических графов , ориентированных графов без циклов, приводит к появлению частично упорядоченных множеств (предпорядков, удовлетворяющих дополнительному свойству антисимметрии).
• Отношение граф -минор также является предварительным порядком.

Информатика

В информатике можно найти примеры следующих предзаказов.

• Асимптотический порядок вызывает предварительный порядок функций $f:\mathbb {N} \to \mathbb {N}$. Соответствующее отношение эквивалентности называется асимптотической эквивалентностью .
• Полиномиальное время , много-один (отображение) и сокращения Тьюринга являются предварительными порядками для классов сложности.
• Отношения подтипирования обычно представляют собой предварительные заказы.
• Предзаказы моделирования — это предзаказы (отсюда и название).
• Отношения редукции в абстрактных системах переписывания .
• Предварительный порядок охвата на множестве терминов , определенный формулой $s\lesssim t$ если подтерм t ​ является замены s экземпляром .
• Тета-подчинение , то есть, когда литералы в дизъюнктивной формуле первого порядка содержатся в другой после применения замены к первой.

Теория категорий

• Категория , имеющая не более одного морфизма любого объекта x в любой другой объект y, является предпорядком. Такие категории называются тонкими . Здесь объекты соответствуют элементам $P,$ и существует один морфизм для объектов, которые связаны, и ноль в противном случае. В этом смысле категории «обобщают» предварительные порядки, допуская более одного отношения между объектами: каждый морфизм представляет собой отдельное (именованное) отношение предпорядка.
• С другой стороны, предварительно упорядоченный набор можно понимать как обогащенную категорию , обогащенную по категории. $2=(0\to 1).$

Другое

Дальнейшие примеры:

• Каждое конечное топологическое пространство порождает предварительный порядок в своих точках, определяя $x\lesssim y$ тогда и только тогда, когда принадлежит каждой окрестности y x . Таким образом , каждый конечный предпорядок может быть сформирован как предпорядок специализации топологического пространства. То есть существует взаимно однозначное соответствие между конечными топологиями и конечными предпорядками. Однако связь между бесконечными топологическими пространствами и предпорядками их специализации не является однозначной.

• Сеть — это направленный предварительный порядок, то есть каждая пара элементов имеет верхнюю границу . Определение сходимости через сети важно в топологии , где предварительные порядки не могут быть заменены частично упорядоченными множествами без потери важных функций.

• Отношение, определяемое $x\lesssim y$ если $f(x)\lesssim f(y),$ где f — функция некоторого предпорядка.
• Отношение, определяемое $x\lesssim y$ если существует некоторая инъекция из x в y . Инъекция может быть заменена сюръекцией или любым типом функции, сохраняющей структуру, такой как гомоморфизм колец или перестановка .
• Отношение вложения для счетных полных порядков .

Пример общего предзаказа :

• Предпочтение по распространённым моделям.

Конструкции

Каждое бинарное отношение $R$ на съемочной площадке $S$ можно продлить на предзаказ на $S$ взяв транзитивное замыкание и рефлексивное замыкание , $R^{+=}.$ Транзитивное замыкание указывает на соединение путей в $R:xR^{+}y$ тогда и только тогда, когда существует $R$- путь из $x$ к $y.$

Левый остаточный предварительный порядок, индуцированный бинарным отношением

Учитывая бинарное отношение $R,$ дополненная композиция $R\backslash R={\overline {R^{\textsf {T}}\circ {\overline {R}}}}$ образует предварительный порядок, называемый левым остатком , где $R^{\textsf {T}}$ обозначает обратное отношение $R,$ и ${\overline {R}}$ обозначает дополнения отношение $R,$ пока $\circ$ обозначает композицию отношения .

Связанные определения

Если предзаказ также антисимметричен , то есть $a\lesssim b$ и $b\lesssim a$ подразумевает $a=b,$ тогда это частичный заказ .

С другой стороны, если оно симметрично , т. е. если $a\lesssim b$ подразумевает $b\lesssim a,$ тогда это отношение эквивалентности .

Предзаказ является полным , если $a\lesssim b$ или $b\lesssim a$ для всех $a,b\in P.$

— Предварительно заказанный класс это класс, оснащенный предзаказом. Каждый набор является классом, и поэтому каждый предварительно упорядоченный набор является предварительно упорядоченным классом.

Использует

Предварительные заказы играют решающую роль в нескольких ситуациях:

• Каждому предзаказу может быть присвоена топология — топология Александрова ; и действительно, каждый предварительный порядок на множестве находится во взаимно однозначном соответствии с топологией Александрова на этом множестве.
• Предварительные порядки могут использоваться для определения внутренних алгебр .
• Предварительные заказы обеспечивают семантику Крипке для определенных типов модальной логики .
• Предварительные порядки используются в для теории множеств доказательства непротиворечивости и независимости результатов.

Количество предзаказов

Количество n -элементных бинарных отношений разных типов

Elem­ents	Любой	Переходный	Рефлексивный	Симметричный	Предварительный заказ	Частичный заказ	Общий предзаказ	Общий заказ	Отношение эквивалентности
0	1	1	1	1	1	1	1	1	1
1	2	2	1	2	1	1	1	1	1
2	16	13	4	8	4	3	3	2	2
3	512	171	64	64	29	19	13	6	5
4	65,536	3,994	4,096	1,024	355	219	75	24	15
н	2 н 2		2 п ( п -1)	2 п ( п +1)/2			∑ н к = 0 к ! С ( п , к )	н !	∑ н k =0 S ( n , k )
ОЭИС	А002416	А006905	А053763	А006125	А000798	А001035	А000670	А000142	А000110

Обратите внимание, что S ( n , k ) относится к числам Стирлинга второго рода .

Как объяснялось выше, между предварительными заказами и парами существует соответствие 1 к 1 (раздел, частичный порядок). Таким образом, количество предварительных заказов представляет собой сумму количества частичных заказов в каждом разделе. Например:

• для $n=3:$
  • 1 раздел из 3, даю 1 предзаказ
  • 3 раздела 2+1 , давая $3\times 3=9$ предзаказы
  • 1 раздел 1 + 1 + 1 , дающий 19 предзаказов
  Т.е. всего 29 предзаказов.
• для $n=4:$
  • 1 раздел из 4, дающий 1 предзаказ
  • 7 разделов с двумя классами (4 из 3+1 и 3 из 2+2 ), дающие $7\times 3=21$ предзаказы
  • 6 разделов 2+1+1 , что дает $6\times 19=114$ предзаказы
  • 1 раздел 1 + 1 + 1 + 1 , дающий 219 предзаказов
  Т.е. всего 355 предзаказов.

Интервал

Для $a\lesssim b,$ интервал ​ $[a,b]$ - это набор точек x, удовлетворяющих $a\lesssim x$ и $x\lesssim b,$ также написано $a\lesssim x\lesssim b.$ Он содержит как минимум точки a и b . Можно распространить определение на все пары. $(a,b)$ Все дополнительные интервалы пусты.

Используя соответствующее строгое соотношение " $<$", можно также определить интервал $(a,b)$ как набор точек x, удовлетворяющих $a<x$ и $x<b,$ также написано $a<x<b.$ Открытый интервал может быть пустым, даже если $a<b.$

Также $[a,b)$ и $(a,b]$ можно определить аналогично.

См. также

• Частичный порядок - антисимметричный предварительный порядок .
• Отношение эквивалентности - симметричный предварительный порядок
• Total preorder предзаказ – общий
• Тотальный порядок - антисимметричный и тотальный предварительный заказ.
• Режиссерский набор
• Категория предзаказанных наборов
• Предварительный заказ
• Ну-квази-упорядочение

Ссылки

• Шмидт, Гюнтер, «Реляционная математика», Энциклопедия математики и ее приложений, том. 132, Издательство Кембриджского университета, 2011 г., ISBN   978-0-521-76268-7
• Шредер, Бернд С.В. (2002), Упорядоченные множества: Введение , Бостон: Birkhäuser, ISBN  0-8176-4128-9