Полная решётка

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

Условно полной решёткой называется частично упорядоченное множество, каждое непустое ограниченное подмножество которого имеет точную верхнюю и точную нижнюю грани. Отличие от общего понятия решётки здесь состоит в том, что в определении обычной (необязательно полной) решётки требуется существование точных верхней и нижней граней не для произвольных, а лишь для двухэлементных множеств. Каждая непустая конечная решётка полна; вещественная прямая $\mathbb {R}$ (с обычным отношением порядка) служит примером бесконечной неполной, но условно полной решётки.

Полная решётка всегда имеет наибольший элемент (единицу) и наименьший элемент (нуль).

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

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

Определения

Основное определение

Полной решёткой называется частично упорядоченное множество $(L,\leqslant )$, такое, что каждое его подмножество $A\subset L$ имеет точную верхнюю грань $\operatorname {sup} A$ (иногда также называемую объединением множества $A$) и точную нижнюю грань $\operatorname {inf} A$ (также называемую пересечением множества $A$).

Для подмножества $A$ решётки $L$ вместо $\operatorname {sup} A$ обычно используется обозначение $\bigvee A$, а вместо $\operatorname {inf} A$ — обозначение $\bigwedge A$. Для индексированных множеств $\{a_{\iota }\}_{\iota \in \mathrm {I} }$ элементов решётки используются обозначения $\bigvee _{\iota \in \mathrm {I} }a_{\iota }$ или $\bigvee \{a_{\iota }:\iota \in \mathrm {I} \}$; аналогично в случае точной нижней грани $\bigwedge$.

Если $A=\varnothing$ (то есть $A$ пусто), то $1=\bigwedge A$ есть наибольший, а $0=\bigvee A$ — наименьший элемент решётки $L$. Таким образом, каждая полная решётка непуста и обладает наибольшим элементом (единицей) и наименьшим элементом (нулём).

Альтернативные определения

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

i) $L$ — полная решётка;

ii) $L$ — полная нижняя полурешётка, то есть каждое подмножество $A\subset L$ имеет точную нижнюю грань;

iii) в $L$ существует наибольший элемент $1$, и каждое непустое подмножество $A\subset L$ имеет точную нижнюю грань;

iv) $L$ непусто, и каждое непустое подмножество $A\subset L$ имеет точную нижнюю грань

ii') $L$ — полная верхняя полурешётка, то есть каждое подмножество $A\subset L$ имеет точную верхнюю грань;

iii') в $L$ существует наименьший элемент $0$, и каждое непустое подмножество $A\subset L$ имеет точную верхнюю грань;

iv') $L$ непусто, и каждое непустое подмножество $A\subset L$ имеет точную верхнюю грань.

Схема доказательства. Условия ii')–iv') двойственны условиям ii)–iv), поэтому достаточно доказать эквивалентность условий i)–iv). Она будет доказана по схеме i)$\implies$ii)$\implies$iii)$\implies$iv)$\implies$ii)$\implies$i). Импликации i)$\implies$ii) и iii)$\implies$iv) тривиальны; импликация ii)$\implies$iii) вытекает из того, что $\bigwedge \varnothing =1$, а iv)$\implies$ii) — из того, что если $L$ непусто, то оно обладает наименьшим элементом $0=\bigwedge L$ и наибольшим элементом $1=\bigvee L$, которые являются соответственно точными верхней и нижней гранями пустого множества. Для доказательства ii)$\implies$i) достаточно заметить, что при выполнении условия ii) у каждого множества $A\subset L$ существует и точная верхняя грань, определяемая формулой

$\bigvee A=\bigwedge A^{\triangle }$,

где $A^{\triangle }=\{x\in L:a\leqslant x$ для всех $a\in A\}$ — верхний конус множества $A$ (то есть множество его верхних граней).

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

Непустое подмножество $S$ полной решётки $L$ называется полной подрешёткой (иногда замкнутой подрешёткой) решётки $L$, если оно вместе с каждым своим непустым подмножеством содержит его точные верхнюю и нижнюю грани (взятые в $L$), то есть если $\sup \nolimits _{L}A\in S$ и $\inf \nolimits _{L}A\in S$ для любого непустого $A\subset S$. Данное определение оправдывается тем, что полная подрешётка $S$ действительно является подрешёткой решётки $L$ и сама является полной решёткой, причём точные верхние и нижние грани (непустых множеств), взятые в ней самой, совпадают с точными и нижними гранями, взятыми в $L$, то есть

$\sup \nolimits _{S}A=\sup \nolimits _{L}A$ и $\inf \nolimits _{S}A=\inf \nolimits _{L}A$ для всех непустых $A\subset S$.

