Глава I. Решетки и полугруппы

13 Решетки и полугруппы

Отображение f: M — M’ частично упорядоченных множеств называется изотонным (монотонным), если для
любых a’b E M из а ^ b следует, что fa ^ fb (термин «порядковый гомоморфизм» в данной книге используется,
в основном, для упорядоченных групп). Биекция f: M — M’ частично упорядоченных множеств называется
изоморфизмом, если f и f-i — изотонные отображения; это эквивалентно тому, что для любых a’b E M неравенство
а ^ b имеет место если и только если fa ^ fb. Всякое частично упорядоченное множество M изоморфно
вкладывается в множество 2^ всех подмножеств некоторого множества N, частично упорядоченное относительно
теоретико-множественного включения; говорят кратко «порядок по включению». В качестве N можно взять само
M. Частично упорядоченные множества M и M’ называются антиизоморфными (двойственно изоморфными или
дуально изоморфными), если одно из них изоморфно другому, взятому с обратной частичной упорядоченностью,
т.е. существует биекция f: M — M’ такая, что а ^ b, где a’b E M, если и только если fb ^ fa.
Прямым произведением AB двух частично упорядоченных множеств A и B называется множество A х B, частично
упорядоченное по правилу: (a’ b) ^ (ai’ bi) (a’ ai E A; b bi E B) тогда и только тогда, когда а ^ ai в A и b ^ bi в B.
Элемент а частично упорядоченного множества M называется минимальным элементом этого множества, если в
M нет элемента x, удовлетворяющего условию x < а. Если же а ^ x для всех x E M, то а называется наименьшим
элементом множества M.
Теорема 1.1. Следующие три условия на частично упорядоченное множество M эквивалентны.
1) (Условие минимальности). Всякое непустое подмножество N С M обладает хотя бы одним минимальным (в
N) элементом.
2) (Условие обрыва убывающих цепей). Для всякой убывающей цепи элементов ai ^ а2 ^ … существует такой
индекс n, на котором эта цепь стабилизируется, т.е. an = an+i = … .
3) (Условие индуктивности). Все элементы частично упорядоченного множества M обладают некоторым свойством
E, если этим свойством обладают все минимальные элементы этого множества (в случае, когда они
существуют) и если из справедливости свойства E для всех элементов, строго предшествующих некоторому
элементу а, может быть выведена справедливость этого свойства для самого элемента а.
Линейно упорядоченное множество, удовлетворяющее условию минимальности (значит, и двум другим условиям
из теоремы 1 .1 ), называется вполне упорядоченным.
Минимальные элементы частично упорядоченного множества M относительно обратной упорядоченности называются
максимальными элементами множества M в его исходной упорядоченности, а убывающие цепи в обратной
упорядоченности называются возрастающими цепями множества M. Двойственным понятием к наименьшему элементу
является понятие наибольшего элемента. Наибольший и наименьший элементы частично упорядоченного
множества называются его единицей и нулем соответственно (если таковые существуют).
Если N — подмножество частично упорядоченного множества M, то всякий элемент a E M (не обязательно a E N),
удовлетворяющий условию а ^ x для всех x E N, называется верхней гранью подмножества N в множестве M.
Двойственным является понятие нижней грани. Точной верхней (нижней) гранью подмножества N в M называется
наименьшая верхняя (наибольшая нижняя) грань для N, обозначаемая через sup^ N (infM N), индекс M обычно
опускается. Верхним конусом NЛ множества N называется множество всех таких элементов x E M, что x ^ а для
всех a E N . Двойственным образом определяется нижний конус N^.
Множество всех цепей частично упорядоченного множества M само является частично упорядоченным при помощи
теоретико-множественного включения. Максимальные элементы этого последнего множества (если они существуют)
называются максимальными цепями множества M.
Теорема 1.2. Следующие утверждения эквивалентны.
1) (Аксиома выбора). Для всякого множества M существует такая функция ф: 2M — M, что ф(Л) E A при
любом 0 = A С M.
2) (Теорема Цермело). Всякое множество можно вполне упорядочить.
3) (Теорема Хаусдорфа). Всякая цепь частично упорядоченного множества содержится в некоторой максимальной
цепи.
4) (Теорема Куратовского-Цорна). Если всякая цепь частично упорядоченного множества M обладает верхней
гранью, то каждый элемент множества M сравним с некоторым максимальным элементом.
Утверждение, что всякое множество может быть линейно упорядочено, является более слабым, чем аксиома выбора.
Частично упорядоченное множество M называется верхней (соответственно, нижней) полурешеткой, если в нем
любое двухэлементное подмножество {a’ b} имеет точную верхнюю (соответственно, нижнюю) грань, обозначаемую
через а + b (соответственно, ab). Если в M для любых a’b E M существуют как а + b, так и ab, то M называется
решеткой.
«+» и «■» являются бинарными операциями на M, называемыми, соответственно, сложением или объединением и
умножением или пересечением.. Вместо «+» и «■» часто употребляют знаки «V» и «Л». Понятие решетки допускает
определение без использования частичной упорядоченности, а лишь при помощи свойств решеточных операций +

