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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

Е.М. Вечтомов

1. Мотивация

Сравнение материальных и идеальных элементов по величине - фундаментальный способ освоения действительности и научного исследования. Часто вещи сравниваются по той или иной числовой величине: города - по численности населения, товары - по цене, люди - по росту или весу и т. п. Столь же привычно сравнение в науке. Достаточно назвать математическое направление, в котором изучаются числовые и функциональные неравенства [1]. В математике, во-первых, сравниваются действительные (вещественные) числа, затем: линии - по длине, плоские фигуры - по площади, числовые функции - поточечно, множества - по мощности и т. д. Перечисленные примеры имеют общую формальную структуру - порядковую, элементы в них связаны отношением квазипорядка (несколько более широким, чем отношение порядка).

Современная математика - структурная наука, изучающая структуру сущего (реального и идеального), отображаемую в общенаучных, философских категориях количества, формы, меры. Точнее, математика изучает математические структуры, т. е. множества с заданными на них операциями и отношениями. На языке математических структур и выражаются разнообразные проявления категорий количества, формы и меры. Подчеркнем, что математические структуры определяются и изучаются на языке теории множеств - фундаменте классической математики последнего столетия [2].

В середине XX в. группа французских математиков под псевдонимом Никола Бурбаки выделила три типа математических структур - алгебраический, порядковый и топологический. В своей знаменитой концептуальной статье 1948 г. «Архитектура математики» [3] Бурбаки назвали математику учением о математических структурах. Многие конкретные математические объекты относятся к одному из этих типов моноструктур или являются их естественным переплетением. Методологические аспекты структурного характера математики отражены в [4].

Исходным порядковым понятием служит отношение порядка, т. е. бинарное отношение на множестве, удовлетворяющее свойствам рефлексивности, транзитивности и антисимметричности. А базовым порядковым объектом является упорядоченное множество как множество с определенным на нем отношением порядка. Тем самым изучение порядковой структуры тесно связано и опирается на понятие бинарного отношения на множестве. Одна из возможных методик изучения бинарных отношений предложена автором [5].

Некоторые ученые (например, психолог Ж. Пиаже) правомерно считают, что основные типы математических структур соответствуют подобным им психологическим структурам и интеллектуальным способностям человека (см. [6]). Это вполне согласуется с метафизическим принципом единства мира, гармоничным сосуществованием его материальной, идеальной и психической граней. Поэтому актуальной задачей математического образования является формирование и развитие абстрактного структурного мышления путем изучения важнейших математических структур.

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

По сравнению с алгебраическим и топологическим типами структур порядковая структура практически не изучается ни в школе, ни в вузе (иногда приводится определение и несколько простейших примеров). Поэтому мы в спецкурсе «Основные математические структуры» [7], предназначенном студентам математических специальностей, отводим изучению упорядоченных множеств заметное место (мы рассматриваем еще два типа фундаментальных структур - структуры инцидентности и пространства с мерой). Мало кто из преподавателей математики задумывается над тем, что НОК и НОД натуральных чисел, объединение и пересечение множеств, дизъюнкция и конъюнкция высказываний суть примеры общих порядковых операций sup и inf, показывающие универсальность порядкового языка, терминологии и обозначений, принятых в теории упорядоченных множеств.

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

Автор данной статьи является активным сторонником и популяризатором специального изучения порядковой структуры, неоднократно выступал с научно-методическими докладами, читал спецкурсы для студентов и вел кружковые занятия со школьниками на эту тему [8].

2. Методика

Сформулируем ведущие дидактические положения, на которые может и должно опираться изучение порядковой структуры.

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

II. Принцип фундаментальности подразумевает научность излагаемого знания, т. е. четкость определений и формулировок, строгость доказательств, «разметку» границ данной математической теории, его связи и приложения.

III. Принцип наглядности. Наглядность порядковых понятий и интерпретаций способствует усвоению абстрактного материала. Важную роль играет изображение конечных упорядоченных множеств диаграммами Хассе.

