Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Теорема. Всякое отношение эквивалентности на множестве А определяет некоторое разбиение множества А на подмножества
|
|
Всякое отношение эквивалентности на множестве А определяет некоторое разбиение множества А на подмножества, и обратно, всякое разбиение множества, определяет отношение эквивалентности на множестве А.
Доказательство
1) Пусть Е – отношение эквивалентности на множестве А, тогда А/Е фактор множество множества А по отношению Е.
Так как в силу рефлексивности Е 
, то каждое из множеств А/Е не пусто и 
.
Чтобы установить, что А/Е – разбиение множества А остается установить, что если 
.
Пусть 
и 
, то есть 
.
Так как отношение Е – симметрично, то
в силу транзитивности, если
и 
, то 
еще раз используем свойство транзитивности, если
и , то 
и 
.
То есть 
. Включение 
доказывается аналогично.
2) Предположим, что Е отношение на множестве А, соответствующее разбиению R={Ai}. Покажем рефлексивность, симметричность и транзитивность отношения Е, задав его следующим образом:
- рефлексивность
, следовательно 
существует i, такое что 
, отсюда и . Значит 
.
- симметричность
значит существует i, такое что и 
, следовательно существует i, такое что и . Отсюда 
.
- транзитивность
, 
значит существует i, такое что и и существует j, такое что 
и 
, то есть и , но система классов не пересекается, следовательно i=j. Отсюда 
.
|
|