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

Бинарным отношением R на множествах А и В называется любое подмножество декартова произведения множеств А и В.

Если элементы x и y множеств А и В находятся в отношении R, то пишут (x,y)ÎR или xRy. Если А=В, то R называется бинарным отношением на А.

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

Пример 1.2 Рассмотрим множества A={1,2,3,4,5,6}, B={1,2,3}. Определим на этих множествах отношение RÍA´B.

R={(x,y) | x делится на y}.

R можно представить графически следующим образом:

d_R={x| (x,y)ÎR для некоторого y},

r_R={y| (x,y)ÎR для некоторого x}.

Пример 1.3 Пусть на множестве A={1,2,3,4,5} задано отношение R: R={(x,y) | остаток от деления y на x равен 1}.

Тогда R={(5,1), (4,1), (3,1), (2,1), (2,3), (2,5), (3,4), (4,5)},

d_R={2,3,4,5}, r_R={1,3,4,5}.

Пусть имеются множества A, B, C и отношения RÍA´B, PÍB´C. Определим отношение SÍA´C следующим образом: оно действует из A в B посредством R, а затем из B в C посредством P. Такое отношение называется составным и обозначается S=P◦R.

S={(x,y) | $zÎB, для которого выполнено (x,z)ÎR, (z,y)ÎP}.

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

d_R={1,2}, r_R={2,3,4}, d_P={1,2,3,4}, r_P={1,2,3,4}, d_S={1,2}, r_S={1,2,3,4}.

Бинарное отношение R на множестве А называется рефлексивным, если для всякого выполняется .

Бинарное отношение R на множестве А называется симметричным, если из того, что выполняется xRy следует выполнение yRx.

Бинарное отношение R на множестве А называется антисимметричным, если из выполнения xRy и yRx следует, что x=y.

Бинарное отношение R на множестве А называется транзитивным, если из выполнения xRy и yRz следует выполнение xRz.

Рефлексивное, симметричное и транзитивное отношение R на множестве A называется отношением эквивалентности.

Рефлексивное, антисимметричное и транзитивное отношение R на множестве А называется частичным порядком.

Пример 1.5. Определим отношение R на множестве натуральных чисел следующим образом: (a+2b делится на 3).

Это отношение является рефлексивным, т.к.

Отношение R симметрично.

. Для того, чтобы проверить выполнение bRa, необходимо показать, что

,

выполнено.

Отношение R не является антисимметричным, т.к. 6R3, 3R6, но .

Проверим, что R – транзитивно.
,

. Для того, чтобы проверить выполнение aRc, необходимо показать, что .

aRc выполнено.