IV. Тренинг. Изучение порядковой структуры должно сопровождаться самостоятельным решением разнообразных упражнений: проверочных тестов, заданий учебного характера, учебно-исследовательских и научно-исследовательских задач.

V. Внутриматематические связи. Математика - единая наука, разные разделы которой связаны содержательно и структурно. Имеется тесная взаимосвязь между основными типами математических структур, установленная еще П.С. Александровым, М. Стоуном, Г. Биркгофом (см. [9]). Особенно хорошо эти связи прослеживаются на конечных объектах.

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

Что следует знать преподавателю математики о порядковой структуре?

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

Во-вторых, модельные примеры: цепь действительных чисел с обычным порядком, булеаны, решетка натуральных чисел с отношением делимости. Эти примеры хорошо иллюстрируют обобщающий характер порядкового подхода. Полезно научиться изображать конечные упорядоченные множества диаграммами Хассе, что особенно важно в дискретной математике. Надо понимать, что алгебры высказываний, множеств и событий являются булевыми алгебрами, а множество всех действительнозначных функций на произвольном множестве образует дистрибутивную решетку с поточечно определенным отношением порядка.

В-третьих, определенный минимум фактов: простейшие свойства упорядоченных множеств, принцип двойственности, эквивалентность порядкового и алгебраического понятий решетки, теорема Стоуна о строении конечных булевых алгебр, теорема Тарского о неподвижной точке, лемма Кенига, формулировки леммы Цорна и теорем Цермело и Гельдера, порядковые свойства основных числовых систем.При обучении математике студентов и учащихся физико-математических лицеев желательно систематически использовать порядковый язык, находить и применять информацию об упорядоченных структурах.

Таблица модельных примеров упорядоченных множеств

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

1. Повторение теоретико-множественных понятий.

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

3. Определение исходных порядковых понятий.

4. Конечные упорядоченные множества и их диаграммы Хассе.

5. Отработка порядковых понятий на модельных примерах, их иллюстрация таблицами и графами, на диаграммах Эйлера - Венна и Хассе.

6. Доказательство простейших свойств упорядоченных множеств. Принцип двойственности.

7. Построение новых примеров и контрпримеров.

8. Понятие решетки. Эквивалентность порядкового и алгебраического определений.

9. Начала теории решеток. Понятия подрешет- ки, идеала, конгруэнции, гомоморфизма, фактор-решетки, прямого произведения решеток.

10. Дистрибутивные решетки. Их свойства и представления.

11. Булевы решетки, булевы алгебры и булевы кольца.

12. Исследовательские задачи об упорядоченных множествах и решетках. Темы курсовых и дипломных работ. Примерные задачи и темы работ можно найти в [10].

Пункты 1-11 сопровождаются решением учебных упражнений.

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

3. Реализация

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

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

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

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

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

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

Определение 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 множество X₁ всех минимальных элементов и изображаем их точками, расположенными горизонтально (это первый уровень). Затем в упорядоченном множестве XXX₁ снова рассматриваем множество X₂ всевозможных минимальных элементов, помещая их на второй горизонтальный уровень над первым. Далее повторяем процедуру: берем упорядоченное множество XX(X₁UX₂) и т. д. В результате упорядоченное множество X разбивается на уровни X₁, X₂, ..., X_n, являющиеся антицепями. Элемент a е X находится на k-м уровне (2 < k < п) тогда и только тогда, когда начинающиеся с a убывающие цепи в X имеют наибольшее число элементов, равное k. Элементы последнего уровня X_n максимальны, но не обязаны исчерпывать множество всех максимальных элементов в X.

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

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

Рис. 3

Упражнение 8. Постройте диаграммы Хассе всех 15 шестиэлементных решеток.

На любой решетке L зададим бинарные операции сложения + и умножения * формулами: a + b = sup(a, b) и ab = a * b = inf(a, b). (*)

Получаем алгебру (L, +, *>, в которой выполняются следующие четыре пары тождеств:

1) a + b = b + a, ab = ba (коммутативность операций);

2) (a + b) + c = a + (b + c), (ab)c = a(bc) (ассоциативность);

3) a + a = a, aa = a (идемпотентность);

4) a + ab = a, a(a + b) = a (законы поглощения).

Упражнение 9. Докажите свойства 1)-4) алгебры (L, +, *>, полученной из решетки L.

Имеет место и обратный переход. Если (L, +, *> - алгебра со свойствами 1)-4), то (L, #> будет решеткой, в которой a # b означает a + b = b (равносильно, ab = a); при этом справедливы формулы (*).

Упражнение 10. Докажите данное утверждение.

Упражнение 11. Проверьте, что в решетках неравенства можно почленно складывать и умножать: a < b и c < d влекут a + c < b + d и ac < bd.

Упражнение 12. Убедитесь, что в любой решетке выполняется тождество (ab + ac)(ab + bc) = ab.

Упражнение 13. Покажите, что в произвольной решетке верны неравенства ab + ac < a(ab + c) < a(b + c).

Упражнение 14. Наименьший элемент решетки обычно называется нулем и обозначается 0, а наибольший элемент решетки часто называется единицей и обозначается 1. Докажите, что нулевой элемент 0 (единичный элемент 1) произвольной решетки определяется любым из тождеств 0a = 0, 0 + a = a (соответственно: 1a = a, 1 + a = 1).

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

Любая полная решетка L является решеткой с 0 = inf L и 1 = sup L.

Укажем основные примеры полных решеток:

1) числовые отрезки [a, b], где a, b е R и a < b (пример 1);

2) булеаны B(M) для произвольных множеств M (пример 2);

3) решетка (N₀, | ) (пример 4);

4) конечные решетки;

5) решетка всех подалгебр любой алгебры относительно включения с;

6) решетка всевозможных конгруэнций на произвольной алгебре с с;

7) решетка всех открытых (замкнутых) множеств любого топологического пространства.

Говорят, что отображение f: X^X множества X в себя имеет неподвижную точку x₀ е X, если f(x₀) = x₀. В теории упорядоченных множеств изучаются неподвижные точки изотонных отображений упорядоченных множеств и решеток. Докажем теорему Тарского о неподвижной точке:

Теорема 2. Всякое изотопное отображение f любой полной решетки L в себя имеет хотя бы одну неподвижную точку.

Доказательство. Рассмотрим в L подмножество A = {x е L: x < f(x)}. Положим x₁ = sup A. Поскольку 0 е A, то sup A существует. Покажем, что f(x₁) = x₁. Так как x < x₁ для всех x е A, то и x < f(x) < f(x₁) для всех x е A. Поэтому f(x₁) - верхняя грань множества A, и x₁ < f(x₁). Откуда f(x₁) < f(f(x₁)), т. е. f(x₁) е A. Значит, и f(x₁) < x₁.

Заметим, что x₁ является наибольшей неподвижной точкой отображения f. Наименьшая неподвижная точка x₀ отображения f получается двойственным способом: x₀ = inf B для B = {x е L: x > f(x)}. Множество F(f) = {x е L: f(x) = x} всех неподвижных точек отображения f совпадает с A n B.

Упражнение 15. Покажите, что множество F(f) не обязано быть подрешеткой решетки L.

Отметим также, что для решеток верна теорема Дэвиса, обратная теореме Тарского.

Упражнение 16. В классе упорядоченных множеств теорема Дэвиса неверна. Приведите соответствующий пример.

Дистрибутивные решетки и булевы решетки

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

Определение 6. Решетка называется дистрибутивной, если в ней выполняется тождество a(b + c) = ab + ac. Класс всех дистрибутивных решеток, как и класс всех решеток, образует многообразие алгебр с двумя бинарными операциями. Более широкое многообразие образуют модулярные решетки, в которых выполняется модулярное тождество (вместо дистрибутивного тождества) a(ab + c) = ab + ac.

