БИНАРНЫЕ ОТНОШЕНИЯ

Пусть р Ì Х´ Y; если Х = Y, то в этом случае говорят о бинарном отношении между элементами одного множества или об отношении на множестве и пишут p ´ х или р Ì х²

Отношения на множестве X могут обладать следующими свойствами:

1. Говорят, что отношение р обладает свойством рефлексивности, если для любого х из множества Х истинно х р х, другими словами, если каждый элемент х Î Х находится в отношении р с самим собой (" хÎ Х)х р х – И.

2. Говорят, что отношение р обладает свойством антирефлексивности если о любом элементе множества х можно сказать, что он не находится в отношении р с самим собой.

(" хÎ Х) –И.

3. Говорят, что отношение р обладает свойством симметричности, если для всех элементов х и у из множества Х истинно утвержде­ние: если элемент х находится в отношении р с элементом у, то и элемент у находится в отношении р с элементом х.

(" х, уÎ Х)хру ® урх –И.

4. Говорят, что отношение/» обладает свойством антисимметрич­ности, если для всех различных элементов х и у из множества X из того, что элемент х находится в отношении р с элементом у, сле­дует, что элемент у не находится в отношении р с элементом х.

(" х, уÎ Х, х ¹ у)х р у® – И.

5. Говорят, что отношение р обладает свойством транзитивности, если для всех элементов х, у, z из множества X истинно утверждение: если элемент х находится в отношении p с элементом у и элемент у находится в отношении р с элементом z, то элемент х находится в отношении р с элементом z.

(" х, у, z Î Х)х р у Ù у р z® х р z – И.

6. Говорят, что отношение р обладает свойством связности, если для любых элементов х и у из множествах Х и х ¹ у, следует, что или х находится в отношении р с у, или у находится в отношении р с х.

(" х, уÎ Х, х ¹ у)х р у или у р х – И.

Указанные свойства отношений позволяют выделить два вида отношений.

1. Отношение р на множестве X называется отношением эквивалентности, если оно обладает свойствами рефлективности, симметричности и транзитивности.

Имеет место теорема:

Для того чтобы отношение р определяло разбиение множества Х на классы, необходимо и достаточно, чтобы р было отношением эквивалентности.

2. Отношение р на множестве X называется отношением порядка, если оно обладает свойствами антисимметричности и транзитивности.

Множество Х сзаданным на нем отношением порядка называется упорядоченным множеством.

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