Свойства бинарных отношений

 

Бинарное отношение R (RÌA´A=A²), заданное на множестве А называется отношением тождества, если все его элементы (кортежи) имеет вид (а,а), где аÎА и обозначается id_A, т.е. . Пары, вида (а,а) называются диагональными, а отношение id_A называют диагональным. Вполне понятно, что матрица отношения тождества будет иметь вид единичной матрицы:

Очевидно, что для любого бинарного отношения R, определенного на множестве А, имеет место равенство: *R=R*id_A=R.

Бинарное отношение R, заданное на множестве А, называется рефлексивным, если id_AÍR, т.е. когда оно включает диагональ.

Примеры:

а. А – множество прямых на плоскости, на котором задано отношение R= «Прямая Х параллельная прямой Y».

Действительно, как известно из элементарной геометрии, две прямые параллельны, если они либо совпадают, либо не имеют ни одной общей точки (нигде не пересекаются). Поскольку прямая Х совпадает сама с собой, то пара (Х,Х) принадлежит данному отношению R, т.е. (Х,Х)Î R.

b. А – множество студентов нашего вуза и на котором задано отношение Р= «студент S ровесник студенту V». Очевидно, что каждый ровесник сам себе, и поэтому (S,S)ÎP.

Бинарное отношение R, заданное на множестве А называется иррефлексивным, если aRa (или (а,а)Î R) не имеет смысла. Или тоже самое можно сформулировать как (а,а)Ï R.

Пример:

а. На числовом множестве D задано отношение R=”<”. Вполне очевидно, что для любых двух чисел х отношение x<x всегда ложно, т.е. все диагональные элементы (х,х) этого отношения на матрице отношений будут равны нулю.

Следует отметить, что иррефлексивные отношения еще называют антиреффлексивным.

Ø Бинарное отношение R, заданное на множестве А называется симметричным, если для пары (а, b) Î А² из аRb следует bRа (RÍR^-1).

Примеры:

а. Прямая А перпендикулярна прямой В в плоскости Z.

b. Студент Х является соседом по парте студента Y.

(Заметим, что приведенные отношения не являются рефлексивными).

Ø Бинарное отношение R, заданное на множестве А называется, антисимметричным, если из и следует, что ( ).

Пример:

а. Отношение включения для множества, т.е. отношение «множество А является подмножеством множества В». И если А Í В и В ÍА, то из аксиомы объемности следует, что А = В.

Ø Бинарное отношение R, заданное на множестве А называется транзитивным, если для любых a, b, c Î A из aRb и bRc следует aRc (R Í R²).

Примеры:

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

в. Отношение «быть ровесником», заданное на множестве студентов;

с. Отношение «быть больше (меньше)», заданное на множестве действительных чисел.

Ø Бинарное отношение R, заданное на множестве А называется отношением эквивалентности (или просто эквивалентностью), если для любых элементов a, b, c Î A выполняются следующие свойства:

- рефлексивность: aRa (id_A Í R);

- симметричность: aRb Þ bRa (R Í R^-1);

- транзитивность: aRb и bRc Þ aRc (R² Í R).

Примеры:

а. Отношение равенства “=” на любом множестве является отношением эквивалентности (рефлексивность: а=а; симметричность: a=bÞb=a; транзитивность: (a=b и b=c) Þ a=c).

b.Отношение R={(1, 1), (1, 2), (1, 3), (2, 2), (2, 2), (2, 1), (2, 3), (3, 3), (3, 2), (3, 1)} является отношением эквивалентности, так как оно рефлексивно: "(а){(a, a) Î R}; симметрично: (a, b) R (b, a) ÎR; транзитивно: ((a, b) и (b, c) ÎR Þ (a, c) Î R, где a, b –числа, принимающие значения 1, 2, 3. Например, транзитивность (1, 2) Î R и (2, 3) Î R влечет (1, 3) Î R. Отметим, что в этом примере R=R^-1.

с. Отношение “быть на одном курсе” на множестве студентов факультета;

