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

22 Отношение нестрогого неравенства (<) на множестве действительных чисел не будет отношением эквивалентноста, ибо не является симметричным; из Ъ £ 5 не следует, что Классом эквивалентности (классом смежности), порожденным элементом а при данном отношении эквивалентности R, называется подмножество тех хеА, которые находятся в отношении R с а. Указанный класс эквивалентности обозначается через [ O J R , следовательно, имеем: [а]я—{х £ Л: (а,х) sR]. Рассмотрим пример. На множестве треугольников введено отношение подобия. Ясно, что все равносторонние треугольники попадают в один смежный класс, ибо каждый из них подобен, например, треугольнику, все стороны которого имеют единичную длину, 1" " Теорема 1.6. Пусть Л - отношение эквивалентности на множестве А и [a]i( смежный класс, т.е. [а]ц={х sA:(a,x} £R}, 1 огд.гч 1) для любого аеА; [а]ц7^0, в частности, ае[а]ц; 2) различные смежные классы не пересекаются; 3) объединение всех смежных классов совпадает со всем множеством Л; 4) совокупность различных смежных luiaccoB образуют разбиение множества А. Доказательство. I) В силу рефлексивности R получим, что для любого а, аеА. имеем (a.a)eR, следовательно А а [ а ] м ^ 0 ; 2) допустим, что [a]i^ п [Ь]ц ^ 0, т.е. существует элемент с т А я се[а]цп [Ь]п. Тогда из (cRa)&(cRb) в силу симметричности R получаем, что (aRc)&(cRb), а из транзитивности R имеем aRb. Для любого Л" имеем: (xRa)&(aRb), тогда в силу транзитивности R получим xRb, т.е. хе[Ь]л, поэтому [а]п с [Ь]ц. Аналогично для любого у, у £ [Ь]ц, имеем: (yRb)&(aRb), а в силу симметри^шости R получим, что l'yRb)&(bRa), затем, в силу транзитивности Л, получим, чтоyRa, т.е.. уе[а]а^ поэтому [b]iiC [a ]R. Из [а ]нс [Ь ]к иP ^ J r s M r получаем [а]к = [bjn, т. е. если смежные классы пересекаются, то они совпадают; 3) для любого а, аеА, как доказано, имеем де/о/л, тогда, очепндно, что обьединение всех смежных классов совпадет с множеством /]. Утверладение 4) теоремы 1.6 следует из 1)-3). Теорема доказана. 1Можно доказать следующую теорему. Теорема 1.7. Различные огношения 'эквивалентности на множестве А порождают различные разбиения А.