Операции над бинарными отношениями

Суперпозиция бинарных отношений

Свойства суперпозиций бинарных отношений

Цели занятия: изучить понятие отношения на множестве как его некоторые подмножества; научиться осуществлять операции над отношениями; понять принцип суперпозиции отношений.

Роль и место лекции

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

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

1. Отношения на множествах

Определение 1.

Отношение – это один из способов задания взаимосвязей между элементами множеств. Они бывают унарные, бинарные и в общем случае n-арные.

Определение 2.

Унарные (одноместные) отношения на множестве – это наличие какого-то определенного признака R (свойства и т. п.) у элементов a некоторого множества M. Унарное отношение образует некоторое подмножество на множестве, в котором они введены, т. е. .

Множество животных одного вида являются подмножеством множества рода животных и т. д. Так {грызуны} {млекопитающие} подмножество задано отношением «класс»

Определение 3.

Соответствие – это способ задания взаимосвязей, взаимодействий между элементами множества (наряду с отношениями). Частными случаями соответствия являются функции, операции, преобразования и др.

Определение  4.

Два множества называются эквивалентными, если для любого элемента а множества А найдется такой элемент b множества В, что .

2. Бинарные отношения

Определение 5.

Бинарное (двухместное) отношение на множестве – это наличие каких-либо взаимосвязей R, которыми характеризуются пары элементов на некотором множестве M. Тогда все пары  элементов из М, между которыми имеет место данное отношение R,образуют подмножество пар из множества всех возможных пар элементов , т. е. , при этом .

Определение  6.

Сокращенное определение. Говорят, что на множестве M задано бинарное отношение , если в M×M выделено некоторое подмножество .

Другими словами, бинарное отношение на множестве M – это подмножество в M×M. Утверждение, что элемент a состоит в отношении  с элементом b, означает, что пара , или

 .                 (1)

ПРИМЕР  2.

1. Отношение делимости в N. Число n состоит в этом отношении с числом m, если n делится на m {(1,1),(3,6),(3,9)…}:. Подмножество R в N², определяющее отношение делимости, имеет вид: R = {(n,m) : : n = km}.

2. Отношение " " в R. Число x состоит в этом отношении с числом y, если x y {(1,2); (3,3); (2,12)…}. Соответствующее подмножество в R² определяется следующим образом: R = {(x,y) : x y}.

3. Отношение равенства в R. Числа x и y состоят в этом отношении, если они равны {(1,1),(3,3)…}: R = {(x,y) : x=y}.

4. Отношение {семейной пары} на множестве {люди}.

Определение  7.

Бинарное отношение , заданное на множестве M называется:

- рефлексивным, если a a для a M,

- симметричным, если a b  b a,

- антисимметричным, если (a b) и (b a)  a = b,

- транзитивным, если (a b) и (b с)  a c.

ПРИМЕР 3.

"<"=R = {(x,y) : x<y},

означающее, что произвольный элемент  должен удовлетворять неравенству a < a, а это неправда. Следовательно, произвольный элемент a не состоит сам с собой в отношении "<", и рефлексивности нет. Множество {животные одного вида} рефлексивно.

2. Определим на множестве R следующее бинарное отношение: элементы связаны бинарным отношением , если равны их целые части [x]=[y]. Докажем, что определенное таким образом бинарное отношение  обладает свойством симметричности. Действительно, имеет место следующее соотношение

[x] = [y]  [y] = [x].

Определение  8.

Бинарное отношение , заданное на множестве M, называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно (см. определение 4).

Пусть на множестве M={1, 2, 3} задано бинарное отношение ={(1,2); (2,1); (1,1); (2,2); (3,3)}. Доказать, что заданное таким образом бинарное отношение  является отношением эквивалентности. Нужно показать, что бинарное отношение  обладает свойствами рефлексивности, симметричности и транзитивности.

1. Необходимо проверить, что для любого элемента a из множества M пара (a,a) принадлежит бинарному отношению . Здесь a = 1, 2, 3 и из определения  видно, что пары (1,1), (2,2), (3,3) принадлежат бинарному отношению .

2. Выполнение условия  видно прямо из определения бинарного отношения .

3. Должно выполняться свойство: .

Действительно: ,   и т. д.

3. Операции над бинарными отношениями

Мы уже знаем, что бинарные отношения являются множествами, и, следовательно, можно говорить о равенстве бинарных отношений и о включении одного бинарного отношения в другое: . На бинарные отношения, заданные на некотором множестве переносятся общие операции над множествами. Пусть  и  – бинарные отношения, заданные на множестве A. Тогда:

- – бинарное отношение в A, пересечение отношений  и ;

- – бинарное отношение в A, объединение отношений  и ;

- – бинарное отношение в A, разность отношений  и ;

- – бинарное отношение в A, дополнение к бинарному отношению  в A, т. е. .

ПРИМЕР 5.

Определим следующие бинарные отношения:

тогда между ними имеют место следующие отношения включения: ; ; ; . Последнее бинарное отношение является отношением равенства в Z и т.д.

В биологии отношение на множестве {ареал} может определять подмножество {вид животных}.

4. Суперпозиция бинарных отношений

Определение 9.

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

когда в множестве A найдется хотя бы один элемент b, такой, что

и

Определение 10.

Множество называется связным, если на этом множестве можно определить суперпозицию любых подмножеств.

ПРИМЕР 6.

Для бинарных отношений, определенных в предыдущем примере, нужно  показать, что справедливы следующие равенства:

1. = = . Действительно, поскольку , , то ; обратно, если , , то ;

2. = . Рассмотрим произвольную пару , возможны два случая a) ; b) . Рассмотрим случай a) , . В случае b) , . Итак, мы показали, что   и, следовательно, ;

3. .                      

Замечание!!!