Предзаказ

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

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

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

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

• 1 Формальное определение
• 2 Примеры
• 3 Использование
• 4 Конструкции
• 5 Количество предварительных заказов
• 6 Интервал
• 7 См. Также
• 8 Примечания
• 9 Ссылки

Рассмотрим некоторый набор P и бинарное отношение ≤ на P. Тогда ≤ является предварительным порядком, или квазипорядок, если он рефлексивный и транзитивный ; т.е. для всех a, b и c в P имеем:

a ≤ a (рефлексивность)

если a ≤ b и b ≤ c, то a ≤ c (транзитивность)

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

, если предварительный заказ также антисимметричный, то есть a ≤ b и b ≤ a подразумевает a = b, то это частичный порядок.

С другой стороны, если он симметричный, то есть, если a ≤ b влечет b ≤ a, то это отношение эквивалентности.

Предварительный порядок равен всего, если a ≤ b или b ≤ a для всех a, b.

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

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

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

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

• Многие единицы и редукции Тьюринга являются предварительными заказами для классов сложности.
• Отношения подтипов обычно являются предварительными заказами.
• Предварительные заказы моделирования являются предварительными заказами (отсюда и название).
• отношения сокращения в системах абстрактного перезаписывания.
• предварительный заказ охвата в наборе терминов, определенных s ≤ t, если подтерм из t является экземпляром подстановки из s.

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

• Предпочтение в соответствии с общими моделями.

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

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

Каждое бинарное отношение 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 ≲ y. По построению ~ это определение не зависит от выбранных представителей, и соответствующее отношение действительно определено правильно. Нетрудно проверить, что это дает частично упорядоченное множество.

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

Для предварительного заказа «», отношение «<" can be defined as a < b if and only if (a ≲ b and not b ≲ a), or equivalently, using the equivalence relation introduced above, (a ≲ b and not a ~ b). It is a строгий частичный порядок ; каждый строгий частичный порядок может быть результатом такой конструкции. Если предварительный порядок антисимметричен, следовательно, частичный порядок» ≤ ", эквивалентность равна равенству, поэтому отношение" <" can also be defined as a < b if and only if (a ≤ b and a ≠ b).

(Мы не определяем отношение "<" as a < b if and only if (a ≲ b and a ≠ b). Doing so would cause problems if the preorder was not antisymmetric, as the resulting relation "<" would not be transitive (think of how equivalent non-equal elements relate).)

И наоборот, мы имеем a ≲ b тогда и только тогда, когда a < b or a ~ b. This is the reason for using the notation "≲"; "≤" can be confusing for a preorder that is not antisymmetric, it may suggest that a ≤ b implies that a < b or a = b.

Примечание что с этой конструкцией несколько предварительных порядков "" могут дать одно и то же отношение "<", so without more information, such as the equivalence relation, "≲" cannot be reconstructed from "<". Possible preorders include the following:

• Определить a ≤ b как a < b or a = b (i.e., take the reflexive closure of the relation). This gives the partial order associated with the strict partial order "<" through reflexive closure; in this case the equivalence is equality, so we don't need the notations ≲ and ~.
• Определить a ≲ b как" not b < a" (i.e., take the inverse complement of the relation), which corresponds to defining a ~ b as "neither a < b nor b < a"; these relations ≲ and ~ are in general not transitive; however, if they are, ~ is an equivalence; in that case "<" is a строгий слабый порядок. Результирующий предварительный порядок равен total, то есть total preorder.

Учитывая бинарное отношение $R\; \{\backslash \; displaystyle\; R\}$, дополненная композиция $R\; \setminus \; R\; =\; RT\; \circ \; R\; ¯\; ¯\; \{\backslash \; displaystyle\; R\; \backslash \; backslash\; R\; =\; \{\backslash \; overline\; \{R\; ^\; \{\backslash textf\; \{T\}\}\; \backslash \; circ\; \{\backslash \; overline\; \{R\}\}\}\}\}$формирует предварительный заказ, называемый левый остаток, где $RT\; \{\backslash \; displaystyle\; R\; ^\; \{\backslash textf\; \{T\}\}\}$обозначает обратное отношение из $R\; \{\backslash \; displaystyle\; R\; \}$и $R\; ¯\; \{\backslash \; dis\; playstyle\; \{\backslash \; overline\; \{R\}\}\}$обозначает отношение дополнения к $R\; \{\backslash \; displaystyle\; R\}$, а $\circ \; \{\backslash \; displaystyle\; \backslash \; circ\}$обозначает состав отношения.

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

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

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

Использование соответствующего строгого отношения "<", one can also define the interval (a, b) as the set of points x satisfying a < x and x < b, also written a < x < b. An open interval may be empty even if a < b.

Аналогично могут быть определены [a, b) и (a, b].

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

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

• Шмидт, Гюнтер, "Реляционная математика", Энциклопедия математики и ее приложений, том. 132, Cambridge University Press, 2011, ISBN 978-0-521-76268-7
• Schröder, Bernd SW (2002), Ordered Sets: An Introduction, Boston: Birkhäuser, ISBN 0-8176-4128-9