Бинарные отношения
Определение. Говорят, что на множестве M задано бинарное отношение j, если в M×M выделено некоторое подмножество R = Rj.
Другими словами, бинарное отношение на множестве M - это подмножество в M×M.
Утверждение, что элемент a состоит в отношении j с элементом b означает, что пара (a,b) Î j или
Примеры. 1) Отношение делимости в
. Число n состоит в этом отношении с числом m, если n делится на m. Подмножество R в
2, определяющее отношение делимости имеет вид:
R = {(n,m) Î 2: $k Î :n = km}
|
|
2) Отношение " £ " в
. Число x состоит в этом отношении с числом y, если x £ y. Соответствующее подмножество в
2 определяется следующим образом:
R = {(x,y) Î 2: x £ y }
|
|
3) Отношение равенства в
. Числа x и y состоят в этом отношении, если они равны:
R = {(x,y) Î 2: x = y }
|
|
Определение. Бинарное отношение j
заданное на множестве M называется:
1) рефлексивным, если aja для "a Î M,
2) симметричным, если ajb Þ bja,
3) антисимметричным, если (ajb) и (bja) Þ a = b,
4) транзитивным, если (ajb) и (bjс) Þ a jc.
Примеры. 1)Отношение " £ ", заданное на множестве является рефлексивным, однако отношение " < ", заданное на том же самом множестве не рефлексивно.
Докажем второе утверждение. Бинарное отношение " < " это:
" < " = R = {(x,y) Î 2: x < y }
|
|
это означает, что произвольный элемент 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) Должно выполняться свойство:
(a,b) Î t, (b,c) Î t Þ (a,c) Î t.
|
|
Действительно
(1,2) Î t, (2,1) Î t Þ (1,1) Î t,
|
|
(1,1) Î t, (1,2) Î t Þ (1,2) Î t,
|
|
ну и так далее. Доказательство окончено.