Доказать что бинарное отношение является отношением эквивалентности. Бинарные отношения, свойства отношений

Часто используют инфиксную форму записи: .

Если отношение определено на множестве, то возможно следующее определение:

Примерами множеств с введёнными на них бинарными отношениями являются графы и частично упорядоченные множества.

Для определены свойства:

Рефлексивность (англ. reflexivity ): ;

Отношение R на множестве Х называется рефлексивным, если о каждом элементе множества Х можно сказать, что он находится в отношении R с самим собой: хRх. Если отношение рефлексивно, то в каждой вершине графа имеется петля. И обратно, граф, каждая вершина которого содержит петлю, представляет собой граф рефлексивного отношения.

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

Антирефлексивность (англ. irreflexivity ): ;

Отношение R на множестве Х называется антирефлексивным , если для любого элемента из множества Х всегда ложно хRх:.

Симметричность (англ. symmetry ): ;

Отношение R на множестве Х называется симметричным , если выполняется условие: из того, что элемент х находится в отношении с элементом y , следует, что и элемент y находится в отношении R с элементом х: xRyyRx .

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

Антисимметричность (англ. antisymmetry ): ;

Отношение R называют антисимметричным , если для любых элементов х и y из истинности xRy следует ложность yRx: : xRyyRx.

Транзитивность (англ. transitivity ): ;

Отношение R на множестве Х называют транзитивным, если из того, что элемент х находится в отношении R с элементом y, а элемент y находится в отношении R с элементом z , следует, что элемент х находится в отношении R с элементом z : xRy и yRzxRz.

Свойством транзитивности обладает и отношение «длиннее» на множестве отрезков: если отрезок а длиннее отрезка b , отрезок b длиннее отрезка с , то отрезок а длиннее отрезка с. Отношение «равенства» на множестве отрезков также обладает свойством транзитивности: (а=b, b=с)(а=с).

Связность (англ. connectivity ): ;

Отношение R на множестве Х называется связанным, если для любых элементов х и y из данного множества выполняется условие: если х и y различны, то либо х находится в отношении R с элементом y , либо элемент y находится в отношении R с элементом х . С помощью символов это определение можно записать так: xyxRy или yRx.

Например, свойством связанности обладает отношение «больше» для натуральных чисел: для любых различных чисел х и y можно утверждать, либо x>y, либо y>x.

Ассимметричность (англ. assymetric relation ): .

Выделяются следующие виды отношений:

квазипорядка (англ. quasiorder ) - рефлексивное транзитивное;

эквивалентности (англ. equivalence ) - рефлексивное симметричное транзитивное;

Отношение R на множестве Х называется отношением эквивалентности, если оно одновременно обладает свойством рефлексивности, симметричности и транзитивности.

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

В рассмотренном выше отношении «равенства дробей», множество Х разбилось на три подмножества: {; ; }, {; }, {}. Эти подмножества не пересекаются, а их объединение совпадает с множеством Х , т.е. имеем разбиение множества на классы.

Итак, если на множестве Х задано отношение эквивалентности, то оно порождает разбиение этого множества на попарно непересекающиеся подмножества – классы эквивалентности.

частичного порядка (англ. partial order ) - рефлексивное антисимметричное транзитивное;

