Смекни!
smekni.com

Отношения эквивалентности и толерантности и их свойства (стр. 7 из 20)

Лемма. Для того чтобы

, необходимо и достаточно, чтобы каждый
-класс содеожался в некотором
-классе.

Действительно, если

, то из
следует
. Зчачит, множество всех
,
-эквивалентных элементу
, содержится во множестве всех
,
-эквивалентных этому
. Обратный вывод столь же очевиден.

Для того чтобы

необходимо и достаточно, чтобы каждый
-класс
содержал любой
-класс
, имеющий с
непустое пересечение.

Для доказательства необходимости выберем произвольный элемент

. По предыдущей лемме
целиком содержится в некотором классе
. Но если бы
был бы отличен от
, то элемент
был бы сразу в двух классах
-разбиения, что невозможно. Значит,
. Для доказательства достаточности нужно только вспомнить, что из
по условию вытекает
, и применить лемму 1.3.1.

Для того чтобы эквивалентности

и
были когерентными, необходимо и достаточно, чтобы всякий
-класс
либо содержался в некотором
-классе
, либо целиком содержал любой
-класс
, имеющий с
непустое пересечение.

Доказательство. Eсли

и
когерентны, то
,
и на
, имеем
, а на
. Тогда по лемме 1.3.1 для каждого класса
, содержащегося в
, существует такой класс
, что
. По лемме 1.3.2 каждый класс
, содержащийся в
, целиком содержит любой класс
, имеющий с
непустое пересечение. Поскольку
и
не пересекаются, из вытекает, что всякий класс эквивалентности
содержится либо в
, либо в
; значит, наше рассуждение охватывает все классы.

Проведем доказательство в обратную сторону. Пусть каждый класс

обладает сформулированным в лемме 1.2.3 свойством. Обозначим через
объединение всех тех классов
, для которых существует такой
, что
, а через
– объединение остальных классов
. Ясно, что
,
и
,
, где
и
– сужения отношений
и
на
. Наконец, очевидно, что
и
, т.е.
и
когерентны.

Теперь мы подготовили все необходимое для доказательства теоремы 1.3.1. Будем вести доказательство от противного, т.е. предположим, что

и
не когерентны. Тогда по лемме 1.3.3 существует класс
и класс
такиее, что
, но не один из них не содержит другой. Значит, существуетвует
, существует
, существует
. Имеем следующие соотношения:
и
, следовательно,
и
. По транзитивности должно было бы быть также
. Однако, соотношения:
и
– оба не выполнены, так как
не лежит с
ни в общем
-классе, ни в общем
-классе. Значит, соотношение
не выполнено. Полученное противоречие доказывает теорему.