Решётка (теория множеств)

Материал из Википедии — свободной энциклопедии

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

Содержание 1 Примеры 2 Алгебраическое определение 3 Связанные определения 4 История 5 Литература

[править] Примеры

1. множество всех подмножеств данного множества, упорядоченное по включению;
2. всякое линейно упорядоченное множество; причем если a ≤ b, то sup{a,b} = b, inf{a,b} = a;
3. множество всех надпространств векторного пространства, упорядоченных по включению, где inf - пересечение, а sup - сумма соответствующих надпространств;
4. множество всех неотрицательных целых чисел, упорядоченных по делимости: a ≤ b, если b = ac для некоторого c. Здесь sup - наименьшее общее кратное, а inf - наибольший общий делитель данных чисел;
5. действительные функции, определенные на отрезке [0, 1] , упорядоченные условием f ≤ g, если f(t) ≤ g(t) для всех t О [0, 1]. Здесь

sup{f,g} = u, где u(t) = max{f(t), g(t)}.

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

Решётка может быть также определена как универсальная алгебра с двумя бинарными операциями (они обозначаются + и ∙ или ∨ и ∧), удовлетворяющая следующим тождествам

1. a + a = a
   a ∙ a = a (идемпотентность)
2. a + b = b + a
   a ∙ b = b ∙ a (коммутативность)
3. (a + b) + c = a + (b + c)
   (a ∙ b) ∙ c = a ∙ (b ∙ c) (ассоциативность)
4. a (a + b) = a
   a + a ∙ b = a (поглощение).

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

a + b = sup{a, b}, a ∙ b = inf {a, b},

и обратно. При этом для любых элементов a и b эквивалентны следующие утверждения: (а) a ≤ b; (б) ab = a; (в) a + b = b.

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

[править] Связанные определения

• Подрешётка ― подмножество элементов решетки, замкнутое относительно операций + и

[править] История

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

[править] Литература

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