Дискретная математика. Множества. Отображения. Отношения

60 ным характеристикам . Такими отношениями являются отношения эквивалентности . Если на множестве A задана эквивалентность R , то каждый элемент a A ∈ множества является представителем некоторого класса эквивалентности ( | ) a R и действия над элементами множе - ства A можно трансформировать в действия над классами эквива - лентности , при этом элементы одного класса отождествляются , хотя они и различны . Поэтому эквивалентности можно назвать обобщенными или ослабленными тождествами . Пример 5.9. Рассмотрим множество A студентов в данной аудитории . Введем отношение R : , ( x y A x R y x ∀ ∈ ↔ сидит в од - ном ряду с ) y . Это отношение рефлексивно , симметрично и тран - зитивно , т . е . является эквивалентностью . Оно разбивает все мно - жество A на подмножества студентов , сидящих в одном ряду и можно перейти к работе по рядам . В этом случае ( например , при выдаче контрольных заданий ) всем студентам достаточно выдать число заданий , равное числу рядов в аудитории . Справедлива теорема обратная к теореме 5.1. Теорема 5.2. Любое разбиение { : } A B β β∈ множества A на непустые классы определяет некоторую эквивалентность R на мно - жестве A . Доказательство . Определим отношение R в виде ( ) 0 0 , : , a b A aR b B a b A β β ∀ ∈ ↔ ∃ ∈ ∈ . (5.26) Здесь R – признак принадлежности элементов одному классу раз - биения . Докажем , что R является эквивалентностью , т . е . рефлексив - но , симметрично и транзитивно . Рефлексивность . По определению разбиения очевидно : 0 0 ( ) a A A a A β β ∀ ∈ ∃ ∈ . Следовательно , a AaRa ∀ ∈ . Рефлексивность отношения R доказана .