Алгебра и логика, 39, N 1 (2000), 87-92
УДК 512.565
НЕОГРАНИЧЕННЫЕ ПОЛУДИСТРИБУТИВНЫЕ РЕШЕТКИ ДЖ.Б.НЕЙШЕН Памяти Виктора Александровича Горбунова
Цель данной работы состоит в демонстрации некоторого способа рас суждений — ранее он уже доказал свою целесообразность и применяется здесь для решения одной достаточно интересной проблемы, а именно, в работе дается отрицательный ответ на вопрос о том, будет ли конечная решетка, в которой выполняются условия (Р) и (Q), близкие к ограничен ности, ограниченной. Необходимая для читателя информация об ограни ченных гомоморфизмах и решетках содержится в [1, глава 2].
§ 1. Неограниченные решетки Вначале приведем один хорошо известный критерий для того, что бы решетка была полудистрибутивной вниз. Пусть L — конечная решетка и а Е J(L). Через к(а) обозначим наибольший элемент, который больше, чем а*, но не больше, чем а (разумеется, в том случае, если такой эле мент существует). Будем рассматривать к : J(L) —> M(L) как частичное отображение. Л Е М М А 1. Пусть L является конечной решеткой. Решетка L удовлетворяет условию SDA в том и только в том случае, если к (а) определено для всех а £ J(L). Более того, если в конечной решетке L выполняется условие SD A , то к отображает J(L) на M(L). Если же в L выполняется еще и условие SD V , то ©
Сибирский фонд алгебры и логики, 2000
88
Дж. Б. Нейшен
к будет взаимно однозначным отображением, а двойственное отображение Kd : M(L) —>- J(L) — отображением, обратным к отображению к. Отношения зависимости на J(L) определяются стандартным обра зом, а именно (при формулировке трех первых предполагается, что вы полняется условие SD A ): аАЬ<& Ь < а < к(Ь)*, аВЬ & афЪ, b £ к(а), 6* < к(а), аСЬ <& аАЬ или а В Ь, aDb<$ существует х £ L такой, что
a
Тогда A U B = C C D . Двойственные к ним отношения определяются на M(L). В полудис трибутивных решетках они устроены достаточно хорошо, что показывает следующая Л Е М М А 2 (см. [2]). Пусть L — конечная
полудистрибутивная
решетка и a, b Е J(L). Имеют место соотношения: 1) аАЬ тогда и только тогда, когда к(а) Bd к(Ь); 2) аВЬ тогда и только тогда, когда к{а) Adк(Ь). Напомним основные результаты об ограниченных (в смысле Р. Маккензи) решетках и о jD-циклах. Т Е О Р Е М А 3. Конечная решетка L ограничена снизу тогда и только тогда, когда L не содерэюит D-циклов. Более того, в каждой ограниченной снизу решетке выполняется условие SDV • Т Е О Р Е М А 4. Конечная полудистрибутивная решетка L ограни чена тогда и только тогда, когда L не содерэюит С-циклов. Будем рассматривать полудистрибутивные решетки, в которых вы полняются условие (Р)
если a,b 6 J(L) и Ь < а, то аАЬ;
и двойственное к нему условие (Q)
если р, q 6 M(L) и q > р, то р Ad q.
Заметим, что pAdq имеет место в точности тогда, когда nd(p)
BKd{q).
Неограниченные полудистрибутивные решетки
89
Н. Каспар [3] доказала, что решетка S n всех перестановок на пэлементном множестве ограничена. В [4] она установила, что в этих ре шетках выполняются условия (Р) и (Q), и, используя указанный результат, нашла удачную характеризацию таких линейных порядков на J(S n ), кото рые согласованы с отношением зависимости D. В связи с этим естественно возникает вопрос: Будет ли конечная полудистрибутивная решетка, в которой вы полняются условия (Р) и (Q), ограниченной! В настоящей работе мы даем отрицательный ответ на этот вопрос.
§ 2* Полудистрибутивные решетки
Л Е М М А 5. Если L — конечная решетка, в которой нарушается условие SD V , то существуют различные элементы a, b E J(L) и с (Е L такие, что a V c = b V c ) ^ c , a * < c u b * < c . ДОКАЗАТЕЛЬСТВО. Предположим, что в L выполняется ao V CQ = = boVco > (aoAbo) Vco. Выберем с так, что aoVfto >- с > (аоЛЬо) Vco- Затем найдем минимальный элемент а такой, что a < оо и a ^ с, и минимальный элемент b такой, что b < bo и b ^ с. • Непосредственно отсюда получаются следующие два результата, ко торые характеризуют полудистрибутивность вниз как своего рода свойство слабой ограниченности снизу. Т Е О Р Е М А 6. Пусть L — конечная региетка. Тогда в L наруша ется условие SDy в том и только в том случае, если существуют раз личные элементы a, b € J(L) и х 6 L, для которых имеют место соот ношения a V х = Ь V х, a j£ Ь* V ж ub j£ a* V x, С Л Е Д С Т В И Е 7. Если L — конечная решетка, в которой наруша ется условие SD V , то L не является ограниченной снизу. Более точно, существуют a, b 6 J(L) такие, что цикл aDbDa и тот Dice элемент х в обоих случаях.
проходит через один
90
Дж. В. Нейшен
Рис. На рисунке представлена решетка, в которой выполняется условие SD V и в которой содержится короткий цикл aDbDa элементы
через различные
хну.
Т Е О Р Е М А 8. Пусть L — конечная решетка, в которой выполня ется условие SD A . Тогда в L условие SD V нарушается в том и только в том случае, если существуют a, b £ J(L) такие, что
аВЫЗа.
ДОКАЗАТЕЛЬСТВО. Если в L нарушается условие SD V , то най дутся элементы a, b € J(L) и с Е L такие, как в лемме 5. Из соотношения а <ЬУ с получаем, что по крайней мере один из элементов 6, с не распо ложен под к(а). Поскольку а* < с и a jt с, то с < «(а), а поэтому 6 ^ к(а). Во всяком случае, 6* < с < «(а), значит, аВЪ. Аналогично получаем и ЬВа. П
§ 3. Контрпример Построим пример полудистрибутивной решетки, в которой выполня ются условия (Р) и (Q), при этом она не будет ограниченной. Пусть К — верхняя полурешетка с 0, порожденная элементами G ~ {а 0 , аъ а2, b0j6Ь Ь2, с0, сх,с2, х, у,z},
Неограниченные полудистрибутивные решетки
91
для которых имеют место следующие соотношения:
а0 < ах < а2,
Ь0 < Ьг < Ь2,
с0 < с\ < с2,
а 2 < ai V ж,
ах < ао V Ь2,
ai < ао V у,
Ь2 < Ьг V у,
bi < Ь0 V с2,
&! < Ь0 V г,
с2 < ci V г,
ci < с0 V а2,
ci < с0 V ж.
При построении используется LISP, и, как можно будет заметить, К со д е р ж и т 198 элементов. Мы утверждаем, что К удовлетворяет требуемым условиям. По построению, J ( К ) = G, и каждый элемент полурешетки К пред ставим как объединение некоторых из указанных элементов, причем в этом представлении встречается не более одного из а,-, одного из Ь, и одного из С{. Более того, выполняются соотношения а2 У ах У а$ У 0, как, впрочем, и аналогичные д л я Ь,--х и с;-х, а элементы ж, у и z являются атомами. Д л я проверки условия SD A в полу решетке К требуется найти к(а) д л я каждого a G G Легко проверить, что справедливы соотношения: к(а2)
=
а\ V Ь2 V с 2 V у V 2,
АС(С2)
=
а2 V Ь2 V ci V ж V у,
к(ах)
=
а 0 Vbi
AC(CI)
=
ai V Ь2 V с 0 V у V z,
к(а0)
=
Ь2 V с2 V ж V у V 2,
к(Ь2)
=
а 2 Vbi Vc2Vx
V с 2 V ж V г,
Vz,
к(со)
=
а 2 V Ь2 V ж V у V г,
к(ж) =
а 2 V 62 V с2 V у V г,
к(Ьх) =
а 2 V Ьо V ct V х V у,
к(у)
=
а 2 V Ь2 V с2 V ж V г,
ю(Ьо) =
а 2 V с2 V ж V у V г,
к(г)
=
а 2 V Ь2 V с2 V ж V у.
Отсюда получаем, что все пары элементов, связанные отношениями Л и В в К , содержатся в списке: a2Aai,
ajAao,
a 2 Aao,
а25ж,
а\ВЪ2,
a>iBy,
6 2 A6i,
6i Або,
62 А&о
Ъ2Ву,
ЬгВс2,
biBz,
с2Асъ
схАсо,
с2Ас0,
c2Bz,
CiBa2,
c\Bx.
(Именно эти соотношения и следовало ожидать, принимая во внимание ис ходные. Существуют еще три нетривиальных покрытия, которые следуют
92
Дж. Б. Нейшен
из указанных соотношений, а именно: покрытие аг < а0 V Ь\ V у и симмет ричные к нему, но все они не дают новых пар в отношениях зависимости.) Суммируя вышесказанное, заметим, что в К выполняется условие SD V , поскольку отсутствуют циклы вида dBeBd.
Тем не менее, К не
является ограниченной, поскольку имеет место цикл «2 A (Xi В &2 А Ь% В С2 А с\ В а2. Условие (Р) очевидно, условие (Q) легко проверяется после представления
его в виде: к{е) > n{d) влечет dBe.
ЛИТЕРАТУРА 1. R.Freese, J.Jezek, J. В. Nation, Free lattices (Math. Surv. Monogr., 42), Providence, RI, Amer. Math. Soc, 1995. 2. J. B, Nation, Bounded finite lattices, in: Universal Algebra (Colloq. Math. Soc. Janos Bolyai, 29), Amsterdam, North-Holland Publ. Co., 1977, 531-533. 3. N. Gaspard, The lattice of permutations is bounded, Discrete Math. Theor. Comput. 8ci,, to appear» 4. N. Caspard) A characterization theorem for all interval doubling schemes of the lattice of permutations, Discrete Math. Theor. Comput. Sci., to appear.
Адрес автора: NATION, James Bryant, Department of Mathematics, University of Hawaii, Honolulu, HI 96822, USA e-mail:
[email protected]
Поступило 21 июля 1999 г.
