Частично заказанный комплект - Partially ordered set
Транзитивные бинарные отношения | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Все определения неявно требуют, чтобы однородное отношение было транзитивным : " " указывает, что свойство столбца требуется по определению термина строки (в самом левом углу). Например, определение отношения эквивалентности требует, чтобы оно было симметричным. Упомянутые здесь дополнительные свойства , что однородное отношение может удовлетворять.
|
В математике , особенно в теории порядка , частично упорядоченное множество (также poset ) формализует и обобщает интуитивную концепцию упорядочения, последовательности или расположения элементов набора . Poset состоит из набора вместе с бинарным отношением, указывающим, что для определенных пар элементов в наборе один из элементов предшествует другому в упорядочении. Само отношение называется «частичным порядком». Слово partial в именах «частичный порядок» и «частично упорядоченный набор» используется как указание на то, что не каждая пара элементов должна быть сопоставимой. То есть могут быть пары элементов, для которых ни один элемент не предшествует другому в poset. Таким образом, частичные заказы обобщают общие заказы , в которых каждая пара сопоставима.
Неформальное определение
Частичный порядок определяет понятие сравнения . Два элемента х и у могут стоять в любом из четырех взаимоисключающих отношений друг к другу: либо х < у или х = у , или х > у или х и у являются несравнима .
Набор с частичным порядком называется частично упорядоченным набором (также называемым poset ). Иногда также используется термин упорядоченный набор , если из контекста ясно, что никакой другой вид порядка не подразумевается. В частности, полностью упорядоченные множества также могут называться «упорядоченные множества», особенно в областях, где эти структуры более распространены, чем посеты.
Позиционирование может быть визуализировано с помощью его диаграммы Хассе , которая отображает отношение упорядочения.
Отношение частичного порядка
Отношение частичного порядка - это однородное отношение, которое является транзитивным и антисимметричным . Есть два общих подопределения для отношения частичного порядка, для рефлексивного и иррефлексивного отношений частичного порядка, также называемых «нестрогим» и «строгим» соответственно. Эти два определения можно поставить во взаимно однозначное соответствие , так что для каждого строгого частичного порядка существует уникальный соответствующий нестрогий частичный порядок, и наоборот. Термин частичный порядок обычно относится к нестрогому отношению частичного порядка.
Нестрогий частичный заказ
Рефлексивный , слабый , или нестрогий частичный порядок - этооднородное отношение≤ надмножеством, которое являетсярефлексивным,антисимметричнымитранзитивным. То есть для всегоон должен удовлетворять:
- рефлексивность :, т.е. каждый элемент связан с самим собой.
- антисимметрия : если , т.е. никакие два различных элемента не предшествуют друг другу.
- транзитивность : если .
Нестрогий частичный порядок также известен как антисимметричный предпорядок .
Строгий частичный заказ
Иррефлексивное , сильный , илистрогий частичный порядок на- это однородное отношение <on,которое являетсяиррефлексивным,транзитивнымиасимметричным; то есть удовлетворяет следующим условиям для всех
- Безрезультатность : нет , т.е. ни один элемент не связан с самим собой
- Транзитивность : если
- Асимметрия : если нет .
Безрефлексивность и транзитивность вместе подразумевают асимметрию. Также асимметрия подразумевает иррефлексивность. Другими словами, транзитивное отношение асимметрично тогда и только тогда, когда оно иррефлексивно. Таким образом, определение будет таким же, если оно не включает иррефлексивность или асимметрию (но не то и другое одновременно).
Строгий частичный заказ также известен как строгий предварительный заказ .
Соответствие строгих и нестрогих отношений частичного порядка
Строгие и нестрогие частичные заказы на множестве тесно связаны. Нестрогий частичный порядок может быть преобразован в строгий частичный порядок, удаляя все отношения формы , то есть строгий частичный порядок является множеством , где этим отношение идентичности на и обозначает набор вычитания . И наоборот, строгий частичный порядок <on может быть преобразован в нестрогий частичный порядок путем присоединения всех отношений этой формы; то есть является нестрогим частичным порядком. Таким образом, если - нестрогий частичный порядок, то соответствующий строгий частичный порядок <является иррефлексивным ядром, задаваемым формулой
Двойные заказы
Двойной (или напротив ) из отношения частичного порядка определяется позволяя быть
обратное отношение из , то есть тогда и только тогда . Двойственный к нестрогому частичному порядку является нестрогим частичным порядком, а двойственный к строгому частичному порядку является строгим частичным порядком. Дуальным к двойственному отношению является исходное отношение.Обозначение
Мы можем рассматривать как частично упорядоченное множество 3-кортежа , или даже 5-кортеж , где и являются нестрогие частичные отношения порядка, и строгие частичные отношения порядка, двойственным является и и также являются двойственными друг друга.
Любое из четырех отношений частичного порядка на данном наборе однозначно определяет остальные три. Следовательно, в качестве обозначения мы можем написать или и предположить, что другие отношения определены соответствующим образом. Чаще всего используется нестрогий частичный порядок . Некоторые авторы используют символы, отличные от таких, как или, чтобы отличать частичные заказы от общих заказов.
Когда речь идет о частичных порядков, не следует принимать в качестве
дополнения в . является обратным к иррефлексивному ядру , которое всегда является подмножеством дополнения , но равно дополнению тогда и только тогда , когда является полным порядком.Примеры
Стандартные примеры позет, возникающих в математике, включают:
- В действительных числах , или вообще любой вполне упорядоченное множество, упорядочены по стандарту менее чем или равных отношению ≤, не является строгим частичным порядком.
- Для действительных чисел обычное отношение «
Один знакомый пример частично упорядоченного множества - это собрание людей, упорядоченное по генеалогическому происхождению. Некоторые пары людей связаны отношениями потомков и предков, но другие пары людей несравнимы, и ни одна из них не является потомком другой.
Заказы на декартово произведение частично упорядоченных множеств
В порядке увеличения силы, т . Е. Уменьшения наборов пар, три из возможных частичных порядков на декартовом произведении двух частично упорядоченных наборов равны (см. Рис. 3-5):
б ) ≤ ( с , d ) , если < с или ( = с и б ≤ d );Все три аналогично можно определить для декартова произведения более двух наборов.
Применительно к упорядоченным векторным пространствам над одним и тем же полем результат в каждом случае также является упорядоченным векторным пространством.
См. Также заказы на декартово произведение полностью упорядоченных наборов .
Суммы частично упорядоченных наборов
Другой способ объединения двух (непересекающихся) множеств - это порядковая сумма (или линейная сумма ) Z = X ⊕ Y , определенная на объединении базовых множеств X и Y в порядке a ≤ Z b тогда и только тогда, когда:
- a , b ∈ X с a ≤ X b , или
- a , b ∈ Y с a ≤ Y b , или
- ∈ X и B ∈ Y .
Если два посета хорошо упорядочены , то их порядковая сумма
тоже .Последовательно-параллельные частичные порядки формируются из операции порядкового суммирования (в этом контексте называемой последовательной компоновкой) и другой операции, называемой параллельной композицией. Параллельная композиция - это несвязное объединение двух частично упорядоченных наборов без отношения порядка между элементами одного набора и элементами другого набора.
Производные понятия
В примерах используется ЧУМ, состоящий из
множества всех подмножеств трехэлементного множества, упорядоченных по включению множества (см. Рис. 1).- имеет отношение к Ь когда это ≤
Extrema
В частности, есть несколько понятий «наибольший» и «наименьший» элементы :
- Наибольший элемент и наименьший элемент: элемент является
В качестве другого примера рассмотрим положительные целые числа , упорядоченные по делимости: 1 - наименьший элемент, так как он делит все остальные элементы; с другой стороны, у этого poset нет наибольшего элемента (хотя, если бы один включил 0 в poset, который кратен любому целому числу, это был бы наибольший элемент; см. Рис.7). В этом частично упорядоченном множестве нет даже максимальных элементов, так как любой g делит, например, 2 g , отличных от него, поэтому g не является максимальным. Если число 1 исключено, сохраняя при этом делимость упорядочением по элементам больше 1, то результирующий poset не имеет минимального элемента, но любое простое число является минимальным элементом для него. В этом наборе 60 - это верхняя граница (хотя и не наименьшая верхняя граница) подмножества, которое не имеет никакой нижней границы (поскольку 1 не входит в набор); с другой стороны, 2 - это нижняя граница подмножества степеней двойки, не имеющая никакой верхней границы.
Отображения между частично упорядоченными наборами
Для двух частично упорядоченных множеств ( 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 помеченных элементов:
Элементы | Любой | Переходный | Рефлексивный | Предзаказ | Частичный заказ | Всего предзаказ | Общий заказ | Отношение эквивалентности |
---|---|---|---|---|---|---|---|---|
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 | 4096 | 355 | 219 | 75 | 24 | 15 |
п | 2 п 2 | 2 п 2 - п | S ( п , к ) | п ! | S ( п , к ) | |||
OEIS | A002416 | A006905 | A053763 | A000798 | A001035 | A000670 | A000142 | A000110 |
Количество строгих частичных заказов такое же, как и количество частичных заказов.
Если подсчет производится только до изоморфизма, получается последовательность 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 .Используя соответствующее строгое отношение «<», открытый интервал ( a , b ) - это набор элементов x, удовлетворяющих a < x < b (то есть a < x и x < b ). Открытый интервал может быть пустым, даже если a < b . Например, открытый интервал (1, 2) для целых чисел пуст, поскольку нет таких целых I , что 1 < I <2 .
В полуинтервалах [ ,
б ) и ( , Ь ] определяются аналогично.Иногда определения расширяются, чтобы позволить a > 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
- Непрерывность Скотта - непрерывность функции между двумя частичными порядками.
- Полурешетка
- Полупорядок
- Стохастическое доминирование
- Строгий слабый порядок - строгий частичный порядок «<», в котором отношение «ни a < b, ни b < a » не является транзитивным.
- Общий заказ - заказ, все элементы которого сопоставимы.
- Дерево - Структура данных включения набора
- Лемма Цорна - Математическое предложение, эквивалентное выбранной аксиоме
Примечания
Цитаты
использованная литература
- Дэйви, BA; Пристли, HA (2002). Введение в решетки и порядок (2-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN 978-0-521-78451-1.
- Дешпанде, Джаянт В. (1968). «О непрерывности частичного порядка» . Труды Американского математического общества . 19 (2): 383–386. DOI : 10.1090 / S0002-9939-1968-0236071-7 .
- Шмидт, Гюнтер (2010). Реляционная математика . Энциклопедия математики и ее приложений. 132 . Издательство Кембриджского университета. ISBN 978-0-521-76268-7.
- Бернд Шредер (11 мая 2016 г.). Упорядоченные множества: введение со связями от комбинаторики к топологии . Birkhäuser. ISBN 978-3-319-29788-0.
- Стэнли, Ричард П. (1997). Перечислительная комбинаторика 1 . Кембриджские исследования в области высшей математики. 49 . Издательство Кембриджского университета. ISBN 0-521-66351-2.