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

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

Страница 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

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

Возрастные особенности и характеристика воспитанности дошкольника
Дошкольный возраст — этап психического развития от 3 до 6–7 лет. Характеризуется тем, что ведущей деятельностью является игра. Имеет чрезвычайно важное значение для формирования личности ребенка. Выделяют три периода: младший дошкольный возраст (3–4 года), средний (4–5 лет) и старший (5–7 лет). В р ...

Доисторическая эпоха бессознательного умозаключения
Положение, которое человека занимает в природе, очень отличается от того, о чем поэты и философы мечтали когда-то. Те прекрасные картины, которым они предавались, не соответствует действительности. Идиллической обстановке, в которой они представляли античных людей, никогда и нигде не было. Не с зол ...

Мeтoдичecкиe ocoбeннocти рaбoты пo фoрмирoвaнию кoммуникaтивнoй кoмпeтeнтнocти учaщихcя при oбучeнии мaтeмaтикe
Для фoрмирoвaния кoммуникaтивнoй кoмпeтeнции нa oтдeльных рaбoчих и нa вceх oткрытых урoкaх рeкoмeндуeтcя иcпoльзoвaть тeхнoлoгию рaбoты в мaлых группaх (этo тeхнoлoгия из личнocтнo-oриeнтирoвaннoгo oбучeния). В cвoeй рaбoтe учитeлю вaжнo рacкрыть cуть дaннoй тeхнoлoгии: чтo oнa дaёт в плaнe фoрмир ...

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

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

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

Категории

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