Тема 5. Специальные виды бинарных отношений. Отношения эквивалентности. Классы эквивалентности. Разбиения.Примеры отношений эквивалентности.

Рассмотрим теперь некоторые специальные бинарные отношения, используя введённые обозначения и представления, а также дадим некоторые новые определения.

Назовём отношение _A = {(x, x) | xA}диагональнымотношением множестваA. Это самый узкий класс эквивалентностей, возможный в некоторой системе обозначений. Обычно это просто отношение равенства наА:_A = {(x, y) | xA & yA & x=y}. Графически ему соответствует набор вершин с петлями без рёбер между вершинами. Матрица такого отношения будет диагональной (единичной) логической матрицей. Отсюда название.

Рассматривавшееся свойство рефлексивности может тогда быть выражено формулой _A  .

Симметричность можно выразить формулой ^-1 =.

Транзитивность можно выразить формулой . (можно написать и²)

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

 - эквивалентность на множестве A(_A  &^-1 =&).

Если - некоторое бинарное отношение (AA), аx– некоторый элемент (xA), то для этого элемента можно указать множества элементов, связанных с ним потак, что он будет являться первым элементом в упорядоченной паре {y | (x, y)}. Графически это можно представить как все вершины, куда можно попасть изxза один шаг:

Аналогично можно указать и множество {y | (y, x)}, вершин, где начинаются стрелки, идущие вx.

Но если ^-1 =то {y | (x, y)}={y | (y, x)}. Для симметричных отношений обозначим такое множество как

[x]_ = {y | (x, y)} = {y | (y, x)}

Если это эквивалентность, то будем называть [x]_классом эквивалентностиэлементаxпо отношению. Это есть простомножество элементов, эквивалентных x. При этом элементxназываютобразующимкласса [x]_.

Для классов эквивалентности некоторого AAследует отметить следующие свойства.

1. Каждый элемент принадлежит своему классу эквивалентности.

xA x[x]_

Это свойство следует из рефлексивности :

_A  xA (x, x) xA x[x]_

2. Каждый элемент из класса образует в точности тот же самый класс.

y[x]_[y]_ = [x]_

Для обоснования необходимо использовать и свойство симметричности, и свойство транзитивности:

y[x]_(y, x)& (x, y)по определению [x]_и симметричности

Покажем что [y]_  [x]_, то есть, чтоz[y]_z[x]_

z[y]_(z, y)& (y, z)по определению [y]_и симметричности.

Имеем (z, y)& (y, x)

По транзитивности и определению [x]_получаем (z, x)  z[x]_

Аналогично покажем [x]_  [y]_, то есть, чтоz[x]_z[y]_

z[x]_(z, x)& (x, z)по определению [x]_и симметричности.

Имеем (z, x)& (x, y)

По транзитивности и определению [y]_получаем (z, y)  z[y]_

Из [y]_  [x]_и [x]_  [y]_получаем [y]_ = [x]_

Следующий возможный фрагмент графа поясняет эти 4 связи (рефлексивность непосредственно не используется для доказательства, но петли на графе приведены для иллюстративных целей, – это эквивалентность):

То есть, если zэквивалентенx, аxиyэквивалентны между собой, тоzэквивалентен каждому из них. Фактически, класс [z]_совпадет с [x]_и [y]_.

Рассмотренное свойство можно сформулировать и в виде следующей фразы:

3. Каждый класс эквивалентности представляет собой в точности множество всех своих образующих элементов.

4. Два класса либо не имеют общих элементов, либо полностью совпадают.

Возможные формулировки:

xA yA ([x]_  [y]_ = )  ( [x]_ = [y]_ )

или

([x]_  [y]_ )([x]_ = [y]_)

([x]_  [y]_)([x]_  [y]_ = )

Таким образом, каждый класс эквивалентности представляет собой полносвязнное по множество, а между разными классами связейнет. Пример фрагмента графа, удовлетворяющего этому условию, показан на рисунке.

В множестве Aвыделено два класса эквивалентности [x]_=[y]_=[z]_={x, y, z} и [u]_=[v]_={u, v}. Эти классы образуют разбиение множестваA. Это множество (множество классов) называется фактормножеством. Для него используется следующее обозначение:

= { [x]_ | xA }

В данном примере = {{x, y, z}, {u, v}}

Вообще разбиением некоторого множества A называют семейство множеств (множество S из множеств C), таких, что они

1. не пустые

2. в объединении покрывают всё множество A

3. попарно либо не пересекаются, либо полностью совпадают

(CS C) & & (C₁S C₂S ((C₁C₂=)  (C₁=C₂)))

При этом сами множества из семейства называют классами разбиений.

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

 = {(x, y) | CS xC & yC}

Рефлексивность: xA & CS  xC  (x, x).

Симметричность: Следует из коммутативности связки & в определении .

Транзитивность:

(x, y) & (y, z)  (C₁S  xC₁ & yC₁) & (C₂S  yC₂ & zC₂) 

(C₁S C₂S  xC₁ & yC₁ &  yC₂ & zC₂ & C₁C₂ & C₁=C₂) 

