Теоремі про решетки.

1. РЕШЕТКИ

1.1. Основные определения

Определение 6.1. Решеткой называется у-множество L, в котором любые два элемента x и y имеют точную нижнюю грань, называемую пересечением (обозначается x Ù y), и точную верхнюю грань, называемую объединением (обозначается x Ú y). Решетка L называется полной, если любое ее подмножество Х имеет в L точные верхнюю и нижнюю грани.

 

Определение 6.2. Подрешеткой решетки L называется подмножество X Ì L такое, что если a Î X, b Î X, то a Ù b Î X и a Ú b Î X.

Пустое подмножество и любое одноэлементное подмножество являются подрешетками. Подрешетка решетки сама является решеткой с теми же операциями объединения и пересечения. Вообще, если a £ b в решетке L, то (замкнутый) интервал [a, b], состоящий из всех элементов x Î L, которые удовлетворяют условию a £ x £ b, всегда будет подрешеткой. Для цепи и ее элементов a, b, таких что a £ b, можно определить понятия полуоткрытых интервалов: (a, b] = {x | a < x £ b} и [a, b) = {x| a £ x < b}, а также открытый интервал (a, b) = {x| a < x < b}. Если эти множества непусты, они также являются подрешетками.

 

Пример. В решетке на рис. 6.1 подмножество Y = {Æ, {b}, {c}, {b, c}} является подрешеткой. Действительно {b} Î Y, {c} Î Y, {b} Ù {c} = Æ Î Y, {b} Ú {c} = {b, c} Î Y,  {b}Ú{b, c} =  {b, c} Î Y, пересечение {b} Ù {а, c} = {b} Î Y и т. д. Это подмножество образует замкнутый интервал [Æ, {b, c}]. Подмножество Z = {Æ, {a}, {a, b}, {a, c}, {c}} не является подрешеткой, так как {a, b} Ú {а, c} = {a, b, c} Ï Z. Это подмножество не является также интервалом. Подрешетками будут также все цепи, например: {Æ, {b}},  {{a}, {a, b}}, {Æ, {b}, {b, c}}, и т.д., а также все элементы решетки.

 

Рис. 6.1. Решетка и ее подрешетки.  

 

 

Определение 6.3. Выпуклым подмножеством в у-множестве Р называется подмножество, которое вместе с любыми своими элементами a и b, где a £ b, содержит весь интервал [a, b].

На рис. 6.1. подмножество {Æ, {b}, {c}, {b, c}}, – выпуклое, а подмножество {Æ, {b}, {b, c}} – нет. Подмножество S решетки L является выпуклой подрешеткой, если для любых a, b Î S  [a Ù b, a Ú b] Ì S. 

1.2. Решетки как алгебры

Решетку можно определить как алгебраическую систему: L = <P, Ú, Ù, £ >, с двумя бинарными операциями Ú и Ù, и отношением порядка £, заданными на множестве P. Решеточные операции Ú и Ù обладают важными алгебраическими свойствами. В этом разделе мы исследуем свойства операций Ú и Ù и покажем, что операции, обладающие этими свойствами, определяют отношение порядка на множестве P, что позволяет рассматривать решетки как алгебры с двумя операциями.

 

Лемма 6.1. В любом у-множестве для операций пересечения и объединения выполняются (при определенных в них выражениях) следующие законы:

 

x Ù x = x,     x Ú x = x	(идемпотентность);	L1
x Ú y = y Ú x,    x Ù y = y Ù x	(коммутативность);	L2
x Ù (y Ù z) = (x Ù y) Ù z, x Ú (y Ú z) = (x Ú y) Ú z	(ассоциативность);	L3
x Ù (x Ú y) = x,   x Ú (x Ù y) = x	(поглощение).	L4

Кроме того, неравенство x £ y равносильно каждому из условий:

x Ù y = x  и x Ú y = y (условия совместимости).

 

