Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Теорема. Всякое отношение эквивалентности на множестве А определяет некоторое разбиение множества А на подмножества






Всякое отношение эквивалентности на множестве А определяет некоторое разбиение множества А на подмножества, и обратно, всякое разбиение множества, определяет отношение эквивалентности на множестве А.

 

Доказательство

1) Пусть Е – отношение эквивалентности на множестве А, тогда А/Е фактор множество множества А по отношению Е.

Так как в силу рефлексивности Е , то каждое из множеств А/Е не пусто и .

Чтобы установить, что А/Е – разбиение множества А остается установить, что если .

Пусть и , то есть .

Так как отношение Е – симметрично, то

в силу транзитивности, если

и , то

еще раз используем свойство транзитивности, если

и , то и .

То есть . Включение доказывается аналогично.

2) Предположим, что Е отношение на множестве А, соответствующее разбиению R={Ai}. Покажем рефлексивность, симметричность и транзитивность отношения Е, задав его следующим образом:

- рефлексивность

, следовательно существует i, такое что , отсюда и . Значит .

- симметричность

значит существует i, такое что и , следовательно существует i, такое что и . Отсюда .

- транзитивность

, значит существует i, такое что и и существует j, такое что и , то есть и , но система классов не пересекается, следовательно i=j. Отсюда .






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.