Дискретная математика

23 Теорема 1.8. Каждое разбиение множества А порождает отношение эквивалентности на множестве А, причем различные разбиения порождают различные отношения эквивалентности. Доказательство. Пусть дано разбиение 5={Б,} множества А. Определим отношение R: (a,b)eR тогда и только тогда, когда существует В, такое, что а и Ь оба принадлежат этому В/. Очевидно, что введенное отношение является рефлексивным, симметричным и транзитивньш, следовательно, R - отношение эквивалентности. Можно показать, что если разбиения различны, то и отношения эквивалентности, ими порождаемые, тоже различны. Совокупность всех классов смежности множества А по данному отношению эквивалентности R называется фактор-множеством и обозначается через A/R. Элементами фактор-множества являются классы смежности. Класс смежности [а]ц, как известно, состоит из элементов А, которые находятся между собой в отношении R. Рассмотрим пример отношения эквивалентности на множестве целых чисел Z= {..., -3, -2, -1, О, 1, 2, 3, Два целых числа а и Ь называют сравнимыми (конгруэнтными) по модулю т, если т делитель числа а-Ь, т. е. если имеем: а=Ь+кт, к=..., -3, -2, -1,0, 1, 2, 3, .... В этом случае записывают a=b(mod т). Теорема 1.9. Для любых чисел а, Ь,си т>0 имеем: \) а =a(modт)', 2)&сша ^b(modm),TO b =a(modm)', 3) если а sb(modт) шЬ sc(mod т), то а =c(modт). Доказательство. Утверждения 1) и 2) очевидны. Докажем 3). Пусть a=b+kim, Ь=с+к2т, тогда a=c+(Ici+k2)m, т.е. а = c(modm). Теорема доказана. Таким образом, отношение сравнимости по модулю т является отношением эквивалентности и делит множество целых чисел на непересекающиеся классы чисел. Построим бесконечно раскручивающуюся спираль, которая на рис. 1.13 изображена сплошной линией, и бесконечно скручивающуюся спираль, изображенную штриховой линией. Пусть задано целое неотрицательное числот . Все целые числа (элементы из множества 2) расположим в точках пересечения этих спиралей с т лучами, как показано на рис. 1.13. Для отношения сравнимости по модулю т (в частности и для т~%) класс эквивалентности - это числа, лежащие на луче. Очевидно, что каждое число попадает в один и только один класс. Можно получить, что для т=8 имеем: