Нижняя грань обозначается через . Двойственно, как наименьший элемент множества , определяетсяверхняя грань .

Заметим, что нижняя грань должна принадлежать множеству , и, значит, удовлетворять неравенствамдля всех 1≤i≤n. И среди элементов, удовлетворяющих этим неравенствам, она должна быть наибольшим элементом.

При n=2 нижняя грань множества обозначается , а верхняя .

Пример 1. Пусть (N₊, |) – множество положительных натуральных чисел {1, 2, 3, …}, с отношением делимости:

m|n  nделится на m (k N₊)mk=n .

Тогда нижняя грань mnравна наибольшему общему делителю, аmn– наименьшему общему кратному.

Определение 3. Частично упорядоченное множество (X,) называется нижней (соответственно верхней) полурешеткой, если для любых множествоимеет нижнюю (соответственно верхнюю) грань вX. Если (X,) является нижней и верхней полурешеткой, то оно называется решеткой.

Пример 2. ПустьX– множество. Частично упорядоченное множество (P(X),) подмножеств множестваXс отношением включения будет решеткой.

Пример 3. Частично упорядоченное множество положительных натуральных чисел (N₊, |) будет решеткой.

Лемма 1. Если конечное частично упорядоченное множество (X,) является нижней полурешеткой и имеет наибольший элемент, то оно будет решеткой.

Доказательство.Пусть. В этом случае множество

S=

непусто и конечно. Поскольку X– нижняя полурешетка, то существует . Положим . Для всехi=1, …, nимеет местоz a_i . Иz– наименьший среди обладающих этим свойством. Стало быть,z= .

Определение 4. ПустьX– множество. Бинарное отношениеR  XXназываетсяотношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. Таким образом,R– отношение эквивалентности наX, если

1. (a,a)R для всех a  X,

2. aRb  bRa

3. для всех a, b, c  Xверна импликацияaRb & bRc aRc,

Определение 5. Разбиением множества X называется множество {X_i : iI} попарно непересекающихся подмножеств X_i  X таких, что . С каждым разбиением{X_i : iI} можно связать отношение эквивалентности ~ на X, полагая x ~ y, если x и y являются элементами некоторого X_i .

Каждому отношению эквивалентности ~ на X соответствует разбиение {X_i : iI}, элементами которого являются подмножества, состоящие из эквивалентных элементов. Эти подмножества называются классами эквивалентности. Множество классов эквивалентности {X_i : iI} называется фактор-множеством множества X по отношению эквивалентности ~ и обозначается: X/~.

Теорема 1. Пусть X – конечное множество. Множество отношений эквивалентности на X с отношением включения  является решеткой.

Доказательство.Множество отношений эквивалентности является нижней полурешеткой, ибо точной нижней гранью отношений эквивалентностей будет их пересечение. Оно будет иметь наибольший элементXX. Стало быть, оно будет решеткой, по лемме 1.

Поскольку разбиения множества Xвзаимно однозначно соответствуют отношениям эквивалентности наX, то множество разбиений легко превратить в частично упорядоченное множество. Отношение порядкамежду разбиениями определяется как имеющее место тогда и только тогда, когда разбиениеP₁мельче чемP₂, т.е. когда верна импликация

.

В этом случае будет верно включение , и, стало быть, отношение эквивалентности, соответствующее разбиениюP₁, будет содержаться в отношении эквивалентности, соответствующем разбиениюP₂ . Мы установили биекцию между разбиениями и отношениями эквивалентности на множестве. Эта биекция сохраняет порядок. Получаем

Следствие 1. Множество разбиений множества является решеткой.

Упражнение 1. Пусть (X,R) – конечное частично упорядоченное множество. Будет ли решеткой множество отношений порядкаR, упорядоченное отношением?