Важно отметить, что подрешётка полной решётки $L$, сама являющаяся полной решёткой, может и не быть полной подрешёткой решетки $L$ в смысле указанного определения (см. примеры ниже).

Пересечение любого непустого семейства полных подрешёток полной решётки $L$ является полной подрешеткой (если оно не пусто). Поэтому среди полных подрешёток, содержащих данное (непустое) множество $A\subset L$ существует наименьшая, о которой говорят, что она вполне порождается множеством $A$.

Условно полные решётки

Условно полной решёткой называется частично упорядоченное множество, такое, что каждое его непустое ограниченное (сверху и снизу) подмножество имеет точную верхнюю грань и точную нижнюю грань. Как и в случае полных решёток, данное определение формально избыточно: для частично упорядоченного множества $(L,\leqslant )$ следующие условия эквивалентны:

i) $L$ — условно полная решётка;

ii) каждое непустое ограниченное подмножество $A\subset L$ имеет точную нижнюю грань;

iii) каждое непустое ограниченное снизу подмножество $A\subset L$ имеет точную нижнюю грань;

ii') каждое непустое ограниченное подмножество $A\subset L$ имеет точную верхнюю грань;

iii') каждое непустое ограниченное сверху подмножество $A\subset L$ имеет точную верхнюю грань.

Каждая полная решётка условно полна; условно полные решётки отличаются от полных по существу лишь тем, что в них могут отсутствовать наибольший и наименьший элементы. Если $L$ — условно полная решётка, а $O$ и $I$ — некоторые элементы, не принадлежащие $L$, то присоединением этих элементов к $L$ в качестве наименьшего и наибольшего получится полная решётка. Более точно, отношение (строгого) частичного порядка на $L$ можно расширить на множество ${\overline {L}}=L\cup \{O,I\}$ правилами:

• $O<x$ и $x<I$ для всех $x\in L$;
• $O<I$.

Так определённое частично упорядоченное множество ${\overline {L}}$ оказывается полной решёткой, причём $O$ и $I$ — её наименьший и наибольший элементы соответственно. Эта конструкция обобщает конструкцию расширенной вещественной прямой ${\overline {\mathbb {R} }}$, получаемой присоединением к $\mathbb {R}$ «бесконечных элементов» $-\infty$ и $+\infty$.

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

Примеры

1. Произвольная непустая конечная решётка полна.
2. Вещественная прямая $\mathbb {R}$ (с обычным линейным порядком) является неполной, но условно полной решёткой. Непустое подмножество $A\subset \mathbb {R}$ является полной подрешёткой решётки $\mathbb {R}$ тогда и только тогда, когда оно замкнуто и ограничено (или, что равносильно, когда оно компактно). В частности, любой отрезок $[a,b]$ (где $a<b$) — полная подрешётка решётки $\mathbb {R}$, вполне порождаемая множеством рациональных чисел, лежащих в интервале $(a,b)$. Расширенная вещественная прямая ${\overline {\mathbb {R} }}$, получаемая присоединением к $\mathbb {R}$ «бесконечных элементов» $-\infty$ и $+\infty$, является полной решёткой.
3. Множество неотрицательных целых чисел, упорядоченное отношением делимости (то есть $a\leqslant b$, если $a|b$) — полная решётка. Наименьшим элементом этой решётки (нулём решетки) является число $1$, а наибольшим (единицей решётки, что может показаться парадоксальным) — число $0$, поскольку его делит любое целое число (в том числе сам $0$). Точной нижней гранью (непустого) множества чисел является их наибольший общий делитель (он очевидным образом определяется и для бесконечного множества). Точной верхней гранью (непустого) конечного множества чисел служит их наименьшее общее кратное, а бесконечного — наибольший элемент решётки, то есть $0$. Если из конструкции изъять $0$ (то есть рассмотреть множество натуральных чисел с отношением делимости), то получится условно полная решётка, имеющая наименьший, но не имеющая наибольшего элемента.
4. Множество всех подмножеств ${\mathcal {P}}(X)$ данного множества, упорядоченное по включению — полная решётка. Точной нижней и точной верхней гранью семейства множеств ${\mathcal {A}}\subset {\mathcal {P}}(X)$ являются соответственно теоретико-множественное пересечение $\bigcap {\mathcal {A}}$ и объединение $\bigcup {\mathcal {A}}$; наименьшим элементом этой решётки является пустое множество, наибольшим — всё $X$.
5. Семейство ${\mathcal {O}}(X)$ всех открытых подмножеств топологического пространства $X$, упорядоченное по включению, является полной решёткой. Пустое множество — её наименьший элемент, а всё пространство $X$ — наибольший элемент. Точная верхняя грань семейства ${\mathcal {U}}\subset \Omega (X)$ совпадает с объединением $\bigcup {\mathcal {U}}$, а точная нижняя грань определяется формулой $\operatorname {Int} \left(\bigcap {\mathcal {U}}\right)$, где $\operatorname {Int}$ — оператор внутренности множества. Это множество в общем случае не совпадает с теоретико-множественным пересечением $\bigcap {\mathcal {U}}$ (поскольку пересечение бесконечного семейства открытых множеств может не быть открытым) и, таким образом, ${\mathcal {O}}(X)$ является полной решёткой, но, вообще говоря, не является полной подрешёткой решётки ${\mathcal {P}}(X)$ из предыдущего примера.
6. Аналогично, семейство ${\mathcal {C}}(X)$ всех замкнутых подмножеств топологического пространства $X$ — полная решётка: её наименьшим и наибольшим элементами являются соответственно $\varnothing$ и $X$; точная верхняя грань семейства ${\mathcal {A}}\subset {\mathcal {C}}(X)$ определяется формулой ${\overline {\bigcup {\mathcal {A}}}}$ (где черта сверху обозначает замыкание), а точная нижняя грань совпадает с теоретико-множественным пересечением $\bigcap {\mathcal {A}}$. Полная решётка ${\mathcal {C}}(X)$ в общем случае не является полной подрешёткой решётки ${\mathcal {P}}(X)$.
7. Семейство подгрупп данной группы $G$, упорядоченное по включению — полная решётка. Наименьшим элементом этой решётки служит одноэлементная (единичная) подгруппа $\{e\}$ (где $e$ — нейтральный элемент группы $G$), наибольшим — сама группа $G$; точной нижней гранью семейства подгрупп является их пересечение, а точной верхней гранью — подгруппа, порождённая теоретико-множественным объединением этого семейства.
8. Предыдущий пример обобщается на произвольные универсальные алгебры. Пусть задана универсальная алгебра $A$ из некоторого эквационального класса (многообразия алгебр) ${\mathfrak {A}}$. Семейство её подалгебр (из класса ${\mathfrak {A}}$), упорядоченное по включению, образует полную решётку.
9. Множество идеалов кольца, упорядоченное по включению, является полной решёткой. Точная верхняя грань семейства идеалов — это их сумма, а точная нижняя грань — пересечение.

