WikiDer > Предварительный заказ
Бинарные отношения | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
А "✓"указывает, что свойство столбца требуется в определении строки. Например, определение отношения эквивалентности требует, чтобы оно было симметричным. Все определения молчаливо требуют транзитивность и рефлексивность. |
В математика, особенно в теория порядка, а Предварительный заказ или же квазипорядок это бинарное отношение то есть рефлексивный и переходный. Предварительные заказы более общие, чем отношения эквивалентности и (нестрогие) частичные заказы, оба из которых являются частными случаями предварительного заказа. 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. Между предпорядками и парами существует соответствие один к одному (разбиение, частичный порядок).
Для предварительного заказа «≲» отношение «<» можно определить как а < б если и только если (а ≲ б и нет б ≲ а), или, что то же самое, используя введенное выше отношение эквивалентности, (а ≲ б и нет а ~ б). Это строгий частичный порядок; любой строгий частичный порядок может быть результатом такой конструкции. Если предварительный порядок антисимметричен, следовательно, частичный порядок «≤», эквивалентность равна равенству, поэтому отношение «<» также можно определить как а < б если и только если (а ≤ б и а ≠ б).
(Мы делаем нет определить отношение "<" как а < б если и только если (а ≲ б и а ≠ б). Это вызвало бы проблемы, если бы предварительный заказ не был антисимметричным, поскольку результирующее отношение «<» не было бы транзитивным (подумайте, как связаны эквивалентные неравные элементы).
Наоборот, мы имеем а ≲ б если и только если а < б или же а ~ б. Это причина использования обозначения «≲»; "≤" может сбивать с толку, если предварительный заказ не является антисимметричным, и может указывать на то, что а ≤ б подразумевает, что а < б или же а = б.
Обратите внимание, что с этой конструкцией несколько предварительных порядков «» могут дать одно и то же отношение «<», поэтому без дополнительной информации, такой как отношение эквивалентности, «≲» не может быть восстановлено из «<». Возможные предзаказы включают следующее:
- Определять а ≤ б в качестве а < б или же а = б (т.е. возьмем рефлексивное замыкание отношения). Это дает частичный порядок, связанный со строгим частичным порядком «<» через рефлексивное замыкание; в этом случае эквивалентность равна равенству, поэтому обозначения ≲ и ~ нам не нужны.
- Определять а ≲ б как "не б < а"(т.е. возьмем обратное дополнение отношения), что соответствует определению а ~ б как "ни а < б ни б < а"; эти отношения ≲ и ~ в общем случае не транзитивны; однако, если они таковы, ~ является эквивалентностью; в этом случае" <"является строгий слабый порядок. Результирующий предзаказ общий, это общий предварительный заказ.
Учитывая бинарное отношение , дополненная композиция формирует предварительный заказ, называемый левый остаток,[4] куда обозначает обратное отношение из , и обозначает дополнять отношение , пока обозначает состав отношений.
Количество предзаказов
Элементы | Любой | Переходный | Рефлексивный | Предварительный заказ | Частичный заказ | Всего предзаказ | Общий заказ | Отношение эквивалентности |
---|---|---|---|---|---|---|---|---|
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 | 2п2−п | ∑п k=0 k! S(п, k) | п! | ∑п 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 предзаказов
- за п = 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 предзаказов
Интервал
За а ≲ б, то интервал [а, б] это набор точек Икс удовлетворение а ≲ Икс и Икс ≲ б, также написано а ≲ Икс ≲ б. Он содержит как минимум точки а и б. Можно расширить определение на все пары (а, б). Все дополнительные интервалы пусты.
Используя соответствующее строгое отношение «<», можно также определить интервал (а, б) как набор точек Икс удовлетворение а < Икс и Икс < б, также написано а < Икс < б. Открытый интервал может быть пустым, даже если а < б.
Также [а, б) и (а, б] можно определить аналогично.
Смотрите также
- Частичный заказ - предзаказ, то есть антисимметричный
- Отношение эквивалентности - предзаказ, то есть симметричный
- Всего предзаказ - предзаказ, то есть общий
- Общий заказ - предзаказ антисимметричный и тотальный
- Режиссерский набор
- Категория предзаказанных наборов
- Предварительный заказ
- Хорошо-квазиупорядоченный
Примечания
- ^ Для "proset" см., Например, Эклунд, Патрик; Гелер, Вернер (1990), "Обобщенные пространства Коши", Mathematische Nachrichten, 147: 219–233, Дои:10.1002 / мана.19901470123, МИСТЕР 1127325.
- ^ Пирс, Бенджамин С. (2002). Типы и языки программирования. Кембридж, Массачусетс / Лондон, Англия: MIT Press. стр. 182ff. ISBN 0-262-16209-1.
- ^ Кунен, Кеннет (1980), Теория множеств, введение в доказательства независимости, Исследования по логике и основам математики, 102, Амстердам, Нидерланды: Elsevier.
- ^ В контексте, ""не означает" установить разницу ".
Рекомендации
- Шмидт, Гюнтер, "Реляционная математика", Энциклопедия математики и ее приложений, вып. 132, Cambridge University Press, 2011 г., ISBN 978-0-521-76268-7
- Шредер, Бернд С. В. (2002), Упорядоченные наборы: введение, Бостон: Биркхойзер, ISBN 0-8176-4128-9