Отношения эквивалентности и толерантности и их свойства
Лемма.
Для того чтобы
,
необходимо
и достаточно,
чтобы каждый
-класс
содеожался
в некотором
-классе.
Действительно,
если
,
то из
следует
.
Зчачит, множество
всех
,
-эквивалентных
элементу
,
содержится
во множестве
всех
,
-эквивалентных
этому
.
Обратный вывод
столь же очевиден.
Для
того чтобы
необходимо
и достаточно,
чтобы каждый
-класс
содержал любой
-класс
,
имеющий с
непустое пересечение.
Для
доказательства
необходимости
выберем произвольный
элемент
.
По предыдущей
лемме
целиком содержится
в некотором
классе
.
Но если бы
был бы отличен
от
,
то элемент
был бы сразу
в двух классах
-разбиения,
что невозможно.
Значит,
.
Для доказательства
достаточности
нужно только
вспомнить, что
из
по условию
вытекает
,
и применить
лемму 1.3.1.
Для
того чтобы
эквивалентности
и
были когерентными,
необходимо
и достаточно,
чтобы всякий
-класс
либо содержался
в некотором
-классе
,
либо целиком
содержал любой
-класс
,
имеющий с
непустое пересечение.
Доказательство.
Eсли
и
когерентны,
то
,
и на
,
имеем
,
а на
.
Тогда по лемме
1.3.1 для каждого
класса
,
содержащегося
в
,
существует
такой класс
,
что
.
По лемме 1.3.2 каждый
класс
,
содержащийся
в
,
целиком содержит
любой класс
,
имеющий с
непустое пересечение.
Поскольку
и
не пересекаются,
из Error: Reference source not found вытекает,
что всякий
класс эквивалентности
содержится
либо в
,
либо в
;
значит, наше
рассуждение
охватывает
все классы.
Проведем
доказательство
в обратную
сторону. Пусть
каждый класс
обладает
сформулированным
в лемме 1.2.3 свойством.
Обозначим через
объединение
всех тех классов
,
для которых
существует
такой
,
что
,
а через
– объединение
остальных
классов
.
Ясно, что
,
и
,
,
где
и
– сужения отношений
и
на
.
Наконец, очевидно,
что
и
,
т.е.
и
когерентны.
Теперь
мы подготовили
все необходимое
для доказательства
теоремы 1.3.1. Будем
вести доказательство
от противного,
т.е. предположим,
что
и
не когерентны.
Тогда по лемме
1.3.3 существует
класс
и класс
такиее, что
,
но не один из
них не содержит
другой. Значит,
существуетвует
,
существует
,
существует
.
Имеем следующие
соотношения:
и
,
следовательно,
и
.
По транзитивности
должно было
бы быть также
.
Однако, соотношения:
и
– оба не выполнены,
так как
не лежит с
ни в общем
-классе,
ни в общем
-классе.
Значит, соотношение
не выполнено.
Полученное
противоречие
доказывает
теорему.
Замечание.
Понятие когерентности
имеет смысл
для любых отношений
и
.
Но для эквивалентностей
когерентность
отношений
и
легко формулируется
в терминах
классов эквивалентности
(лемма 1.3.3).
1.3.4 Лемма
Если
и
рефлексивны,
то
26
Доказательство.
Если
,
то, в силу
,
выполнено и
соотношение
,
т.е.
.
Аналогично
получается
.
Из этих двух
включений
следует Error: Reference source not found.
Теорема.
Для того чтобы
объединение
эквивалентностей
и
само было отношением
эквивалентности,
необходимо
и достаточно,
чтобы
26
Доказательство.
Пусть
– эквивалентность.
По лемме 1.3.4 выполняется
Error: Reference source not found. Для
доказательства
Error: Reference source not found остается
доказать
26
Пусть
.
Тогда для некоторого
имеем
и