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

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

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

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

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

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

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

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

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

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

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

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

ПРИМЕР 1.

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

Определение 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.

1. Отношение " ", заданное на множестве R, является рефлексивным, однако отношение "<", заданное на том же самом множестве R, не рефлексивно. Докажем второе утверждение. Бинарное отношение " < " это:

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

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

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

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

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

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

ПРИМЕР 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. Должно выполняться свойство: .

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