index
  • решетки
  • полурешетки

  • решетки

    решетка - это частично упорядоченное множество для любых двух элементов которого существует наименьшая верхняя граница (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, называется решеткой

    непустое подмножество 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

    отображение 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 ∈ Z}

    ясно, что сопоставление точке x = m*u + n*v ∈ L пары ее координат (m,n) в базисе (u,v) задает изоморфизм L с прямым произведением Z × Z

    заметим, что структура прямого произведения на L (т.е. задание проекций pr1, pr2 : L → Z) зависит не только от самой решетки 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

    поскольку бинарная операция в полурешётке идемпотентна, коммутативна и ассоциативна, то определённый таким образом порядок является рефлексивным, антисимметричным и транзитивным


    index