Материал: Дискретная математика. учебное пособие. Собенина О.В

2.2. Отношение эквивалентности и разбиения

Введем некоторые специальные типы отношений. Рефлексивное, симметричное, транзитивное отношение называется отношением эквивалентности или эквивалентностью (обозначение I).

Примеры.

1. Отношение равенства на множестве целых чисел R={(x,y)| x,yZ и x=y}является отношением эквивалентности, так как оно рефлексивно (x=x), симметрично (x=y y=x), транзитивно (x=y, y=z x=z)).

2. Отношение подо­бия на множестве треугольников являются отношением эквивалентности.

3. Отношение принадлежности к одной студенческой группе на множестве студентов ВГТУ – отношение эквивалентности.

4. Говорят, что целые числа х и у сравнимы по модулю m, если их разность делится на m. Этот факт обозначают в виде х y(mod m). На множестве целых чисел определим бинарное отношение R, полагая xRy, если х y(mod m). Это отношение называется отношением сравнимости по модулю m. Заметим, что R рефлексивно на множестве целых чисел, так как х-х = 0, и, следовательно, делится на m; R симметрично, так как если (х-у) делится на m, то (у-х) также разделится на т; это отношение транзитивно, так как если (х-у) делится на т, то для некоторого целого t имеем х-у=t m, а если (y-z) делится на m, то для некоторого целого t имеем y-z=t m. Отсюда x-z= =(t +t )m, то есть число (x-z) делится на m. Таким образом, отношение сравнимости по модулю m на множестве целых чисел является эквивалентностью.

Классом эквивалентности K(x) элемента х называется множество всех элементов у Х, каждый из которых находится с этим элементом в отношении эквивалентности. Иными словами, класс эквивалентности – это множество эквивалентных элементов.

Примеры:

1. Для отношения принадлежности к одной студенческой группе классом эквивалентности является множество студентов одной группы.

2. Отношение сравнимости на множестве целых чисел порождает следующие классы эквивалентности: вместе с любым числом х в этом же классе эквивалентности содержатся все числа вида (у + km), где k – целое число. Очевидно, что числа 0, 1,…, m-1 порождают различные классы эквивалентности, которые называются классами вычетов по модулю m. Все остальные классы эквивалентности для этого отношения совпадают с ними, так как любое число х из множества целых чисел, можно представить в виде

у = tm+ r, где 0 r m.

Заметим, что два различных класса эквивалентности не пересекаются, поэтому если все элементы множества Х распределены по классам эквивалентности, то эти классы эквивалентности образуют разбиение множества X. Справедливо утверждение: всякое отношение эквивалентности определяет разбиение множества Х на классы эквивалентности. Множество всех классов эквивалентности называется фактор-множеством по данному отношению эквивалентности и обозначается Х /I.

Пример. Для отношения принадлежности к одной студенческой группе фактор-множество множества студентов ВГТУ представляется собой множество студенческих групп.

Для определения, является ли заданное отношение R отношением эквивалентности используют следующий критерий:

Пусть R – матрица бинарного отношения. Если путем перестановки строк и столбцов ее можно привести к блочно-диагональному виду (на главной диагонали расположены подматрицы, состоящие из 1, а остальные элементы равны 0), то R является отношением эквивалентности, иначе – R не является отношением эквивалентности.

Пример. Рассмотрим отношение R, матрица которого имеет вид

Переставляя строки и столбцы, матрицу отношения R можно привести к блочно-диагональному виду, а значит R является эквивалентностью, и по полученной матрице можно определить классы эквивалентности К , К , К .

Таким образом, К = {а, d), К = {b}, К = {с, е, f}.

Отношение эквивалентности имеет большое практическое значение. Так сущность моделирования заключается в том, что устанавливают отношение эквивалентности между двумя системами, каждая из которых может быль абстрактной или реально существующей. Если одна из систем оказывается проще для исследования, то ее рассматривают в качестве модели для другой. Модель называется изоморфной, если между моделью и реальной системой наблюдается полное поэлементное соответствие (чертеж и изготовленная по нему деталь). Однако часто используются модели, которые позволяют судить только о существенных аспектах поведения реальных систем, не детализируя их (географическая карта по отношению к изображенному на ней участку земной поверхности). Модели, отдельные элементы которых соответствуют лишь крупным частям реальной системы, а полное поэлементное соответствие отсутствует, называются гомоморф­ными.

2.3. Отношения порядка. Диаграмма Хассе

