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

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

Содержание 1 Определение и примеры 1.1 Терминология и обозначения 1.2 Строгий и нестрогий порядок 1.3 Примеры 2 Связанные определения 2.1 Несравнимые элементы 2.2 Минимальный/максимальный и наименьший/наибольший элементы 2.3 Верхние и нижние грани 2.4 Верхнее и нижнее множество 3 Специальные типы частично упорядоченных множеств 3.1 Линейно упорядоченные множества 3.2 Вполне упорядоченные множества 3.3 Полное частично упорядоченное множество 4 Теоремы о частично упорядоченных множествах 5 Примечания 6 Литература 7 См. также

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

• Множество действительных чисел частично упорядочено по отношению «меньше либо равно» — .

• Пусть  — множество всех действительнозначных функций, определенных на отрезке , то есть функций вида

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

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

• Множество всех натуральных чисел частично упорядочено по отношению делимости .

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

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

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

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

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

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

Элемент называется минимальным (англ. minimal element), если не существует элемента . Другими словами,  — минимальный элемент, если для любого элемента либо , либо , либо и несравнимы. Элемент называется наименьшим (англ. least element, lower bound (opp. upper bound)), если для любого элемента имеет место неравенство . Очевидно, всякий наименьший элемент является также минимальным, но обратное в общем случае неверно: минимальный элемент может и не быть наименьшим, если существуют элементы , не сравнимые с .

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

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

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

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

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

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

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

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

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

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

Пусть  — частично упорядоченное множество. Если в любые два элемента сравнимы, то множество называется линейно упорядоченным (англ. linearly ordered set). Линейно упорядоченное множество также называют совершенно упорядоченным (англ. totally ordered set), или просто, упорядоченным множеством^[3]. Таким образом, в линейно упорядоченном множество для любых двух элементов и имеет место одно и только одно из соотношений: либо , либо , либо .

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

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

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

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

Линейно упорядоченное множество называется вполне упорядоченным (англ. well-ordered), если каждое его непустое подмножество имеет наименьший элемент^[4]. Такой порядок на множестве называется полным порядком (англ. well-order, в контексте, где его невозможно спутать с полным порядком в смысле полных частично упорядоченных множеств, англ. complete order).

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

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

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

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

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

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

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

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

Примечания

Литература

• Александров П. С. Введение в теорию множеств и общую топологию. — М.: Наука, 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

См. также

• Решётка
• Порядковое число
• Предпорядок