Jump to content

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

(Перенаправлено с Квазиордера )
Транзитивные   бинарные отношения
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric
Total, Semiconnex Anti-
reflexive
Equivalence relation Green tickY Green tickY
Preorder (Quasiorder) Green tickY
Partial order Green tickY Green tickY
Total preorder Green tickY Green tickY
Total order Green tickY Green tickY Green tickY
Prewellordering Green tickY Green tickY Green tickY
Well-quasi-ordering Green tickY Green tickY
Well-ordering Green tickY Green tickY Green tickY Green tickY
Lattice Green tickY Green tickY Green tickY Green tickY
Join-semilattice Green tickY Green tickY Green tickY
Meet-semilattice Green tickY Green tickY Green tickY
Strict partial order Green tickY Green tickY Green tickY
Strict weak order Green tickY Green tickY Green tickY
Strict total order Green tickY Green tickY Green tickY Green tickY
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric
Definitions, for all and
Green tickY indicates that the column's property is always true the row's term (at the very left), while indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated by Green tickY in the "Symmetric" column and in the "Antisymmetric" column, respectively.

All definitions tacitly require the homogeneous relation be transitive: for all if and then
A term's definition may require additional properties that are not listed in this table.

Диаграмма Хассе предпорядка x R y, определяемого как x // 4≤ y // 4 для натуральных чисел . Классы эквивалентности (наборы элементов, такие что x R y и y R x ) показаны вместе как один узел. Отношение на классах эквивалентности является частичным порядком .

В математике , особенно в теории порядка , предпорядок или квазипорядок — это бинарное отношение , которое является рефлексивным и транзитивным . Название preorder предполагает, что предварительные порядки — это почти частичные порядки , но не совсем, поскольку они не обязательно антисимметричны .

Естественным примером предзаказа является отношение деления «x делит y» между целыми числами, многочленами или элементами коммутативного кольца . Например, отношение деления является рефлексивным, поскольку каждое целое число делит само себя. Но отношение деления не является антисимметричным, потому что делит и делит . Именно к этому предпорядку относятся «наибольший» и «наименьший» во фразах « наибольший общий делитель » и « наименьшее общее кратное » (за исключением того, что для целых чисел наибольший общий делитель также является наибольшим для естественного порядка целых чисел). ).

Предпорядки тесно связаны с отношениями эквивалентности и (нестрогими) частичными порядками. Оба они являются частными случаями предпорядка: антисимметричный предпорядок — это частичный порядок, а симметричный предпорядок — это отношение эквивалентности. Тем более предзаказ на набор можно эквивалентно определить как отношение эквивалентности на , вместе с частичным порядком на множестве класса эквивалентности. Подобно частичным порядкам и отношениям эквивалентности, предварительные порядки (на непустом множестве) никогда не являются асимметричными .

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

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

Определение

[ редактировать ]

Позволять быть бинарным отношением на множестве так что по определению это какое-то подмножество и обозначения используется вместо Затем называется предпорядком или квазипорядком , если он рефлексивен и транзитивен ; то есть, если оно удовлетворяет:

  1. Рефлексивность : для всех и
  2. Транзитивность : если для всех

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

Предзаказы как частичные заказы по разделам

[ редактировать ]

Учитывая предзаказ на можно определить отношение эквивалентности на такой, что Полученное соотношение является рефлексивным, поскольку предварительный заказ является рефлексивным; транзитивно, применяя транзитивность дважды; и симметричен по определению.

Используя это соотношение, можно построить частичный порядок на фактормножестве эквивалентности: который представляет собой множество всех эквивалентности классов Если предзаказ обозначается затем это набор - циклов классы эквивалентности : тогда и только тогда, когда или находится в -цикл с . В любом случае на можно определить тогда и только тогда, когда То, что это четко определено, означает, что его определяющее условие не зависит от того, какие представители и выбираются, следует из определения Легко проверить, что это дает частично упорядоченное множество.

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