14 Решетки и полугруппы

Решетки.

и • (см. 1.2, 1.3). Это позволяет трактовать решетки как алгебраические системы с двумя бинарными операциями.
Если частично упорядоченное множество (L’ ^) является решеткой, то двойственное ему частично упорядоченное
множество (L’ ^) — тоже решетка. К решеткам применим принцип двойственности, для которых он принимает
следующую форму.
Пусть Е — утверждение о решетках, записанное в терминах операций + и •, а также символов ^ и, возможно, 0 и
1. Образуем утверждение, двойственное Е, заменяя друг на друга + и •, 0 и 1 и меняя ^ на ^. Если Е истинно во
всех решетках, то двойственное ему утверждение также истинно во всех решетках.
Подмножества любого множества составляют решетку с частичной упорядоченностью по включению. Можно говорить
о решетке подгрупп и решетке нормальных подгрупп некоторой группы G. Порядок подразумевается по
включению, а произведением (решеточным) подгрупп A и B является их теоретико-множественное пересечение
A П B, а роль суммы (решеточной) играет подгруппа (A’B), порожденная этими подгруппами, т.е. наименьшая
подгруппа, содержащая как A, так и B. Похожим способом вводится решетка подколец, решетка идеалов, решетка
левых (правых) идеалов некоторого кольца R, решетка подмодулей некоторого модуля M.
Решетка M называется полной, если всякое ее непустое подмножество N имеет sup N и inf N.
Решетка M называется дедекиндовой (или модулярной), если для любых a’bc E M, где а ^ c, справедлив модулярный
закон (а + b)c = а + bc. Дедекиндовыми являются решетки нормальных подгрупп произвольной группы,
идеалов кольца, подмодулей модуля. Напротив, решетка всех подгрупп не обязана быть дедекиндовой.
Решетка M называется дистрибутивной, если для любых a’b’c E M имеет место (а + b)c = ac + bc. Важнейшим
примером дистрибутивной решетки является решетка всех подмножеств произвольного множества. Однако
дедекиндова решетка всех подпространств векторного пространства уже не является дистрибутивной.
Теорема 1.3. Всякая дистрибутивная решетка изоморфна решетке подмножеств (не обязательно всех) некоторого
множества.
Непустое подмножество I решетки M называется идеалом, если для любых a’b E I следует, что а+ b E I и x E I для
всех x ^ а. Если I = M, то идеал I называется собственным. Двойственным образом вводится понятие коидеала
(также называемого фильтром). Для любого a E M множество (а] всех таких элементов b E M, что b ^ а (т.е.
(а] = а^), будет идеалом; это главный идеал, порожденный элементом а.
Собственный идеал P называется простым, если ab E P влечет a E P или b E P. Собственный коидеал F называется
простым, если а + b E F влечет a E F или b E F. Собственные идеалы решетки образуют упорядоченное
множество относительно включения. Максимальные элементы этого упорядоченного множества называются максимальными
идеалами решетки. Непустое пересечение идеалов снова является идеалом решетки. Поэтому для всякого
подмножества H решетки существует наименьший идеал, содержащий H, он называется идеалом, порожденным
подмножеством H. Идеалы решетки также образуют решетку.
Непустое подмножество P решетки называется подрешеткой, если a+b ab E P для любых a’b E P. Стоит отметить,
что решетка подгрупп группы G не будет подрешеткой в решетке подмножеств множества G, так как сложения в
этих двух решетках имеют разный смысл. Так же обстоит дело и с решетками подколец, идеалов, подмодулей.
Отображение ф решетки M в решетку L называется гомоморфизмом, если ф(а + b) = ф(а) + ф(Ь) и ф(аЪ) =
ф(а)ф(Ъ) для всех a’b E M. Гомоморфизм ф: M — L решеток, являющийся биекцией, называется изоморфизмом
(это эквивалентно тому, что ф — изоморфизм частично упорядоченных множеств M и L).
Решетка называется самодвойственной, если она антиизоморфна себе.
Эквивалентность =, определенная на решетке, называется конгруэнцией, если а = c и b = d влечет а + b = c + d и
ab = cd.
Теорема 1.4. Если всякое изотонное отображение ф решетки L в себя имеет неподвижную точку (т.е. ф(а) = а
для некоторого a E L), то L полна.
Если a’b — элементы частично упорядоченного множества M, причем а ^ b, то множество [a’b] = {x E M | a ^
x ^ b} называется интервалом. Если [a’b] = {a’b}, то этот интервал называется простым. Элемент а частично
упорядоченного множества M с 0 называется атомом, если интервал [0’а] прост, т.е. а — минимальный элемент
в множестве всех ненулевых элементов множества M.
Конечные частично упорядоченные множества удобно иллюстрировать диаграммами, на которых элементы изображаются
в виде точек по правилу: если а < b, то точка, соответствующая элементу b, расположена выше точки,
соответствующей элементу а, причем, если интервал [a’ b] прост, то соответствующие точки соединяются отрезком
прямой.
Решетка M называется решеткой с относительными дополнениями, если для всякого элемента c из любого интервала
[a’ b] найдется такой элемент d, что c + d = b и cd = а. Этот элемент d называется дополнением элемента
c в интервале [a’b]. Дополнение, в общем случае, определено не однозначно. Решетка с 0 и 1 называется решеткой
с дополнениями, если каждый ее элемент имеет дополнения в интервале [0 ’ 1 ], которые в этом случае называются
просто дополнениями. Любая решетка с относительными дополнениями, имеющая 0 и 1, обладает дополнениями.