Сформулируем полезные критерии дистрибутивности решетки:

1. Произвольная решетка дистрибутивна тогда и только тогда, когда любая ее подрешетка не изоморфна ни пентагону, ни диаманту.

2. Дистрибутивность решетки эквивалентна выполнению в ней двойственного дистрибутивного закона: (a + b)(a + c) = a + bc.

3. Решетка дистрибутивна тогда и только тогда, когда для любых ее элементов a, b и c имеем: a + b = a + c и ab = ac влекут b = c.

4. Дистрибутивность решетки равносильна выполнению в ней тождества: (a + b)(a + c)(b + c) = = abc.

Покажем, например, что дистрибутивная решетка L удовлетворяет свойству из критерия 3. Пусть a + b = a + c и ab = ac для некоторых b, c из L.

Тогда b = b(a + b) = b(a + с) = ab + bc = = ac + bc = c(a + b) = c(a + с) = с.

Решетка с 0 и 1 называется ограниченной. Если в ограниченной решетке a + b = 1 и ab = 0, то элементы a и b называются дополнениями друг друга.

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

Упражнение 17. Убедитесь непосредственно, что диамант и пентагон не дистрибутивны.

Упражнение 18. Проверьте свойство 2.

Упражнение 19. Докажите y в свойстве 4.

Определение 7. Ограниченная дистрибутивная решетка с 1 * 0, в которой каждый элемент имеет дополнение, называется булевой решеткой.

Сведения о булевых решетках, булевых алгебрах и булевых кольцах можно найти в [14]. Заметим, что эти понятия равносильны, точнее, классы булевых решеток, булевых алгебр и булевых колец с единицей совпадают между собой.

Атомы решетки L с нулем 0 - это минимальные элементы упорядоченного множества L\{0}. Решетка с нулем 0 называется атомной, если для любого ее ненулевого элемента x существует такой атом а, что a # x.

Примеры булевых решеток:

1. Пусть M - произвольное непустое множество. Тогда булеан B(M) есть булева решетка с операциями и и п и порядком с, причем дополнением любого элемента A є B(M) служит его теоретико-множественное дополнение M\A. Булеан B(M) изоморфен прямому произведению Ml экземпляров двухэлементной цепи D = {0, 1}.

2. Рассмотрим множество B всех конечных множеств натуральных чисел и дополнений до них в N (так называемых коконечных множеств). Относительно включения множеств с множество B будет счетной атомной булевой решеткой - подрешеткой булеана B(N).

3. Рассмотрим алгебру (пропозициональных) высказываний A с операциями дизъюнкции, конъюнкции и отрицания. Ее элементами служат формулы логики высказываний. Отношение / равносильности высказываний является конгруэнцией на алгебре A. Соответствующая факторалгебра A// , называемая алгеброй Линденбаума, является булевой решеткой. В ней [P] # [Q] означает, что P^Q - тавтология, т. е. P^Q / И (истина). Дополнением к [P] будет класс []P] отрицания высказывания P.

Решетка +N₀, |) - полная атомная дистрибутивная решетка с условием минимальности с наименьшим элементом 1 и наибольшим элементом

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

Пусть L - произвольная булева решетка. Каждый ее элемент а обладает единственным дополнением, которое будем обозначать а'.

Булевы решетки обладают следующими свойствами:

(1) 0N=1, 1N=0.

(2) а"=а.

(3) а # Ь ] Ь' # а' ] а' + Ь = 1 ] аЬ' = 0.

(4) (а + Ь)' = а'Ь', (аЬ)' = а' + Ь' (законы де Моргана).

(5) а + а' =1, аа' = 0.

Упражнение 20. Проверьте эти свойства.

Изобразим диаграммы Хассе трех первых (по

числу элементов) булевых решеток (рис. 4).

