Введение

Математическое понятие для сравнения объектов – математическое понятие.

В математике, отношение эквивалентности — это бинарное отношение, которое является рефлексивным, симметричным и транзитивным. Отношение эквиполлентности между отрезками в геометрии является распространенным примером отношения эквивалентности. Более простой пример — равенство. Любое число равно самому себе (рефлексивность). Если a = b, то b = a (симметричность). Если a = b и b = c, то a = c (транзитивность). Каждое отношение эквивалентности задает разбиение базового множества на непересекающиеся классы эквивалентности. Два элемента данного множества эквивалентны друг другу тогда и только тогда, когда они принадлежат одному и тому же классу эквивалентности.

Обозначение

В литературе используются различные обозначения для указания того, что два элемента *a* и *b* множества эквивалентны относительно отношения эквивалентности *R*. Наиболее распространенными являются "" и "a ≡ b", которые используются, когда *R* подразумевается, и вариации "", "a ≡R b" или "" для явного указания *R*. Неэквивалентность может быть записана как "a ≁ b" или "".

Определение

Двоичное отношение на множестве называется отношением эквивалентности, если и только если оно рефлексивно, симметрично и транзитивно. То есть, для всех x и y из (рефлексивность). если и только если (симметрия). Если x и y связаны отношением , то и y и x связаны отношением (транзитивность). Множество вместе с отношением называется сетоидом. Класс эквивалентности элемента x по отношению , обозначаемый , определяется как

Альтернативное определение с использованием реляционной алгебры

В реляционной алгебре, если R и S – отношения, то составное отношение R∘S определяется так, что (x, y) ∈ R∘S тогда и только тогда, когда существует z такое, что (x, z) ∈ R и (z, y) ∈ S. Это определение является обобщением определения функциональной композиции. Определяющие свойства отношения эквивалентности R на множестве A могут быть переформулированы следующим образом:
(рефлексивность). (Здесь, id обозначает функцию идентичности на A.) (симметричность). (транзитивность).

Простой пример

На множестве отношение является отношением эквивалентности. Следующие множества являются классами эквивалентности этого отношения:

Множество всех классов эквивалентности для — это . Это множество является разбиением множества относительно .

Сопутствующие важные определения

Пусть , и являются отношением эквивалентности. Далее следуют некоторые ключевые определения и терминология:

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

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

Набор коэффициентов

Множество всех классов эквивалентности, обозначаемое как , является фактормножеством по отношению к . Если является топологическим пространством, существует естественный способ преобразования в топологическое пространство; подробности см. в статье "Факторпространство".

Ядро эквивалентности

Ядро эквивалентности функции — это отношение эквивалентности ~, определяемое соотношением. Ядро эквивалентности инъекции — это отношение тождества.

Разделение

Разбиение множества X — это набор P непустых подмножеств X, такой, что каждый элемент X принадлежит ровно одному подмножеству из P. Каждый элемент P называется ячейкой разбиения. Кроме того, элементы P попарно не пересекаются, и их объединение равно X.

Подсчет перегородок

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

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

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

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

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

Алгебраическая структура

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

Решетки

Отношения эквивалентности на любом множестве X, упорядоченные по включению, образуют полную решетку, обозначаемую Con X по соглашению. Каноническое отображение ker : X^X → Con X связывает моноид X^X всех функций на X и Con X. Отображение ker сюръективно, но не инъективно. Неформально, отношение эквивалентности ker на X сопоставляет каждой функции f : X → X её ядро ker f. Аналогично, ker(ker) является отношением эквивалентности на X^X.