КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Система представителейЭквивалентность. Классы эквивалентности ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ Отношение эквивалентности удовлетворяет условиям рефлексивности, симметрич-ности, транзитивности и обычно обозначается знаком ~. При этом х ~ у означает, что упорядоченная пара (х, у) принадлежит множеству , являющимся отношением эквивалентностив множестве М. Свойства эквивалентности записываются следующим образом: 1) х ~ х (рефлексивность); 2) х~у Þ у ~ х (симметричность); 3) х~у Ù у ~ z Þ х ~ z (транзитивность). Классом эквивалентности [ х ] элемента х называется множество всех эквивалентных ему элементов ([ x ]={ y: y~x }). Теорема. Классы эквивалентности различных элементов не пересекаются. Доказательство. Рассмотрим два произвольных не эквивалентных друг другу элемента х и у. Предположим, что их классы эквивалентности пересекаются. [ x ]Ç[ y ]¹Æ Þ $ z: z Î[ x ]Ç[ y ] Þ z Î[ x ] Ù z Î[ y ] Þ х ~ z Ù у ~ z Þ х~у – противоречие. Следовательно, различные классы эквивалентности не пересекаются. Таким образом, отношение эквивалентности разбивает множество М на непересекающиеся классы эквивалентности. Наоборот, всякое разбиение множества М на непересекающиеся подмножества определяет между элементами этого множества некоторое отношение эквивалентности. Все элементы, принадлежащие некоторому классу Мi разбиения множества М, связаны отношением эквивалентности. Они взаимозаменяемые в том смысле, что любой из этих элементов определяет данный класс, т. е. может служить его представителем (эталоном). Подмножество из М, содержащее по одному и только по одному элементу из каждого класса некоторого разбиения, называют системой представителей соответствующего отношения эквивалентности. Множество всех классов разбиения множества М, определяемого отношением эквивалентности А, образует фактор-множество М/А. Например, отношение параллельности определяет разбиение множества прямых на плоскости на классы, каждый из которых образован множеством параллельных между собой прямых и характеризуется некоторым направлением (следует также считать, что прямая параллельна самой себе). Любая из параллельных прямых может служить представителем данного класса, а само направление есть класс эквивалентности. Множество всех направлений составляет фактор-множество множества всех прямых по отношению параллельности. 4.3. Классы вычетов по модулю т. Рассмотрим отношение сравнения но модулю т на множестве натуральных чисел, что записывается как х=у (mod т) и означает: х сравнимо с у по модулю т (т - целое положительное число, не равное нулю), если х-у делится на т. Целые числа, сравнимые по модулю т, связаны соотношением х = у + km (k - целое число) и образуют подмножество целых чисел, имеющих одинаковый остаток при делении на т. Так как эти подмножества не пересекаются, они являются классами эквивалентности, а в качестве представителя каждого из них естественно выбрать остаток j = 0, 1, 2,..., т- 1. Таким образом, отношение сравнения по модулю т определяет разбиение множества натуральных чисел на т классов , где — счетное множество, называемое классом вычетов по модулю т. пример. при т =4 имеем М 0={0, 4, 8, 12,...}; М 1={1, 5, 9, 13,...}, M 2 = {2, 6, 10, 14,...}, М 3={3, 7, 11, 15,...}. Представителями классов эквивалентности являются числа 0, 1, 2 и 3, так как 0 = 4(mod4) = 8(mod4) =...; 1 = 5(mod4) = 9(mod4) =...; 2 = 6(mod 4) = 10(mod 4) =...и 3=7(mod4) = 11(mod 4) =.... Таким образом, множество целых чисел разбивается отношением сравнения по модулю 4 на четыре класса эквивалентности. Внутри каждого класса эти числа неразличимы (4 ~ 0, 5 ~ 1, 6 ~ 2, 7 ~ 3 и т. д.). При т = 1 разбиение состоит из единственного класса, который совпадает с исходным множеством, т. е. имеем полное отношение эквивалентности, при котором любые два элемента эквивалентны (все целые числа делятся на единицу). Отношение х = у (mod 2) разбивает множество целых чисел на классы четных и нечетных чисел.
Дата добавления: 2014-01-13; Просмотров: 480; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |