ОТНОШЕНИЕ НА МНОЖЕСТВЕ

Пусть задано некоторое непустое множество А и R – некоторое подмножество декартова квадрата множества А: R Í A ´ A.

Отношением R на множестве А называют подмножество множества А´А (или А²). Таким образом отношение есть частный случай соответствия, где область прибытия совпадает с областью отправления. Так же, как и соответствие, отношение – это упорядоченные пары, где оба элемента принадлежат одному и тому же множеству.

R Í A ´ A = {(a, b) | aÎA, bÎA, (a, b)ÎR}.

Тот факт, что (a, b)ÎR можно записать так: a R b. Читается: «а находится в отношении R к b» или «между а и b имеет место отношение R». В противном случае записывают: (a, b)ÏR или a `R b.

Примером отношений на множестве чисел являются следующие: «=», «¹», «£», «>» и т.д. На множестве сотрудников какой-либо фирмы ‑ отношение «быть начальником» или «быть подчинённым», на множестве родственников – «быть предком», «быть братом», «быть отцом» и т.д.

Рассмотренные отношения носят название бинарных (двухместных) однородных отношений и являются важнейшими в математике. Наряду с ними рассматривают также п -местные или п -арные отношения:

R Í A ´ A ´…´ A = Aⁿ = {(a₁, a₂,…a_n) | a₁, a₂,…a_n Î A}.

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

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

При геометрическом (графическом) изображении отношения мы получим схему, включающую:

¨ вершины, обозначаемые точками или кружочками, которые соответствуют элементам множества,

¨ и дуги (линии), соответствующие парам элементов, входящих в бинарные отношения, обозначаемые линиями со стрелками, направленными от вершины, соответствующей элементу a к вершине, соответствующей элементу b, если a R b.

Такая фигура называется ориентированным графом (или орграфом) бинарного отношения.

Задача 4.9.1. Отношение R«быть делителем на множестве M = {1, 2, 3, 4 }» может быть задано матрицей:

;

перечислением: R = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), ((4,4)};

геометрически (графически):

 

Рис. 4.20

Задачи для самостоятельного решения.

1. Выписать упорядоченные пары, принадлежащие следующим бинарным отношениям на множестве А = {1, 2, 3, 4, 5, 6, 7}:

а) R1 = {(x, y)| x, yÎA; x + y = 9};

б) R2 = {(x, y)| x, yÎA; x < y}.

2. Отношение R на множестве X = {a, b, c, d} задано матрицей

,

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

3. Отношение на множестве А = {1, 2, 3, 4} представлено графом. Необходимо:

а) перечислить упорядоченные пары, принадлежащие R;

б) выписать соответствующую матрицу;

в) определить это отношение с помощью предикатов.

(ответ: a-b= 1).