Доказательство. L1 и L2 выполняются очевидно. Ассоциативный закон L3 также очевиден: x Ù (y Ù z) = inf {x, inf {y, z}} =  inf {inf {x, y}, z} = (x Ù y) Ù z. Закон поглощения L4 выполним в силу того, что x Ù (x Ú y) = inf{x, sup{x, y}}. Если x £ y, то sup{x, y} = y, и тогда inf{x, y} = x, а если y £ x, то sup{x, y} = x, и тогда inf{x, x} = x. Условие совместимости: x Ù y = x, если x £ y, и x Ú y = y, если x £ y, — выполняется также очевидно.

 

Из условия совместимости  следуют важные свойства универсальных граней 0 и I.

Лемма 6.2. Если у-множество P имеет 0, то

0 Ù x = 0 и 0 Ú x = x   для всякого x Î P,

и если у-множество P имеет I, то

x Ù I = x и x Ú I = I   для всякого x Î P.

Доказательство не представляет труда.

 

Лемма 6.3. Во всякой решетке операции объединения и пересечения изотонны:

если y £ z, то x Ù y £ x Ù z и x Ú y £ x Ú z.

Доказательство. Согласно L1 – L4, если y £ z, то x Ù y = (x Ù x) Ù (y Ù z) = (x Ù y) Ù (x Ù z). Учитывая, что x Ù x = x и y Ù z = y, по условию совместимости получаем x Ù y £ x Ù z. Второе неравенство доказывается двойственно.

 

Лемма 6.4. Во всякой решетке имеют место следующие неравенства дистрибутивности:

x Ù (y Ú z) ³ (x Ù y) Ú (x Ù z), (6.1)