Решётка замкнутых элементов

Примеры 6–9, приведённые выше, представляют собой частные случаи решётки замкнутых элементов некоторой полной решётки. Более подробно, пусть на полной решётке $(L,\leqslant )$ задан оператор замыкания $C$ (то есть отображение $C\colon L\to L$, обладающее свойствами экстенсивности, монотонности и идемпотентности). Тогда подмножество $F\subset L$ замкнутых относительно $C$ элементов (то есть элементов $x\in L$, для которых $C(x)=x$) является полной решёткой (относительно ограничения порядка $\leqslant$ на $F$), причём точные нижние грани в этой решётке совпадают с точными нижними гранями в $L$:

$\inf \nolimits _{F}A=\inf \nolimits _{L}A$ для любого $A\subset F$.

Точные верхние грани в решётке $F$, вообще говоря, не совпадают с точными верхними гранями в $L$ (то есть $F$ в общем случае не является полной подрешёткой решётки $L$); точная верхняя грань множества $A\subset F$ определяется формулой

$\sup \nolimits _{F}A=C(\sup \nolimits _{L}A)$.

В примерах 6–9 на полной решетке $L={\mathcal {P}}(X)$ всех подмножеств множества $X$ операторами замыкания являются соответственно оператор топологического замыкания и оператор взятия подгруппы (подалгебры, идеала), порождённой данным множеством.

См.также

• Решётка

Литература

• Курош А. Г. Общая алгебра. Лекции 1969-1970 учебного года.. — М.: Наука, 1974. — С. 106—113. — 159 с.
• Скорняков Л. А. Элементы общей алгебры. — М.: Наука, 1983. — С. 23—30. — 272 с.
• Биркгоф Г. Теория решёток. — М.: Наука, 1984. — С. 149—174. — 566 с.
• Артамонов В. А., Салий В. Н., Скорняков Л. А., Шеврин Л. Н., Шульгейфер Е. Г. Общая алгебра / Под общ. ред. Л. А. Скорнякова. — М.: Наука, 1991. — Т. 2. — 479 с. — (Справочная математическая библиотека). — ISBN 5-02-014427-4.

Одним из источников, использованных при создании данной статьи, является статья из википроекта «Рувики» («ruwiki.ru») под названием «Полная решётка», расположенная по адресу: — «https://ru.ruwiki.ru/wiki/Полная_решётка» Материал указанной статьи полностью или частично использован в Циклопедии по лицензии CC-BY-SA 4.0 и более поздних версий. Всем участникам Рувики предлагается прочитать материал «Почему Циклопедия?».