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

Рис. 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) решетка (N0, | ) (пример 4);

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

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

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

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

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

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

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

Заметим, что x1 является наибольшей неподвижной точкой отображения f. Наименьшая неподвижная точка x0 отображения f получается двойственным способом: x0 = 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.