double arrow

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

Связи между свойствами отношений

1. Отношение R слабо полно тогда и только тогда, когда Rd антисимметрично.

Доказательство. Пусть R слабо полно и x ¹ y. Рассмотрим три случая.

1) (x, y)ÎR.Тогда, по определению обратного отношения (y, x)ÎR-1, а по определению двойственного отношения – (y, x)ÏRd.

2) (y, x)ÎR, тогда (x, y)ÎR–1 и, следовательно, (x,y)Ï`R–1 = Rd.

3) (x, y)ÎR и одновременно (y, x)ÎR. Отсюда, (y, х)ÏRd и (x, y)Ï Rd.

Так как R – слабо полное отношение, то для любых x ¹ y выполняется либо случай а), либо б), либо в). Ни в одном из этих случаев включения (x, y)ÎRd и (y, x)ÎRd не могут выполняться одновременно. Следовательно, отношение Rd антисимметрично.

Докажем, обратное, что из антисимметричности Rd следует слабая полнота отношения R. Рассмотрим эквивалентное определение антисимметричности. Если x ¹ y, то либо (x, y)ÎRd и (y, x)Ï Rd, либо (x, y)ÏRd и (y, x)ÎRd, либо (x, y)ÏRd и (y, x)ÏRd. В первом случае получим, что (x, y)ÎR, во втором – (y, x)ÎR, в третьем – (x, y)ÎR и (y, x)ÎR. Это утверждение означает, что отношение R слабо полно.

2. Отношение R асимметрично тогда и только тогда, когда Rd полно.

Доказательство. Пусть R – асимметрично. Тогда по определению, RÇ R–1 = Æ. Рассмотрим два случая.

1) (x, y)ÎR. Тогда (х, y)ÏR–1, значит, (x, y)ÎRd.

2) (x, y)ÏR. Тогда (x, y)Î`R и (y, x) Î`R–1 = Rd.

В любом случае либо (x, y)ÎRd, либо (y, x)ÎRd, а это означает, что Rd полно.

Докажем обратное следствие. Пусть Rd полно. Снова рассмотрим два случая:

а) (x, y)ÎRd, тогда (y, x)ÏR;

б) (y, x)ÎRd, тогда (x, y)ÏR.

Так как Rd полно, то либо случай а), либо случай б) всегда будет иметь место, а отсюда следует невозможность одновременного выполнения yRx и xRy. Это означает, что R асимметрично.

Задание 1. Доказать, что асимметричное отношение антирефлексивно.

Задание 2. Доказать, что ацикличное отношение асимметрично.

Задание 3. Доказать, что если отношение антирефлексивно и транзитивно, то оно ациклично.

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

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

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

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

Iупотношение безразличия (толерантности). Это отношение исключает Pуп между двумя элементами, т.е.

x Iуп y Û ( x`Pуп у и y`Pуп x ). (1)

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

Iуп =`Pуп ÇPdуп. (2)

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

Симметричность. Отношение xIупy означает, что (x, y)ÏPуп и (y, x)ÏPуп. Отношение же yIупx означает, что (y, x)ÏPуп и (x, y)ÏPуп. То есть, xIупy и yIупx эквивалентны. Значит, Iуп симметрично.

Рефлексивность. Так как Pуп антирефлексивно (см. задание 1), то (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уп.


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