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

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

План

1. Покрытие и разбиение множества.

2. Отношение эквивалентности.

3. Отношения порядка.

4. Операции над бинарными отношениями.

1.Покрытие и разбиение множества

Пусть – некоторое семейство (совокупность) множеств.

Семейство называется покрытием множества А, если каждый элемент А принадлежит хотя бы одному из множеств , т.е.

.

Если покрытие таково, что его элементы попарно не пересекаются (), и все , то такое покрытие называется разбиением множества А.

Пример. . Тогда - покрытие, но не разбиение, - разбиение и покрытие, - не является ни покрытием, ни разбиением.

Разбиение множества А всегда является его покрытием; покрытие не всегда является разбиением.

Пример. На рис.1 построена диаграмма Венна для совокупности множеств . Семейство множеств образуют покрытие множества , поскольку , но не является разбиением множества, поскольку можно указать такое множество из , которое не является подмножеством , например: .

Рис.1.

2.Отношение эквивалентности

Определение. Пусть задано бинарное отношение . Если это отношение является одновременно рефлексивным, симметричным и транзитивным, то оно называется отношением эквивалентности.

Пример. Пусть - это множество таких вещественных чисел, что . Отношение имеет место между двумя элементами тогда и только тогда, когда их разность является рациональным числом, т.е. когда . Такое отношение является рефлексивным, поскольку для (); является симметричным, поскольку, если , то , т.е. если , то и ; транзитивным, поскольку, если и , то , т.е. из того, что и ,следует, что . Таким образом, рассмотренное отношение является отношением эквивалентности.

Пример. Отношение равносильности, заданное на множестве формул, является отношением эквивалентности.

Пример. Отношение «проживания в одном доме» на множестве жителей города Одесса является отношением эквивалентности.

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

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

3.Отношения порядка

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

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

Отношения нестрогого и строгого порядка вместе называются отношениями порядка.

Примеры бинарных отношений нестрого порядка: «быть не старше» на множестве людей, «быть не больше» на множестве действительных чисел.

Примеры бинарных отношений строго порядка: «быть старше» на множестве людей, «быть больше» на множестве действительных чисел.

Пусть - отношение порядка. Элементы называются сравнимыми по отношению порядка на множестве , если выполняется или .

Множество , на котором задано отношение порядка , может быть:

• Полностью упорядоченным множеством, если любые сравнимы по отношению порядка . В таком случае говорят, что отношение задает полный порядок на множестве . Например, отношение «быть моложе» задает полный порядок на множестве всех людей;

• Частично упорядоченным множеством, если существуют , которые не сравнимы по отношению порядка . В таком случае говорят, что отношение задает частичный порядок на множестве . Например, отношение «быть начальником» задает строгий частичный порядок на множестве сотрудников некоторой организации.

4.Операции над бинарными отношениями

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

1. Объединением бинарных отношений и называется такое бинарное отношение , для которого имеет место соотношение:

2. Пересечением бинарных отношений и называется такое бинарное отношение , для которого имеет место соотношение:

3. Разностью бинарных отношений и называется такое бинарное отношение , для которого имеет место соотношение:

4. Дополнением бинарного отношения называется такое бинарное отношение , для которого имеет место соотношение:

, где (если ) или (если )

5. Обратным отношением к бинарному отношению называется такое бинарное отношение , для которого имеет место соотношение:

.

Пример. Пусть - бинарное отношение «быть руководителем», определенное на множестве сотрудников некоторой организации. Тогда бинарные отношения имеют следующий смысл:

- «не быть руководителем»

- «быть подчиненным».

Перечисленные отношения имеют свойства, отраженные в таблице 1.

Таблица 1.

Вопросы

1. Что такое покрытие множества? Привести примеры.

2. Для любого ли множества можно построить покрытие? Ответ обосновать.

3. Чем покрытие множества отличается от разбиения этого множества? Привести примеры.

4. Всегда ли покрытие множества является его разбиением?

5. Может ли покрытие множества быть его разбиением?

6. Всегда ли разбиение множества является его покрытием?

7. Какое бинарное отношение называется отношением эквивалентности? Привести примеры отношений эквивалентности.

8. Какое бинарное отношение называется отношение нестрогого/строгого порядка? Привести примеры.

9. Какое множество называется полностью упорядоченным? Привести примеры.

10. Какое множество называется частично упорядоченным? Привести примеры.

11. Какие операции над бинарными отношениями можно определить?