§ 5.2. Сравнения

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

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

фиксировано. Оно называется периодом, или модулем отношения, которое мы собираемся определить.

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

Приведем несколько числовых примеров. Для модуля

Выберем другой модуль, скажем в этом случае

Заметим, что числа, сравнимые по некоторому модулю, не обязательно сравнимы по другому модулю. Так, 21 сравнимо с 1 по модулю 5; но эти числа не сравнимы по модулю 7, потому что разность не кратна 7.

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

Следующим идет свойство симметричности. Пусть для некоторых целых справедливо сравнение Это означает, что для какого-то целого к. Умножая это равенство на —1, получаем

что также кратно Поэтому и мы доказали, что сравнение по модулю симметрично.

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

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

Пусть Класс о образован всеми целыми для которых а кратно т. е. для некоторого к Таким образом, класс эквивалентности числа о описывается формулой:

Заметим, что 0 состоит из всех чисел, кратных и каждый класс эквивалентности — бесконечное множество.

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

Следовательно, разность кратна Поэтому Число называется вычетом а по модулю

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

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

Это все очень хорошо, но кажется довольно абстрактным. Хорошо бы иметь наглядную геометрическую картинку, изображающую множество Вспомним геометрическое изображение множества Большинство людей представляют себе целые числа как точки, равномерно расположенные вдоль прямой линии. Где-то на этой прямой стоит точка, изображающая О, так что отрицательные целые числа находятся слева от нее, а положительные — справа. Сравнение по модулю отождествляет между собой все числа, отличающиеся на и поэтому, подходя к мы должны вернуться опять к 0.

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