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

Если в упорядоченном множестве А любые два различных элемента несравнимы, то множество А называется антицепью.

Элемент аА называется наибольшим, если x а для xА. Понятие наименьшего элемента определяется аналогичным образом. Если наибольший и наименьший элементы существуют, то они единственны. Наибольший элемент обычно обозначают - 1, а наименьший - 0.

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

Упорядоченное множество называется конечным, если конечно множество его элементов. Конечное упорядоченное множество <A, ? > удобно изображать в виде графа, который можно построить следующим образом:

Ш элементы множества А изображаются точками;

Ш точки а и в соединяются ребром - идущим вверх отрезком, не обязательно вертикальным, если а<в и между ними нет других элементов из А;

Ш при этом все минимальные элементы А располагаются на одной горизонтали и образуют - первый уровень;

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

Ш еще выше идет третий уровень, состоящий из минимальных элементов множества, полученного удалением из А элементов второго и первого уровней, и т.д.

Заметим, что если а<в, то из точки а по ребрам, двигаясь вверх, можно добраться до точки в. Полученный граф назовем стандартным графом (диаграммой Хассе) упорядоченного множества А. Изоморфные упорядоченные множества имеют одинаковые стандартные графы, а неизоморфные - различные.

Приведем графы упорядоченных 4-х элементных множеств.

Следует обратить внимание на то, что из любой точки стандартного графа конечного упорядоченного множества можно по рёбрам спуститься на первый уровень, побывав на всех промежуточных уровнях. Т.е. среди стандартных графов не может быть такого, например, графа:

А должен быть такой

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

Шириной А называется наибольшее из чисел элементов антицепей в А. Ширина А будет не меньше числа элементов любого уровня этого графа.

Замечание: число элементов любого конечного упорядоченного множества не превосходит произведения его длины на ширину.

Пусть В - непустое подмножество упорядоченного множества А. Элемент аА называется верхней гранью для В, если ва для всех вВ. Точной верхней гранью В называется наименьший элемент множества всех верхних граней В в А, его обозначают sup B. Точная нижняя грань определяется аналогичным образом и обозначается inf B.

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

Любая конечная решётка обладает наибольшим и наименьшим элементами. Среди графов 5-ти элементных множеств, только пять решёток.

В нашей дипломной работе пойдёт речь ещё и прямом произведении конечных упорядоченных множествах. Поэтому объясним, что это такое.

Пусть <A,?> и <В,?> - конечные упорядоченные множества с одинаковым порядком, тогда их прямым произведением называется конечное упорядоченное множество , элементы которого - это всевозможные пары, состоящие из двух компонент,1-ая компонента принадлежит множеству А, а вторая - В. Порядок на определяется следующим образом:

(a,b)?(c,d)a?c и b?d).

§2.Определение размерности упорядоченного множества

Напомним, что такое цепь на примере диаграммы Хассе для конечного упорядоченного множества <A,>. Здесь порядок будет линейным.

Примером антицепи может служить множество:

Нелинейный порядок на конечном упорядоченном множестве А можно доупорядочить до различных линейных порядков на А.

Например, нелинейный порядок на А

можно доупорядочить до следующих линейных порядков:

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

Теорема 1. Любой нелинейный порядок ? на конечном упорядоченном множестве А можно продолжить до линейных порядков, дающих в пересечении исходный порядок ?.

Доказательство:

Возьмём произвольное конечное упорядоченное множество А с нелинейным порядком .

Рассмотрим 2 его произвольных элемента а и b.