Отношения порядка и эквивалентности

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

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

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

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