Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 3 часа [ Летнее время ]


Решетки и полурешетки

Решетки и полурешетки


Напомним, что полурешеткой называют полугруппу, операция которой коммутативна и идемпотентна.


Таким образом, полурешетка — это алгебра \mathcal{L}=(L,\lor), в которой для любых a,b,c\in L выполнены равенства


a\lor (b\lor c)=(a\lor b)\lor c,\qquad a\lor b=b\lor a,\qquad a\lor a=a.

В каждой полурешетке может быть определено естественное отношение порядка аналогично тому, как это определялось для (идемпотентного) полукольца. По определению полагаем для произвольных a,b\in L


a \leqslant b\quad \Leftrightarrow\quad a\lor b=b.
(3.32)

Из определения (3.32) отношения порядка в полурешетке следует, что элемент a\lor b есть точная верхняя грань двухэлементного множества \{a,b\}. Действительно,


a\lor (a\lor b)= (a\lor a)\lor b=a\lor b

(в силу ассоциативности и идемпотентности операции \lor). Аналогично b\lor (a\lor b)=a\lor b (с использованием и коммутативности операции \lor). Итак, a\lor b есть верхняя грань множества \{a,b\}. Полагая, что c есть какая-то верхняя грань данного множества, вычислим (a\lor b)\lor c. Используя ассоциативность и то, что в силу b\leqslant c выполняется равенство b\lor c=c, получим


(a\lor b)\lor c=a\lor (b\lor c)=a\lor c\,.

Но так как a\leqslant c, то a\lor c=c. Итак, (a\lor b)\lor c=c, то есть a\lor b\leqslant c, и поэтому элемент a\lor b есть точная верхняя грань множества \{a,b\}.


Отношение порядка, определенное в произвольной полурешетке согласно условию (3.32), будем называть естественным порядком данной полурешетки.


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


Можно доказать, что имеет место и обратное.




Теорема 3.10. Любое упорядоченное множество \mathcal{L}=(L,\leqslant), в котором всякое двухэлементное подмножество имеет точную верхнюю грань, является полурешеткой, естественный порядок которой совпадает с отношением \leqslant.


Определим операцию \lor так: a\lor b=\sup\{a,b\}. Коммутативность и идемпотентность операции \lor следует сразу из определения точной верхней грани множества. Действительно,


a\lor a=\sup\{a,a\}=\sup\{a\}=a

и так как \{a,b\}=\{b,a\}, то a\lor b=\sup\{a,b\}=\sup\{b,a\}=b\lor a.


Докажем ассоциативность операции \lor. Для этого нужно показать, что для произвольных a,b\in L имеет место равенство


\sup\bigl\{\sup\{a,b\},c\bigr\}= \sup\bigl\{a,\sup\{b,c\}\bigr\}.
(3.33)

Обозначим левую часть равенства (3.33) через d_1, а правую — через d_2. Элемент d_1 является точной верхней гранью множества, элементы которого суть \sup\{a,b\} и c. Поэтому d_1\geqslant \sup\{a,b\} и d_1\geqslant c. Из первого неравенства следует, что d_1\geqslant a и d_1\geqslant b. Тогда, поскольку d_1\geqslant b и d_1\geqslant c, то d_1 есть верхняя грань множества \{b,c\}, то есть d_1\geqslant \sup\{b,c\}. Так как d_1\geqslant a, то d_1\geqslant \sup\{a,\sup\{b,c\}\}=d_2. Аналогично доказывается, что d_2\geqslant d_1, то есть d_1=d_2, что и требовалось доказать.


Поскольку для любых элементов a,b упорядоченного множества (L,\leqslant) согласно условию теоремы соотношение a\leqslant b эквивалентно тому, что \sup\{a,b\}=b, то исходное отношение порядка \leqslant совпадает с естественным порядком полурешетки (L,\sup).




Из принципа двойственности для упорядоченных множеств следует, что точная верхняя (нижняя) грань любого подмножества упорядоченного множества (L,\sup) является одновременно точной нижней (верхней) гранью этого подмножества в смысле двойственного порядка \geqslant. Отсюда получаем утверждение, двойственное теореме 3.10.


Теорема 3.11. Любое упорядоченное множество \mathcal{L}=(L,\sup), в котором всякое двухэлементное подмножество имеет точную нижнюю грань, является полурешеткой, причем естественный порядок этой полурешетки является порядком, двойственным к исходному порядку \leqslant.


Доказательство дословно повторяет доказательство теоремы 3.10, но операция \land полурешетки определяется так:


a\land b=\inf\{a,b\}.



Верхняя и нижняя полурешетки


Полурешетку (L,\sup), определенную теоремой 3.10, называют верхней полурешеткой, а полурешетку (L,\inf), определяемую теоремой 3.11, — нижней полурешеткой.


Замечание 3.3. Обратим внимание на то, что понятия "верхний" и "нижний" имеют смысл относительно фиксированного отношения порядка и при переходе к двойственному порядку "верх" превращается в "низ" и наоборот.


Пример 3.14. а. Отрезок [a,b] числовой прямой (с естественным числовым порядком), согласно теоремам 3.10 и 3.11, является и верхней и нижней полурешеткой. Более того, поскольку на числовой прямой любое двухэлементное подмножество имеет как точную верхнюю, так и точную нижнюю грань, то любое подмножество множества действительных чисел \mathbb{R} (в частности, само \mathbb{R}) является и верхней и нижней полурешеткой.


б. Если на множестве точек плоскости (на которой задана некоторая декартова система координат и точка рассматривается как упорядоченная пара действительных чисел) определить отношение порядка так, что (x,y)\leqslant (u,v) тогда и только тогда, когда x\leqslant u и y\leqslant v (см. пример 1.17 и рис. 1.11), то множество точек любого прямоугольника [a,b]\times[c,d] (с указанным отношением порядка), согласно теоремам 3.10 и 3.11, есть и верхняя и нижняя полурешетка (рис. 3.1). Если же мы "срежем" у этого прямоугольника углы и рассмотрим, например, множество точек многоугольника ABCDEF на рис. 3.2, то это множество не будет ни верхней, ни нижней полурешеткой, так как, скажем, множество \{A,F\} не имеет \inf, а множество \{C,D\} не имеет sup. Если мы "срежем" только один угол, левый нижний или правый верхний, то получим верхнюю или нижнюю полурешетку соответственно.


Верхняя и нижняя полурешетка и множество точек многоугольника

Диаграмма Хассе множества, не являющегося ни верхней, ни нижней полурешеткой

в. На рис. 3.3 изображена диаграмма Хассе множества, не являющегося ни верхней, ни нижней полурешеткой. Действительно, множество \{d,e\} не имеет точной верхней грани, хотя имеет точную нижнюю грань: \inf\{d,e\}=c. Аналогично множество \{a,b\} не имеет точной нижней грани, хотя имеет точную верхнюю грань: \sup\{a,b\}=c.




Нейтральный элемент полурешетки


Полурешетка, как полугруппа, может быть моноидом, т.е. может иметь нейтральный элемент. Нейтральный элемент верхней полурешетки (L,\lor) называют нулем полурешетки и обозначают 0, называя при этом саму полу решетку верхней полурешеткой с нулем. Двойственным образом нейтральный элемент нижней полурешетки (L,\land) называют единицей полурешетки, используя обозначение 1 и называя эту полурешетку нижней полурешеткой с единицей.


Для нуля полурешетки (L,\lor,\bold{0}) имеем a\lor \bold{0}=a для всякого a\in L, т.е. нуль полурешетки есть ее наименьший элемент. Двойственным образом единица полурешетки (L,\land,\bold{1}) есть её наибольший элемент.


Пример 3.15. а. Прямоугольник [a,b]\times[c,d] (см. пример 3.14.6 и рис. 3.1) — одновременно и нижняя полурешетка с единицей, которой служит точка (b,d), и верхняя полурешетка с нулем, которым является точка (a,c). Прямоугольник со "срезанным" правым верхним углом — нижняя полурешетка, но без единицы полурешетки.


б. Отрезок [a,b]\subset\mathbb{R} (при любых его границах) есть одновременно и нижняя полурешетка с единицей, которой является число b, и верхняя полурешетка с нулем. Им служит число a.


Полуинтервалы (a,b] и [a,b) суть соответственно нижняя полурешетка с единицей и верхняя полурешетка с нулем. Заметим, что одновременно первый полуинтервал есть верхняя полурешетка, не имеющая нуля, а второй полуинтервал — нижняя полурешетка без единицы.


Интервал (a,b) есть одновременно и нижняя и верхняя полурешетка, но ни та, ни другая не имеет нейтральных элементов.


