Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Отношение эквивалентности
Отношение эквивалентности является формализацией такой ситуации, когда говорят о сходстве двух элементов множества. Бинарное отношение R называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. Отношение эквивалентности xRy часто обозначается: х ~ у. Пример 1. Отношение «одного роста» есть отношение эквивалентности на множестве X людей. Рефлексивность. Каждый человек такого же роста, как он сам. Симметричность. Сидоров одного роста с Петровым тогда и только тогда, когда Петров одного роста с Сидоровым. Транзитивность. Если Сидоров одного роста с Петровым, а Петров одного роста с Ивановым, то Сидоров одного роста с Ивановым. Пример 2. Отношение обычного равенства на множестве целых чисел есть отношение эквивалентности. Пример 3. Отношение х < у на множестве действительных чисел не есть отношение эквивалентности, так как оно не рефлексивно, не симметрично, а лишь транзитивно. Если для бинарного отношения потребовать только выполнения свойств рефлексивности и симметричности, а транзитивности не требовать, то получим другой тип отношения. Оно называется отношением толерантности и является формализацией случая, когда два элемента множества не сходны, а только почти сходны (похожи). Подмножество [х] = {у X: у ~ х} называется классом эквивалентности, содержащим x (это множество всех элементов X, эквивалентных данному элементу x). Любой элемент у [x] называется представителем этого класса. Пример. Рассмотрим отношение принадлежности к одной студенческой группе. Классом эквивалентности является все множество студентов одной группы. Теорема 1. Пусть R — отношение эквивалентности на множестве X. Тогда: 1) для х X имеем х [x]; 2) если х, у X и xRy, то [х] = [у]. Другими словами, класс эквивалентности порождается любым своим элементом. Доказательство. Воспользуемся рефлексивностью отношения эквивалентности R, т. е. xRx. Следовательно, по определению, х [х]. Пусть z [у]. Тогда yRz, и в силу транзитивности отношения эквивалентности имеем: из xRy и yRz справедливо xRz, т. е. z [х]. Отсюда [у] [х]. Аналогично в силу симметричности R получаем [х] [у]. Следовательно, [х] = [у]. Теорема 2. Всякое отношение эквивалентности R определяет разбиение множества X на классы эквивалентности относительно этого отношения R. Теорема 3. Пусть задано разбиение множества X на попарно непересекающиеся подмножества. Тогда эти подмножества будут классами эквивалентности по некоторому отношению эквивалентности на X.
|