§ 4.2. Выпуклые множества и выпуклые оболочки

Наличие понятия «между» в пространстве предпочтений позволяет ввести естественное понятие выпуклого множества. Соответственно тому, что у нас имеется два определения «между», мы дадим два определения выпуклости.

Определение 4.4. Множество X точек пространства называется выпуклым, если вместе с любыми двумя точками оно содержит любую точку, лежащую между ними.

Используя наши обозначения, можно сказать, что множество X выпукло, если из следует, что

Определение 4.5. Множество точек пространства называется выпуклым, если из следует, что

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

Исследуем связь между двумя определениями выпуклости. Следующее утверждение непосредственно вытекает из леммы 4.1.

Лемма 4.3. Из выпуклости в смысле определения 4.5 следует выпуклость в смысле определения 4.4 для любого пространства бинарных отношений

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

Условие полноты. Для любых двух соседних точек пространства симметрическая разность есть одноэлементное множество.

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

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

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

Лемма 4.4. Для полного пространства из выпуклости в смысле определения 4.4 следует выпуклость в смысле определения 4.5.

Доказательство. Пусть множество, выпуклое в смысле определения 4.4, т. е. вместе с любыми двумя точками из X содержит все точки, лежащие между ними. Пусть й Рассмотрим линейный сегмент между (выбор точки произволен). Предположим, что Поскольку то в линейном сегменте между найдутся две последовательные точки такие, что Так как точки соседние, то возможны два случая: или для некоторой пары Рассмотрим эти случаи отдельно.

1. . Так как по определению линейного сегмента, то откуда Так как . Отсюда для некоторого Покажем, что Действительно, так как Далее, так как

Итак, что противоречит выпуклости.

2. . Так как по определению линейного сегмента, то откуда Так как то Г) Отсюда найдется номер такой, что Покажем, что Действительно, так как Далее, так как Итак, Но а что противоречит выпуклости

Полученные противоречия показывают, что что и требовалось доказать.

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

Теорема 4.2. Для полного пространства оба определения выпуклости эквивалентны.

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

Пусть теперь X — произвольное множество в пространстве бинарных отношений

Определение 4.6. Выпуклой оболочкой множества X в пространстве называется наименьшее выпуклое множество, содержащее X (понимая выпуклость в смысле определений 4.4 или 4.5).

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

Наличие двух определений выпуклости и соответственно — двух вариантов выпуклой оболочки позволяет дать два способа построения выпуклой оболочки. Используем сначала определение Для данного множества X обозначим через X множество, полученное добавлением к X всех точек, лежащих между парами точек из Введем обозначения: Очевидно, что Так как число точек в пространстве конечно, то последовательность вложенных множеств стабилизируется, т. е. найдется номер такой, что

Лемма 4.5. В предыдущих обозначениях для любого пространства

Доказательство. Пусть Имеем Но по определению Итак,

выпуклое множество. Пусть выпуклое в смысле определения 4.4 множество и Очевидно, что для всех

В частности, откуда следует, что минимальное выпуклое множество, содержащее

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

Лемма 4.6. Для полного пространства

Доказательство. Согласно лемме 4.1 X — выпуклое множество в смысле определения 4.5. С другой стороны, если выпуклое множество, то в силу определения 4.5. Отсюда следует утверждение леммы.

Лемма 4.7. Пусть X — подмножество в произвольном пространстве Тогда

Доказательство. Следует непосредственно из следствия -к лемме 4.1, леммы 4.5 и леммы 4.6.

Теорема 4.3. Для произвольного подмножества X в полном пространстве бинарных отношений

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

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