Отношения

Бинарным отношением на множестве называется пара , где область задания отношения, а – график отношения.

Если , то будем писать и говорить, что и вступают в отношение . Если и не вступают в отношение , будем писать .

Диагональю множества называется график .

Свойства отношений:

1. Рефлексивность: .

2. Антирефлексивность: .

3. Симметричность: .

4. Антисимметричность: или равносильное определение: .

5. Транзитивность: .

6. Связность: .

Эти свойства можно определить с помощью графиков отношений:

1. , 2. , 3. ,

4. , 5. , 6. .

Операции над отношениями и сводятся к операциям над их графиками:

, , ,

, .

Отношение называется отношением частичного порядка, если оно рефлексивно, антисимметрично и транзитно.

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

Отношение называется отношением строгого порядка, если оно антирефлексивно, антисимметрично и транзитивно.

Отношение называется отношением строгого линейного порядка, если оно – связное отношение строгого порядка.

Отношение называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Классом эквивалентности, порождённым элементом , называется множество всех элементов из , вступающих с в отношение эквивалентности.

Фактор-множеством множества по отношению эквивалентности называется множество всех различных классов эквивалентности, которое обозначается .

Мощность фактор-множества называется индексом разбиения, порождённого отношением .

Задание 4.1. Проверить для произвольных отношений и справедливость утверждения: «Если отношения и обладают свойством , то отношение также обладает свойством ».

Обозначения: 1 – рефлексивность, 2 – антирефлексивность, 3 – симметричность, 4 – антисимметричность, 5 – транзитивность, 6 – связность.