Дискретная математика. Элементы теории, задачи и упражнения. Часть 1. Булгакова И.Н. - 21 стр.

� определяет разбиение множества � на классы эквивалентности отно-
сительно этого отношения.
         Совокупность классов эквивалентности элементов множества � по
отношению эквивалентности � называется фактор-множеством множества
� по отношению � и обозначается � / � .
         Рефлексивное, антисимметричное и транзитивное отношение назы-
вается отношением частичного порядка на множестве � и вместо записи
� x, y � � � для данного отношения часто используют запись x � y . Отноше-
ние частичного порядка на множестве � , для которого любые два элемен-
та сравнимы, т.е. для любых x, y � � выполнено либо x � y , либо y � x ,
называется отношением линейного порядка. Множество � с заданным на
нем частичным (линейным) порядком называется частично (линейно) упо-
рядоченным.
         Пусть � – непустое конечное множество, на котором задано отноше-
ние частичного порядка. Запишем x � y , если x � y и x � y . Говорят, что
элемент y покрывает элемент x , если x � y , и не существует такого элемен-
та u , что x � u � y . Для x � y можно записать x � x1 � x 2 � ... � x n � y , где
xi �1 покрывает xi .
         Частично упорядоченные множества можно изображать с помощью
так называемых диаграмм Хассе. На диаграмме Хассе элементы частично
упорядоченного множества изображаются точками на плоскости, и если
элемент y покрывает элемент x , то точки x и y соединяются отрезком,
причем точку, соответствующую x , располагают ниже y .

        Пример 1. Доказать, что бинарное отношение на множестве целых
чисел
                            � � �� x, y � � � � � : x � y�
является отношением эквивалентности, и построить соответствующее ему
фактор-множество � / � .
     Решение. Проверку рефлексивности, симметричности и транзитив-
ности данного бинарного отношения выполните самостоятельно. Постро-
им классы эквивалентности для данного отношения эквивалентности.
Класс эквивалентности, порожденный любым элементом x � � , имеет вид
                   �x� � �y � � : x � y� � �y � � : x � y� � �x� .
     Таким образом, для данного отношения эквивалентности класс экви-
валентности, порожденный элементом x � � , состоит только из этого эле-
мента x, и фактор-множество � / � имеет вид
                               � / � � ��x� : x � � �.



                                       21