stringtranslate.com

Частично упорядоченный набор

Рис. 1 Диаграмма Хассе множества всех подмножеств трехэлементного множества , упорядоченного по включению . Множества, соединенные восходящим путем, например и , сравнимы, тогда как например и не сравнимы.

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

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

Отношения частичного порядка

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

Частичные заказы

Рефлексивный , слабый , [1 ] илинестрогий частичный порядок [2],обычноназываемый просточастичным порядком, являетсяоднородным отношением≤ намножестве , которое являетсярефлексивным,антисимметричнымитранзитивным. То есть, для всехоно должно удовлетворять:

  1. Рефлексивность : каждый элемент соотносится сам с собой.
  2. Антисимметрия : если и , то , т.е. никакие два различных элемента не предшествуют друг другу.
  3. Транзитивность : если и то .

Нестрогий частичный порядок также известен как антисимметричный предпорядок .

Строгие частичные заказы

Нерефлексивный , сильный , [1 ] илистрогий частичный порядок — это однородное отношение < на множестве, которое являетсятранзитивным,иррефлексивнымиасимметричным; то есть оно удовлетворяет следующим условиям для всех

  1. Транзитивность : если и то .
  2. Иррефлексивность : , т.е. ни один элемент не связан сам с собой (также называется антирефлексивным).
  3. Асимметрия : если да, то нет .

Транзитивное отношение асимметрично тогда и только тогда, когда оно иррефлексивно. [3] Таким образом, определение остается тем же, если оно исключает либо иррефлексивность, либо асимметрию (но не оба сразу).

Строгий частичный порядок также известен как асимметричный строгий предварительный порядок .

Соответствие строгих и нестрогих отношений частичного порядка

Рис. 2 Коммутативная диаграмма связей между строгими/нестрогими отношениями и их дуальными отношениями посредством операций рефлексивного замыкания ( cls ), иррефлексивного ядра ( ker ) и обратного отношения ( cnv ). Каждое отношение изображается своей логической матрицей для частично упорядоченного множества, диаграмма Хассе которого изображена в центре. Например, строка 3, столбец 4 нижней левой матрицы пусты.

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

Двойные заказы

Двойственное (или противоположное ) отношение частичного порядка определяется, если будет обратным отношением , то есть тогда и только тогда, когда . Двойственное нестрогому частичному порядку является нестрогим частичным порядком, [4] а двойственное строгому частичному порядку является строгим частичным порядком. Двойственное двойственному отношению является исходное отношение.

Обозначение

При наличии множества и отношения частичного порядка, обычно нестрогого частичного порядка , мы можем однозначно расширить нашу нотацию, чтобы определить четыре отношения частичного порядка и , где — отношение нестрогого частичного порядка на , — связанное отношение строгого частичного порядка на ( иррефлексивное ядро ​​) , — двойственное к , а — двойственное к . Строго говоря, термин частично упорядоченный набор относится к множеству со всеми этими отношениями, определенными соответствующим образом. Но на практике нужно рассматривать только одно отношение, или , или, в редких случаях, нестрогие и строгие отношения вместе, . [5]

Термин упорядоченный набор иногда используется как сокращение для частично упорядоченного набора , если из контекста ясно, что никакой другой вид порядка не подразумевается. В частности, полностью упорядоченные наборы также могут называться «упорядоченными наборами», особенно в областях, где эти структуры более распространены, чем частично упорядоченные множества. Некоторые авторы используют другие символы, чем, например, [6] или [7], чтобы отличать частичные порядки от полных порядков.

При ссылке на частичные порядки не следует понимать как дополнение к . Отношение является обратным к иррефлексивному ядру , которое всегда является подмножеством дополнения к , но равно дополнению к , если и только если , является полным порядком. [a]

Альтернативные определения

Другой способ определения частичного порядка, найденный в информатике , — это понятие сравнения . В частности, учитывая, как определено ранее, можно заметить, что два элемента x и y могут находиться в любом из четырех взаимоисключающих отношений друг к другу: либо x < y , либо x = y , либо x > y , либо x и y несравнимы . Это может быть представлено функцией , которая возвращает один из четырех кодов , когда даны два элемента. [8] [9] Это определение эквивалентно частичному порядку на сетоиде , где равенство считается определенным отношением эквивалентности, а не равенством множеств. [10]

Уоллис определяет более общее понятие отношения частичного порядка как любое однородное отношение , которое является транзитивным и антисимметричным . Это включает в себя как рефлексивные, так и нерефлексивные частичные порядки как подтипы. [1]

Конечный частично упорядоченный набор может быть визуализирован с помощью его диаграммы Хассе . [11] В частности, принимая отношение строгого частичного порядка , можно построить направленный ациклический граф (DAG), взяв каждый элемент из за узел, а каждый элемент из за ребро. Транзитивное сокращение этого DAG [b] тогда является диаграммой Хассе. Аналогично этот процесс может быть обращен для построения строгих частичных порядков из определенных DAG. Напротив, граф, связанный с нестрогим частичным порядком, имеет самопетли в каждом узле и, следовательно, не является DAG; когда говорят, что нестрогий порядок изображен диаграммой Хассе, на самом деле показан соответствующий строгий порядок.

Примеры

Отношения деления до 4
Рис. 3 График делимости чисел от 1 до 4. Этот набор частично, но не полностью, упорядочен, поскольку существует связь между 1 и каждым другим числом, но нет связи между 2 и 3 или 3 и 4.

Стандартные примеры частично упорядоченных множеств, возникающих в математике, включают в себя:

Один из известных примеров частично упорядоченного множества — это набор людей, упорядоченных по генеалогическому происхождению. Некоторые пары людей имеют связь потомок-предок, но другие пары людей несравнимы, и ни один из них не является потомком другого.

Порядки декартового произведения частично упорядоченных множеств

В порядке возрастания силы, т.е. убывания наборов пар, три возможных частичных порядка декартова произведения двух частично упорядоченных наборов следующие (см. рис. 4):

Все три можно аналогичным образом определить для декартова произведения более чем двух множеств.

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

См. также порядки декартова произведения полностью упорядоченных множеств .

Суммы частично упорядоченных множеств

Другим способом объединения двух (непересекающихся) частично упорядоченных множеств является порядковая сумма [12] (или линейная сумма ), [13] Z = XY , определяемая на объединении базовых множеств X и Y порядком aZ b тогда и только тогда, когда:

Если два частично упорядоченных множества вполне упорядочены , то таковой является и их порядковая сумма. [14]

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

Производные понятия

В примерах используется частично упорядоченное множество, состоящее из множества всех подмножеств трехэлементного множества, упорядоченного по включению множеств (см. рис. 1).

Экстремумы

Рис. 5 Рисунок выше с удаленными наибольшими и наименьшими элементами. В этом сокращенном посете верхний ряд элементов — все максимальные элементы, а нижний ряд — все минимальные элементы, но нет наибольшего и наименьшего элемента.

В частично упорядоченном множестве существует несколько понятий «наибольшего» и «наименьшего» элемента, а именно:

Рис. 6 Неотрицательные целые числа , упорядоченные по делимости

В качестве другого примера рассмотрим положительные целые числа , упорядоченные по делимости: 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 , ≼) называются изоморфными . Изоморфные порядки имеют структурно подобные диаграммы Хассе (см. рис. 7a). Можно показать, что если существуют сохраняющие порядок отображения и такие, что и дает функцию тождества на S и T , соответственно, то S и T являются изоморфными порядком. [15]

Например, отображение из множества натуральных чисел (упорядоченного по делимости) в множество степеней натуральных чисел (упорядоченное по включению множеств) можно определить, переведя каждое число в множество его простых делителей . Оно сохраняет порядок: если x делит y , то каждый простой делитель x также является простым делителем y . Однако оно не является ни инъективным (поскольку оно отображает и 12, и 6 в ), ни отражающим порядок (поскольку 12 не делит 6). Вместо этого, переводя каждое число в множество его простых делителей степеней, мы определяем отображение , которое сохраняет порядок, отражает порядок и, следовательно, вкладывает порядок. Это не изоморфизм порядка (поскольку оно, например, не отображает ни одно число в множество ), но его можно сделать таковым, ограничив его область значений до Рис. 7b показывает подмножество и его изоморфный образ при g . Построение такого порядкового изоморфизма в степенное множество может быть обобщено на широкий класс частичных порядков, называемых дистрибутивными решетками ; см. теорему Биркгофа о представлении .

Количество частичных заказов

Последовательность A001035 в OEIS дает число частичных порядков на наборе из n помеченных элементов:

Обратите внимание, что S ( n , k ) относится к числам Стирлинга второго рода .

Количество строгих частичных порядков такое же, как и количество частичных порядков.

Если подсчет ведется только до изоморфизма, то получается последовательность 1, 1, 2, 5, 16, 63, 318, ... (последовательность A000112 в OEIS ).

Подгруппы

ЧУМ называется подмножеством другого ЧУМ , если является подмножеством и является подмножеством . Последнее условие эквивалентно требованию, что для любого и в (и, следовательно, также в ), если , то .

Если является подмножеством и, кроме того, для всех и в , всякий раз, когда мы также имеем , то мы называем подмножество , индуцированное , и пишем .

Линейное расширение

Частичный порядок на множестве называется расширением другого частичного порядка на при условии, что для всех элементов всякий раз, когда также имеет место, что Линейное расширение является расширением, которое также является линейным (то есть полным) порядком. В качестве классического примера, лексикографический порядок полностью упорядоченных множеств является линейным расширением их порядка произведения. Каждый частичный порядок может быть расширен до полного порядка ( принцип порядка-расширения ). [16]

В информатике алгоритмы нахождения линейных расширений частичных порядков (представленных в виде порядков достижимости направленных ациклических графов ) называются топологической сортировкой .

В теории категорий

Каждый посет (и каждое предупорядоченное множество ) можно рассматривать как категорию , в которой для объектов и существует не более одного морфизма из в Более явно, пусть hom( x , y ) = {( x , y )}, если xy (и в противном случае пустое множество ) и Такие категории иногда называют посетальными .

ЧУМ эквивалентны друг другу тогда и только тогда, когда они изоморфны . В ЧУМ наименьший элемент, если он существует, является начальным объектом , а наибольший элемент, если он существует, является конечным объектом . Кроме того, каждое предупорядоченное множество эквивалентно ЧУМ. Наконец, каждая подкатегория ЧУМ замкнута относительно изоморфизма .

Частичные порядки в топологических пространствах

Если — частично упорядоченное множество, которому также задана структура топологического пространства , то принято предполагать, что — замкнутое подмножество топологического пространства произведения. При этом предположении отношения частичного порядка ведут себя хорошо в пределах в том смысле, что если и и для всех , то [17]

Интервалы

Выпуклое множество в частично упорядоченном множестве P — это подмножество I множества P , обладающее тем свойством, что для любых x и y из I и любого z из P , если xzy , то z также принадлежит I. Это определение обобщает определение интервалов действительных чисел . Когда возможна путаница с выпуклыми множествами геометрии , вместо «выпуклый» используют порядково-выпуклый .

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

Интервал в частично упорядоченном множестве P — это подмножество, которое можно определить с помощью интервальной нотации:

