Главная
Частично упорядоченное множество — математическое понятие, которое формализует интуитивные идеи упорядочения, расположения элементов в определённой последовательности. Неформально, множество частично упорядочено, если указано, какие элементы следуют за какими (какие элементы больше каких). В общем случае может оказаться так, что некоторые пары элементов не связаны отношением «следует за».
В качестве абстрактного примера можно привести совокупность подмножеств множества из трёх элементов { x , y , z } {displaystyle {x,y,z}} (булеан данного множества), упорядоченную по отношению включения.
Определение и примеры
Отношением порядка, или частичным порядком, на множестве M {displaystyle M} называется бинарное отношение φ {displaystyle varphi } на M {displaystyle M} (определяемое некоторым множеством R φ ⊂ M × M {displaystyle R_{varphi }subset M imes M} ), удовлетворяющее следующим условиям:
- Рефлексивность: ∀ a ( a φ a ) {displaystyle forall a;(avarphi a)}
- Транзитивность: ∀ a , b , c ( a φ b ) ∧ ( b φ c ) ⇒ a φ c {displaystyle forall a,b,c;(avarphi b)wedge (bvarphi c)Rightarrow avarphi c}
- Антисимметричность: ∀ a , b ( a φ b ) ∧ ( b φ a ) ⇒ a = b {displaystyle forall a,b;(avarphi b)wedge (bvarphi a)Rightarrow a=b}
Множество M {displaystyle M} , на котором задано отношение частичного порядка, называется частично упорядоченным. Если быть совсем точным, то частично упорядоченным множеством называется пара ⟨ M , φ ⟩ {displaystyle langle M,varphi angle } , где M {displaystyle M} — множество, а φ {displaystyle varphi } — отношение частичного порядка на M {displaystyle M} .
Терминология и обозначения
Отношение частичного порядка обычно обозначают символом ⩽ {displaystyle leqslant } , по аналогии с отношением «меньше либо равно» на множестве вещественных чисел. При этом, если a ⩽ b {displaystyle aleqslant b} , то говорят, что элемент a {displaystyle a} не превосходит b {displaystyle b} , или что a {displaystyle a} подчинён b {displaystyle b} .
Если a ⩽ b {displaystyle aleqslant b} и a ≠ b {displaystyle a eq b} , то пишут a < b {displaystyle a<b} , и говорят, что a {displaystyle a} меньше b {displaystyle b} , или что a {displaystyle a} строго подчинен b {displaystyle b} .
Иногда, чтобы отличить произвольный порядок на некотором множестве от известного отношения «меньше либо равно» на множестве действительных чисел, вместо ⩽ {displaystyle leqslant } и < {displaystyle <} используют специальные символы ≼ {displaystyle preccurlyeq } и ≺ {displaystyle prec } соответственно.
Строгий и нестрогий порядок
Отношение, удовлетворяющее условиям рефлексивности, транзитивности и антисимметричности, также называют нестрогим, или рефлексивным порядком. Если условие рефлексивности заменить на условие антирефлексивности (тогда свойство антисимметричности заменится на асимметричность):
∀ a ¬ ( a φ a ) {displaystyle forall a; eg (avarphi a)}то получим определение строгого, или антирефлексивного порядка.
Если ⩽ {displaystyle leqslant } — нестрогий порядок на множестве M {displaystyle M} , то отношение < {displaystyle <} , определяемое как:
a < b ⟺ d e f ( a ⩽ b ) ∧ ( a ≠ b ) {displaystyle a<b;{overset {mathrm {def} }{Longleftrightarrow }};(aleqslant b)wedge (a eq b)}является строгим порядком на M {displaystyle M} . Обратно, если < {displaystyle <} — строгий порядок, то отношение ⩽ {displaystyle leqslant } , определенное как
a ⩽ b ⟺ d e f ( a < b ) ∨ ( a = b ) {displaystyle aleqslant b;{overset {mathrm {def} }{Longleftrightarrow }};(a<b)vee (a=b)}является нестрогим порядком.
Поэтому всё равно — задать на множестве нестрогий порядок, или строгий порядок. В результате получится одна и та же структура. Разница только в терминологии и обозначениях.
Интервал
Для 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. Например, открытый интервал (1,2) для целых чисел пуст, поскольку нет целых чисел i, таких что 1 < i < 2.
Иногда определение расширяется, позволяя a > b. В этом случае интервал пуст.
Полуоткрытые интервалы [a,b) и (a,b] определяются аналогичным образом.
Частично упорядоченное множество является локально конечным, если любой интервал конечен. Например, целые числа локально конечны по их естественному упорядочению. Лексикографический порядок на прямом произведении ℕ×ℕ не является локально конечным, поскольку, например, (1,2)≤(1,3)≤(1,4)≤(1,5)≤...≤(2,1).
Концепцию интервала в частично упорядоченных множествах не следует путать со специфичным классом частичных упорядоченных множеств, известных как интервальные порядки.
Примеры
- Множество вещественных чисел R {displaystyle mathbb {R} } частично упорядочено по отношению «меньше либо равно» — ⩽ {displaystyle leqslant } .
- Пусть M {displaystyle M} — множество всех вещественнозначных функций, определенных на отрезке [ a , b ] {displaystyle [a,b]} , то есть функций вида
Введём отношение порядка ⩽ {displaystyle leqslant } на M {displaystyle M} следующим образом: f ⩽ g {displaystyle fleqslant g} , если для всех x ∈ [ a , b ] {displaystyle xin [a,b]} выполнено неравенство f ( x ) ⩽ g ( x ) {displaystyle f(x)leqslant g(x)} . Очевидно, введенное отношение в самом деле является отношением частичного порядка.
- Пусть M {displaystyle M} — некоторое множество. Множество P ( M ) {displaystyle {mathcal {P}}(M)} всех подмножеств M {displaystyle M} (так называемый булеан), частично упорядочено по включению M ⊆ N {displaystyle Msubseteq N} .
- Множество всех натуральных чисел N {displaystyle mathbb {N} } частично упорядочено по отношению делимости m ∣ n {displaystyle mmid n} .
Связанные определения
Несравнимые элементы
Если a {displaystyle a} и b {displaystyle b} — действительные числа, то имеет место только одно из следующих соотношений:
a < b , a = b , b < a {displaystyle a<b,qquad a=b,qquad b<a}В случае, если a {displaystyle a} и b {displaystyle b} — элементы произвольного частично упорядоченного множества, то существует четвёртая логическая возможность: не выполнено ни одно из указанных трех соотношений. В этом случае элементы a {displaystyle a} и b {displaystyle b} называются несравнимыми. Например, если M {displaystyle M} — множество действительнозначных функций на отрезке [ 0 , 1 ] {displaystyle [0,1]} , то элементы f ( x ) = x {displaystyle f(x)=x} и g ( x ) = 1 − x {displaystyle g(x)=1-x} будут несравнимы. Возможность существования несравнимых элементов объясняет смысл термина «частично упорядоченное множество».
Минимальный/максимальный и наименьший/наибольший элементы
Из-за того, что в частично упорядоченном множестве могут быть пары несравнимых элементов, вводятся два различных определения: минимального элемента и наименьшего элемента.
Элемент a ∈ M {displaystyle ain M} называется минимальным, если не существует элемента b < a {displaystyle b<a} . Другими словами, a {displaystyle a} — минимальный элемент, если для любого элемента b ∈ M {displaystyle bin M} либо b > a {displaystyle b>a} , либо b = a {displaystyle b=a} , либо b {displaystyle b} и a {displaystyle a} несравнимы. Элемент a {displaystyle a} называется наименьшим, если для любого элемента b ∈ M {displaystyle bin M} имеет место неравенство b ⩾ a {displaystyle bgeqslant a} . Очевидно, всякий наименьший элемент является также минимальным, но обратное в общем случае неверно: минимальный элемент a {displaystyle a} может и не быть наименьшим, если существуют элементы b {displaystyle b} , не сравнимые с a {displaystyle a} .
Очевидно, что если в множестве существует наименьший элемент, то он единственен. А вот минимальных элементов может быть несколько. В качестве примера рассмотрим множество N ∖ { 1 } = { 2 , 3 , … } {displaystyle mathbb {N} setminus {1}={2,3,ldots }} натуральных чисел без единицы, упорядоченное по отношению делимости ∣ {displaystyle mid } . Здесь минимальными элементами будут простые числа, а вот наименьшего элемента не существует.
Аналогично вводятся понятия максимального и наибольшего элементов.
Верхние и нижние грани
Пусть A {displaystyle A} — подмножество частично упорядоченного множества ⟨ M , ⩽ ⟩ {displaystyle langle M,leqslant angle } . Элемент u ∈ M {displaystyle uin M} называется верхней гранью A {displaystyle A} , если любой элемент a ∈ A {displaystyle ain A} не превосходит u {displaystyle u} . Аналогично вводится понятие нижней грани множества A {displaystyle A} .
Любой элемент, больший, чем некоторая верхняя грань A {displaystyle A} , также будет верхней гранью A {displaystyle A} . А любой элемент, меньший, чем некоторая нижняя грань A {displaystyle A} , также будет нижней гранью A {displaystyle A} . Эти соображения ведут к введению понятий наименьшей верхней грани и наибольшей нижней грани.
Верхнее и нижнее множество
Для элемента m {displaystyle m} частично упорядоченного множества ⟨ M , ⩽ ⟩ {displaystyle langle M,leqslant angle } верхним множеством называется множество M ↑ m {displaystyle Muparrow m} всех элементов, которым m {displaystyle m} предшествует ( { x ∈ M ∣ m ⩽ x } {displaystyle {xin Mmid mleqslant x}} ).
Двойственным образом определяется нижнее множество, как множество всех элементов, предшествующих заданному: M ↓ m = d e f { x ∈ M ∣ x ⩽ m } {displaystyle Mdownarrow m{stackrel {mathrm {def} }{=}}{xin Mmid xleqslant m}} .
Условия обрыва цепей
Частично упорядоченное множество M {displaystyle M} называется удовлетворяющим условию обрыва строго возрастающих цепей, если не существует бесконечной строго возрастающей последовательности ( a i < a i + 1 ) {displaystyle (a_{i},<,a_{i+1})} . Это условие эквивалентно условию стабилизации нестрого возрастающих цепей: любая нестрого ( a i ⩽ a i + 1 ) {displaystyle (a_{i},leqslant ,a_{i+1})} возрастающая последовательность его элементов стабилизируется. То есть, для любой последовательности вида
a 1 ⩽ a 2 ⩽ a 3 ⩽ ⋯ {displaystyle a_{1},leqslant ,a_{2},leqslant ,a_{3},leqslant ,cdots }существует натуральное n , {displaystyle n,} такое что
a n = a n + 1 = a n + 2 = ⋯ . {displaystyle a_{n}=a_{n+1}=a_{n+2}=cdots .}Аналогичным образом определяется для убывающих цепей, тогда очевидно, M {displaystyle M} удовлетворяет условию обрыва убывающих цепей, тогда и только тогда, когда любая нестрого убывающая последовательность его элементов стабилизируется. Эти понятия часто используются в общей алгебре — см., например, нётерово кольцо, артиново кольцо.
Специальные типы частично упорядоченных множеств
Линейно упорядоченные множества
Пусть ⟨ M , ⩽ ⟩ {displaystyle langle M,leqslant angle } — частично упорядоченное множество. Если в M {displaystyle M} любые два элемента сравнимы, то множество M {displaystyle M} называется линейно упорядоченным. Линейно упорядоченное множество также называют совершенно упорядоченным, или просто, упорядоченным множеством. Таким образом, в линейно упорядоченном множестве для любых двух элементов a {displaystyle a} и b {displaystyle b} имеет место одно и только одно из соотношений: либо a < b {displaystyle a<b} , либо a = b {displaystyle a=b} , либо b < a {displaystyle b<a} .
Также всякое линейно упорядоченное подмножество частично упорядоченного множества называют цепью, то есть цепь в частично упорядоченном множестве ⟨ M , ⩽ ⟩ {displaystyle langle M,leqslant angle } — такое его подмножество, в котором любые два элемента сравнимы.
Из приведенных выше примеров частично упорядоченных множеств только множество действительных чисел является линейно упорядоченным. Множество действительнозначных функций на отрезке [ a , b ] {displaystyle [a,b]} (при условии a < b {displaystyle a<b} ), булеан P ( M ) {displaystyle {mathcal {P}}(M)} (при | M | ⩾ 2 {displaystyle |M|geqslant 2} ), натуральные числа с отношением делимости — не являются линейно упорядоченными.
В линейно упорядоченном множестве понятия наименьшего и минимального, а также наибольшего и максимального, совпадают.
Вполне упорядоченные множества
Линейно упорядоченное множество называется вполне упорядоченным, если каждое его непустое подмножество имеет наименьший элемент. Такой порядок на множестве называется полным порядком, в контексте, где его невозможно спутать с полным порядком в смысле полных частично упорядоченных множеств.
Классический пример вполне упорядоченного множества — множество натуральных чисел N {displaystyle mathbb {N} } . Утверждение о том, что любое непустое подмножество N {displaystyle mathbb {N} } содержит наименьший элемент, равносильно принципу математической индукции. В качестве примера линейно упорядоченного, но не вполне упорядоченного множества можно привести множество неотрицательных чисел, упорядоченное естественным образом R + = { x : x ⩾ 0 } {displaystyle mathbb {R} _{+}={x:xgeqslant 0}} . Действительно, его подмножество { x : x > 1 } {displaystyle {x:x>1}} не имеет наименьшего элемента.
Вполне упорядоченные множества играют исключительно важную роль в общей теории множеств.
Полное частично упорядоченное множество
Полное частично упорядоченное множество — частично упорядоченное множество, у которого есть дно — единственный элемент, который предшествует любому другому элементу и у каждого направленного подмножества которого есть точная верхняя граница. Полные частично упорядоченные множества применяются в λ-исчислении и информатике, в частности, на них вводится топология Скотта, на основе которой строится непротиворечивая модель λ-исчисления и денотационная семантика. Специальным случаем полного частично упорядоченного множества является полная решётка — если любое подмножество, не обязательно направленное, имеет точную верхнюю грань, то оно оказывается полной решёткой.
Упорядоченное множество M {displaystyle M} тогда и только тогда является полным частично упорядоченным, когда каждая функция f : M → M {displaystyle fcolon M ightarrow M} , монотонная относительно порядка ( a ⩽ b ⇒ f ( a ) ⩽ f ( b ) {displaystyle aleqslant bRightarrow f(a)leqslant f(b)} ) обладает хотя бы одной неподвижной точкой: ∃ x ∈ M f ( x ) = x {displaystyle exists _{xin M}f(x)=x} .
Любое множество M {displaystyle M} можно превратить в полное частично упорядоченное выделением дна ⊥ {displaystyle ot } и определением порядка ⩽ {displaystyle leqslant } как ⊥ ⩽ m {displaystyle ot leqslant m} и m ⩽ m {displaystyle mleqslant m} для всех элементов m {displaystyle m} множества M {displaystyle M} .
Теоремы о частично упорядоченных множествах
К числу фундаментальных теорем о частично упорядоченных множествах относятся принцип максимума Хаусдорфа и лемма Куратовского — Цорна. Каждая из этих теорем эквивалентна аксиоме выбора.
В теории категорий
Каждое частично упорядоченное множество (и каждый предпорядок) можно рассматривать как категорию, в которой каждое множество морфизмов H o m ( A , B ) {displaystyle mathrm {Hom} (A,B)} состоит не более чем из одного элемента. Например, эту категорию можно определить так: H o m ( A , B ) = { ( A , B ) } {displaystyle mathrm {Hom} (A,B)={(A,B)}} , если A ≤ B (и пустое множество в противном случае); правило композиции морфизмов: (y, z)∘(x, y) = (x, z). Каждая категория-предпорядок эквивалентна частично упорядоченному множеству.
Функтор из категории-частично упорядоченного множества (то есть диаграмма, категория индексов которой является частично упорядоченным множеством) — это коммутативная диаграмма.