(CS xC & zC)(x, z)

Важным примером отношений эквивалентности являются отношения, получаемые при функциональном отображении одного множества на другое. Допустим, f B^A. Построим отношениеAAследующим образом:

 =  {(x, y) |  f(x)=f(y) }

Тогда оно будет являться отношением эквивалентности. Эквивалентными будут элементы, которым функция fставит в соответствие одинаковые значения (в смысле некоторого отношения равенства на множествеB). При этом классом эквивалентности будут множества всех тех элементов вA, для которых значения функции равны:

[x]_ = {y | f(x)=f(y) }

Следующая диаграмма показывает пример такого отношения:

То, что данное отношение действительно является эквивалентностью, непосредственно следует из аналогичных свойств отношения = на множестве B.

Примеры отношений эквивалентности: Сравнимость. Конгруэнция.

В теории чисел часто рассматривается следующее отношение эквивалентности. По некоторому натуральному числу nлюбоецелоечислоxможно единственным образом представить в видеx=an+bтак, чтобы 0≤bиb<n. Тогдаbназывают остатком от деленияxнаn. При фиксированномnbможно рассматривать в качестве результата вычисления некоторой функции:b=R_n(x). Определяя по рассмотренной схеме для этой функции отношение эквивалентности, получаем отношение «иметь одинаковые остатки от деления наn»:_n =  {(x, y) |  R_n(x)=R_n(y) }. Такое отношение называетсясравнением по модулюn. Для него в математике используется специальное обозначение

xy (modn)

Читается: «xсравнимо сyпо модулюn».

Каждый класс эквивалентности для этого отношения представляет собой множество чисел, дающих определённый остаток от деления на n, и называетсяклассом вычетов по модулюn. Обозначаются эти классы обычно просто символами квадратных скобок вокруг числа, выбранного образующим элементом класса. Обычно числоnясно из контекста. Образующими обычно берут минимальные неотрицательные элементы классов.

Пример для n=3. Возможны три вида остатков: 0, 1, 2. Множество всех классов вычетов по модулю 3 будет {[0], [1], [2]}. Число 7 и число 13 оба дают остаток от деления на 3, равный 1. Поэтому пишут 713 (mod 3), при этом 7[1] и 13[1].

Множество всех целых чисел обычно обозначают символом ℤ, а множество всех классов вычетов по модулюnобозначаютℤ_n. Например, ℤ₃={[0], [1], [2]}.

Для операции сложения целых чисел + такое разбиение на классы эквивалентности обладает важным свойством:

ab (mod n) & cd (mod n)  a+cb+d (mod n)

Получается, что данное отношение эквивалентности «согласовано» с некоторой операцией на разбиваемом множестве.

Отношение эквивалентности, согласованное с некоторой ассоциативной операцией на разбиваемом им на классы множестве, называется конгруэнцией:

(a, b)& (c, d) (a∗c, b∗d),

где ∗– некоторая ассоциативная бинарная операция.

Таким же свойством сравнение по модулю nобладает и по отношению к умножению целых чисел:ab (modn) &cd (modn)acbd (modn).

Конгруэнция – основной способ получения конечных алгебр (особенно недвоичных) из бесконечных. Она позволяет определять операции между классами на основе операций между образующими элементами.

Операцией между классами называют множество возможных значений результатов операции между элементами классов:

[x]_∗[y]_={ u∗v | u[x]_ & v[y]_ }

Для конгруэнции имеет место следующее представление:

[x]_∗[y]_= [x∗y]_

Для рассмотренного примера сравнения по модулю 3 можно построить следующие алгебры сложения и умножения классов:

+	[0]	[1]	[2]
[0]	[0]	[1]	[2]
[1]	[1]	[2]	[0]
[2]	[2]	[0]	[1]

Такая алгебра классов с операциями + и называется кольцом классов вычетов по модулю 3. Например, выражение [2]+[2]=[1] означает, что если сложить любые два числа, дающие остаток от деления на 3 равный 2, то получится число, дающее остаток от деления на 3 равный 1.

Примеры отношений эквивалентности: Эквивалентность (равномощность) множеств. Мощность множества. Счётные и несчётные множества.

Еще одним примером отношения эквивалентности является уже упомянутая эквивалентность (равномощность) множеств: A~B(f B^A  ( f ^-1 A^B)). То, что это действительно отношение эквивалентности, следует из следующего:

1. Рефлексивность. Каждое множество равномощно самому себе. Рассматривая отношение _Aкак функцию, ставящую каждому элементу множестваAего самого,_A A^A,xA _A(x)=x(эта функция биективная, так как (_A)^-1=_A) видим, чтоA~A. То, что некоторая функция устанавливает равномощность, удобно обозначать, надписывая её обозначение над символом ~: .

2. Симметричность. .

3. Транзитивность.

Классы эквивалентности отношения ~ представляют собой множества из всех множеств, равномощных некоторому образующему элементу (множеству). Обозначаются они обычно вертикальными чертами с обеих сторон от выбранного образующего элемента (множества) – представителя класса:

|A| = { B |A~B }

Такой класс эквивалентности называют мощностью множества. Для конечных множеств представление о таких классах можно считать отвлечённым представлением о числе, возникающим при рассматривании разнородных наборов предметов, общим для которых является именно количество предметов в наборах. Для бесконечных множеств их мощности представляют дальнейшее развитие понятия числа.Мощности произвольных множеств называют кардинальными числами.Множества, равномощные множеству натуральных чиселℕ,называют счётными множествами.В математике известны примеры построенных определений для бесконечных множеств, не являющихся счётными, например множество всех функцийℬ^ℕ(ℬ={0, 1}) не является счётным. Это множество можно представить как множество всехбесконечныхдвоичных последовательностей. В каждой последовательности на позиции с номеромjℕ записано одно из двух возможных значений 0 или 1 (как функция от номера позиции). Если бы всё множество таких последовательностей было счётным (каждой последовательности был бы назначен номерiℕ), последовательности можно было бы представить в видеa_ij, гдеi– номер последовательности,j– номер позиции. Но тогда можно построить новую последовательность, не совпадающую ни с одной из перечисленных по формуле

jℕ  b_j = a_jj

Эта последовательность, на каждой позиции которой с номером jзаписано значениеb_j, отличается от всех последовательностей, которые можно данным образом занумеровать (от каждой занумерованной последовательности она отличается, по крайней мере, в позиции, равной номеру последовательности). С другой стороны, она также (как функция от номера позиции) является элементом множестваℬ^ℕ. То есть, каково бы ни было отображение изℕвℬ^ℕ, вℬ^ℕостанутся незанумерованные элементы (функции), что и показывает несчётностьℬ^ℕ.

Для конечных множеств само число элементов выбирают в качестве обозначений их мощности, пишут |A|=n, имея в виду, что каждому натуральному числуnℕвзаимнооднозначно сопоставлен некоторый класс множеств, равномощныхK_n– множеству натуральных чисел от 1 доn. Мощность самого множестваℕтрадиционно обозначают |ℕ|=₀(древнееврейская буква алеф с индексом 0, обычно произносят «алеф-ноль», индексирование используется для указания порядковых типов множеств, здесь не рассматривается). Мощность множестваℬ^ℕобозначают как |ℬ^ℕ|=(алеф без индекса) или готической буквойc, и называютмощностью континуума.

Примеры отношений эквивалентности: подобие (изоморфизм) бинарных отношений (ориентированных графов).

Следующий пример связан непосредственно с самим предметом рассмотрения – бинарными отношениями. Допустим, задано два бинарных отношения, каждое на своем множестве:   AAи  BBи имеется биективная функция со следующим свойством:

fB^A & f ^-1A^B & (xA yA ( (x, y) ↔ (f(x), f(y)) ) )

Следующий рисунок иллюстрирует пример такого отображения.

Везде, где есть связь по отношению вA, есть связь между соответствующими отображениями по функцииfвBпо. И наоборот, если нет связи вAмежду некоторыми элементами, то нет и связи между их отображениями вB. Например, (a, b),f(a)=p,f(b)=qи (p, q). Где есть петля в графе, есть петля в графев вершине, соответствующей вершине с петлей впо функцииf.

Отношения, между которыми можно установить такие отображения, называются подобными.

Возможность установить такое отображение называется отношением подобия. Отношение подобия обозначим инфиксным символом .

    AA&  BB&

( f  B^A  ( f ^-1  A^B ) & (xA yA ( (x, y) ↔ (f(x), f(y)) ) )

Как и с равномощностью множеств, для удобства будем надписывать над символом обозначение функции, устанавливающей данное соответствие.

Покажем, что подобие отношений является отношением эквивалентности.

1. Рефлексивность.

2. Симметричность.

3. Транзитивность.

Классы эквивалентностей отношения подобия представляют собой множество всех отношений, имеющих определенную структуру связей между элементами без учета названий элементов и отношений. С точки зрения рассмотрения графов подобных отношений, подобие – это свойство иметь одинаковую форму графа. В рассмотренном примере оба графа могут быть описаны словами «три вершины, одна стрелка и петля в вершине, куда входит стрелка». Такие классы эквивалентностей можно назвать абстрактными отношениями. Их можно изображать графами, не подписывая узлов. Важно, что все свойства отношений, рассматриваемые здесь, не зависят от названий отношений, названий элементов и интерпретации отношения в предметной области. С другой стороны, изучив свойства какого-либо конкретного отношения, фактически мы изучили свойствавсехотношений данного класса. Для рассмотренного примера граф абстрактного отношения выглядит так:

Число различных классов отношений вообще-то меньше, чем самих отношений. Например, для двоичного множества все отношения могут быть представлены логическими матрицами 22. Таких матриц 16. Некоторые из них будут представлять подобные отношения. Разбиение множества таких матриц на классы эквивалентности по подобию соответствующих им отношений представим ориентированными графами и укажем матрицы, реализующие эти отношения. Видно, что число классов (форм конфигураций связей) будет 10. Некоторые классы имеют по две реализации.