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

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

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

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

Мы уже знаем, что бинарные отношения являются множествами и, следовательно, можно говорить о равенстве бинарных отношений и о включении одного бинарного отношения в другое: j = y, j Í y.

На бинарные отношения, заданные на некотором множестве переносятся общие операции над множествами. Пусть j и y - бинарные отношения заданные на множестве A. Тогда

1) jÇy - есть бинарное отношение в A являющееся пересечением отношений j и y,

2) jÈy - есть бинарное отношение в A являющееся объединением отношений j и y,

3) jy - есть бинарное отношение в A являющееся разностью отношений j и y,

4) `j - есть бинарное отношение в A являющееся дополнением к бинарному отношению j в A, т.е. `j = A²j.

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

j₁ = {(n,m) Î ² : n ³ m },

j₂ = {(n,m) Î ² : n > m },

j₃ = {(n,m) Î ² : n < m },

j₄ = {(n,m) Î ² : 4n = m² },

тогда между ними имеют место следующие отношения включения:

j₂ Ì j₁; j₁ Èj₂ = j₁, j₁ Çj₂ = j₂, j₁j₂ = {(n,m) Î ²:n = m } последнее бинарное отношение является отношением равенства в ну и т.д.

Можно определить еще одну операцию над парой заданных на множестве A бинарных отношений j и y.

Определение. Назовем суперпозицией (композицией) этих двух бинарных отношений бинарное отношение (мы будем обозначать его как jy) определенное следующим образом: (a,c) Î jy Û когда в множестве A найдется хотя бы один элемент b такой, что (a,b) Î j и (b,c) Î y.

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

1) j₁ j₂ = j₂ j₁ = j₂. Действительно, поскольку n ³ m₁, а m₁ > m, то n > m; обратно, если n > m₁ m₁ ³ m, то n > m.

2) j₁j₃ = ². Рассмотрим произвольную пару (n,m) Î ², возможны два случая a)n ³ m; b)n < m. Рассмотрим случай a) (n,m-1) Î j₁, (m-1,m) Î j₃Þ (n,m) Î j₁j₃

в случае b) (n,n-1) Î j₁, (n-1,m) Î j₃Þ (n,m) Î j₁j₃. Итак, мы показали, что ² Í j₁j₃ и следовательно j₁j₃ = ².

3) j₁j₄ ¹ j₄j₁. Этот пример показывает, что суперпозиция бинарных отношений, вообще говоря, не обладает свойством коммутативности.

Доказательство. Поскольку (3,1) Î j₁ и (1,2) Î j₄ мы получаем, что пара (3,2) Î j₁j₄ Теперь надо показать, что пара (3,2) Ï j₄j₁ перепишем бинарное отношение j₄ как j₄ = {((m²)/ 4,m): $k Î , m = 2k} следовательно (3,n) Ï j₄ причем для любого n; откуда получаем, что пара (3,2) Ï j₄j₁, ибо в противном случае (3,n) Î j₄, что невозможно. Доказательство окончено.

Однако легко показать, что

jEM = EM j = j; jÆ = Æj = Æ,

здесь E_M - бинарное отношение равенства в множестве M.

Немного сложнее доказательство следующих равенств. Пусть в множестве A заданы бинарные отношения y и j_i, i Î I, здесь I - конечный или бесконечный набор индексов. Тогда

( È i Î I ji)y = È i Î I (ji y),

 

y( È i Î I ji) = È i Î I (yji),

заметим, что в вышеприведенных соотношениях значки È нельзя заменить на Ç.

Докажем первое утверждение. Пусть (a,b) Î (È_{i Î I}j_i)y Û $c : (a,c) Î È_{i Î I}j_i и (c,b) Î yÛ $i₀ Î I : (a,c) Î j_i0 Þ (a,b) Î j_i0y Þ (a,b) Î È_{i Î I} (j_iy).

Утверждение. Для любых бинарных отношений j, y,r заданных на некотором множестве A справедливо следующее равенство

(jy)r = j(yr).

Оно означает, что суперпозиция бинарных отношений обладает свойством ассоциативности.

Доказательство.

Пусть пара (a,b) Î (jy)rÞ $c :(a,c) Î jy и (c,b) Î r. Это означает, что $d : (a,d) Î j и (d,c) Î yÞ(d,b) Î yr и (a,b) Î j(yr). Итак мы доказали, что если (a,b) Î (jy)r, то из этого следует, что (a,b) Î j(yr). Обратное включение доказывается аналогично.

Это утверждение говорит о том, что какими бы двумя различными способами мы ни расставляли скобки в выражении j₁ j₂... j_n, чтобы получить суперпозицию двух отношений мы получим равные отношения.

Определение. Пусть на множестве A задано бинарное отношение j, тогда отношением обратным к j называется отношение j^-1 также заданное на A, которое состоит из тех и только тех пар (b,a), для которых справедливо, что (a,b) Î j.

Пример. Пусть на множестве A = {0,1,2,3 } задано бинарное отношение j = {(0,1);(2,3);(1,3)}, тогда j^-1 = {(1,0);(3,2);(3,1) }

Кроме того, справедливы следующие равенства:

(j-1)-1 = j, (jy)-1 = y-1j-1.

Функции

Определение. Функцией называется любое бинарное отношение, которое не содержит двух пар с одинаковыми первыми элементами и разными вторыми. Если f - функция, то множество Df мы будем называть областью определения… Примеры. 1) {(1,1);(2,3); (3,2)} есть функция с областью определения {1,2,3} и это же множество является ее областью…

Мощность множеств

Определение. Говорят, что множество A эквивалентно множеству B, если существует биективное отображение f:A --> B. Под словами "биективное отображение" понимают взаимнооднозначное… Примеры. 1) Множество и множество четных натуральных чисел эквивалентны. Необходимая биекция задается формулой f(n)…

Мощность континуума

Доказательство мы будем проводить от противного. Давайте, предположим, что множество M - счетно и следовательно согласно приведенному утверждению…   Запишем числа xi Î (0,1) в виде десятичных дробей (без 9 в периоде) x1 = 0,a11 a12 a13 ... …

ИСЧИСЛЕHИЕ ВЫСКАЗЫВАHИЙ.

Из высказываний пyтём их соединения pазличными способами можно составлять новые более сложные высказывания. Мы бyдем pассматpивать одни только… Определение. Отpицание является одной из пpостейших опеpаций над… Таблица истинности этой операции. A ù A И Л Л И

Пpимеp.

Пpимеp. (A = ù A ) Утверждение. Пpопозициональная фоpма X является тавтологией тогда и только… Введём некотоpые соглашения об экономном использовании скобок пpи записи фоpмyл. Эти соглашения облегчают чтение…