Решетка, или структура
AUB =BUA АПВ =ВГ\А
AU(ВUC) = (AUB)UC
АГ\(В Г)С) = (АПВ) ПС
АЩАПВ) =А AC\(AUB)=A
Упорядоченное множество - это такое множество, в котором элементы подчинены правилу предшествования, или следования (обозначается < - знак отношения порядка на множество).
Или, по определению В. Серпинского, множество называется упорядоченным, если для любых двух различных элементов определено правило, по которому один из этих элементов предшествует другому. Каждое упорядоченное множество удовлетворяет сле-дующие аксиомы:из любых двух различных элементов а' и а" , принадлежащих множеству А, один предшествует другому, а' < а";
отношение а' <а" и а" < а' исключают друг друга;
если а' < а" и а' < а"', то а' < а";
если а' < а" и а" <а', то а' = а";
а' <а" или а" <а' для всех а\ а" є А.
Не всякое множество может быть упорядочено. Считается, что нельзя упорядочить множество всех множеств точек данной прямой.
Множество является упорядоченным, если для его элементов определен предикат от двух переменных, которые не рефлексивны, но транзитивны и которые для произвольных отличных друг от друга А и В выполняются либо для пары (АВ), либо для пары (ВА).
П.Н. Новиков называет упорядоченное множество вполне упорядоченным, если каждая его непустая часть содержит элемент, предшествующий всем другим элементам этой части. Операции по упорядочению множеств определяются такими теоремами, как: 1) любое вполне упорядоченное множество имеет первый элемент. Каждый элемент, кроме последнего (если такой существует), имеет последователя (следующего за); 2) никакое вполне упорядоченное множество не подобно своему отрезку; 3) никакие два различные отрезка вполне упорядоченного множества не подобны; 4) если множества А и В вполне упорядочены, то либо они подобны, либо множество А подобно отрезку множества В, либо множество В подобно отрезку множества А.
В этом контексте операции объединения и пересечения множества характеризуются следующими свойствами:
a Uа= а.
а <а Uв
в <а Uв
а < с и е< с влекут aU е< с
а< в тогда и только тогда когда a Ue =в
а <с и e аП е <а аГів < в с <а и с <в влекут с<аП в в< а тогда и только тогда когда а П в = а<с и e Решетка имеет верхнюю границу элементов а, в є М, если а< ао при всех а є М, которая (граница) обозначается посредством aUe, или supМ(от лат. Решетка имеет точную нижнюю границу элементов а, в є М, если а>а при всех а є М, которая (граница) обозначается посредством аП в, или infM (от лат. - infimus - низ). Отношение порядка < на множестве М называется отношением решеточного порядка, если для любых а, в є М элементы sup (а, в) и inf (а, в) существуют. Решетка М называется дистрибутивной, если при любых а, в, сє Мвыполняются А П (В UC) = (АПВ) U (АПС) А и(ВП С) = (AUB) П (AUC). Дистрибутивная решетка называется булевой алгеброй, в которой имеются два элемента (нуль и единица), причем такие элементы, что aU0=a, аГ)1=а, и для любого элемента а имеется такой элемент -| а, что aU~\а= 1, а П-| а=0. Решетка М называется импликативной, если А^В существует для всех элементов а, в є М. Каждая импликативная решетка с нулевым элементом называется псевдобулевой алгеброй. Каждая импликативная решетка может рассматриваться как алгебра с тремя бинарными операциями М, П, II —а каждая псевдобулева алгебра М - как алгебра с тремя бинарными операциями П, U, —» и с одной унарной операцией М, П, II, —~ Решетка М называется булевой алгеброй, если она дистрибутивна и каждый элемент а М имеет дополнение не-а, так что (а П-|о) U (в=в), (a U -| а) П (в=в).