решетка - это частично упорядоченное множество для любых двух элементов которого существует наименьшая верхняя граница (least upper bounds) и наибольшая нижняя граница (greatest lower bounds). на решетке определены две операции - join (∪) and meet (∩) - которые удовлетворяют требованиям идемпотентности, коммутативности, ассоциативнсти, дистрибутивности и закону поглощения:
L1: ассоциативность (X ∪ Y) ∪ Z = X ∪ (Y ∪ Z) , (X ∩ Y) ∩ Z = X ∩ (Y ∩ Z) L2: коммутативность X ∪ Y = Y ∪ X , X ∩ Y = Y ∩ X L3: идемпотентность X ∪ X = X , X ∩ X = X L4: поглощение X ∩ (X ∪ Y) = X , X ∪ (X ∩ Y) = X
Def: непустое множество L, на котором заданы две операции ∩ и ∪, удовлетворяющие перечисленным выше тождествам L1–L4, называется решеткой
Def: непустое подмножество M решетки L называется подрешеткой, если M замкнуто относительно операций ∩ и ∪, т.е. из того, что X,Y∈M вытекает, что X∩Y∈M и X∪Y∈M
отображение f : L → M одной решетки в другую называется гомоморфизмом, если оно сохраняет операции ∩ и ∪, т.е.
f (X ∩ Y) = f (X) ∩ f (Y) и
f (X ∪ Y) = f (X) ∪ f (Y) ∀ X,Y ∈ L
Def: отображение f : L → M одной решетки в другую называется дуальным гомоморфизмом, если оно переставляет операции ∩ и ∪, т.е.
f (X ∩ Y) = f (X) ∪ f (Y) и
f (X ∪ Y) = f (X) ∩ f (Y) ∀ X,Y ∈ L
оказывается, решетки можно определить совершенно иначе. а именно, если L - произвольная решетка, мы можем определить на L частичный порядок полагая X≤Y в том и только том случае, когда X∩Y=X или, что то же самое, когда X∪Y=Y
если у нас имеется такое частично упорядоченное множество L, что для любых двух его элементов X,Y существуют inf(X,Y) и sup(X,Y), то мы можем превратить его в решетку в нашем смысле, полагая
X ∩ Y = inf(X,Y) и
X ∪ Y = sup(X,Y)
именно так решетки и были первоначально определены Пирсом в 1880 году
L5': существование нуля X ∩ ∅ = ∅ , X ∪ ∅ = X L5": существование единицы X ∩ U = X , X ∪ U = U
вообще говоря, они не обязаны существовать. так, например, если множество U бесконечно, то в Λ(U) есть 0, но нет 1
решетка L называется решеткой с 0 и 1, если в ней существуют элементы, удовлетворяющие аксиомам L5' и L5", соответственно
L6: дистрибутивность A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
дистрибутивность пересечения относительно объединения была впервые сформулирована Булем, а объединения относительно пересечения - Пирсом. вообще говоря, L6 не вытекает из остальных аксиом, решетка, для которой она выполняется, называется дистрибутивной. многие решетки не являются дистрибутивными, скажем, решетка подпространств векторного пространства, решетка подгрупп группы, и т.д.
оказывается, с учетом предыдущих аксиом достаточно проверять только один из фигурирующих в L6 законов дистрибутивности
Th Биркгофа: всякая дистрибутивная решетка изоморфна подрешетке в 2K для подходящего множества K
в действительности, большинство реально возникающих в алгебре решеток не являются дистрибутивными, но удовлетворяют несколько более слабому условию "модулярности", впервые отмеченному Дедекиндом
тождество модулярности: если L есть дистрибутивная решетка, то для ее элементов выполнено следующее
(X ∩ Z) ∪ (Y ∩ Z) = ((X ∩ Z) ∪ Y) ∩ Z
однако чаще условие модулярности формулируют не в виде тождества, а в виде условного тождества
X ≤ Z ⇒ X ∪ (Y ∩ Z) = (X ∪ Y) ∩ Z
в самом деле, предположим, что выполняется тождество модулярности. тогда, если X ≤ Z, то
X ∪ (Y ∩ Z) = (X ∩ Z) ∪ (Y ∩ Z) = ((X ∩ Z) ∪ Y) ∩ Z = (X ∪ Y) ∩ Z
обратно, если верно условное тождество модулярности, то,
так как X ∩ Z ≤ Z, его можно применить к (X ∩ Z) ∪ (Y ∩ Z)
решетка называется модулярной или дедекиндовой, если в ней выполняется тождество модулярности
каждая дистрибутивная решетка - модулярна. однако обратное, вообще говоря, неверно: решетки подпространств векторного пространства, идеалов кольца, нормальных подгрупп группы и т.д. модулярны, но не дистрибутивны! а решетка всех подгрупп группы, вообще говоря, не является даже модулярной
в действительности обе операции ∩ и ∪ легко восстанавливаются по одной тернарной операции на подмножествах. определим медиану трех множеств равенством
M (X, Y, Z) = (X ∩ Y) ∪ (X ∩ Z) ∪ (Z ∩ X)
мы могли бы в этом определении поменять местами ∩ и ∪
медиана X, Y, Z состоит из тех элементов, которые принадлежат по крайней мере двум из множеств X, Y, Z. в частности, медиана симметрична относительно любых перестановок X, Y, Z :
M (X, Y, Z) = M (X, Z, Y) = M (Y, X, Z) = M (Y, Z, X) = M (X, Y, Z) = M (Z, Y, X)
смысл введения медианы состоит в том, что она описывает теоретико-множественное отношение "лежать между" в том же самом духе, в каком ∩ и ∪ описывают отношения ⊆ и ⊇
посмотрим, прежде всего, как выглядит формула включения-исключения для небольшого количества множеств.
для двух множеств эта формула записывается в виде
|A ∪ B| = |A| + |B| − |A ∩ B|
для трех множеств она приобретает вид
|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|
и в том и в другом случае ее легко переписать в виде комбинаторных формул
|A ∪ B| = |A| + |B \ A| и
|A ∪ B ∪ C| = |A \ B| + |B \ C| + |C \ A| + |A ∩ B ∩ C|пусть X = ∪ Xi, i ∈ I, - покрытие множества X. мы хотим вычислить |X|
в качестве первого приближения воспользуемся правилом суммы. однако при этом элементы, принадлежащие более чем одному множеству Xi будут посчитаны несколько раз и для получения правильного ответа мы должны их исключить. при этом мы исключим те элементы, которые содержатся более, чем в двух множествах Xi слишком много раз, и нам придется их снова включить и т.д.
|∪ Xi| = ∑ |Xi| − ∑ |Xi ∩ Xj| + ∑ |Xi ∩ Xj ∩ Xh| − ..
i < j < h < ..
формула решета:
|X \∪ Xi| = |X| − ∑ |Xi| + ∑ |Xi ∩ Xj| − ∑ |Xi ∩ Xj ∩ Xh| + ..
i < j < h
фиксируем два неколлинеарных вектора u и v на плоскости. множество L точек плоскости, получающихся из начала координат 0 произвольными итерациями сдвигов на u и v и обратных к ним, называется двумерной решеткой, порожденной векторами u и v. при этом о паре векторов (u,v) говорят как о базисе решетки
таким образом, L = {m*u + n*v | u,v ∈ ℤ}
ясно, что сопоставление точке x = m*u + n*v ∈ L пары ее координат (m,n) в базисе (u,v) задает изоморфизм L с прямым произведением ℤ×ℤ
заметим, что структура прямого произведения на L (т.е. задание проекций pr1, pr2 : L → ℤ) зависит не только от самой решетки L, но и от выбора векторов u,v и, в свою очередь, определяет эти векторы
пусть L - двумерная решетка, порожденная векторами u и v. назовем стандартной элементарной ячейкой этой решетки - множество
C = { (a * u) + (b * v) | 0 ≤ a , b < 1 }
назовем элементарной ячейкой - любой сдвиг C при помощи целых кратных векторов u и v:
C (m * n) = C + (m * u) + (n * v) = { x + (m * u) + (n * v) | x ∈ C }
= { (a * u) + (b * v) | m ≤ a < m+1 , n ≤ b < n+1 }
это граф Кэли свободной группы. вершинами являются элементы группы, а ребрами соединяются те из них, которые получаются умножением на образующие
это решетка, элементами которой являются точки некоторого пространства, на котором действует группа. вершинами являются элементы пространства, а ребрами связываются те из них, которые могут быть получены один из другого действием генератора группы
полурешётка (semilattice) - полугруппа, бинарная операция в которой коммутативна и идемпотентна
полурёшетка определяется как частично упорядоченное множество, для каждой пары элементов которого определена точная верхняя грань (верхняя полурешётка) или точная нижняя грань (нижняя полурешётка) [ а множество, являющееся одновременно верхней и нижней полурешёткой является решёткой]
полурешётка аксиоматизируется как алгебра, снабжённая бинарной операцией "∙"
x ∙ x = x идемпотентность x ∙ (y ∙ z) = (x ∙ y) ∙ z ассоциативность x ∙ y = y ∙ x коммутативность
в полурешётке можно определить частичный порядок таким образом:
x ≤ y тогда и только тогда, когда x ∙ y = x
поскольку бинарная операция в полурешётке идемпотентна, коммутативна и ассоциативна, то определённый таким образом порядок является рефлексивным, антисимметричным и транзитивным