В математике , особенно в теории порядка , частичный порядок множества — это такое расположение, при котором для определенных пар элементов один предшествует другому. Слово «частичный» используется для обозначения того, что не каждая пара элементов должна быть сопоставима; то есть могут существовать пары, в которых ни один элемент не предшествует другому. Таким образом, частичные заказы обобщают общие заказы , в которых каждая пара сопоставима.
Формально частичный порядок — это однородное бинарное отношение , которое является рефлексивным , антисимметричным и транзитивным . Частично упорядоченный набор ( сокращенно частично упорядоченный набор ) — это упорядоченная пара набора (называемого основным набором ) и частичного порядка на . Когда значение ясно из контекста и нет никакой двусмысленности в отношении частичного порядка, сам набор иногда называют частично упорядоченным набором.
Отношения частичного порядка
Термин «частичный порядок» обычно относится к рефлексивным отношениям частичного порядка, называемым в этой статье нестрогим частичным порядком. Однако некоторые авторы используют этот термин для обозначения другого распространенного типа отношений частичного порядка — иррефлексивных отношений частичного порядка, также называемых строгими отношениями частичного порядка. Строгий и нестрогий частичный порядок можно поставить во взаимно однозначное соответствие , поэтому для каждого строгого частичного порядка существует уникальный соответствующий нестрогий частичный порядок, и наоборот.
Иррефлексивный , сильный , [ 1 ] илистрогий частичный порядок — однородное отношение < на множестве, которое являетсяиррефлексивным,асимметричнымитранзитивным; то есть он удовлетворяет следующим условиям для всех
Иррефлексивность : не , т.е. ни один элемент не связан сам с собой (также называемый антирефлексивным).
Иррефлексивность и транзитивность вместе подразумевают асимметрию. Кроме того, асимметрия подразумевает иррефлексивность. Другими словами, транзитивное отношение асимметрично тогда и только тогда, когда оно иррефлексивно. [3] Таким образом, определение остается тем же, если оно опускает либо иррефлексивность, либо асимметрию (но не то и другое одновременно).
Соответствие строгих и нестрогих отношений частичного порядка.
Строгие и нестрогие частичные порядки на множестве тесно связаны между собой. Нестрогий частичный порядок может быть преобразован в строгий частичный порядок путем удаления всех отношений вида , то есть строгий частичный порядок представляет собой набор , в котором находится тождественное отношение и обозначает вычитание множества . И наоборот, строгий частичный порядок <on может быть преобразован в нестрогий частичный порядок путем присоединения всех отношений этой формы; то есть является нестрогим частичным порядком. Таким образом, если это нестрогий частичный порядок, то соответствующий строгий частичный порядок < является иррефлексивным ядром, заданным формулой
Двойственное (или противоположное ) отношению частичного порядка определяется путем обозначения обратного отношения к , т.е. тогда и только тогда, когда . Двойственным к нестрогому частичному порядку является нестрогий частичный порядок [4] , а двойственным строгому частичному порядку является строгий частичный порядок. Двойственное к двойственному отношению является исходным отношением.
Обозначения
Учитывая набор и отношение частичного порядка, обычно нестрогий частичный порядок , мы можем однозначно расширить наши обозначения, чтобы определить четыре отношения частичного порядка и , где нестрогое отношение частичного порядка на , является ассоциированным строгим отношением частичного порядка на ( иррефлексивное ядро ) , является двойственным , и является двойственным . Строго говоря, термин « частично упорядоченное множество» относится к множеству, в котором все эти отношения определены соответствующим образом. Но на практике достаточно рассматривать только одно отношение или , или, в редких случаях, строгие и нестрогие отношения вместе, . [5]
Термин «упорядоченный набор» иногда используется как сокращение от частично упорядоченного набора , если из контекста ясно, что никакой другой вид порядка не подразумевается. В частности, полностью упорядоченные множества также можно называть «упорядоченными множествами», особенно в областях, где эти структуры более распространены, чем частично упорядоченные множества. Некоторые авторы используют символы, отличные от таких, как [6] или [7] , чтобы отличить частичные заказы от полных.
Когда речь идет о частичных заказах, их не следует воспринимать как дополнение к . Отношение является обратным иррефлексивному ядру , которое всегда является подмножеством дополнения , но равно дополнению if и только тогда, когда , является полным порядком. [а]
Альтернативные определения
Другой способ определения частичного порядка, встречающийся в информатике , заключается в использовании понятия сравнения . В частности, учитывая , как определено ранее, можно заметить, что два элемента x и y могут находиться в любом из четырех взаимоисключающих отношений друг с другом: либо x < y , либо x = y , либо x > y , либо x и y являются несравненный . Это можно представить функцией , которая возвращает один из четырех кодов при наличии двух элементов. [8] [9] Это определение эквивалентно частичному порядку на сетоиде , где равенство считается определенным отношением эквивалентности , а не примитивным понятием равенства множеств. [10]
Уоллис определяет более общее понятие отношения частичного порядка как любое однородное отношение , которое является транзитивным и антисимметричным . Сюда входят как рефлексивные, так и иррефлексивные частичные заказы как подтипы. [1]
Конечное ЧУ-множество можно визуализировать через его диаграмму Хассе . [11] В частности, используя строгое отношение частичного порядка , можно построить ориентированный ациклический граф (DAG), принимая каждый элемент в качестве узла, а каждый элемент в качестве ребра. Тогда транзитивная редукция этого DAG [b] представляет собой диаграмму Хассе. Аналогичным образом этот процесс можно обратить вспять, чтобы создать строгие частичные заказы из определенных групп DAG. Напротив, граф, связанный с нестрогим частичным порядком, имеет циклы в каждом узле и, следовательно, не является DAG; когда говорят, что нестрогий порядок изображается диаграммой Хассе, на самом деле показан соответствующий строгий порядок.
Примеры
Стандартные примеры ЧУМ, возникающих в математике, включают:
Действительные числа или вообще любой полностью упорядоченный набор, упорядоченный по стандартному отношению «меньше или равно» ≤, является частичным порядком.
Для действительных чисел обычное отношение меньше чем < является строгим частичным порядком. То же самое справедливо и для обычного отношения «больше чем » > на .
Для частично упорядоченного набора P — пространство последовательностей , содержащее все последовательности элементов из P , где последовательность a предшествует последовательности b , если каждый элемент в a предшествует соответствующему элементу в b . Формально тогда и только тогда, когда для всех ; то есть покомпонентный порядок .
Для набора X и частично упорядоченного набора P функциональное пространство , содержащее все функции от X до P , где f ≤ g тогда и только тогда, когда f ( x ) ≤ g ( x ) для всех
Забор — частично упорядоченный набор, определяемый чередующейся последовательностью отношений порядка a <b> c < d ...
Набор событий в специальной теории относительности и, в большинстве случаев, [c] общей теории относительности , где для двух событий X и Y X ≤ Y тогда и только тогда, когда Y находится в будущем световом конусе X. На событие Y может причинно повлиять X только в том случае, если X ≤ Y .
Один знакомый пример частично упорядоченного множества — это совокупность людей, упорядоченных по генеалогическому происхождению. Некоторые пары людей имеют отношения потомок-предок, но другие пары людей несравнимы, поскольку ни один из них не является потомком другого.
Заказы на декартово произведение частично упорядоченных множеств
В порядке возрастания силы, т. е. убывания наборов пар, можно выделить три возможных частичных порядка декартова произведения двух частично упорядоченных наборов (см. рис. 4):
лексикографический порядок : ( a , b ) ≤ ( c , d ), если a < c или ( a = c и b ≤ d );
Другим способом объединения двух (непересекающихся) ЧУМ является порядковая сумма [12] (или линейная сумма ), [13] Z = X ⊕ Y , определенная на объединении основных множеств X и Y по порядку a ≤ Z b , если и только если:
a , b ∈ X с a ≤ X b , или
a , b ∈ Y с a ≤ Y b , или
а € X и б € Y .
Если два ЧУУ упорядочены , то упорядочена и их порядковая сумма. [14]
Последовательно-параллельные частичные заказы формируются из операции порядковой суммы (в данном контексте называемой композицией серии) и другой операции, называемой параллельной композицией. Параллельная композиция — это непересекающееся объединение двух частично упорядоченных множеств без отношения порядка между элементами одного множества и элементами другого множества.
Производные понятия
В примерах используется ЧУУ, состоящее из множества всех подмножеств трехэлементного множества , упорядоченных по включению множества (см. рис. 1).
a относится к b , когда a ≤ b . Это не означает, что b также связано с a , поскольку отношение не обязательно должно быть симметричным . Например, связано с , но не наоборот.
a и b сравнимы , если a ≤ b или b ≤ a . В остальном они несравнимы . Например, и сопоставимы, а и нет.
Полный порядок или линейный порядок — это частичный порядок, при котором каждая пара элементов сравнима, т. е. сохраняется трихотомия . Например, натуральные числа в их стандартном порядке.
Цепочка — это подмножество частично упорядоченного множества. Например, это цепь.
Антицепь — это подмножество частичного множества, в котором нет двух различных элементов, сравнимых друг с другом . Например, набор синглтонов
Говорят, что элемент a строго меньше элемента b , если a ≤ b и, например, строго меньше, чем
Говорят, что элемент a покрыт другим элементом b , записанным a ⋖ b (или a <: b ), если a строго меньше b и между ними не помещается третий элемент c ; формально: если оба a ≤ b и истинны, и a ≤ c ≤ b ложно для каждого c с использованием строгого порядка <, отношение a ⋖ b можно эквивалентно перефразировать как « a < b , но не a < c < b для любого c ". Например, охвачено, но не охвачено
Экстрема
В ЧУМ есть несколько понятий «наибольшего» и «наименьшего» элемента :
Наибольший элемент и наименьший элемент: элемент является наибольшим элементом , если для каждого элемента Элемент является наименьшим элементом , если для каждого элемента ЧУ-множество может иметь только один наибольший или наименьший элемент. В нашем примере набор является наибольшим элементом и наименьшим.
Максимальные элементы и минимальные элементы: элемент является максимальным элементом, если не существует такого элемента, что. Аналогично, элемент является минимальным элементом, если не существует такого элемента, что Если ЧУ-множество имеет наибольший элемент, он должен быть уникальным максимальным элементом, но в противном случае может быть более одного максимального элемента, и аналогично для наименьших и минимальных элементов. В нашем примере и — максимальный и минимальный элементы. Если убрать их, останется 3 максимальных элемента и 3 минимальных элемента (см. рис. 5).
Верхняя и нижняя границы : для подмножества A из P элемент x в P является верхней границей A , если a ≤ x , для каждого элемента a в A. В частности, x не обязательно должен находиться в A , чтобы быть верхней границей A . Аналогично, элемент x в P является нижней границей A , если a ≥ x , для каждого элемента a в A. Наибольший элемент P — это верхняя граница самого P , а наименьший элемент — нижняя граница P. В нашем примере набор является верхней границей набора элементов.
В качестве другого примера рассмотрим положительные целые числа , упорядоченные по делимости: 1 — наименьший элемент, так как он делит все остальные элементы; с другой стороны, в этом частичном наборе нет наибольшего элемента. В этом частично упорядоченном множестве даже нет максимальных элементов, поскольку любой g делит, например, 2 g , отличный от него, поэтому g не является максимальным. Если исключить число 1, сохранив при этом делимость как порядок на элементы больше 1, то в результирующем ЧУМ нет наименьшего элемента, но любое простое число является для него минимальным элементом. В этом частичном наборе 60 — это верхняя граница (но не наименьшая верхняя граница) подмножества , которое не имеет нижней границы (поскольку 1 нет в частичном наборе); с другой стороны, 2 — это нижняя граница подмножества степеней 2, которая не имеет верхней границы. Если включено число 0, это будет наибольший элемент, поскольку он кратен каждому целому числу (см. рис. 6).
Отображения между частично упорядоченными наборами
Учитывая два частично упорядоченных набора ( S , ≤) и ( T , ≼) , функция называется сохраняющей порядок , или монотонной , или изотонной , если для всех подразумевает f ( x ) ≼ f ( y ) . Если ( U , ≲) также является частично упорядоченным множеством и оба и сохраняют порядок, их композиция также сохраняет порядок. Функция называется отражающей порядок, если для всех f ( x ) ≼ f ( y ) следует.
Если f одновременно сохраняет порядок и отражает порядок, то она называется вложением порядка ( S , ≤) в ( T , ≼) . В последнем случае f обязательно инъективен , поскольку подразумевает и, в свою очередь , в соответствии с антисимметрией Если существует порядковое вложение между двумя частично упорядоченными множествами S и T , говорят, что S может быть вложено в T . Если вложение порядка биективно , оно называется изоморфизмом порядка , а частичные порядки ( S , ≤) и ( T , ≼) называются изоморфными . Изоморфные порядки имеют структурно схожие диаграммы Хассе (см. рис. 7а). Можно показать, что если сохраняющие порядок отображения и существуют такие, что и дают тождественную функцию на S и T соответственно, то S и T порядково-изоморфны. [15]
Например, отображение набора натуральных чисел (упорядоченных по делимости) в набор степеней натуральных чисел (упорядоченных по включению множества) можно определить, приведя каждое число к множеству его простых делителей . Это сохраняет порядок: если x делит y , то каждый простой делитель x также является простым делителем y . Однако он не является ни инъективным (поскольку он отображает и 12, и 6 в ), ни отражающим порядок (поскольку 12 не делит 6). Вместо этого перенос каждого числа в набор его простых делителей степени определяет отображение , которое сохраняет порядок, отражает порядок и, следовательно, вкладывает порядок. Это не порядковый изоморфизм (поскольку он, например, не отображает какое-либо число в множество ), но его можно сделать таковым, ограничив его кодомен до того, что на рис. 7b показано подмножество и его изоморфный образ при g . Построение такого изоморфизма порядка в степенное множество можно обобщить на широкий класс частичных порядков, называемых дистрибутивными решетками ; см. теорему о представлении Биркгофа .
Количество частичных заказов
Последовательность A001035 в OEIS дает количество частичных заказов в наборе из n помеченных элементов:
Количество строгих частичных заказов такое же, как и у частичных заказов.
Если счет производится только до изоморфизма, то получается последовательность 1, 1, 2, 5, 16, 63, 318,... (последовательность A000112 в OEIS ).
Линейное расширение
Частичный порядок на множестве является расширением другого частичного порядка при условии, что для всех элементов всякий раз, когда это также имеет место, Линейное расширение — это расширение, которое также является линейным (то есть полным) порядком. Классический пример: лексикографический порядок полностью упорядоченных множеств является линейным расширением порядка их произведений. Каждый частичный порядок может быть расширен до полного порядка ( принцип расширения порядка ). [16]
Каждое частично упорядоченное множество (и каждое предварительно упорядоченное множество ) можно рассматривать как категорию , в которой для объектов и существует не более одного морфизма от до . Более подробно, пусть hom( x , y ) = {( x , y )}, если x ≤ y ( а в противном случае — пустое множество ) и такие категории иногда называют посетальными . В дифференциальной топологии теория гомологии (HT) используется для классификации эквивалентных гладких многообразий M, связанных с геометрическими формами M.
Частные множества эквивалентны друг другу тогда и только тогда, когда они изоморфны . В частичном наборе наименьший элемент, если он существует, является начальным объектом , а самый большой элемент, если он существует, является конечным объектом . Кроме того, каждый предварительно упорядоченный набор эквивалентен частичному множеству. Наконец, каждая подкатегория ЧУМ является изоморфизм-замкнутой . В дифференциальной топологии теория гомологии (HT) используется для классификации эквивалентных гладких многообразий M, связанных с геометрическими формами M. В теории гомологии дается аксиоматический подход HT, особенно к сингулярным гомологиям. [ необходимо разъяснение ] Члены HT являются алгебраическими инвариантами относительно диффеоморфизмов. Аксиоматическая категория HT взята у Г. Калмбаха из книги Эйленберга–Стинрода (см. ссылки) для того, чтобы показать, что теоретико-множественная топологическая концепция для определения HT может быть расширена до частично упорядоченных множеств P. Важными являются цепи и фильтры в P (заменяет формы M) для определения классификаций HT, доступен для многих приложений P, не связанных с теорией множеств.
Частичные порядки в топологических пространствах
Если это частично упорядоченное множество, которое также имеет структуру топологического пространства , то принято предполагать, что это замкнутое подмножество топологического пространства произведения . При этом предположении отношения частичного порядка хорошо ведут себя на пределе в том смысле, что если и и для всех тогда [17]
Интервалы
Выпуклое множество в частично упорядоченном множестве P — это подмножество I в P , обладающее тем свойством, что для любых x и y в I и любого z в P , если x ⩽ z ⩽ y , то z также находится в I. Это определение обобщает определение интервалов действительных чисел . Когда возможна путаница с выпуклыми множествами геометрии , вместо слова «выпуклый» используется порядково-выпуклый .
Выпуклая подрешетка решетки L — это подрешетка решетки L , которая также является выпуклым множеством решетки L . Любую непустую выпуклую подрешетку можно однозначно представить как пересечение фильтра и идеала L .
Интервал в частичном наборе P — это подмножество, которое можно определить с помощью обозначения интервала :
Для a ≤ b замкнутый интервал [ a , b ] представляет собой набор элементов x, удовлетворяющих a ≤ x ≤ b (то есть a ≤ x и x ≤ b ). Он содержит как минимум элементы a и b .
Используя соответствующее строгое отношение «<», открытый интервал ( a , b ) представляет собой набор элементов x, удовлетворяющих a < x < b (т. е. a < x и x < b ). Открытый интервал может быть пустым, даже если a < b . Например, открытый интервал (0, 1) для целых чисел пуст, поскольку не существует целого числа x такого, что 0 < x < 1 .
Полуинтервалы [ a , b ) и ( a , b ] определяются аналогично .
Всякий раз, когда a ≤ b не выполняется, все эти интервалы пусты. Каждый интервал представляет собой выпуклое множество, но обратное неверно; например, в упорядоченном по делимости наборе делителей числа 120 (см. рис. 7б) множество {1, 2, 4, 5, 8} является выпуклым, но не интервалом.
Интервал 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 » можно эквивалентно перефразировать как
Эту концепцию интервала в частичном порядке не следует путать с особым классом частичных порядков, известным как интервальные порядки .
Смотрите также
Антиматроид , формализация упорядочения на множестве, которая допускает более общие семейства порядков, чем частично упорядоченные множества.
Причинное множество — подход к квантовой гравитации, основанный на частичном множестве.
Граф сопоставимости - граф, связывающий пары сравнимых элементов в частичном порядке.
Полный частичный порядок - термин, используемый в математической теории порядка.Pages displaying wikidata descriptions as a fallback
Градуированный частично упорядоченный набор - частично упорядоченный набор, оснащенный ранговой функцией, иногда называемый ранжированным частично упорядоченным набором.Pages displaying wikidata descriptions as a fallback
Алгебра инцидентности - ассоциативная алгебра, используемая в комбинаторике, разделе математики.Pages displaying wikidata descriptions as a fallback
Решетка - набор, пары которого имеют минимумы и максимумы.
Локально конечное ЧУУ - МатематикаPages displaying wikidata descriptions as a fallbackPages displaying short descriptions with no spaces
^ abc Уоллис, WD (14 марта 2013 г.). Руководство для начинающих по дискретной математике. Springer Science & Business Media. п. 100. ИСБН 978-1-4757-3826-1.
^ Симовичи, Дэн А. и Джераба, Чабане (2008). «Частично упорядоченные множества». Математические инструменты для интеллектуального анализа данных: теория множеств, частичные порядки, комбинаторика . Спрингер. ISBN9781848002012.
^ Флашка, В.; Ежек, Дж.; Кепка, Т.; Кортелайнен, Дж. (2007). «Транзитивные замыкания бинарных отношений I». Acta Universitatis Carolinae. Математика и физика . Прага: Школа математики – Физика Карлова университета. 48 (1): 55–69.Лемма 1.1 (iv). Этот источник называет асимметричные отношения «строго антисимметричными».
^ Дэйви и Пристли (2002), стр. 14–15.
^ Авигад, Джереми; Льюис, Роберт Ю.; ван Доорн, Флорис (29 марта 2021 г.). «13.2. Еще о заказах». Логика и доказательство (выпуск 3.18.4 под ред.) . Проверено 24 июля 2021 г. Таким образом, мы можем думать о каждом частичном порядке как о паре, состоящей из слабого частичного порядка и связанного с ним строгого.
↑ Раундс, Уильям К. (7 марта 2002 г.). «Слайды лекций» (PDF) . EECS 203: ДИСКРЕТНАЯ МАТЕМАТИКА . Проверено 23 июля 2021 г.
↑ Квонг, Харрис (25 апреля 2018 г.). «7.4: Частичный и полный заказ». Спиральная рабочая тетрадь по дискретной математике . Проверено 23 июля 2021 г.
^ «Конечные частично упорядоченные множества». Sage 9.2.beta2 Справочное руководство: Комбинаторика . Проверено 5 января 2022 г. Compare_elements( x , y ): сравнивает x и y в заданном наборе. Если x < y , верните −1. Если x = y , верните 0. Если x > y , верните 1. Если x и y несопоставимы, верните None.
^ Чен, Питер; Дин, Гуоли; Сейден, Стив. Об объединении Poset (PDF) (Технический отчет). п. 2 . Проверено 5 января 2022 г. Сравнение двух элементов s, t в S возвращает одно из трех различных значений, а именно s≤t, s>t или s|t.
^ Превосто, Вергилий; Жауме, Матье (11 сентября 2003 г.). Проведение доказательств в иерархии математических структур. CALCULEMUS-2003 – 11-й симпозиум по интеграции символических вычислений и механизированного мышления. Рим, Италия: Аракне. стр. 89–100.
^ Меррифилд, Ричард Э.; Симмонс, Ховард Э. (1989). Топологические методы в химии . Нью-Йорк: Джон Уайли и сыновья. стр. 28. ISBN0-471-83817-9. Проверено 27 июля 2012 г. Частично упорядоченное множество удобно представить диаграммой Хассе ...
^ Неггерс, Дж.; Ким, Хи Сик (1998), «4.2 Порядок продуктов и лексикографический порядок», Basic Posets , World Scientific, стр. 62–63, ISBN9789810235895
^ Дэйви и Пристли (2002), стр. 17–18.
^ PR Халмош (1974). Наивная теория множеств . Спрингер. п. 82. ИСБН978-1-4757-1645-0.
Дешпанде, Джаянт В. (1968). «О непрерывности частичного приказа». Труды Американского математического общества . 19 (2): 383–386. дои : 10.1090/S0002-9939-1968-0236071-7 .
Шмидт, Гюнтер (2010). Реляционная математика . Энциклопедия математики и ее приложений. Том. 132. Издательство Кембриджского университета. ISBN 978-0-521-76268-7.
Бернд Шредер (11 мая 2016 г.). Упорядоченные множества: введение со связями от комбинаторики к топологии. Биркхойзер. ISBN 978-3-319-29788-0.
Стэнли, Ричард П. (1997). Перечислительная комбинаторика 1 . Кембриджские исследования по высшей математике. Том. 49. Издательство Кембриджского университета. ISBN 0-521-66351-2.
Эйленберг, С. (2016). Основы алгебраической топологии . Издательство Принстонского университета.
Кальмбах, Г. (1976). «Распространение теории гомологии на частично упорядоченные множества». Дж. Рейн Анжью. Математика . 280 : 134–156.
Внешние ссылки
Викискладе есть медиафайлы по теме диаграммы Хассе.
Последовательность OEIS A001035 (количество частично упорядоченных наборов с n помеченными элементами)
Последовательность OEIS A000112 (Количество частично упорядоченных наборов («posesets») с n непомеченными элементами.)