В решетке D² элементы а и а' являются атомами. Атомы а, Ь, с решетки D³ располагаются на втором уровне диаграммы, а их дополнения а', Ь', с' - на третьем уровне.

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

Теорема 3. Любая конечная булева решетка изоморфна булеану B(A), где A - множество всех ее атомов.

Доказательство. Пусть A - множество всех атомов конечной булевой решетки L. Установим изоморфизм между решетками L и B(A), сопоставив каждому элементу x є L подмножество в A: /(х)={а є A: а # x}. Сразу заметим, что f(0)= i и f(1) = A. Покажем, что f является биекцией L на B(A). Возьмем в L элементы x * у.

Тогда одно из соотношений x # у или у # x неверно. Можно считать, что неверно x # у. По свойству (3) булевых решеток xy' * 0. В силу атомности конечной решетки L в ней найдется такой атом a, что a # xy'. Имеем a # x и a # у', откуда a е f(x) и ay = ay'у = a0 = 0. Последнее означает, что a $ f(y). Поэтому f(x) * f(y). Тем самым доказана инъективность отображения f.

Для проверки сюръективности f возьмем произвольное непустое множество B = {a₁, ..., a_k} атомов решетки L. Нужно найти элемент b е L, для которого f(b) = B. Положим b = a₁ + ... + a_k. Ясно, что B с f(b). Если a е f(b), т. е. a # b, то a = a(a₁ + . + a_k) = aa₁ + . + aa_k. Отсюда следует, что атом a совпадает с одним из атомов а, иначе aa₁ + ... + aa_k = 0. Поэтому и f(b) с B, т. е. f(b) = B.

Наконец, если x # у, то f(x) с f(y) по определению отображения f. Обратно, если f(x) с f(y) для x, у е L, то по доказанному x = Ef(x) # Ef(y) = у. Следовательно, биекция f является (порядковым) изоморфизмом решеток L и B(A), что завершает доказательство теоремы.

Булеан B(M) является булевой алгеброй относительно операций объединения, пересечения и дополнения. Пусть B - произвольная булева алгебра с бинарными операциями +, * и унарной операцией'.

Упомянутая классическая теорема Стоуна утверждает, что B изоморфна подалгебре булеана B(M), где в качестве M можно взять множество всех максимальных идеалов в B. Элементы и операции в B интерпретируются соответственно как подмножества в M и теоретико-множественные операции над ними.

Так, равенство ab = 0 в алгебре B означает, что соответствующие множества не пересекаются. Мы уже знаем, что B является (булевой) решеткой с отношением порядка # (a # b означает a + b = b), интерпретируемым как отношение включения с подмножеств множества M. После этого становится ясно, что булевы алгебры действительно должны обладать естественные свойствами (1) - (5).

В заключение рассмотрим обобщение примера 6, показывающее возможность дальнейших исследований в теории решеток. Для данных непустого множества X и решетки S рассмотрим решетку S^x всевозможных отображений X^S с поточечно определенными операциями сложения и умножения отображений. Если решетка S имеет наименьший элемент 0 и не содержит делителей нуля, то равенство fg = 0 (здесь 0 трактуется как функция-константа, принимающая в любой точке множества X значение 0) в решетке функций S^x означает, что f(x) = 0 или g(x) = 0 для каждого x е X. Знакомая картина получается в случае R^x для числовых промежутков X, когда функции изображаются графиками. В теории пучковых (функциональных) представлений [15] абстрактная ограниченная дистрибутивная решетка S представляется как решетка сечений соответствующего пучка ограниченных дистрибутивных решеток-слоев S_x, индексированных точками базисного топологического пространства X. Слои должны быть устроены проще исходной решетки S. На этом пути получается и сформулированная выше классическая теорема Стоуна, когда все S_x изоморфны двухэлементной цепи.

Примечания

порядковый структура математический

1. Харди Г., Литтлвуд Д., Полиа Г. Неравенства. М.: ГИИЛ, 1948; Беккенбах Э., Беллман Р. Неравенства. М.: Мир, 1965; Калинин С. И. Средние величины степенного типа. Неравенства Коши и Ки Фана. Киров: Изд-во ВятГГУ, 2002.

2. Архангельский А.В. Канторовская теория множеств. М.: МГУ, 1989; Куратовский К., Мостов- ский А. Теория множеств. М.: Мир, 1970.

3. Бурбаки Н. Очерки по истории математики. М.: ИЛ, 1963, С. 245-259.

4. Вечтомов Е.М. Метафизика математики. Киров: Изд-во ВятГГУ, 2006.

5. Вечтомов Е.М. Бинарные отношения// Математика в образовании. 2007. Вып. 3. С. 41-51.

6. Тестов В.А. Стратегия обучения математике. М.: Технологическая Школа Бизнеса, 1999.

7. Вечтомов Е.М. Основные структуры классической математики. Киров: Изд-во ВятГГУ, 2007.

8. Вечтомов Е.М. Теория решеток. Киров: КГПИ, 1995; Вечтомов Е.М. Упорядоченные структуры в курсе математики// Математика и общество. Математическое образование на рубеже веков: сб. материалов Всерос. конф. (Дубна). М.: МЦНМО, 2000. С. 351-- 154;

9. Вечтомов Е.М. Модельные примеры в обучении современной математике// Вестник ВятГПУ. 2001. № 5. С. 79-82;

10. Вечтомов Е.М. О взаимосвязи основных математических структур // Материалы XXV Всерос. семинара преподавателей математики педвузов и университетов. Киров; М.: Изд-во ВятГГУ, 2006. C. 6-11;

11. Вечтомов Е.М. Взаимосвязь основных математических структур // Современные методы физико-математических дисциплин: материалы Междунар. науч. конф. Т. 1. Орел: Орлов. гос. ун-т, 2006. С. 183-187; Вечтомов Е.М. Обучение математике через простейшие модели // Материалы III Междунар. конф. М.: РУДН, 2008. С. 597-599.

12. Вечтомов Е.М. Основные структуры классической математики. Киров: ВятГГУ, 2007. Гл. 7.

13. Там же; Вечтомов Е.М., Варанкина В.И. Упорядоченные множества с конечным условием минимальности // Вестник ВятГПУ. 2000. № 3-4. С. 11

14. Беран Л. Упорядоченные множества (Ь-ка «Популярные лекции по математике», вып. 55). М.: Наука, 1981;

15. Биркгоф Г., Барти Т. Современная прикладная алгебра. М.: Мир, 1976. Гл. 2, 5, 9;

16. Столл Р. Множества. Логика. Аксиоматические теории. М.: Просвещение, 1968. Гл. I, IV;

17. Фрид Э. Элементарное введение в абстрактную алгебру. М.: Мир, 1979. Гл. 3;

18. Шрейдер Ю.А. Равенство, сходство, порядок. М.: Наука, 1971.

19. Биркгоф Г. Теория решеток. М.: Наука, 1984;

20. Гретцер Г. Общая теория решеток. М.: Мир, 1982;

21. Расева Е., Сикорский Р. Математика метаматематики. М.: Наука, 1973. Гл. I-IV;

22. Скорняков Л.А. Элементы теории структур. М.: Наука, 1982; Стенли Р. Перечислительная комбинаторика. М.: Мир, 1990. Гл. 3.

23. Вечтомов Е.М. Упорядоченные множества с диаграммой Хассе // Вестник ВятГГУ. 2002. № 6. С. 13-15.

24. Сикорской Р. Булевы алгебры. М.: Мир, 1969; Вечтомов Е. М. Аннуляторные характеризации булевых колец и булевых решеток // Математические заметки. 1993. Т. 53. Вып. 2. С. 15-24; см. также примечания 9, 11, 12.

Размещено на Allbest.ru