Транзитивные бинарные отношения |
| Симметричный | Антисимметричный | Связаны | Обоснованный | Присоединяется | Встречается | Рефлексивный | Нерефлексивный | Асимметричный | Также известный как: | | | Итого, Semiconnex | | | | | Антирефлексивный | | Отношение эквивалентности | Y | ✗ | ✗ | ✗ | ✗ | ✗ | Y | ✗ | ✗ | Предзаказ (Квазипорядок) | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | Y | ✗ | ✗ | Частичный заказ | ✗ | Y | ✗ | ✗ | ✗ | ✗ | Y | ✗ | ✗ | Всего предзаказ | ✗ | ✗ | Y | ✗ | ✗ | ✗ | Y | ✗ | ✗ | Общий заказ | ✗ | Y | Y | ✗ | ✗ | ✗ | Y | ✗ | ✗ | Предварительный заказ | ✗ | ✗ | Y | Y | ✗ | ✗ | Y | ✗ | ✗ | Хорошо-квазиупорядоченный | ✗ | ✗ | ✗ | Y | ✗ | ✗ | Y | ✗ | ✗ | Хороший порядок | ✗ | Y | Y | Y | ✗ | ✗ | Y | ✗ | ✗ | Решетка | ✗ | Y | ✗ | ✗ | Y | Y | Y | ✗ | ✗ | Соединение-полурешетка | ✗ | Y | ✗ | ✗ | Y | ✗ | Y | ✗ | ✗ | Встреча-полурешетка | ✗ | Y | ✗ | ✗ | ✗ | Y | Y | ✗ | ✗ | | | | | | | | | | | | | | | | | | | | | Строгий частичный заказ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | Y | Y | Строгий слабый порядок | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | Y | Y | Строгий общий порядок | ✗ | ✗ | Y | ✗ | ✗ | ✗ | ✗ | Y | Y | | Симметричный | Антисимметричный | Связаны | Обоснованный | Присоединяется | Встречается | Рефлексивный | Нерефлексивный | Асимметричный | Определения: | | | | | | | | | | |
Все определения неявно требуют, чтобы однородное отношение было транзитивным : " " указывает, что свойство столбца требуется по определению термина строки (в самом левом углу). Например, определение отношения эквивалентности требует, чтобы оно было симметричным. Упомянутые здесь дополнительные свойства, что однородное отношение может удовлетворять. Y |
Рис.1
Диаграмма Хассе из
множества всех подмножеств из множества трехэлементного упорядочены по
включению. Множества, соединенные восходящим путем, например, и, сопоставимы, а например, и нет.
В математике, особенно в теории порядка, частично упорядоченное множество (также poset) формализует и обобщает интуитивную концепцию упорядочения, последовательности или расположения элементов набора. Poset состоит из набора вместе с бинарным отношением, указывающим, что для определенных пар элементов в наборе один из элементов предшествует другому в упорядочении. Само отношение называется «частичным порядком». Слово partial в именах «частичный порядок» и «частично упорядоченный набор» используется как указание на то, что не каждая пара элементов должна быть сопоставимой. То есть могут быть пары элементов, для которых ни один элемент не предшествует другому в poset. Таким образом, частичные заказы обобщают общие заказы, в которых каждая пара сопоставима.
СОДЕРЖАНИЕ
- 1 Неформальное определение
- 2 Отношение частичного порядка
- 2.1 Нестрогий частичный порядок
- 2.2 Строгий частичный порядок
- 2.3 Соответствие строгих и нестрогих отношений частичного порядка
- 2.4 Двойные заказы
- 3 Обозначения
- 4 Примеры
- 4.1 Заказы на декартово произведение частично упорядоченных множеств
- 4.2 Суммы частично упорядоченных множеств
- 5 Производные понятия
- 6 Отображения между частично упорядоченными множествами
- 7 Количество частичных заказов
- 8 Линейное удлинение
- 9 Направленные ациклические графы
- 10 В теории категорий
- 11 частичные порядки в топологических пространствах
- 12 интервалов
- 13 См. Также
- 14 Примечания
- 15 цитат
- 16 Ссылки
- 17 Внешние ссылки
Неформальное определение
Частичный порядок определяет понятие сравнения. Два элемента х и у могут стоять в любом из четырех взаимоисключающих отношений друг к другу: либо х lt; у или х = у, или х gt; у или х и у являются несравнима.
Набор с частичным порядком называется частично упорядоченным набором (также называемым poset). Иногда также используется термин упорядоченный набор, если из контекста ясно, что никакой другой вид порядка не подразумевается. В частности, полностью упорядоченные множества также могут называться «упорядоченные множества», особенно в областях, где эти структуры более распространены, чем посеты.
Позиционирование может быть визуализировано с помощью его диаграммы Хассе, которая отображает отношение упорядочения.
Отношение частичного порядка
Отношение частичного порядка - это однородное отношение, которое является транзитивным и антисимметричным. Есть два общих подопределения для отношения частичного порядка, для рефлексивного и иррефлексивного отношений частичного порядка, также называемых «нестрогим» и «строгим» соответственно. Эти два определения можно поставить во взаимно однозначное соответствие, так что для каждого строгого частичного порядка существует уникальный соответствующий нестрогий частичный порядок, и наоборот. Термин частичный порядок обычно относится к нестрогому отношению частичного порядка.
Нестрогий частичный заказ
Рефлексивный, слабый, или нестрогий частичный порядок - это однородное отношение ≤ над множеством, которое является рефлексивным, антисимметричным и транзитивным. То есть для всегоон должен удовлетворять:
- рефлексивность :, т.е. каждый элемент связан с самим собой.
- антисимметрия : если, т.е. никакие два различных элемента не предшествуют друг другу.
- транзитивность : если.
Нестрогий частичный порядок также известен как антисимметричный предпорядок.
Строгий частичный заказ
Иррефлексивное, сильный, илистрогий частичный порядок на- это однородное отношение lt;on,которое является иррефлексивным, транзитивным и асимметричным ; то есть удовлетворяет следующим условиям для всех
- Безрезультатность : нет, т.е. ни один элемент не связан с самим собой
- Транзитивность : если
- Асимметрия : если нет.
Безрефлексивность и транзитивность вместе подразумевают асимметрию. Также асимметрия подразумевает иррефлексивность. Другими словами, транзитивное отношение асимметрично тогда и только тогда, когда оно иррефлексивно. Таким образом, определение будет таким же, если оно не включает иррефлексивность или асимметрию (но не то и другое одновременно).
Строгий частичный заказ также известен как строгий предварительный заказ.
Соответствие строгих и нестрогих отношений частичного порядка
Рис.2
Коммутативная диаграмма о связи между рефлексивным замыканием ( cls), иррефлексивным ядром ( ker) и обратным отношением ( cnv) на примере отношения ( изображена
диаграмма Хассе ).
Строгие и нестрогие частичные заказы на множестве тесно связаны. Нестрогий частичный порядок может быть преобразован в строгий частичный порядок, удаляя все отношения формы, то есть строгий частичный порядок является множеством, где этим отношение идентичности на и обозначает набор вычитания. И наоборот, строгий частичный порядок lt;on может быть преобразован в нестрогий частичный порядок путем присоединения всех отношений этой формы; то есть является нестрогим частичным порядком. Таким образом, если - нестрогий частичный порядок, то соответствующий строгий частичный порядок lt;является иррефлексивным ядром, задаваемым формулой
И наоборот, если lt;- строгий частичный порядок, то соответствующий нестрогий частичный порядок является
рефлексивным замыканием, задаваемым формулой:
Двойные заказы
Основная статья:
Двойственность (теория порядка) Двойной (или напротив) из отношения частичного порядка определяется позволяя быть
обратное отношение из, то есть тогда и только тогда. Двойственный к нестрогому частичному порядку является нестрогим частичным порядком, а двойственный к строгому частичному порядку является строгим частичным порядком. Дуальным к двойственному отношению является исходное отношение.
Обозначение
Мы можем рассматривать как частично упорядоченное множество 3-кортежа, или даже 5-кортеж, где и являются нестрогие частичные отношения порядка, и строгие частичные отношения порядка, двойственным является и и также являются двойственными друг друга.
Любое из четырех отношений частичного порядка на данном наборе однозначно определяет остальные три. Следовательно, в качестве обозначения мы можем написать или и предположить, что другие отношения определены соответствующим образом. Чаще всего используется нестрогий частичный порядок. Некоторые авторы используют символы, отличные от таких, как или, чтобы отличать частичные заказы от общих заказов.
Когда речь идет о частичных порядков, не следует принимать в качестве
дополнения в. является обратным к иррефлексивному ядру, которое всегда является подмножеством дополнения, но равно дополнению
тогда и только тогда,
когда является полным порядком.
Примеры
Стандартные примеры позет, возникающих в математике, включают:
- В действительных числах, или вообще любой вполне упорядоченное множество, упорядочены по стандарту менее чем или равных отношению ≤, не является строгим частичным порядком.
- Для действительных чисел обычное отношение «
меньше, чем» lt;является строгим частичным порядком, и то же самое верно и для обычного отношения «
больше, чем» gt; на
По определению каждый строгий слабый порядок является строгим частичным порядком. Множество подмножеств данного набора (его набор мощности ), упорядоченное по включению (см. Рис.1). Точно так же набор последовательностей, упорядоченных по подпоследовательности, и набор строк, упорядоченных по подстроке. Множество натуральных чисел с отношением делимости. Множество вершин ориентированного ациклического графа, упорядоченное по достижимости. Множество подпространств одного векторного пространства упорядочены по включению. Для частично упорядоченного множества Р, то пространство последовательностей, содержащее все последовательности элементов из Р, где последовательность последовательности предшествуетЬ, если каждый элемент в течение предшествует соответствующий пункт в б. Формально тогда и только тогда, когда для всех ; то есть
покомпонентный порядок.
Для множества X и частично упорядоченного множества Р, тем функциональное пространство, содержащее все функции из X в Р, где Р ≤ г тогда и только тогда, когда F ( х) ≤ г ( х) для всех Забор, частично упорядоченное множество, определенное с помощью переменной последовательности порядковых отношений lt;Ь gt; с lt; д...
Множество событий в специальной теории относительности и, в большинстве случаев, общая теория относительности, где в течение двух событий X и Y, X ≤ Y тогда и только тогда, когда Y в будущем светового конуса в X. Событие Y может быть каузально зависит только от X, если X ≤ Y. Один знакомый пример частично упорядоченного множества - это собрание людей, упорядоченное по генеалогическому происхождению. Некоторые пары людей связаны отношениями потомков и предков, но другие пары людей несравнимы, и ни одна из них не является потомком другой.
Заказы на декартово произведение частично упорядоченных множеств
Рис.3 Лексикографический порядок на
Рис.4 Заказ продукции на
Рис.5 Рефлексивное закрытие строгого прямого заказа продукта на элементах, охватываемых (3,3) и покрывающих (3,3), выделены зеленым и красным соответственно.
В порядке увеличения силы, т. Е. Уменьшения наборов пар, три из возможных частичных порядков на декартовом произведении двух частично упорядоченных наборов равны (см. Рис. 3-5):
б) ≤ ( с, d), если lt; с или ( = с и б ≤ d);
заказ продукции : (,б) ≤ ( с, d), если ≤ C и B ≤ d ;
рефлексивное замыкание на прямом произведении соответствующих строгих порядков: (,б) ≤ ( с, d), если ( lt; с и б lt; д) или ( = с и Ь = д).
Все три аналогично можно определить для декартова произведения более двух наборов.
Применительно к упорядоченным векторным пространствам над одним и тем же полем результат в каждом случае также является упорядоченным векторным пространством.
См. Также заказы на декартово произведение полностью упорядоченных наборов.
Суммы частично упорядоченных наборов
Другой способ объединения двух (непересекающихся) множеств - это порядковая сумма (или линейная сумма) Z = X ⊕ Y, определенная на объединении базовых множеств X и Y в порядке a ≤ Z b тогда и только тогда, когда:
- a, b ∈ X с a ≤ X b, или
- a, b ∈ Y с a ≤ Y b, или
- ∈ X и B ∈ Y.
Если два посета хорошо упорядочены, то их порядковая сумма
тоже.
Последовательно-параллельные частичные порядки формируются из операции порядкового суммирования (в этом контексте называемой последовательной компоновкой) и другой операции, называемой параллельной композицией. Параллельная композиция - это несвязное объединение двух частично упорядоченных наборов без отношения порядка между элементами одного набора и элементами другого набора.
Производные понятия
В примерах используется ЧУМ, состоящий из
множества всех подмножеств трехэлементного множества, упорядоченных по включению множества (см. Рис. 1).
- имеет отношение к Ь когда это ≤
б. Это не означает, что b также связано с a, потому что отношение не обязательно должно быть
симметричным. Например, это связано с, но не наоборот.
и б являются сопоставимыми, если ≤б или б ≤. В остальном они несравнимы. Например, и сопоставимы, а пока и нет.
Общий порядок или линейный порядок частичный порядок, согласно которому каждая пара элементов сопоставима, т.е. трихотомии имеет место. Например, натуральные числа в стандартном порядке. Цепь представляет собой подмножество посета, который представляет собой упорядоченное множество. Например, это цепочка. Антицепь является подмножеством посета, в котором не существует двух различных элементов не сопоставимы. Например, набор синглтонов Элемент a называется строго меньшим, чем элемент b, если a ≤ b и, например, строго меньше, чем Элемент a называется покрытым другим элементом b, записываемым как a b (или a lt;: b), если a строго меньше, чем b, и между ними не помещается третий элемент c ; формально: если и a ≤ b, и истинны, иa ≤ c ≤ b ложно для каждого c с использованием строгого порядка lt;, отношение a ⋖ b может быть эквивалентно перефразировано как « a lt; b, но не a lt; c lt; b для любого c ". Например, покрывается, но не покрывается
Extrema
Рис.6 Рисунок выше с удаленными наибольшим и наименьшим элементами. В этом сокращенном ЧУМе верхний ряд элементов - это все максимальные элементы, а нижний ряд - все минимальные элементы, но нет ни наибольшего, ни наименьшего элемента.
В частности, есть несколько понятий «наибольший» и «наименьший» элементы:
наибольшим элементом, если для каждого элемента Элемент является наименьшим элементом, если для каждого элемента в poset может быть только один наибольший или наименьший элемент. В нашем текущем примере набор является самым большим элементом и наименьшим.
Максимальные элементы и минимальные элементы: элемент является максимальным элементом, если нет такого элемента, что. Аналогично, элемент является минимальным элементом, если нет такого элемента, что если элемент poset имеет наибольший элемент, он должен быть единственным максимальным элементом, но в противном случае может быть более одного максимального элемента, и аналогично для наименьших элементов и минимальных элементов. В нашем запущенном примере, и являются максимальным и минимальным элементами. После их удаления остается 3 максимальных элемента и 3 минимальных элемента (см. Рис. 6). Верхние и нижние границы : Для подмножества А из Р, элемент х в Р есть верхняя граница А, если ≤ х, для каждого элемента а в A. В частности, й не должен быть в A, чтобы быть верхней границей A. Аналогичным образом, элемент х в Р является нижней гранью А, если ≥ х, для каждого элемента а в A. Наибольший элемент из Р представляет собой верхнюю грань Р самого, и наименьший элемент является нижняя граница Р. В нашем примере набор - это верхняя граница для набора элементов
Рис.7 неотрицательные целые числа, упорядоченных по делимости
В качестве другого примера рассмотрим положительные целые числа, упорядоченные по делимости: 1 - наименьший элемент, так как он делит все остальные элементы; с другой стороны, у этого poset нет наибольшего элемента (хотя, если бы один включил 0 в poset, который кратен любому целому числу, это был бы наибольший элемент; см. Рис.7). В этом частично упорядоченном множестве нет даже максимальных элементов, так как любой g делит, например, 2 g, отличных от него, поэтому g не является максимальным. Если число 1 исключено, сохраняя при этом делимость упорядочением по элементам больше 1, то результирующий poset не имеет минимального элемента, но любое простое число является минимальным элементом для него. В этом наборе 60 - это верхняя граница (хотя и не наименьшая верхняя граница) подмножества, которое не имеет никакой нижней границы (поскольку 1 не входит в набор); с другой стороны, 2 - это нижняя граница подмножества степеней двойки, не имеющая никакой верхней границы.
Отображения между частично упорядоченными наборами
Рис.8 Сохраняющее порядок, но не отражающее порядок (поскольку f ( u) ≼ f ( v), но не u v) отображение.
Рис.9 Порядковый изоморфизм между делителями 120 (частично упорядоченными по делимости) и замкнутыми по делителям подмножествами {2, 3, 4, 5, 8 } (частично упорядоченными по включению множества)
Для двух частично упорядоченных множеств ( S, ≤) и ( T, ≼) функция называется
сохраняющей порядок, или
монотонной, или изотонной, если для всех следует, что f ( x) ≼ f ( y). Если ( U, ≲) также частично упорядоченное множество, и оба, и это с сохранением порядка их
композиция сохраняет порядок, тоже. Функция называется отражающей порядок, если для всех f ( x) ≼ f ( y) подразумевает, что If одновременно сохраняет порядок и отражает порядок, то она называется
упорядоченным вложением ( S, ≤) в ( T, ≼). В последнем случае, обязательно
инъективны, так как предполагает, и в свою очередь в соответствии с антисимметричности Если заказ-вложение между двумя ч.у.м. S и Т существует, то говорят, что S может быть встроен в T. Если заказ-вложение является
взаимно однозначным, оно называется
порядковым изоморфизмом, а частичные порядки ( S, ≤) и ( Т, ≼) называются изоморфными. Изоморфные порядки имеют структурно похожие
диаграммы Хассе (см. Рис.8). Можно показать, что если сохраняющие порядок отображения и существуют такие, что и дает
тождественную функцию на S и T соответственно, то S и T изоморфны по порядку.
Например, отображение набора натуральных чисел (упорядоченных по делимости) в
набор степеней натуральных чисел (упорядоченных по включению множества) может быть определено путем преобразования каждого числа в набор его
простых делителей. Он сохраняет порядок: если делит, то каждый простой делитель числа также является простым делителем числа. Однако он не является ни инъективным (поскольку он отображает как 12, так и 6), ни отражающим порядок (поскольку 12 не делит 6). Вместо этого взятие каждого числа в набор его
простых делителей
мощности определяет отображение, которое сохраняет порядок, отражает порядок и, следовательно, является вложением порядка. Это не изоморфизм порядка (так как он, например, не отображает какое-либо число в набор), но его можно сделать так,
ограничив его область значений до Фиг.9 показывает подмножество и его изоморфный образ в соответствии с построением такой изоморфизм порядка в набор степеней может быть обобщен на широкий класс частичных порядков, называемых
дистрибутивными решетками, см. «
Теорема Биркгофа о представлении ».
Количество частичных заказов
Последовательность A001035 в OEIS дает количество частичных порядков для набора из n помеченных элементов:
Количество строгих частичных заказов такое же, как и количество частичных заказов.
Если подсчет производится только до изоморфизма, получается последовательность 1, 1, 2, 5, 16, 63, 318,... (последовательность A000112 в OEIS ).
Линейное расширение
Частичный порядок на множестве является
продолжением другого частичного порядка на условии, что для всех элементов всякий раз, когда это также тот случай, когда
линейное расширение является расширением, что также является линейной (то есть, всего) порядка. Классический пример: лексикографический порядок полностью упорядоченных множеств является линейным продолжением порядка их продуктов. Каждый частичный заказ может быть расширен до полного заказа (
принцип расширения заказа ).
В информатике алгоритмы поиска линейных расширений частичных порядков (представленных как порядки достижимости ориентированных ациклических графов ) называются топологической сортировкой.
Направленные ациклические графы
Строгие частичные порядки напрямую соответствуют ориентированным ациклическим графам (DAG). Если граф построен, принимая каждый элемент как узел, а каждый элемент - как ребро, то каждый строгий частичный порядок является DAG, а
транзитивное закрытие DAG является как строгим частичным порядком, так и самим DAG.. Напротив, нестрогий частичный порядок будет иметь петли на каждом узле и, следовательно, не будет DAG.
В теории категорий
Каждый упорядоченный набор (и каждый предварительно упорядоченный
набор ) может рассматриваться как категория, где для объектов и существует не более одного
морфизма от до Более явно, пусть hom ( x, y) = {( x, y)}, если x ≤ y ( а в противном случае - пустое множество). Такие категории иногда называют позетальными.
Посеты эквивалентны друг другу тогда и только тогда, когда они изоморфны. В poset наименьший элемент, если он существует, является начальным объектом, а наибольший элемент, если он существует, является конечным объектом. Кроме того, каждый предварительно упорядоченный набор эквивалентен poset. Наконец, каждая подкатегория чугуна изоморфизм-замкнута.
Частичные порядки в топологических пространствах
Основная статья:
Частично упорядоченное пространство Если это частично упорядоченное множество, которому также была задана структура
топологического пространства, то принято считать, что это
замкнутое подмножество пространства топологического
произведения. В этом предположении отношения частичного порядка хорошо себя ведут в
пределах в том смысле, что если и для всех тогда
Интервалы
Интервал в посете P является подмножеством я из P со свойством, что для любых х и у в I и любой г в Р, если X ≤ Z ≤ у, то г также находится в I. (Это определение обобщает определение интервала для действительных чисел.)
Для получения более ≤ б, то отрезок [,
Ь ] есть множество элементов х, удовлетворяющих а ≤ х ≤ B (то есть, ≤ х и х ≤ б). Он содержит как минимум элементы a и b.
Используя соответствующее строгое отношение «lt;», открытый интервал ( a, b) - это набор элементов x, удовлетворяющих a lt; x lt; b (то есть a lt; x и x lt; b). Открытый интервал может быть пустым, даже если a lt; b. Например, открытый интервал (1, 2) для целых чисел пуст, поскольку нет таких целых I, что 1 lt; I lt;2.
В полуинтервалах [,
б) и (, Ь ] определяются аналогично.
Иногда определения расширяются, чтобы позволить a gt; b, и в этом случае интервал пуст.
Интервал I ограничен, если существуют такие элементы, что
I ⊆ [ a, b ]. Каждый интервал, который может быть представлен в обозначении интервалов, очевидно, ограничен, но обратное неверно. Например, пусть P = (0, 1) ∪ (1, 2) ∪ (2, 3) как подмножество
действительных чисел. Подмножество (1, 2) является ограниченным интервалом, но это не имеет никакого
инфимуму или
супремума в P, поэтому он не может быть записан в интервале обозначений с использованием элементов P.
ЧУМ называется локально конечным, если
конечен любой ограниченный интервал. Например,
целые числа локально конечны при их естественном порядке. Лексикографический порядок в декартовом произведении не является локально конечным, поскольку (1, 2) ≤ (1, 3) ≤ (1, 4) ≤ (1, 5) ≤... ≤ (2, 1). Используя обозначение интервалов, свойство « a покрывается b » можно эквивалентно перефразировать как
Эту концепцию интервала в частичном порядке не следует путать с конкретным классом частичных порядков, известным как интервальные порядки.
Смотрите также
- Антиматроид, формализация порядков на множестве, которая позволяет использовать более общие семейства порядков, чем посеты.
- Причинная совокупность, подход к квантовой гравитации на основе позета
- График сопоставимости
- Полный частичный заказ
- Направленный набор - набор с предварительным порядком, в котором любые два элемента всегда меньше или равны некоторому третьему элементу.
- Градуированный посет
- Алгебра инцидентности
- Решетка - абстрактная структура, изучаемая в математических дисциплинах теории порядка и абстрактной алгебры.
- Локально конечный ЧУМ
- Функция Мёбиуса на позах
- Вложенная коллекция наборов
- Многогранник порядка
- Заказанное поле
- Заказанная группа
- Упорядоченное векторное пространство
- Топология Poset, своего рода топологическое пространство, которое может быть определено из любого poset
- Непрерывность Скотта - непрерывность функции между двумя частичными порядками.
- Полурешетка
- Полупорядок
- Стохастическое доминирование
- Строгий слабый порядок - строгий частичный порядок «lt;», в котором отношение «ни a lt; b, ни b lt; a » не является транзитивным.
- Общий заказ - заказ, все элементы которого сопоставимы.
- Дерево - Структура данных включения набора
- Лемма Цорна - Математическое предложение, эквивалентное выбранной аксиоме
Примечания
Цитаты
использованная литература
внешние ссылки