d. Отношение “иметь одинаковый остаток при делении на 3” на множестве

натуральных чисел;

e. Отношение параллельности на множестве прямых плоскости.

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

 

Считается, что термин “отношение эквивалентности” применяется только в случае, если выполняются следующие три условия:

Ø Каждый элемент эквивалентен самому себе;

Ø Высказывание, что два элемента являются эквивалентными, не требует уточнения, какой из элементов рассматривается первым, а какой вторым;

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

Для обозначения эквивалентности иногда применяют символ ”~”1.

Тогда общее определение отношения эквивалентности получим, записав три вышеприведенные условия в виде следующих соотношений:

а~а (рефлексивность);

а~bÞb~a (симметричность);

а~b и b~c Þa~c (транзитивность).

Отношение эквивалентности, заданное на множестве А, тесно связано с разбиением множества на классы. Эта определяется следующим утверждением:

Лемма: «Всякое отношение эквивалентности, определенное на множестве А, задает разбиение множества на классы».

Доказательство:

Пусть на множестве А задано отношение эквивалентности «~». Выполним следующее построение. Выберем элемент а₁ÎА и образуем класс (подмножество А) А₁, состоящий из элемента а₁ и всех элементов, эквивалентных а₁; затем выберем элемент а₂ÏА₁ и образуем класс А₂, состоящий из а₂ и всех элементов, эквивалентных а₂ и т.д. получится система классов А₁, А₂….(возможно бесконечная) такая, что любой элемент из А входит в один класс. Вполне очевидно, что полученная система классов обладает свойствами:

Ø А_i=А;

Ø

Ø .

Построенное разбиение, т.е. система классов, называется системой классов эквивалентности по отношению R.

С другой стороны, любое разбиение А на классы определяет некоторое отношение эквивалентности, а именно, отношение “входить в один и тот же класс данного разбиения”, что утверждается следующей леммой:

Лемма: «Всякое разбиение множества А на классы задает на множестве А отношение эквивалентности»

Доказательство:

Пусть a, b Î A и aRb Û a и b лежат в одном классе разбиения. Тогда для любого а Î К aRa, т.е данное отношение рефлексивно.

Пусть К – некоторый класс разбиения, и a, b Î К. Тогда и b, a Î K, т.е. aRb Þ bRa, что доказывает симметричность отношения элементов данного класса.

Из aRb и bRc следует, что a, b, c Î K. Следовательно aRc что доказывает транзитивность отношения элементов данного класса.

Таким образом доказано, что элементы, определяющие класс разбиения, связаны отношением эквивалентности.

Пример. Разбиение множества натуральных чисел N={1, 2, ….} по отношению “иметь общий остаток от деления на 7” состоит из 7 бесконечных (счетных) классов: первый класс –{0, 7, 14, 21,….} (остаток 0), второй класс –{1, 8, 15, 22,…} (остаток 1), третий класс –{2, 9, 16,….} (остаток 2) ……, седьмой класс – {6, 13, 20, 27,….} (остаток 6).

Пример 5. Отношение “проживание в одном доме” в множестве жителей России образует разбиение населения России.

Множество классов эквивалентности множества А образует фактормножество множества А по отношению эквивалентности и обозначается А|~.

return false">ссылка скрыта

Системой представителей некоторого отношения эквивалентности ~ называется множество, содержащее по одному элементу из каждого класса эквивалентности.

Пример. Пусть на плоскости определена декартова система координат и координаты обозначаются через х и у. Будем говорить, что две точки М₁ и М₂ эквивалентны, если их абсциссы равны: М₁~М₂Ûх₁=х₂.

Класс эквивалентности – прямая, параллельная оси ординат. Фактормножества образованы прямыми на плоскости, параллельными оси ординат. Система представителей может определена точками, лежащими на оси абсцисс, т.е. точками с координатами (х, 0), хÎR.

Другими примерами отношения эквивалентности могут служить равенство и подобие фигур, логические утверждения, выражаемые с помощью оборотов “иметь такое же”, “быть таким же”.