Классы эквивалентных элементов и их свойства

Пусть %%R%% — отношение эквивалентности на множестве %%M%% и %%a%% — некоторый элемент из %%M%%. Рассмотрим множество всех элементов из %%M%%, находящихся в отношении %%R%% к элементу %%a%%.

Классом эквивалентности %%M_a%%

называется множество всех элементов %%M%%, находящихся в отношении %%R%% к элементу %%a%%, то есть множество

$$ M_a = \{x \in M: x~R~a\}. $$

Пример

Пусть %%M%% — множество всех жителей России и %%R%% — отношение эквивалентности «проживать в одном городе». Найти классы эквивалентных элементов %%M_a%% для %%a \in M%%.

Класс элементов, эквивалентных элементу %%a%%, имеет вид: $$ M_a = \{x \in M: x \text{ проживает в одном городе с человеком } a\} $$

В зависимости от элемента %%a%% получаем несколько классов эквивалентности. Например, класс эквивалентности жителей Москвы или Санкт-Петербурга.

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

Пусть %%R%% — отношение эквивалентности на множестве %%M%% и %%M_a, M_b, \dotsc, M_z, \dotsc%% — все классы эквивалентности для отношения %%R%%. Тогда эти классы имеют следующие свойства.

Свойство 1

Для любого элемента %%a \in M%% выполняется условие $$ a \in M_a $$

Действительно, по определению, класс %%M_a = \{x \in M: x~R~a\}%%. Тогда для элемента %%a%% должно выполняться условие %%a \in M_a \leftrightarrow a~R~a%%, которое выполняется в связи с тем, что отношение %%R%% рефлексивно по определению отношения эквивалентности. Следовательно, %%a \in M_a%%.

Как следствие этого свойства можно сказать, что всякий класс %%M_a%% является непустым множеством.

Свойство 2

Пусть %%M_a%% и %%M_b%% классы эквивалентности для отношения %%R%%. Классы %%M_a%% и %%M_b%% равны тогда и только тогда, когда элемент %%a%% находится в отношении %%R%% к элементу %%b%%. $$ M_a = M_b \leftrightarrow a~R~b. $$

Свойство 3

Пусть %%M_a%% и %%M_b%% классы эквивалентности для отношения %%R%%. Тогда классы %%M_a%% и %%M_b%% не имеют общих элементов. $$ M_a \neq M_b \rightarrow M_a \cap M_b = \varnothing $$

Свойство 4

Объединение всех классов эквивалентности множества %%M%% равно множеству %%M%%. $$ \bigcup_{a\in M}{M_a} = M. $$

Разбиение множества

Совокупностью подмножеств %%M_i%%, где %%i \in I%% (множеству индексов), множества %%M%% называется разбиением множества %%M%% если выполняются следующие условия:

1. Каждое из подмножеств %%M_i%% непусто.
2. Объединение всех подмножеств %%M_i%% равно множеству %%M%%.
3. Два различных подмножества %%M_i%% и %%M_j%%, где %%i \neq j%%, не имеют общих элементов.

Теорема. Пусть %%R%% — отношение эквивалентности на множестве %%M%%. Тогда совокупность классов эквивалентности множества %%M%% образует его разбиение.

Действительно, если в качестве подмножеств %%M_i%% взять классы эквивалентности %%M_a%%, то все три условия выполняются:

1. Каждый класс эквивалентности является непустым множеством, согласно свойству 1 .
2. Объединение всех классов эквивалентности есть множество %%M%%, согласно свойству 4 .
3. Два различных класса эквивалентности не имеют общих элементов, согласно свойству 3 .

Все условия определения разбиения выполнены. Следовательно классы эквивалентности есть разбиение множества %%M%%.

Примеры

Пусть дано множество %%M = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 0 \}%%, тогда разбиением этого множества могут быть следующие совокупности множеств:

1. %%A_1 = \{1, 2, 3\}, A_2 = \{4, 5, 6, 7\}, A_3 = \{8, 9, 0 \}%%.
2. %%B_1 = \{0, 7, 2\}, B_2 = \{1, 3, 5 \}, B_3 = \{4, 6, 8, 9\}%%.

Но следующие совокупности не являются разбиением:

