В данном подразделе изучаются частично упорядоченные множества и решетки. Рассматриваются также отношения эквивалентности и их связь с разбиениями множества. Доказывается, что частично упорядоченное множество отношений эквивалентности на множестве является решеткой.

Определение 1

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

1) (a,a) Î R для всех a Î X;

2) aRb & bRa Þ a = b;

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

Пара (X,R), состоящая из множества X и отношения порядка R на X называется частично упорядоченным множеством.

Пусть (X,R) – частично упорядоченное множество. Всякое подмножество AÍX будет частично упорядоченным множеством с отношением порядка R Ç (A ´ A).

Отношение порядка обычно обозначается символом  «£».  

Элемент x частично упорядоченного множества (X,£) называется наибольшим (соответственно наименьшим), если для всякого y Î X верно y £ x (соответственно x £ y).

Определение 2

Пусть (X,£) – частично упорядоченное множество. Нижней гранью множества его элементов  называется наибольший элемент подмножества:

.

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

,

определяется верхняя грань   .

Заметим, что нижняя грань должна принадлежать множеству:

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

Следствие 1

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

Упражнение 1

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