Предварительный заказ
В математике , особенно в теории порядка , предпорядок или квазипорядок — это бинарное отношение , которое является рефлексивным и транзитивным . Название preorder предполагает, что предварительные порядки — это почти частичные порядки , но не совсем, поскольку они не обязательно антисимметричны .
Естественным примером предзаказа является отношение деления «x делит y» между целыми числами, многочленами или элементами коммутативного кольца . Например, отношение деления является рефлексивным, поскольку каждое целое число делит само себя. Но отношение деления не является антисимметричным, потому что делит и делит . Именно к этому предпорядку относятся «наибольший» и «наименьший» во фразах « наибольший общий делитель » и « наименьшее общее кратное » (за исключением того, что для целых чисел наибольший общий делитель также является наибольшим для естественного порядка целых чисел). ).
Предпорядки тесно связаны с отношениями эквивалентности и (нестрогими) частичными порядками. Оба они являются частными случаями предпорядка: антисимметричный предпорядок — это частичный порядок, а симметричный предпорядок — это отношение эквивалентности. Тем более предзаказ на набор можно эквивалентно определить как отношение эквивалентности на , вместе с частичным порядком на множестве класса эквивалентности. Подобно частичным порядкам и отношениям эквивалентности, предварительные порядки (на непустом множестве) никогда не являются асимметричными .
Предварительный порядок можно визуализировать как ориентированный граф , элементы которого соответствуют вершинам, а отношение порядка между парами элементов соответствует направленным ребрам между вершинами. Обратное неверно: большинство ориентированных графов не являются ни рефлексивными, ни транзитивными. Антисимметричный предварительный порядок больше не имеет циклов; это частичный порядок и соответствует ориентированному ациклическому графу . Симметричный предварительный порядок является отношением эквивалентности; это можно рассматривать как потерю маркеров направления на краях графа. В общем, соответствующий ориентированный граф предзаказа может иметь множество несвязных компонентов.
В качестве бинарного отношения предварительный порядок можно обозначить или . На словах, когда можно сказать, что b покрывает a , или что a предшествует b , или что b сводится к a . Иногда также используются обозначения ← или →.
Определение
[ редактировать ]Позволять быть бинарным отношением на множестве так что по определению это какое-то подмножество и обозначения используется вместо Затем называется предпорядком или квазипорядком , если он рефлексивен и транзитивен ; то есть, если оно удовлетворяет:
- Рефлексивность : для всех и
- Транзитивность : если для всех
Набор, снабженный предзаказом, называется предупорядоченным набором (или просетом ). [1]
Предзаказы как частичные заказы по разделам
[ редактировать ]Учитывая предзаказ на можно определить отношение эквивалентности на такой, что Полученное соотношение является рефлексивным, поскольку предварительный заказ является рефлексивным; транзитивно, применяя транзитивность дважды; и симметричен по определению.
Используя это соотношение, можно построить частичный порядок на фактормножестве эквивалентности: который представляет собой множество всех эквивалентности классов Если предзаказ обозначается затем это набор - циклов классы эквивалентности : тогда и только тогда, когда или находится в -цикл с . В любом случае на можно определить тогда и только тогда, когда То, что это четко определено, означает, что его определяющее условие не зависит от того, какие представители и выбираются, следует из определения Легко проверить, что это дает частично упорядоченное множество.
И наоборот, из любого частичного порядка на разбиении множества можно оформить предзаказ на сам. Между предзаказами и парами существует взаимно однозначное соответствие (раздел, частичный порядок).
Пример : Пусть быть формальной теорией , представляющей собой набор предложений с определёнными свойствами (подробности о которых можно прочитать в статье по теме ). Например, может быть теорией первого порядка (например, теорией множеств Цермело–Френкеля ) или более простой теорией нулевого порядка . Одно из многих свойств заключается в том, что оно замкнуто по логическим следствиям, так что, например, если предложение логически подразумевает какое-то предложение который будет записан как а также как тогда обязательно (по модусу поненсу ). Отношение это предзаказ на потому что всегда держится и когда угодно и оба держатся, то и то же самое Более того, для любого тогда и только тогда, когда ; то есть два предложения эквивалентны по отношению к тогда и только тогда, когда они логически эквивалентны . Это частное отношение эквивалентности обычно обозначается своим специальным символом и вот этот символ может использоваться вместо Класс эквивалентности предложения обозначается состоит из всех предложений которые логически эквивалентны (то есть все такой, что ). Частичный заказ на вызванный который также будет обозначаться тем же символом характеризуется тогда и только тогда, когда где условие правой части не зависит от выбора представителей и классов эквивалентности. Все, что было сказано о до сих пор можно сказать и об обратном отношении Предзаказной набор является направленным множеством, потому что если и если обозначает предложение, образованное логическим союзом затем и где Частично упорядоченное множество следовательно, также является направленным множеством. см. в алгебре Линденбаума – Тарского Соответствующий пример .
Отношение к строгим частичным заказам
[ редактировать ]Если рефлексивность заменить на иррефлексивность (с сохранением транзитивности), то мы получим определение строгого частичного порядка на . По этой причине термин строгий предварительный заказ иногда используется для обозначения строгого частичного порядка. То есть это бинарное отношение на что удовлетворяет:
- Иррефлексивность или антирефлексивность: нет для всех то есть, ложно всех для и
- Транзитивность : если для всех
Строгий частичный порядок, индуцированный предварительным порядком
[ редактировать ]Любой предзаказ приводит к строгому частичному порядку, определяемому тогда и только тогда, когда и не .Используя отношение эквивалентности представленное выше, тогда и только тогда, когда и поэтому справедливо следующее Отношение является строгим частичным порядком , и каждый строгий частичный порядок может быть построен таким образом. Если предзаказ антисимметричен (и , следовательно, является частичным порядком), то эквивалентность равенство (т. е. тогда и только тогда, когда ) и поэтому в этом случае определение можно переформулировать как: Но важно то, что это новое условие не используется в качестве общего определения отношения (и не эквивалентно ему). (то есть, не определяется как : тогда и только тогда, когда ) потому что если предзаказ не антисимметричен, то полученное соотношение не было бы транзитивным (подумайте, как соотносятся эквивалентные неравные элементы). Это причина использования символа « " вместо символа "меньше или равно" ", что может вызвать путаницу в отношении предзаказа, который не является антисимметричным, поскольку может ввести в заблуждение предположение, что подразумевает
Предварительные заказы, вызванные строгим частичным порядком
[ редактировать ]Используя приведенную выше конструкцию, несколько нестрогих предварительных заказов могут создать один и тот же строгий предварительный заказ. поэтому без дополнительной информации о том, как было построено (такое знание отношения эквивалентности например), может быть невозможно восстановить исходный нестрогий предварительный порядок из Возможные (нестрогие) предварительные заказы, которые вызывают данный строгий предварительный порядок включают следующее:
- Определять как (то есть возьмем рефлексивное замыкание отношения). Это дает частичный порядок, связанный со строгим частичным порядком. «посредством рефлексивного замыкания; в этом случае эквивалентностью является равенство поэтому символы и не нужны.
- Определять как " " (то есть взять обратное дополнение отношения), что соответствует определению как «ни "; эти отношения и вообще не транзитивны; однако, если они есть, то является эквивалентностью; в таком случае" « — строгий слабый порядок . Получающийся предзаказ является связным (ранее назывался тотальным), то есть тотальным предзаказом .
Если затем Верно обратное (т. е. ) тогда и только тогда, когда затем или
Примеры
[ редактировать ]Теория графов
[ редактировать ]- Отношение достижимости в любом ориентированном графе (возможно, содержащем циклы) порождает предварительный порядок, где существует путь от x до y в предпорядке тогда и только тогда, когда в ориентированном графе . И наоборот, каждый предварительный порядок — это отношение достижимости ориентированного графа (например, графа, который имеет ребро от x до y для каждой пары ( x , y ) с ). Однако многие разные графы могут иметь одинаковый предварительный порядок достижимости. Точно так же достижимость ориентированных ациклических графов , ориентированных графов без циклов, приводит к появлению частично упорядоченных множеств (предпорядков, удовлетворяющих дополнительному свойству антисимметрии).
- Отношение граф -минор также является предварительным порядком.
Информатика
[ редактировать ]В информатике можно найти примеры следующих предзаказов.
- Асимптотический порядок вызывает предварительный порядок функций . Соответствующее отношение эквивалентности называется асимптотической эквивалентностью .
- Полиномиальное время , много-один (отображение) и сокращения Тьюринга являются предварительными порядками для классов сложности.
- Отношения подтипирования обычно представляют собой предварительные заказы. [2]
- Предзаказы моделирования — это предзаказы (отсюда и название).
- Отношения редукции в абстрактных системах переписывания .
- Предварительный порядок охвата на множестве терминов , определенный формулой если подтерм t является замены s экземпляром .
- Тета-подчинение , [3] то есть, когда литералы в дизъюнктивной формуле первого порядка содержатся в другой после применения замены к первой.
Теория категорий
[ редактировать ]- Категория , имеющая не более одного морфизма любого объекта x в любой другой объект y, является предпорядком. Такие категории называются тонкими . Здесь объекты соответствуют элементам и существует один морфизм для объектов, которые связаны, и ноль в противном случае. В этом смысле категории «обобщают» предварительные порядки, допуская более одного отношения между объектами: каждый морфизм представляет собой отдельное (именованное) отношение предпорядка.
- С другой стороны, предварительно упорядоченный набор можно понимать как обогащенную категорию , обогащенную по категории.
Другой
[ редактировать ]Дальнейшие примеры:
- Каждое конечное топологическое пространство порождает предварительный порядок в своих точках, определяя тогда и только тогда, когда принадлежит каждой окрестности y x . Таким образом , каждый конечный предпорядок может быть сформирован как предпорядок специализации топологического пространства. То есть существует взаимно однозначное соответствие между конечными топологиями и конечными предпорядками. Однако связь между бесконечными топологическими пространствами и предпорядками их специализации не является однозначной.
- Сеть — это направленный предварительный порядок, то есть каждая пара элементов имеет верхнюю границу . Определение сходимости через сети важно в топологии , где предварительные порядки не могут быть заменены частично упорядоченными множествами без потери важных функций.
- Отношение, определяемое если где f — функция некоторого предпорядка.
- Отношение, определяемое если существует некоторая инъекция из x в y . Инъекция может быть заменена сюръекцией или любым типом функции, сохраняющей структуру, такой как гомоморфизм колец или перестановка .
- Отношение вложения для счетных полных порядков .
Пример общего предзаказа :
- Предпочтение по распространённым моделям.
Конструкции
[ редактировать ]Каждое бинарное отношение на съемочной площадке можно продлить на предзаказ на взяв транзитивное замыкание и рефлексивное замыкание , Транзитивное замыкание указывает на соединение путей в тогда и только тогда, когда существует - путь из к
Левый остаточный предварительный порядок, индуцированный бинарным отношением
Учитывая бинарное отношение дополненная композиция образует предварительный порядок, называемый левым остатком , [4] где обозначает обратное отношение и обозначает дополнения отношение пока обозначает композицию отношения .
Связанные определения
[ редактировать ]Если предзаказ также антисимметричен , то есть и подразумевает тогда это частичный заказ .
С другой стороны, если оно симметрично , т. е. если подразумевает тогда это отношение эквивалентности .
Предзаказ является полным , если или для всех
— Предварительно заказанный класс это класс, оснащенный предзаказом. Каждый набор является классом, и поэтому каждый предварительно упорядоченный набор является предварительно упорядоченным классом.
Использование
[ редактировать ]Предварительные заказы играют решающую роль в нескольких ситуациях:
- Каждому предзаказу может быть присвоена топология — топология Александрова ; и действительно, каждый предварительный порядок на множестве находится во взаимно однозначном соответствии с топологией Александрова на этом множестве.
- Предварительные порядки могут использоваться для определения внутренних алгебр .
- Предварительные заказы обеспечивают семантику Крипке для определенных типов модальной логики .
- Предварительные порядки используются в для теории множеств доказательства непротиворечивости и независимости результатов. [5]
Количество предзаказов
[ редактировать ]Elements | Любой | Переходный | Рефлексивный | Симметричный | Предварительный заказ | Частичный заказ | Общий предзаказ | Общий заказ | Отношение эквивалентности |
---|---|---|---|---|---|---|---|---|---|
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 2 | 2 | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
2 | 16 | 13 | 4 | 8 | 4 | 3 | 3 | 2 | 2 |
3 | 512 | 171 | 64 | 64 | 29 | 19 | 13 | 6 | 5 |
4 | 65,536 | 3,994 | 4,096 | 1,024 | 355 | 219 | 75 | 24 | 15 |
н | 2 н 2 | 2 п ( п -1) | 2 п ( п +1)/2 | ∑ н к = 0 к ! С ( п , к ) | н ! | ∑ н k =0 S ( n , k ) | |||
ОЭИС | А002416 | А006905 | А053763 | А006125 | А000798 | А001035 | А000670 | А000142 | А000110 |
Обратите внимание, что S ( n , k ) относится к числам Стирлинга второго рода .
Как объяснялось выше, между предварительными заказами и парами существует соответствие 1 к 1 (раздел, частичный порядок). Таким образом, количество предварительных заказов представляет собой сумму количества частичных заказов в каждом разделе. Например:
- для
- 1 раздел из 3, даю 1 предзаказ
- 3 раздела 2+1 , давая предзаказы
- 1 раздел 1 + 1 + 1 , дающий 19 предзаказов
- для
- 1 раздел из 4, дающий 1 предзаказ
- 7 разделов с двумя классами (4 из 3+1 и 3 из 2+2 ), дающие предзаказы
- 6 разделов 2+1+1 , что дает предзаказы
- 1 раздел 1 + 1 + 1 + 1 , дающий 219 предзаказов
Интервал
[ редактировать ]Для интервал - это набор точек x, удовлетворяющих и также написано Он содержит как минимум точки a и b . Можно распространить определение на все пары. Все дополнительные интервалы пусты.
Используя соответствующее строгое соотношение " ", можно также определить интервал как набор точек x, удовлетворяющих и также написано Открытый интервал может быть пустым, даже если
Также и можно определить аналогично.
См. также
[ редактировать ]- Частичный порядок - антисимметричный предварительный порядок .
- Отношение эквивалентности - симметричный предварительный порядок
- Total preorder предзаказ – общий
- Тотальный порядок - антисимметричный и тотальный предварительный заказ.
- Режиссерский набор
- Категория предзаказанных наборов
- Предварительный заказ
- Ну-квази-упорядочение
Примечания
[ редактировать ]- ^ О «просете» см., например. Эклунд, Патрик; Гэлер, Вернер (1990), «Обобщенные пространства Коши», Mathematical News , 147 : 219–233, doi : 10.1002/mana.19901470123 , MR 1127325 .
- ^ Пирс, Бенджамин К. (2002). Типы и языки программирования . Кембридж, Массачусетс/Лондон, Англия: MIT Press. стр. 182 и далее. ISBN 0-262-16209-1 .
- ^ Робинсон, Дж. А. (1965). «Машинно-ориентированная логика, основанная на принципе разрешения» . АКМ . 12 (1): 23–41. дои : 10.1145/321250.321253 . S2CID 14389185 .
- ^ В этом контексте " " не означает "установленную разницу".
- ^ Кунен, Кеннет (1980), Теория множеств, Введение в доказательства независимости , Исследования по логике и основам математики, том. 102, Амстердам, Нидерланды: Elsevier .
Ссылки
[ редактировать ]- Шмидт, Гюнтер, «Реляционная математика», Энциклопедия математики и ее приложений, том. 132, Издательство Кембриджского университета, 2011 г., ISBN 978-0-521-76268-7
- Шредер, Бернд С.В. (2002), Упорядоченные множества: Введение , Бостон: Birkhäuser, ISBN 0-8176-4128-9