1. %%C_1 = \{1, 2, 3\}, C_2 = \{4, 5, 6, 7\}, C_3 = \{8, 9, 0, 3\}%%.
2. %%D_1 = \{0, 7, 2\}, D_2 = \{1, 3, 5 \}, D_3 = \{4, 6, 8, 9\}, D_4 = \varnothing%%.
3. %%E_1 = \{0, 1, 2\}, E_2 = \{3, 4, 5\}, E_3 = \{6, 7, 8\}%%.

Совокупность множеств %%C_i%% не является разбиением, т.к. оно не удовлетворяет условию 3 разбиения множеств: множества %%C_1%% и %%C_3%% имеют общий элемент %%3%%.

Совокупность множеств %%D_i%% не является разбиением, т.к. оно не удовлетворяет условию 1 разбиения множеств: множество %%D_4%% пусто.

Совокупность множеств %%E_i%% не является разбиением, т.к. оно не удовлетворяет условию 2 разбиения множеств: объединение множеств %%E_1, E_2%% и %%E_3%% не образует множество %%M%%.

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

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

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

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

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

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

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

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

Видим, что множество разбилось на три подмножества: Эти подмножества не пересекаются, а их объединение совпадает с множеством X, т е имеем разбиение множества 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.

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

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

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

Отношения эквивалентности и порядка

Напомним, что бинарным отношением на множестве называется подмножество ; вместо часто пишут .

Бинарное отношение на множестве называется отношением эквивалентности , если выполнены следующие свойства:

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

Теорема 11 . (а) Если множество разбито в объединение непересекающихся подмножеств, то отношение " лежать в одном подмножестве" является отношением эквивалентности.

(б) Всякое отношение эквивалентности получается описанным способом из некоторого разбиения.

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

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

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

78. Покажите, что требования симметричности и транзитивности можно заменить одним: (при сохранении требования рефлексивности).

79. Сколько различных отношений эквивалентности существует на множестве ?

80. На множестве задано два отношения эквивалентности, обозначаемые и , имеющие и классов эквивалентности соответственно. Будет ли их пересечение отношением эквивалентности? Сколько у него может быть классов? Что можно сказать про объединение отношений ?

81. (Теорема Рамсея) Множество всех - элементных подмножеств бесконечного множества разбито на классов (, - натуральные числа). Докажите, что найдется бесконечное множество , все - элементные подмножества которого принадлежат одному классу.

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

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

Отношения эквивалентности нам не раз еще встретятся, но сейчас наша основная тема - отношения порядка.

Бинарное отношение на множестве называется отношением частичного порядка , если выполнены такие свойства:

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

Говорят, что два элемента частично упорядоченного множества сравнимы , если или . Заметим, что определение частичного порядка не требует, чтобы любые два элемента множества были сравнимы. Добавив это требование, мы получим определение линейного порядка (линейно упорядоченного множества ).

Приведем несколько примеров частичных порядков:

• Числовые множества с обычным отношением порядка (здесь порядок будет линейным).
• На множестве всех пар действительных чисел можно ввести частичный порядок , считая, что , если и . Этот порядок уже не будет линейным: пары и не сравнимы.
• На множестве функций с действительными аргументами и значениями можно ввести частичный порядок , считая, что , если при всех . Этот порядок не будет линейным.
• На множестве целых положительных чисел можно определить порядок, считая, что , если делит . Этот порядок тоже не будет линейным.
• Отношение " любой простой делитель числа является также и делителем числа " не будет отношением порядка на множестве целых положительных чисел (оно рефлексивно и транзитивно, но не антисимметрично).
• Пусть - произвольное множество. Тогда на множестве всех подмножеств множества отношение включения будет частичным порядком.
• На буквах русского алфавита традиция определяет некоторый порядок (). Этот порядок линеен - про любые две буквы можно сказать, какая из них раньше (при необходимости заглянув в словарь).
• На словах русского алфавита определен лексикографический порядок (как в словаре). Формально определить его можно так: если слово является началом слова , то (например, ). Если ни одно из слов не является началом другого, посмотрим на первую по порядку букву, в которой слова отличаются: то слово, где эта буква меньше в алфавитном порядке, и будет меньше. Этот порядок также линеен (иначе что бы делали составители словарей?).
• Отношение равенства () также является отношением частичного порядка , для которого никакие два различных элемента не сравнимы.
• Приведем теперь бытовой пример. Пусть есть множество картонных коробок. Введем на нем порядок, считая, что , если коробка целиком помещается внутрь коробки (или если и - одна и та же коробка). В зависимости от набора коробок этот порядок может быть или не быть линейным.

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

