Слабый порядок

ЛЕКЦИЯ № 7

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

ОПРЕДЕЛЕНИЕ. Асимметричное, негатранзитивное отношение P_сл назовем слабым порядком.

Кроме того, по аналогии с I_уп введем отношение I_сл

xI_слy <=> ((x, y) Î`P<sub>сл</sub> и (y, x) Î`P_сл)

или

xI_слy <=> ((y, x)ÏP_сл и (x, y)ÏP_сл).

Назовем его отношением эквивалентности. Введем также отношение

R_сл = P_сл ÈI_сл,

называемое нестрогим слабым порядком . Из определения следует, что P_сл Í P_уп . Так как P_уп только асимметрично, а P_сл асимметрично и негатранзитивно, то из (x, y)ÎP_сл всегда следует

(x, y)ÎP_уп.

В качестве примера R_сл можно привести отношение "³".

Рассмотрим свойства слабого порядка и порожденных им отношений.

1) R_сл = P^d_сл , R^d_сл = P_сл.

2) I_сл = R^s_сл , P_сл = R^a_сл.

3) Для любых x,yÎA выполняется одно и только одно из соот-

ношений: xP_слy, yP_слx, xI_слy.

4) Отношение P_сл транзитивно.

5) Отношение I_сл рефлексивно, симметрично, транзитивно.

6) Отношение R_сл транзитивно и полно.

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

xPy Þ " zÎА, xPz или zPy. (4)

Предположим противное, что отношение Р негатранзитивно, но свойство (4) не выполняется, т.е.

xPy и $ z : x`Pz и z`P y. (5)

 

Так как Р негатранзитивно, то из (5) следует одновременное выполнение xРy и x`Py, а этого быть не может, поэтому из негатранзитивности следует свойство (4).

Докажем обратное следствие. Предположим противное, т.е. что (4) выполнено, но Р не является негатранзитивным. Последнее означает, что

$ x,y,zÎA : x`Pz, z`Py, но (x, y) Ï`P,

т.е. (x, y)ÎP. Таким образом, получаем, что xPy выполняется, а xPz и zPy не выполняется, и, значит, (4) неверно, что противоречит предположению. Полученное противоречие доказывает требуемое следствие.

Перейдем теперь непосредственно к доказательству свойства 4). Предположим, что x, y, z таковы, что выполняются соотношения xP_слy и yP_слz. Запишем для них условие (4):

xP_слy Þ " z : xP_слz или zP_слy;

yP_слz Þ " x : yP_слx или xP_слz.

Вспомним, что отношение P_сл асимметрично, т.е. xP_слy и yP_слx, а также yP_слz и zP_слy не могут выполнятся одновременно. Поэтому, из xP_слy может следовать только xP_слz, а из yP_слz - также только xP_слz. Объединив оба этих следствия, получим, что

xP_слy и yP_слz Þ xP_слz,

т.е. P_сл транзитивно.

Докажем свойство 5).

Ранее, в п.6, было доказано, что I_уп рефлексивно и симметрично. Аналогично доказывается рефлексивность и симметричность I_сл. Поэтому остается доказать транзитивность I_сл.

Пусть x, y, zÎA таковы, что xI_слy и yI_слz, покажем, что (x, z)ÎI_сл. По определению I_сл, отношение xI_слy эквивалентно выполнению условий (x, y)ÏP_сл и (y, x)ÏP_сл, а отношение yI_слz - (y, z)ÏP_сл и (z, y)ÏP_сл. В силу негатранзитивности P_сл получим, что (x, z)ÏP_сл и (z, x)ÏP_сл. Следовательно, (x, z)ÎI_сл по определению I_сл.

ЗАМЕЧАНИЕ. Свойства рефлексивности, симметричности и транзитивности считают определяющими свойствами отношения эквивалентности.