Алгебраические свойства операций над толерантностями сравнительно просты.

Лемма

Если  – толерантность,  – эквивалентность и , то .

Доказательство получается применением транзитивного замыкания к обеим частям включения .

Смысл этой леммы в том, что транзитивное замыкание  отношения толерантности  есть минимальная эквивалентность, включающая эту толерантность.

Теорема. Для того, чтобы произведение  отношений толерантности  и  было толерантностью, необходимо и достаточно, чтобы  и  коммутировали. В этом случае .

Доказательство. Симметрическое произведение  толерантностей  и  всегда будет толерантностью. Симметричность симметризованного произведения  следует из того, что: .

Можно ввести еще один вариант симметризованного произведения: . Легко показать, что  будет толерантностью, если  и  – толерантности.

Полезно заметить, что для любого рефлексивного отношения  отношения  будут толерантностями.

Классы толерантности

Изучим структуру пространств толерантности и попробуем различными способами представить, как устроены произвольные пространства толерантности. Общий результат состоит в том, что любое отношение толерантности может быть задано набором признаков так, что толерантные элементы – это те, которые имеют общие признаки.

Охарактеризуем некоторую совокупность объектов признаками. Возьмем множество  всех этих объектов и множество  всех возможных признаков. Установим теперь соответствие , сопоставляющее каждому объекту из  все те признаки, которыми он обладает. Наоборот, любое соответствие  можно интерпретировать как присвоение некоторым объектам (элементам множества ) некоторых признаков (элементов из ).

Строгое понятие "соответствие" позволяет придать точный смысл обиходному выражению "иметь признаки". В 1 мы показали, что всякое всюду определенное на  соответствие  задает на множестве  отношение толерантности , определяемое как совпадение хотя бы одного признака (наличие общего признака).

Покажем, что любое отношение толерантности можно задать таким образом. Более того, существует некоторая каноническая совокупность признаков, которая строится по данному отношению толерантности независимо от способа его конкретного задания.

Отношение толерантности  на множестве  может быть определено на языке покрытий. (Система множеств  называется покрытием множества , если .)

Пусть  – всюду определенное соответствие. Сопоставим каждому "признаку"  множество  всех элементов из , обладающих признаком , т.е. множество . Система всех множеств  образует покрытие множества , поскольку любой элемент  входит в некоторое . Легко видеть, что  тогда и только тогда, когда существует такой признак , что  и . Таким образом, толерантность  может быть задана так: , если  и  принадлежат некоторому общему классу покрытия .

Перейдем к формальным построениям. Пусть задано пространство толерантности .

Определение

Множество  называется предклассом в , если любые два его элемента  и  толерантны, т.е. для них выполнено соотношение: .

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

Доказательство. Если  и  лежат в предклассе , то по определению 2.3.1 предкласса выполнено соотношение . Если , то множество  само образует предкласс, так как, кроме исходного соотношения, выполнены также соотношения  и .

Определение

Множество  называется классом толерантности в , если  есть максимальный предкласс.

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

Лемма. Всякий предкласс содержится хотя бы в одном классе .

Доказательство. Проведем его лишь для случая, когда само множество  конечно. Пусть  – предкласс. Если  – есть класс, то лемма доказана. Если  – не класс, то в множестве  существует элемент , толерантный ко всякому элементу из . Добавим такой элемент  к , т.е. рассмотрим множество . Тогда  и  снова является предклассом. Либо  – класс, либо мы продолжаем дальше этот процесс расширения предкласса до класса. Поскольку множество  конечно, то через конечное число шагов наше построение класса закончится.

Следствие. Всякий элемент  содержится в некотором классе, т.е. система классов толерантности образует покрытие множества .

Действительно, в силу рефлексивности,  и множество , состоящее из одного элемента , образует предкласс.

Лемма

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

Все подготовлено к тому, чтобы сформулировать и доказать основную классификационную теорему.

Теорема. Пусть  – произвольное пространство толерантности, а  – множество всех его классов толерантности. Тогда существует отображение  такое, что элементы из  толерантны в том и только в том случае, когда толерантны их образы в .

Доказательство. Выберем в качестве  отображение, которое каждому элементу  сопоставляет множество , состоящее из всех содержащих его классов. По следствию из леммы 2.3.2 . По лемме 2.3.3 отношение  выполнено в том и только в том случае, когда , т.е.  и  содержат общий класс.

Если  – конечно, то количество всех его подмножеств конечно и поэтому конечно пространство . Поэтому вместо отображения  можно взять отображение , где  – число классов толерантности в , которое каждому элементу  сопоставляет множество номеров, содержащих его классов:  (здесь ).

Толерантность элементов  и  означает, что среди номеров, сопоставленных элементам  и  согласно , есть хотя бы один общий. Т.е.  и  имеют общий числовой признак. Рассмотрим всюду определенное соответствие , которое каждому  сопоставляет все классы, в которые он входит. Из леммы 2.3.3 следует, что  равносильно тому, что у  и y  имеется общий образ в .

(Л. Кальмар – С. Якубович) Теорема. Произвольное отношение толерантности  на множестве  можно задать как отношение  с помощью некоторого всюду определенного соответствия .