Условие
На множестве {0,1,…,11} задано отношение a~b, если 4 делит a−b. Докажите, что это эквивалентность, и найдите классы.
Решение по шагам
Рефлексивность: a−a=0 делится на 4. Симметричность: если a−b кратно 4, то b−a тоже кратно 4. Транзитивность: сумма a−b и b−c равна a−c и сохраняет кратность.
Классы определяются остатком: {0,4,8}, {1,5,9}, {2,6,10}, {3,7,11}. Любые два числа внутри одного класса связаны; числа из разных классов — нет.
Проверка результата
Каждый из 12 элементов входит ровно в один из четырёх классов, по три элемента в каждом. Проверка всех 144 упорядоченных пар совпадает со сравнением остатков.
Типичная ошибка
Один представитель класса не заменяет сам класс. Класс [1] здесь равен {1,5,9}, а не множеству всех целых чисел с остатком 1: исходное множество ограничено.
Что даёт этот метод
Любая эквивалентность задаёт разбиение множества, и любое разбиение задаёт эквивалентность. Остатки — наглядный пример фактор-множества.
Дальше по теме
Комбинаторика и дискретная математика: другие задачи и разборы.
Учебное условие и объяснение сформулированы редакцией damirock.com. Это самостоятельный разбор, а не официальный билет или ключ экзамена. Числа относятся к модели задачи.