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

У этого термина существуют и другие значения, см. Решётка.

Решётка^[1][2][3] (англ. lattice, нем. Verband^[4]) (ранее использовался термин структура^[4][5][6][7]) — частично упорядоченное множество, каждое двухэлементное подмножество которого обладает одновременно точной верхней и точной нижней гранями. Поэтому у произвольного непустого конечного подмножества решётки также имеются обе эти грани➤^{[1][2][3][4][5][6][7]}.

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

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

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

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

Определение

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

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

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

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

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

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

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

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

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

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

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

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

История

Понятие решётки возникло в середине XIX века^[1][12]. Наиболее полно это понятие сформулировал немецкий математик Рихард Дедекинд в трудах 1894 и 1897 годов. Сам термин (англ. lattice), который затем перевели на русский как «структура», был введён в 1933 году американским математиком Гарретом Биркгофом. Сейчас термин «структура» из-за его многозначности в математике в русской терминологии вытеснен термином «решётка»^[1].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(4) ${\displaystyle a\cdot (a+b)=a}$^{[комм 1]}, ${\displaystyle \quad }$(4') ${\displaystyle a+(a\cdot b)=a}$.

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

${\displaystyle a\cdot 0=0}$, ${\displaystyle \quad a\cdot 1=a}$, ${\displaystyle \quad a+0=a}$, ${\displaystyle \quad a+1=1}$,

при любых ${\displaystyle a}$, причём первые три из них аналогичны соответствующим законам обычной арифметики^[16].

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

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

${\displaystyle a\leqslant b}$ при ${\displaystyle a+b=b}$,

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

${\displaystyle a\leqslant b}$ при ${\displaystyle a\cdot b=a}$,

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

${\displaystyle a\leqslant b}$, ${\displaystyle \quad a+b=b}$, ${\displaystyle \quad a\cdot b=a}$.

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

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

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

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

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

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

1. Множество всех подмножеств данного множества, которые упорядочены по включению множеств следующим образом^{[1][2][13][17]}:

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

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

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

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

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

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

${\displaystyle \inf\{a,\,b\}=A\cap B}$^{[комм 1]}.

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

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

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

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

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

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

${\displaystyle 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}}}$

${\displaystyle 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}}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

то

${\displaystyle \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 — точной нижней.

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

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

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

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

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

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

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

${\displaystyle +}$	${\displaystyle 0}$	${\displaystyle a}$	${\displaystyle b}$	${\displaystyle 1}$
${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle a}$	${\displaystyle b}$	${\displaystyle 1}$
${\displaystyle a}$	${\displaystyle a}$	${\displaystyle a}$	${\displaystyle 1}$	${\displaystyle 1}$
${\displaystyle b}$	${\displaystyle b}$	${\displaystyle 1}$	${\displaystyle b}$	${\displaystyle 1}$
${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle 1}$

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

${\displaystyle \cdot }$	${\displaystyle 0}$	${\displaystyle a}$	${\displaystyle b}$	${\displaystyle 1}$
${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle 0}$
${\displaystyle a}$	${\displaystyle 0}$	${\displaystyle a}$	${\displaystyle 0}$	${\displaystyle a}$
${\displaystyle b}$	${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle b}$	${\displaystyle b}$
${\displaystyle 1}$	${\displaystyle 0}$	${\displaystyle a}$	${\displaystyle b}$	${\displaystyle 1}$

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

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

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

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

${\displaystyle +}$	${\displaystyle 0}$	${\displaystyle a}$	${\displaystyle b}$	${\displaystyle 1}$
${\displaystyle \cdot }$
${\displaystyle 0}$		${\displaystyle a}$	${\displaystyle b}$	${\displaystyle 1}$
${\displaystyle a}$	${\displaystyle 0}$		${\displaystyle 1}$	${\displaystyle 1}$
${\displaystyle b}$	${\displaystyle 0}$	${\displaystyle 0}$		${\displaystyle 1}$
${\displaystyle 1}$	${\displaystyle 0}$	${\displaystyle a}$	${\displaystyle b}$

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

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

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

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

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

${\displaystyle \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 \}.}$

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

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

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

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

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

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

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

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

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

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

и математическая индукция по ${\displaystyle n}$ даёт ${\displaystyle a\leqslant b}$^[24].

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

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

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

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

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

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

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

Существует всего 5 неизоморфных разновидностей решёток с 5 элементами, 3 из них двойственны себе. Получить эти 5 решёток можно, добавляя элементы ${\displaystyle 0}$ и ${\displaystyle 1}$ к 5 неизоморфным разновидностям частично упорядоченных множеств из 3 элементов^[25][26][27].

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

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

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

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

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

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

${\displaystyle \varphi (x+y)=\varphi (x)+\varphi (y)}$, ${\displaystyle \quad \varphi (x\cdot y)=\varphi (x)\cdot \varphi (y)}$^{[комм 1]}.

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

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

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

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

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

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

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

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

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

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

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

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

Подрешётка

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

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

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

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

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

Примеры выпуклых подрешёток^[32][6]:

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

См. также

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