Эквивалентность
На основании перечисленных выше свойств отношения можно разбить на отдельные группы, произвести их классификацию.
Определение 16. Эквивалентностью называют отношения, которые одновременно рефлексивны, симметричны и транзитивны, т.е.
(
эквивалентность)
Таким образом, к эквивалентностям относятся такие отношения: «быть однополчанином», «быть членом той же партии, что и …», «быть тезкой», «быть единомышленником», «быть одной веры с …», «иметь тот же остаток при делении на 5», «и много, много других.
Отношение эквивалентности тесно связано с разбиением множества . Эту связь отражает следующая теорема.
Теорема 4. Задание отношения эквивалентности на конечном множестве равносильно разбиению этого множества.
Доказательство. Необходимость. Пусть на конечном множестве задано отношение эквивалентности с областью истинности . Проведем следующее построение.
Выберем
некоторый элемент
и построим подмножество
из всех элементов, эквивалентных
,
т.е.
.
Из множества
удалим все элементы, содержащиеся в
подмножестве
.
Получим множество
.
Если
,
то построение завершено. В противном
случае снова выберем некоторый элемент
и, построив подмножество
,
удалим его из
,
получая множество
.
Процесс нашего построения будет завершен,
как только будет получено пустое
множество
,
а результатом этого построения станет
совокупность
подмножеств
,
,
…,
,
которая, согласно нашему построению,
будет удовлетворять следующим условиям:
Следовательно,
данное множество {
,
,
…,
}
подмножеств множества
(согласно определению разбиения) есть
разбиение последнего. Необходимость
доказана.
Достаточность.
Пусть теперь задано разбиение {
,
,
…,
}
множества
.
Рассмотрим на нем отношение «принадлежать
одному и тому же подмножеству». Данное
отношение рефлексивно (любой элемент
принадлежит тому же подмножеству, в
котором сам и находится), симметрично
(если
принадлежит тому же подмножеству, что
и
,
то и
принадлежит тому же подмножеству, что
и
)
и, наконец, транзитивно (если
принадлежит тому же подмножеству, что
и
,
а
принадлежит тому же подмножеству, что
и
,
то
принадлежит тому же подмножеству, что
и
).
Следовательно, данное отношение есть
эквивалентность. Теорема доказана.
Замечание 1. Данная теорема легко распространяется на случай бесконечного множества . При этом алгоритм построения, описанный в первой части доказательства, будет работать сколь угодно долго, формируя конечное или бесконечное множество { , , …, , …}.
Замечание
2. Формируемые
при работе описанного выше алгоритма
подмножества
,
,
…,
называют классами
эквивалентности.
Например, отношение «иметь тот же остаток
при делении на 5» разобьет множество
натуральных чисел на такие пять классов
эквивалентности:
класс
чисел, кратных пяти (числа, остаток
которых при делении на 5 равен нулю);
класс чисел с остатком при делении на
5, равным 1;
класс чисел с остатком при делении на
5, равным 2;
класс чисел с остатком, равным 3;
класс чисел с остатком, равным 4. Классами
эквивалентности отношения «иметь то
же социальное происхождение» будут
социальные группы: рабочие, служащие,
крестьяне и т.д.
Замечание
3. Непересекаемость
классов эквивалентности (т.е. условие
)
обеспечивает непротиворечивость деления
множества
на классы (каждый элемент принадлежит
не более чем одному классу), а условие
говорит о полноте системы этих классов
(любой элемент из
принадлежит
какому-либо классу).
Замечание 4. Данная теорема имеет применение не только в математических науках. Любая научная теория так или иначе, связана с классификацией объектов, составляющих область ее исследований. Для успешного осуществления этой классификации необходимо найти отношение эквивалентности между объектами. Если будет найдено отношение, которое одновременно рефлексивно, симметрично и транзитивно, то оно определит непротиворечивую и полную классификацию изучаемого разнообразия.
Представляет определенный интерес рассмотреть последствия, к которым приводит отсутствие свойства транзитивности в рефлексивных и симметричных отношениях.
Вопросы для самоконтроля
Какие отношения из нижеследующих являются эквивалентностью? а) «быть того же цвета»; б) «быть кратным тому же числу»; в) «иметь тот же наибольший общий делитель»; г) «иметь хотя бы одно общее свойство».
Для приведенных выше отношений эквивалентности определите их классы эквивалентности.