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

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

Построим диаграммы Хассе упорядоченных множеств, имеющих п < 4 элементов (см. рис. 1).

Длиной конечной цепи X назовем число |X| ее элементов. Длиной I(X) конечного упорядоченного множества X называется наибольшая из длин его цепей. Наибольшее число элементов антицепей конечного упорядоченного множества X называется его шириной w(X).

Теорема 1. Для любого конечного упорядоченного множества X справедливо неравенство |X| < /(X) • w(X).

Доказательство. Рассмотрим диаграмму Хассе конечного упорядоченного множества X. Ясно, что число уровней диаграммы равно /(X). Каждый уровень является антицепью в X, поэтому число его элементов не превосходит ширины w(X).

Поскольку различные (попарно не пересекающиеся) уровни в объединении дают все множество X, то получаем искомое неравенство.

Применим эту теорему к решению одной задачи XIII Московской математической олимпиады.

Задача. Пусть числа 1, 2, 3, ., 101 выписаны в ряд в произвольном порядке. Докажите, что в данной последовательности можно вычеркнуть 90 чисел так, чтобы оставшиеся 11 чисел были расположены в порядке возрастания либо в порядке убывания.

Решение. На множестве X = {1, 2, 3, ., 101} введем новый порядок, соответствующий данному расположению чисел. Положим mрn в том и только том случае, когда m = n или m < n и m расположено раньше n. В результате получим упорядоченное множество (X, р>. В нем возрастающие подпоследовательности служат цепями, а убывающие подпоследовательности - антицепями. По теореме 1 /(X) • w(X) > |X| = 101, откуда /(X) > 11 или w(X) > 11. Что и требовалось доказать.

Имеет место принцип двойственности для упорядоченных множеств: если некоторое предложение об упорядоченных множествах верно для всех упорядоченных множеств, то верно и двойственное предложение, получающееся из данного заменой отношения # на отношение > и обратно.

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

а) (B(M)\{i, M}, с> при |M| > 2; б) (N\{1}, | >;

в) ((0, 1], #>.

Упражнение 2. Постройте диаграмму Хассе упорядоченного множества всех натуральных делителей числа 36 по отношению делимости.

Упражнение 3. Сколько различных отношений порядка можно задать на n-элементном множестве при n # 4?

Упражнение 4. Приведите примеры двойственных понятий и двойственных теорем.

Упражнение 5. Что такое строгий порядок < на множестве X? Дайте его абстрактную характеризацию.

Упражнение 6. Пусть р - отношение квазипорядка на множестве X. Для произвольных элементов а, Ъ є X положим а~Ъ, если арЪ и Ъра. Покажите, что отношение ~ является эквивалентностью на X. На фактор-множестве X/~ задается отношение порядка # по формуле: a <t>] арЪ для любых а, Ъ є X. Проверьте корректность этого утверждения.

Упражнение 7. Докажите, что любое изотон- ное взаимно однозначное отображение

а) конечного упорядоченного множества, б) цепи на себя будет порядковым изоморфизмом.Замечание.

С точностью до порядкового изоморфизма существуют 63 пятиэлементных упорядоченных множества (нарисуйте их диаграммы Хассе), 318 - шестиэлементных, 2045 - семиэлементных.

Число упорядочений п-элемент- ного множества равно: 3 при п = 2; 19 при п = 3; 219 при п = 4; 4321 при п = 5, 130023 при п = 6; 6129859 при п = 7.

4. Решетки

Среди упорядоченных множеств выделяются решетки.

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

Если из m-элементной решетки (т > 3) выбросить наименьший и наибольший элементы, то получим (т-2)-элементное упорядоченное множество. Таким образом можно построить все конечные решетки.

Приведем диаграммы Хассе всех решеток мощности т = 4 и 5. (При т < 3 получаем одно-, двух- и трехэлементные цепи.) (Рис. 2.)

Шестиэлементные решетки получаются из четырехэлементных упорядоченных множеств добавлением «новых» наименьшего и наибольшего элементов. При этом мы имеем 15 решеток из 16 «возможных». Дело в том, что выделенное выше четырехэлементное упорядоченное множество дает изображенное справа упорядоченное множество X, не являющееся решеткой. Его элементы a, b не обладают точной верхней гранью в X, так как множество их верхних граней {c, d, 1} не имеет наименьшего элемента (рис. 3).