Изучение порядковой структуры

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

Реализация

Изложим апробированную нами схему изучения темы.

Сразу заметим, что мы приводим минимум понятий и фактов - только самые необходимые. Характерные методы и рассуждения демонстрируем на доказательстве нескольких теорем. Изложение сопровождаем модельными примерами и специально подобранными упражнениями.

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

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

Основные понятия

Введем важнейшие понятия теории упорядоченных множеств.

Определение 1. Упорядоченным множеством называется непустое множество X вместе с заданным на нем бинарным отношением порядка <, которое по определению (для любых a, b, c е X):

1) рефлексивно: a < a;

2) транзитивно: a < b < c y a < c;

3) антисимметрично: a < b < a y a = b.

Более общим понятием служит отношение

квазипорядка, определяемое как рефлексивное транзитивное бинарное отношение на множестве.

Пусть (X, <) - произвольное упорядоченное множество. Элементы a и b упорядоченного множества X называются сравнимыми, если a < b, a = b или b < a, и несравнимыми в противном случае. Знаки <, > и > имеют обычный смысл. Упорядоченное множество (X, >) двойственно к упорядоченному множеству (X, <), которое в свою очередь двойственно к (X, >).

Определение 2. Упорядоченное множество называется линейно упорядоченным, или цепью, если любые два его элемента сравнимы. Если любые два * элемента упорядоченного множества несравнимы, то оно называется антицепью.

Элемент a е X называется наибольшим (наименьшим), если x < a (a < x) для всех элементов x е X. Элемент a е X называется максимальным (минимальным), когда в X нет элементов x > a (x < a).

Возьмем непустое подмножество Y в X. Элемент x е X называется верхней гранью (нижней гранью) множества Y, если у < x (x < у) для любого у е Y. Если множество всех верхних граней множества Y непусто и имеет наименьший элемент, то этот элемент называется точной верхней гранью множества Y и обозначается sup Y. Двойственным образом определяется понятие точной нижней грани inf Y.

Мы видим, что в основополагающих моделях теории упорядоченных множеств, приведенных в таблице, операции inf и sup дают классические математические операции. Они играют роль «материала» для представлений, реализации произвольных упорядоченных множеств. Так, любое упорядоченное множество X (порядково) изоморфно некоторому подмножеству (с индуцированным порядком) булеана B(X) с сохранением всех имеющихся в X точных верхних граней (либо точных нижних граней).

Определение 3. Отображение f: X^Y упорядоченных множеств называется изотопным, если a < b влечет f(a) < f(b) для любых a, b е X. Изо- тонная биекция f: X^ Y упорядоченных множеств называется их (порядковым) изоморфизмом, если обратное отображение f-1 также изотонно. Упорядоченные множества, между которыми существует изоморфизм, называются (порядково) изоморфными.

Говорят, что элемент b е X покрывает элемент a е X, если a < b и в X нет элементов x, удовлетворяющих неравенствам a < x < b (находящихся между a и b).

Конечные упорядоченные множества удобно изображать диаграммами Хассе. Элементы конечного упорядоченного множества X изображаются точками «вертикальной» плоскости. Если элемент a покрыт элементом b, то соединяем точку a с точкой b отрезком, идущим вверх. Полученный при этом граф и называется диаграммой Хассе упорядоченного множества X.

Диаграмму Хассе любого конечного упорядоченного множества X можно построить следующим образом. Берем в X множество X1 всех минимальных элементов и изображаем их точками, расположенными горизонтально (это первый уровень). Затем в упорядоченном множестве XXX1 снова рассматриваем множество X2 всевозможных минимальных элементов, помещая их на второй горизонтальный уровень над первым. Далее повторяем процедуру: берем упорядоченное множество XX(X1UX2) и т. д. В результате упорядоченное множество X разбивается на уровни X1, X2, ., Xn, являющиеся антицепями. Элемент a е X находится на k-м уровне (2 < k < п) тогда и только тогда, когда начинающиеся с a убывающие цепи в X имеют наибольшее число элементов, равное k. Элементы последнего уровня Xn максимальны, но не обязаны исчерпывать множество всех максимальных элементов в X.