Отношение эквивалентности
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
? стрелка, непосредственно ведущая из вершины х с вершину у.
отношение эквивалентность математика
Глава 2. Разбиение на классы. Отношение эквивалентности. Свойства эквивалентности. Фактор-множество
.Разбиение на классы. Отношение эквивалентности
Определение 2.1. Назовем взаимозаменяемыми те и только те объекты некоторого данного множества М, которые обладают одним и тем же набором формальных признаков, существенных в данной ситуации.
Обозначим через Мх -множество всех объектов, взаимозаменяемых с объектом х. Очевидно, что х Мх и объединение всех Мх (при всевозможных х из М) совпадает совсем множеством М:
(2.1)
Предположим, что. Это значит, что существует некоторый элемент z, такой, что он одновременно принадлежит и и . Значит x взаимозаменяем с z и z взаимозаменяем с у. Следовательно, х взаимозаменяем с у, а значит и с любым элементом из. Таким образом . Аналогично показывается и обратное включение. Таким образом, встречающиеся в объединении (2.1) множества либо не пресекаются, либо целиком совпадают.
Определение 2.2. Систему непустых подмножеств {M1, M2,….} множества М мы будем называть разбиением этого множества, если
i..
Сам множества при этом называются классами разбиения.
Определение 2.3. Отношение ? на множестве М называется эквивалентностью (или отношением эквивалентности), если существует такое разбиение {M1, M2,….} множества М такое, что (х, у) выполняется тогда и только тогда, когда х и у принадлежат к некоторому общему классу Mi данного разбиения.
Пусть {M1, M2,….} разбиение множества М. Определим, исходя из этого разбиения, отношение ? на М: (х, у),если х и у принадлежат к некоторому общему классу Mi данного разбиения. Очевидно, что отношение ? является эквивалентностью. Назовем ? отношением эквивалентности, соответствующим данному разбиению.
Определение 2.4. Если в каждом подмножестве Mi выбрать содержащийся в нем элемент хi, то этот элемент будем называть эталоном для всякого элемента у, входящего в тоже множество Mi. По определению, положим выполненным отношение ?* быть эталоном (хi, у)
Легко видеть, что эквивалентность ?, соответствующая данному разбиению, может быть определена и так: (z, у) если z и у имеют общий эталон (хi, z) и (хi, у).
Пример 2.1: Рассмотрим в качестве М множество целых неотрицательных чисел и возьмем его разбиение на множество М0 четных чисел и множество М1 - нечетных. Соответствующее отношение эквивалентности на множестве целых чисел обозначается так:
и читается: n сравнимо с m по модулю 2. В качестве эталонов естественно выбрать 0 - для четных чисел и 1 - для нечетных. Аналогично, разбивая то же множество М на k подмножеств M0, M1,… Mk-1, где Mj состоит из всех чисел, дающих при делении на k в остатке j, мы придем к отношению эквивалентности:
которое выполняется, если n и m имеют одинаковые остатки при делении на k.
В качестве эталона в каждом Mj естественно выбрать соответствующий остаток j.
II.Фактор-множество
Пусть - отношение эквивалентности. Тогда по теореме, существует разбиение {M1, M2,….} множества М на классы эквивалентных друг другу элементов - так называемые классы эквивалентности.
Определение 2.5. Множество классов эквивалентности по отношению обозначают М/ и читают фактор-множество множества М по отношению.
Пусть ?: M > S - сюрьективное отображение множества М на некоторое множество S.
Для всякого ?: M > S - сюрьективного отображения существует такое отношение эквивалентности на множестве М, что М/ и S могут быть поставлены во взаимно однозначное соответствие.
III.Свойства эквивалентности
Определение 2.6. Отношение ? на множестве М называется эквивалентностью (отношением эквивалентности), если оно рефлексивно, симметрично и транзитивно.
Теорема 2.1: Если отношение ? на множестве М рефлексивно, симметрично и транзитивно, существует такое разбиение {M1, M2,….} множества М такое, что (х, у) выполняется тогда и только тогда, когда х и у принадлежат к некоторому общему классу Mi данного разбиения.
Обратно: Если задано разбиение {M1, M2,….} и бинарное отношение ? задано как принадлежать к общему классу разбиения, то ? рефлексивно, симметрично и транзитивно.
Доказательство:
Рассмотрим рефлексивное, симметричное и транзитивное отношение ? на М. Пусть для любого состоит из всех таких z, для которых (x, z) ?
Лемма 2.1: Для любых x и y либо либо
Из леммы и рефлексивности отношения ? следует, что множества вида образуют разбиение множества М. (Это разбиение естественно назвать разбиением, соответствующим исходному отношению). Пусть теперь (x, y) ?. Это значит, что y. Но и х в силу (x, х) ?. Следовательно, оба элемента входят в . Итак, если (x, y) ?, то х и у входят в общий класс разбиения. Наоборот, пусть uи v. Покажем, что (u, v) ?, Действительно, имеем (x, u) ? и (x, v) ?. Отсюда по симметричности (u, x) ?. По транзитивности из (u, x) ? и (x, v) ? следует (u, v) ?. Первая часть теоремы доказана.
Пусть дано разбиение {M1, M2,….} множества М. Т.к. объединение всех классов разбиения совпадает с М, то любой хвходит в некоторый класс . Отсюда следует, что (x, х) ?, т.е. ? - рефлексивно. Если x и y входят в некоторый класс , то y и x входят в тот же класс. Это означает, что из (x, y) ? вытекает (y, x) ?, т.е. отношение симметрично. Пусть теперь выполнено (x, y) ? и (y, z ) ?. Это означает, что x и y входят в некоторый класс , а y и z входят в некоторый класс . Классы имеют общий элемент у, а, следовательно, совпадают. Значит x и z входят в класс , т.е. выполняется (x, z) ? и отношение транзит