Подрешетки решеток выпуклых подмножеств векторных пространств

Алгебра и логика, 43, N 3 (2004), 261—290

УДК 512.56

ПОДРЕШЕТКИ РЕШЕТОК ВЫПУКЛЫХ ПОДМНОЖЕСТВ ВЕКТОРНЫХ ПРОСТРАНСТВ∗)

Ф. ВЕРУНГ, М. В. СЕМЁНОВА Введение Вопрос о возможности вложить решетки из одного класса, в решетки из другого класса (или вопрос об описании подрешеток решеток, лежащих в заданном классе) имеет долгую историю. В этом направлении было получено много замечательных результатов. Среди первых, ставших к настоящему времени классическими, следует отметить результат из [1] о том, что любую решетку можно вложить в решетку разбиений некоторого множества. Вопрос о возможности вложить любую конечную решетку в решетку разбиений конечного множества долго оставался без ответа и был решен положительно в [2]. В [3] исследовался вопрос о вложении решеток в так называемые выпуклые геометрии, т. е. решетки замкнутых подмножеств пространств замыкания, обладающих свойством антизамены. Хорошо известно, что любая конечная выпуклая геометрия полудистрибутивна вверх, т. е. удовлетворяет квазитождеству ∗)

Работа

выполнена

при

финансовой

поддержке

фондов

GA CR,

проект

201/00/0766, и MSM, проект J13/98:1132000007a. Второй автор был также поддержан фондом ИНТАС, проект YSF:2001/1-65, РФФИ–DFG, проект 01-01-04003, Минобразованием РФ, проект Е02-1.0-32, Советом по грантам Президента РФ и государственной поддержке ведущих научных школ, проект НШ-2112.2003.1, а также Фондом поддержки отечественной науки.

c Сибиpский фонд алгебpы и логики, 2005

262

Ф. Верунг, М. В. Семёнова ∀xyz x ∨ y = x ∨ z → x ∨ y = x ∨ (y ∧ z).

Более того, в [3, теор. 1.11] показано, что любая конечная полудистрибутивная вверх решетка вложима в некоторую конечную выпуклую геометрию. В упомянутой работе среди прочего изучался один конкретный класс выпуклых геометрий, а именно, решетки алгебраических подмножеств полных решеток, и было доказано, что любая конечная полудистрибутивная вверх решетка вложима в решетку алгебраических подмножеств некоторой алгебраической и коалгебраической полной решетки A. В общем случае A может оказаться бесконечной. В связи с этим результатом в [3] была сформулирована следующая ПРОБЛЕМА. Существует ли класс U конечных выпуклых геометрий конкретного типа, содержащий все конечные полудистрибутивные вверх решетки в качестве подрешеток? Другими словами, существует ли класс U выпуклых геометрий конкретного типа такой, что любая полудистрибутивная вверх решетка вложима в некоторую решетку из U? Ответ на этот вопрос для класса решеток подполурешеток конечных полурешеток следует из результата, полученного независимо в [4] и [5], который утверждает, что конечная решетка вложима в решетку подполурешеток некоторой конечной (полу)решетки тогда и только тогда, когда она ограничена снизу. Другой результат того же характера получен в [6] (см. также [7]): конечная решетка вложима в решетку подпорядков некоторого конечного частично упорядоченного множества тогда и только тогда, когда она ограничена снизу. Заметим, что класс конечных ограниченных снизу решеток является собственным подклассом в классе конечных полудистрибутивных вверх решеток (см. [8]). Точное определение ограниченной снизу решетки дается в § 1. В качестве возможных вариантов ответа на поставленную проблему в [3] были предложены следующие классы: (1) класс конечных точечных полудистрибутивных вверх биатомных решеток;

Подрешетки решеток выпуклых подмножеств векторных пространств 263 (2) класс конечных решеток вида Co(P ), где Co(P ) обозначает решетку выпуклых подмножеств частично упорядоченного множества P ; (3) класс решеток вида Co(Rn , Ω) = {X ∩ Ω | X выпукло в Rn }, где n < ω, а множество Ω ⊆ Rn конечно. Класс (1) оказывается слишком узким, чтобы выступать в роли U (см. [9]), класс (2) еще более узок. В [10] дано описание подрешеток конечных решеток вида Co(P ). Это в точности все конечные решетки, удовлетворяющие трем тождествам, обозначаемым в [10] через (S), (U), (B). Вопрос о том, можно ли выбрать класс (3) в качестве такого универсального класса U для класса конечных полудистрибутивных вверх решеток, остается открытым (см. вопрос 1). В данной работе показывается, что любая решетка вложима в решетку выпуклых подмножеств некоторого векторного пространства (см. теор. 9.1). Кроме того, частично подтверждается гипотеза об ”универсальности“ класса (3), а именно, устанавливается, что любая конечная ограниченная снизу решетка вложима в решетку Co(Rn , Ω) для некоторых n < ω и конечного множества Ω ⊆ Rn . Доказательство обоих основных результатов работы использует одну и ту же конструкцию, которая описана в §§ 2—8. Все рассматриваемые векторные пространства будут строиться с использованием так называемых раскрашенных деревьев (см. опр. 2.1). Вершинами деревьев являются конечные последовательности неразложимых элементов исходной решетки. Отметим, что эта конструкция имеет много общего с конструкцией [4], где из конечных последовательностей неразложимых элементов исходной конечной ограниченной снизу решетки построена конечная нижняя полурешетка (см. также [3, § 2.1]). Элементы дерева T нумеруют базис свободного векторного пространства F(T ) от |T | порождающих. Используя правило преобразования −→∗ , применяемое к векторам, лежащим в по(T )

ложительном конусе F+ пространства F(T ) , получаем новые отношения, связывающие векторы исходного базиса (см. § 2). Это правило преобразования обладает свойством конфлюэнтности (лемма 4.2), что позволяет определить отношение эквивалентности, полагая два вектора эквивалент-

264

Ф. Верунг, М. В. Семёнова

ными, если их можно привести к одному и тому же вектору посредством правила преобразования (см. обознач. 4.3 и предлож. 4.4). Полученное отношение эквивалентности определяет векторное подпространство NT пространства F(T ) ; все построения будут проводиться в фактор-пространстве VT = F(T ) /NT (см. § 6). Технические результаты настоящей работы можно разделить на две группы. К первой группе относятся общие результаты, полученные для векторного пространства F(T ) , построенного по произвольному дереву T . В частности, это позволяет выразить равенство двух векторов из F(T ) по модулю NT через правило преобразования (см. предлож. 4.4 и теор. 6.2). Эти результаты не относятся к теории решеток и имеют комбинаторный характер. Вторую группу составляют результаты, касающиеся теории решеток. Они связаны с построением раскрашенного дерева T по исходной решетке L, которое позволяет вложить L в Co(VT ). Основным результатом здесь является теорема 8.2, ее доказательство использует понятие L-нормы, определенной на дереве T . В § 10 устанавливаются отношения между вложением в Co(V ) и в Co(V, Ω), в § 11 приводятся открытые вопросы. Заметим, что ранее А. Хун изучал класс решеток выпуклых подмножеств векторных пространств, например, в [11], где показано, что для (n − 1)-мерного векторного пространства V решетка Co(V ) принадлежит многообразию, порожденному всеми конечными n-дистрибутивными решетками, поэтому сама является n-дистрибутивной, хотя и не является (n − 1)-дистрибутивной (см. также [12]). Описание главных идеалов решеток выпуклых подмножеств конечномерных пространств дано в [13].

§ 1. Основные понятия Напомним некоторые основные понятия, изложенные в [8]. Для произвольной (верхней) полурешетки L полагаем L− = L \ {0}, когда L имеет наименьший элемент 0, и L− = L в противном случае. Для подмножеств

