Бинарные отношения и система преимуществ ЛПР.

Упорядоченные множества и их свойства. Аксиома выбора Цермело.Основные результаты теории упорядоченных множеств позволяются обосновать процедуры преобразования и модификации систем преимуществ ЛПР. Одна из интереснейших аксиом теории множеств, которая непосредственно связанна с принятием решений, является аксиома выбора.

Аксиома выбора. Если Х – объединение не пустых множеств X_i, которые не пересекаются, то существует как минимум одно подмножество , пересечение которой с каждым множеством X_i являются одноэлементными множествами.

Аксиома выбора Цермело. Для каждого множества Х непустых множеств X_i iÎI, существует функция

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

Элемент xÎA, где А – множество носитель отношения R, называется максимумом отношения R, если , то есть отношение xRy выполняется для всех элементов множества носителя А.

Элемент xÎA где А – множество носитель отношения R, называется минимумом отношения R, если , то есть отношение yRx выполняется для всех элементов множества носителя А.

Элемент xÎA где А – множество носитель отношения R, называется мажорантой отношения R, если , где - дополнение к R, то есть отношение y x выполняется для всех элементов множества носителя А.

Элемент xÎA где А – множество носитель отношения R, называется минорантой отношения R, если , где - дополнение к R, то есть отношение x y выполняется для всех элементов множества носителя А.

Множество называется упорядоченным по отношению строгого порядка (транзитивным и асимметричным), если оно является носителем этого отношения строгого порядкаD,DÍA´A.

Упорядоченное множество обозначается двойкой . Элемент yÎA называется мажорантой подмножества XÌA, если y является мажорантой для сужения D на X. Упорядоченное множество называется индуктивным, если каждое подмножество Х имеет мажоранту.

Лемма Куратовского-Цорна. В индуктивном упорядоченном множестве для каждого элемента существует мажоранта.

Бинарное отношение Р совместимо с строгим порядком D, если отношение Р D может быть включено в некоторое отношение строгого порядка с носителем А.

Теорема о совместимости. Пусть D – отношение строгого порядка, Р – бинарное отношение (все эти отношения с носителем А), и элементы пар (x,y) ÎР являются элементами подмножества XÌA. Если Р совместимо с строгим порядком, которое является сужением D на X, то Р совместимо со строгим порядком D.

Следствие теоремы о совместимости. В упорядоченном множестве всех отношений строгого порядка с носителем А мажорантами являются линейные отношения строгого порядка и только они.

Теорема Шпильрайна. Для произвольного отношения строгого порядка D с носителем А найдется такое линейное отношение строгого порядка R с носителем А, что D R. Другими словами каждый строгий порядок можно продолжить до линейного строгого порядка.

Произвольное линейное упорядоченное подмножество упорядоченного множества может быть продолжено до линейного упорядочивания упорядоченного множества в целом.(стр64)

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

Интерпретацией теоремы Шпильрайна является интерпретация с помощью понятия нумерации. Нумерацией n-элементного упорядоченного множества А, n=card(A), которая является носителем отношения строгого порядка D, называется взаимнооднозначное (изоморфное) отображение множества А в множество N={1,2,…,n}, при этом «лучшему» или «большему» элементу xÎA, чем yÎA (xDy) соответствует большее значение iÎN.

Удобным и наглядным способом отображения упорядоченного множества является диаграмма Гасе. На диаграмме каждый элемент изображается точкой на плоскости, и если y доминирует над x, то точки x и y соединяют отрезком, при этом точка, которая соответствует x, размещается ниже чем y. Диаграмма Гасе строится следующим образом: элементы множества А изображаются точками на плоскасти, при этом для x,y ÎP, которые xPy, точка которая отвечает x находится выше точкиy и эти точки соединяются между собой отрезком.

(пример диаграммы Гасе)