§ 5.1. Отношение эквивалентности

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

Пусть X — конечное или бесконечное множество. Отношением на X называется правило, по которому «сравниваются» его элементы. Это неформальное определение, но его вполне достаточно для наших целей. Заметим, что для определения отношения мы должны четко задать само множество; другими словами, нам должно быть ясно, какие элементы нужно сравнивать.

Рассмотрим несколько примеров. На множестве целых чисел есть много простых отношений, вроде «равно», «не равно», «меньше, чем», «меньше или равно». На множестве цветных мячей у нас есть отношение «тот же цвет». Последний пример, ввиду своей конкретности, хорош для запоминания в качестве модельного случая. Кстати, мы предполагаем, что каждый мяч из множества окрашен только в один цвет, пестрые мячи мы не рассматриваем.

Отношение эквивалентности — это отношение весьма специфичного вида. Возвращаясь к общим определениям, предположим, что X — множество, в котором было определено отношение. Удобно зафиксировать какой-нибудь символ для обозначения эквивалентности, обычно употребляют значок «~». С этого момента «~» будет отношением эквивалентности,

если для всех выполнены следующие свойства:

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

Второе свойство называется симметричностью. Отношение на множестве целых чисел не симметрично. Действительно, в то время как неравенство ложно. С другой стороны, отношение на рефлексивно, но не симметрично.

Третье — свойство транзитивности. На множестве целых чисел отношения «равно», «меньше, чем», «меньше или равно», — транзитивны. А вот «не равно» этим свойством не обладает. Действительно, и но из этих неравенств не следует Добавим, что симметрично, но не рефлексивно.

Мы предусмотрительно привели примеры отношений, которые не удовлетворяют этим свойствам, потому что это единственный путь к пониманию их действительного смысла. Именно владение примерами и контрпримерами обеспечивает успех в усвоении новых понятий. В примерах отношения эквивалентности нет недостатка. Равенство целых чисел, очевидно, удовлетворяет всем свойствам, выписанным выше. Отношение «тот же цвет» на множестве цветных мячей — еще один простой и, пожалуй, самый яркий пример. Среди примеров отношения эквивалентности на множестве многоугольников находятся такие отношения, как «одинаковое число сторон» и «одна и та же площадь».

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

Приведем простой пример. Обозначим символом М множество цветных мячей с отношением эквивалентности «тот же цвет». Класс эквивалентности красного мяча в М состоит из всех красных мячей, содержащихся в М.

Одно из свойств классов эквивалентности настолько важно, что мы назовем его основным принципом классов эквивалентности. Принцип гласит, что любой элемент класса эквивалентности — хороший представитель всего класса. Иначе говоря, зная один элемент из класса эквивалентности, можно немедленно восстановить этот класс полностью. Этот факт бросается в глаза, когда мы имеем дело с множеством М цветных мячей и отношением «тот же цвет». Предположим, Вам говорят, что в картонной коробке находятся все элементы одного класса эквивалентности множества М. Увидев один элемент из этого множества (допустим, это синий мяч), Вы немедленно заключаете, что в коробке лежит класс эквивалентности всех синих мячей М. Проще и быть не может!

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

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

Основной принцип приводит к важнейшему свойству отношения эквивалентности. Как и раньше, пусть X — множество с отношением эквивалентности тогда

(1) X — объединение своих классов эквивалентности относительно и

(2) два разных класса эквивалентности не могут иметь общего элемента.

Первое утверждение следует из часто упоминаемого факта: класс эквивалентности элемента содержит сам этот элемент. Для доказательства второго предположим, что элементы Так как то по основному принципу Аналогично Так что у. Заметим, что свойства (1) и (2) означают, что множество X разбито на непересекающиеся подмножества, классы эквивалентности. Другими словами, мы имеем дело с разбиением множества

Множество, составленное из классов эквивалентности множества X относительно отношения эквивалентности имеет специальное название: фактормножество X по отношению Отметим, что элементы фактормножества — это подмножества в Поэтому фактормножество не является подмножеством в X, будьте внимательны!

Закончим этот параграф примером, в котором проявляется наконец истинная природа дробей. Из чего состоит дробь? Когда Вы на нее смотрите, то видите два числа, одно из которых (знаменатель) должно быть ненулевым. Конечно, Вы ее, вероятно, воспринимаете как частное. Но если на Вас надавить, Вы можете попытаться выбрать более легкий выход и сказать, что дробь в действительности — пара чисел, одно из которых не равно нулю. Однако, такое определение некорректно.

В математике две пары равны, если они имеют одинаковые первый и второй элементы. Так, пары (2,4) и (1,2) неравны. Но дроби 2/4 и 1/2 равны; так что дроби — не пары чисел.

Что же такое дроби? Это элементы фактормножества! Рассмотрим множество пар целых На стандартном жаргоне Две пары и целых чисел можно теперь называть эквивалентными, если Легко проверить, что это отношение эквивалентности, а дробь — класс эквивалентности множества относительно этого отношения. Следовательно, означает не пару а бесконечное множество всех пар из эквивалентных Итак, множество рациональных чисел — это фактормножество множества по только что определенному отношению эквивалентности.

Представьте себе на минуту, что Вы до сих пор ничего о дробях не слышали и Вам придется исходить из описания, сделанного выше. Если Вам теперь скажут, что нужно вычислять с дробями, Вы почувствуете, что имеете вескую причину для паники: Вы же только что выучили, что дробь — это бесконечное множество. Мысль о прибавлении к одному бесконечному множеству другого бесконечного множества внушает легкое беспокойство. Именно в этот момент приходит на помощь основной принцип. Вам не нужно заботиться о бремени всего бесконечного множества; нужно знать только один элемент из него. Этот элемент расскажет Вам обо всем, что

необходимо знать о целом классе эквивалентности. Более того, Вас устроит любой элемент класса.

Итак, Вы можете оперировать с 1/2 как обычно, так же, как если бы это была пара чисел. Вы вспоминаете, что дробь — это класс эквивалентности, только когда (в процессе вычислений) оказывается, что дробь можно сократить. В этот момент вы заменяете одного представителя класса эквивалентности на другой для упрощения вычислений.

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