Если ab не выполняется, все эти интервалы пусты. Каждый интервал является выпуклым множеством, но обратное не выполняется; например, в частично упорядоченном множестве делителей числа 120, упорядоченном по делимости (см. рис. 7b), множество {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 » можно перефразировать эквивалентно как

Эту концепцию интервала в частичном порядке не следует путать с особым классом частичных порядков, известных как интервальные порядки .

Смотрите также

Примечания

  1. ^ Доказательство можно найти здесь .
  2. ^ который всегда существует и является единственным, поскольку предполагается конечным
  3. ^ См . Общая теория относительности § Путешествия во времени .

Цитаты

  1. ^ abc Wallis, WD (14 марта 2013 г.). Руководство для начинающих по дискретной математике. Springer Science & Business Media. стр. 100. ISBN 978-1-4757-3826-1.
  2. ^ Simovici, Dan A. & Djeraba, Chabane (2008). "Частично упорядоченные множества". Математические инструменты для интеллектуального анализа данных: теория множеств, частичные порядки, комбинаторика . Springer. ISBN 9781848002012.
  3. ^ Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007). «Транзитивные замыкания бинарных отношений I». Acta Universitatis Carolinae. Mathematica et Physica . 48 (1). Прага: Школа математики – физики Карлова университета: 55–69.Лемма 1.1 (iv). Этот источник называет асимметричные отношения «строго антисимметричными».
  4. Дэйви и Пристли (2002), стр. 14–15.
  5. ^ Авигад, Джереми; Льюис, Роберт Й.; ван Дорн, Флорис (29 марта 2021 г.). "13.2. Подробнее об упорядочениях". Логика и доказательство (выпуск 3.18.4 ред.) . Получено 24 июля 2021 г. Таким образом, мы можем рассматривать каждый частичный порядок как пару, состоящую из слабого частичного порядка и связанного с ним строгого.
  6. ^ Раундс, Уильям С. (7 марта 2002 г.). "Слайды лекций" (PDF) . EECS 203: ДИСКРЕТНАЯ МАТЕМАТИКА . Получено 23 июля 2021 г.
  7. ^ Квонг, Харрис (25 апреля 2018 г.). «7.4: Частичный и полный порядок». Спиральная рабочая тетрадь по дискретной математике . Получено 23 июля 2021 г.
  8. ^ "Конечные частично упорядоченные множества". Sage 9.2.beta2 Справочное руководство: Комбинаторика . Получено 5 января 2022 г. compare_elements( x , y ): Сравнить x и y в частично упорядоченном множестве. Если x < y , вернуть −1. Если x = y , вернуть 0. Если x > y , вернуть 1. Если x и y несравнимы, вернуть None.
  9. ^ Чен, Питер; Дин, Гуоли; Сейден, Стив. On Poset Merging (PDF) (Технический отчет). стр. 2. Получено 5 января 2022 г. Сравнение двух элементов s, t в S возвращает одно из трех различных значений, а именно s≤t, s>t или s|t.
  10. ^ Превосто, Виржиле; Жауме, Матье (11 сентября 2003 г.). Создание доказательств в иерархии математических структур. CALCULEMUS-2003 – 11-й симпозиум по интеграции символических вычислений и механизированного рассуждения. Рим, Италия: Aracne. С. 89–100.
  11. ^ Меррифилд, Ричард Э.; Симмонс, Говард Э. (1989). Топологические методы в химии . Нью-Йорк: John Wiley & Sons. С. 28. ISBN 0-471-83817-9. Получено 27 июля 2012 г. Частично упорядоченное множество удобно представлять диаграммой Хассе ...
  12. ^ Неггерс, Дж.; Ким, Хи Сик (1998), «4.2 Порядок продукта и лексикографический порядок», Basic Posets , World Scientific, стр. 62–63, ISBN 9789810235895
  13. Дэйви и Пристли (2002), стр. 17–18.
  14. ^ PR Халмос (1974). Наивная теория множеств . Спрингер. п. 82. ИСБН 978-1-4757-1645-0.
  15. Дэйви и Пристли (2002), стр. 23–24.
  16. ^ Jech, Thomas (2008) [1973]. Аксиома выбора . Dover Publications . ISBN 978-0-486-46624-8.
  17. ^ Уорд, Л. Э. Младший (1954). «Частично упорядоченные топологические пространства». Труды Американского математического общества . 5 (1): 144–161. doi : 10.1090/S0002-9939-1954-0063016-5 . hdl :10338.dmlcz/101379.

Ссылки

Внешние ссылки

Медиафайлы, связанные с диаграммами Хассе на Wikimedia Commons; каждый из которых показывает пример частичного порядка