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

Установим основные свойства отношения

:

Отношение

всегда симметрично.

Это следует из того, что

.

Отношение

рефлексивно тогда и только тогда, когда соответствие

определено на всем

.

В самом деле, в этом и только в этом случае множество

.

Если на элементе

отношение

не рефлексивно (не выполняется

или

), то соотношение

не выполнено ни для какого

, так как

.

Если соответствие

является функцией, т.е.

состоит не более чем из одного элемента (в этом случае

равносильно

), то отношение

транзитивно.

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

и . Это значит, что и . Следовательно, , т.е. .

Из свойств следует, что всюду определенное соответствие

определяет на симметричное и рефлексивное отношение , т.е. толерантность.

2.2 Операции над толерантностями

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

2.2.1 Лемма

Если

– толерантность,

– эквивалентность и

, то

.

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

.

Смысл этой леммы в том, что транзитивное замыкание

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

Теорема. Для того, чтобы произведение

отношений толерантности

и

было толерантностью, необходимо и достаточно, чтобы

и

коммутировали. В этом случае

.

Доказательство. Симметрическое произведение

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

Можно ввести еще один вариант симметризованного произведения:

. Легко показать, что будет толерантностью, если и – толерантности.

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

отношения будут толерантностями.

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

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

Охарактеризуем некоторую совокупность объектов признаками. Возьмем множество

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

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

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

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

Отношение толерантности

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

Пусть

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