85976 (612617), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Заметим, что класс эквивалентности, содержащий точку , есть проекция пересечения множества и прямой на ось ординат.

Сейчас мы приведем некоторые примеры множеств на плоскости, определяющих отношение эквивалентности.

1 Пример. (тривиальный). Множество вся плоскость. Выполнение свойств , , очевидно. Все точки исходной прямой отождествляются, т.е. входят в один класс эквивалентности.

Замечание. Для любого , если множество , определяющее отношение эквивалентности, содержит полосу , то оно совпадает со всей плоскостью. В самом деле, вместе с любой точкой множество содержит все внутренние точки квадрата с вершинами , , , , т.е. полосу . Ясно, что таким образом свойство "принадлежать " распространяется на все точки плоскости.

2 Пример. (периодичность). Возьмем которое число. Пусть множество состоит из прямых , где – произвольное целое число. Выполнение свойств и очевидно, и если , , то .

3 Пример. "Все константы равны единице, кроме нуля". (Такое утверждение высказал И.М. Гельфанд на одной из своих лекций.) В этом примере множество есть вся плоскость с выброшенными осями координат и добавленным началом координат. Иначе говоря, всегда, кроме случая , и ему симметричного. Если точки , принадлежат , то либо , и тогда , , либо , и тогда и . В обоих случаях .

4 Пример. (Все целые числа равны друг другу.) Множество состоит из главной диагонали и всех точек с целыми координатами.

Очевидно, можно рассматривать и конечные варианты такой эквивалентности типа

5 Пример. (Все числа, не большие единицы по модулю, равны друг другу.) Множество состоит из диагонали и замкнутого единичного квадрата. Очевидно, множество, состоящее из открытого (или полузамкнутого: ) квадрата, также дает эквивалентность.

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

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

2.1.1 Определение

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

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

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

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

2.1.2 Пример

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

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

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

2.1.3 Пример

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

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

2.1.4 Пример

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2.1 Лемма

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3.1 Определение

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

Характеристики

Список файлов курсовой работы