Упорядочение и безразличие

Специальные бинарные отношения.

Для бинарных отношений нет устоявшейся терминологии. В данном пособии использованы названия специальных бинарных отношений из [5].

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

Введем следующие отношения.

P_уп - отношение строгого упорядочения, обладающее свойством асимметричности.

I_уп - отношение безразличия. Это отношение исключает P^d_уп

между двумя элементами, т.е.

x I_упy <=> (x`P_упу и y`P_уп x). (1)

Так как (x, y) и (y, x) не принадлежат P_уп, то нельзя сказать, что x лучше y, или x лучше y. Если воспользоваться понятием пересечения отношений, то I_уп можно также представить в виде

I_уп =`P_упÇP^d_уп. (2)

Покажем, что I_уп рефлексивно и симметрично.

Симметричность. Отношение xI_упy означает, что (x, y)ÏP_уп и (y, x)ÏP_уп. Отношение же yI_упx означает, что (y, x)ÏP_уп и (x, y)ÏP_уп. Т.е. xI_упy и yI_упx абсолютно эквивалентны. Значит, I_уп симметрично.

Рефлексивность. Так как P_уп антирефлексивно, то (x, x)Ï P_упи по определению (x, x)ÎI_уп. Значит, I_уп рефлексивно.

Можно дать другое определение отношения I_уп, как симметричного, рефлексивного отношения.

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

R_уп = P_уп ÈI_уп, (3)

которое называется нестрогим упорядочением.

Докажем, что R_уп полно.

ДОКАЗАТЕЛЬСТВО. Возьмем любую пару (x, y). Для нее возможны три случая:

а) (x, y)ÎP_уп; б) (y, x)ÎP_уп;

в) (x, y)ÏP_уп и (y, x)ÏP_уп, т.е. (x, y)ÎI_уп.

Если имеют место случаи а) или в), то по свойству объединения (x, y)ÎR_уп. Если выполняется б) или в), то (y, х)ÎR_уп. Иными словами, в любом случае либо пара (x, y), либо (y, x) принадлежит R_уп. Значит, R_уп полно.

Свойство полноты можно взять за определение отношения R_уп.

Рассмотрим основные свойства отношений P_уп и R_уп.

1. а) P_уп È P^d_уп = P^d_уп;

б) P_уп Ç P^d_уп = P_уп; в) I =`P_уп Ç P^d_уп.

ДОКАЗАТЕЛЬСТВО.

Докажем свойства а) и б). Пусть (x,y)ÎP_уп. Тогда, в силу асимметричности, (y, x)ÏP_уп, а значит, (x, y)ÎP^d_уп по определению двойственного отношения. Таким образом, из (x, y)ÎP_уп следует (x, y)Î P^d_уп, а это означает, что P_уп ÍP^d_уп. Тогда, по свойствам объединения и пересечения множеств, P_уп ÈP^d_уп = P^d_уп, a P_уп = P^d_уп ÇP_уп, что и требовалось доказать.

Докажем свойство в). Пусть (x, y)ÎI_уп. Тогда, по определению I_уп, будем иметь

(x, y) Î`P_уп и (y, x) Î`P_уп.

Второе соотношение эквивалентно тому, что (x, y)ÎP^d_уп. Следовательно, из (x, y)ÎI_уп одновременно вытекает (x, y)ÎP^d_уп и (x,y) Î`P_уп, т.е. (x, y) Î`P_упÇP^d_уп и I_уп Í`PÇP^d_уп.

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

Что и требовалось доказать.

2. R_уп = P^d_уп; P_уп = R^d_уп, т.е. P_уп и R_уп образуют двойственную пару.

ДОКАЗАТЕЛЬСТВО. По определению R_уп = P_упÈI_уп. Воспользуемся представлением (2) отношения безразличия I_уп. Тогда R_уп = P_упÈ(`P_упÇP^d_уп) = (P_упÈ`P_уп)Ç(P_уп ÈP^d_уп). Так как (P_упÈ`P_уп)=А´А, то R_уп = P_уп ÈP^d_уп, а по свойству 1а) R_уп = P^d_уп.