Предзаказ

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

Название preorder происходит от идеи, что предварительные заказы (которые не являются частичными заказами) являются «почти» (частичными) заказами, но не совсем; они не обязательно антисимметричны или асимметричны . Поскольку предварительный порядок является бинарным отношением, символ ≤ может использоваться в качестве устройства записи для отношения. Однако, поскольку они не обязательно антисимметричны, некоторые из обычных интуитивных представлений, связанных с символом ≤, могут не применяться. С другой стороны, предварительный заказ может использоваться простым способом для определения частичного порядка и отношения эквивалентности. Однако это не всегда полезно или целесообразно, в зависимости от изучаемой проблемной области.

На словах, когда a ≤ b , можно сказать, что b покрывает a, или что a предшествует b , или что b сводится к a . Иногда вместо ≤ используется обозначение ← или ≲.

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

Формальное определение [ править ]

Рассмотрим однородное отношение на некотором заданном множестве, так что по определению, является некоторым подмножеством, а обозначение используется вместо Then , называется предпорядком или квазипорядком, если оно рефлексивно и транзитивно ; то есть, если он удовлетворяет:${\ Displaystyle \, \ Leq \,}$ ${\ displaystyle P,}$${\ Displaystyle \, \ Leq \,}$${\ displaystyle P \ times P}$${\ displaystyle a \ leq b}$${\ Displaystyle (а, Ь) \ в \, \ leq.}$${\ Displaystyle \, \ Leq \,}$

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

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

Если рефлексивность заменить на иррефлексивность (с сохранением транзитивности), то результат называется строгим предпорядком; явно, строгий предварительный заказon - транзитивное однородное отношение на, которое также удовлетворяет следующему условию:${\displaystyle P}$${\displaystyle \,<\,}$${\displaystyle P}$

3. Иррефлексивность или антирефлексивность: неверно для всех${\displaystyle a<a}$${\displaystyle a\in P.}$

Каждый строгий частичный заказ является (по определению) строгим предварительным заказом ; и наоборот, поскольку каждое транзитивное иррефлексивное отношение обязательно асимметрично , каждый строгий предпорядок также является строгим частичным порядком. Следовательно, бинарное отношение является строгим предварительным порядком тогда и только тогда, когда оно является строгим частичным порядком. Хотя они эквивалентны, термин «строгий частичный порядок» обычно предпочтительнее, чем «строгий предварительный порядок», и читателям рекомендуется ознакомиться со статьей о строгих частичных порядках для получения подробной информации о таких отношениях. В отличие от строгих предварительных заказов, существует множество (нестрогих) предварительных заказов, которые не являются (нестрогими) частичными заказами .

Связанные определения [ править ]

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

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

Как объясняют Факкини и Финоккиаро (2020) , эти два особых случая предварительных порядков (частично упорядоченные множества и множества, снабженные отношением эквивалентности) являются строительными блоками теории претензий в категории предварительно упорядоченных множеств.

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

Понятие предварительно упорядоченного множества может быть сформулировано в категориальной структуре как тонкая категория ; то есть как категория с не более чем одним морфизмом от объекта к другому. Здесь объекты соответствуют элементам, и существует один морфизм для связанных объектов, в противном случае - ноль. С другой стороны, предварительно упорядоченный набор можно понимать как обогащенную категорию , обогащенную над категорией 2 = (0 → 1) .${\displaystyle P}$${\displaystyle P,}$

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

Примеры [ править ]

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

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

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

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

• Отношение, определяемое формулой x ≤ y, если f ( x ) ≤ f ( y ) , где f - функция в некотором предпорядке.
• Отношение, определяемое как x ≤ y, если существует некоторая инъекция из x в y . Инъекция может быть заменена сюръекцией или функцией сохранения структуры любого типа, такой как гомоморфизм колец или перестановка .
• Отношение вложения для счетных полных порядков .
• Отношение граф-минор в теории графов .
• Категории с более чем одним морфизма из любого объекта х до любого другого объекта у является предзаказ. Такие категории называются тонкими . В этом смысле категории «обобщают» предварительные порядки, разрешая более одного отношения между объектами: каждый морфизм является отдельным (именованным) отношением предварительного порядка.

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

• Редукции много-один и Тьюринга являются предварительными заказами для классов сложности.
• Отношения подтипов обычно являются предварительными заказами. ^[2]
• Предварительные заказы на моделирование - это предварительные заказы (отсюда и название).
• Редукционные отношения в абстрактных системах перезаписи .
• Оцепления предпорядок на множестве терминов , определяемый с ≤ т , если подтермами из т является замена экземпляром из с .

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

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

Использует [ редактировать ]

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

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

Конструкции [ править ]

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

Для предпорядка ≲ на S можно определить отношение эквивалентности ~ на S такое, что a ~ b тогда и только тогда, когда a ≲ b и b ≲ a . (Полученное отношение рефлексивно, поскольку предпорядок рефлексивен, транзитивен при применении транзитивности предпорядка дважды и симметричен по определению.)

Используя это отношение, можно построить частичный порядок на фактормножестве эквивалентности S / ~ , множестве всех классов эквивалентности ~. Обратите внимание, что если предпорядок равен R ^{+ =} , S / ~ - это множество классов эквивалентности R- цикла : x ∈ [ y ] тогда и только тогда, когда x = y или x находится в R-цикле с y . В любом случае на S / ~ можно определить [ x ] ≤ [ y ] тогда и только тогда, когда x ≲у . По построению ~, это определение не зависит от выбранных представителей, и соответствующее отношение действительно корректно определено. Легко проверить, что это дает частично упорядоченное множество.

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

Для предварительного заказа «≲», отношение «<» может быть определен как в < Ь тогда и только тогда , когда ( ≲ б , а не б ≲ а ), или , что эквивалентно, используя отношение эквивалентности введенной выше, ( а ≲ б и не а ~ б ). Это строгий частичный заказ ; любой строгий частичный порядок может быть результатом такой конструкции. Если предварительный порядок антисимметричен, следовательно, частичный порядок «≤», эквивалентность равна равенству, поэтому отношение «<» также может быть определено как a <b тогда и только тогда, когда ( a ≤ b иа ≠ б ).

Отношение «<» не определяется как: a < b тогда и только тогда, когда ( a ≲ b и a ≠ b ). Это вызвало бы проблемы, если бы предварительный заказ не был антисимметричным, поскольку результирующее отношение «<» не было бы транзитивным (подумайте, как соотносятся эквивалентные неравные элементы).

Наоборот, a ≲ b тогда и только тогда, когда a < b или a ~ b . Это причина использования обозначения «≲»; «≤» может сбивать с толку неантисимметричный предварительный заказ, он может указывать на то, что a ≤ b подразумевает, что a < b или a = b .

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

• Определим a ≤ b как a < b или a = b (т. Е. Возьмем рефлексивное замыкание отношения). Это дает частичный порядок, связанный со строгим частичным порядком «<» через рефлексивное замыкание; в этом случае эквивалентность равна равенству, поэтому обозначения ≲ и ~ нам не нужны.
• Определите a ≲ b как «not b < a » (т. Е. Возьмите обратное дополнение отношения), что соответствует определению a ~ b как «ни a < b, ни b < a »; эти отношения ≲ и ~, вообще говоря, не транзитивны; однако, если это так, ~ является эквивалентом; в этом случае «<» - строгий слабый порядок . Результирующий предварительный заказ является полным , то есть полным предварительным заказом .

Учитывая бинарное отношение , дополненная композиция образует предпорядок называется левым остаточным , ^[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 }$

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

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

Интервал [ править ]

Для получения более ≲ б , то интервал [ , Ь ] есть множество точек х , удовлетворяющих с ≲ х и х ≲ б , также записывается в ≲ х ≲ б . Он содержит как минимум точки a и b . Можно расширить определение на все пары ( a , b ) . Все дополнительные интервалы пусты.

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

Кроме [ , б ) и ( , Ь ] могут быть определены аналогичным образом .

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]

• Факкини, Альберто; Финоккиаро, Кармело Антонио (2020), «Теории претензий, стабильная категория и предварительно упорядоченные множества», Annali di Matematica Pura ed Applicata. Серии IV , 199 (3): 1073-1089, DOI : 10.1007 / s10231-019-00912-2 , МР  4102802

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