Решетки (структуры)

На непустом множестве X  задан частичный порядок ≤, если выделено множество пар элементов x≤y, причем если x≤y≤z, то x≤z. Кроме того, x≤x, и  если x≤y≤x, то x=y.  Частично упорядоченное множество называется решеткой, если для любых элементов x,y существуют элементы m=x˄y, M=x˅y, что m≤x,y≤M,  и если для каких-то элементов m’, M’ выполнены неравенства m’≤x,y≤M’,   то m’ ≤m ,M≤M’.  

Примером решетки являются целые числа с естественным порядком, либо с порядком n≤m, если n делит m. Все подмодули некоторого модуля образуют решетку, где порядок определяется включением подмодулей. Все подмножества некоторого множества также образуют решетку по включению.

 Решетку можно рассматривать как универсальную алгебру с двумя коммутативными, ассоциативными операциями x˄y, x˅y, причем

x˄x = x˅x = x˅(x˄y) = x˄(x˅y).

Важную роль играют дистриубтивные решетки, которые задаются тождеством x˄(y˅z) = (x˅y) ˄(x˅z). Примерами таких решеток являются решетки подмножеств некоторого множества. Справедлива теорема Стоуна: любая дистрибутивная решетка вкладывается в качестве подрешетки в решетку подмножеств некоторого множества.

Дистрибутивная решетка с наибольшим элементом 1 и наименьшим 0 называется булевой алгеброй, если для любого элемента x существует дополнение x’, причем x˄x’=0, x˅x’=1.

Примером булевой алгебры является решетка всех подмножеств некоторого множества. Каждая конечная булева алгебра совпадает с решеткой всех подмножеств некоторого конечного множества.