в. Индуктивное упорядоченное множество в общем случае не является верхней полурешеткой с нулем, хотя и имеет наименьший элемент. Дело в том, что двухэлементное подмножество этого множества, состоящее из несравнимых элементов, может и не иметь точной верхней грани, поскольку точную верхнюю грань имеет в этом множестве любая неубывающая последовательность и, как можно показать, любая конечная или счетная цепь.


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




Решётки: понятие, определение и примеры


Рассмотренные выше примеры показывают, что существуют упорядоченные множества, являющиеся нижней и верхней полурешетками одновременно. Если такая "связка" полурешеток имеет определенные дополнительные свойства, то она называется решеткой.


Определение 3.5. Решетка — это алгебра \mathcal{L}=(L,\lor,\land) с двумя бинарными операциями, такая, что каждая из алгебр (L,\lor) и (L,\land) является полурешеткой и выполняются следующие тождества поглощения:


a\lor (a\land b)=a,\qquad a\land (a\lor b)=a\,.

Операции решетки \lor и \land называют решеточным объединением и решеточным пересечением соответственно. Операции решетки называют также решеточными операциями.


Другими словами, решетка — это алгебра с двумя бинарными операциями, обозначаемыми \lor и \land, такими, что выполняются тождества


\begin{array}{ll}\mathsf{\scriptstyle{1)}}\quad a\lor (b\lor c)=(a\lor b)\lor c;&\qquad \mathsf{\scriptstyle{5)}}\quad a\lor a=a;\\[2pt] \mathsf{\scriptstyle{2)}}\quad a\land (b\land c)=(a\land b)\land c;&\qquad \mathsf{\scriptstyle{6)}}\quad a\land a=a;\\[2pt] \mathsf{\scriptstyle{3)}}\quad a\lor b=b\lor a;&\qquad \mathsf{\scriptstyle{7)}}\quad a\lor (a\land b)=a;\\[2pt] \mathsf{\scriptstyle{4)}}\quad a\land b=b\land a;&\qquad \mathsf{\scriptstyle{8)}}\quad a\land (a\lor b)=a. \end{array}


Из определения решетки следует, что всякое симметричное полукольцо и, значит, любая булева алгебра являются решетками, т.е. сложение и умножение симметричного полукольца, равно как и булево объединение и булево пересечение, есть примеры решеточных операций. Тогда и булева алгебра \mathcal{S}_A всех подмножеств некоторого множества A, и полукольцо \mathcal{D}_n всех делителей натурального числа n — примеры решеток.


Приведем пример решетки, не являющейся полукольцом.


Пример 3.16. Алгебра \bigl((a,b),\max,\min\bigr), носитель которой — открытый интервал на числовой прямой, а операции — взятие наибольшего и наименьшего из двух чисел (относительно естественного числового порядка), есть решетка. Однако отсутствие нейтральных элементов по данным операциям не позволяет считать данную алгебру полукольцом.


Заметим, что решеточные операции в общем случае и не дистрибутивны (хотя в только что рассмотренном примере 3.16 дистрибутивность каждой операции относительно другой имеет место). Конкретные примеры недистрибутивных решеток будут приведены ниже.


Выясним теперь связь между понятием решетки и понятием упорядоченного множества. Каждая решетка, как следует из определения, есть "связка" двух полурешеток, но априори совсем не очевидно, что естественные порядки этих полурешеток суть взаимно двойственные порядки, т.е. для любых a,b\in L неравенство a\leqslant b, равносильное равенству a\lor b=b, имеет место если и только если a\land b=a. Такую связь между решеточными операциями устанавливает следующая теорема.




Теорема 3.12. В любой решетке \mathcal{L}=(L,\lor,\land) естественный порядок \leqslant полурешетки (L,\lor) есть порядок, двойственный к естественному порядку полурешетки (L,\land), т.е. для любых a,b\in L имеет место равенство


a\lor b=b \Leftrightarrow a\land b=a, то есть a\lor b=\sup\{a,b\} и a\land b=\inf\{a,b\}.

Согласно определению естественного порядка полурешетки, для любых a,b\in L выполняется условие a\leqslant b\Leftrightarrow a\lor b=b. Мы должны доказать, что двойственный порядок \geqslant совпадает с естественным порядком полурешетки (L,\land), т.е. нужно доказать, что a\geqslant b\Leftrightarrow a\land b=b или, что равносильно, a\leqslant b\Leftrightarrow a\land b=a. Для этого достаточно показать, что a\lor b=b \Leftrightarrow a\land b=a.


Имеем: если a\lor b=b, то a\land b=a\lor (a\lor b). Согласно второму тождеству поглощения, a\land (a\lor b)=a, и поэтому a\land b=a; если же a\land b=a, то с учетом первого тождества поглощения будем иметь


a\lor b=(a\land b)\lor b=b.

Итак, естественные порядки полурешеток (L,\land) и (L,\lor) взаимно двойственные. Так как в силу теоремы 3.10 \sup\{a,b\}=a\lor b для любых a,b\in L, то, согласно принципу двойственности, \inf\{a,b\}=a\land b.




Обратим внимание на использование тождеств поглощения при доказательстве теоремы 3.12. Именно они делают естественные порядки полурешеток (L,\land) и (L,\lor) взаимно двойственными.


Таким образом, любая решетка \mathcal{L}=(L,\lor,\land) есть в то же время упорядоченное множество (L,\leqslant), где отношение порядка \leqslant совпадает с естественным порядком полурешетки (L,\lor), которая тогда будет верхней полурешеткой. Полурешетка же (L,\land) оказывается (относительно этого же отношения порядка) нижней полурешеткой. Первую полурешетку поэтому часто называют верхней полурешеткой решетки \mathcal{L}, а вторую полурешетку — нижней полурешеткой той же самой решетки. Само же отношение порядка \leqslant называют естественным порядком решетки \mathcal{L}.


Можно доказать утверждение, обратное к теореме 3.12.


Теорема 3.13. Любое упорядоченное множество \mathcal{L}=(L,\leqslant), в котором всякое двухэлементное подмножество имеет точную верхнюю и точную нижнюю грани, т.е. для любых a,b\in L существуют \sup\{a,b\} и \inf\{a,b\}, является решеткой в смысле определения 3.5, в которой решеточные операции определяются так:


a\lor b=\sup\{a,b\},\qquad a\land b=\inf\{a,b\}.

При этом естественный порядок решетки (L,\sup,\inf) совпадает с исходным порядком \leqslant.


То, что каждая из алгебр (L,\sup) и (L,\inf) является полурешеткой, равно как и то, что естественный порядок первой полурешетки совпадает с исходным порядком \leqslant, а естественный порядок второй полурешетки двойствен к порядку \leqslant, следует из теорем 3.10 и 3.11. Остается доказать тождества поглощения. Достаточно доказать одно из них, так как второе будет выполняться в силу принципа двойственности (для упорядоченных множеств).


Итак, докажем, что для любых a,b\in L выполняется равенство


\inf\bigl\{a,\sup\{a,b\}\bigr\}=a\,.
(3.34)

Равенство (3.34) следует из того, что для любых элементов c,d\in L из того, что c\leqslant d, следует, что c=\inf\{c,d\}. Тогда в силу неравенства a\leqslant\sup\{a,b\} имеем (3.34).


Важность последнего результата состоит в том, что полурешетку можно задавать как упорядоченное множество с точными верхними и точными нижними гранями для любой пары элементов. Иными словами, для того чтобы убедиться, что перед нами решетка, достаточно проверить это свойство.




Пример 3.17. а. Рассмотренный в примере 3.14.6 прямоугольник [a,b]\times [c,d] есть решетка (см. рис. 3.1), но если мы "срежем" у этого прямоугольника углы и рассмотрим, например, множество точек многоугольника ABCDEF на рис. 3.2, то это множество уже не будет решеткой, так как, скажем, множество \{A,F\} не имеет \inf, а множество \{C,D\} не имеет \sup.


Декартов квадрат множества целых чисел

б. Не является решеткой и конечное упорядоченное множество, диаграмма Хассе которого изображена на рис. 3.3. Здесь \sup\{a,b\}=c, но \inf\{a,b\} не существует. Аналогично \inf\{d,e\}=c, но \sup\{d,e\} не существует.