15 Решетки и полугруппы

Обратное, как показывает, например, решетка N5 (см. ниже), вообще говоря, не верно.
Дистрибутивная решетка с дополнениями называется булевой алгеброй. В булевой алгебре каждый ее элемент а
обладает в точности одним дополнением а’ (упр. 1.35). Доказано, что существуют недистрибутивные решетки с
единственными дополнениями.
Примерами недистрибутивных решеток являются решетки N5 и M3 .
Решетка называется пентагоном или диамантом, если она изоморфна N5 или M3 соответственно.
Теорема 1.5. Решетка дедекиндова (дистрибутивна) тогда и только тогда, когда она не содержит пентагонов
(пентагонов и диамантов).
Цепь ао < ai < … < ап, принадлежащая частично упорядоченному множеству с 0 и 1, называется композиционным
рядом, если ао =0, ап = 1 и все интервалы [aj_i,aj] (г = 1,… , п) простые. Число п называется длиной
композиционного ряда.
Теорема 1.6. Все композиционные ряды дедекиндовой решетки имеют одинаковую длину.
Теорема 1.6 находит применения в теории колец, модулей и групп. Элементы ai,… ,ап дедекиндовой решетки с
нулем 0 называются независимыми, если (ai + … + ai_i + ai+i + … + an)ai = 0 для всех г = 1,… ,п. Сумму
независимых элементов ai,… ,ап называют прямой и обозначают через ai 0 … 0 ап.
Ненулевой элемент а дедекиндовой решетки с 0 и 1 называется неразложимым, если он не может быть представлен
в виде а = b 0 c, где b,c = 0 .
Теорема 1.7. Если дедекиндова решетка обладает композиционным рядом, то всякий ее ненулевой элемент
представим в виде конечной прямой суммы неразложимых элементов. Кроме того, если 1 = ai 0 … 0 ат =
bi 0 … 0 bk, где ai,… , am, bi,… ,bk — неразложимые элементы, то m = к и для всякого ai найдется такой
элемент bj, что 1 = ai 0 … 0 ai_i 0 bj 0 ai+i 0 … 0 am.
Теорема 1.7 в применении к решетке подпространств конечномерного векторного пространства дает известную
теорему о замене для двух эквивалентных систем линейно независимых векторов. Из последней вытекает, что все
базисы содержат одно и то же число векторов.
Элемент а решетки называется П-неразложимым, если а = bc влечет а = b или а = с. Представление элемента
а в виде а = ai …ап называется несократимым П-представлением, если элементы ai,… ,ап П-неразложимы и
ai… ai_iai+i.. .ап ^ ai для всех г = 1 ,… ,п.
Теорема 1.8. Если а = ai …am = bi …Ьп — два несократимых П-представления элемента а дедекиндовой
решетки, то m = п и для всякого ai найдется такой элемент bj, что а = ai… ai_ibjai+i… am.
Теорема 1.9. Для дедекиндовой решетки L с композиционным рядом эквивалентны следующие свойства:
а) L — решетка с дополнениями;
б) каждый элемент из L представим в виде прямой суммы атомов;
в) 1 представима в виде прямой суммы атомов.

