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

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

отношение эквивалентности — бинарное отношение между элементами данного множества, свойства которого сходны со свойствами отношения равенства.

Определение

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

1. рефлексивность: ;
2. симметричность: если , то ;
3. транзитивность: если и , то .

Запись вида «» читается как « эквивалентно ».

Отношение эквивалентности представляет собой строгое матема­тическое определение таких обыденных понятий как «одинаковость» или «неразличимость».

Обозначается X~Y. Отношение эквивалентности А в множестве М означает, что упорядоченная пара (X, Y) принадлежит множеству А Ì М´М.

Отношение эквивалентности обладает свойствами:

· Рефлексивности: X~Y;

· Симметричности: если X~Y, то Y~X;

· Транзитивности: если X~Y и Y~Z, то X~Z.

Важнейшее значение эквивалентности состоит в том, что это отношение определяет признак, который допускает разбиение множества М на непересекающиеся подмножества, называемые Клас­Сами эквивалентности. И наоборот: всякое разбиение множества М на непересекающиеся подмножества определяет между элементами этого множества некоторое отношение эквивалентности.

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

Все элементы, принадлежащие некоторому классу МI разбиения {М1, М2,..., МN} множества М на классы эквивалентности, связаны отношением эквивалентности. Любой из этих элементов определяет данный класс и может служить его Представителем или Эталоном.

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

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

Рассмотрим матрицу отношения эквивалентности.

Элементы, принадлежащие некоторому классу эквивалентности, попарно эквивалентны между собой, а их сечения совпадают. Сле­довательно, столбцы матрицы отношения эквивалентности для элемен­тов одного класса одинаковы и содержат «1» во всех строках, которые соответствуют этим элементам. Так как классы эквивалентности не пересекаются, то в столбцах различных классов не будет единиц в одинаковых строках. Если расположить элементы множества так, чтобы в каждом классе эквивалентности принадлежащие ему элементы стояли рядом, то единичные элементы матрицы образуют непересекаю­щиеся квадраты, диагонали которых располагаются на главной диагонали матрицы.

Например: Пусть множество М разбито на классы эквивалент­ности следующим образом:

М1 = {Х1, х2, х3}; М2 = {Х4}; М3 = {Х5, х6, х7, х8}.

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

Предположим, Например, что мы хотим разбить точки плоскости на классы, относя две точки к одному классу в том, и только в том случае, когда расстояние между ними меньше 1. Об этом говорит сайт https://intellect.icu . Пусть расстояние от точки А до точки Bменьше 1, и расстояние от B До С тоже меньше 1. Тогда, относя А в один класс с B, а B в один класс с С , мы должны отнести С в один класс с А. Но расстояние от А до С может быть и больше 1. Следовательно, такой признак не позволяет разбить мно­жество на классы эквивалентности. Это объясняется тем, что для него не выполняется свойство транзитивности: если А ~ B, а B ~ С, то А ~ С. Таким образом, можно определить отношение эквивалентности как бинарное отношение, для которого выполняются свойства рефлексив­ности, симметричности и транзитивности.

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

Пример: на множестве из 6-ти ниже приведенных графов



построим граф, соответствующий отношению эквивалентности.

Решение:

т.к. отношение эквивалентности на множестве объектов есть совокупность трех свойств – рефлективности, симметричности и транзитивности, то имеем:



Здесь: М₁М={σ₁,σ₂,σ₃,σ₄,σ₅,σ₆}, М_i – множество попарно изолированных графов, т.е. М₁={ σ₁,σ₂,σ₅}. Аналогично М₂М и М₂={ σ₃,σ₄}, М₃М и М₃={ σ₆}. Итак, отношением эквивалентности множество М из 6-ти графов разбивается на три непересекающихся подмножества изоморфных графов М₁М₂=Ø, М₁М₃=Ø, М₂М₃=Ø, M₁M₂M₃=M.

Иллюстративные примеры отношений эквивалентности

Связанные определения

Классом эквивалентности элемента называется подмножество элементов, эквивалентных ; то есть,

.

Из вышеприведенного определения немедленно следует, что если , то .

Фактормножество — множество всех классов эквивалентности заданного множества по заданному отношению , обозначается .

Для класса эквивалентности элемента используются следующие обозначения: , , .

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

Примеры

• Равенство («»), тривиальное отношение эквивалентности на любом множестве, в частности, вещественных чисел.
• Сравнение по модулю: а ≡ b (mod n).
• В евклидовой геометрии
  • Отношение конгруэнтности («»).
  • Отношение подобия («»).
  • Отношение параллельности прямых («») (но только если дополнительно к принятому определению считать каждую прямую параллельной самой себе).
• Эквивалентность функций в математическом анализе:

  Говорят, что функция эквивалентна функции при , если она допускает представление вида , где при . В этом случае пишут , напоминая при необходимости, что речь идет о сравнении функций при . Если при , эквивалентность функций и при , очевидно, равносильна соотношению .

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

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

Множество всех классов эквивалентности, отвечающее отношению эквивалентности , обозначается символом и называется фактормножеством относительно . При этом сюръективное отображение

называется естественным отображением (или канонической проекцией) на фактормножество .

Пусть и — множества, — отображение, тогда бинарное отношение , определенное правилом

,

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

или, что то же самое,

.

При этом получается факторизация отображения на сюръективное отображение и инъективное отображение .

Вау!! 😲 Ты еще не читал? Это зря!

• Отношение толерантности — ослабленная форма эквивалентности.
• Отношение порядка отношение порядка ,
• бинарное отношение , биекция , сюръекция , инъекция ,
• отношение строгого порядка , отношение не строгого порядка ,
• Эквиваленция — логическая операция .
• Знак равенства.

Надеюсь, эта статья про отношение эквивалентности, была вам полезна, счастья и удачи в ваших начинаниях! Надеюсь, что теперь ты понял что такое отношение эквивалентности и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика.