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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

x I_уп y Û (x`P<sub>уп</sub> у и 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_уп антирефлексивно (см. задание 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_уп.

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