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

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_уп.

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

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

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_сл, y x и z y. Предположим противное, что x z, тогда в силу негатранзитивности из x z и z y следует x y, что противоречит условию. Следовательно, 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_сл.

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

 

Разбиение и эквивалентность

Def. Система (конечная или бесконечная) непустых подмножеств А₁, A₂,..., А_n... множества А называется разбиением, если:

1) объединение множеств А_i образуют все A (т.е. ÈА_i=А);

2) множества А_i попарно не пересекаются (т.е. для любых i¹j справедливо А_i Ç A_j = Æ).

Теорема о разбиении. Отношение I ÌА´А, будет отношением эквивалентности тогда и только тогда, когда существует разбиение А₁, А₂,..., А_n,... множества А, что из xIy следует существование такого А_i, что x, yÎА_i.

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

Доказательство. Предположим, что I – отношение эквивалентности, т.е. оно является рефлексивным, симметричным, транзитивным. Наша задача – построить такое разбиение, чтобы между элементами каждого класса выполнялось отношение I. Введем для каждого xÎА множество В_x, состоящее из элементов эквивалентных х, т.е. В_x = {zÎA | xIz }.

Покажем, что два любых множества B_x и B_y либо совпадают, либо не пересекаются. Пусть zÎB_x Ç B_y. Это означает, что одновременно zIx и zIy. Тогда, в силу симметричности и транзитивности, получаем xIy. Пусть теперь v – произвольный элемент из B_x, т.е. выполнено отношение vIx. Тогда, вследствие транзитивности отношения I и соотношения xIy, получим vIy, т.е. vÎB_y. Точно также можно доказать, что если vÎB_y, то vÎB_x. Это означает, что всякий элемент v из B_x одновременно принадлежит и B_y и наоборот. Следовательно, два множества B_x и B_y, имеющие хотя бы один общий элемент, совпадают между собой.

Наконец, в силу того, что множества B_x построены для всех элементов х из A, и, в силу рефлексивности I, элемент х принадлежит своему множеству B_x, объединение B_x включает в себя все множество A. Это означает, что система {B_x} образует разбиение A, т.е. в одну сторону теорема доказана.

Докажем обратное. Пусть имеем разбиение множества А на непересекающиеся классы. Определим отношение I следующим образом: элемент x находится с элементом y в отношении I тогда и только тогда, когда они оба принадлежат одному классу. Тогда это отношение обладает свойством рефлексивности, т.к. сам элемент х принадлежит классу, элементом которого является.

Обладает отношение I и свойством симметричности, т.к. если x и y принадлежат какому-то классу, то это же можно сказать и про y и x.

Наконец, если имеют место отношения xIy и yIz, то это значит, что x, yÎB и y, zÎB, где B – какой-то класс. Таким образом, x, zÎB, т.е. между x и z установлено отношение I. Следовательно, I обладает транзитивностью. Значит, I – отношение эквивалентности. Теорема полностью доказана.

 

Качественный порядок

Дополним отношение строгого упорядочения P_уп свойством транзитивности. Назовем полученное отношение качественным порядком P_кач. Рассмотрим два примера такого отношения.

1) Пусть х, у – вещественные числа. Введем качественный порядок следующим соотношением:

хР_качу Û x > у + 1.

Очевидно, что в данном случае отношение Р_кач асимметрично и транзитивно, но оно не является негатранзитивным. Покажем это.

Дополнение к введенному отношению определим как

х`Р_кач у <=> х £ у + 1

Положим у = 0; х = 0.9; z = – 0.9. Тогда, очевидно, выполняются отношения (х, y) Î`Р<sub>кач</sub>; (y, z) Î`Р_кач; (х, z) Ï Р_кач. Т.е. условие негатранзитивности не выполняется.

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

2) Введем на множестве точек n-мерного евклидова пространства следующее отношение Par, называемое отношением Парето:

х, уÎРаr Û " i: х_i ³ y_i и $ j: х_j > у_j.

Отношение Парето называется также безусловным критерием предпочтения (БКП). Оно означает, что точка x по всем координатам имеет не меньшие значения, чем точка y и хотя бы по одной координате имеется строгое превосходство. В двумерном случае данное отношение можно изобразить графически. Возможны следующие ситуации:

 

а) x₁ < y₁ б) x₁ > y₁ в) x₁ < y₁

x₂ > y₂ x₂ = y₂ x₂ < y₂

нет отношения Раr; есть отношение Раr, есть отношение Раr,

x лучше y; y лучше x.

Задание. Доказать, что отношение Раr является качественным порядком.