1. Способы задания бинарных отношений

Существует четыре разных способа задания отношений:

ОПИСАНИЕ ВЫБОРА НА ЯЗЫКЕ БИНАРНЫХ ОТНОШЕНИЙ
Перечисление пар (x,y) R	Задание матрицы пред почтении	Задание графа предпочтении	Задание сечений

преимущества каждого проявляются при разных характеристиках множества X.

Первый, очевидный, способ состоит в непосредственном перечислении таких пар. Ясно, что он приемлем лишь в случае конечного множества X.

Второй удобный способ задания отношения R на конечном множестве - матричный. Все элементы нумеруются, и матрица отношения R определяется своими элементами a_ij(R)={1: x_iRx_j; 0: x_iRx_j] для всех i и j. Известным примером такого задания отношений являются турнирные таблицы (если ничьи обозначить нулями, как и проигрыш, то матрица изобразит отношение "x_i - победитель x_j").

Третий способ-задание отношения графом. Вершинам графа G(R) ставят в соответствие (пронумерованные) элементы множества X, и если x_iRx_j, то от вершины x_i проводят направленную дугу к вершине x_j, если же x_iRx_j, то дуга отсутствует.

Для определения отношений на бесконечных множествах используется четвертый способ - задание отношения R сечениями. Множество R⁺(х)={y Х|(у, х) R} называется верхним сечением отношения R, а множество R^-(х)={y Х|(x, y) R} - нижним сечением. Иначе говоря, верхнее сечение - это множество всех у X, которые находятся в отношении yRx с заданным элементом х X, а нижнее сечение- множество всех у X, с которыми заданный элемент х находится в отношении R. Отношение однозначно определяется одним из своих сечений.

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

Пример 1. Полное бинарное отношение U:

1) в U входят все пары (х_i, х_ij), х_s X;

2) a_ij(U)=1 для всех i и j;

3) граф G(U) такой, что его дуги соединяют любую пару вершин;

4) R⁺(x)=R^-(x)=Х  х X.

Пример 2. Диагональное отношение Е:

1. в Е входят только пары с одинаковыми номерами: х_iЕх_j верно только при i =j;

2. a_ij(E)={1: i=j; 0: i j};

3. граф G(E) такой, что каждая его вершина имеет петлю, а остальные дуги отсутствуют;

4. R⁺(x)=R^-(x)=x  х X.

2. Отношения эквивалентности, порядка и доминирования

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

Для их определения нам понадобятся некоторые свойства отношений вообще. Бинарное отношение R на множестве Х называется:

рефлексивным, если xRx  х X;

антирефлексивным, если xRх  х X (т.е. R может выполняться только для несовпадающих элементов);

симметричным, если xRy yRx  х, у X;

асимметричным, если xRy yRx  х, у X;

антисимметричным, если  х, у X (xRy, yRx) х=у;

транзитивным, если для всех х, у, z X (xRy, yRz) xRz;

отрицательно транзитивным, если отношение R транзитивно;

сильно транзитивным, если отношение R одновременно транзитивно и отрицательно транзитивно.

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

Отношение R на множестве Х называется отношением эквивалентности (обозначение ~), если оно рефлексивно, симметрично и транзитивно. Примеры отношений эквивалентности: "быть четным", "иметь одинаковый остаток от деления на 3" - на множестве натуральных чисел; "быть одноклассниками" - на множестве учеников данной школы; "быть подобными" -на множестве многоугольников. Задание отношения эквивалентности равносильно разбиению множества Х на непересекающиеся классы (X= |_iX_i; X_i X_j= при i j) эквивалентных элементов: х~у тогда и только тогда, когда х, у X, (т.е. если х и у принадлежат одному классу эквивалентности),

Отношением нестрогого порядка (обозначение <) называется рефлексивное, антисимметричное и транзитивное отношение. Отношением строгого порядка (обозначение <) называется антирефлексивное, асимметричное и транзитивное отношение. Отношение нестрогого порядка можно рассматривать как объединение отношений < и ~.

Наконец, отношением доминирования называется отношение, обладающее антирефлексивностью и асимметричностью. Говорят, что "х доминирует у" (обозначается х » у), когда х в каком-то смысле превосходит у. (Очевидно, строгий порядок-частный случай доминирования, при котором имеет место еще транзитивность.)

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

В случае конечных множеств Х очень удобно находить наилучшие альтернативы с помощью графа предпочтений, стрелки которого направлены в сторону менее предпочтимой альтернативы (рис. 7.4) . Выделив вершины графа, из которых стрелки только исходят (альтернативы 6 и 10 на рис. 7,4), мы находим недоминируемые, т.е. наилучшие, альтернативы. Можно показать, что если граф сильно транзитивен (т.е. тран-зитивен и по наличию, и по отсутствию стрелок) и антирефлексивен (отсутствуют петли), то описываемый выбор сводится к однокритериальному выбору. Другие типы графов описывают другие ситуации выбора.

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

Например, многомерное критериальное пространство (с теми оговорками о соотношении размерностей критериев, которые были сделаны в предыдущем параграфе) может быть поставлено в соответствие евклидову пространству. Введение на этом пространстве бинарных отношений требует учета его свойств. В частности, начинают играть роль отношения инвариантные (относительно переноса), для которых верхнее сечение в любой точке может быть получено параллельным переносом верхнего сечения в любой другой точке. Примером инвариантного отношения является отношение Парето Р: ( х, у Х)[хРу] {( j=1 ... m)[х_j у_j] & (j₀=1 ... m)[х_j0>у_j0]} .

Верхнее сечение отношения Р есть первый квадрант с началом в точке х; теперь понятно, как находится паретовское множество альтернатив: в паретовское множество включаются альтернативы, верхнее сечение которых пусто.

В общем же случае выделение наиболее предпочтительных альтернатив возможно с помощью понятия оптимальности по отношению R, позволяющего придавать разный смысл понятию "наилучший" (задавая разные отношения R). Элемент х Х называется мажорантой по отношению R на X, если для всех у Х выполнено условие yRх. Множество X₊(R) всех мажорант называется множеством R-оптимальных элементов.