Предварительный заказ
В математике , особенно в теории порядка , предпорядок или квазипорядок — это бинарное отношение , которое является рефлексивным и транзитивным . Название 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 | ∑ н k =0 k ! S ( n , k ) |
н ! | ∑ н k знак равно 0 S ( п , 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