Подрешётка

Подрешётка ― непустое подмножество некоторой решётки, замкнутое относительно обеих алгебраических операций ${\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 \langle L_{1},\,\leqslant \rangle }$ или упорядоченной тройкой ${\displaystyle \langle L_{1},\,+,\,\cdot \rangle }$, где ${\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 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].

1. ↑ ^{1 2 3} Исправленная опечатка в источнике.

1. ↑ ^{1 2 3 4 5 6 7 8} Фофанова Т. С. Подрешётка, 1984.
2. ↑ ^{1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20} Гретцер Г. Общая теория решёток, 1982, Глава I. Начальные понятия. § 3. Некоторые алгебраические понятия, с. 35.
3. ↑ ^{1 2 3 4 5 6} Вулих Б. З. Введение в теорию полуупорядоченных пространств, 1961, Глава II. Структуры. § 2. Подструктуры, с. 28.
4. ↑ ^{1 2 3 4 5 6} Вулих Б. З. Введение в теорию полуупорядоченных пространств, 1961, Глава II. Структуры. § 2. Подструктуры, с. 27.
5. ↑ ^{1 2} Скорняков Л. А. Элементы теории структур, 1970, § 4. Структуры, с. 50.
6. ↑ ^{1 2 3} Скорняков Л. А. Элементы теории структур, 1970, § 4. Структуры. Упражнения, с. 65.
7. ↑ ^{1 2 3 4} Биркгоф Г. Теория решёток, 1984, Глава II. Постулаты для решёток. 3. Гомоморфизмы и идеалы, с. 41.
8. ↑ Беран Л. Упорядоченные множества, 1981, Глава 4. Основные классы решёток, с. 38.
9. ↑ Салий В. Н. Решетки с единственными дополнениями, 1984, Глава первая. § 2. Решётки. 5, с. 23.
10. ↑ ^{1 2 3} Биркгоф Г. Теория решёток, 1984, Глава II. Постулаты для решёток. 3. Гомоморфизмы и идеалы, с. 42.
11. ↑ ^{1 2 3 4 5 6 7 8 9} Гретцер Г. Общая теория решёток, 1982, Глава I. Начальные понятия. § 3. Некоторые алгебраические понятия, с. 38.
12. ↑ ^{1 2} Фофанова Т. С. Фильтр, 1985.
13. ↑ ^{1 2} Фофанова Т. С. Идеал, 1979, с. 483.
14. ↑ ^{1 2 3 4} Гретцер Г. Общая теория решёток, 1982, Глава I. Начальные понятия. § 3. Некоторые алгебраические понятия, с. 36.
15. ↑ ^{1 2} Фофанова Т. С. Идеал, 1979, с. 482.
16. ↑ ^{1 2 3 4} Скорняков Л. А. Элементы теории структур, 1970, § 4. Структуры, с. 58.

• Беран Л. Упорядоченные множества = Beran L. Uspořádané množiny (1978) (рус.) / Пер. с чешск. В. Н. Салия под ред. Л. А. Скорнякова. — М.: «Наука», 1981. — 64 с.: ил. — (Популярные лекции по математике. Вып. 55). — 100 000 экз.
• Биркгоф Г. Теория решёток = Garrett Birkhoff, Lattice theory (1967) (рус.) / Перевёл с англ. В. Н. Салий под ред. Л. А. Скорнякова. — М.: «Наука», 1984. — 566 с.: ил. — 9400 экз.
• Вулих Б. З. Введение в теорию полуупорядоченных пространств (рус.). — М.: Физматгиз, 1961. — 407 с. — 9000 экз.
• Гретцер Г.. Общая теория решёток = George Grätzer. General Lattice Theory (1978) (рус.) / Пер. с англ. А. Д. Больбота, В. А. Горбунова и В. И. Туманова под ред. Д. М. Смирнова. — М.: «Мир», 1982. — 452 с.: ил. — 6000 экз.
• Салий В. Н. Решетки с единственными дополнениями (рус.). — М.: «Наука», 1984. — 128 с., ил. — 4400 экз.
• Скорняков Л. А. Элементы теории структур (рус.). — М.: «Наука», 1970. — 148,[1] с., ил. — 12 000 экз.
• Фофанова Т. С. Идеал // Математическая энциклопедия : [в 5 т.] / Гл. ред. И. М. Виноградов. — М.: Советская энциклопедия, 1979. — Т. 2: Д — Коо. — Стб. 481—483. — 1104 стб. : ил. — 148 800 экз.— Перевод на английский: Ideal . Encyclopedia of Mathematics. EMS Press.
• Фофанова Т. С. Подрешётка // Математическая энциклопедия : [в 5 т.] / Гл. ред. И. М. Виноградов. — М.: Советская энциклопедия, 1984. — Т. 4: Ок — Сло. — Стб. 380. — 1216 стб. : ил. — 148 900 экз.— Перевод на английский: Sublattice . Encyclopedia of Mathematics. EMS Press.
• Фофанова Т. С. Фильтр // Математическая энциклопедия : [в 5 т.] / Гл. ред. И. М. Виноградов. — М.: Советская энциклопедия, 1985. — Т. 5: Слу — Я. — Стб. 615. — 1248 стб. : ил. — 147 300 экз.— Перевод на английский: Filter . Encyclopedia of Mathematics. EMS Press.

• Биркгоф Г. Теория структур = Garrett Birkhoff, Lattice theory. Revised Edition (1948) (рус.) / Пер. с англ. М. И. Граева. — М.: «Издательство иностранной литературы», 1952. — 407 с.: ил.
• Garrett Birkhoff. Lattice theory (англ.). — Revised Edition. — New York: American Mathematical Society, 1948. — xiii+283 p.
• George Grätzer. General Lattice Theory (англ.). — New York · San Francisco: Academic Press, 1978. — xiii+381 p. — (Pure and applied mathematics). — ISBN 0-12-295750-4.