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

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

Страница 4

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

Построим диаграммы Хассе упорядоченных множеств, имеющих п < 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).

Страницы: 1 2 3 4 5 6 7

Смотрите также:

Взаимодействие семьи и школы
Законодательство Российской Федерации (Закон "Об образовании", Концепция модернизации российского образования на период до 2010 года) значительно расширило функции семейного воспитания, предоставив родителям право выбора места и формы дошкольного, школьного и дополнительного образования. ...

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

Описание экспериментального обучения
Опытно-экспериментальная работа проводилась нами в начальной школе № 618 в 3 "А" и 3 "В" классах. В эксперименте принимали участие 45 учеников. 1. Выявление уровня орфографической грамотности учащихся в словах с непроверяемыми написаниями (констатирующий эксперимент) В ходе наше ...

Приёмы и методы запоминания

Приёмы и методы запоминания

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

Категории

Copyright © 2020 - All Rights Reserved - www.newlypedagog.ru