Отношение эквивалентности
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
е выполняется для всех пар.
Особую роль играет также матрица ||?i j||, где
Символ называют символом Кронекера. Этой матрице соответствует так называемое диагональное отношение Е или отношение равенства: (x, y), если x и y - один и тот же элемент множества.
Полезно также ввести антидиагональное отношение условием:
aij=1-
Для пустого, полного, диагонального и антидиагонального отношений имеет место любопытное свойство - их матрицы на зависят от выбора нумерации элементов множества М. Иначе говоря, если отношение ? таково, что при любом выборе нумерации в М матрицы || aij || совпадают, то ? либо полное, либо пустое, либо диагональное, либо антидиагональное.
Можно представить отношение и иначе:
Пусть снова ? М х М. Определим (ориентированный) граф G(?) следующим образом: Множество вершин этого графа будут составлять множество М при этом, из вершины ai проводится ребро в вершину bj в том и только в том случае, если, причем если (аi, ai), то у точки ai нарисуем петлю, выходящую и входящую в одну и ту же точку.
Пустому отношению соответствует граф без стрелок и петель, диагональное отношение описывается графом, в котором присутствуют только петли (рис1.1). Полное отношение задается полным графом (все вершины соединены со всеми, рис 1.2).
рис. 1.1 рис. 1.2
Граф есть геометрическое изображение отношения, как график - геометрическое изображение функции. Геометрический язык полезен, когда граф достаточно прост. Наоборот, изучать и описывать графы с большим числом вершин удобнее в терминах отношений.
II.Функции как отношения
Частным случаем отношений можно считать и функции. Пусть отношение на множестве М таково, что для всякого хМ существует ровно один элемент у М, для которого ( х, у ) . Тем самым каждому элементу хМ сопоставляется некоторый у М, определенный этим условием. Такое отношение и называется функцией или отображением. Множество пар, для которых ( х, у ) , называется графиком функции.
Пример: Если М - числовая прямая, а отношение - есть отношение равенства х = у, то график состоит из всех точек вида (х, х) и является биссектрисой координатного угла (графиком функции у = х). Если отношение выполнено для тех пар, для которых у =sin x, то график этой функции -обычная синусоида.
Итак, наше определение графика - обобщение обычного графика числовых функций.
III.Операции над отношениями.
Поскольку отношения между множествами A и В представляют собой ни что иное, как подмножества множества А х В, то для них определены все теоретико-множественные операции.
Определение 1.4. Пересечением отношений ? и ? назовем пересечение соответствующих подмножеств. Ясно что (x, y) тогда и только тогда, когда одновременно (x, y).
Определение 1.5. Объединением отношений ? и ? назовем объединение соответствующих подмножеств. Ясно что (x, y) тогда и только тогда, когда выполнено хотя бы одно из соотношений (x, y).
Важную роль играет операция, обозначаемая ?? - произведение отношений. Эта операция определяется так: соотношение (x, y) равносильно тому, что существует такое z, для которого выполнено (x, z)
IV.Свойства отношений.
Здесь мы укажем некоторые важные свойства отношений, которые позволят нам в дальнейшем определить отношение эквивалентности и понять его природу.
Определение 1.6. Отношение ? называют рефлексивным, если оно всегда выполнено между объектом и им самим: (х, х).
Содержательные примеры рефлексивных отношений -быть похожим на, быть не старше, с другой стороны, отношение быть братом - заведомо не рефлексивно.
Рефлексивные отношения всегда представимы в виде матриц, у которых на главной диагонали стоят единицы. В графе, изображающем рефлексивное отношение, каждая вершина имеет петлю.
Определение 1.7. Отношение ? называют антирефлексивным, если из (х, у), всегда следует х ? у.
Отношения быть братом, быть старше - антирефлексивны.
Матрица, представляющая антирефлексивное отношение, имеет на главной диагонали нули, а соответствующий граф непременно не имеет петель.
Определение 1.8. Отношение ? называют симметричным, если из (х, у), всегда следует (у, х).
Содержательные примеры симметричных отношений -быть похожим на, быть родственником.
В матрице, представляющей симметричное отношение, элементы, расположенные симметрично относительно главной диагонали, равны между собой aij = aji.
В соответствующем графе, вместе с каждой стрелкой существует стрелка противоположного направления. Симметричное отношение можно изображать виде неориентированного графа.
Определение 1.9. Отношение ? называют асимметричным, если из двух соотношений (х, у) или (у, х) по меньшей мере, одно не выполнено.
Для матричных элементов это приводит к равенству: aij •aji=0
В соответствующем графе, не может быть стрелок, соединяющих две вершины в противоположном направлении.
Теорема 1.1: Если отношение асимметрично, то оно антирефлексивно.
Определение 1.10. Отношение ? называют антисимметричным, если соотношения (х, у) и (у, х) выполняются одновременно, только когда х=у.
Для матричных элементов это приводит к равенству: aij •aji=0, когда i?j
Определение 1.11. Отношение ? называют транзитивным, если из того, что выполняются соотношения (х, z) и (z, y) следует, что (х, у). По индукции отсюда следует такое свойство: если (х, z1), (z1, z2) …(zn-1, y) то (х, y).
Это свойство хорошо интерпретируется на графе: если точки х и у соединены путем, проходимым по направлению стрелок, то существуе?/p>