Задачи

1.1. Решеточные операции обладают следующими свойствами:
а) а + а = а, аа = а;
б) а + b = b + a, ab = ba;
в) (а + b) + с = а + (b + с), (ab)c = a(bc);
г) а(а + b) = а, а + ab = а.
1.2. В решетке L следующие свойства эквивалентны:
а) а ^ b; б) а + b = b; в) ab = a.

16 Решетки и полугруппы

В частности, для нуля и единицы (если они существуют) справедливы равенства а • 0 = 0, а + 0 = а, а • 1 = а и
а + 1=1 для всех а Е L.
1.3. Пусть L — множество с бинарными операциями + и •, обладающими свойствами б) — г) из 1.1. Положим а ^ b
в точности тогда, когда а + b = b. Отношение ^ является частичным порядком на L, при этом L — решетка,
а + b = sup{a, b} и ab = inf{a, b}.
1.4. Почему следующие диаграммы частично упорядоченных множеств не являются решетками?
1.5. Всякий решеточный гомоморфизм является изотонным отображением. Обратное неверно.
1.6. Найдите все изотонные отображения и все решеточные гомоморфизмы из четырехэлементной решетки (рис.
1 ) в трехэлементную цепь (рис. 2 ).
ii
00
рис. i рис. 2
1.7. 1) Существует ровно два неизоморфных двухэлементных частично упорядоченных множества.
2) Существует в точности пять неизоморфных трехэлементных частично упорядоченных множеств, три из которых
самодвойственны.
1.8. 1) Имеется только пять неизоморфных решеток, содержащих менее пяти элементов.
2) Имеется в точности пять неизоморфных пятиэлементных решеток и три из них самодвойственны.
1.9. Нарисуйте диаграммы всех решеток из 1.8 1) и 1.8 2).
1.10. В решетке, если а ^ c и b ^ d, то а + b ^ c + d и ab ^ cd.
1.11. Подрешетка I решетки L является идеалом тогда и только тогда, когда если а Е I и b Е L, то ab Е I.
1.12. Если ф — изоморфизм частично упорядоченного множества L на частично упорядоченное множество M и
L — решетка, то M также решетка и ф является изоморфизмом решеток.
1.13. Следующие свойства решетки L эквивалентны:
а) L — цепь;
б) все непустые подмножества множества L являются подрешетками;
в) всякое изотонное отображение частично упорядоченного множества L в решетку M является решеточным
гомоморфизмом;
г) а = bc влечет а = b или а = c.
1.14. Решетка тогда и только тогда полна, когда в ней есть наибольший элемент и любое ее непустое подмножество
имеет точную нижнюю грань.
1.15. 1) Конечное частично упорядоченное множество с 0 и 1 имеет композиционный ряд.
2) Постройте бесконечное частично упорядоченное множество, имеющее композиционный ряд.
3) Прямое произведение двух решеток является решеткой.
1.16. Интервал [a, b] полной решетки L является полной решеткой, причем supja ь] A = supL A и infA = infl A
для всякого непустого подмножества A С [a, b].
1.17. Если ф — изотонное отображение полной решетки L в себя, то фа = а для некоторого а Е L. Кроме того,
множество неподвижных точек содержит наименьший элемент.
1.18. Приведите пример частично упорядоченного множества, не являющегося полной решеткой, все изотонные
отображения которого в себя имеют неподвижную точку.
1.19. Если решетка удовлетворяет условию максимальности, то все ее идеалы являются главными. Сформулировать
двойственное утверждение

