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

(перенаправлено с «Частичный порядок»)

Части́чно упоря́доченное мно́жество (сокр. ЧУМ) — математическое понятие, которое формализует интуитивные идеи упорядочения, расположения элементов в определённой последовательности. Неформально, множество частично упорядочено, если указано, какие элементы следуют за какими (какие элементы больше каких). В общем случае может оказаться так, что некоторые пары элементов не связаны отношением «следует за».

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

Определение и примеры

править

Отношением порядка, или частичным порядком, на множестве   называется бинарное отношение   на   (определяемое некоторым множеством  ), удовлетворяющее следующим условиям[1]:

  • Рефлексивность:  
  • Транзитивность:  
  • Антисимметричность:  

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

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

Терминология и обозначения

править

Отношение частичного порядка обычно обозначают символом  , по аналогии с отношением «меньше либо равно» на множестве вещественных чисел. При этом, если  , то говорят, что элемент   не превосходит  , или что   подчинён  .

Если   и  , то пишут  , и говорят, что   меньше  , или что   строго подчинен  .

Иногда, чтобы отличить произвольный порядок на некотором множестве от известного отношения «меньше либо равно» на множестве действительных чисел, вместо   и   используют специальные символы   и   соответственно.

Строгий и нестрогий порядок

править

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

 

то получим определение строгого, или антирефлексивного порядка.

Если   — нестрогий порядок на множестве  , то отношение  , определяемое как:

 

является строгим порядком на  . Обратно, если   — строгий порядок, то отношение  , определённое как

 

является нестрогим порядком.

Поэтому всё равно — задать на множестве нестрогий порядок или строгий порядок. В результате получится одна и та же структура. Разница только в терминологии и обозначениях.

Интервал

править

Для   замкнутый интервал [a,b] — это множество элементов x, удовлетворяющих неравенству   (то есть   и  ). Интервал содержит, по меньшей мере, элементы a и b.

Если использовать строгое неравенство «<», получим открытый интервал (a,b), множество элементов x, удовлетворяющих неравенству a < x < b (то есть a < x и x < b). Открытый интервал может быть пустым, даже если a < b. Например, открытый интервал (1,2) для целых чисел пуст, поскольку нет целых чисел i, таких что 1 < i < 2.

Иногда определение расширяется, позволяя a > b. В этом случае интервал пуст.

Полуоткрытые интервалы [a,b) и (a,b] определяются аналогичным образом.

Частично упорядоченное множество является локально конечным[англ.], если любой интервал конечен. Например, целые числа локально конечны по их естественному упорядочению. Лексикографический порядок на прямом произведении ℕ×ℕ не является локально конечным, поскольку, например,  .

Концепцию интервала в частично упорядоченных множествах не следует путать со специфичным классом частичных упорядоченных множеств, известных как интервальные порядки[англ.].

Примеры

править
 
Подмножества {x, y, z}, упорядоченные отношением включения
  • Множество вещественных чисел   частично упорядочено по отношению «меньше либо равно» —  .
  • Пусть   — множество всех вещественнозначных функций, определённых на отрезке  , то есть функций вида
 

Введём отношение порядка   на   следующим образом:  , если для всех   выполнено неравенство  . Очевидно, введенное отношение в самом деле является отношением частичного порядка.

  • Пусть   — некоторое множество. Множество   всех подмножеств   (так называемый булеан), частично упорядочено по включению  .

Связанные определения

править

Несравнимые элементы

править

Если   и   — вещественные числа, то имеет место только одно из следующих соотношений:

 

В случае, если   и   — элементы произвольного частично упорядоченного множества, то существует четвёртая логическая возможность: не выполнено ни одно из указанных трех соотношений. В этом случае элементы   и   называются несравнимыми. Например, если   — множество действительнозначных функций на отрезке  , то элементы   и   будут несравнимы. Возможность существования несравнимых элементов объясняет смысл термина «частично упорядоченное множество».

Минимальный/максимальный и наименьший/наибольший элементы

править

Из-за того, что в частично упорядоченном множестве могут быть пары несравнимых элементов, вводятся два различных определения: минимального элемента и наименьшего элемента.

Элемент   называется минимальным, если не существует элемента  . Другими словами,   — минимальный элемент, если для любого элемента   либо  , либо  , либо   и   несравнимы. Элемент   называется наименьшим, если для любого элемента   имеет место неравенство  . Очевидно, всякий наименьший элемент является также минимальным, но обратное в общем случае неверно: минимальный элемент   может и не быть наименьшим, если существуют элементы  , не сравнимые с  .

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

Аналогично вводятся понятия максимального и наибольшего элементов.

Верхние и нижние грани

править

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

Любой элемент, больший, чем некоторая верхняя грань  , также будет верхней гранью  . А любой элемент, меньший, чем некоторая нижняя грань  , также будет нижней гранью  . Эти соображения ведут к введению понятий наименьшей верхней грани и наибольшей нижней грани.

Верхнее и нижнее множество

править
 
Элементы верхнего множества   отмечены зелёным

Для элемента   частично упорядоченного множества   верхним множеством называется множество   всех элементов, которым   предшествует ( ).

Двойственным образом определяется нижнее множество, как множество всех элементов, предшествующих заданному:  .

Условия обрыва цепей

править

Частично упорядоченное множество   называется удовлетворяющим условию обрыва строго возрастающих цепей, если не существует бесконечной строго возрастающей последовательности  . Это условие эквивалентно условию стабилизации нестрого возрастающих цепей: любая нестрого   возрастающая последовательность его элементов стабилизируется. То есть, для любой последовательности вида

 

существует натуральное   такое что

 

Аналогичным образом определяется для убывающих цепей, тогда очевидно,   удовлетворяет условию обрыва убывающих цепей, тогда и только тогда, когда любая нестрого убывающая последовательность его элементов стабилизируется. Эти понятия часто используются в общей алгебре — см., например, нётерово кольцо, артиново кольцо.

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

править

Тривиально упорядоченные множества

править

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

 

Тривиальный порядок есть наименьший по включению частичный порядок, который можно задать на множестве.

Строгий тривиальный порядок определяется так:

 

Другими словами, строгий тривиальный порядок — пустое бинарное отношение.

Тривиальное упорядоченное множество (антицепь) — частично упорядоченное множество  , где   — тривиальный порядок на  .[4][5]

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

править

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

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

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

В линейно упорядоченном множестве понятия наименьшего и минимального, а также наибольшего и максимального, совпадают.

Вполне упорядоченные множества

править

Линейно упорядоченное множество называется вполне упорядоченным, если каждое его непустое подмножество имеет наименьший элемент[7]. Такой порядок на множестве называется полным порядком, в контексте, где его невозможно спутать с полным порядком в смысле полных частично упорядоченных множеств.

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

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

Полное частично упорядоченное множество

править

Полное частично упорядоченное множество — частично упорядоченное множество, у которого есть дно — единственный элемент, который предшествует любому другому элементу и у каждого направленного подмножества которого есть точная верхняя граница[8]. Полные частично упорядоченные множества применяются в λ-исчислении и информатике, в частности, на них вводится топология Скотта, на основе которой строится непротиворечивая модель λ-исчисления и денотационная семантика[англ.]. Специальным случаем полного частично упорядоченного множества является полная решётка — если любое подмножество, не обязательно направленное, имеет точную верхнюю грань, то оно оказывается полной решёткой.

Упорядоченное множество   тогда и только тогда является полным частично упорядоченным, когда каждая функция  , монотонная относительно порядка ( ) обладает хотя бы одной неподвижной точкой:  .

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

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

править

К числу фундаментальных теорем о частично упорядоченных множествах относятся принцип максимума Хаусдорфа и лемма Куратовского — Цорна. Каждая из этих теорем эквивалентна аксиоме выбора.

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

править

Каждое частично упорядоченное множество (и каждый предпорядок) можно рассматривать как категорию, в которой каждое множество морфизмов   состоит не более чем из одного элемента. Например, эту категорию можно определить так:  , если AB (и пустое множество в противном случае); правило композиции морфизмов: (y, z)∘(x, y) = (x, z). Каждая категория-предпорядок эквивалентна частично упорядоченному множеству.

Функтор из категории-частично упорядоченного множества (то есть диаграмма, категория индексов которой является частично упорядоченным множеством) — это коммутативная диаграмма.

Примечания

править
  1. Колмогоров, 2004, с. 36.
  2. Александров, 1977, с. 78.
  3. Harzheim, 2005, с. 85.
  4. Trivially ordered set (англ.). https://encyclopediaofmath.org/. Дата обращения: 11 апреля 2024. Архивировано 9 апреля 2024 года.
  5. Anti-chain (англ.). https://encyclopediaofmath.org/. Дата обращения: 11 апреля 2024. Архивировано 28 ноября 2023 года.
  6. Колмогоров, 2004, с. 38.
  7. Колмогоров, 2004, с. 40.
  8. Барендрегт, 1985, с. 23.

Литература

править
  • Александров П. С. Введение в теорию множеств и общую топологию. — М.: Наука, 1977. — 368 с.
  • Барендрегт, Хенк. Ламбда-исчисление. Его синтаксис и семантика = The Lambda Calculus. Its syntax and semantics. — М.: Мир, 1985. — 606 с. — 4800 экз.
  • Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. — 7-е изд. — М.: Физматлит, 2004. — 572 с. — ISBN 5-9221-0266-4.
  • Хаусдорф Ф. Теория множеств. — 4-е изд. — М.: УРСС, 2007. — 304 с. — ISBN 978-5-382-00127-2.
  • Гуров С.И. Булевы алгебры, упорядоченные множества, решетки: Определения, свойства, примеры. — 2-е изд. — М.: Либроком, 2013. — 352 с. — ISBN 978-5-397-03899-7.
  • Harzheim E. Ordered Sets (англ.). — Springer, 2005. — ISBN 9789810235895.

См. также

править