Пример : Пусть быть формальной теорией , представляющей собой набор предложений с определёнными свойствами (подробности о которых можно прочитать в статье по теме ). Например, может быть теорией первого порядка (например, теорией множеств Цермело–Френкеля ) или более простой теорией нулевого порядка . Одно из многих свойств заключается в том, что оно замкнуто по логическим следствиям, так что, например, если предложение логически подразумевает какое-то предложение который будет записан как а также как тогда обязательно (по модусу поненсу ). Отношение это предзаказ на потому что всегда держится и когда угодно и оба держатся, то и то же самое Более того, для любого тогда и только тогда, когда ; то есть два предложения эквивалентны по отношению к тогда и только тогда, когда они логически эквивалентны . Это частное отношение эквивалентности обычно обозначается своим специальным символом и вот этот символ может использоваться вместо Класс эквивалентности предложения обозначается состоит из всех предложений которые логически эквивалентны (то есть все такой, что ). Частичный заказ на вызванный который также будет обозначаться тем же символом характеризуется тогда и только тогда, когда где условие правой части не зависит от выбора представителей и классов эквивалентности. Все, что было сказано о до сих пор можно сказать и об обратном отношении Предзаказной набор является направленным множеством, потому что если и если обозначает предложение, образованное логическим союзом затем и где Частично упорядоченное множество следовательно, также является направленным множеством. см. в алгебре Линденбаума – Тарского Соответствующий пример .

Отношение к строгим частичным заказам

[ редактировать ]

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

  1. Иррефлексивность или антирефлексивность: нет для всех то есть, ложно всех для и
  2. Транзитивность : если для всех

Строгий частичный порядок, индуцированный предварительным порядком

[ редактировать ]

Любой предзаказ приводит к строгому частичному порядку, определяемому тогда и только тогда, когда и не .Используя отношение эквивалентности представленное выше, тогда и только тогда, когда и поэтому справедливо следующее Отношение является строгим частичным порядком , и каждый строгий частичный порядок может быть построен таким образом. Если предзаказ антисимметричен (и , следовательно, является частичным порядком), то эквивалентность равенство (т. е. тогда и только тогда, когда ) и поэтому в этом случае определение можно переформулировать как: Но важно то, что это новое условие не используется в качестве общего определения отношения (и не эквивалентно ему). (то есть, не определяется как : тогда и только тогда, когда ) потому что если предзаказ не антисимметричен, то полученное соотношение не было бы транзитивным (подумайте, как соотносятся эквивалентные неравные элементы). Это причина использования символа « " вместо символа "меньше или равно" ", что может вызвать путаницу в отношении предзаказа, который не является антисимметричным, поскольку может ввести в заблуждение предположение, что подразумевает

Предварительные заказы, вызванные строгим частичным порядком

[ редактировать ]

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

  • Определять как (то есть возьмем рефлексивное замыкание отношения). Это дает частичный порядок, связанный со строгим частичным порядком. «посредством рефлексивного замыкания; в этом случае эквивалентностью является равенство поэтому символы и не нужны.
  • Определять как " " (то есть взять обратное дополнение отношения), что соответствует определению как «ни "; эти отношения и вообще не транзитивны; однако, если они есть, то является эквивалентностью; в таком случае" « — строгий слабый порядок . Получающийся предзаказ является связным (ранее назывался тотальным), то есть тотальным предзаказом .

Если затем Верно обратное (т. е. ) тогда и только тогда, когда затем или

Теория графов

[ редактировать ]
  • Отношение достижимости в любом ориентированном графе (возможно, содержащем циклы) порождает предварительный порядок, где существует путь от x до y в предпорядке тогда и только тогда, когда в ориентированном графе . И наоборот, каждый предварительный порядок — это отношение достижимости ориентированного графа (например, графа, который имеет ребро от x до y для каждой пары ( x , y ) с ). Однако многие разные графы могут иметь одинаковый предварительный порядок достижимости. Точно так же достижимость ориентированных ациклических графов , ориентированных графов без циклов, приводит к появлению частично упорядоченных множеств (предпорядков, удовлетворяющих дополнительному свойству антисимметрии).
  • Отношение граф -минор также является предварительным порядком.