Подрешетки решеток выпуклых подмножеств векторных пространств 265 X и Y полурешетки L пишем X ≪ Y , если каждый элемент из X меньше либо равен некоторому элементу из Y . Если a ∈ L− , то нетривиальным покрытием элемента a называется конечное множество X ⊆ L− такое, что a ≤ ∨X и a  x для всех x ∈ X. Нетривиальное покрытие X элемента a минимально, если для любого нетривиального покрытия Y для a условие Y ≪ X влечет X ⊆ Y . Пусть J(L) обозначает множество всех неразложимых элементов полурешетки L. Если a, b ∈ J(L), то пишем aDb, если b принадлежит некоторому минимальному покрытию элемента a. Последовательность a0 , . . . , an−1 элементов из J(L) называется D-циклом, если a0 D . . . . . . Dan−1 Da0 . Гомоморфизм h : K → L ограничен снизу, если для любого a ∈ L множество {x ∈ K | h(x) ≥ a} либо пусто, либо содержит наименьший элемент. Конечно порожденная решетка L называется ограниченной снизу, если она является ограниченным снизу гомоморфным образом некоторой конечно порожденной свободной решетки. Для конечной решетки L это равносильно отсутствию D-циклов в L. Для частично упорядоченных множеств K и L говорим, что отображение f : K → L сохраняет нуль, если f (0K ) является наименьшим элементом L в случае, когда K содержит наименьший элемент 0K . Говорим, что f сохраняет существующие пересечения, если для любого X ⊆ K, имеющего точную нижнюю грань, множество f [X] также имеет точную нижнюю грань и ∧f [X] = f (∧X). Если F – линейно упорядоченное тело, а n > 0, множество ) ( X + n ξi = 1 ∆n (F) = (ξi )i
(1.1)

i
называют (n − 1)-симплексом в Fn .

Пусть V — векторное пространство над линейно упорядоченным телом F. Для всех x, y ∈ V полагаем [x, y] = {ξ0 x + ξ1 y | (ξ0 , ξ1 ) ∈ ∆2 (F)}. Подмножество X векторного пространства V выпукло, если [x, y] ⊆ X для

266

Ф. Верунг, М. В. Семёнова

всех x, y ∈ X. Пусть далее Co(V ) — решетка выпуклых подмножеств в V , упорядоченных по включению. Если X ⊆ V , то через Co(X) обозначается выпуклая оболочка множества X. Очевидно, ) ( X Co(X) = ξi xi 0 < n < ω, (ξi )i
Для Ω ⊆ V полагаем

Co(V, Ω) = {X ∩ Ω | X ∈ Co(V )}. Нетрудно видеть, что Co(V, Ω) является решеткой; более того, Co(V, Ω) изоморфна решетке выпуклых подмножеств так называемой выпуклой геометрии (см. [3]). Как показывает следующее предложение, неразложимыми элементами решетки Co(V, Ω) являются лишь одноэлементные множества. ПРЕДЛОЖЕНИЕ 1.1. Пусть V — векторное пространство над линейно упорядоченным телом F, Ω ⊆ V . Тогда неразложимыми элементами решетки Co(V, Ω) являются в точности множества вида {p}, где p ∈ Ω. ДОКАЗАТЕЛЬСТВО. Очевидно, что одноэлементные подмножества Ω (вполне) неразложимы. Пусть P — неразложимый элемент в Co(V, Ω) и найдутся различные a, b ∈ P . Существует линейный функционал f : V → → F такой, что f (a) < f (b). Положим X = {x ∈ P | f (x) ≤ f (a)}, Y = {x ∈ P | f (x) > f (a)}. Тогда X, Y ∈ Co(V, Ω), P = X ∪ Y = X ∨ Y и X, Y 6= P , получаем противоречие. 2 Если G — частично упорядоченная абелева группа, полагаем G+ = {x ∈ G | 0 ≤ x}, G++ = G+ \ {0}. В дальнейшем нам потребуется несколько операций на ординалах: через (α, β) 7→ αβ обозначается возведение в степень, (α, β) 7→ α ∔ β — сложение, (α, β) 7→ α·β — умножение и (α, β) 7→ α+β — сумма Хессенберга (см. [14]).

Подрешетки решеток выпуклых подмножеств векторных пространств 267 Согласно определению если k, n0 , . . . , nk−1 , p0 , . . . , pk−1 , q0 , . . . , qk−1 — натуральные числа с условием n0 > n1 > . . . > nk−1 , а α = ω n0 · p0 ∔ . . . ∔ ω nk−1 · pk−1 , β = ω n0 · q0 ∔ . . . ∔ ω nk−1 · qk−1 , то сумма Хессенберга α и β равна α + β = ω n0 · (p0 + q0 ) ∔ . . . ∔ ω nk−1 · (pk−1 + qk−1 ). В частности, эта операция коммутативна, ассоциативна и обладает свойством сокращения; кроме того, если n0 > n1 > . . . > nk−1 , то X

ω ni = ω n0 ∔ . . . ∔ ω nk−1 .

i
§ 2. Свободное векторное пространство, связанное с раскрашенным деревом Пусть (T, E) — частично упорядоченное множество. Через ⊳ будем обозначать строгий частичный порядок на T . Если a, b ∈ T , то говорим, что a является нижним покрытием b и пишем a ≺ b, если a ⊳ b и нет элемента x ∈ T со свойством a ⊳ x ⊳ b. В случае, когда b имеет ровно одно нижнее покрытие, обозначим последнее через b∗ . ОПРЕДЕЛЕНИЕ 2.1. Деревом называется частично упорядоченное множество (T, E), для которого множество ↓p = {q ∈ T | q E p} является конечной цепью для всех p ∈ T , полагаем ht(p) = |↓ p | − 1 для всех p ∈ T . Раскраской дерева (T, E) называется отношение эквивалентности ∼ на T со следующими свойствами: (i) смежный класс [p] по отношению ∼ конечен и содержит по крайней мере два элемента для любого p ∈ T , не являющегося минимальным; (ii) если p, q ∈ T и p ∼ q, то либо p и q минимальны, либо p∗ = q∗ . Раскрашенным деревом называется тройка (T, E, ∼), где (T, E) — дерево, а ∼ является раскраской на T .

268

Ф. Верунг, М. В. Семёнова Если (T, E, ∼) — раскрашенное дерево, полагаем MT = {(p, [q]) | p, q ∈ T и p ≺ q}; MT (p) = {[q] | q ∈ T и p ≺ q} для всех p ∈ T. Для любого линейно упорядоченного тела F рассмотрим свободное

векторное пространство F(T ) со множеством порождающих T , элементами которого являются отображения x : T → F такие, что множество supp(x) = = {p ∈ T | x(p) 6= 0} конечно. Через (p) ˙ p∈T обозначается естественный базис пространства F(T ) . Считаем, что F(T ) упорядочено покомпонентно, т. е. x ≤ y, если x(p) ≤ y(p) для всех p ∈ T. F(T ) с определенным таким образом порядком является решеточно упо(T )

рядоченным векторным пространством над F. Через F+

обозначается

положительный конус F(T ) , т. е. (T )

F+ = {x ∈ F(T ) | x(p) ≥ 0 для всех p ∈ T }. Для каждой пары (p, I) ∈ MT определим бинарные отношения −→ и −։ (p,I)

на

(T ) F+

(p,I)

по правилам: (T )

если λ ∈ F+ , а z ∈ F+ , то x −→ y ⇔ x = (p,I)

λ X q˙ + z, а y = λp˙ + z; |I| q∈I

(T )

если λ ∈ F+ , z ∈ F+ и z(q0 ) = 0 для некоторого q0 ∈ I, то x −։ y ⇔ x = (p,I)

λ X q˙ + z, а y = λp˙ + z. |I| q∈I

Если x −→ y, то говорим, что y является результатом свертки x в p. Оче(p,I) P ω ht(p) (сумма Хесвидно, x −։ y влечет x −→ y. Полагаем ν(x) = (p,I)

сенберга) для всех x ∈

(p,I)

p∈supp(x)

(T ) F+ .

(T )

Определим по индукции бинарное отношение −→n на F+ . Пусть −→0 является отношением равенства, а x−→1 y в том и только том случае,

Подрешетки решеток выпуклых подмножеств векторных пространств 269 если x −→ y для некоторого (p, I) ∈ MT . Далее, положим x −→n+1 y, если (p,I) 1 x−→ z−→n y

(T )

для некоторого z ∈ F+ . Кроме того, пусть x −→∗ y, если

x−→n y для некоторого n < ω. Отношения −։n и −։∗ определяются аналогично.

§ 3. Свойство сокращения для отношений типа −→ Зафиксируем раскрашенное дерево (T, E, ∼). Здесь используются понятия из § 2. (T )

ОПРЕДЕЛЕНИЕ 3.1. Бинарное отношение R на F+ называется (T )

аддитивным, если xRy влечет (x + z)R(y + z) для всех x, y, z ∈ F+ ; (T )

однородным, если xRy влечет λxRλy для всех x, y ∈ F+ и λ ∈ F+ . (T )

Бинарное отношение R на F+

обладает свойством сокращения, если (T )

(x + z)R(y + z) влечет xRy для всех x, y, z ∈ F+ . Очевидно, что имеет место ЛЕММА 3.2. Отношения −→, −→1 , −→n и −→∗ являются адди(p,I)

тивными и однородными для всех n < ω и (p, I) ∈ MT . (T )

ЛЕММА 3.3. Пусть x, y, z ∈ F+ и (p, I), (q, J) ∈ MT . Если x −→ (p,I)

−→y −→ z и p ∈ / J, то существует (p,I)

(q,J)

y′

∈

(T ) F+

такой, что x −→

ДОКАЗАТЕЛЬСТВО. По условию найдутся λ, µ ∈

y′

−→ z.

(q,J) (p,I) (T ) + F и u, v ∈ F+

такие, что справедливы равенства x=

λ X ′ p˙ + u, |I| ′

(3.1)

p ∈I

y = λp˙ + u =

µ X ′ q˙ + v, |J| ′

(3.2)

q ∈J

z = µq˙ + v.

(3.3)

Из условия (3.2) и предположения о том, что p ∈ / J, вытекает существова(T )

ние w ∈ F+ такого, что u=

µ X ′ q˙ + w и v = λp˙ + w. |J| ′ q ∈J

270

Ф. Верунг, М. В. Семёнова λ |I|

Согласно (3.1) и (3.3) имеем x = поэтому x −→ y ′ −→ z, где y ′ = (q,J)

(p,I)

λ |I|

P

p˙′ +

p′ ∈I

P

µ |J|

q˙′ + w, z = λp˙ + µq˙ + w,

P

q ′ ∈J

p˙′ + µq˙ + w. 2

p′ ∈I

ПРЕДЛОЖЕНИЕ 3.4. Отношения −→n (n < ω) и −→∗ обладают свойством сокращения. ДОКАЗАТЕЛЬСТВО. Достаточно показать, что −→n обладает свойством сокращения. Воспользуемся индукцией по n. Утверждение очевидно для n = 0. Пусть n = 1. Поскольку −→1 однородно (см. лемму 3.2), до(T )

статочно показать, что p˙ + x −→ p˙ + y влечет x −→ y для всех x, y ∈ F+ , (q,I)

p ∈ T и (q, I) ∈ MT . По условию существуют λ p˙ + x =

(q,I) ∈ F+

(T )

и u ∈ F+ такие, что

λ X r˙ + u, |I|

(3.4)

r∈I

p˙ + y = λq˙ + u.

(3.5) (T )

Если p 6= q, тогда согласно (3.5) существует v ∈ F+ такой, что u = p˙ + v. Если p = q, то p ∈ / I; поэтому и по (3.4) имеем u = p˙ + v для некоторого (T )

v ∈ F+ . В любом случае x −→ y. Это завершает рассуждение в случае (q,I)

n = 1. Предположим, что n > 1 и утверждение верно для n − 1. Пусть (T )

p˙ + x−→n p˙ + y, где p ∈ T и x, y ∈ F+ . Покажем, что x−→n y. Существует (T )

z ∈ F+

такой, что p˙ + x −→n−1 z−→1 p˙ + y. Тогда z = z(p)p˙ + z ′ для (T )

некоторого z ′ ∈ F+ с условием z ′ (p) = 0. Согласно предположению индукции получаем x −→n−1 (z(p) − 1)p˙ + +z ′ −→1 y, если z(p) > 1, и (1 − z(p))p˙ + x −→n−1 z ′ −→1 (1 − z(p))p˙ + y, если z(p) < 1. В первом случае x−→n y, что и требовалось. Поэтому можем предполагать, что p+x ˙ −→n−1 z−→1 p+y, ˙ где z(p) = 0. Поскольку z−→1 p+ ˙ +y и z(p) = 0, то z −→ p˙ + y для некоторого I ∈ MT (p). Из p˙ + x −→n−1 z следует

(p,I)

p˙ + x = z0 −→ z1 −→ . . . (p1 ,I1 )

(p2 ,I2 )

−→

(pn−1 ,In−1 )

zn−1 = z,

где (p1 , I1 ), . . . , (pn−1 , In−1 ) ∈ MT . Поскольку z0 (p) > 1 > 0 и zn−1 (p) = 0, существует наибольшее k ∈ {1, . . . , n − 1} такое, что zk (p) > 0; более того, k < n − 1. Из соотношений zk

−→

(pk+1 ,Ik+1 )

zk+1 и zk+1 (p) = 0 получаем

Подрешетки решеток выпуклых подмножеств векторных пространств 271 pk+1 = p∗ . В частности, ht(pk+1 ) < ht(p). Пусть l — наибольший элемент множества {1, . . . , n−1} с условием, что ht(pl ) минимально; очевидно, ht(pl ) < ht(p). Применяя лемму 3.3 к соотношениям zl−1 −→ zl (pl ,Il )

−→

(pl+1 ,Il+1 )

...

−→

(pn−1 ,In−1 )

zn−1 = z −→ p˙ + y, (p,I)

(и замечая, что pl ∈ / Il+1 ∪ . . . ∪ In−1 ∪ I), получаем zl−1

−→

(pl+1 ,Il+1 )

zl′

−→

(pl+2 ,Il+2 )

′ . . . −→ zn−1 −→ p˙ + y (p,I)

(pl ,Il )

(T )

′ ′ . Условия ∈ F+ . Тогда p˙ + x −→n−1 zn−1 для некоторых zl′ , . . . , zn−1 ′ ′ ′ zn−1 −→ p˙ + y и ht(pl ) < ht(p) влекут zn−1 (p) > 1, поэтому zn−1 = p˙ + u (pl ,Il )

(T )

для некоторого u ∈ F+ . Таким образом, p˙ + x −→n−1 p˙ + u−→1 p˙ + y, и по индукционному предположению получаем x −→n−1 u−→1 y, т. е. x−→n y. 2

§ 4. Конфлюэнтность отношения −→1 , отношение ≡ (T )

ЛЕММА 4.1. Пусть u, v, x ∈ F+ . Если x−→1 u и x−→1 v, то (T )

u−→1 w и v−→1 w для некоторого w ∈ F+ . ДОКАЗАТЕЛЬСТВО. По условию существуют λ, µ ∈ F+ , (p, I), (T )

(q, J) ∈ MT и u′ , v ′ ∈ F+

такие, что при m = |I| и n = |J| имеем ра-

венства u = λp˙ + u′ ,

(4.1)

v = µq˙ + v ′ ,

(4.2)

µX ′ λ X ′ p˙ + u′ = q˙ + v ′ . x= m ′ n ′ p ∈I

(4.3)

q ∈J

Без ограничения общности можем считать, что λ 6 µ. Рассмотрим два возможных случая. С л у ч а й 1: I = J. Поскольку T — дерево, то p = q. Из (4.3) вытекает P ′ u′ = p˙ + v ′ , поэтому µ−λ m

p′ ∈I

u = λp˙ +

µ−λ X ′ p˙ + v ′ и v = µp˙ + v ′ = λp˙ + (µ − λ)p˙ + v ′ , m ′ p ∈I

272

Ф. Верунг, М. В. Семёнова

следовательно, полагая w = v, имеем u−→1 v, что и требовалось. С л у ч а й 2: I 6= J. Поскольку I и J являются классами эквивалент(T )

ности по ∼, имеем I ∩ J = ∅, поэтому и по (4.3) найдется t ∈ F+ такой, что u′ =

µX ′ λ X ′ q˙ + t и v ′ = p˙ + t, n ′ m ′ q ∈J

p ∈I

откуда, применяя (4.1) и (4.2), получаем u = λp˙ +

λ X ′ µX ′ q˙ + t и v = p˙ + µq˙ + t. n ′ m ′ q ∈J

p ∈I

Значит, u−→1 w и v−→1 w, где w = λp˙ + µq˙ + t. 2 Применением простой индукции получается (T )

ЛЕММА 4.2. Пусть u, v, x ∈ F+ , m, n < ω. (i) Если x−→m u и x−→n v, то u−→n w и v−→m w для некоторого (T )

w ∈ F+ . (ii) Если x−→∗ u и x−→∗ v, то u−→∗ w и v−→∗ w для некоторого w ∈ (T )

∈ F+ . (T )

ОБОЗНАЧЕНИЕ 4.3. Для x, y ∈ F+ полагаем x ≡ y, если существу(T )

ет u ∈ F+ со свойством x−→∗ u и y−→∗ u. Из леммы 4.2(ii) немедленно следует ПРЕДЛОЖЕНИЕ 4.4. Отношение ≡ является отношением эк(T )

вивалентности на F+ .

§ 5. Отношения −։n и элемент x♯ Здесь применяется отношение −։n , определенное в § 2. ЛЕММА 5.1. Если x−։∗ y и x 6= y, то ν(x) > ν(y) для всех x, y ∈ (T )

∈ F+ . ДОКАЗАТЕЛЬСТВО. Достаточно рассмотреть случай x−։1 y. Существуют разложения x=

λ X q˙ + u и y = λp˙ + u, |I| q∈I

Подрешетки решеток выпуклых подмножеств векторных пространств 273 (T )

где λ ∈ F++ , (p, I) ∈ MT , u ∈ F+ и u(q0 ) = 0 для некоторого q0 ∈ I. Тогда supp(x) = supp(u) ∪ I и supp(y) = supp(u) ∪ {p}, где q0 ∈ I \ supp(u). Используя определение суммы Хессенберга, получаем ν(y) ≤ ν(u) + ω ht(p) < ν(u) + ω ht(q0 ) (поскольку ht(q0 ) = ht(p) + 1) ≤ ν(x) (поскольку u(q0 ) = 0). 2 (T )

(T )

ЛЕММА 5.2. Для любых x ∈ F+ , (p, I) ∈ MT существует y ∈ F+ такой, что x −։ y. (p,I)

λ P q˙ + u, где λ = |I| · min{x(q) | ДОКАЗАТЕЛЬСТВО. Имеем x = |I| q∈I P λ q. ˙ Если y = λp˙ + u, то x −։ y. 2 q ∈ I} и u = x − |I| (p,I)

q∈I

(T )

ЛЕММА 5.3. Пусть x, y, z ∈ F+ , (p, I) ∈ MT . Если z−։ x и z−→ y, (p,I)

(p,I)

то y −։ x. Более того, y 6= z влечет x 6= z. (p,I) (T )

ДОКАЗАТЕЛЬСТВО. Существуют λ, µ ∈ F+ и u, v ∈ F+ такие, что выполняются следующие равенства (здесь n = |I|): x = λp˙ + u;

(5.1)

y = µp˙ + v; µX λX q˙ + u = q˙ + v, z= n n

(5.2)

q∈I

(5.3)

q∈I

причем u(q0 ) = 0 для некоторого q0 ∈ I. Из (5.3) вытекает, что µ 6 λ, P откуда v = λ−µ q˙ + u, n q∈I

x = λp˙ + u и y = µp˙ +

λ−µX q˙ + u, n q∈I

где u(q0 ) = 0, т. е. y −։ x. (p,I)

Если y 6= z, то µ > 0 и λ > 0, т. е. x 6= z. 2 (T )

ОПРЕДЕЛЕНИЕ 5.4. Для любого x ∈ F+ полагаем (T )

Φ(x) = {y ∈ F+ | x−→∗ y}, Φ∗ (x) = {y ∈ Φ(x) | Φ(y) = {y}}.

274

Ф. Верунг, М. В. Семёнова (T )

ЛЕММА 5.5. Для всех x ∈ F+

множество Φ∗ (x) содержит в

точности один элемент. ДОКАЗАТЕЛЬСТВО. Выберем u в Φ(x) такой, что ν(u) минимально. Пусть u−→∗ v для некоторого v 6= u. Тогда найдется v 6= u с условием u−→1 v; таким образом, согласно леммам 5.2 и 5.3 существует v 6= u такой, что u−։1 v. По лемме 5.1 имеем ν(v) < ν(u), что противоречит минимальности ν(u). Поэтому u лежит в Φ∗ (x). Единственность следует из леммы 4.2. 2 ОПРЕДЕЛЕНИЕ 5.6. Единственный элемент из Φ∗ (x) назовем нор(T )

мальной формой вектора x ∈ F+ и обозначим его через x♯ . Говорим, что вектор x нормален, если x = x♯ . В силу определения из x−→∗ y вытекает x♯ = y ♯ . Легко доказывается следующая ЛЕММА 5.7. (i) Любой вектор вида λp, ˙ где λ ∈ F+ и p ∈ T , нормален. (T )

(ii) Если вектор x нормален, то любой вектор y ∈ F+ такой, что y ≤ x, нормален. ЗАМЕЧАНИЕ 5.8. Можно показать, что отношение −→∗ в действительности является антисимметричным. Однако здесь этот факт нигде не используется. (T )

ЛЕММА 5.9. Если x−→∗ nx♯ , то x−։n x♯ для всех x ∈ F+ и n < ω. ДОКАЗАТЕЛЬСТВО проводится индукцией по n. Если n = 0, то (T )

x = x♯ . Пусть n > 0. Тогда существуют y ∈ F+ и (p, I) ∈ MT такие, что (T )

x −→ y−→n−1 x♯ . Согласно лемме 5.2 найдется z ∈ F+ с условием x −։ z. (p,I)

(p,I)

По лемме 5.3 имеем y −։ z, а по лемме 4.2 существует w ∈ (p,I)

(T ) F+

такой,

что x♯ −→1 w и z−→n−1 w. Тогда w = x♯ и z−→n−1 x♯ . Поскольку x♯ = z ♯ и согласно индукционному предположению, получаем x−։1 z−։n−1 x♯ . 2 § 6. Теорема о сокращении Докажем сначала, что имеет место (T )

ЛЕММА 6.1. Пусть x, y ∈ F+ , вектор x нормален, p ∈ T , λ ∈ F+ .

Подрешетки решеток выпуклых подмножеств векторных пространств 275 (T )

1 y и λp+x Если λp+x−։ ˙ ˙ 6= y, то λ > 0, x(p) = 0 и существуют x′ ∈ F+

и ξ ∈ (0, λ] такие, что выполняются следующие условия (здесь I = [p]\{p} и l = |I|): (i) x = ξ

P

q˙ + x′ и y = (λ − ξ)p˙ + (l + 1)ξ p˙∗ + x′ ;

q∈I

(ii) вектор (λ − ξ)p˙ + x′ нормален; (iii) ((λ − ξ)p˙ + x′ )(q) = x(q) для всех q ∈ T с условием ht(p) < ht(q). ДОКАЗАТЕЛЬСТВО. Если λ = 0, то (поскольку x нормален) y = x, приходим к противоречию; отсюда λ > 0. Пусть x(p) > 0. Тогда существует ε ∈ F++ такой, что ελp˙ ≤ (1 − ε)x, поэтому ε(λp˙ + x) ≤ x. Поскольку x нормален и по лемме 5.7(ii), заключаем, что λp˙ + x нормален, это противоречит условиям λp˙ + x−։1 y и λp˙ + x 6= y. Поэтому x(p) = 0. Положим I = {pi | 0 6 i < l}. Пусть ξ ′ — наименьший элемент множества {x(pi ) | i < l}, а ξ = min{ξ ′ , λ}. Поскольку x нормален, свертка вектора λp˙ + x к вектору y действует в p∗ . Таким образом, существуют следующие разложения: λp˙ + x = (λ − ξ)p˙ + ξ p˙ + ξ

X

p˙i + x′ ,

(6.1)

i
y = (λ − ξ)p˙ + (l + 1)ξ p˙∗ + x′ ,

(6.2)

(T )

где x′ ∈ F+ и x′ (pj ) = 0 для некоторого j < l, и ξ > 0, поскольку y 6= λp˙ + x.

Вектор (λ − ξ)p˙ + x′ является нормальным. Действительно, в противном случае ξ < λ, и рассуждая как выше, получаем существование P ξ ′′ ∈ F++ , для которого x′ ≥ ξ ′′ p˙i , что противоречило бы условию x′ (pj ) = 0.

i
Согласно (6.1) для любого q ∈ T с условием ht(p) < ht(q), справедливо равенство x(q) = x′ (q), откуда ((λ − ξ)p˙ + x′ )(q) = x(q). 2 ТЕОРЕМА 6.2 (о сокращении). Отношение ≡ обладает свойством сокращения. ДОКАЗАТЕЛЬСТВО. Напомним, что отношение ≡ является отношением эквивалентности (см. предлож. 4.4). Согласно лемме 3.2 оно аддитивно. Поэтому остается показать, что x ≡ y, если x, y ∈ F(T ) , p ∈ T и p˙ + x ≡ p˙ + y. Поскольку x ≡ x♯ и y ≡ y ♯ , достаточно рассмотреть

276

Ф. Верунг, М. В. Семёнова

случай, когда x и y нормальны. Тогда p˙ + x−→∗ u, а p˙ + y−→∗ u, где u = (p˙ + x)♯ = (p˙ + y)♯ и все сводится к проверке следующего утверждения: (T )

если m, n < ω, p ∈ T , а векторы x, y, u ∈ F+ +x−→m u

и p˙ +

y−→n u

нормальны, то p˙ +

влекут x = y.

Осуществим это индукцией по m + n. Если m = 0, то p˙ + y−→n p˙ + x, и согласно предложению 3.4 имеем y−→n x. Поскольку y нормален, получаем x = y, что и требовалось. То же самое справедливо для n = 0. Пусть m, n > 0. Из леммы 5.9 следует, что p˙ + x−։m u и p˙ + y−։n u. Поэтому существуют последовательности p˙ + x = x0 −։1 x1 −։1 . . . −։1 xm−1 −։1 xm = u,

(6.3)

p˙ + y = y0 −։1 y1 −։1 . . . −։1 yn−1 −։1 yn = u,

(6.4)

(T )

где x0 , . . . , xm , y0 , . . . , yn ∈ F+ . Если два члена одной из этих последовательностей совпадают, то либо p˙ + x−։m−1 u, либо p˙ + y−։n−1 u, и x = y согласно индукционному предположению. Предположим, что каждая из последовательностей (6.3) и (6.4) состоит из различных элементов. Пусть (qi )i
x, y ∈ F+ , i0 < m и j0 < n такие, что верны равенства X

q˙i + x;

(6.5)

x1 = (1 − ξ)p˙ + (l + 1)ξ p˙∗ + x; X q˙i + y; p˙ + y = (1 − η)p˙ + η p˙ + η

(6.6) (6.7)

y1 = (1 − η)p˙ + (l + 1)η p˙∗ + y;

(6.8)

x(qi0 ) = y(qj0 ) = 0.

(6.9)

p˙ + x = (1 − ξ)p˙ + ξ p˙ + ξ

i
i
По лемме 6.1 имеем x(p) = y(p) = 0, и оба вектора x′1 = (1 − ξ)p˙ + x и y1′ = (1 − η)p˙ + y нормальны. Заметим, что x1 = (l + 1)ξ p˙∗ + x′1 и y1 = (l + 1)η p˙∗ + y1′ .

(6.10)

Подрешетки решеток выпуклых подмножеств векторных пространств 277 Определим по индукции p0 = p и pi+1 = (pi )∗ (для i < ω) в случае, когда (pi )∗ существует, в частности, p1 = p∗ . Применяя достаточное число раз лемму 6.1 к (6.6), получим разложения xi = λi p˙i +x′i , 1 6 i 6 m, где λi ∈ (T )

∈ F++ и вектор x′i ∈ F+

нормален, причем x′i (p) = x′1 (p) = 1 − ξ. Ана-

логично, применяя лемму 6.1 к (6.8), получим разложения yj = µj p˙j + yj′ , (T )

1 6 j 6 n, где µj ∈ F++ и вектор yj′ ∈ F+

нормален, причем yj′ (p) =

= y1′ (p) = 1 − η. В частности, 1−ξ = xm (p) = u(p) = yn (p) = 1−η, откуда ξ = η. Таким образом, x1 = (l + 1)ξ p˙∗ + x′1 и y1 = (l + 1)ξ p˙∗ + y1′ , где оба вектора x′1 и y1′ нормальны. Поскольку x1 −→m−1 u и y1 −→n−1 u, по индукционному предположению x′1 = y1′ ; отсюда x = y. Согласно (6.5) и (6.7) имеем x = y, что завершает доказательство. 2 ОБОЗНАЧЕНИЕ 6.3. Пусть NT — подпространство в F(T ) , определенное как (T )

NT = {x − y | x, y ∈ F+ и x ≡ y}. Полагаем VT = F(T ) /NT и p = p˙ + NT для всех p ∈ T . Из теоремы 6.2 прямо вытекает (T )

СЛЕДСТВИЕ 6.4. Для всех x, y ∈ F+

включение x − y ∈ NT

справедливо в том и только том случае, если x ≡ y. В частности (поскольку все элементы p˙ (p ∈ T ) нормальны) получаем СЛЕДСТВИЕ 6.5. Отображение p 7→ p взаимно однозначно.

§ 7. Пленарные множества, пленарные вложения и функционал следа ОПРЕДЕЛЕНИЕ 7.1. Подмножество Ω векторного пространства V называем пленарным, если для любого x ∈ Co(Ω) существует наименьшее (конечное) подмножество X ∈ Co(V, Ω) такое, что x ∈ Co(X). Отметим также, что для подмножества Ω пространства V каноническое отображение ϕΩ : Co(V, Ω) → Co(V ), действующее по правилу

278

Ф. Верунг, М. В. Семёнова

X 7→ Co(X), всегда является полным ∨-вложением. Непосредственно из определения вытекает ПРЕДЛОЖЕНИЕ 7.2. Подмножество Ω векторного пространства V над линейно упорядоченным телом пленарно в том и только том случае, если каноническое отображение ϕΩ из Co(V, Ω) в Co(V ) является полным вложением. ПРИМЕР 7.3. Все пространство V , а также любое аффинно независимое подмножество V являются пленарными. С другой стороны, квадрат C = {(0, 0), (0, 1), (1, 0), (1, 1)} не является пленарным множеством в Q2 (возьмем X = C \ {(1, 1)}, Y = = C \ {(1, 0)}). ОПРЕДЕЛЕНИЕ 7.4. Для полурешетки L и векторного пространства V над линейно упорядоченным телом отображение ϕ : L → Co(V ) пленарно, если ϕ = ϕΩ ◦ψ для некоторых пленарного подмножества Ω ⊆ V и ∨-гомоморфизма ψ : L → Co(V, Ω), сохраняющего существующие пересечения. Итак, любое пленарное отображение из некоторой решетки в Co(V ) является решеточным гомоморфизмом, который сохраняет существующие пересечения. Более того, в определении, приведенном выше, ϕ является вложением в том и только том случае, если ψ — вложение. До конца настоящего параграфа фиксируем линейно упорядоченное тело F и раскрашенное дерево (T, E, ∼). Будем использовать все обозначения и терминологию предыдущих параграфов, относящуюся к F(T ) , −→∗ , ≡, VT , NT , p, ˙ p и т. д. ЛЕММА 7.5. Существует единственный линейный функционал τ : VT → F со свойством τ (p) = 1 для всех p ∈ T . ДОКАЗАТЕЛЬСТВО. Пусть f : F(T ) → F — единственный линейный функционал такой, что f (p) ˙ = 1 для всех p ∈ T . Достаточно показать, что ограничение f на подпространство NT тождественно равно нулю. Для этого требуется лишь проверить, что x−→1 y влечет f (x) = f (y) для всех (T )

x, y ∈ F+ , последнее очевидно. 2

Подрешетки решеток выпуклых подмножеств векторных пространств 279 Линейный функционал τ : VT → F, существование которого установлено в лемме 7.5, назовем функционалом следа. (T )

ОБОЗНАЧЕНИЕ 7.6. Пусть ΩT = {p | p ∈ T } ⊆ VT . Для x ∈ F+ полагаем supp(x) = {p | p ∈ supp(x)} ⊆ ΩT . (T )

ЛЕММА 7.7. Если x, y ∈ F+ , x−→∗ y, то supp(y) ⊆ ΩT ∩ ∩ Co(supp(x)). ДОКАЗАТЕЛЬСТВО. Достаточно рассмотреть только случай (T )

x−→1 y и x 6= y. Тогда существуют λ ∈ F++ , (p, I) ∈ MT и u ∈ F+ таλ P кие, что x = |I| q˙ + u и y = λp˙ + u, откуда supp(y) = supp(u) ∪ {p}, а q∈I 1 P supp(x) = supp(u)∪{q | q ∈ I}. Поэтому p = |I| q лежит в Co(supp(x)). 2 q∈I

ПРЕДЛОЖЕНИЕ 7.8. Множество ΩT является пленарным под-

множеством в VT . ДОКАЗАТЕЛЬСТВО. Пусть x ∈ Co(ΩT ), Y = {p | p ∈ Y } для всех Y ⊆ T . Обозначим через x (единственный) нормальный вектор, лежащий в x. Тогда существуют m > 0, α0 , . . . , αm−1 ∈ F++ и p0 , . . . , pm−1 ∈ T такие, что x=

X

αi p˙i .

(7.1)

i<m

Поскольку x ∈ Co(ΩT ) и по лемме 7.5, имеем τ (x) = 1, т. е.

P

αi =

i<m

= 1. В силу (7.1) справедливо x ∈ Co(X), где X = {pi | i < n}.

Пусть Y ⊆ T таково, что x ∈ Co(Y ). Тогда существуют n > 0, β0 , . . . , βn−1 ∈ F++ и q0 , . . . , qm−1 ∈ Y такие, что x=

X

βj q j .

(7.2)

j
Положим y =

P

βj q˙j . Из (7.1) и (7.2) получаем x ≡ y. Поскольку x нор-

j
мален, справедливо y−→∗ x. Согласно лемме 7.7 X = supp(x) ⊆ ΩT ∩ Co(supp(y)) ⊆ Y , т. е. X — наименьшее подмножество ΩT , выпуклая оболочка которого содержит x. 2

280

Ф. Верунг, М. В. Семёнова Согласно предложению 1.1 множество неразложимых элементов в

Co(V, ΩT ) совпадает с множеством одноэлементных подмножеств в ΩT . Еще одно замечательное свойство множества ΩT устанавливает ПРЕДЛОЖЕНИЕ 7.9. Если p, q ∈ T и {p}D{q} в Co(VT , ΩT ), то p ⊳ q. В частности, отношение зависимости D на множестве неразложимых элементов решетки Co(VT , ΩT ) является фундированным (т. е. не имеет бесконечных убывающих цепей). ДОКАЗАТЕЛЬСТВО. Поскольку p ⊳ q влечет ht(p) < ht(q), достаточно показать, что {p}D{q} влечет p ⊳ q для всех p, q ∈ T . Согласно нашему предположению, p 6= q и существует X ∈ Co(VT , ΩT ) такое, что p ∈ / X и p ∈ {q} ∨ X. Таким образом, найдутся λ ∈ F, 0 < λ < 1, и x ∈ Co(X) такие, что p = (1 − λ)q + λx. Поскольку вектор p˙ нормален и согласно следствию 6.4, получаем (1 − λ)q˙ + λx−→∗ p˙ для некоторого (в действительности, любого) x ∈ x. В частности, p 6= q влечет p ⊳ q. 2 Поскольку в конечном случае отсутствие D-циклов равносильно ограниченности снизу (см. [8]), получаем СЛЕДСТВИЕ 7.10. Если дерево T конечно, то решетка Co(VT , ΩT ) конечна и ограничена снизу.

§ 8. Нормированные деревья

ОПРЕДЕЛЕНИЕ 8.1. L-нормой на T будем называть отображение e : T → L− , удовлетворяющее следующим условиям: (i) множество e[I] = {e(q) | q ∈ I} является нетривиальным покрытием элемента e(p) для всех (p, I) ∈ MT ; (ii) для любых p ∈ T и нетривиального покрытия X элемента e(p) существует I ∈ MT (p) такое, что e[I] ≪ X.

Подрешетки решеток выпуклых подмножеств векторных пространств 281 Норма e полна, если любой элемент x полурешетки L является суммой некоторых элементов из e[T ]. ТЕОРЕМА 8.2. Пусть T — раскрашенное дерево, L — произвольная полурешетка, e : T → L− — норма, F — линейно упорядоченное тело. Рассмотрим векторное пространство VT и подмножество ΩT , построенные выше, и определим ∨-гомоморфизм ψ : L → Co(VT , ΩT ) по правилу ψ(x) = {p | p ∈ T и e(p) ≤ x} для всех x ∈ L. Тогда ψ сохраняет существующие пересечения, и справедливы следующие утверждения: (i) отображение ϕ : L → Co(VT ), определенное по правилу ϕ(x) = = Co(ψ(x)), x ∈ L, является пленарным ∨-гомоморфизмом из L в Co(VT ); (ii) отображения ψ и ϕ сохраняют нуль; (iii) если норма e полна, то ψ и ϕ являются вложениями. ДОКАЗАТЕЛЬСТВО. Пусть L◦ = L∪{O}, где O 6∈ L. Продолжаем e (T )

до отображения из F+ в L◦ (которое также обозначаем через e), полагая e(x) = и

W

∅ = O.

_

(T )

{e(p) | p ∈ supp(x)} для всех x ∈ F+

(T )

УТВЕРЖДЕНИЕ 8.3. Если x, y ∈ F+ и x−→∗ y, то e(y) ≤ e(x). ДОКАЗАТЕЛЬСТВО.

Достаточно

рассмотреть

случай,

когда (T )

x−→1 y и x 6= y. Тогда существуют λ ∈ F++ , (p, I) ∈ MT и z ∈ F+

та-

кие, что λ X q˙ + z и y = λp˙ + z. |I| q∈I W Поскольку e является нормой, имеем e(p) ≤ e[I]; откуда x=

e(y) = e(p) ∨ e(z) ≤

_

e[I] ∨ e(z) = e(x). 2

УТВЕРЖДЕНИЕ 8.4. Для любого x ∈ L справедливо ψ(x) ∈ ∈ Co(VT , ΩT ).

282

Ф. Верунг, М. В. Семёнова

ДОКАЗАТЕЛЬСТВО. Пусть p ∈ T и p ∈ Co(ψ(x)). Следует поP казать, что p ∈ ψ(x). Согласно предположению p = λi pi для некоi
торых n > 0, (λi )i
Поскольку e[T ] содержится в L− , то ψ(0) = ϕ(0) = ∅, если L имеет

наименьший элемент. Очевидно, что ψ сохраняет существующие пересечения. Покажем, что ψ является ∨-гомоморфизмом. Достаточно проверить, что для всех x, y ∈ L и любого p ∈ T если e(p) ≤ x ∨ y, то p ∈ ψ(x) ∨ ψ(y) (объединение ψ(x) ∨ ψ(y) вычисляется в Co(VT , ΩT )). Если e(p) ≤ x или e(p) ≤ y, то p ∈ ψ(x) ∪ ψ(y). Пусть e(p)  x, y. Тогда {x, y} является нетривиальным покрытием элемента e(p), поэтому (поскольку e — норма) существует I ∈ 1 P q лежит в Co(ψ(x) ∪ ψ(y)). ∈ MT (p) такое, что e[I] ≪ {x, y} и p = |I| q∈I

Так как p ∈ ΩT , получаем, что p ∈ ψ(x) ∨ ψ(y).

Поскольку ΩT — пленарное подмножество в VT (см. предлож. 7.8), ϕ является пленарным ∨-гомоморфизмом. Наконец, предположим, что e является полной нормой и покажем, что ψ является вложением (тогда ϕ — тоже вложение). Пусть x, y ∈ L и x  y. Поскольку норма e полна, существует p ∈ T такой, что e(p) ≤ x и e(p)  y, откуда p ∈ ψ(x) \ ψ(y) и ψ(x) 6⊆ ψ(y). Следовательно, ϕ — вложение L в Co(VT ). 2 Утверждение, составляющее содержание теоремы 8.2, для произвольного линейно упорядоченного тела не следует тривиальным образом из соответствующего утверждения для F = Q, поскольку, к примеру, естественное вложение Co(Q) в Co(R) не сохраняет пересечения. § 9. Вложение в решетки выпуклых подмножеств Результаты предыдущих параграфов применяются здесь для доказательства того, что любая решетка вложима в решетку выпуклых под-

Подрешетки решеток выпуклых подмножеств векторных пространств 283 множеств некоторого векторного пространства. Всюду в этом параграфе фиксируется линейно упорядоченное тело F. ТЕОРЕМА 9.1. Для любой решетки существует пленарное сохраняющее нуль вложение в Co(V ) для некоторого векторного пространства V над F. ДОКАЗАТЕЛЬСТВО. Пусть L — произвольная решетка, T обозначает множество, состоящее из всех конечных последовательностей вида p = ha0 , I0 , a1 , I1 , . . . , am−1 , Im−1 , am i,

(9.1)

где m < ω, a0 , . . . , am ∈ L− , Ik — нетривиальное покрытие ak и ak+1 ∈ Ik для всех k < m. Пусть q = hb0 , J0 , b1 , J1 , . . . , bn−1 , Jn−1 , bn i,

(9.2)

полагаем p E q, если p является начальным отрезком q, и p ∼ q, если m = n и (ak , Ik ) = (bk , Jk ) для всех k < m. Полагаем также e(p) = am . Нетрудно проверить, что (T, E, ∼) является раскрашенным деревом. Если p и q такие, как соответственно в (9.1) и (9.2), то p ≺ q тогда и только тогда, когда p E q и n = m + 1. В этом случае множество I = [q] состоит из последовательностей вида q ′ = ha0 , I0 , a1 , I1 , . . . , am−1 , Im−1 , am , Jm , xi, где x ∈ Jm . В частности, e[I] = Jm является нетривиальным покрытием элемента e(p) = am . Поскольку для любого нетривиального покрытия J элемента am найдется r ≻ p такой, что J = e([r]), норма e полна. 2 Для конечных ограниченных снизу решеток справедливо более сильное утверждение. Если V — векторное пространство над линейно упорядоченным телом, то через K(V ) обозначается решетка выпуклых политопов пространства V , т. е. конечно порожденных выпуклых подмножеств в V . Хорошо известно, что K(V ) — полудистрибутивная вверх подрешетка Co(V ) (см. [15, теор. 15]). ТЕОРЕМА 9.2. Для любой конечной ограниченной снизу решетки L существует пленарное сохраняющее нуль вложение в K(Fn ) для неко-

284

Ф. Верунг, М. В. Семёнова

торого n < ω. Более того, для L существует сохраняющее нуль вложение в ограниченную снизу решетку вида Co(Qn , Ω) для некоторых числа n < ω и пленарного конечного подмножества Ω в Zn . ДОКАЗАТЕЛЬСТВО. Пусть L — конечная ограниченная снизу решетка, T состоит из всех конечных последовательностей вида (9.1), где n < ω, a0 , . . . , an ∈ J(L), Ik — минимальное нетривиальное покрытие элемента ak и ak+1 ∈ Ik для всех k < n. Определим отношения E, ∼ и отображение e так же, как и в доказательстве теоремы 9.1. Вновь нетрудно проверить, что (T, E, ∼) является раскрашенным деревом, e — полной нормой. Более того, поскольку L конечна и ограничена снизу, в ней нет D-циклов, поэтому T конечно; таким образом, пространство VT конечномерно, а множество ΩT конечно. Согласно предложению 7.8 множество ΩT пленарно. Для случая F = Q, фиксируя изоморфизм между VT и Qn и заменяя ΩT на Ω = mΩT (для подходящего m), можно считать, что Ω является подмножеством в Zn . Требуемое заключение следует из теоремы 8.2. 2 Таким образом, получен новый универсальный класс для конечных ограниченных снизу решеток, а именно, класс решеток вида Co(Qn , Ω), где n > 0, а Ω — конечное пленарное подмножество в Zn . Напомним, что два других хорошо известных универсальных класса конечных ограниченных снизу решеток образуют решетки Sub∧ (2m ) (нижних) подполурешеток булевых решеток 2m и решетки O(n) подпорядков линейно упорядоченных конечных множеств n, соответственно. Другое доказательство второго утверждения теоремы 9.2, использующее основной результат из [4], можно найти в [16].

§ 10. Решетки Co(V, Ω) и K(V ) В [3] была поставлена проблема о существовании вложения произвольной конечной решетки в некоторую конечную решетку вида Co(Rn , Ω), где n > 0 и Ω — конечное подмножество в Rn . Отношение между вложимостью в решетки вида Co(Fn ) и Co(Fn , Ω) устанавливает следующее простое

Подрешетки решеток выпуклых подмножеств векторных пространств 285 ПРЕДЛОЖЕНИЕ 10.1. Пусть L — решетка, V — векторное пространство над линейно упорядоченным телом F, ϕ : L֒→K(V ) — вложение. Если Ω — подмножество V , содержащее все предельные точки всех множеств вида ϕ(x), x ∈ L, то отображение ψ : L֒→Co(V, Ω), x 7→ ϕ(x) ∩ Ω, является вложением L в Co(V, Ω), а ϕ(x) = Co(ψ(x)) для всех x ∈ L. ДОКАЗАТЕЛЬСТВО. Очевидно, ψ сохраняет пересечения. Поскольку любой элемент из образа ϕ является выпуклой оболочкой (конечного) множества своих предельных точек, которое содержится в Ω, равенство ϕ(x) = Co(ψ(x)) справедливо для всех x ∈ L, поэтому ψ взаимно однозначно и сохраняет порядок. Обозначим через ∂e (X) множество предельных точек выпуклого политопа X в V , пусть x, y ∈ L. Если X ∈ Co(V, Ω) и ψ(x) ∨ ψ(y) ⊆ X, то ∂e (ϕ(x))∪∂e (ϕ(y)) ⊆ X; поэтому и меньшее множество ∂e (ϕ(x)∨ϕ(y)), совпадающее с ∂e (ϕ(x∨y)), содержится в X. Следовательно, ψ(x∨y) ⊆ X, что доказывает равенство ψ(x ∨ y) = ψ(x) ∨ ψ(y). Таким образом, ψ сохраняет и объединения. 2 СЛЕДСТВИЕ 10.2. Пусть F — линейно упорядоченное тело, n < < ω. Если конечная решетка L вложима в K(Fn ), то она вложима и в Co(Fn , Ω) для достаточно больших конечных подмножеств Ω ⊂ Fn . Считая x, a0 , a1 , b0 , b1 , c0 , c1 переменными, определим решеточные термы x′ = x ∧ (a0 ∨ a1 ) ∧ (b0 ∨ b1 ) ∧ (c0 ∨ c1 ),

(10.1)

ai,j,k = a1−i ∨ ((ai ∨ x′ ) ∧ (bj ∨ ck )),

(10.2)

bi,j,k = b1−j ∨ ((bj ∨ x′ ) ∧ (ai ∨ ck ))

(10.3)

и рассмотрим тождество x′ =

_

i,j,k<2


(x′ ∧ ai,j,k ) ∨ (x′ ∧ bi,j,k ) .

(10.4)

ЛЕММА 10.3. Решетка Co(F2 ) удовлетворяет тождеству (10.4) для любого линейно упорядоченного тела F.

286

Ф. Верунг, М. В. Семёнова СХЕМА ДОКАЗАТЕЛЬСТВА. Пусть X, A0 , A1 , B0 , B1 , C0 , C1 ле-

жат в Co(F2 ); X ′ , Ai,j,k , Bi,j,k , где i, j, k < 2, построены из них как в (10.1)—(10.3). Обозначим через Y правую часть равенства (10.4). Поскольку Y очевидным образом содержится в X ′ , достаточно показать, что X ′ содержится в Y . Пусть x ∈ X ′ . Если x ∈ Ai ∪ Bi ∪ Ci для некоторого i < 2, то x ∈ Y . Предположим, что x ∈ / Ai ∪ Bi ∪ Ci для всех i < 2. Поскольку x ∈ A0 ∨ A1 , существуют ai ∈ Ai , i < 2 такие, что x ∈ [a0 , a1 ]. Аналогично, существуют bi ∈ Bi и ci ∈ Ci , i < 2, такие, что x ∈ [b0 , b1 ]∩[c0 , c1 ]. Заметим, что x ∈ / {ai , bi , ci } для всех i < 2. Пусть ℓ — аффинная прямая, содержащая {c0 , c1 }, i, j < 2 — таковы, что ai и bj лежат в одной полуплоскости относительно ℓ, в то время как a1−i и b1−j лежат в другой полуплоскости. Возьмем x в качестве начала координат и выберем произвольную прямую ℓ′ , проходящую через x, такую, что либо ai и bj принадлежат ℓ′ (если x, ai , bj коллинеарны), либо ai и bj лежат в разных полуплоскостях, отсекаемых ℓ′ (в противном случае). В системе координат (ℓ, ℓ′ ) ℓ′ -координаты точек ai и bj не меньше, чем 0, а ℓ′ -координаты точек a1−i и b1−j не больше, чем 0. Выражая координаты точек x, c0 , c1 , ai , bj в этой системе координат, получаем (с точностью до перестановки (a0 , a1 ) и (b0 , b1 )) существование k < 2, α, β, α′ , β ′ ∈ F+ и γ0 , γ1 ∈ F++ таких, что α′ ≤ β ′ и ai

= (−α, α′ ),

c1−k = (−γ0 , 0), x

bj

= (β, β ′ ),

ck = (γ1 , 0),

= (0, 0).

Аккуратная проверка каждого случая показывает, что множество [ai , ck ] ∩ ∩ [x, bj ] всегда непусто. Если z лежит в этом множестве, то x содержится в [b1−j , z] ⊆ Bi,j,k , а поэтому и в Y . 2 ЛЕММА 10.4. Существует семиэлементное подмножество Ω в Q2 такое, что тождество (10.4) не выполняется в Co(Q2 , Ω). ДОКАЗАТЕЛЬСТВО. Положим Ω = {a˙ 0 , a˙ 1 , b˙ 0 , b˙ 1 , c˙0 , c˙1 , x}, ˙ где

Подрешетки решеток выпуклых подмножеств векторных пространств 287 a˙ 0 = (−2, 0), b˙ 0 = (−1, 1),

a˙ 1 = (2, 0), b˙ 1 = (1, −1),

c˙0

= (1, 1),

c˙1

x˙

= (0, 0).

= (−1, −1),

Пусть x = {x}, ˙ ai = {a˙ i }, bi = {b˙ i }, ci = {c˙i }, i < 2. Непосредственные вычисления показывают, что правая часть (10.4) (вычисленная в Co(Q2 , Ω)) пуста, в то время как левая совпадает с x. Следовательно, Co(Q2 , Ω) не удовлетворяет (10.4). 2 СЛЕДСТВИЕ 10.5. Пусть Ω — множество, рассмотренное в лемме 10.4. Тогда решетка Co(Q2 , Ω) не вложима в Co(F2 ) для любого линейно упорядоченного тела F. Если C — квадрат в Q2 (как в прим. 7.3) и C ′ = C ∪{c}, где c — центр ∼ 24 вложима в K(Q2 ) (достаточно каждому C, то решетка Co(Q2 , C) = a ∈ C сопоставить отрезок [a, c]), а соответствующее вложение никогда не сохраняет нуль. С другой стороны, C ′ — пленарное подмножество в Q2 (см. определ. 7.1), поэтому существует пленарное вложение Co(Q2 , C ′ ) в Co(Q2 ), сохраняющее нуль. Заметим, что Co(Q2 , C) является гомоморфным образом решетки Co(Q2 , C ′ ).

§ 11. Нерешенные вопросы Известно, что для всех натуральных n решетка K(Qn ) полудистрибутивна вверх. ВОПРОС 1. Верно ли, что любая конечная полудистрибутивная вверх решетка вложима в K(Qn ) для некоторого n > 0? Согласно теореме 9.2 вопрос 1 решается положительно для конечных ограниченных снизу решеток. Выпуклое множество в Qn называется полуалгебраическим, если оно совпадает с множеством решений некоторой конечной системы линейных неравенств (строгих или нестрогих), т. е. совпадает с пересечением конечного числа (открытых или замкнутых) полупространств Qn .

288

Ф. Верунг, М. В. Семёнова ВОПРОС 2. Верно ли, что любая конечная решетка вложима в ре-

шетку K(Qn ) ограниченных полуалгебраических выпуклых подмножеств в Qn для некоторого натурального n? Хорошо известно, что для любого хаусдорфова компактного локально выпуклого векторного пространства V над R решетка CB(V ) выпуклых тел в V (компактных выпуклых подмножеств в V ) полудистрибутивна вверх. Это доказывается как и [15, теор. 15]. ВОПРОС 3. Верно ли, что любая полудистрибутивная вверх решетка вложима в CB(V ) для некоторого хаусдорфова компактного локально выпуклого топологического векторного пространства V над R? ВОПРОС 4. Верно ли, что любая решетка вложима в решетку ограниченных замкнутых выпуклых подмножеств некоторого банахова пространства над R? Следующий вопрос связан с выбором тела F. Из теоремы 9.1 вытекает, что для любого линейно упорядоченного тела F универсальная теория класса решеток вида Co(FI ), где I бесконечно, совпадает с универсальной теорией класса всех решеток. Вопрос для случая конечной размерности пока остается открытым. ВОПРОС 5. Пусть n > 0, а F — линейно упорядоченное тело. Верно ли, что решетки Co(Qn ) и Co(Fn ) имеют одинаковую универсальную теорию? Как было показано в [17], ответ на вопрос 5 положителен для n = 1. Заметим также, что решетки Co(Q2 ) и Co(R2 ) имеют разные элементарные теории, см. [18, прим. 5.5.3]. Результаты настоящей работы были получены во время визита авторов в Карлов университет г. Праги в июне 2002. Авторы выражают благодарность за гостеприимство кафедре алгебры этого университета, особенно проф. И. Туме и проф. В. Славику.

Подрешетки решеток выпуклых подмножеств векторных пространств 289 ЛИТЕРАТУРА 1. Ph. M. Whitman, Lattices, equivalence relations, and subgroups, Bull. Am. Math. Soc., 52, N 6 (1946), 507—522. 2. P. Pudl´ ak, J. T˚ uma, Every finite lattice can be embedded in a finite partition lattice, Algebra Univers., 10, N 1 (1980), 74—95. 3. K. V. Adaricheva, V. A. Gorbunov, V. I. Tumanov, Join-semidistributive lattices and convex geometries, Adv. Math., 173, N 1 (2003), 1—49. 4. K. V. Adaricheva, Two embedding theorems for lower bounded lattices, Algebra Univers., 36, N 4 (1996), 425—430. 5. V. B. Repnitskii, On finite lattices which are embeddable in subsemigroup lattices, Semigroup Forum, 46, N 3 (1993), 388—397. ˇ 6. B. Sivak, Representation of finite lattices by orders on finite sets, Math. Slovaca, 28, N 2 (1978), 203—215. 7. М. В. Семенова, Решетки подпорядков, Сиб. матем. ж., 40, N 3 (1999), 673— 682. 8. R. Freese, J. Jeˇzek, J. B. Nation, Free lattices (Math. Surv. Monogr., 42), Providence, RI, Am. Math. Soc., 1995. 9. K. V. Adaricheva, F. Wehrung, Embedding finite lattices into finite biatomic lattices, Order, 20, N 1 (2003), 31—48. 10. M. Semenova, F. Wehrung, Sublattices of lattices of order-convex sets, I. The main representation theorem, J. Algebra, to appear. 11. A. Huhn, On non-modular n-distributive lattices I. Lattices of convex sets, Acta Sci. Math., 52, N 1/2 (1988), 35—45. 12. G. M. Bergman, On lattices of convex sets in Rn , preprint, 2003. 13. M. K. Bennett, Lattices of convex sets, Trans. Am. Math. Soc., 234, N 1 (1977), 279—288. 14. К. Куратовский, А. Мостовский, Теория множеств, М., Мир, 1970. 15. G. Birkhoff, M. K. Bennett, The convexity lattice of a poset, Order, 2 (1985), 223—242. 16. K. V. Adaricheva, Join-semidistributive lattices of relatively convex sets, Contributions to General Algebra 14, Proc. of the Olomouc Conf. 2002 (AAA64) and the Potsdam Conf. 2003 (AAA65), Klagenfurt, Verlag Johannes Heyn, 2004, 1—14.

290

Ф. Верунг, М. В. Семёнова

17. M. Semenova, F. Wehrung, Sublattices of lattices of order-convex sets, III. The case of totally ordered sets, Internat. J. Algebra Comput., to appear. 18. B. Gr¨ unbaum, Convex polytopes, London a. o., Interscience Publ., 1967.

Поступило 23 сентября 2002 г. Окончательный вариант 11 февраля 2004 г. Адреса авторов: WEHRUNG, Friedrich, CNRS, UMR 6139, D´epartement de Math´ematiques, Universit´e de Caen, 14032 Caen Cedex, FRANCE. e-mail: [email protected]; http://www.math.unicaen.fr/˜wehrung СЕМЁНОВА Марина Владимировна, Институт математики СО РАН, пр. Ак. Коптюга, 4, г. Новосибирск, 630090, РОССИЯ. e-mail: [email protected]