Дальнейшее исследование структуры толерантностей
Рассмотрим множество и его покрытие . Пару мы будем далее называть картой. Произвольная карта позволяет ввести на множестве отношение толерантности , определенное условием: , если существует такое , что одновременно и . Так определенную толерантность мы назовем толерантностью, порожденную картон . Очевидно, каждое является предклассом порожденной толерантности . Если – пространство толерантности и – множество всех классов толерантности в этом пространстве, то, в силу леммы 2.3.3 толерантность, порожденная картой , совпадает с исходной толерантностью . Аналогичное утверждение справедливо и для произвольного базиса в пространстве . Карта называется канонической, если каждый элемент покрытия оказывается классом толерантности, порожденной исходной картон . Легко видеть, что если карта является канонической, то содержит некоторый базис , порожденный толерантности: . На рис. 1 изображена некоторая карта , а справа система классов порожденной толерантности (впрочем, в данном случае эта система состоит из одного класса). Этот пример показывает, в частности, существование неканонических карт. Каждая карта естественным образом приводит к всюду определенному соответствию
которое каждому элементу сопоставляет все те , для которых . Наоборот, если дано некоторое всюду определенное соответствие , то оно порождает покрытие множества , состоящее из прообразов элементов из при соответствии . Таким образом, тогда и только тогда, когда существует такое , что есть множество элементов из , которым соответствие сопоставляет . Обозначим для дальнейшего прообраз элемента при соответствии через . По соответствию можно построить отображение,
которое каждому элементу сопоставляет непустое множество элементов , для которых . С помощью отображении толерантность , порожденная исходной картой , выражается условием , если . Можно ввести еще и отношение , определяемое условием: , если . , очевидно, является эквивалентностью. Посмотрим на примерах, как канонические признаки выражаются через исходные признаки карты. В примере на рис. 1 Имеем . В примере на рис. 2а, изображено соответствие: , где , . Нa рис. 2б изображены классы порожденной толерантности. Легко проверить, что , . На рис 3 исходная карта уже является канонической. Но если взять каноническую карту с полным набором классов толерантности, то получим, что . Посмотрим далее, каким образом и всегда ли канонические признаки могут быть выражены через исходные. Теорема Для произвольной карты любой класс порожденной толерантности всегда может быть выражен через элементы покрытия с помощью операций пересечения и объединения. Доказательство. Рассмотрим некоторый класс толерантности . Пусть . По определению класса, для всякого , , а по определению толераптности существует признак такой, что . Тогда 1) ; 2) . Действительно, 1) следует из того, что для всех признаков , a 2) следует из того, что всякий , принадленжащий , толерантен к . Поскольку – произвольный элемент из , по свойству максимальности класса . Отсюда вытекает, что , что доказывает теорему. Подчеркнем, что канонические признаки оправляются через исходные без перехода к дополнениям. О связи между исходными и каноническими признаками говорит также.
Теорема Существует такой базис классов порожденной толерантности, что каждый из классов этого базиса содержит некоторое множество . Доказательство. По определению толерантности в для всякого любая пара и толерантна. Значит, есть предкласс. Тогда по лемме 2.3.2 получается существует класс . Выберем для каждого один из классов . Очевидно, выбранная совокупность классов удовлетворяет условию 1) из определения 1.4.1. Значит, она содержит некоторый базис . Следствие. Когда конечно, то существует базис классов толерантности, число классов в котором не превышает количества исходных признаков. Рассмотрим исходную карту и полученную из нее каноническую карту , где – базис. Как уже было отмечено, отношения толерантности, издаваемые на множестве обьектов обеими картами, совпадают. Несколько иначе обстоит дело с отношением эквивалентности , задаваемым на с помощью определения, приведенного в начале параграфа. Пусть – отношение эквивалентности, заданное исходным множеством признаков , а – отношение эквивалентности, заданное по . Как показывает пример на рис. 1, отношения и могут и не совпадать. В общем, случае справедлива Теорема Если выполнено соотношение: , то выполнено и соотношение , т.е. . Доказательство. Если , то совокупности исходных признаков и , выполненных для и , совпадают. Из теоремы 2.6.1 вытекает, что для каждого класса толерантности и одновременно содержатся или не содержатся в нем. Таким образом, и имеют одинаковые наборы канонических признаков, т.е. . Теорема доказана. Следующая теорема, принадлежащая С.М. Якубович, дает условия того, что некоторое множество является классом толерантности, т.е. того, что некоторый признак является каноническим. Теорема Пусть имеется карта . Для, того чтобы элемент покрытия являлся классом порожденной толерантности , необходимо и достаточно, чтобы для любого подмножества , из следоаало бы . Доказательство. Сначала предположим, что множество не является классом толерантности. Так как является предклассом, то единственная причина, по которой может не быть классом, состоит в том, что существует , не входящий в и толерантный ко всем элементам . Значит, для всякого существует множество , содержащее и . Таким образом, множества образуют покрытие множества . Но все содержат элемент , не входящий в . Следовательно, пересечение не содержится в . Итак, мы доказали достаточность условия, указанною в теореме 2.6.4. Докажем теперь необходимость. Пусть существует такое подмножество , что , но . Значит, существует элемент , не входящий в , но входящий во все . Этот элемент толерантен ко всем . Значит, не является максимальным предклассом, т.е. не является классом толерантности. Теорема доказана. Рассмотрим еще так называемые сопряженные и производные пространства толерантности. Пусть – произвольное пространство толерантности, и пусть – некоторая совокупность классов толерантности. Множество естественным образом превращается в пространство толерантности при помощи следующего определения: , если . Определение. Если совпадает с множеством всех классов, то пространство называется сопряженным к и обозначается (таким образом, ). Рассмотрим несколько примеров. В пространстве элемент , содержащий все числа, толерантен ко всем элементам и, стало быть, входит во все классы толерантности. Значит, в пространствe – полное отношение. На рис. 4 изображен циклический граф из 7 вершин. Классами толерантности являются "ребра", а толерантны классы, соответствующие смежным ребрам. Ясно, что для линейного графа из вершин сопряженным является линейный граф из вершин. На рис. 5 изображен циклический граф. Сопряженным к нему будет циклический граф из того же числа верин (если количество вершин исходного графа было больше трех). На рис. 6 изображено пространство толерантности , состоящее из двух циклов, зацепленных в одной точке. Сопряженное пространство состоит из таких же циклов с более сложным зацеплением. Но сопряженное к последнему пространство по существу совпадает с исходным пространством . Определение. Пусть – базис. Тогда пространство называется сопряженным к , относительно данного базиса . Определение. Второе сопряженное пространство относительно некоторого базиса в и базиса в называется производным от исходного пространства толерантности . Итак, производное пространство толерантности определяется не однозначно, а с точностью до выбора базисов. Этот произвол исключается, когда и имеют по единственному базису. Рассмотрим несколько примеров. 1. Для линейного графа с вершинами производное пространство также есть линейный граф, но с вершинами (см. рис. 4) 2. Для циклического графа с вершинами производное пространство "совпадает" с исходным пространством (см. рис. 5). 3. Та же ситуация для зацепленных циклических графов (см. рис. 6). 4. Для пространства производное пространство состоит из одного элемента.
Теорема Если – произвольное пространство толерантности, а – произвольный базис в нем, то существует такой базис в сопряженном пространстве и такое инъективное отображение , что при и из следует . Доказательство. Обозначим через множество классов из базиса , содержащих . Для любых классов и из имеем , т.е. . Итак, множества суть предклассы в . Значит, для всякого существует класс в , для которого . Зафиксируем для каждого некоторый класс и множество этих классов обозначим через . Мы имеем сюръекцию , которое каждому сопоставляет класс . Покажем, что содержит некоторый базис . Действительно, если , то существует , содержащийся в и . Тогда и содержаться в , а значит, и . Теперь для каждого выберем ровно один элемент , для которого . Множество таких элементов обозначим через . Ясно, что и возникающая при этом сюръекция на инъективно. Тогда обратное к нему отображение инъективно отображает на подмножество множества . Поэтому его можно рассматривать как инъективное (но уже в общем случае не сюръективное) отображение. Пусть теперь и, где и и . Тогда существует класс , содержащий и . Значит, . Но из и следует, что , т.е. . Теорема доказана.
Популярное: Как построить свою речь (словесное оформление):
При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою... Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (200)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |