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

Определения, примеры, свойства

Определение

Отношение  на множестве  называется толерантностью или отношением толерантности, если оно рефлексивно и симметрично.

Пример. Множество  состоит из четырехбуквенных русских слов – нарицательных существительных в именительном падеже. Будем называть такие слова сходными, если они отличаются не более чем на одну букву. Известная задача "Превращение мухи в слона" в точных терминах формулируется так:

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

Приведем решение этой задачи: Муха – мура – тура – тара – кара – каре – кафе – кафр – каюр – каюк – крюк – крок – срок – сток – стон – слон.

Пример

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

Множество  называется -мерным симплексом. Это понятие обобщает понятия отрезка, треугольника и тетраэдра на многомерный случай. Числа  интерпретируются как вершины симплекса. Двухэлементные подмножества – как ребра, трехэлементные как плоские грани, -элементные подмножества – как -мерные грани. Толерантность граней симплекса  означает их геометрическую инцидентность – наличие общих вершин. Число всех элементов из  равно .

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

Пример

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

Пространство  играет роль "универсального" пространства толерантности.

Пример

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

Существует еще один способ задания отношений толерантности. Рассмотрим соответствие . Множество всех образов элемента  при соответствии  мы обозначим . Отношение  на множестве  задается условием: , если у элементов  и  существует образ, т.е. если .

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

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

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

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

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

Если на элементе  отношение  не рефлексивно (не выполняется  или ), то соотношение  не выполнено ни для какого , так как .

Если соответствие  является функцией, т.е.  состоит не более чем из одного элемента (в этом случае  равносильно ), то отношение  транзитивно.

Действительно, пусть  и . Это значит, что  и . Следовательно, , т.е. .

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