БИНАРНЫЕ ОТНОШЕНИЯ НА МНОЖЕСТВЕ

Бинарные отношения являются простым и удобным аппаратом для решения разнообразных задач. Язык бинарных отношений и вообще парных отношений очень удобен и естественен для математической лингвистики, математической биологии и целого ряда других, прикладных для математики областей. Часто складывается впечатление, что математика занимается исключительно числами и вычислениями. Однако математика - это нечто гораздо большее, чем просто наука для счетоводов и кассиров, скорее она имеет дело с логикой и качественными связями между понятиями. Теория бинарных отношений - один из важных разделов "неколичественной", если можно так сказать, математики. На базе понятия бинарного отношения вводятся такие фундаментальные математические понятия, как функция, отображение, преобразование, алгебраическая операция, группа и другие.

Примеры

1. Пусть даны множества А={1, 2, 3} и В={4, 5, 6}. Занесем все двузначные числа, у которых первая цифра из А, вторая из В, в таблицу:

2. Пусть имеются две игральные кости в виде куба. На гранях каждой кости числа 1,2,3,4,5,6. Вы бросили обе кости. Какие из наборов чисел можно вписать? Договоримся, что если на первой кости выпадет 1, а на второй 3, то это будем записывать в виде (1,3). Тогда возможен один из следующих случаев:

(1,1), (1,2), (1,3), (1,4), (1,5), (1,6),

(2,1), (2,2), (2,3), (2,4), (2,5), (2,6),

(3,1), (3,2), (3,3), (3,4), (3,5), (3,6),

(4,1), (4,2), (4,3), (4,4), (4,5), (4,6),

(5,1), (5,2), (5,3), (5,4), (5,5), (5,6),

(6,1), (6,2), (6,3), (6,4), (6,5), (6,6).

Определение декартова произведения. Пусть X и У - произвольные множества. Пару (х,у), где хÎC и уÎY, взятые в данном порядке, будем называть упорядоченной парой, считая, что (x₁,y₁)=(x₂,y₂) тогда и только тогда, когда x₁=x₂, y₁=y₂. Декартовым произведением двух множеств Х и Y называется множество всех упорядоченных пар (х,у), первый элемент которых принадлежит множеству X, а второй – множеству Y.

Х ´ Y = {(x,у)½ хÎC, уÎY}.

Декартово произведение множества А на себя называется декартовым квадратом множества А и обозначается А´А=А².

Например, множество R²=R ´R в силу определения декартова произведения, есть множество всех упорядоченных пар (а,b) вещественных чисел. Каждую такую пару можно изобразить точкой М с координатами а и b на координатной плоскости.

В декартовом произведении множеств А и В содержатся всевозможные упорядоченные пары, где первая компонента принадлежит множеству А, а вторая - множеству В. В некоторых случаях целесообразно рассматривать не все, а некоторые пары элементов А´В. В этом случае говорят о бинарном отношении между элементами множеств А и В, или о соответствии между элементами множеств А и В.

Определение. Бинарным отношением (соответствием) между множествами А и В называется тройка (A,B,F), где F ÌA´B.

Множество F называется графиком бинарного отношения (А,В, F). Иногда F для краткости называют бинарным отношением между множествами А и В, но всегда надо четко представлять, между какими множествами установлены данные бинарные отношения, то есть представлять бинарные отношения как тройку, хотя для краткости иногда не делается акцент на исходные множества.

Примеры

1. Пусть А={Коля, Петя}, В={Москва, Баку, Санкт-Петербург}, F={(Коля, Москва), (Петя, Баку), (Петя, Санкт-Петербург)} тройка (А, В, F) есть бинарное отношение между множествами А и В, которое можно понять так: пара (Коля, Москва) ÎF означает, что Коля бывал в Москве и т.д.

2. Пусть А - множество вещественных чисел, В - множество вещественных чисел; F={(х,у)½хÎA, уÎВ, у=(х+2)+3}. Будет ли (A, B, F) бинарным отношением между множествами А и В? Да, будет, так как FÌA´B.

3. Пусть А={1,2,3}, В={4,5}, F={(1,4), (2,5), (2, 6)}. Будет ли (A, B, F) бинарным отношением между множествами А и В? Нет, не будет, так как (2,6)ÏA´B (6ÏB) и, следовательно, F Ë A´B.

Определение. Пусть А - некоторое множество. Тройка (А, А, P), где PÌA´A=A² , называется бинарным отношением на множестве А.

Таким образом, бинарные отношения на множестве А есть частный случай бинарного отношения между множествами А и В, когда А=В.

Рассмотрим еще несколько примеров бинарных отношений:

1. Пусть A - множество вещественных чисел, Р₁ состоит из тех и только тех пар чисел (х, у), для которых х £ у.

2. Пусть А - множество вещественных чисел, Р₂ состоит из тех и только тех пар чисел (х,у), для которых х = у.

3. Пусть А - множество учащихся вашего класса, Р₃ состоит из тех и только тех пар учеников, которые сидят за одной партой.

4. Пусть А - множество прямых на плоскости (а,b)ÎР₄ Û а ^ b.

5. Пусть А - множество натуральных чисел,

Р₅ = {(m,n)½НОД(m,n)=1}, (25,13)ÎP₅; (13,5)ÎP₅; (6,2)Ï Р₅.

6. А={тигр, слон, лев}; Р₆={(тигр, тигр), (тигр, слон}, (слон, лев)}.

Перейдем к знакомству со свойствами бинарных отношений.

Определение. Бинарное отношение (А, А, P) на множестве А называется симметричным, если (a, b)ÎPÞ(b, a)ÎP.

По свойствам равенства, Р₂ симметрично, так как

(х,у) Î Р₂ Û х=у Û у=х Û (у, х)Î P₂.

Отношение р₃ симметрично, так как если ученик а сидит за одной партой с учеником b, то и ученик b сидит за одной партой с учеником а.

Рассмотрим отношение Р₁: (2, 3)ÎR₁, так как 2£3, но (3,2}ÏR₁, значит, р₁ - не симметрично.

Аналогично рассматриваются Р₄, Р₅, Р₆. Отношения Р₄, Р₅ симметричны, а Р₆ - -не симметрично, ибо (слон, лев)ÎР₆, (лев, слон )ÏR₆.

Определение. Бинарное отношение (А,А,Р) на множестве А называется рефлексивным, если любая пара с одинаковыми компонентами принадлежит Р. То есть Р рефлексивно Û "аÎА((а,а)ÎР).

Бинарные отношения R₁, R₂, R₃ рефлексивны. Бинарные отношения Р₄ и Р₅ не рефлексивны, так как а не перпендикулярна а, и если nÎÀ и n¹l, то НОД(n,n)¹1.

Рассмотрим отношение Р₆: “слон”Î А, но (слон, слон)ÏР₆, значит, Р₆ не рефлексивно.

Определение. Бинарное отношение (А,А,Р) на множестве А называется транзитивным, если из того, что (а,b)ÎР и (b,с)ÎР, следует, что (а,с)ÎР.

P транзитивно Û "a,bÎP((a,b)ÎPÙ(b,c)ÎPÞ(a,c)ÎP)

Рассмотрим отношение Р₁. Если х£y и у£z, то х£z. Значит, Р₁ транзитивно.

Если x=у, y=z, то x=z, и следовательно, Р₂ - транзитивно.

Если a^b, b^c, то а не перпендикулярно с по известному свойству прямых. Следовательно, Р₄ не транзитивно.

Так как НОД(12,5)=1, НОД(5,24)=1, но НОД(12,24)¹1, значит Р₅ не транзитивно.

Рассмотрим Р₆: (тигр, слон)ÎР₆ - и (слон, лев)ÎР₆, но (тигр, лев)ÏР₆, значит, Р6 не транзитивно.

Определение. Бинарное отношение (А,А,Р) на множестве А называется антисимметричным, если из того, что (а,b)ÎР и (b,а)ÎР, следует, что а=b.

Р антисимметрично Û "a,bÎP((a,b)ÎPÙ(b,a)ÎPÞa=b)

Рассмотрим отношение Р₁. Если х£ у и у£ х, то х=у. Значит, P₁ антисимметрично.

Если a^b, тогда и b^а, причем a¹b, следовательно, Р₄ не является антисимметричным.

Если НОД(n,m)=1 и НОД(m,n)=1, то необязательно n=m. Например, НОД(12,5)=1, НОД(5,12)=1, но 12¹5, значит, Р₅ не антисимметрично.

Определение. Бинарное отношение (А,А,Р) на множестве А называется эквивалентностью, если Р рефлексивно, симметрично и транзитивно.

Определение. Бинарное отношение (А,А,Р) на множестве А называется упорядоченностью, если Р рефлексивно, антисимметрично и транзитивно.

Как следует из приведенных выше рассуждений, Р₁ - упорядоченность, Р₂, P₃ - эквивалентности, Р₄, Р₅, Р₆ - не являются ни эквивалентностями, ни упорядоченностями.

Теорема. Пусть А¹Æ, (А,А,r) - бинарное отношение. Если r - эквивалентность и упорядоченность, то r - равенство.

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

1) Пусть r - эквивалентность и упорядоченность, тогда r рефлексивно, транзитивно, симметрично и антисимметрично. Покажем, что

r=D={(а,а)½ аÎА}.

Если (а,b)Îr, то из симметричности (b,а)Îr, а из антисимметричности получаем а=b и (а,b)=(а,а)ÎD.

Обратно, пусть (а,b)ÎD, тогда а=b, следовательно, (а,b)=(а,а) и из рефлексивности отношения r следует, что (а,b)Îr.

2) Отношение D={(а,a)½aÎA}, по определению, рефлексивно, симметрично, транзитивно и антисимметрично, следовательно, оно является эквивалентностью и упорядоченностью. Теорема доказана.

Определение. Бинарное отношение (А,А, r) на множестве А называется линейной упорядоченностью, если r - упорядоченность и для всяких а,b Î А и а¹b или (а,b)Îr или (b,а)Îr.

Например, отношение Р₁ на множестве À является линейной упорядоченностью.