x Ú (y Ù z) £ (x Ú y) Ù (x Ú z). (6.1')

Доказательство. Очевидно, что x Ù y £ x и x Ù y £ y £ y Ú z, откуда x Ù y £ x Ù (y Ú z). Аналогично: x Ù z £ x и x Ù z £ z £ y Ú z, откуда x Ù z £ x Ù (y Ú z). Таким образом, x Ù (y Ú z) является верхней гранью для x Ù y и x Ù z и, следовательно, выполняется (6.1). (6.1') доказывается двойственно.

 

Лемма 6.5. Элементы любой решетки удовлетворяют неравенству модулярности:

если x £ z, то x Ú (y Ù z) £ (x Ú y) Ù z. (6.2)

Доказательство. x £ x Ú y и x £ z, значит x £ (x Ú y) Ù z. Аналогично, y Ù z £ y £ x Ú y и y Ù z £ z, следовательно, y Ù z £ (x Ú y) Ù z, отсюда x Ú (y Ù z) £ (x Ú y) Ù z.

Дадим следующие определения.

 

Определение 6.6. Система с одной бинарной идемпотентной, коммутативной и ассоциативной операцией называется полурешеткой. У-множество P, в котором любые два элемента имеют пересечение, является полурешеткой относительно бинарной операции Ù. Такие полурешетки называются Ù-полурешетками, или нижними полурешетками. У-множество P, в котором любые два элемента имеют объединение, является полурешеткой относительно бинарной операции Ú. Такие полурешетки называются Ú-полурешетками, или верхними полурешетками.

 

Пример. На рис. 6.2 приведены диаграммы верхней и нижней полурешеток. В у-множестве P₁ любые два элемента имеют объединение, однако элементы a и b не имеют пересечения, поэтому P₁ является верхней полурешеткой; в у-множестве P₂ любые два элемента имеют пересечение, однако элементы c и d не имеют объединения, поэтому это нижняя полурешетка.  

Верхняя полурешетка P₁.  Нижняя полурешетка P₂.

Рис.  6.2. Полурешетки.

Теперь докажем важную лемму, которая связывает полурешетку  как алгебру с понятием у-множества. Эта лемма утверждает, что если на множестве P задана алгебра с одной бинарной операцией, удовлетворяющей свойствам идемпотентности, коммутативности и ассоциативности, то эта операция задает отношение порядка на P, т.е. множество, на котором задана эта операция, является у-множеством. Таким образом, мы можем ничего не знать о существовании каких-либо отношений на множестве P, но задание операции со свойствами L1, L2, L3 определяет отношение порядка на нем.

 

Лемма 6.6. Если в полурешетке с бинарной операцией o положить

x £ y тогда и только тогда, когда xoу = x,

то она становится у-множеством, в котором inf{x, y} = xoy.

Поясним смысл леммы. В лемме  задано некоторое множество с некоторой бинарной операцией o, и, поскольку указано, что множество образует полурешетку, то это означает, что операция o является идемпотентной, коммутативной и ассоциативной. Далее мы вводим некоторое (пока абстрактное) отношение £ на множестве таким образом, что если xoу = x, то x £ y, и наоборот, если x £ y, то xoу = x, т.е. эти два условия равнозначны. Нужно доказать, что отношение £ является отношением порядка, и операция o имеет смысл нахождения точной нижней грани x и y.

 

Доказательство.

1. Сначала  докажем, что отношение £ является отношением порядка, т.е. удовлетворяет свойствам рефлексивности, антисимметричности и транзитивности: Р1, Р2, Р3.

По предположению  леммы, x £ y тогда и только тогда, когда xoу = x. Из закона идемпотентности xox  = x следует рефлексивность отношения: x £ x. В силу коммутативности xoу = yox получаем антисимметричность: если x £ y, то по условию xoу = x, и если y £ x, то yox = y. Тогда, если выполняются одновременно x £ y и x £ y, то x = xoу = yox = y, т.е. отношение £ антисимметрично. Применяя ассоциативный закон, из x £ y и y £ z получим x £ z.  Действительно, если x £ y и y £ z, то x = xoу и y = yoz, т.е. x  = xoу  = xo(yoz) = (xoy)oz = xoz , откуда x £ z, т.е. доказана транзитивность £. Отсюда следует, что £ является отношением порядка.

2. Теперь  докажем, что xoy =  inf{x, y} для любых x, y. Докажем сначала, что xoy £ x и xoy £ y. Если x £ y, то xoу  =  x по определению, и, следовательно, xoу £ y, а в силу рефлексивности x £ x справедливо и xoу £ x. Наконец, если x и y несравнимы, то, в силу того, что операция o всюду определена, найдется z £ x  и z £ y. Тогда zo(xoy) =  (zox)oy = zoy = z, откуда z £ xoy,  и, следовательно,  xoy = inf{x, y}.

Справедлива и двойственная лемма  относительно объединения.

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

 

Теорема 6.3. Любая алгебра L = <P, Ú, Ù> с двумя бинарными операциями Ú, Ù, удовлетворяющими условиям L1 — L4, является решеткой, и обратно.

Доказательство. Согласно лемме 6.6, любая система L, операции которой удовлетворяют условиям L1 — L4, является у-множеством, в котором x Ù y = inf{x, y}, так что x £ y означает, что x Ù y = x. Рассмотрим теперь операцию x Ú y . Если x £ y, то x Ù y = x. Подставим x Ù y вместо x в x Ú y; получим x Ú y = (x Ù y) Ú y = y (последнее равенство выполнимо в силу закона поглощения L4). В силу двойственности справедливо и обратное утверждение: если x Ú y = y, то x £ y.  Следовательно, неравенство x £ y равносильно также и равенству x Ú y = y. По принципу двойственности получаем, что x Ú y = sup{x, y} и, значит, L является решеткой.

 

Пример. Пусть на  множестве L = {a, b, c, d}  заданы бинарные операции Ä и Å  (табл. 6.1).

 

Таблица 6.1.

 

Ä	a	b	c	d		Å	a	b	c	d
a	a	a	a	a		a	a	b	c	d
b	a	b	a	b		b	b	b	d	d
c	a	a	c	c		c	c	d	c	d
d	a	b	c	d		d	d	d	d	d

 

 

Рис. 6.3.  Решетка L = {a, b, c, d}.

Непосредственно из таблиц видно, что обе операции идемпотентны (см. значения на диагонали таблиц) и  коммутативны (таблицы симметричны). В ассоциативности операций также нетрудно убедиться. Будем полагать, что x £ y всякий раз, когда x Ä y = x. Тогда из первой строки табл. 6.1 получим: a £ b, a £ c, a £ d, далее: b £ d, так как b Ä d = d, и c £ d, так как c  Ä d = d. Имеем также: b Ä c = c Ä b = a, откуда следует, что a является точной нижней гранью b и c, и, учитывая первую строку, универсальной нижней гранью. Тогда, построив диаграммы двух цепей: a £ b, b £ d, и a £ c, c £ d, получим диаграмму на рис. 6.3, где операция Ä является пересечением, а Å – объединением любых двух элементов. Таким образом, множество L является решеткой.

 

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

Можно выделить решетки, обладающие дополнительными свойствами, и определить типы решеток, согласно этим свойствам. Так, например, для любой решетки выполняются неравенства дистрибутивности (6.1) и (6.1¢), однако существуют и такие, для которых выполнимы строгие равенства.

Определение 6.7. Решетка называется дистрибутивной, если в ней для всех x, y, z выполняются тождества:

x Ù (y Ú z) = (x Ù y) Ú (x Ù z),  L6¢

x Ú (y Ù z) = (x Ú y) Ù (x Ú z). L6¢¢

Следует отметить, что  выполнимость L6¢ для отдельных элементов решетки не влечет выполнимости для них L6¢¢ (свойство L6¢¢ для тех же элементов может не выполняться, если решетка недистрибутивна). Однако выполнимость одного из этих свойств для всех элементов решетки влечет выполнимость и другого. Тогда для проверки дистрибутивности решетки достаточно установить тождество L6¢ (или L6¢¢) для всех элементов, – второе будет следовать по теореме 6.4.

 

Теорема 6.4. Если в решетке для  всех элементов выполняется тождество L6¢, то выполняется тождество L6¢¢ и наоборот.

Доказательство. Покажем, что из L6¢ следует L6¢¢. Из L6¢¢ будет следовать L6¢ по принципу двойственности. Для всех x, y, z:

(x Ú y) Ù (x Ú z) = [(x Ú y) Ù x] Ú [(x Ú y) Ù z] = согласно L6¢ 

= x Ú [z Ù (x Ú y)] = по L4,  L2 

= x Ú [(z Ù x) Ú (z Ù y)] = по L6¢ 

= [x Ú (z Ù x) Ú (z Ù y)] = по L3  

= x Ú (z Ù y). по L4

 

1.4. Модулярность

 

Определение 6.8. Решетка называется модулярной, если в ней выполняется модулярный закон L5:

если x £ z, то x Ú (y Ù z) = (x Ú y) Ù z. L5

Заметим, что по принципу двойственности, если z £ x, то x Ù (y Ú z) = (x Ù y) Ú z, что совпадает с L5, т.е. закон модулярности является самодвойственным.

Модулярный закон может быть получен из L6", если x £ z. Таким образом, модулярный закон L5 имеет место в любой дистрибутивной решетке. Отсюда следует, что если решетка дистрибутивна, то она модулярна.

 

Примеры.

1. Рассмотрим решетку N₅ («пентагон») на рис. 6.4. Докажем, что она немодулярна. Все цепи в решетке дистрибутивны, следовательно, для любых двух элементов, лежащих на одной цепи, условие модулярности выполняется. Возьмем элементы a £ b и элемент c, не лежащий с ними на одной цепи. Проверим выполнимость свойства L5: a Ú (c Ù b) = (a Ú c) Ù b. Получим: a Ú (c Ù b) = a Ú 0 = a,  (a Ú c) Ù b = I Ù b = b. Так как a ¹ b, то закон модулярности не выполняется. Рассмотрим, удовлетворяется ли свойство дистрибутивности: a Ú (c Ù b) = (a Ú c) Ù (a Ú b), но a Ú 0 ¹ I Ù b, следовательно, решетка N₅ недистрибутивна.

Отсюда следует вывод: если решетка немодулярна, то она недистрибутивна.

 

Рис. 6.4. Решетки N₅ (пентагон), M₃ (диамант), N₇.