Парадигма развития науки. Методологическое обеспечение (стр. 65 )

Ни одна из точек, входящих в ядро, не «тяготеет» к какому-либо одному из исходных суждений. В этом смысле все точки ядра «равноправны». Очевидно, что они также удовлетворяют условию Парето. Исходя из этих свойств точки ядра признаются в геометрическом подходе допустимыми для поиска среди них групповых решений.

8. Теория выпуклых множеств в пространствах частичных порядков и квазитранзитивных отношений

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

8.1. Выпуклые множества в пространстве

Прежде всего мы установим полноту пространства Напомним, что точками этого пространства служат отношения час­тичного порядка на некотором конечном множестве А, т. е. ан­тирефлексивные и транзитивные бинарные отношения на А. Отношение частичного порядка всегда обладает свойством анти­симметричности. Очевидно, что пересечениедвух отноше­ний частичного порядка Р и Q снова является отношением час­тичного порядка. Напротив, их объединение вообще го­воря, уже не является отношением частичного порядка.

Для доказательства полноты необходимо проверить, что лю­бые соседние точки пространства различаются лишь на одно­элементном множестве. Пусть Р и Q — две соседние точки в Так как и, очевидно, то либо

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

Лемма 8.1. Если — две соседние точки в пространстве то для некоторой пары

Доказательство. Согласно теореме Шпильрайна элементы множества А могут быть за­нумерованы так, что из всегда следует, чтоРас­смотрим пары (аі, аj), принадлежащие Q и не принадлежащие Пусть і0 — наибольший из индексов i у таких пар. ПоложимСреди индексов j таких, что выберем наименьший j0. Положим Очевидно,

Определим отношение R на А следующим образом:

Покажем, что R — частичный порядок. Очевидно, достаточно установить транзитивность R. Пусть Докажем, что и Если

то так как Q транзитивно. Предположим, что

Тогда Пусть у=аk. Тогда имеем

Так как то по определению j0. Следовательно, Так как то по определению i0. Следовательно, Р. Отсюда в силу транзитивности Р имеемчто противоречит тому, что Полученное противо­речие завершает доказатель­ство.

Для случая небольших кардинальных чисел множе­ства А (п = 2, 3) простран­ство можно изобразить графически в виде обычной диаграммы Хассе. Опуская тривиальный случай п = 2, мы приведем эту диаграмму для случая, когда А состоит из трех элементов: А =

На рис. 8.1 стрелки ука­зывают вложение частичных порядков, рассматриваемых как подмножества в

Рис. 8.1.

Буквой обозначен тривиальный частичный порядок, совпадаю­щий с пустым подмножеством. Рис. 8.1 является хорошей иллюст­рацией к лемме 8.1: соседние точки на нем — это в точности те, которые соединены стрелками.

Из леммы 8.1 непосредственно следует, что справедлива

Теорема 8.1. Пространство является полным пространством.

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

Изучим теперь подробнее структуру выпуклых множеств в пространстве Пусть X — выпуклое множество в пространстве . Тогда на X также определено отношение частичного по­рядка из

Опишем подробнее структуру частичного порядка на X.

Лемма 8.2. В выпуклом множестве X имеется единственный минимальный элемент.

Доказательство. Пусть Р и Q — два различных мини­мальных элемента из X. Частичный порядок лежит между Р и Q и, следовательно,С другой стороны, R со­держится в Р и Q, но не совпадает с ними, что противоречит минимальности Р и Q.

Множество X является выпуклой оболочкой множества, со­стоящего из минимального элемента и всех максимальных эле­ментов, так как любой элемент множества X лежит между ми­нимальным и некоторым максимальным элементом. Максималь­ных элементов в множестве X может быть несколько. Таким об­разом, выпуклая оболочка множества X полностью определяется минимальными и максимальными элементами. Мы будем го­ворить, что выпуклое множество X порождается подмножеством X', если В рассматриваемом случае выпуклое множество X порождается подмножеством, состоящим из минималь­ного и всех максимальных элементов.