Бинарное отношение на множественазывается отношением частичного порядка (англ. partial order relation

Рефлексивность (англ. reflexivity ): .

Антисимметричность (англ. antisymmetry ): еслии, то.

Транзитивность (англ. transitivity ): еслии, то.

«больше или равно» и «меньше или равно» - нестрогого, причем линейного порядка, но не полного.

Отношение «является делителем» на множестве натуральных чисел является отношением частичного порядка.

строгого порядка (англ. strict order ) - антирефлексивное антисимметричное транзитивное;

Бинарное отношение на множественазывается строгим отношением частичного порядка (англ. strict order relation ), если оно обладает следующими свойствами:

Антирефлексивность (англ. irreflexivity ): - не выполняется.

Антисимметричность (англ. antisymmetry ): еслии, то.

Транзитивность : (англ. transitivity ) еслии, то.

На множестве вещественных чисел отношения «больше» и «меньше» являются отношениями строгого порядка

линейного порядка (англ. total order ) - полное антисимметричное транзитивное;

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

Бинарное отношение на множественазывается отношением линейного порядка (англ. total order relation ), если оно является отношением частичного порядка и обладает следующим свойством: либо, либо.

доминирования (англ. dominance ) - антирефлексивное антисимметричное.

толерантности

Отношением толерантности (или просто толерантностью) на множестве X называется бинарное отношение, удовлетворяющее свойствам рефлексивности и симметричности , но не обязательно являющееся транзитивным. Таким образом, отношение эквивалентности является частным случаем толерантности.

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

На содержательном уровне толерантность означает следующее. Любой объект неразличим сам с собой (свойство рефлексивности), а сходство двух объектов не зависит от того, в каком порядке они сравниваются (свойство симметричности). Однако, если один объект сходен с другим, а этот другой - с третьим, то это вовсе не значит, что все три объекта схожи между собой (таким образом, свойство транзитивности может не выполняться).

Отношение толерантности часто используется для описания отношения сходства между реальными объектами, отношений знакомства или дружбы между людьми. Во всех этих случаях свойство транзитивности не предполагается обязательно быть выполненным. В самом деле, Иванов может быть знаком с Петровым, Петров - с Сидоровым, но при этом Иванов и Сидоров могут быть незнакомы между собой.

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

Примеры отношений

Примеры рефлексивных отношений : равенство, одновременность, сходство.

Примеры нерефлексивных отношений : «заботиться о», «развлекать», «нервировать».

Примеры транзитивных отношений : «больше», «меньше», «равно», «подобно», «выше», «севернее».

Примеры симметричных отношений : равенство (=), неравенство, отношение эквивалентности, подобия, одновременности, некоторые отношения родства (например, отношение братства).

Примеры антисимметричных отношений : больше, меньше, больше или равно.

Примеры асимметричных отношений : отношение «больше» (>) и «меньше» (<).

Бинарное отношение на множественазывается отношением эквивалентности (англ. equivalence binary relation ), если оно обладает следующими свойствами:

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

Симметричность : если, то.

Транзитивность : еслии, то.

Отношение эквивалентности обозначают символом. Запись видачитают как "эквивалентно"

Отношение равенства () является тривиальным примером отношения эквивалентности на любом множестве.

Отношение равенства по модулю : на множестве целых чисел.

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

Отношение подобия фигур на плоскости.

Отношение равносильности на множестве уравнений.

Отношение связности вершин в графе.

Отношение быть одного роста на множестве людей.

Система непустых подмножеств множестваназывается разбиением (англ. partition ) данного множества, если:

Множества называются классами данного разбиения.

Если на множестве M задано отношение эквивалентности, то оно порождает разбиение этого множества на классы эквивалентности такое, что:

любые два элемента одного класса находятся в отношении

любые два элемента разных классов не находятся в отношении

Семейство всех классов эквивалентности множества образует множество, называемое фактор-множеством , или факторизацией множества по отношению, и обозначаемое.

Равенство - классический пример отношения эквивалентности на любом множестве.

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

1. Отношение эквивалентности. Связь отношения эквивалентности с разбиением множества на классы.

2. Отношение порядка. Строгое и нестрогое отношения порядка, отношение линейного порядка. Упорядоченность множеств.

3. Основные выводы

Рассмотрим на множестве дробей X = {1/2, 1/3, 1/4, 2/4, 2/6, 3/6} отношение равенства. Это отношение:

Рефлексивно, так как всякая дробь равна сама себе;

Симметрично, так как из того, что дробь m /n равна дроби p /q , следует, что дробь p /q равна дроби m /n ;

Транзитивно, так как из того, что дробь m /n равна дроби p /q и дробь p /q равна дроби r /s , следует, что дробь m /n равна дроби r /s .

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

Определение. Отношение R на множестве X называется отношением эквивалентности, если оно одновременно обладает свойствами рефлексивности, симметричности и транзитивности.

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

Почему в математике выделили этот вид отношений? Рассмотрим отношение равенства дробей, заданное на множестве X = {1/2, 1/3, 1/4, 2/4, 2/6, 3/6} (Рис.106). Видим, что множество разбилось на три подмножества: {1/2, 2/4, 3/6}, {1/3, 2/6}, {1/4}. Эти подмножества не пересекаются, а их объединение совпадает с множеством Х, т.е. имеем разбиение множества X на классы. Это не случайно.

Вообще, если на множестве X задано отношение эквивалентности, то оно порождает разбиение этого множества на попарно непересекающиеся подмножества (классы эквивалентности).

Так, мы установили, что отношению равенства на множестве дробей {1/2, 1/3, 1/4, 2/4, 2/6, 3/6} соответствует разбиение этого множества на классы эквивалентности, каждый из которых состоит из равных между собой дробей.

Верно и обратное утверждение: если какое-либо отношение, заданное на множестве X, порождает разбиение этого множества на классы, то оно является отношением эквивалентности.

Рассмотрим, например, на множестве X = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} отношение «иметь один и тот же остаток при делении на 3». Оно порождает разбиение множества X на классы: в один попадут все числа, при делении которых на 3 получается в остатке 0 (это числа 3, 6, 9), во второй - числа, при делении которых на 3 в остатке получается 1 (это числа 1, 4, 7, 10), и в третий - все числа, при делении которых на 3 в остатке получается 2 (это числа 2, 5, 8). Действительно, полученные подмножества не пересекаются и их объединение совпадает с множеством X. Следовательно, отношение «иметь один и тот же остаток при делении на 3», заданное на множестве X, является отношением эквивалентности. Заметим, что утверждение о взаимосвязи отношения эквивалентности и разбиения множества на классы нуждается в доказательстве. Мы его опускаем. Скажем только, что если отношение эквивалентности имеет название, то соответствующее название дается и классам. Например, если на множестве отрезков задается отношение равенства (а оно является отношением эквивалентности), то множество отрезков разбивается на классы равных отрезков (см. рис. 99). Отношению подобия соответствует разбиение множества треугольников на классы подобных треугольников.

Итак, имея отношение эквивалентности на некотором множестве, мы можем разбить это множество на классы. Но можно поступить и наоборот: сначала разбить множество на классы, а затем определить отношение эквивалентности, считая, что два элемента эквивалентны тогда и только тогда, когда они принадлежат одному классу рассматриваемого разбиения.

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

Во-первых , эквивалентный - это значит равносильный, взаимозаменяемый. Поэтому элементы одного класса эквивалентности взаимозаменяемы. Так, дроби, оказавшиеся в одном классе эквивалентности {1/2, 2/4, 3/6} неразличимы с точки зрения отношения равенства, и дробь 3/6 может быть заменена другой, например 1/2. И эта замена не изменит результата вычислений.

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

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

Вообще любое понятие, которым оперирует человек, представляет собой некоторый класс эквивалентности. «Стол», «дом», «книга» - все эти понятия являются обобщенными представлениями о множестве конкретных предметов, имеющих одинаковое назначение.

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

Определение. Отношение R на множестве X называется отношением порядка, если оно одновременно обладает свойствами антисимметричности и транзитивности .

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

Если отношение порядка обладает еще свойством связанности, то говорят, что оно является отношением линейного порядка.

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

Определение. Множество X называется упорядоченным, если на нем задано отношение порядка.

Так, множество N натуральных чисел можно упорядочить, если задать на нем отношение «меньше».

Если отношение порядка, заданное на множестве X, обладает свойством связанности, то говорят, что оно линейно упорядочивает множество X.

Например, множество натуральных чисел можно упорядочить и с помощью отношения «меньше», и с помощью отношения «кратно» - оба они являются отношениями порядка. Но отношение «меньше», в отличие от отношения «кратно», обладает еще и свойством связанности. Значит, отношение «меньше» упорядочивает множество натуральных чисел линейно.

Не следует думать, что все отношения делятся на отношения эквивалентности и отношения порядка. Существует огромное число отношений, не являющихся ни отношениями эквивалентности, ни отношениями порядка.

Рассмотрим на множестве дробей X = { } отношение равенства. Это отношение:

Рефлексивно, так как всякая дробь равна сама себе;

Симметрично, так как из того, что дробь равна дроби , следует, что дробь равна дроби ;

Транзитивно, так как из того, что дробь равна дроби и дробь равна дроби , следует, что дробь равна дроби .

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

Почему в математике выделили этот вид отношений? Рассмотрим отношения равенства дробей, заданного на множестве X = { }. (Рис.7).

Видим, что множество разбилось на три подмножества: Эти подмножества не пересекаются, а их объединение совпадает с множеством X, т е имеем разбиение множества X на классы. Это не случайно.

Вообще если на множестве X задано отношение эквивалентности, то оно порождает разбиение этого множества на попарно непересекающиеся подмножества (классы эквивалентности).

Так, мы установили, что отношению равенства на множестве дробей

X = { } соответствует разбиение этого множества на классы эквивалентности, каждый из которых состоит из равных между собой дробей.

Рассмотрим, например, на множестве X = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} отношение «иметь один и тот же остаток при делении на 3». Оно порождает разбиение множества X на классы: в один попадут все числа, при делении которых на 3 получается в остатке 0 (это числа 3, 6, 9), во второй - числа, при делении которых на 3 в остатке получается 1 (это числа 1, 4, 7, 10), и в третий - все числа, при делении которых на 3 в остатке получается 2 (это числа 2, 5, 8). Действительно, полученные подмножества не пересекаются и их объединение совпадает с множеством X. Следовательно, отношение «иметь один и тот же остаток при делении на 3», заданное на множестве X, является отношением эквивалентности. Заметим, что утверждение о взаимосвязи отношения эквивалентности и разбиения множества на классы нуждается в доказательстве. Мы его опускаем. Скажем только, что если отношение эквивалентности имеет название, то соответствующее название дается и классам. Например, если на множестве отрезков задается отношение равенства (а оно является отношением эквивалентности), то множество отрезков разбивается на классы равных отрезков (см. рис. 4). Отношению подобия соответствует разбиение множества треугольников на классы подобных треугольников.

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

Другим важным видом отношений являются отношения порядка. Оно определяется следующим образом.

Определение. Отношение R на множестве X называется отношением порядка, если оно одновременно обладает свойством антисимметричности и транзитивности.

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

«короче» на множестве отрезков, поскольку они антисимметричны и транзитивны.

Если отношение порядка обладает еще свойством связанности, то говорят, что оно является отношением линейного порядка.

Определение. Множество X называется упорядоченным, если на нем задано отношение порядка.

Так, множество N натуральных чисел можно упорядочить, если задать на нем отношение «меньше».

Если отношение порядка, заданное на множестве X, обладает свойством связанности, то говорят, что оно линейно упорядочивает множество X.

ОТНОШЕНИЯ

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

x А, у А отношение Г = {(x,y)| P(x,y)}, P(x,y) какое-то утверждение (предикат).

Если (x,y) Г, то говорят, что х находятся в отношении Г к у .

Например, иметь одинаковый остаток от деления (для чисел), быть на одинаковом расстоянии от прямой (для точек), родственные отношения или соседские отношения (для множества людей).

Более строгое определение:

Бинарным отношением называется два множества:

1) несущее множество А,

2) множество пар Г={(x,y)| x A, y A}, являющегося подмножеством квадрата несущего множества.

