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