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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Определение и примеры[править | править вики-текст]

Порядком, или частичным порядком, на множестве M называется бинарное отношение \varphi на M (определяемое некоторым множеством  R_{\varphi} \subset M \times M ), удовлетворяющее следующим условиям[1]:

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

Терминология и обозначения[править | править вики-текст]

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

Если a \leqslant b и a \neq b, то пишут a < b, и говорят, что a меньше b, или что a строго подчинен b.

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

Строгий и нестрогий порядок[править | править вики-текст]

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

\forall a \; \neg (a \varphi a)

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

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

a < b \; \overset{\mathrm{def}}{\Longleftrightarrow} \; (a \leqslant b) \wedge (a \neq b)

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

a \leqslant b \; \overset{\mathrm{def}}{\Longleftrightarrow} \; (a < b) \vee (a = b)

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

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

Примеры[править | править вики-текст]

Подмножества {x, y, z}, упорядоченные отношением включения
  • Пусть M — множество всех вещественнозначных функций, определенных на отрезке [a,b], то есть функций вида

f \colon [a,b] \to \mathbb{R}

Введём отношение порядка \leqslant на M следующим образом: f \leqslant g, если для всех x \in [a,b] выполнено неравенство f(x) \leqslant g(x). Очевидно, введенное отношение в самом деле является отношением частичного порядка.

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

Связанные определения[править | править вики-текст]

Несравнимые элементы[править | править вики-текст]

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


a < b, \qquad a=b, \qquad b<a

В случае, если a и b — элементы произвольного частично упорядоченного множества, то существует четвёртая логическая возможность: не выполнено ни одно из указанных трех соотношений. В этом случае элементы a и b называются несравнимыми. Например, если M — множество действительнозначных функций на отрезке [0,1], то элементы f(x) = x и g(x) = 1-x будут несравнимы. Возможность существования несравнимых элементов объясняет смысл термина «частично упорядоченное множество».

Минимальный/максимальный и наименьший/наибольший элементы[править | править вики-текст]

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

Элемент a \in M называется минимальным, если не существует элемента b < a. Другими словами, a — минимальный элемент, если для любого элемента b \in M либо b>a, либо b=a, либо b и a несравнимы. Элемент a называется наименьшим, если для любого элемента b \in M имеет место неравенство b \geqslant a. Очевидно, всякий наименьший элемент является также минимальным, но обратное в общем случае неверно: минимальный элемент a может и не быть наименьшим, если существуют элементы b, не сравнимые с a.

Очевидно, что если в множестве существует наименьший элемент, то он единственен. А вот минимальных элементов может быть несколько. В качестве примера рассмотрим множество \mathbb{N}\setminus \{ 1 \} = \{ 2, 3, \ldots \} натуральных чисел без единицы, упорядоченное по отношению делимости \mid. Здесь минимальными элементами будут простые числа, а вот наименьшего элемента не существует.

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

Верхние и нижние грани[править | править вики-текст]

Пусть A — подмножество частично упорядоченного множества \langle M, \leqslant\rangle. Элемент u \in M называется верхней гранью A, если любой элемент a \in A не превосходит u. Аналогично вводится понятие нижней грани множества A.

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

Верхнее и нижнее множество[править | править вики-текст]

Элементы верхнего множества 2^{\{1,2,3,4\}} \uparrow \{1\} отмечены зелёным

Для элемента m частично упорядоченного множества \langle M, \leqslant\rangle верхним множеством называется множество M \uparrow m всех элементов, которым m предшествует (\{ x \in M \mid m \leqslant x\}).

Двойственным образом определяется нижнее множество, как множество всех элементов, предшествующих заданному: M \downarrow m \stackrel{\mathrm{def}}{ = } \{ x \in M \mid x \leqslant m\}.

Условия обрыва цепей[править | править вики-текст]

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

a_1 \,\leqslant\, a_2 \,\leqslant\, a_3 \,\leqslant\, \cdots

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

a_n = a_{n+1} = a_{n+2} = \cdots.

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

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

Линейно упорядоченные множества[править | править вики-текст]

Пусть \langle M, \leqslant\rangle — частично упорядоченное множество. Если в M любые два элемента сравнимы, то множество M называется линейно упорядоченным. Линейно упорядоченное множество также называют совершенно упорядоченным, или просто, упорядоченным множеством[3]. Таким образом, в линейно упорядоченном множество для любых двух элементов a и b имеет место одно и только одно из соотношений: либо a<b, либо a=b, либо b<a.

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

Из приведенных выше примеров частично упорядоченных множеств только множество действительных чисел является линейно упорядоченным. Множество действительнозначных функций на отрезке [a, b] (при условии a<b), булеан \mathcal{P}(M) (при |M|\geqslant 2), натуральные числа с отношением делимости — не являются линейно упорядоченными.

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

Вполне упорядоченные множества[править | править вики-текст]

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

Классический пример вполне упорядоченного множества — множество натуральных чисел \mathbb{N}. Утверждение о том, что любое непустое подмножество \mathbb{N} содержит наименьший элемент, равносильно принципу математической индукции. В качестве примера линейно упорядоченного, но не вполне упорядоченного множества можно привести множество неотрицательных чисел, упорядоченное естественным образом \mathbb{R}_{+} = \{ x: x \geqslant 0\}. Действительно, его подмножество \{x: x > 1\} не имеет наименьшего элемента.

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

Полное частично упорядоченное множество[править | править вики-текст]

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

Упорядоченное множество M тогда и только тогда является полным частично упорядоченным, когда каждая функция f \colon M\rightarrow M, монотонная относительно порядка (a \leqslant b \Rightarrow f(a) \leqslant f(b)) обладает хотя бы одной неподвижной точкой: \exists _{x \in M} f(x)=x.

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

Теоремы о частично упорядоченных множествах[править | править вики-текст]

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

В теории категорий[править | править вики-текст]

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

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

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

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

См. также[править | править вики-текст]