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

Бинарные отношения

	Симметричный	Антисимметричный	Connex	Обоснованный	Присоединяется	Встречается
Отношение эквивалентности	✓	✗	✗	✗	✗	✗
Предварительный заказ (Квазипорядок)	✗	✗	✗	✗	✗	✗
Частичный заказ	✗	✓	✗	✗	✗	✗
Всего предзаказ	✗	✗	✓	✗	✗	✗
Общий заказ	✗	✓	✓	✗	✗	✗
Предварительный заказ	✗	✗	✓	✓	✗	✗
Хорошо-квазиупорядоченный	✗	✗	✗	✓	✗	✗
Хороший порядок	✗	✓	✓	✓	✗	✗
Решетка	✗	✓	✗	✗	✓	✓
Соединение-полурешетка	✗	✓	✗	✗	✓	✗
Встреча-полурешетка	✗	✓	✗	✗	✗	✓

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

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

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

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

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

Формальное определение

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

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

если а ≤ б и б ≤ c тогда а ≤ c (транзитивность)

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

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

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

Предварительный заказ общий если а ≤ б или же б ≤ а для всех а, б.

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

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

Примеры

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

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

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

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

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

Использует

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

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

Конструкции

Каждое бинарное отношение R на множестве S может быть расширено до предпорядка на S, взяв переходное закрытие и рефлексивное закрытие, Р⁺⁼. Транзитивное замыкание указывает на соединение пути в Р: Икс р⁺ у тогда и только тогда, когда существует R-дорожка из Икс к y.

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

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

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

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

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

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

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

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

Учитывая бинарное отношение ${displaystyle R}$ , дополненная композиция ${displaystyle R ackslash R = {overline {R ^ {extsf {T}} circ {overline {R}}}}}$ формирует предварительный заказ, называемый левый остаток,^[4] куда ${displaystyle R ^ {extsf {T}}}$ обозначает обратное отношение из ${displaystyle R}$ , и ${displaystyle {overline {R}}}$ обозначает дополнять отношение ${displaystyle R}$ , пока ${displaystyle circ}$ обозначает состав отношений.

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

Количество п-элементные бинарные отношения разных типов
Элементы	Любой	Переходный	Рефлексивный	Предварительный заказ	Частичный заказ	Всего предзаказ	Общий заказ	Отношение эквивалентности
0	1	1	1	1	1	1	1	1
1	2	2	1	1	1	1	1	1
2	16	13	4	4	3	3	2	2
3	512	171	64	29	19	13	6	5
4	65,536	3,994	4,096	355	219	75	24	15
п	2^п²		2^п²−п			$\sum п k =0 k! S (п, k)$	п!	$\sum п k =0 S (п, k)$
OEIS	A002416	A006905	A053763	A000798	A001035	A000670	A000142	A000110

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

за п = 3:
- 1 раздел из 3, дающий 1 предварительный заказ
- 3 раздела 2 + 1, давая 3 × 3 = 9 предварительные заказы
- 1 раздел 1 + 1 + 1, дав 19 предзаказов
То есть вместе 29 предзаказов.
за п = 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 предзаказов.

Интервал

За а ≲ б, то интервал [а, б] это набор точек Икс удовлетворение а ≲ Икс и Икс ≲ б, также написано а ≲ Икс ≲ б. Он содержит как минимум точки а и б. Можно расширить определение на все пары (а, б). Все дополнительные интервалы пусты.

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

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

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

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

Примечания

^ Для "proset" см., Например, Эклунд, Патрик; Гелер, Вернер (1990), "Обобщенные пространства Коши", Mathematische Nachrichten, 147: 219–233, Дои:10.1002 / мана.19901470123, МИСТЕР 1127325.
^ Пирс, Бенджамин С. (2002). Типы и языки программирования. Кембридж, Массачусетс / Лондон, Англия: MIT Press. стр. 182ff. ISBN 0-262-16209-1.
^ Кунен, Кеннет (1980), Теория множеств, введение в доказательства независимости, Исследования по логике и основам математики, 102, Амстердам, Нидерланды: Elsevier.
^ В контексте, " ${displaystyle ackslash}$ "не означает" установить разницу ".