n-местное отношение, или n-арное (тернарное, кватернарное, …) отношение – это несущее множество А и множества кортежной размерностью n ,являющегося подмножеством множества А n .

Пример тернарного отношения: входить в «тройку игроков».

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

Отношение можно определить также как двухместный предикат предметных переменных х, у , принимающего значение «истина», если (х, у) Г и значение «ложь», если не принадлежит.

Обозначения: (х, у) Г, у = Г(x), у = Гx или просто xГу , например, отношение равенства(х = у) , отношение порядка(х < у) .

Если (х, у) Г , то xГу принимает значение «истина», иначе – «ложь».

Если отношения заданы на дискретном множестве, их можно записывать в виде матрицы

A i , j =

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

Г -1 ={(y,x)| (x,y) Г}, Г ◦ Δ = {(x,z) | y ((x,y) Г &(y,z Δ))}.

Вводят понятие «единичного элемента» Δ 0 = {(x,x)} – «быть в отношении к самому себе». В матричном представлении это будет - главная диагональ).

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

1 Рефлексивность – «находиться в отношении к самому себе»

хГх – истина (например, отношения х=x, х≤x, х≥x ).

2 Антирефлексивность - «не быть в отношении к самому себе»

хГx - ложь (например, отношения х≠x, хх ).

Если множество не «рефлексивно», то это еще не значит что оно «антирефлексивно».

3 Симметричность «независимость от того, какой элемент первый, какой второй»

хГу – истина → уГх – истина (например, отношения х=у, х≠у ).

4 Антисимметричность «не превосходить»

(хГу – истина) & (yГх – истина) → (х=у) (например, отношения х≤у, х≥у ).

5 Асимметричность (несимметричность) «превосходить»

хГу – истина → уГх –ложь (например, отношения х<у, х>у ).

6. Транзитивность «передаточность»

(хГу – истина) & (yГz – истина) → (хГz – истина) (например, отношения х=у, х<у, х>у, х≤у, х≥у , отношение х≠у транзитивностью не обладает).

СПЕЦИАЛЬНЫЕ БИНАРНЫЕ ОТНОШЕНИЯ

Рассмотрим «отношение эквивалентности», «отношение нестрогого порядка», «отношение строгого порядка» и «отношение доминирования».

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

Отношением эквивалентности называется рефлексивное (х~x) , симметричное ((х~y)=(y~x)) , транзитивное ((х~у)&(y~z)→(х~z)) отношение.

Примеры: равенство, тождественность, эквивалентность множеств, эквивалентность логических высказываний, подобие геометрических фигур, параллельность прямых, а вот перпендикулярность прямых - не является отношением эквивалентности.

Подмножество элементов, эквивалентных одному элементу, называется классом эквивалентности или смежным классом.

Любой элемент из класса называется представителем класса.

Свойства.

Все элементы в классе эквивалентны между собой.

Элементы из разных классов не эквивалентны.

Один элемент может входить только в свой класс.

Все множество можно представить как объединение классов.

Таким образом, множество классов эквивалентности или полная система классов образуют разбиение несущего множества. Напоминание: разбиение множества – это представление его в виде непересекающихся подмножеств.

Индекс разбиения – число классов эквивалентности.

Фактор-множество относительно отношения эквивалентности - это множество всех классов или представителей класса.

Мощность фактора-множества равна индексу разбиения.

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

Отношением порядка называют два вида бинарных отношений.

Отношениемнестрогого порядка называется рефлексивное (х≥x) , антисимметричное ((x≤y)&(y≤x)→ (x=y)) , транзитивное ((х≥у)&(y≥z)→(х≥z)) отношение .

