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

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

ОПРЕДЕЛЕНИЕ. Асимметричное, негатранзитивное отношение P_сл назовем слабым порядком.

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

XIслy  ((X, y) Pсл и (y, X) Pсл)

или

XIслy  ((y, X)Pсл и (X, y)Pсл).

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

R_сл = P_сл  I_сл,

называемое нестрогим слабым порядком. Из определения следует, что P_сл  P_уп . Так как P_уп только асимметрично, а P_сл асимметрично и негатранзитивно, то из (x, y)P_сл всегда следует

(x, y)P_уп.

В качестве примера R_сл можно привести отношение "".

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

1) R_сл = P^d_сл , R^d_сл = P_сл.

2) I_сл = R^s_сл , P_сл = R^a_сл.

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

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

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

6) Отношение R_сл транзитивно и полно.

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

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

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

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

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

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

ОПРЕДЕЛЕНИЕ. Система ( конечная или бесконечная ) непустых подмножеств А₁, А₂,..., А_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, их объединение включает в себя все множество 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 – отношение эквивалент-ности. Теорема доказана и в другую сторону.