Решётка (алгебра)

Диаграмма Хассе решётки всех делителей числа 60

Решётка (англ. lattice, нем. Verband) (ранее использовался термин структура) — частично упорядоченное множество, каждое двухэлементное подмножество которого обладает одновременно точной верхней и точной нижней гранями. Поэтому у произвольного непустого конечного подмножества решётки также имеются обе эти грани.

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

Линейно упорядоченное множество — частный случай решётки.

Понятие решётки (нем. Dualgruppe) возникло в середине XIX века, и наиболее полное определение было дано в работах Рихарда Дедекинда.

Определение

Решетка — частично упорядоченное множество $A$, в котором выполняются три аксиомы частичного порядка и одна специальная аксиома:

I. Отношение рефлексивности: для каждого $x\in A$ всегда выполняется $x\circ x$;

II. Отношение транзитивности: для любых $x,\,y,\,z\in A$, $x\circ y$, $y\circ z$ всегда выполняется $x\circ z$;

III. Отношение антисимметричности: для любых $x,\,y\in A$, $x\circ y$, $y\circ x$ всегда выполняется $x=y$;

IV. Для любых $x,\,y\in A$ найдётся супремум $\sup(x,\,y)$ и инфимум $\inf(x,\,y)$.

Синонимы: решёточно упорядоченное множество; бинаправленное множество.

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

Линейно упорядоченное множество — частный случай решётки.

Решётка в общем случае может не иметь нуля и единицы, то есть $\sup \varnothing =0$ и $\inf \varnothing =1$ в решётке могут не существовать.

Значимость решёток

Наиболее востребованы с получением важных результатов следующие частные случаи решёток: алгебраическая решётка, атомная решётка, решётка Брауэра, векторная решётка, дедекиндова решётка, дистрибутивная решётка, мультипликативная решётка, ортомодулярная решётка, полная решётка, свободная решётка, решётка с дополнениями, булева алгебра.

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

История

Джорж Буль

Рихард Дедекинд

Гаррет Биркгоф

Понятие булевой алгебры возникло в первой половине XIX века при исследовании английского математика и логика Джоржа Буля формализации пропозициональной логики. Понятие решётки возникло в середине XIX века.

В конце XIX века, занимаясь аксиоматикой булевых алгебр, американский логик и математик Чарльз Пирс и немецкий математик и логик Эрнст Шрёдер определили понятие решётки, но без введения самого термина. Наиболее полно это понятие независимо от них сформулировал немецкий математик Рихард Дедекинд в трудах 1894 и 1897 годов (у него решётка — нем. Dualgruppe) при изучении идеалов алгебраических чисел. Кроме того, Дедекинд изучал модулярность (модулярная решётка — нем. Dualgruppen von Modultypus), то есть ослабленную дистрибутивность. Ряд достаточно элегантных и глубоких ранних результатов этих математиков и американского математика Эдварда Хантингтона не были всё-таки замечены математической общественностью.

В середине тридцатых годов XX века труды американского математика Гарретта Биркгофа наконец подтолкнули общее развитие теории решёток, так как и сам Биркгоф, и советский математик и логик Валерий Иванович Гливенко, австрийско-американский математик Карл Менгер, венгеро-американский математик Джон фон Нейман, норвежский математик Ойстин Оре и другие достаточно продвинулись в этой новой области. В результате Биркгоф успешно «подал» теорию решёток математической общественности в первом издании монографии «Теория решёток». Развитие этой области математики от слеживается по первому, второму и третьему изданиям этой книги (1940, 1948, 1967).

Сам термин (англ. lattice), который затем первоначально перевели на русский как «структура», был введён в 1933 году Биркгофом. Сейчас термин «структура» из-за его многозначности в математике в русской терминологии вытеснен термином «решётка».

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

Обилие решёток в различных разделах математики не было ясно осознано до Дедекинда. После Дедекинда немецкий математик Эмми Нетер указала на важность решёток в алгебре. Важность в других разделах математики признавали независимо друг от друга немецкий математик Фриц Клейн-Бармен, Менгер и Биркгоф.

В 30-х годах XX века теория решёток обрела самостоятельность как раздел алгебры. Её наиболее важные разделы следующие:

• модулярные решётки,
• полные решётки,
• дистрибутивные решётки,
• булевы алгебры.

В итоге развитие теории решёток имеет три этапа. Первый период начался с опубликования в 1847 году английским математиком и логиком Джорджем Булем статьи «Математический анализ логики». Вслед за этим рядом математиков-логиков были рассмотрены аксиомы булевой алгебры и алгебры отношений. Итоги опубликованы в 1890—1895 годах немецким математиком и логиком Эрнстом Шрёдером в трёхтомной «Алгебре логики».

В 1930 году вышла классическая книга «Современная алгебра», которую написал голландский математик и историк математики Бартель Леендерт Ван дер Варден. Второй этап развития теории структур наступил через два года. В 1933—1937 годах вышло несколько статей, написанных Биркгофом, Нейманом, Маршаллом Стоуном и советским математиком Леонидом Витальевичем Канторовичем, которые показали, что обобщения булевой алгебры до соответствующих «структур» основополагающие для современной алгебры, проективной геометрии, теории точечных множеств, функционального анализа, логики и теории вероятностей. Часть этих статей были предвосхищены в двух работах Дедекинда (которые остались почти незамеченными), Менгера, польско-американского математика и логика Альфреда Тарского и Фрица Клейна-Бармена.

