Отношения эквивалентности и толерантности и их свойства
Действительно,
пусть
и
.
Это значит, что
и
.
Следовательно,
,
т.е.
.
Из
свойств следует,
что всюду
определенное
соответствие
определяет
на
симметричное
и рефлексивное
отношение
,
т.е. толерантность.
2.2 Операции над толерантностями
Алгебраические свойства операций над толерантностями сравнительно просты.
2.2.1 Лемма
Если
– толерантность,
– эквивалентность
и
,
то
.
Доказательство
получается
применением
транзитивного
замыкания к
обеим частям
включения
.
Смысл
этой леммы в
том, что транзитивное
замыкание
отношения
толерантности
есть минимальная
эквивалентность,
включающая
эту толерантность.
Теорема.
Для того, чтобы
произведение
отношений
толерантности
и
было толерантностью,
необходимо
и достаточно,
чтобы
и
коммутировали.
В этом случае
.
Доказательство.
Симметрическое
произведение
толерантностей
и
всегда будет
толерантностью.
Симметричность
симметризованного
произведения
следует из
того, что:
.
Можно
ввести еще один
вариант симметризованного
произведения:
.
Легко показать,
что
будет толерантностью,
если
и
– толерантности.
Полезно
заметить, что
для любого
рефлексивного
отношения
отношения
будут толерантностями.
2.3 Классы толерантности
Изучим структуру пространств толерантности и попробуем различными способами представить, как устроены произвольные пространства толерантности. Общий результат состоит в том, что любое отношение толерантности может быть задано набором признаков так, что толерантные элементы – это те, которые имеют общие признаки.
Охарактеризуем
некоторую
совокупность
объектов признаками.
Возьмем множество
всех этих объектов
и множество
всех возможных
признаков.
Установим
теперь соответствие
,
сопоставляющее
каждому объекту
из
все те признаки,
которыми он
обладает. Наоборот,
любое соответствие
можно интерпретировать
как присвоение
некоторым
объектам (элементам
множества
)
некоторых
признаков
(элементов из
).
Строгое
понятие "соответствие"
позволяет
придать точный
смысл обиходному
выражению
"иметь признаки".
В
1
мы показали,
что всякое
всюду определенное
на
соответствие
задает на множестве
отношение
толерантности
,
определяемое
как совпадение
хотя бы одного
признака (наличие
общего признака).
Покажем, что любое отношение толерантности можно задать таким образом. Более того, существует некоторая каноническая совокупность признаков, которая строится по данному отношению толерантности независимо от способа его конкретного задания.
Отношение
толерантности
на множестве
может быть
определено
на языке покрытий.
(Система множеств
называется
покрытием
множества
,
если
.)
Пусть
– всюду определенное
соответствие.
Сопоставим
каждому "признаку"
множество
всех элементов
из
,
обладающих
признаком
,
т.е. множество
.
Система всех
множеств
образует покрытие
множества
,
поскольку любой
элемент
входит в некоторое
.
Легко видеть,
что
тогда и только
тогда, когда
существует
такой признак
,
что
и
.
Таким образом,
толерантность
может быть
задана так:
,
если
и
принадлежат
некоторому
общему классу
покрытия
.
Перейдем
к формальным
построениям.
Пусть задано
пространство
толерантности
.
2.3.1 Определение
Множество
называется
предклассом
в
,
если любые два
его элемента
и
толерантны,
т.е. для них
выполнено
соотношение:
.
Лемма.
Для того, чтобы
два элемента
и
были толерантны,
необходимо
и достаточно,
существовал
предкласс
,
содержащий
оба этих элемента.
Доказательство.
Если
и
лежат в предклассе
,
то по определению
2.3.1 предкласса
выполнено
соотношение
.
Если
,
то множество
само образует
предкласс, так
как, кроме исходного
соотношения,
выполнены также
соотношения
и
.
2.3.2 Определение
Множество
называется
классом толерантности
в
,
если
есть максимальный
предкласс.
Это
значит, что
любое множество
уже не является
предклассом.
Или, иначе,
,
не входящего
в
,
существует
элемент
,
не толерантный
к
.
Лемма.
Всякий предкласс
содержится
хотя бы в одном
классе
.
Доказательство.
Проведем его
лишь для случая,
когда само
множество
конечно. Пусть
– предкласс.
Если
– есть класс,
то лемма доказана.
Если
– не класс, то
в множестве
существует
элемент
,
толерантный
ко всякому
элементу из
.
Добавим такой
элемент
к
,
т.е. рассмотрим
множество
.
Тогда
и
снова является
предклассом.
Либо
– класс, либо
мы продолжаем
дальше этот
процесс расширения
предкласса
до класса. Поскольку
множество
конечно, то
через конечное
число шагов
наше построение
класса закончится.
Следствие.
Всякий элемент
содержится
в некотором
классе, т.е. система
классов толерантности
образует покрытие
множества
.
Действительно,
в силу рефлексивности,
и множество
,
состоящее из
одного элемента
,
образует предкласс.
2.3.3 Лемма
Для
того, чтобы два
элемента
и
были толерантны,
необходимо
и достаточно,
чтобы существовал
класс, содержащий
оба этих элемента.
Все подготовлено к тому, чтобы сформулировать и доказать основную классификационную теорему.
Теорема.
Пусть
– произвольное
пространство
толерантности,
а
– множество
всех его классов
толерантности.
Тогда существует
отображение
такое, что элементы
из
толерантны
в том и