Подрешётка

Обзорная статья: Решётка (алгебра)

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

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

Слева закрашены элементы подрешётки, справа — решётки, но не подрешётки

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

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

Примеры выпуклых подрешёток: любое одноэлементное подмножество решётки; идеал➤; фильтр➤; интервал➤^[1][5].

Идеал и фильтр обладают свойством кастовости, то есть их можно определить следующим образом: два элемента им принадлежат тогда и только тогда, когда им принадлежит соответствующая бинарная операция с этими элементами➤➤^[6][7].

Подрешётка может быть порождена любым подмножеством решётки➤^[2].

Определение

Рассмотрим некоторое подмножество ${\displaystyle L_{1}}$ решётки ${\displaystyle L}$. Тогда множество ${\displaystyle L_{1}}$ частично упорядочено при том же отношении порядке, которое действует на его надмножестве ${\displaystyle L}$, но при этом в общем случае ${\displaystyle L_{1}}$ не обязательно решётка^[4].

При описанной ситуации возможно, что подмножество ${\displaystyle L_{1}}$ оказывается решёткой, но для некоторых ${\displaystyle a,\,b\in L_{1}}$ их ${\displaystyle \sup\{a,\,b\}}$ (или ${\displaystyle \inf\{a,\,b\}}$) в подмножестве ${\displaystyle L_{1}}$ отличается от ${\displaystyle a+b}$ (соответственно от ${\displaystyle a\cdot b}$), который определён в надмножестве ${\displaystyle L}$^[4].

Причём этот ${\displaystyle \sup\{a,\,b\}}$ (или этот ${\displaystyle \inf\{a,\,b\}}$) оказывается больше (соответственно меньше) чем этот ${\displaystyle a+b}$ (соответственно этот ${\displaystyle a\cdot b}$). Действительно, поскольку ${\displaystyle L_{1}\subset L}$, то в ${\displaystyle L}$ множество ${\displaystyle \{a,\,b\}}$, как и любое другое подмножество из ${\displaystyle L_{1}}$, может иметь только более обширный набор верхних (соответственно нижних) границ, чем в ${\displaystyle L_{1}}$^[4].

Подрешётка — подмножество ${\displaystyle L_{1}}$ решётки ${\displaystyle L}$ такое, что при произвольной паре ${\displaystyle a,\,b\in L_{1}}$ обе её грани ${\displaystyle a+b}$ и ${\displaystyle a\cdot b}$, которые вычислены в исходной решётке ${\displaystyle L}$, лежат снова в подмножестве ${\displaystyle L_{1}}$^[3]. Другими словами, подрешётка есть подалгебра некоторой решётки, определённой как универсальная алгебра, имеющая две бинарные операции^[1].

Подрешётки, как и решётки, также обозначаются упорядоченной парой ${\displaystyle (L_{1},\,\leqslant )}$ или упорядоченной тройкой ${\displaystyle (L_{1},\,+,\,\cdot )}$, где ${\displaystyle L_{1}}$ — множество-носитель подрешётки^[8].

Когда ${\displaystyle L_{1}}$ есть подрешётка решётки ${\displaystyle L}$, то для произвольного конечного подмножества из ${\displaystyle L_{1}}$ его верхние (или нижние) грани, вычисленные как в ${\displaystyle L_{1}}$, так и в ${\displaystyle L}$, совпадают^[3].

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

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

Примеры решёток как не подрешёток

Решётка, но не подрешётка

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

Решётка, но не подрешётка

2. Рассмотрим трёхмерное евклидово пространство ${\displaystyle \mathbb {R} ^{3}(x_{1},\,x_{2},\,x_{3})}$, а в нём — наклонную плоскость ${\displaystyle x_{3}=x_{1}+x_{2}}$, то есть плоскость, которой принадлежат все векторы ${\displaystyle (x_{1},\,x_{2},\,x_{1}+x_{2})}$^[4].

Множество ${\displaystyle L}$ векторов указанного вида есть решётка^[4]. Действительно, пусть ${\displaystyle x=(x_{1},\,x_{2},\,x_{1}+x_{2})}$ и ${\displaystyle y=(y_{1},\,y_{2},\,y_{1}+y_{2})}$, тогда их точная верхняя грань в множестве ${\displaystyle L}$ есть вектор ${\displaystyle (z_{1},\,z_{2},\,z_{1}+z_{2})}$, где ${\displaystyle z_{1}=\max\{x_{1},\,y_{1}\}}$^{[комм 1]}, ${\displaystyle z_{2}=\max\{x_{2},\,y_{2}\}}$^{[комм 1]}. Точно так же вычисляется и точная нижняя грань^[3].