Говорят, что на множестве установлен нестрогий порядок. В понятия ≤ , ≥ вкладывают более широкий смысл: не хуже – не лучше, не раньше – не позже и так далее. В теории множеств пример нестрого порядка - нестрогое включение (быть подмножеством другого множества0.

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

((х>у)&(y отношение .

Говорят, что на множестве установлен строгий порядок. В понятия < , > вкладывают более широкий смысл: хуже – лучше, раньше – позже и так далее. В теории множеств пример строго порядка - строгое включение (быть подмножеством другого множества и при этом не быть равным ему).

Упорядоченные множества

Множество называется линейно упорядоченным , если любы едва элемента можно сравнить)то есть сказать: больше, меньше или равно).

Множество действительных или целых чисел: классические примеры упорядоченного множества.

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

Это множество векторов, множество комплексных чисел, множества в теории множеств. В некоторых случаях мы можем говорит «больше – меньше» или «являться надмножеством и подмножеством», но не во всех случаях.

I. Разбиение на классы. Отношение эквивалентности

Определение 2.1. Назовем взаимозаменяемыми те и только те объекты некоторого данного множества М, которые обладают одним и тем же набором формальных признаков, существенных в данной ситуации.

Обозначим через М х -множество всех объектов, взаимозаменяемых с объектом х. Очевидно, что х М х и объединение всех М х (при всевозможных х из М) совпадает совсем множеством М:

Предположим, что. Это значит, что существует некоторый элемент z, такой, что он одновременно принадлежит и и. Значит x взаимозаменяем с z и z взаимозаменяем с у. Следовательно, х взаимозаменяем с у, а значит и с любым элементом из. Таким образом. Аналогично показывается и обратное включение. Таким образом, встречающиеся в объединении (2.1) множества либо не пресекаются, либо целиком совпадают.

Определение 2.2. Систему непустых подмножеств {M 1 , M 2 ,….} множества М мы будем называть разбиением этого множества, если

Сам множества при этом называются классами разбиения.

Определение 2.3. Отношение с на множестве М называется эквивалентностью (или отношением эквивалентности), если существует такое разбиение {M 1 , M 2 ,….} множества М такое, что (х, у) выполняется тогда и только тогда, когда х и у принадлежат к некоторому общему классу M i данного разбиения.

Пусть {M 1 , M 2 ,….} разбиение множества М. Определим, исходя из этого разбиения, отношение с на М: (х, у),если х и у принадлежат к некоторому общему классу M i данного разбиения. Очевидно, что отношение с является эквивалентностью. Назовем с отношением эквивалентности, соответствующим данному разбиению.

Определение 2.4. Если в каждом подмножестве M i выбрать содержащийся в нем элемент х i , то этот элемент будем называть эталоном для всякого элемента у, входящего в тоже множество M i . По определению, положим выполненным отношение с* «быть эталоном» (х i , у)

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

Пример 2.1: Рассмотрим в качестве М множество целых неотрицательных чисел и возьмем его разбиение на множество М 0 четных чисел и множество М 1 - нечетных. Соответствующее отношение эквивалентности на множестве целых чисел обозначается так:

и читается: n сравнимо с m по модулю 2. В качестве эталонов естественно выбрать 0 - для четных чисел и 1 - для нечетных. Аналогично, разбивая то же множество М на k подмножеств M 0 , M 1 ,… M k-1 , где M j состоит из всех чисел, дающих при делении на k в остатке j, мы придем к отношению эквивалентности:

которое выполняется, если n и m имеют одинаковые остатки при делении на k.

В качестве эталона в каждом M j естественно выбрать соответствующий остаток j.

II. Фактор-множество

Пусть - отношение эквивалентности. Тогда по теореме, существует разбиение {M 1 , M 2 ,….} множества М на классы эквивалентных друг другу элементов - так называемые классы эквивалентности.

Определение 2.5. Множество классов эквивалентности по отношению обозначают М/ и читают фактор-множество множества М по отношению.

Пусть ц: M > S - сюрьективное отображение множества М на некоторое множество S.

Для всякого ц: M > S - сюрьективного отображения существует такое отношение эквивалентности на множестве М, что М/ и S могут быть поставлены во взаимно однозначное соответствие.

III. Свойства эквивалентности

Определение 2.6. Отношение с на множестве М называется эквивалентностью (отношением эквивалентности), если оно рефлексивно, симметрично и транзитивно.

Теорема 2.1: Если отношение с на множестве М рефлексивно, симметрично и транзитивно, существует такое разбиение {M 1 , M 2 ,….} множества М такое, что (х, у) выполняется тогда и только тогда, когда х и у принадлежат к некоторому общему классу M i данного разбиения.

Обратно: Если задано разбиение {M 1 , M 2 ,….} и бинарное отношение с задано как «принадлежать к общему классу разбиения», то с рефлексивно, симметрично и транзитивно.

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

Рассмотрим рефлексивное, симметричное и транзитивное отношение с на М. Пусть для любого состоит из всех таких 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) с. Первая часть теоремы доказана.

