Отношения эквивалентности и толерантности и их свойства
2.6.3 Теорема
Если
выполнено
соотношение:
,
то выполнено
и соотношение
,
т.е.
.
Доказательство.
Если
,
то совокупности
исходных признаков
и
,
выполненных
для
и
,
совпадают. Из
теоремы 2.6.1 вытекает,
что для каждого
класса толерантности
и
одновременно
содержатся
или не содержатся
в нем. Таким
образом,
и
имеют одинаковые
наборы канонических
признаков, т.е.
.
Теорема доказана.
Следующая теорема, принадлежащая С.М. Якубович, дает условия того, что некоторое множество является классом толерантности, т.е. того, что некоторый признак является каноническим.
2.6.4 Теорема
Пусть
имеется карта
.
Для, того чтобы
элемент покрытия
являлся классом
порожденной
толерантности
,
необходимо
и достаточно,
чтобы для любого
подмножества
,
из
следоаало бы
.
Доказательство.
Сначала предположим,
что множество
не является
классом толерантности.
Так как
является предклассом,
то единственная
причина, по
которой
может не быть
классом, состоит
в том, что существует
,
не входящий
в
и толерантный
ко всем элементам
.
Значит, для
всякого
существует
множество
,
содержащее
и
.
Таким образом,
множества
образуют покрытие
множества
.
Но все
содержат элемент
,
не входящий
в
.
Следовательно,
пересечение
не содержится
в
.
Итак, мы доказали
достаточность
условия, указанною
в теореме 2.6.4.
Докажем теперь
необходимость.
Пусть существует
такое подмножество
,
что
,
но
.
Значит, существует
элемент
,
не входящий
в
,
но входящий
во все
.
Этот элемент
толерантен
ко всем
.
Значит,
не является
максимальным
предклассом,
т.е. не является
классом толерантности.
Теорема доказана.
Рассмотрим еще так называемые сопряженные и производные пространства толерантности.
Пусть
– произвольное
пространство
толерантности,
и пусть
– некоторая
совокупность
классов толерантности.
Множество
естественным
образом превращается
в пространство
толерантности
при помощи
следующего
определения:
,
если
.
Определение.
Если
совпадает с
множеством
всех классов,
то пространство
называется
сопряженным
к
и обозначается
(таким образом,
).
Рассмотрим несколько примеров.
В
пространстве
элемент
,
содержащий
все числа, толерантен
ко всем элементам
и, стало быть,
входит во все
классы толерантности.
Значит, в пространствe
– полное отношение.
На
рис. 4 изображен
циклический
граф из 7 вершин.
Классами
толерантности
являются "ребра",
а толерантны
классы, соответствующие
смежным ребрам.
Ясно, что для
линейного графа
из
вершин сопряженным
является линейный
граф из
вершин.
На рис. 5 изображен циклический граф. Сопряженным к нему будет циклический граф из того же числа верин (если количество вершин исходного графа было больше трех).
На
рис. 6 изображено
пространство
толерантности
,
состоящее из
двух циклов,
зацепленных
в одной точке.
Сопряженное
пространство
состоит из
таких же циклов
с более сложным
зацеплением.
Но сопряженное
к последнему
пространство
по существу
совпадает с
исходным
пространством
.
Определение.
Пусть
– базис. Тогда
пространство
называется
сопряженным
к
,
относительно
данного базиса
.
Определение.
Второе сопряженное
пространство
относительно
некоторого
базиса
в
и базиса
в
называется
производным
от исходного
пространства
толерантности
.
Итак,
производное
пространство
толерантности
определяется
не однозначно,
а с точностью
до выбора базисов.
Этот произвол
исключается,
когда
и
имеют по единственному
базису.
Рассмотрим несколько примеров.
1.
Для линейного
графа с
вершинами
производное
пространство
также есть
линейный граф,
но с
вершинами (см.
рис. 4)
2.
Для циклического
графа с
вершинами
производное
пространство
"совпадает"
с исходным
пространством
(см. рис. 5).
3. Та же ситуация для зацепленных циклических графов (см. рис. 6).
4.
Для пространства
производное
пространство
состоит из
одного элемента.
2.6.5 Теорема
Если
– произвольное
пространство
толерантности,
а
– произвольный
базис в нем, то
существует
такой базис
в сопряженном
пространстве
и такое инъективное
отображение
,
что при
и
из
следует
.
Доказательство.
Обозначим через
множество
классов из
базиса
,
содержащих
.
Для любых классов
и
из
имеем
,
т.е.
.
Итак, множества
суть предклассы
в
.
Значит, для
всякого
существует
класс в
,
для которого
.
Зафиксируем
для каждого
некоторый класс
и множество
этих классов
обозначим через
.
Мы имеем сюръекцию
,
которое каждому
сопоставляет
класс
.
Покажем, что
содержит некоторый
базис
.
Действительно,
если
,
то существует
,
содержащийся
в