Но для тех же векторов их точная верхняя грань в ${\displaystyle \mathbb {R} ^{3}}$ равен ${\displaystyle z=x+y=(z_{1},\,z_{2},\,z_{3})}$, где ${\displaystyle z_{3}=\max\{x_{1}+x_{2},\,y_{1}+y_{2}\}}$^{[комм 1]}, причём ${\displaystyle z_{3}}$ может отличаться от ${\displaystyle z_{1}+z_{2}}$^[3].

Например, если ${\displaystyle x_{1}=1}$, ${\displaystyle x_{2}=2}$, ${\displaystyle y_{1}=2}$, ${\displaystyle y_{2}=1}$, то ${\displaystyle z_{1}+z_{2}=4}$, но ${\displaystyle z_{3}=3}$^[3].

Выпуклая подрешётка

Выпуклая подрешётка (выпуклое подмножество решётки) — подрешётка (соответственно подмножество) ${\displaystyle L_{1}}$, для которой (для которого) из ${\displaystyle a,\,b\in L_{1}}$, ${\displaystyle c\in L}$ и ${\displaystyle a\leqslant c\leqslant b}$ следует ${\displaystyle c\in L_{1}}$^[1][2].

Выпуклая подрешетка — характерный пример взаимопроникновения алгебраических и теоретико-порядковых понятий^[2].

Примеры выпуклых подрешёток^[1][5]: любое одноэлементное подмножество решётки; идеал➤; фильтр➤; интервал➤.

Идеал и фильтр

Основные статьи: Фильтр (математика) и Ультрафильтр

Простой идеал ${\displaystyle P}$ и непростой идеал ${\displaystyle I}$

Ультрафильтр ${\displaystyle P}$ и
не ультрафильтр ${\displaystyle D}$

Идеал — (непустая) подрешётка ${\displaystyle I}$ решетки ${\displaystyle L}$ при условии, что ${\displaystyle \inf\{a,\,i\}\in I}$ для произвольных элементов ${\displaystyle i\in I}$ и ${\displaystyle a\in L}$^[2].

Непустота идеалов обладает тем преимуществом, что даёт возможность доказывать обращение некоторых теорем, и тем недостатком, что невозможно непустое пересечение бесконечного множества непустых идеалов, если решетка не имеет наименьшего элемента ${\displaystyle 0}$. Но в случае, когда в решетке содержится ${\displaystyle 0}$, все идеалы содержат ${\displaystyle 0}$ и недостатка нет^[10].

Фильтр — (непустая) подрешётка ${\displaystyle D}$ решетки ${\displaystyle L}$ при условии, что ${\displaystyle \sup\{d,\,a\}\in D}$ для произвольных элементов ${\displaystyle d\in D}$ и ${\displaystyle a\in L}$^[2].

Синонимы фильтра: коидеал^[11]; дуальный идеал^[12][13][7]

Понятие фильтра и всех утверждений, к нему относящихся, получаются из понятий идеала и соответственных утверждений, к нему относящихся, по принципу двойственности^[11][12][13].

Следующее утверждение в некоторых источниках является определением идеала^[14][15][16].

Непустое подмножество ${\displaystyle I}$ решетки ${\displaystyle L}$ есть идеал тогда и только тогда, когда^[14][15][16]:

• ${\displaystyle \sup\{i,\,j\}\in I}$ для произвольных элементов ${\displaystyle i,\,j\in I}$;
• ${\displaystyle a\in I}$ для произвольных элементов ${\displaystyle i\in I}$, ${\displaystyle a\in L}$, ${\displaystyle a\leqslant i}$.

Действительно, если ${\displaystyle I}$ — идеал, то, поскольку ${\displaystyle I}$ подрешётка, из ${\displaystyle i,\,j\in I}$ следует ${\displaystyle \sup\{i,\,j\}\in I}$, а при ${\displaystyle a\leqslant i\in I}$ получаем ${\displaystyle a=\inf\{a,\,i\}\in I}$, то есть условия верны. Обратно, когда для ${\displaystyle I}$ выполняются оба условия, то при ${\displaystyle i,\,j\in I}$ верно ${\displaystyle \sup\{i,\,j\}\in I}$, и поскольку ${\displaystyle \inf\{i,\,j\}\leqslant i\in I}$, то ${\displaystyle \inf\{i,\,j\}\in I}$, то есть ${\displaystyle I}$ — подрешётка, а при ${\displaystyle i\in I}$, ${\displaystyle a\in L}$ верно ${\displaystyle \inf\{i,\,a\}\leqslant i\in I}$, откуда ${\displaystyle \inf\{i,\,a\}\in I}$, то есть ${\displaystyle I}$ — идеал^[14].

