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

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

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

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

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

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

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

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

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

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

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

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

2.3.3 Лемма

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

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

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

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

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

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

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

2.4 Классы толерантности в некоторых конкретных пространствах толерантности

Рассмотрим пространство . Это пространство толерантности состоит из множеств номеров вида , где все , причем элементы и толерантны, если они содержат общий номер.

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

2.4.1 Лемма

Множество является классом толерантности.

Так как состоит из всех множеств вида , то число элементов множества равно – число всех подмножеств множества из оставшихся номеров.

Найденных классов достаточно, чтобы задать толерантность в .

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

Определение. Совокупность классов в пространстве толерантности называется базисом, если:

1) для всякой толерантной пары и существует класс , содержащий оба этих элемента: ;

2) удаление из хотя бы одного класса приводит к потере этого свойства, т.е. существует толерантная пара , , для которой является единственным общим классом толерантности в .

Замечание. Произвольная система классов толерантности, обладающая свойством 1) из определения 2.4.1, содержит базис. Чтобы выделить этот базис, достаточно последовательно удалить "лишние" классы. В качестве исходной системы можно выбрать все множество классов. Отсюда следует существование базиса в любом пространстве толерантности.

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

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

Выше было показано, что в пространстве толерантности набор классов образует базис, не совпадающий с совокупностью всех классов.

Установим одно простое свойство всех классов толерантности в .

2.4.2 Лемма

Если – класс толерантности в , содержащий элемент , то .

Доказательство. Действительно, все элементы, толерантные к , обязаны содержать номер в своем наборе. Значит, . Но есть класс, т.е. по определению не может целиком содержаться в другом классе. Значит, .

2.4.3 Лемма

В пространстве существует единственный базис: .

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

В силу определения базиса толерантность в можно задать только признаками, соответствующими базисным классам .

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

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

2.5 Связь отношений эквивалентности и толерантности

Когда отношение толерантности оказывается транзитивным, т.е. превращается в свой частный случай – в отношение эквивалентности, то классы толерантности превращакугся в классы эквивалентности. Так как классы эквивалентности не пересекаются, справедлива

Лемма. Отношение толерантности янлнигся отношением эквивалентности тогда и только тогда, когда классы толерантности не пересекаются друг с другом.

Вернемся теперь к изучению отображения , построенного в процессе доказательства теоремы 2.3.1 и выясним, какие элементы из имеют одинаковый образ при отображении , т.е. отчего бывает не инъективным.

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

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

Ядра – это прообразы при отображении . Действительно, ядро состоит из всех тex элементов , для которых образ есть именно это множество классов толерантности: . Отсюда ясно, что непустые ядра образуют разбиение, множества и тем самым задают отношение эквивалентности. Мы попробуем разобраться, как это отношение связано с исходной толерантностью.

Пусть задано пространство толерантности , Далее мы будем обозначать через множество всех элементов, толерантных к . Отношение на определим условием

2323()

Иначе говоря, означает, что и толерантны к одним идем же элементам.

Лемма. Для того чтобы выполнялось соотношение , необходимо и достаточно, чтобы и лежали в одном и том же ядре .

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

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