Математика · объяснение и практика

Когда отношение делит множество на непересекающиеся классы

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

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

В теме Множества, отношения и математическая логика · Учебная карта

В маршруте Множества, отношения и мощности · 10 тем

Главная мысль

Рефлексивное, симметричное и транзитивное отношение объединяет элементы в классы эквивалентности. Два таких класса либо не пересекаются, либо полностью совпадают.

Почему одного сходства недостаточно

Можно назвать два целых числа связанными, когда они дают одинаковый остаток при делении на пять. Каждое число связано с собой. Если первое связано со вторым, то и второе связано с первым. Наконец, совпадение остатка у первого и второго, а затем у второго и третьего означает совпадение у первого и третьего.

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

Один представитель, целый класс

Класс числа a состоит из всех чисел, связанных с a. Для одинаковых остатков по модулю пять классы можно представить остатками 0,1,2,3,4. Например, числа 2,7,−3 принадлежат одному классу. Представитель не обязан быть самым маленьким: в этом бесконечном классе минимального целого элемента вообще нет.

Если классы a и b имеют общий элемент c, то a связано с c, а c — с b; после симметрии и транзитивности получаем связь a с b. Любой элемент класса a поэтому связан с b и входит в его класс. Обратное включение доказывается так же. Значит классы не могут пересекаться лишь частично.

Пример

На множестве {1,2,3,4,5,6,7,8} числа эквивалентны при одинаковом остатке по модулю три. Какие классы получаются?

Получаем {1,4,7}, {2,5,8}, {3,6}. Каждый исходный элемент находится ровно в одном классе; повторный выбор представителя 4 вместо 1 не создаёт нового класса.

Что даёт переход к классам

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

Проверка трёх свойств нужна до подсчёта классов. Рефлексивность гарантирует присутствие каждого элемента в собственном классе, симметрия устраняет направление связи, а транзитивность не даёт двум группам пересекаться кусочком. Можно начать и с готового разбиения: объявить связанными элементы одной группы. Тогда все свойства выполняются, и два описания одной структуры согласуются.

От чтения к действию

А теперь — вы

На целых числах задано aRb тогда и только тогда, когда |a−b|≤1. Какого свойства эквивалентности не хватает?

Частые вопросы

Всегда ли одинаковый класс означает равные элементы?

Нет. Класс хранит лишь выбранный общий признак, например остаток; разные числа могут оказаться эквивалентными.

Может ли представитель принадлежать двум разным классам?

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

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться