Отношения. Свойства отношений.

Пусть и – два множества.

Определение 4.1. Прямым (декартовым) произведением двух множеств и называется множество упорядоченных пар, в котором первый элемент каждой пары принадлежит множеству , а второй множеству :

.

Определение 4.2. Степенью множества называется его прямое произведение самого на себя. Соответственно: .

Теорема: .

Доказательство:

Первый компонент упорядоченной пары можно выбрать способами, второй – способами ( – число элементов множества ; – число элементов множества ). Т.о., всего имеется упорядоченных пар.

Пример: ;

;

.

Определение 4.3. Бинарным отношением из множества в множество называется подмножество прямого произведения: . Для бинарных отношений обычно используется инфиксная форма записи: .

Если , то говорят, что есть отношение на множестве и записывают или .

Т.к. всякое бинарное отношение – множество, то над ним можно проводить следующие операции: объединение, пересечение и разность.

Пусть бинарные отношения и определены на множествах и , тогда:

объединение: ;

пересечение: ;

разность: .

Обобщением понятия бинарного отношения является понятие -местного или -арного отношения, которое является подмножеством прямого произведения множеств.

Определение 4.4. -местным отношением называется любое подмножество множества , где – произвольное множество, . При отношение называют бинарным, а при – тернарным:

.

Пусть – есть отношение на множествах и : . Введем следующие понятия:

1. обратное отношение: ;

2. дополнение отношения: ;

3. тождественное отношение: ;

4. универсальное отношение: .

Пример: Пусть заданы множества и пусть отношение быть в 2 раза меньше.

;

;

;

;

;

.

Если – отношение, заданное на множестве , то обратное отношение определяется как .

Отношения и могут образовывать композицию (произведение) отношений, которое само является отношением. .