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

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

Def. Асимметричное, негатранзитивное отношение P_сл назовем слабым порядком.

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

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

или

xI_слy Û ((y, x)ÏP_сл и (x, y)ÏP_сл).

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

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

1) Для любых x, yÎA выполняется одно и только одно из соотношений: xP_слy, yP_слx, xI_слy.

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

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

Докажем транзитивность P_сл.

Пусть xP_слy и yP_слz, тогда в силу асимметричности P_сл, yx и zy. Предположим противное, что xz, тогда в силу негатранзитивности из xz и zy следует xy, что противоречит условию. Следовательно, xP_слz, т.е. P_сл – транзитивно.

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

Ранее было доказано, что 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_сл.

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

Дата добавления: 2014-01-11