Информатика

[ редактировать ]

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

Теория категорий

[ редактировать ]
  • Категория , имеющая не более одного морфизма любого объекта x в любой другой объект y, является предпорядком. Такие категории называются тонкими . Здесь объекты соответствуют элементам и существует один морфизм для объектов, которые связаны, и ноль в противном случае. В этом смысле категории «обобщают» предварительные порядки, допуская более одного отношения между объектами: каждый морфизм представляет собой отдельное (именованное) отношение предпорядка.
  • С другой стороны, предварительно упорядоченный набор можно понимать как обогащенную категорию , обогащенную по категории.

Дальнейшие примеры:

Пример общего предзаказа :

Конструкции

[ редактировать ]

Каждое бинарное отношение на съемочной площадке можно продлить на предзаказ на взяв транзитивное замыкание и рефлексивное замыкание , Транзитивное замыкание указывает на соединение путей в тогда и только тогда, когда существует - путь из к

Левый остаточный предварительный порядок, индуцированный бинарным отношением

Учитывая бинарное отношение дополненная композиция образует предварительный порядок, называемый левым остатком , [4] где обозначает обратное отношение и обозначает дополнения отношение пока обозначает композицию отношения .

[ редактировать ]

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

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

Предзаказ является полным , если или для всех

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

Использование

[ редактировать ]

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

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

[ редактировать ]
Количество n -элементных бинарных отношений разных типов
Elem­ents Любой Переходный Рефлексивный Симметричный Предварительный заказ Частичный заказ Общий предзаказ Общий заказ Отношение эквивалентности
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 предзаказов
    Т.е. всего 29 предзаказов.
  • для
    • 1 раздел из 4, дающий 1 предзаказ
    • 7 разделов с двумя классами (4 из 3+1 и 3 из 2+2 ), дающие предзаказы
    • 6 разделов 2+1+1 , что дает предзаказы
    • 1 раздел 1 + 1 + 1 + 1 , дающий 219 предзаказов
    Т.е. всего 355 предзаказов.

Интервал

[ редактировать ]

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

Используя соответствующее строгое соотношение " ", можно также определить интервал как набор точек x, удовлетворяющих и также написано Открытый интервал может быть пустым, даже если

Также и можно определить аналогично.

См. также

[ редактировать ]

Примечания

[ редактировать ]
  1. ^ О «просете» см., например. Эклунд, Патрик; Гэлер, Вернер (1990), «Обобщенные пространства Коши», Mathematical News , 147 : 219–233, doi : 10.1002/mana.19901470123 , MR   1127325 .
  2. ^ Пирс, Бенджамин К. (2002). Типы и языки программирования . Кембридж, Массачусетс/Лондон, Англия: MIT Press. стр. 182 и далее. ISBN  0-262-16209-1 .
  3. ^ Робинсон, Дж. А. (1965). «Машинно-ориентированная логика, основанная на принципе разрешения» . АКМ . 12 (1): 23–41. дои : 10.1145/321250.321253 . S2CID   14389185 .
  4. ^ В этом контексте " " не означает "установленную разницу".
  5. ^ Кунен, Кеннет (1980), Теория множеств, Введение в доказательства независимости , Исследования по логике и основам математики, том. 102, Амстердам, Нидерланды: Elsevier .
  • Шмидт, Гюнтер, «Реляционная математика», Энциклопедия математики и ее приложений, том. 132, Издательство Кембриджского университета, 2011 г., ISBN   978-0-521-76268-7
  • Шредер, Бернд С.В. (2002), Упорядоченные множества: Введение , Бостон: Birkhäuser, ISBN  0-8176-4128-9
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 523a14f4ed93eeab7deacfa3ed03e04a__1721559000
URL1:https://arc.ask3.ru/arc/aa/52/4a/523a14f4ed93eeab7deacfa3ed03e04a.html
Заголовок, (Title) документа по адресу, URL1:
Preorder - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)