Решётка (алгебра)
Решётка (ранее использовался термин структура) — частично упорядоченное множество, в котором каждое двухэлементное подмножество имеет как точную верхнюю (sup), так и точную нижнюю (inf) грани. Отсюда вытекает существование этих граней для любых непустых конечных подмножеств.
Примеры
- множество всех подмножеств данного множества, упорядоченное по включению; например: [math]\displaystyle{ \sup\{ \{x\}, \{x,y\} \} = \{x,y\}, \inf\{ \{x\}, \{x,y\} \} = \{x\} }[/math], [math]\displaystyle{ \sup\{ \{x\}, \{y,z\} \} = \{x,y,z\}, \inf\{ \{x\}, \{y,z\} \} = \emptyset }[/math];
- всякое линейно упорядоченное множество; причём если [math]\displaystyle{ a\leqslant b }[/math], то [math]\displaystyle{ \sup(a,b) = b, \inf(a,b) = a }[/math];
- множество всех подпространств векторного пространства, упорядоченных по включению, где [math]\displaystyle{ \inf }[/math] — пересечение, а [math]\displaystyle{ \sup }[/math] — сумма соответствующих подпространств;
- множество всех неотрицательных целых чисел, упорядоченных по делимости: [math]\displaystyle{ a\leqslant b }[/math], если [math]\displaystyle{ b = ac }[/math] для некоторого [math]\displaystyle{ c }[/math]. Здесь [math]\displaystyle{ \sup }[/math] — наименьшее общее кратное, а [math]\displaystyle{ \inf }[/math] — наибольший общий делитель данных чисел;
- вещественные функции, определённые на отрезке [0, 1], упорядоченные условием [math]\displaystyle{ f\leqslant g }[/math], если [math]\displaystyle{ f(t)\leqslant g(t) }[/math] для всех [math]\displaystyle{ t\in [0,1] }[/math]. Здесь
- [math]\displaystyle{ \sup(f,g) = u }[/math], где [math]\displaystyle{ u(t) =\max (f(t),g(t)) }[/math].
Алгебраическое определение
Решётка может быть также определена как универсальная алгебра с двумя бинарными операциями (они обозначаются [math]\displaystyle{ \vee }[/math] и [math]\displaystyle{ \wedge }[/math] или + и ∙), удовлетворяющая следующим тождествам
- [math]\displaystyle{ a\vee a = a }[/math]
[math]\displaystyle{ a\wedge a = a }[/math] (идемпотентность) - [math]\displaystyle{ a\vee b = b\vee a }[/math]
[math]\displaystyle{ a\wedge b = b\wedge a }[/math] (коммутативность) - [math]\displaystyle{ (a\vee b)\vee c = a\vee (b\vee c) }[/math]
[math]\displaystyle{ (a\wedge b)\wedge c = a\wedge (b\wedge c) }[/math] (ассоциативность) - [math]\displaystyle{ a\wedge(a\vee b) = a }[/math]
[math]\displaystyle{ a\vee(a\wedge b) = a }[/math] (поглощение).
Связь между этими двумя определениями устанавливается при помощи формул:
- [math]\displaystyle{ a\vee b = \sup(a,b) }[/math],
- [math]\displaystyle{ a\wedge b = \inf(a,b) }[/math],
и обратно. При этом для любых элементов [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math] эквивалентны следующие утверждения:
- [math]\displaystyle{ a\leqslant b }[/math];
- [math]\displaystyle{ a\wedge b = a }[/math];
- [math]\displaystyle{ a\vee b = b }[/math].
Понятия изоморфизма решёток как универсальных алгебр и как частично упорядоченных множеств совпадают. Однако произвольное изотонное отображение решётки [math]\displaystyle{ R }[/math] в решётку [math]\displaystyle{ R' }[/math] не обязано быть гомоморфизмом этих решёток как универсальных алгебр.
Подрешётки
Подрешётка ― подмножество элементов решётки, замкнутое относительно операций [math]\displaystyle{ + }[/math] и [math]\displaystyle{ \cdot }[/math]. Примерами подрешёток являются всякое одноэлементное подмножество решётки, идеал, фильтр, интервал.
Подрешётка [math]\displaystyle{ A }[/math] называется выпуклой, если из [math]\displaystyle{ a,b\in A }[/math] и [math]\displaystyle{ a\lt c\lt b }[/math] вытекает, что [math]\displaystyle{ c\in A }[/math]. Все подрешётки выше — выпуклые.
Любое подмножество элементов цепи является её подрешёткой (не обязательно выпуклой). Все подрешётки данной решётки, упорядоченные отношением включения, образуют решётку.
История
Появление понятия «решётка» относится к середине 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.