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

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

ПримерыПравить

1. множество всех подмножеств данного множества, упорядоченное по включению; например: $sup\{\{x\},\{x,y\}\}=\{x,y\},inf\{\{x\},\{x,y\}\}=\{x\}$$\sup\{\{x\},\{x,y\}\}=\{x,y\},\inf\{\{x\},\{x,y\}\}=\{x\}$ , $sup\{\{x\},\{y,z\}\}=\{x,y,z\},inf\{\{x\},\{y,z\}\}=\mathrm{\varnothing <!--\; \varnothing \; -->}$$\sup\{\{x\},\{y,z\}\}=\{x,y,z\},\inf\{\{x\},\{y,z\}\}=\emptyset$ ;
2. всякое линейно упорядоченное множество; причём если $a⩽<!--\; ⩽\; -->b$$a\leqslant b$ , то $sup(a,b)=b,inf(a,b)=a$$\sup(a,b)=b,\inf(a,b)=a$ ;
3. множество всех подпространств векторного пространства, упорядоченных по включению, где $inf$$\inf$  — пересечение, а $sup$$\sup$  — сумма соответствующих подпространств;
4. множество всех неотрицательных целых чисел, упорядоченных по делимости: $a⩽<!--\; ⩽\; -->b$$a\leqslant b$ , если $b=ac$$b=ac$  для некоторого $c$$c$ . Здесь $sup$$\sup$  — наименьшее общее кратное, а $inf$$\inf$  — наибольший общий делитель данных чисел;
5. вещественные функции, определённые на отрезке [0, 1], упорядоченные условием $f⩽<!--\; ⩽\; -->g$$f\leqslant g$ , если $f(t)⩽<!--\; ⩽\; -->g(t)$$f(t)\leqslant g(t)$  для всех $t\in <!--\; \in \; -->[0,1]$$t\in [0,1]$ . Здесь

$sup(f,g)=u$$\sup(f,g)=u$ , где $u(t)=max(f(t),g(t))$$u(t)=\max(f(t),g(t))$ .

Алгебраическое определениеПравить

Решётка может быть также определена как универсальная алгебра с двумя бинарными операциями (они обозначаются $\vee <!--\; \vee \; -->$$\vee$  и $\wedge <!--\; \wedge \; -->$$\wedge$  или + и ∙), удовлетворяющая следующим тождествам

1. $a\vee <!--\; \vee \; -->a=a$$a\vee a=a$ 
   $a\wedge <!--\; \wedge \; -->a=a$$a\wedge a=a$  (идемпотентность)
2. $a\vee <!--\; \vee \; -->b=b\vee <!--\; \vee \; -->a$$a\vee b=b\vee a$ 
   $a\wedge <!--\; \wedge \; -->b=b\wedge <!--\; \wedge \; -->a$$a\wedge b=b\wedge a$  (коммутативность)
3. $(a\vee <!--\; \vee \; -->b)\vee <!--\; \vee \; -->c=a\vee <!--\; \vee \; -->(b\vee <!--\; \vee \; -->c)$$(a\vee b)\vee c=a\vee (b\vee c)$ 
   $(a\wedge <!--\; \wedge \; -->b)\wedge <!--\; \wedge \; -->c=a\wedge <!--\; \wedge \; -->(b\wedge <!--\; \wedge \; -->c)$$(a\wedge b)\wedge c=a\wedge (b\wedge c)$  (ассоциативность)
4. $a\wedge <!--\; \wedge \; -->(a\vee <!--\; \vee \; -->b)=a$$a\wedge (a\vee b)=a$ 
   $a\vee <!--\; \vee \; -->(a\wedge <!--\; \wedge \; -->b)=a$$a\vee (a\wedge b)=a$  (поглощение).

Связь между этими двумя определениями устанавливается при помощи формул:

$a\vee <!--\; \vee \; -->b=sup(a,b)$$a\vee b=\sup(a,b)$ ,

$a\wedge <!--\; \wedge \; -->b=inf(a,b)$$a\wedge b=\inf(a,b)$ ,

и обратно. При этом для любых элементов $a$$a$  и $b$$b$  эквивалентны следующие утверждения:

$a⩽<!--\; ⩽\; -->b$$a\leqslant b$ ;

$a\wedge <!--\; \wedge \; -->b=a$$a\wedge b=a$ ;

$a\vee <!--\; \vee \; -->b=b$$a\vee b=b$ .

Понятия изоморфизма решёток как универсальных алгебр и как частично упорядоченных множеств совпадают. Однако произвольное изотонное отображение решётки $R$$R$  в решётку $R^{\prime }$$R'$  не обязано быть гомоморфизмом этих решёток как универсальных алгебр.

ПодрешёткиПравить

Запрос «Подрешётка» перенаправляется сюда; об одноимённом понятии из теории групп см. Решётка (геометрия)#Подрешётка.

Подрешётка ― подмножество элементов решётки, замкнутое относительно операций $+$$+$  и $\cdot <!--\; \cdot \; -->$$\cdot$ . Примерами подрешёток являются всякое одноэлементное подмножество решётки, идеал, фильтр, интервал.

Подрешётка $A$$A$  называется выпуклой, если из $a,b\in <!--\; \in \; -->A$$a,b\in A$  и $a<c<b$  вытекает, что $c\in <!--\; \in \; -->A$$c\in A$ . Все подрешётки выше — выпуклые.

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

ИсторияПравить

Появление понятия «решётка» относится к середине XIX века. Чётко его сформулировал Р. Дедекинд в работах 1894 и 1897 годов. Термин «lattice», переведённый как «структура», был введён Биркгофом в 1933 году. В настоящее время в русской терминологии (из-за многозначности слова «структура») он вытеснен переводом «решётка». Исторически роль теории решёток объясняется тем, что многие факты, касающиеся множества идеалов кольца и множества нормальных подгрупп группы, выглядят аналогично и могут быть доказаны в рамках теории дедекиндовых решёток. Как самостоятельное направление алгебры эта теория сформировалась в 30-х годах XX века. Наиболее важные классы решёток, кроме дедекиндовых, — это полные решётки, дистрибутивные решётки и булевы алгебры.

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

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

См. такжеПравить

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

СсылкиПравить

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

• 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.

ЛитератураПравить

• Биркгоф Г. Теория структур / Пер. с англ. — М., 1952;
• Скорняков Л. А. Элементы теории структур. — М., 1970;
• Житомирский Г. И. Упорядоченные множества и решётки. — Саратов, 1981;
• Гретцер Г. Общая теория решёток / Пер. с англ. — М., 1982.