17 Решетки и полугруппы

1 .2 0 . N5 является единственной недедекиндовой пятиэлементной решеткой.
1.21. Какие из элементов следующих решеток имеют дополнения? В каких из этих решетках элементы с дополнениями
образуют подрешетку?
1.22. Каждый смежный класс конгруэнции на решетке является выпуклой подрешеткой.
1.23. Пусть = — конгруэнция на решетке L и а — смежный класс, определяемый элементом а. Положим а + b =
а + b и а • b = а • b. Убедитесь, что операции определены корректно и обладают свойствами б) — г) из 1.1, т.е.
фактормножество L = L/ = является решеткой.
Решетка L называется факторрешеткой решетки L по конгруэнции =. Отображение а ^ а является гомоморфизмом,
называемым каноническим.
1.24. Пусть ф: L P — решеточный гомоморфизм. Отношение: «aRb тогда и только тогда, когда ф(а) = ф(Ь)»
является конгруэнцией, называемой ядром гомоморфизма ф.
1.25 (Теорема о гомоморфизме). Пусть ф — гомоморфизм решетки L на решетку M и R — ядро этого гомоморфизма.
Тогда существует такой изоморфизм ф решетки M на факторрешетку L/R, что ф(ф(а)) = а для всех а Е L, где
а — образ элемента а при каноническим гомоморфизме, определяемом конгруэнцией R.
1.26. Если конгруэнция R на решетке L такова, что факторрешетка L/R имеет нуль, то полный прообраз этого
нуля является идеалом, называемым ядерным идеалом конгруэнции R (ядерный коидеал определяется двойственным
образом). В отличие от групп, колец и модулей, не всякий идеал решетки является ядерным. Всякий же простой
идеал служит ядерным идеалом некоторого решеточного гомоморфизма.
1.27. Подрешетка P решетки L является простым идеалом тогда и только тогда, когда L \ P — простой коидеал.
1.28. Следующие свойства решетки L эквивалентны:
а) L дедекиндова;
б) a(ab + c) = ab + ac для любых a,b,c Е L;
в) если а ^ b и для некоторого c Е L справедливо а + c = b + c и ac = bc, то a = b.
1.29. Дедекиндовость решетки равносильна каждому из следующих свойств:
а) а + b(a + c) = (а + b)(a + c);
б) (а + bc)(b + c) = a(b + c) + bc;
в) если a ^ c и d ^ b, то a + b(c + d) = (a + b)c + d;
г) если a ^ c ^ a + b, то a + bc = c;
д) если a ^ b ^ c + d, ac = bc и (a + c)d = (b + c)d, то a = b.
1.30. 1) Если в дедекиндовой решетке (а + b)c = 0, то a(b + c) = ab.
2) В дедекиндовой решетке справедливо равенство (ab+ac)(ab+bc) = ab, а из (a+b)c = bc вытекает, что a(b+c) = ab.
3) Дедекиндова решетка с дополнениями является решеткой с относительными дополнениями.
1.31. Если a,b — элементы дедекиндовой решетки, то отображения ф(х) = x + b (ab ^ x ^ а) и ф(у) = ay
(b ^ у ^ а + b) осуществляют изоморфизм интервалов [ab, а] и [b,a + b].
1.32. Если ai,… ,an,bi,… ,bn — элементы дедекиндовой решетки и ai ^ bj при i = j, то (ai +… + an)bi •… • bn =
aibi + … + anbn.
1.33. Дедекиндовость (дистрибутивность) решетки равносильна дедекиндовости (дистрибутивности) решетки ее
идеалов.
1.34. Следующие свойства решетки L эквивалентны:
а) L дистрибутивна;
б) ab + c = (a + c)(b + c) для любых a,b,c Е L;
в) ab + bc + ca = (a + b)(b + c)(c + a) для любых a,b,c Е L;

18 Решетки и полугруппы 

г) если для некоторого c Е L справедливо a + c = b + c и ac = bc, то a = b.
1.35. В дистрибутивной решетке каждый элемент может иметь не более одного дополнения. В частности, в булевой
алгебре каждый элемент обладает единственным дополнением.
1.36. Дистрибутивная решетка, обладающая композиционным рядом, конечна.
1.37. Решетки (2M, П, U), (N, нод, нок) и все цепи дистрибутивны.
1.38. Убедитесь, что следующие две диаграммы изображают одну и ту же решетку.
1.39. Упростите диаграммы на следующих рисунках.
1.40. В дистрибутивной решетке каждый максимальный идеал прост, а произвольный идеал совпадает с пересечением
всех содержащих его простых идеалов.
1.41. Нарисуйте диаграмму булевой алгебры всех подмножеств трехэлементного множества A = {1, 2, 3}.
1.42. В булевой алгебре справедливы соотношения: (а + b)’ = a’b’, (ab)’ = а’ + b’, а» = а, 0′ = 1, 1′ = 0; если а ^ b,
то b’ ^ а’.
1.43. В булевой алгебре равносильны утверждения: а) а ^ b; б) ab’ = 0; в) а’ + b = 1.
1.44. Если в решетке L с 0 и 1 каждый элемент а обладает единственным дополнением а’, причем (а + b)’ = ab’ и
(ab)’ = а’ + b’, то L — булева алгебра.
1.45. Совокупность элементов дистрибутивной решетки, обладающих дополнениями, образует решетку, являющуюся
булевой алгеброй.
1.46. Дедекиндова решетка с единствеными дополнениями является булевой алгеброй.
1.47. Каждая дистрибутивная решетка является подрешеткой некоторой булевой алгебры.
1.48. Если ф — гомоморфизм булевой алгебры B на булеву алгебру, то ф(Ь’) = (ф(Ь))’ для всех b Е B.
1.49. Дистрибутивная решетка является булевой алгеброй тогда и только тогда, когда каждый ее простой идеал
максимален.
1.50. Решетка M3 изоморфна решетке всех подгрупп четверной группы Клейна V4, т.е. группы Z2 0 Z2 .
1.51. Постройте диаграммы решеток всех подгрупп следующих групп: Z2 0 Z3 , Z2 0 Z4 , симметрической группы
S3, группы диэдра D4.
1.52. Пусть R — кольцо всех линейных операторов конечномерного векторного пространства V над некоторым
полем. Решетка всех подпространств пространства V изоморфна решетке всех правых идеалов кольца R и анти-
изоморфна решетке всех его левых идеалов.
1.53. Решетка всех правых идеалов кольца матриц порядка n (n > 1) над некоторым полем как изоморфна, так
и антиизоморфна решетке всех левых идеалов этого кольца. Обе эти решетки и все решетки из предыдущего
упражнения самодвойственны.
1.54. Пусть V и W — конечномерные векторные пространства над одним полем. Если решетки всех подпространств
этих пространств изоморфны, то пространства V и W имеют одинаковую размерность и, значит, они изоморфны.
Длина конечной цепи из n элементов по определению полагается равной n — 1. Длиной частично упорядоченного
множества M называется точная верхняя грань длин цепей в M; если она конечна, то говорят, что M имеет
конечную длину.
1.55. В дедекиндовой решетке:
а) если а = b и для некоторого элемента c интервалы [c, a], [c, b] простые, то просты интервалы [a, а + b], [b,a + b];

19 Решетки и полугруппы 

б) если а = b и для некоторого элемента c интервалы [a, c], [b, c] простые, то просты интервалы [ab, a], [ab, b].
Доказано, что в решетке конечной длины условия а) и б) необходимы и достаточны для дедекиндовости. Как
показывает следующая диаграмма, решетка с дополнениями и удовлетворяющая свойству а) не обязана обладать
относительными дополнениями (ср. с 1.30 3)).

20 Решетки и полугруппы