Пусть дано разбиение {M 1 , M 2 ,….} множества М. Т.к. объединение всех классов разбиения совпадает с М, то любой хвходит в некоторый класс. Отсюда следует, что (x, х) с, т.е. с - рефлексивно. Если x и y входят в некоторый класс, то y и x входят в тот же класс. Это означает, что из (x, y) с вытекает (y, x) с, т.е. отношение симметрично. Пусть теперь выполнено (x, y) с и (y, z) с. Это означает, что x и y входят в некоторый класс, а y и z входят в некоторый класс. Классы имеют общий элемент у, а, следовательно, совпадают. Значит x и z входят в класс, т.е. выполняется (x, z) с и отношение транзитивно. Теорема доказана.

IV. Операции над эквивалентностями.

Определим здесь некоторые теоретико-множественные операции над эквивалентностями и приведем без доказательств их важные свойства.

Вспомним, что отношение - это пара (), где М - множество элементов, вступающих в отношение, а - множество пар, для которых отношение выполнено.

Определение 2.7. Пересечением отношений (с 1 , М) и (с 2 , М) назовем отношение, определенное пересечением соответствующих подмножеств. (x, y) с 1 с 2 тогда и только тогда, когда одновременно (x, y) с 1 и (x, y) с 2 .

Теорема 2.2: Пересечение с 1 с 2 эквивалентностей с 1 с 2 само является отношением эквивалентности.

Определение 2.8. Объединением отношений (с 1 , М) и (с 2 , М) назовем отношение, определенное объединением соответствующих подмножеств. (x, y) с 1 с 2 тогда и только тогда, когда (x, y) с 1 или (x, y) с 2 .

Теорема 2.3: Для того, чтобы объединение с 1 с 2 эквивалентностей с 1 с 2 само по себе было отношением эквивалентности необходимо и достаточно, чтобы

с 1 с 2 =с 1 с 2

Определение 2.9. Прямой суммой отношений (с 1 , М 1) и (с 2 , М 2) называется отношение). Прямая сумма обозначается (с 1 , М 1) (с 2 , М 2).

Таким образом, если (с 1 , М 1) (с 2 , М 2)= (), то M=.

Теорема 2.4: Если, а отношения - эквивалентности, то прямая сумма отношений (с 1 , М 1) (с 2 , М 2)= (), также является эквивалентностью.

V. Типы отношений

Введем еще несколько важных типов отношений. Примеры будут приведены в третьей главе.

Определение 2.10. Отношение с на множестве М называется толерантностью, если оно рефлексивно и симметрично.

Определение 2.11. Отношение с на множестве М называется отношением строгого порядка если оно антирефлексивно и транзитивно.

Определение 2.12. Отношение строгого порядка с называется совершенным строгим порядком, если для всякой пары элементов x и y из М верно либо (х, у), либо (у, х)

Определение 2.13. Отношение с на множестве М называется отношением нестрогого порядка если оно может быть представлено в виде:

где строгий порядок на М, а Е -диагональное отношение.