П р и м е р 1. Пусть на множестве всех целых неотрицательных чисел N 0 = {0, 1, 2, 3, …} задано отношение Р : «числа х и у имеют один и тот же остаток при делении на 3». Докажем, что Р – отношение эквивалентности и определим классы эквивалентности, определяемые этим отношением.

В самом деле:

а) отношение Р – рефлексивно, поскольку любое х Î N 0 имеет при делении на 3 тот же остаток, что х ;

б) Р – симметрично, поскольку для любых х, у Î N 0 , если числа х и у у и х имеют один и и тот же остаток при делении на 3;

в) Р – транзитивно, поскольку для любых трех чисел x, y, z Î N 0, если х и у имеют один и тот же остаток при делении на 3, и у и z имеют один и тот же остаток при делении на 3, то числа х и z имеют один и тот же остаток при делении на 3.

Следовательно, отношение Р : «числа х и у имеют один и тот же остаток при делении на 3» является отношением эквивалентности, и поэтому оно разбивает множество N 0 на классы. Эти классы называются классами вычетов по модулю 3.

– так обозначается класс чисел, дающих при делении на 3 остаток 0, т.е. = {0, 3, 6, 9, 12 …}, или = {3k }, где k Î N 0 .

– так обозначается класс чисел, дающих при делении на 3 остаток 1, т.е. = {1, 4, 7, 10, 13 …}, или = {3k + 1};

– так обозначается класс чисел, дающих при делении на 3 остаток 2, т.е. = {2, 5, 8, 11, 14 …}, или = {3k + 2}.

Итак, отношение Р разбивает множество N 0 на 3 класса, и вообще, можно доказать, что отношение «числа х и у имеют один и тот же остаток при делении на m » разбивает это множество на m классов.

П р и м е р 2. На множестве N – натуральных чисел задано отношение Р следующим образом: (х 1 , у 1) Р (х 2 , у 2) .

Установим, что Р является отношением эквивалентности и определим классы эквивалентности, определяемые этим отношением.

Действительно, это отношение:

а) рефлексивно, поскольку для любых пар (х , у ) имеет место
ху = ух ;

б) симметрично, поскольку для любых двух пар натуральных чисел (х 1 , у 1) и (х 2 , у 2), если х 1 у 2 = у 1 х 2 , то х 2 у 1 = у 2 х 1 ;

в) транзитивно, поскольку для любых трех пар (х 1 , у 1), (х 2 , у 2), (х 3 , у 3), если х 1 у 2 = у 1 х 2 и х 2 у 3 = у 2 х 3 , то х 1 у 2 х 2 у 3 = у 1 х 2 у 2 х 3 , т.е. х 1 у 3 = у 1 х 3 .

Таким образом, отношение Р разбивает множество N на классы эквивалентности. Каждый из этих классов называется рациональным числом.

Например, пары (1, 2), (2, 4), (3, 6) принадлежат одному классу {(1, 2), (2, 4), (3, 6), …}. Можно этот класс определить следующим образом , т.е. как множество пар, эквивалентных паре (1, 2). Обычно эти пары записывают так: и называют дробями, а эквивалентность пар называют равенством дробей. Для упрощения заменяют класс эквивалентности каким-нибудь его элементом (представителем), чаще всего наиболее простым (несократимой дробью), называя его рациональным числом. Такое упрощение допустимо, так как рациональное число, как класс эквивалентности, однозначно определяется любым элементом этого класса, а операции над рациональными числами, как над классами пар, определяются через операции над представителями этих классов таким образом, что результаты этих операций не зависят от выбора представителей.

Как видно, дробь – форма выражения числа, при этом бесконечное множество дробей, составляющих один класс эквивалентности по отношению P на N , выражает одно число, которое может оказаться целым или дробным положительным числом, т.е. одно рациональное число.

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

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

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

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

Рефлексивность (англ. 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 задано отношение эквивалентности, то оно порождает разбиение этого множества на классы эквивалентности такое, что:

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

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

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

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