в. Декартов квадрат множества целых чисел \mathbb{Z}^2 — решетка, где упорядоченные пары целых чисел упорядочиваются аналогично точкам плоскости (см. пример 3.17.а). Относительно этого же отношения порядка решеткой будет и любой "целочисленный прямоугольник" [a\ldots b]\times [c\ldots d], где [m\times n] обозначает множество всех целых чисел p, таких, что m\leqslant p\leqslant n. Этот "прямоугольник" и графически выглядит как "решетка", что видно на рис. 3.4, на котором изображено множество [1\ldots5]\times[1\ldots4].




Наименьший и наибольший элементы решётки


Если верхняя полурешетка решетки \mathcal{L}=(L,\lor,\land) есть полурешетка с нулем, то этот нуль является наименьшим элементом решетки \mathcal{L}. Тогда ее называют решеткой с нулем, а нуль полурешетки (L,\lor) — нулем решетки \mathcal{L}. Двойственным образом единица нижней полурешетки (L,\land), если она существует, является наибольшим элементом решетки \mathcal{L}. Эту единицу тогда называют единицей решетки \mathcal{L}, а саму решетку — решеткой с единицей.


Таким образом, решетка с нулем имеет нейтральный элемент по операции решеточного объединения (и ее верхняя полурешетка превращается в моноид), а решетка с единицей имеет нейтральный элемент по операции решеточного пересечения (и моноидом становится уже ее нижняя полурешетка). Кроме того, из теоремы 3.12 следует, что a\land\bold{0}=\bold{0} для любого a\in L (соответственно a\lor\bold{1}=\bold{1} для любого a\in L), т.е. выполняются аналоги аннулирующих свойств в симметричных полукольцах. Симметричное полукольцо является примером решетки с нулем и единицей.


Пример 3.18. На рис. 3.1 прямоугольник [a,b]\times [c,d] является решеткой с нулем и единицей, причем \bold{0}=(a,c),~ \bold{1}=(b,d).


Рассмотрим теперь вместо отрезка [a,b] промежуток A=\{x\colon\, x\leqslant b\} (\leqslant означает здесь естественный числовой порядок). Тогда множество A\times[c,d] при сохранении того же отношения порядка на \mathbb{R}^2, что и в примере 3.17, будет решеткой с единицей, равной (b,d). Нуля у этой решетки не будет (если рассматривать, конечно, нерасширенную числовую прямую, точнее, не включать в нее -\infty). Если же вместо отрезка [a,b] взять также неограниченный промежуток B=\{x\colon\, x\geqslant a\}, то B\times[c,d] будет решеткой с нулем, равным (a,c). Если опять-таки считать, что элемент +\infty не принадлежит \mathbb{R}, то эта решетка не будет иметь единицу.




В общем случае в решетке не имеет места дистрибутивность одной из операций относительно другой. На рис. 3.5 и 3.6 приведены диаграммы Хассе решеток, называемых соответственно Пентагоном и диамантом. В каждой из них ни одна из операций не является дистрибутивной относительно другой. Так, например, в первой из них


a\land (b\lor c)=a\land \bold{1}=a, но (a\land b)\lor (a\land c)=b\lor \bold{0}=b.

Для второй решетки a\land (b\lor c)=a\land \bold{1}=a, тогда как (a\land b)\lor (a\land c)=\bold{0}\lor \bold{0}=\bold{0}.


Диаграммы Хассе решеток - пентагон и диамант

Определение 3.6. Решетку \mathcal{L}=(L,\lor,\land)) называют дистрибутивной, если для любых a,b,c\in L имеют место равенства


a\lor (b\land c)= (a\lor b)\land (a\lor c),\qquad a\land (b\lor c)= (a\land b)\lor (a\land c).

Теперь мы можем дать в терминах решеток характеристику симметричных полуколец и булевых алгебр.


Теорема 3.14. Симметричное полукольцо — это дистрибутивная решетка с нулем и единицей.


Булева алгебра — это дистрибутивная решетка с нулем и единицей, в которой для каждого элемента х существует дополнение, т.е. такой элемент \overline{x}, что x\lor \overline{x}=\bold{1} и x\land\overline{x}=\bold{0}.


Доказательство теоремы 3.14 мы не приводим, так как оно является непосредственным следствием определении 3.3, 3.4 и 3.6.


Теория решеток находит многочисленные применения в теории графов и теоретическом программировании. В специальной литературе на базе теории решеток развиты стройная концепция типов данных в языках программирования и теория типов данных, хорошо изложены общая теория решеток и ее приложения к теории графов.

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2019 MathHelpPlanet.com. All rights reserved