Отношение эквивалентности является обобщением отношения равенства: эквивалентные элементы считаются «равными». Обобщением обычного отношения служат отношения порядка.

Отношение называется предпорядком или квазипорядком, если R рефлексивно и транзитивно.

Пример. Отношение

R={(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(1,3)}

на множестве X={1,2,3} является предпорядком.

Рефлексивное, антисимметричное, транзитивное отношение называется отношением нестрогого порядка и обозначается символом .

Антирефлексивное, антисимметричное, транзитивное отношение называется отношением строгого порядка и обозначается символом . Отношения строгого и нестрогого порядков иначе называют отношениями упорядоченности. Отношение, обратное отношению упорядоченности, также является отношением упорядоченности, т.е. ( ) = .

Примеры:

1. Пусть Y – некоторое множество, тогда отношение включения на множестве всех подмножеств P(Y) является отношением нестрогого порядка.

2. Отношение «х старше у» на некотором множестве людей является отношением строгого порядка.

Множество Х с заданным в нем отношением порядка называется упорядоченным этим отношением. Если любые два элемента х и у множества Х находятся между собой в отношении порядка, то множество Х называется линейно упорядоченным или цепью, иначе множество Х называется частично упорядоченным. В частично упорядоченном множестве можно выделить цепь. Цепь с повторяющимися элементами называется мультицепью. Если между элементами х и у установлено отношение порядка, то они называются сравнимыми, иначе – несравнимыми. Антицепью (семейством Шпернера) называется подмножество частично упорядоченного множества, в котором любые два элемента несравнимы. Специальным типом частично упорядоченного множества является интервал |x,y]={z X|x z у} (замкнутый) или (x,y)P={z X|x z у} (открытый).

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

Рассмотрим множество Х с заданным на нем отношением частичного порядка .

Говорят, что элемент y покрывает элемент x, если х у и не существует никакого элемента z X, такого что х z у. Таким образом, у покрывает х тогда и только тогда, когда х у и [х,у]={х,у}. Любое частично упорядоченное множество можно представить в виде схемы. Диаграммой Хассе частично упорядоченного множества Х называ­ется граф, вершинами которого являются элементы множества X, а пара (х,у) образует ребро, если элемент у покрывает элемент х, и такой что, если х у, то у рисуют с большей вертикальной координатой чем х.

Пример. Отношение включения на булеане Р(Х), где Х={а, b, с}. Оно является частично упорядоченным множеством. Множество Р(Х) содержит восемь элементов: { , {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}. Диаграмма Хассе для этого отношения будет иметь вид (рис. 2.2).

Рис. 2.2

Правило чтения диаграмм Хассе состоит в том, что х у, если можно пройти из точки х в точку у, следуя вдоль восходящих отрезков соединяющих точки. Смена направления движения разрешается только в точках диаграммы.

Пример. Пусть А={1, 2, 3, 5, 6, 10, 15, 30}. Рассмотрим отношение частичного порядка ≤ на этом множестве, задаваемое по правилу: x≤y y делится на x. Диаграмма Хассе изображена на рис.2.3.

Заметим, что диаграммы Хассе этих двух отношений совпадают

Пусть Х и Y два частично упорядоченных множества. Если их диаграммы Хассе совпадают, то эти частично упорядоченные множества имеют одинаковую структуру.

П ример. На рис. 2.4 изображена диаграмма Хассе линейно упорядоченного множества Х={1, 2, 3, 4, 5, 6, 7, 8} с обычным отношением порядка (≤) на множестве натуральных чисел, не превосходящих восьми.

Рис. 2.3 Рис. 2.4

Пусть задано частично упорядоченное множество X. Для элементов х и у из множества Х их верхней гранью называется любой элемент z Х такой, что и , а их нижней гранью – любой элемент t X, такой, что х и t у. На языке диаграмм Хассе х у означает, что существует путь из x в y; верхняя грань x и y – это вершина, в которую есть путь из x и y; нижняя грань x и y – это вершина из которой есть путь и в x и в y. В общем случае для некоторых элементов верхняя и нижняя грань может не существовать или быть неединственной, причем различные верхние (или нижние) грани могут быть несравнимы.

Пример. На рис. 2.5 а) изображена диаграмма Хассе множества , у которого элементы не имеют верхней грани, а элементы – нижней грани. На рис. 2.5 б) изображена диаграмма Хассе множества у которого все элементы имеют верхние и нижние грани, однако, например, и имеют две несравнимые верхние грани.