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

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

Диаграмма Хассе предпорядка 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 ). Отношение является предварительным порядком, потому что всегда выполняется и всякий раз, когда и оба выполняются, то также выполняется Кроме того, для любого тогда и только тогда, когда ; то есть два предложения эквивалентны тогда и только тогда, когда они логически эквивалентны . Это конкретное отношение эквивалентности обычно обозначается собственным специальным символом , поэтому этот символ можно использовать вместо. Класс эквивалентности предложения, обозначаемого как, состоит из всех предложений , которые логически эквивалентны (то есть все такие, что ). Частичный порядок на , который также будет обозначаться тем же символом, характеризуется тогда и только тогда, когда условие правой части не зависит от выбора представителей и классов эквивалентности. Все, что было сказано до сих пор, можно также сказать и о его обратном отношении. Предварительно упорядоченный набор является направленным набором, потому что if и if обозначает предложение, образованное логическим союзом, тогда и где Частично упорядоченный набор, следовательно, также является направленным набором. Соответствующий пример см. в алгебре Линденбаума – Тарского . ${\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.}$

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

Любой предварительный порядок приводит к строгому частичному порядку, определяемому тогда и только тогда, когда и not . Используя введенное выше отношение эквивалентности , тогда и только тогда, когда и поэтому выполняется следующее ${\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}$

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

• Отношение, определяемое формулой if , где 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]}$

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

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

Примечания

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

Рекомендации

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