Третий, современный, период характеризуется непрерывным возникновением новых исследований теории решёток, которая стала существенным направлением современной алгебры. как и её старшая сестра — теория групп — теория решёток богата абстрактными идеями, общими для нескольких направлений математики, которые до сих пор не были связаны. Основа обеих теорий — аксиомы, которые обладают очень простой и общематематической природой.

Решётка как универсальная алгебра

Определение универсальной алгебры на основе решётки

Решётку можно также определить как универсальную алгебру с двумя бинарными операциями. Для этого определяют следующие две операции:

$a+b=\sup\{a,\,b\},\quad$ $a\cdot b=\inf\{a,\,b\}.$

Вместо обозначений $+$ и $\cdot$ часто используют другие символы: соответственно либо $\cup$ и $\cap$, либо $\vee$ и $\wedge$.

Операция $a+b=\sup\{a,\,b\}$ называется сложением, операция $a\cdot b=\inf\{a,\,b\}$ — умножением.

Синонимы операций: операции $a+b=\sup\{a,\,b\}$ и $a\cdot b=\inf\{a,\,b\}$ называются также соответственно объединение и пересечение, или супре́мум и и́нфимум.

Так определённая универсальная алгебра отвечает следующим тождествам:

• L1) идемпотентность:

(1) $a+a=a$, $\quad$(1') $a\cdot a=a$;

• L2) коммутативность:

(2) $a+b=b+a$, $\quad$(2') $a\cdot b=b\cdot a$;

• L3) ассоциативность:

(3) $(a+b)+c=a+(b+c)$, $\quad$(3') $(a\cdot b)\cdot c=a\cdot (b\cdot c)$;

• L4) поглощение:

(4) $a\cdot (a+b)=a$, $\quad$(4') $a+(a\cdot b)=a$.

Кроме того, элементы $0$ и $1$ отвечают равенствам

$a\cdot 0=0$, $\quad a\cdot 1=a$, $\quad a+0=a$, $\quad a+1=1$,

при любых $a$, причём первые три из них аналогичны соответствующим законам обычной арифметики.

Определение решётки на основе универсальной алгебры

И наоборот, рассмотрим множество $M$ с некоторыми двумя бинарными операциями, которые удовлетворяют приведённым ранее свойствам L1—L4. Тогда на множестве $M$ можно определить порядок $\leqslant$ следующим образом:

$a\leqslant b$ при $a+b=b$,

при этом сразу автоматически получится и следующее определение:

$a\leqslant b$ при $a\cdot b=a$,

другими словами, следующие три утверждения эквивалентны:

$a\leqslant b$, $\quad a+b=b$, $\quad a\cdot b=a$.

Получающееся при таком конструировании частично упорядоченное множество оказывается решёткой со следующими определениями:

$\sup\{a,\,b\}=a+b,\quad$ $\inf\{a,\,b\}=a\cdot b.$

В итоге получаем, что решётка определяется как универсальная алгебра, которая определяется приведёнными ранее тождествами L1—L4, то есть решётка образует многообразие универсальных алгебр.

Примеры решёток

Большая доля важнейших изучаемых в математике частично упорядоченных систем суть решётки. Более того, в таких системах точная верхняя и нижняя границы $+$ и $\cdot$ обычно отвечают достаточно известным и важным построениям.

Диаграмма Хассе решётки всех подмножеств множества из двух элементов

1. $\langle P(A),\,\subseteq \rangle$. Множество всех подмножеств данного множества, которые упорядочены по включению множеств следующим образом:

$\sup\{A,\,B\}=A\cup B,\quad$ $\inf\{A,\,B\}=A\cap B.$

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

2. Любое линейно упорядоченное множество: при $a\leqslant b$ имеем:

$\sup\{a,\,b\}=b,\quad$ $\inf\{a,\,b\}=a$.

3. Все подпространства некоторого векторного пространства, которые упорядочены по включению множеств следующим образом:

$\sup\{a,\,b\}=\{\mathbf {x} \mid \mathbf {x} =\mathbf {a} +\mathbf {b} ,\,\mathbf {a} \in A,\,\mathbf {b} \in B\},$

$\inf\{a,\,b\}=A\cap B$.

4. $\langle \mathbb {N} ,\,\mid \rangle$. Все неотрицательные (или положительные) целые числа, которые упорядочены по делимости, то есть $a\leqslant b$ при $b=ac$ для некоторого $c$. Здесь $\sup\{a,\,b\}$ — наименьшее общее кратное, а $\inf\{a,\,b\}$ — наибольший общий делитель данных чисел. Это множество частично упорядочено в отличие от множества натуральных чисел (с нулём или без), упорядоченного по возрастанию, которое есть линейно упорядоченное множество. Например, при упорядочении по делимости числа 8 и 12 не сравнимы, а наименьшее число, следующим за 8 и 12 — их наименьшее общее кратное 24.

Максимум и минимум двух функций

5. Все вещественные функции, определённые на единичном отрезке $[0,\,1]$, упорядоченные следующим условием: $f\leqslant g$, если $f(t)\leqslant g(t)$ для всех $t\in [0,\,1]$. Здесь имеем:

$\sup\{f,\,g\}=u,\quad$ $u(t)=\max\{f(t),\,g(t)\}$,

$\inf\{f,\,g\}=v,\quad$ $v(t)=\min\{f(t),\,g(t)\}$.

Например, если $f(t)=t^{2}$, $g(t)=1-t^{2}$, то

$u(t)={\begin{cases}1-t^{2},&0\leqslant t\leqslant {\frac {\sqrt {2}}{2}},\\t^{2},&{\frac {\sqrt {2}}{2}}\leqslant t\leqslant 1,\end{cases}}$

$u(t)={\begin{cases}t^{2},&0\leqslant t\leqslant {\frac {\sqrt {2}}{2}},\\1-t^{2},&{\frac {\sqrt {2}}{2}}\leqslant t\leqslant 1.\end{cases}}$

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

6. Все подгруппы некоторой группы с теоретико-множественным включением. В этом случае бинарные операции решётки суть обычные объединение и пересечение множеств.

7. Рассмотрим множество $L$ всех отношений конгруэнтности на абстрактной алгебре $A$. Введём отношение порядка $\theta \leqslant \theta '$ случай, когда $\theta$ есть подразбиение $\theta '$, то есть из $x\equiv y(\operatorname {mod} \theta )$ вытекает $x\equiv y(\operatorname {mod} \theta ')$. Тогда $L$ есть решётка. Причём $\theta \cdot \theta '$ задаёт произведение разбиений $\theta$ и $\theta '$ в обычном смысле, то есть $x\equiv y(\operatorname {mod} \theta \cdot \theta ')$ равносильно $x\equiv y(\operatorname {mod} \theta )$ и $x\equiv y(\operatorname {mod} \theta ')$. Кроме того, в вырожденном случае, то есть когда на $A$ не задано никаких операций, $L$ есть решётка, состоящая из всех разбиений множества $A$.

8. Произвольное векторное пространство вещественных чисел $\mathbb {R} ^{n}$, для любых двух векторов $x=(x_{1},\,x_{2},\,\dots ,\,x_{n})$ и $y=(y_{1},\,y_{2},\,\dots ,\,y_{n})$ которого определено неравенство $x>y$, если $x_{i}\geqslant y_{i}$ для всех $i=1,\,2,\,\dots ,\,n$, причём $x_{i}>y_{i}$ по крайней мере при одном из $i$. Любое ограниченное подмножество этого пространства обладает точной верхней и точной нижней гранями, которые задаются покоординатно. Другими словами, пусть подмножество

$E=\{x^{(\gamma )}\}_{\gamma \in \Gamma }\subset \mathbb {R} ^{n}$, $x^{(\gamma )}=(x_{1}^{(\gamma )},\,x_{2}^{(\gamma )},\,\dots ,\,x_{n}^{(\gamma )})$,

причём $E$ ограничено сверху. Тогда

$\sup E=x=(x_{1},\,x_{2},\,\dots ,\,x_{n}),$

где $x_{i}=\sup _{\gamma }\{x_{i}^{(\gamma )}\}$ при любом $i=1,\,2,\,\dots ,\,n$.

9. Аналогично предыдущему примеру, упорядочивается множество всех векторов $x=(x_{1},\,x_{2},\,\dots ,\,x_{n},\,\dots )$ бесконечномерного вещественного векторного пространства. И также любое ограниченное подмножество этого пространства обладает точной верхней и точной нижней гранями, которые задаются покоординатно.

10. Совокупность всех порядковых чисел первого и второго классов как любых типов полного упорядочения конечных и счётных множеств упорядочена по возрастанию, так как два произвольных трансфинитных числа сравнимы.

11. Множество всех идеалов произвольного частично упорядоченного множества.

• Диаграммы Хассе частично упорядоченного множества и его решётки идеалов
• 
  Частично упорядоченное множество
• 
  Решётка, образованная всеми идеалами частично упорядоченного множества

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

Диаграмма Хассе не решётки: нет $\varnothing$

1. Множество, которое состоит из всех подмножеств некоторого множества, за исключением пустого множества, есть частично упорядоченное множество, но не является решёткой.

Максимум и минимум двух функций

2. Множество всех вещественных функций, определённые на единичном отрезке $[0,\,1]$, причём каждая функция больше нуля по крайней мере в одной точке, есть частично упорядоченное множество, но не решётка. Это следует из того, что $\inf \,\{f,\,g\}$ отсутствует в этом множестве тогда, когда $\min \,[f(t),\,g(t)]\leqslant 0$ в любой точке $t\in [0,\,1]$.

Например, если

$f(t)=t^{2}-0,5,\quad$ $g(t)=0,5-t^{2}$,

то

$\min \,[f,\,g]={\begin{cases}t^{2}-0,5,0\leqslant t\leqslant {\frac {\sqrt {2}}{2}},\\0,5-t^{2},{\frac {\sqrt {2}}{2}}\leqslant t\leqslant 1.\end{cases}}$

3. Дискретный порядок, когда любые два разных элемента несравнимы, будет решёткой, только если элемент один-единственный.

4. Делители числа 36 без 6 — {1, 2, 3, 12, 18, 36}, упорядоченные по делимости. Числа 2 и 3 не имеют точной верхней грани, а 12 и 18 — точной нижней.

Описания решётки

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

Табличный способ

Конечная решётка наглядно описывается с помощью двух таблиц:

• таблицы сложения (или объединений), которая определяет результат сложения элементов решётки;
• таблицы умножения (или пересечений), определяющей результат умножения.

Пример. Рассмотрим решётку $L=\{0,\,a,\,b,\,1\}$. Таблицы сложения и умножения для этой решётки имеет следующий вид:

Таблица сложения

$+$	$0$	$a$	$b$	$1$
$0$	$0$	$a$	$b$	$1$
$a$	$a$	$a$	$1$	$1$
$b$	$b$	$1$	$b$	$1$
$1$	$1$	$1$	$1$	$1$

Таблица умножения

$\cdot$	$0$	$a$	$b$	$1$
$0$	$0$	$0$	$0$	$0$
$a$	$0$	$a$	$0$	$a$
$b$	$0$	$0$	$b$	$b$
$1$	$0$	$a$	$b$	$1$

Хорошо видно, что большая часть данных в таблицах повторяется и даже лишняя:

• обе операции коммутативны, $x+y=y+x$, $x\cdot y=y\cdot x$поэтому таблицы симметричны относительно главной диагонали;
• обе операции идемпотентны, $x+x=x$, $x\cdot x=x$, поэтому на главных диагоналях нет новых данных,

следовательно, две таблицы можно объединить в следующую одну таблицу:

Объединённая таблица

$+$	$0$	$a$	$b$	$1$
$\cdot$
$0$		$a$	$b$	$1$
$a$	$0$		$1$	$1$
$b$	$0$	$0$		$1$
$1$	$0$	$a$	$b$

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

Для доказательства того, что таблица действительно задаёт решётку, достаточно проверить только ассоциативность и поглощение операций.

Описание частичным порядком

Второй способ представляет собой описание частичного порядка, то есть множество всех пар $\langle x,\,y\rangle$ элементов решётки, связанных отношением $x\leqslant y$.

Рассмотрим в качестве примера решётку $L=\{0,\,a,\,b,\,1\}$. Частичный порядок для этой решётки имеет следующий вид:

$\leqslant {}=\{\langle 0,\,0\rangle ,\langle 0,\,a\rangle ,\langle 0,\,b\rangle ,\langle 0,\,1\rangle ,\langle a,\,a\rangle ,\langle a,\,1\rangle ,\langle b,\,b\rangle ,\langle b,\,1\rangle ,\langle 1,\,1\rangle \}.$

Хорошо видно, что большая часть данных в парах лишняя:

• все пары, имеющие вид $\langle x,\,x\rangle$, в списке лишние, так как $x\leqslant x$;
• если $x\leqslant y$ и $y\leqslant z$, то $x\leqslant z$. Например, если $0\leqslant a$ и $a\leqslant 1$, то неравенство $0\leqslant 1$ лишнее.

Эти соображения определяют следующую терминологию для частично упорядоченного множества.

Отношение покрываемости состоит в следующем. Элемент $a$ частично упорядоченного множества покрывает элемент $b$, а $b$ покрывается $a$, $a\,\rangle \!\!\!-b$ или $b-\!\!\!\langle \,a$, если:

• $a>b$;
• не найдётся $x$, $a>x>b$.

Отношение покрываемости для решётки $L=\{0,\,a,\,b,\,1\}$ имеет следующий вид:

${}-\!\!\!\langle \,=\{\langle 0,\,a\rangle ,\langle 0,\,b\rangle ,\langle a,\,1\rangle ,\langle b,\,1\rangle \}.$

Возникает вопрос, задаёт ли отношение покрываемости частичный порядок на множестве? Следующая «лемма» отвечает, что задаёт: для произвольных элементов $a$ и $b$ частично упорядоченного множества $P$ отношение $a\leqslant b$ верно тогда и только тогда, когда либо $a=b$, либо найдётся такая конечная последовательность элементов множества $x_{0},\,x_{1},\,\dots ,\,x_{n-1}$, что $x_{0}=a$, $x_{n-1}=b$, а $x_{i}-\!\!\!\langle \,x_{i+1}$ для всех $0\leqslant i\leqslant n-2$.

Действительно, пусть указанная последовательность найдётся, тогда

$a=x_{0}\leqslant x_{1}\leqslant \cdots \leqslant x_{n-1}=b$

и математическая индукция по $n$ даёт $a\leqslant b$.

Обратно, если $a<b$, то указанная последовательность найдётся. Действительно, выберем произвольные элементы $a,\,b\in P$, $a<b$. Пусть $H$ — цепь в $P$, у которой $a$ — наименьший элемент цепи, а $b$ — наибольший. Такие цепи всегда имеются, например, $\{a,\,b\}$.

Пусть теперь наибольшая из цепей $H$ содержит $m$ элементов, $H=\{x_{0},\,x_{1},\,\dots ,\,x_{m-1}\}$, $a=x_{0}<x_{1}<\cdots <x_{m-1}=b$. Оказывается, что $a=x_{0}-\!\!\!\langle \,x_{1}-\!\!\!\langle \,\cdots -\!\!\!\langle \,x_{m-1}=b$. От противного. Имеем по предположению: $x_{i}<x_{i+1}$. Следовательно, если не выполняется $x_{i}-\!\!\!\langle \,x_{i+1}$, то найдётся $x\in P$, $x_{i}<x<x_{i+1}$. Но тогда $H\cup \{x\}$ есть снова цепь от $a$ до $b$ уже из $m+1$ элементов, что противоречит максимальности исходной цепи $H$.

Описание диаграммой Хассе

Диаграмма Хассе решётки $L=\{0,\,a,\,b,\,1\}$

На диаграмме Хассе решётки маленькими окружностями ○ представлены его элементы, а соединение отрезком двух элементов означает, что один элемент покрывает другой, причём покрывающий элемент рисуется выше.

Диаграммы «бесконечных» решёток всегда наделяются комментариями при их описании.

На диаграмме Хассе наглядно видна структура решётки, а также все связи между её элементами: хорошо просматриваются максимальные и минимальные элементы, ясно представлена каждая цепь, соединяющая два данных элемента, и так далее. Один элемент меньше другого тогда и только тогда, когда на диаграмме Хассе между ними существует восходящая ломаная.

Существует всего 4 неизоморфные разновидности решёток с числом элементов от 1 до 4, все они двойственны себе.

Существует всего 5 неизоморфных разновидностей решёток с 5 элементами, 3 из них двойственны себе. Получить эти 5 решёток можно, добавляя элементы $0$ и $1$ к 5 неизоморфным разновидностям частично упорядоченных множеств из 3 элементов.

Существует всего 15 неизоморфных разновидностей решёток с 6 элементами, 7 из них двойственны себе. Получить эти 15 решёток можно, добавляя элементы $0$ и $1$ к 16 (шестнадцати) неизоморфным разновидностям частично упорядоченных множеств из 4 элементов.

• Неизоморфные диаграммы Хассе решёток с 1—4 элементами
• 
  Линейное упорядочение
• 
  Линейное упорядочение
• 
  Линейное упорядочение
• 
  Частичное упорядочение

• Неизоморфные диаграммы Хассе решёток с 5 элементами
• 
  Само­двой­ст­вен­ная
• 
  Пяти­у­голь­ник $N_{5}$. Само­двой­ст­вен­ная
• 
  Ромб $M_{3}$. Самодвой­ственная
• 
  Двой­ст­вен­ная сле­ду­ю­щей
• 
  Двой­ст­вен­ная пре­ды­ду­щей

Описание модифицированной диаграммой Хассе

Модифицированная диаграмма Хассе решётки $L=\{0,\,a,\,b,\,1\}$

Диаграмма Хассе не является графом, потому на диаграмме что имеется фиксация уровня элементов в решётке.

Модифицированная диаграмма Хассе — ориентированный граф, который получается из диаграммы Хассе ориентацией её отрезков в направлении от меньшего элемента к большему.

Модифицированная диаграмма Хассе не только показывает все данные исходной диаграммы, но и представляет собой граф, дающий новые возможности для исследования особенностей представляемой решётки.

• Диаграммы множества всех подмножеств трёхэлементного множества
• 
  Диаграмма Хассе
• 
  Модифицированная диаграмма Хассе

Описание ориентированным графом

Ориентированный граф решётки $L=\{0,\,a,\,b,\,1\}$

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

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

Описание диаграммой Эйлера

Пересечение элементов решётки

Решётки при небольшом количестве элементов удобно задавать диаграммой Хассе. Но для сложно устроенных решеток обращение к таким диаграммам мало помогает интуиции.

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

А именно, любая решётка $\langle A,\,\subseteq \rangle$ вкладывается в множество всех подмножеств $P(A)$ отображением $\varphi \colon A\to P(A)$, которое каждому элементу $x\in A$ ставит в соответствие главный идеал $J(x)\in P(A)$.

Поэтому элементы произвольной решётки отождествляются с подмножествами соответствующего множества $A$, а их пересечение — с пересечением подмножеств $A$. В этом случае, если в решётке есть наибольший элемент $1$, то $\varphi (1)=J(1)=A$, а если есть наименьший $0$, то $\varphi (0)=J(0)=\{\varnothing \}$ (поскольку $0$ принадлежит всем идеалам, то его можно удалить, при этом отношение включения между идеалами не изменится).

Объединение элементов решётки

Схемы задания решёток, подобные диаграммам Эйлера, отличаются от них изображением объединения двух элементов $\varphi (x+y)\supseteq \varphi (x)\cup \varphi (y)$, так как

$z\in \varphi (x)\cup \varphi (y)=J(x)\cup J(y)\Rightarrow$ $z\in J(x)$ или $z\in J(y)\Rightarrow$

$\Rightarrow z\leqslant x$ или $z\leqslant y\Rightarrow$ $z\leqslant x+y\Rightarrow$ $z\in J(x+y)=\varphi (x+y)$,

но в общем случае равенство отсутствует, причём равенство имеет место тогда и только тогда, когда $x$ и $y$ сравнимы. Следовательно, при визуализации объединения элементов, которые представлены связными выпуклыми фигурами, всегда рисуют такую выпуклую фигуру, которая «с запасом» их покрывает (см. рисунок справа).

Свойства решёток

Следующие неравенства верны для любой решётки.

1. Неравенство дистрибутивности:

$(x\cdot y)+(x\cdot z)\leqslant x\cdot (y+z)$.

2. Неравенство дистрибутивности:

$x+(y\cdot z)\leqslant (x+y)\cdot (x+z)$.

3. Неравенство дистрибутивности:

$(x\cdot y)+(y\cdot z)+(z\cdot x)\leqslant (x+y)\cdot (y+z)\cdot (z+x)$.

4. Неравенство модулярности:

$(x\cdot y)+(x\cdot z)\leqslant x\cdot (y+(x\cdot z))$.

Математические выкладки

Действительно, из

$(x\cdot y)\leqslant x,\,\quad$ $(x\cdot z)\leqslant x,\,\quad$

следует

(*) $(x\cdot y)+(x\cdot z)\leqslant x.$

Аналогично из

$(x\cdot y)\leqslant y\leqslant y+(x\cdot z),\,\quad$ $(x\cdot z)\leqslant y+(x\cdot z),\,\quad$

следует

(**) $(x\cdot y)+(x\cdot z)\leqslant y+(x\cdot z).$

Используя для неравенств (*) и (**) операцию $\cdot$, получаем неравенство модулярности.

5. Следующие выражения равносильны для любой решётки $L$:

(i) $(x\cdot y)+(x\cdot z)=x\cdot (y+z)$;

(ii) $(x+y)\cdot (x+z)=x+(y\cdot z)$;

(iii) $(x+y)\cdot z\leqslant x+(y\cdot z)$.

Дистрибутивная решётка — решетка, для всех элементов которой верны (i) или (ii). Причём (i) и (ii) не эквивалентны: в недистрибутивной решётке (i) может быть верно для некоторых трёх элементов $a,\,b,\,c,\,\in L$, а (ii) — нет, и наоборот.

Решётка как малая категория

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

Понятия изоморфизма решёток, которые рассматриваются и как универсальные алгебры, и как частично упорядоченные множества, одинаковы. Рассмотрим две решётки $L$ и $L'$ и их изоморфизм $\varphi$ как частично упорядоченных множеств. Тогда $\varphi$ есть также изоморфизм этих решёток как универсальных алгебр, то есть при произвольных $x,\,y\in L$ верны следующие равенства:

$\varphi (x+y)=\varphi (x)+\varphi (y)$, $\quad \varphi (x\cdot y)=\varphi (x)\cdot \varphi (y)$.

Но любое изотонное отображение решётки $L$ в решётку $L'$, то есть такое отображение $\varphi$, что из $x\leqslant y$ следует $\varphi (x)\leqslant \varphi (y)$, в общем случае не обязательно есть гомоморфизм этих решёток, рассматриваемых как универсальные алгебры.

При произвольном $a\in L$ отображения $\varphi (x)=x+a$ и $\psi (x)=x\cdot a$ есть изотонные отображения решётки $L$ в себя, которые суть также и гомоморфизмы тогда и только тогда, когда $L$ есть дистрибутивная решётка.

Отображение $\varphi (x)=x+a$ есть гомоморфизм полурешётки $L$ с операцией $+$, а отображение $\psi (x)=x\cdot a$ есть гомоморфизм полурешётки $L$ с операцией $\cdot$.

Множество всех решёток составляет категорию при условии, что гомоморфизмы считаются морфизмами.

Антигомоморфизм решётки

Антигомоморфизм решётки $L$ в решётку $L'$ — отображение $\varphi (x)\colon L\to L'$ такое, что при произвольных $x,\,y\in L$ верны следующие равенства:

$\varphi (x+y)=\varphi (x)\cdot \varphi (y)$, $\quad \varphi (x\cdot y)=\varphi (x)+\varphi (y)$.

Повторное выполнение антигомоморфизма есть гомоморфизм.

Частично упорядоченное множество, антигомоморфное некоторой решётке, есть решётка.

Координация решётки

Координация решётки — поиск такой алгебраической системы, обычно в универсальной алгебре, что данная решётка изоморфна либо решётке подсистем, либо решётке конгруэнций, либо другой решётке, согласованной с этой алгебраической системой или некоторой универсальной алгеброй.

Любая решётка с 0 и 1 обычно координируется частично упорядоченной полугруппой её резидуальных отображений в себя, при этом она изоморфна решётке правых аннуляторов этой частично упорядоченной полугруппы. Сама полугруппа бэровская, поскольку оба аннулятора, правый и левый, любого из её элементов порождается идемпотентом.

Подрешётка

Основная статья: Подрешётка

Не следует путать с подрешёткой — подгруппой решётки в геометрии.

Подрешётка ― непустое подмножество некоторой решётки, замкнутое относительно обеих операций $+$ и $\cdot$ именно исходной решётки. Другими словами, подрешётка есть подалгебра некоторой решётки, определённой как универсальная алгебра, имеющая две бинарные операции.

Подрешётка — второе основное понятие теории решёток после понятия решётки.

Подмножество решётки может быть решёткой и в то же время не быть подрешёткой.

Примеры выпуклых подрешёток:

• любое одноэлементное подмножество решётки,
• идеал,
• фильтр,
• интервал.

Модулярная решётка

Основная статья: Модулярная решётка

Модулярный закон для решётки

Модулярная, или дедекиндова, решётка, — решётка $L$ такая, что для её трёх произвольных элементов $x,\,y,\,z\in L$ выполняется следующая самодвойственная импликация — модулярный закон:

$x\leqslant y\Rightarrow x+(y\cdot z)=y\cdot (x+z)=(x+z)\cdot y$.

На рисунке справа представлен модулярный закон для решёток в виде схемы, подобной диаграмме Эйлера. Эта схема показывает, что элементы из $z$, не входящие в $y$, никак не влияют на значение операции $x+(y\cdot z)$.

Любые линейно упорядоченные множества, решётки $\langle P(A),\,\subseteq \rangle$, $\langle \mathbb {N} ,\,\mid \rangle$ и их подрешётки суть модулярные и даже дистрибутивные решётки.

Множество всех модулярных решеток замкнуто относительно дуальных изоморфизмов, поэтому на модулярных решетках действует принцип двойственности.

Модулярные решетки составляют эквациональный класс, то есть многообразие решеток. Поэтому все гомоморфные образы и подрешётки модулярной решётки суть снова модулярные решётки, как и прямые произведения модулярных решёток.

Для любой решётки следующие четыре условия равносильны:

(i) решётка модулярна;

(ii) выполняется следующее условие:

$x+(y\cdot z)=x+((y+(x\cdot z))\cdot z)$;

(iii) пятиугольник $N_{5}$ не содержится в решётке, то есть не изоморфен подрешётке;

(iv) выполняется следующее условие:

$x+((x+y)\cdot z)=(x+y)\cdot (x+z)$.

Тождества (ii) и (iv) применяются без каких-либо предположений, в этом их смысл и удобство. Следует иметь в виду двойственные выражения:

$x\cdot (y+z)=x\cdot ((y\cdot (x+z))+z)$;

$x\cdot ((x\cdot y)+z)=(x\cdot y)+(x\cdot z)$.

Условие (iii) — основной критерий проверки решётки на модулярность.

Пятиугольник $N_{5}$ — единственная пятиэлементная немодулярная решётка. Более того, $N_{5}$ есть подрешётка произвольной немодулярной решётки, другими словами, это наименьшая немодулярная решётка.

Модулярная решётка дистрибутивна тогда и только тогда, когда ромб $M_{3}$ в ней не содержится, то есть не изоморфен какой-либо подрешётке.

Дистрибутивная решётка

Дистрибутивная решётка — решётка $L$ такая, что для её трёх произвольных элементов $x,\,y,\,z\in L$ выполняется следующее тождество — дистрибутивный закон:

$x+(y\cdot z)=(x+y)\cdot (x+z)$.

Смысл дистрибутивного закона для решёток состоит в истинности противоположного неравенства, поскольку в произвольной решётке всегда выполняется следующее неравенство:

$x+(y\cdot z)\geqslant y\cdot (x+z)=(x+z)\cdot y$.

Модулярность есть ослабленная дистрибутивность, поэтому любая дистрибутивная решетка модулярна.

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

Двойственная дистрибутивной решётка дистрибутивна. Дистрибутивные решётки подпадают под принцип двойственности. Отсюда верно следующее двойственное равенство:

$x\cdot (y+z)=(x\cdot y)+(x\cdot z)$.

Это равенство вместе с равенством из определения дистрибутивной решётки не имеют аналога в обычной алгебре, где в общем случае имеет место следующее неравенство:

$x+(y\cdot z)\neq (x+y)\cdot (x+z)$.

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

Имеет место следующая теорема Биркгофа:

любая дистрибутивная решётка вкладывается в решётку множество всех подмножеств $\langle P(A),\,\subseteq \rangle$ соответствующего множества $A$.

Две пятиэлементные решётки, пятиугольник $N_{5}$ и ромб $M_{3}$, — типичные примеры недистрибутивной решётки, которые играют важную роль в теории решёток.

Модулярная решётка дистрибутивна тогда и только тогда, когда ромб $M_{3}$ в ней не содержится, то есть не изоморфен какой-либо подрешётке.

Решётка дистрибутивна тогда и только тогда, когда ни пятиугольник $N_{5}$, ни ромб $M_{3}$ в ней не содержатся, то есть они не изоморфны каким-либо подрешёткам.

См. также

• Математическая структура
• Анализ формальных понятий
• Полурешётка

Литература

• Богомолов А. М, Салий В. Н. Алгебраические основы теории дискретных систем (рус.). — М.: Наука. Физматлит, 1997. — 368 с., ил. — ISBN 5-02-015033-9.
• Биркгоф Г. Теория решёток = Garrett Birkhoff, Lattice theory (1967) (рус.) / Перевёл с англ. В. Н. Салий под ред. Л. А. Скорнякова. — М.: «Наука», 1984. — 566 с.: ил. — 9400 экз.
• Биркгоф Г. Теория структур = Garrett Birkhoff, Lattice theory. Revised Edition (1948) (рус.) / Пер. с англ. М. И. Граева. — М.: «Издательство иностранной литературы», 1952. — 407 с.: ил.
• Вулих Б. З. Введение в теорию полуупорядоченных пространств (рус.). — М.: Физматгиз, 1961. — 407 с. — 9000 экз.
• Гретцер Г.. Общая теория решёток = George Grätzer. General Lattice Theory (1978) (рус.) / Пер. с англ. А. Д. Больбота, В. А. Горбунова и В. И. Туманова под ред. Д. М. Смирнова. — М.: «Мир», 1982. — 452 с.: ил. — 6000 экз.
• Гуров С. И. Булевы алгебры, упорядоченные множества, решётки: определения, свойства, примеры (рус.). — 2-е изд. — М.: URSS : Книжный дом «Либроком», 2013. — 221 с., ил. — (Основы защиты информации. Секретно для пользы = Secreto ad utilitatem). — ISBN 978-5-397-03899-7.
• Житомирский Г. И. Упорядоченные множества и решётки. — Саратов, 1981;
• Салий В. Н. Решетки с единственными дополнениями (рус.). — М.: «Наука», 1984. — 128 с., ил. — 4400 экз.
• Скорняков Л. А. Дедекиндова решётка // Математическая энциклопедия : [в 5 т.] / Гл. ред. И. М. Виноградов. — М.: Советская энциклопедия, 1979. — Т. 2: Д — Коо. — Стб. 63—64. — 1104 стб. : ил. — 148 800 экз.
• Скорняков Л. А. Решётка // Математическая энциклопедия : [в 5 т.] / Гл. ред. И. М. Виноградов. — М.: Советская энциклопедия, 1984. — Т. 4: Ок — Сло. — Стб. 980—982. — 1216 стб. : ил. — 148 900 экз.
• Скорняков Л. А. Решётка // Математический энциклопедический словарь / Гл. ред. Ю. В. Прохоров. Ред. кол. С. И. Адян, Н. С. Бахвалов, В. И. Битюцков, А. П. Ершов, Л. Д. Кудрявцев, А. Л. Онищик, А. П. Юшкевич. — М.: «Советская энциклопедия», 1988. — С. 527. — 847 с., ил. — 148 900 экз.
• Скорняков Л. А. Элементы теории структур (рус.). — М.: «Наука», 1970. — 148,[1] с., ил. — 12 000 экз.
• Стенли Р. Перечислительная комбинаторика = Richard P. Stanley. Enumerarive combinatorics. Volume I (рус.) / Пер. с англ. А. И. Барвинка, А. А. Лодкина под ред. А. М. Вершика. — М.: «Мир», 1990. — 440 с., ил. — 5500 экз. — ISBN 5-03-001348-2.
• Структура // Большая советская энциклопедия. (В 30 томах) (рус.) / гл. ред. А. М. Прохоров. — 3-е изд. — М.: «Советская энциклопедия», 1975. — Т. 24 Собаки — Струна. — С. 599. — 608 с., ил., 30 л. ил., 5 л. карт. — 631 тыс. экз.
• Фофанова Т. С. Подрешётка // Математическая энциклопедия (рус.) / гл. ред. И. М. Виноградов. — М.: «Советская энциклопедия», 1984. — Т. 4 Ок—Сло. — Стб. 380. — 1216 стб., ил. — 148 900 экз.

Дополнительная литература

Доступные бесплатно в интернете монографии:

• Burris, Stanley N., H.P. Sankappanavar. A Course in Universal Algebra. — Springer-Verlag, 1981. ISBN 3-540-90578-2.
• Peter Jipsen, Henry Rose. Varieties of Lattices — Lecture Notes in Mathematics 1533, Springer Verlag, 1992. ISBN 0-387-56314-8.

Элементарные тексты для обладающих малой математической культурой:

• Thomas Donnellan. Lattice Theory. — Pergamon, 1968.
• G. Grätzer. Lattice Theory: First concepts and distributive lattices. — W. H. Freeman, 1971.

Обычные введения в предмет, несколько более сложные, чем указанный выше:

• B.A. Davey, H. A. Priestley. Introduction to Lattices and Order. — Cambridge University Press, 2002.

Продвинутые монографии:

• Garrett Birkhoff. Lattice Theory. — 3rd ed. Vol. 25 of AMS Colloquium Publications. American Mathematical Society, 1967.
• Robert P. Dilworth, Peter Crawley. Algebraic Theory of Lattices. — Prentice-Hall, 1973. ISBN 978-0-13-022269-5.

О свободных решётках:

• R. Freese, J. Jezek, J. B. Nation. Free Lattices. — Mathematical Surveys and Monographs Vol. 42. Mathematical Association of America, 1985.
• P.T. Johnstone. Stone spaces. — Cambridge Studies in Advanced Mathematics 3. Cambridge University Press, 1982.