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

Определение. Говорят, что на множестве M задано бинарное отношение j, если в M×M выделено некоторое подмножество R = R_j.

Другими словами, бинарное отношение на множестве M - это подмножество в M×M.

Утверждение, что элемент a состоит в отношении j с элементом b означает, что пара (a,b) Î j или

Примеры. 1) Отношение делимости в . Число n состоит в этом отношении с числом m, если n делится на m. Подмножество R в ², определяющее отношение делимости имеет вид:

2) Отношение " £ " в . Число x состоит в этом отношении с числом y, если x £ y. Соответствующее подмножество в ² определяется следующим образом:

3) Отношение равенства в . Числа x и y состоят в этом отношении, если они равны:

Определение. Бинарное отношение j заданное на множестве M называется:

1) рефлексивным, если aja для "a Î M,

2) симметричным, если ajb Þ bja,

3) антисимметричным, если (ajb) и (bja) Þ a = b,

4) транзитивным, если (ajb) и (bjс) Þ a jc.

Примеры. 1)Отношение " £ ", заданное на множестве является рефлексивным, однако отношение " < ", заданное на том же самом множестве не рефлексивно.

Докажем второе утверждение. Бинарное отношение " < " это:

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

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

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

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

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

2) Выполнение условия (a,b) Î t Þ (b,a) Î t видно прямо из определения бинарного отношения t.

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

Действительно

ну и так далее. Доказательство окончено.