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

Рефлексивное и транзитивное бинарное отношение

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

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

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

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

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

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

Определение

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

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

Набор, снабженный предварительным порядком, называется предварительным порядком (или просетом ). ^[1]

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

Учитывая предпорядок на , можно определить отношение эквивалентности на таким образом, что Результирующее отношение рефлексивно, поскольку предпорядок рефлексивен; транзитивно, поскольку применяется транзитивность дважды; и симметрично по определению. ${\displaystyle \,\lesssim \,}$ ${\displaystyle S}$ ${\displaystyle \,\sim \,}$ ${\displaystyle S}$ $${\displaystyle a\sim b\quad {\text{ if and only if }}\quad a\lesssim b\;{\text{ and }}\;b\lesssim a.}$$ ${\displaystyle \,\sim \,}$ ${\displaystyle \,\lesssim \,}$ ${\displaystyle \,\lesssim \,}$

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

Наоборот, из любого частичного порядка на разбиении множества можно построить предпорядок на нем самом. Существует взаимно-однозначное соответствие между предпорядками и парами (разбиение, частичный порядок). ${\displaystyle S,}$ ${\displaystyle S}$

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

Отношение к строгим частичным порядкам

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

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

Строгий частичный порядок, вызванный предварительным порядком

Любой предпорядок порождает строгий частичный порядок, определяемый как если и только если и не . Используя отношение эквивалентности, введенное выше, если и только если и поэтому выполняется следующее Отношение является строгим частичным порядком , и каждый строгий частичный порядок может быть построен таким образом. Если предпорядок антисимметричен (и , следовательно, частичный порядок), то эквивалентность является равенством (то есть, если и только если ) и поэтому в этом случае определение можно переформулировать как: Но важно, что это новое условие не используется как (и не эквивалентно) общему определению отношения (то есть, не определяется как: если и только если ), потому что если предпорядок не антисимметричен, то полученное отношение не будет транзитивным (рассмотрите, как соотносятся эквивалентные неравные элементы). Это причина использования символа " " вместо символа "меньше или равно" " ", что может вызвать путаницу для предпорядка, который не антисимметричен, поскольку это может ввести в заблуждение, что подразумевает ${\displaystyle \,\lesssim \,}$ ${\displaystyle a<b}$ ${\displaystyle a\lesssim b}$ ${\displaystyle b\lesssim a}$ ${\displaystyle \,\sim \,}$ ${\displaystyle a<b}$ ${\displaystyle a\lesssim b{\text{ and not }}a\sim b;}$ $${\displaystyle a\lesssim b\quad {\text{ if and only if }}\quad a<b\;{\text{ or }}\;a\sim b.}$$ ${\displaystyle \,<\,}$ ${\displaystyle \,\lesssim \,}$ ${\displaystyle \,\sim \,}$ ${\displaystyle a\sim b}$ ${\displaystyle a=b}$ ${\displaystyle \,<\,}$ $${\displaystyle 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}}).}$$ ${\displaystyle \,<\,}$ ${\displaystyle \,<\,}$ ${\displaystyle a<b}$ ${\displaystyle a\lesssim b{\text{ and }}a\neq b}$ ${\displaystyle \,\lesssim \,}$ ${\displaystyle \,<\,}$ ${\displaystyle \lesssim }$ ${\displaystyle \leq }$ ${\displaystyle a\leq b}$ ${\displaystyle a<b{\text{ or }}a=b.}$

Предварительные заказы, вызванные строгим частичным порядком

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

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

Если тогда Обратное утверждение верно (то есть, ) тогда и только тогда, когда всякий раз, когда то или ${\displaystyle a\leq b}$ ${\displaystyle a\lesssim b.}$ ${\displaystyle \,\lesssim \;\;=\;\;\leq \,}$ ${\displaystyle a\neq b}$ ${\displaystyle a<b}$ ${\displaystyle b<a.}$

Примеры

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

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

Информатика

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

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

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

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

Другой

Дополнительные примеры:

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

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

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

Пример общего предварительного заказа :

• Предпочтение , согласно общепринятым моделям.

Конструкции

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

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

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

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

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

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

Предварительный заказ является общим, если или для всех ${\displaystyle a\lesssim b}$ ${\displaystyle b\lesssim a}$ ${\displaystyle a,b\in P.}$

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

Использует

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

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

Количество предварительных заказов

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

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

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

Интервал

Для интервала есть множество точек x, удовлетворяющих и также записанных Он содержит по крайней мере точки a и b . Можно расширить определение на все пары Все дополнительные интервалы пусты. ${\displaystyle a\lesssim b,}$ ${\displaystyle [a,b]}$ ${\displaystyle a\lesssim x}$ ${\displaystyle x\lesssim b,}$ ${\displaystyle a\lesssim x\lesssim b.}$ ${\displaystyle (a,b)}$

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

Аналогично можно определить и . ${\displaystyle [a,b)}$ ${\displaystyle (a,b]}$

Смотрите также

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

Примечания

1. О «просете» см., например, Эклунд, Патрик; Гэлер, Вернер (1990), «Обобщенные пространства Коши», Mathematische Nachrichten , 147 : 219–233, doi : 10.1002/mana.19901470123, MR  1127325.
2. Пирс, Бенджамин С. (2002). Типы и языки программирования . Кембридж, Массачусетс/Лондон, Англия: The MIT Press. стр. 182 и далее. ISBN 0-262-16209-1.
3. Робинсон, JA (1965). «Машинно-ориентированная логика, основанная на принципе разрешения». ACM . 12 (1): 23–41. doi : 10.1145/321250.321253 . S2CID  14389185.
4. В этом контексте « » не означает «установить разницу». ${\displaystyle \backslash }$
5. Кунен, Кеннет (1980), Теория множеств, Введение в доказательства независимости , Исследования по логике и основания математики, т. 102, Амстердам, Нидерланды: Elsevier.

Ссылки

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