Следующее утверждение, называемое свойством кастовости идеала, также может служить определением идеала^[6][7].

Непустое подмножество ${\displaystyle I}$ решетки ${\displaystyle L}$ есть идеал тогда и только тогда, когда ${\displaystyle \sup\{i,\,j\}\in I}$ если и только если ${\displaystyle i,\,j\in I}$^[6][7].

Собственный идеал — идеал ${\displaystyle I}$ решетки ${\displaystyle L}$ такой, что ${\displaystyle I\neq L}$^[2].

Простой идеал — собственный идеал ${\displaystyle I}$ решетки ${\displaystyle L}$ такой, что из условий

${\displaystyle a,\,b\in L\,}$ и ${\displaystyle \,\inf\{a,\,b\}\in I}$

следует ${\displaystyle a\in I}$ или ${\displaystyle b\in I}$^[2].

Простой фильтр называют также ультрафильтром^[2].

Некоторые авторы называют фильтром только собственный дуальный идеал решетки всех подмножеств произвольного множества^[11][10].

Интервал

Интервал, открытый интервал, полуоткрытые интервалы

Интервал — подрешётка

${\displaystyle [a,\,b]=\{x\in L\mid a\leqslant x\leqslant b\}}$

решетки ${\displaystyle L}$, где произвольные ${\displaystyle a,\,b\in L}$, ${\displaystyle a\leqslant b}$^[2].

Для подрешётки ${\displaystyle C}$, которая представляет собой линейно упорядоченное множество, и её произвольных элементов ${\displaystyle a,\,b\in C}$ определяются следующие понятия ^[2].

Открытый интервал — подрешётка

${\displaystyle (a,\,b)=\{x\in C\mid a<x<b\}}$

подрешётки ${\displaystyle C}$^[2].

Полуоткрытый интервал — любая из подрешёток

${\displaystyle (a,\,b]=\{x\in C\mid a<x\leqslant b\},}$

${\displaystyle [a,\,b)=\{x\in C\mid a\leqslant x<b\}}$

подрешётки ${\displaystyle C}$^[2].

Открытый интервал и полуоткрытые интервалы — примеры выпуклых подрешёток, когда они непусты^[2].

Порождённая подрешётка

Теоретико-множественное пересечение любого набора подрешёток решётки ${\displaystyle L}$ тоже замкнуто относительно обеих операций ${\displaystyle +}$ и ${\displaystyle \cdot }$ исходной решётки. Поэтому произвольное подмножество ${\displaystyle H\subseteq L}$, ${\displaystyle H\neq \varnothing }$ содержится в некотором наименьшем подмножестве ${\displaystyle [H]\subseteq L}$, замкнутом относительно ${\displaystyle +}$ и ${\displaystyle \cdot }$^[2].

Подрешётка, порожденная множеством ${\displaystyle H\subseteq L}$, — наименьшая подрешётка ${\displaystyle [H]}$ решётки ${\displaystyle L}$, содержащая множество ${\displaystyle H}$^[2].

Порождающее множество подрешётки — множество ${\displaystyle H\subseteq L}$, которым порождена подрешётка ${\displaystyle [H]}$ решётки ${\displaystyle L}$^[2].

Когда ${\displaystyle H=\{a,\,b,\,c,\,\dots \}}$, вместо ${\displaystyle [H]}$ пишут ${\displaystyle H=[\{a,\,b,\,c,\,\dots \}]}$ или даже просто ${\displaystyle H=[a,\,b,\,c,\,\dots ]}$^[2].

Непустое теоретико-множественное пересечение произвольного количества выпуклых подрешёток (идеалов, фильтров^[11]) решётки ${\displaystyle L}$ опять есть выпуклая подрешётка (идеал, фильтр^[11]), поэтому аналогично определяется выпуклая подрешётка (идеал ${\displaystyle (H]}$, фильтр ${\displaystyle [H)}$^[11]), порождённая непустым подмножеством ${\displaystyle H\subseteq L}$^[2].

Главный идеал (главный фильтр^[11]) — идеал (фильтр^[11]), порождённый одним элементом ${\displaystyle a\in L}$ решётки ${\displaystyle L}$ и обозначаемый ${\displaystyle (\{a\}]}$, или ${\displaystyle (a]}$, или ${\displaystyle a^{\nabla }}$ (${\displaystyle [\{a\})}$, или ${\displaystyle [a)}$^[11], или ${\displaystyle a^{\Delta }}$^[16])^[14][16].

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