2.1. Понятие отношения

Определение 2.1. n-арным (или n-местным) отношением P на множествах A₁, A₂, …, A_n называется любое подмножество прямого произведения A₁ × A₂ × … × A_n.

Обозначение n-местного отношения: P(x₁, x₂, …, x_n).

В случае n = 1 отношение P называется унарным (одноместным) и является подмножеством множества A₁.

При n = 2 P называется бинарным (двуместным) отношением или соответствием. Если P  A₁  A₂, то также говорят, что Р есть отношение между множествами A₁ и A₂ (между элементами множеств A₁ и A₂) или что Р задано (определено) на паре множеств A₁ и A₂. Если A₁ = A₂ = A (P  A  A), то говорят, что Р есть бинарное отношение на множестве А.

Пусть Р – бинарное отношение и (x, y)  P, тогда говорят, что элемент x находится в отношении P к элементу y, или что x и y связаны отношением P. Вместо записи (x, y)  P часто пишут xPy.

Определение 2.2. Элементы x₁, x₂, …, x_n.называются координатами, или компонентами, отношения P.

Определение 2.3. Пусть P  A  B, S  A  B. Бинарные отношения P и S называются равными (пишут Р = S), если для любых x  A и y  B:  .

Другими словами, отношения Р и S равны, если Р и S равны как множества.

Определение 2.4. Для любого множества А отношение id_A = {(x, x) | x  A} называется тождественным отношением (или диагональю), а U_A = A² = A  A = {(x, y) | x, y  A} – полным отношением (или универсальным отношением или полным квадратом).

Пусть Р – некоторое бинарное отношение, т. е. P  A₁  A₂.

Определение 2.5. Областью определения бинарного отношения Р называется множество DomР = {x |  y : (x, y)  P}.

Определение 2.6. Областью значений бинарного отношения Р называется множество ImР = {y |  x : (x, y)  P}.

Пример 2.1. Задано множество Р = {(1, y), (2, y), (3, x)} на множествах А = {1, 2, 3} и B = {x, y}. Покажем, что это действительно отношение, т. е. P  A  В. Найдем декартовое произведение множеств А и В: A  В = {(1, x), (1, y), (2, x), (2, y), (3, x), (3, y)}, следовательно, P  A  В.

Найдем область определения и область значений бинарного отношения Р.

DomР = {1, 2, 3} = А; ImР = {х, y} = В.

Пример 2.2. Пусть P  R  R : Р = {(х, y) | y = x²}. Найдем область определения и область значений бинарного отношения Р.

DomР = R; ImР = [0, +).