Отношения порядка. Упорядоченные множества. Решетки

Пусть Æ. Отношение  называется отношением порядка (кратко: порядком) на множестве А, если оно рефлексивно, транзитивно и антисимметрично.

Для обозначения порядка r на множестве А часто используется инфиксный знак £, т.е. вместо  пишут . Запись  читается «х содержится в у», или «х включается в у», или «х не больше у», или
«х меньше или равен у».

Пара (А,£), где Æ, £ – порядок на А, называется упорядоченным множеством (кратко: у-множеством).

Пример 1.15.

1. (N,£) – у-множество.

2. Пусть Æ. Пара  является у-множеством (см. теоре-
му 1.1).

3. (N, |) – у-множество (отношение | делимости без остатка рассматривалось в примере 1.6).

Имеем:

а) ("хÎN)(x|x);

б) ("х, у, zÎN) (x|y & y|zÞx|z);

в) ("х, уÎN) (x|y & y|хÞх=у).

У-множество (А, £) называется линейно упорядоченным, или цепью, если порядок £ обладает свойством полноты, т.е.

("x,yÎА)(x£y Ú y£x).

Пусть (А, £) – произвольное у-множество.

Если x,yÎА и x£y или y£x, то элементы х и у называются сравнимыми, а в противном случае – несравнимыми.

Если х не сравним с у, то пишут х||y.

Таким образом, цепь – это у-множество, в котором любые два элемента сравнимы.

Примеры цепей: (N,£), (Z,£), (R,£). У-множество (Р(А), Í) при |А|³2 не будет цепью. Не будет цепью и у-множество (N, |), так как, например, 2||3.

Пусть (А, £) – у-множество, аÎА. Убывающей цепью, начинающейся с а, называется последовательность вида а>a₁>a₂>…>a_n>… (Запись х>y означает, что у£х и у¹х.)

Пусть (А, £) – конечное у-множество (т.е. здесь А – конечное множество). Длиной убывающей цепи в (А,£) называется уменьшенное на 1 количество элементов в ней. Высотой h(a) элемента аÎА в у-множестве (А, £) называется наибольшая из длин убывающих цепей, начинающихся с а.

Пусть (А, £) – у-множество, а,bÎА.

Говорят, что а – нижний сосед для b, если

а<b и ^Ø(($xÎА)(a<x<b))

(запись a<b означает, что a£b и a¹b).

Пусть (А, £) – конечное у-множество и n – наибольшая из высот его элементов. Изобразим n+1 горизонтальную линию, нумеруя их снизу вверх числами 0,1,…,n. На этих горизонтальных линиях произвольно разместим элементы множества А в соответствии с их высотами. При этом элементы изобразим точками или кружками. Далее, двигаясь снизу вверх, каждый элемент соединим прямолинейными отрезками с его нижними соседями. После просмотра всех элементов горизонтали убираются, а оставшаяся схема называется диаграммой у-множества А.

Пример 1.16.

1. Пусть N₅:={1,2,3,4,5}. Рассмотрим у-множество (N₅, £). В этом
у-множестве  при всех nÎN₅.

Диаграмма у-множества (N₅, £) имеет вид

2. Построим диаграмму у-множества (N₈, |), где N₈:={1,2,3,4,5,6,7,8}.

Имеем

(n M m читается “n делится на m” и означает, что m|n).

Диаграмма у-множества (N₈, |) имеет вид

3. Пусть А={1,2}. Тогда Р(А)={Æ,{1},{2},{1,2}=A}. Диаграмма
у-множества (Р(А),Í) имеет вид

4. Пусть А={1,2,3}. Тогда Р(А)= {Æ,{1},{2},{3},{1,2},{1,3},{2,3}, {1,2,3}=A}. Диаграмма у-множества (Р(А),Í) имеет вид

5. Пусть А={1,2,3,4,12}. Диаграмма у-множества (А,|) имеет вид

6. Пусть А={2,4,6,7,10,11,49,60}. Диаграмма у-множества (А,|) имеет вид

Пусть (А, £) – у-множество, аÎА. Элемент а называется:

1) наибольшим элементом у-множества (А, £), если ("хÎА)(х£а);

2) наименьшим элементом у-множества (А, £), если ("хÎА)(а£х).

Пусть (А, £) – у-множество, ВÍА, аÎА. Элемент а называется:

1) верхней гранью подмножества В, если ("хÎВ)(х£а);

2) нижней гранью подмножества В, если ("хÎВ)(а£х).

Совокупность всех верхних (нижних) граней подмножества ВÍА обозначается В^D(В^Ñ).

Точной верхней гранью подмножества В в у-множестве (А, £) называется наименьший элемент у-множества (В^D,£) (если он существует). Этот элемент обозначается Sup B («супремум В»).

Точной нижней гранью подмножества В в у-множестве (А, £) называется наибольший элемент у-множества (В^Ñ,£) (если он существует). Этот элемент обозначается Inf B («инфимум В»).

У-множество (А, £) называется решеткой, если любое его двухэлементое подмножество {a,b} имеет точную верхнюю грань sup(a,b) и точную нижнюю грань inf(a,b).

Пример 1.17.

1. У-множества (N, £), (Z, £), (R, £) являются решетками, при этом sup(x,y)=max(x,y), inf(x,y)=min(x,y).

2. У-множество (Р(А),Í) является решеткой. При этом sup(X,У)=XÈУ, inf(X,У)=XÇУ для любых X,УÍА.

3. У-множество (А, £), где А={a,b,c,d,f}, имеющее диаграмму вида

не является решеткой, так как, например, {a, b}^D={c, d, f}, но у-множество ({c, d, f},£) не имеет наименьшего элемента. Следовательно, множество
{a, b} не имеет точной верхней грани. Аналогично, множество {c,d} не имеет точной нижней грани. Множество {a,b} также не имеет точной нижней грани, так как вообще .

Теорема 1.9. Конечное упорядоченное множество (A, £) тогда и только тогда является решеткой, когда:

1) оно имеет наибольший элемент;

2) для любых двух его элементов существует точная нижняя грань.