Глава V. ТЕОРИЯ ВЫПУКЛЫХ МНОЖЕСТВ В ПРОСТРАНСТВАХ ЧАСТИЧНЫХ ПОРЯДКОВ И КВАЗИТРАНЗИТИВНЫХ ОТНОШЕНИЙ

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

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

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

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

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

Доказательство. Согласно известной теореме Шпильрайна (см., напр., [38]) элементы множества А могут быть занумерованы так, что из всегда следует, что Рассмотрим пары принадлежащие и не принадлежащие Пусть наибольший из индексов у таких пар. Положим а Среди индексов таких, что выберем наименьший Положим о. Очевидно,

Определим отношение на А следующим образом: Покажем, что частичный порядок. Очевидно, достаточно установить транзитивность Пусть Докажем, что и Если

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

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

Рис. 5.1.

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим структуру выпуклого множества, обладающего единственным максимальным элементом. В этом случае, как следует из изложенного, все точки множества X лежат между минимальным и единственным максимальным элементами. Обозначим через минимальный и максимальный элементы множества X соответственно. Очевидно, что Обозначим через мощность разности отношений т. е. Рассмотрим структуру множества всех отношений (не обязательно частичных порядков), лежащих между Каждое такое отношение получается добавлением к отношению некоторого подмножества из Тем самым множество всех отношений, лежащих между имеет ту же структуру, что и множество всех подмножеств Поскольку множество всех подмножеств естественным образом отождествляется с вершинами -мерного куба, то и множество всех отношений, лежащих между , имеет

ту же структуру. При этом отношения соответствуют противоположным вершинам такого куба.

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

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

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