double arrow

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


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

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

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

xIслy Û ( (x, y) Î`Pсл и (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сл.

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







Сейчас читают про: