Бинарные отношения. Примеры бинарных отношений

Определение . Бинарным отношением R называется подмножество пар (a,b)∈R декартова произведения A×B, т. е. R⊆A×B . При этом множество A называют областью определения отношения R, множество B – областью значений.

Обозначение: aRb (т. е. a и b находятся в отношении R). /

Замечание : если A = B , то говорят, что R есть отношение на множестве A .

Способы задания бинарных отношений

1. Списком (перечислением пар), для которых это отношение выполняется.

2. Матрицей. Бинарному отношению R ∈ A × A , где A = (a 1 , a 2 ,..., a n), соответствует квадратная матрица порядка n , в которой элемент c ij , стоящий на пересечении i-й строки и j-го столбца, равен 1, если между a i и a j имеет место отношение R , или 0, если оно отсутствует:

Свойства отношений

Пусть R – отношение на множестве A, R ∈ A×A . Тогда отношение R:

рефлексивно, если Ɐ a ∈ A: a R a (главная диагональ матрицы рефлексивного отношения содержит только единицы);

антирефлексивно, если Ɐ a ∈ A: a R a (главная диагональ матрицы рефле сивного отношения содержит только нули);

симметрично, если Ɐ a , b ∈ A: a R b ⇒ b R a (матрица такого отношения симметрична относительно главной диагонали, т.е. c ij c ji);

антисимметрично, если Ɐ a, b ∈ A: a R b & b R a ⇒ a = b (в матрице такого отношения отсутствуют единицы, симметричные относительно главной диагонали);

транзитивно, если Ɐ a, b, c ∈ A: a R b & b R c ⇒ a R c (в матрице такого отношения должно выполняться условие: если в i-й строке стоит единица, например в j-ой координате (столбце) строки, т. е. c ij = 1 , то всем единицам в j-ой строке (пусть этим единицам соответствуют k е координаты такие, что, c jk = 1) должны соответствовать единицы в i-й строке в тех же k-х координатах, т. е. c ik = 1 (и, может быть, ещё и в других координатах).

Задача 3.1. Определите свойства отношения R – «быть делителем», заданного на множестве натуральных чисел.

Решение.

отношение R = {(a,b):a делитель b}:

рефлексивно, не антирефлексивно, так как любое число делит само себя без остатка: a/a = 1 для всех a∈N ;

не симметрично, антисимметрично, например, 2 делитель 4, но 4 не является делителем 2;

транзитивно,таккакесли b/a ∈ N и c/b ∈ N, то c/a = b/a ⋅ c/b ∈ N, например, если 6/3 = 2∈N и 18/6 = 3∈N, то 18/3 = 18/6⋅6/3 = 6∈N.

Задача 3.2. Определите свойства отношения R – «быть братом», заданного на множестве людей.
Решение.

Отношение R = {(a,b):a - брат b}:

не рефлексивно, антирефлексивно из-за очевидного отсутствия aRa для всех a;

не симметрично, так как в общем случае между братом a и сестрой b имеет место aRb , но не bRa ;

не антисимметрично, так как если a и b –братья, то aRb и bRa, но a≠b;

транзитивно, если называть братьями людей, имеющих общих родителей (отца и мать).

Задача 3.3. Определите свойства отношения R – «быть начальником», заданного на множестве элементов структуры

Решение.

Отношение R = {(a,b) : a - начальник b}:

• не рефлексивно, антирефлексивно, если в конкретной интерпретации не имеет смысла;
• не симметрично, антисимметрично, так как для всех a≠b не выполняется одновременно aRb и bRa;
• транзитивно, так как если a начальник b и b начальник c , то a начальник c .

Определите свойства отношения R i , заданного на множестве M i матрицей, если:

1. R 1 «иметь один и тот же остаток от деления на 5»; M 1 множество натуральных чисел.
2. R 2 «быть равным»; M 2 множество натуральных чисел.
3. R 3 «жить в одном городе»; M 3 множество людей.
4. R 4 «быть знакомым»; M 4 множество людей.
5. R 5 {(a,b):(a-b) - чётное; M 5 множество чисел {1,2,3,4,5,6,7,8,9}.
6. R 6 {(a,b):(a+b) - чётное; M 6 множество чисел {1,2,3,4,5,6,7,8,9}.
7. R 7 {(a,b):(a+1) - делитель (a+b)} ; M 7 - множество {1,2,3,4,5,6,7,8,9}.
8. R 8 {(a,b):a - делитель (a+b),a≠1}; M 8 - множество натуральных чисел.
9. R 9 «быть сестрой»; M 9 - множество людей.
10. R 10 «быть дочерью»; M 10 - множество людей.

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

Пусть R 1 , R 1 есть отношения, заданные на множестве A .

объединение R 1 ∪ R 2: R 1 ∪ R 2 = {(a,b) : (a,b) ∈ R 1 или (a,b) ∈ R 2 } ;

пересечение R 1 ∩ R 2: R 1 ∩ R 2 = {(a,b) : (a,b) ∈ R 1 и (a,b) ∈ R 2 } ;

разность R 1 \ R 2: R 1 \ R 2 = {(a,b) : (a,b) ∈ R 1 и (a,b) ∉ R 2 } ;

универсальное отношение U: = {(a;b)/a ∈ A & b ∈ A}. ;

дополнение R 1 U \ R 1 , где U = A × A;

тождественное отношение I: = {(a;a) / a ∈ A};

обратное отношение R -11 : R -11 = {(a,b) : (b,a) ∈ R 1 };

композиция R 1 º R 2: R 1 º R 2: = {(a,b) / a ∈ A&b ∈ B& ∃ c ∈ C: aR 1 c & c R 2 b}, где R 1 ⊂ A × C и R 2 ⊂ C × B;

Определение. Степенью отношения R на множестве A называется его композиция с самим собой.

Обозначение:

Определение . Если R ⊂ A × B , то R º R -1 называется ядром отношения R .

Теорема 3.1. Пусть R ⊂ A × A – отношение, заданное на множестве A .

1. R рефлексивно тогда и только тогда, (далее используется знак ⇔) когда I ⊂ R.
2. R симметрично ⇔ R = R -1 .
3. R транзитивно ⇔ R º R ⊂ R
4. R антисимметрично ⇔ R ⌒ R -1 ⊂ I .
5. R антирефлексивно ⇔ R ⌒ I = ∅ .

Задача 3.4 . Пусть R - отношение между множествами {1,2,3} и {1,2,3,4}, заданное перечислением пар: R = {(1,1), (2,3), (2,4), (3,1), (3,4)}. Кроме того, S - отношение между множествами S = {(1,1), (1,2), (2,1), (3,1), (4,2)}. Вычислите R -1 , S -1 и S º R. Проверьте, что (S º R) -1 = R -1 , S -1 .

Решение.
R -1 = {(1,1), (1,3), (3,2), (4,2), (4,3)};
S -1 = {(1,1), (1,2), (1,3), (2,1), (2,4)};
S º R = {(1,1), (1,2), (2,1), (2,2), (3,1), (3,2)};
(S º R) -1 = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3)};
R -1 º S -1 = {(1,1), (1,2), (1,3), (2 ,1), (2,2), (2,3)} = (S º R) -1 .

Задача 3.5 . Пусть R отношение «...родитель...», а S отношение «...брат...» на множестве всех людей. Дайте краткое словесное описание отношениям:

R -1 , S -1 , R º S, S -1 º R -1 и R º R.

Решение.

R -1 - отношение«...ребёнок...»;

S -1 - отношение«...брат или сестра...»;

R º S - отношение «...родитель...»;

S -1 º R -1 - отношение «...ребёнок...»

R º R - отношение «...бабушка или дедушка...»

Задачи для самостоятельного решения

1) Пусть R - отношение «...отец...», а S - отношение «...сестра...» на множестве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , R º S, S -1 º R -1 , R º R.

2) Пусть R - отношение «...брат...», а S - отношение «...мать...» на множестве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , S º R, R -1 º S -1 , S º S.

3) Пусть R - отношение «...дед...», а S - отношение «...сын...» на множестве всех людей. Дайте словесное описание отношениям:

4) Пусть R - отношение «...дочь...», а S - отношение «...бабушка...» на множе- стве всех людей. Дайте словесное описание отношениям:

5) Пусть R - отношение «...племянница...», а S - отношение «...отец...» на множестве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , S º R, R -1 º S -1 , R º R.

6) Пусть R - отношение «сестра...», а S - отношение «мать...» на множестве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , R º S, S -1 º R -1 , S º S.

7) Пусть R - отношение «...мать...», а S - отношение «...сестра...» на множе- стве всех людей. Дайте словесное описание отношениям:

R -1 , S1, R º S, S1 º R1, S º S.

8) Пусть R - отношение «...сын...», а S - отношение «...дед...» на множестве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , S º R, R -1 º S -1 , R º R.

9) Пусть R - отношение «...сестра...», а S - отношение «...отец...» на множе- стве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , R º S, S -1 º R -1 , S º S.

10) Пусть R - отношение «...мать...», а S - отношение «...брат...» на множестве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , S º R, R -1 º S -1 , R º R.

1. Рефлексивность:

2. Слабая рефлексивность:

3. Сильная рефлексивность:

4. Антирефлексивность:

5. Слабая антирефлексивность:

6. Сильная антирефлексивность:

7. Симметричность:

8. Антисимметричность:

9. Асимметричность:

10. Сильная линейность:

11. Слабая линейность:

12. Транзитивность:

Рефлексивность, свойство бинарных (двуместных, двучленных) отношений, выражающее выполнимость их для пар объектов с совпадающими членами (так сказать, между объектом и его "зеркальным отражением"): отношение R называется рефлексивным, если для любого объекта х из области его определения выполняется xRx. Типичные и наиболее важные примеры рефлексивных отношений: отношения типа равенства (тождества, эквивалентности, подобия и т.п.: любой предмет равен самому себе) и отношения нестрогого порядка (любой предмет не меньше и не больше самого себя). Интуитивные представления о "равенстве" (эквивалентности, подобии и т.п.), очевидным образом наделяющие его свойствами симметричности и транзитивности, "вынуждают" и свойство Р., поскольку последнее свойство следует из первых двух. Поэтому многие употребительные в математике отношения, по определению Р. не обладающие, оказывается естественным доопределить таким образом, чтобы они становились рефлексивными, например, считать, что каждая прямая или плоскость параллельна самой себе, и т.п.

Глава 1. Элементы теории множеств

1.1 Множества

Наиболее простая структура данных, используемая в математике, имеет место в случае, когда между отдельными изолированными данными отсутствуют какие-либо взаимосвязи. Совокупность таких данных представляет собой множество . Понятие множества является неопределяемым понятием. Множество не обладает внутренней структурой. Множество можно представить себе как совокупность элементов, обладающих некоторым общим свойством. Для того чтобы некоторую совокупность элементов можно было назвать множеством, необходимо, чтобы выполнялись следующие условия:

Должно существовать правило, позволяющее определить, принадлежит ли указанный элемент данной совокупности.

Должно существовать правило, позволяющее отличать элементы друг от друга. (Это, в частности, означает, что множество не может содержать двух одинаковых элементов).

Множества обычно обозначаются заглавными латинскими буквами. Если элемент

принадлежит множеству , то это обозначается:

Если каждый элемент множества

является также и элементом множества , то говорят, что множество является подмножеством множества :

Подмножество

множества называется собственным подмножеством , если

Используя понятие множества можно построить более сложные и содержательные объекты.

1.2 Операции над множествами

Основными операциями над множествами являются объединение , пересечение и разность .

Определение 1 . Объединением

Определение 2 . Пересечением двух множеств называется новое множество

Определение 3 . Разностью двух множеств называется новое множество

Если класс объектов, на которых определяются различные множества обозначить

(Универсум ), то дополнением множества называют разность упорядоченную n-ку , называют мощностью отношения .

Замечание. Понятие отношения является очень важным не только с математической точки зрения. Понятие отношения фактически лежит в основе всей реляционной теории баз данных. Как будет показано ниже, отношения являются математическим аналогом таблиц . Сам термин "реляционное представление данных", впервые введенный Коддом , происходит от термина relation , понимаемом именно в смысле этого определения.

Т. к. любое множество можно рассматривать как декартовое произведение степени 1, то любое подмножество, как и любое множество, можно считать отношением степени 1. Это не очень интересный пример, свидетельствующий лишь о том, что термины "отношение степени 1" и "подмножество" являются синонимами. Нетривиальность понятия отношения проявляется, когда степень отношения больше 1. Ключевыми здесь являются два момента:

Во-первых , все элементы отношения есть однотипные кортежи. Однотипность кортежей позволяет считать их аналогами строк в простой таблице, т.е. в такой таблице, в которой все строки состоят из одинакового числа ячеек и в соответствующих ячейках содержатся одинаковые типы данных. Например, отношение, состоящее из трех следующих кортежей { (1, "Иванов", 1000), (2, "Петров", 2000), (3, "Сидоров", 3000) } можно считать таблицей, содержащей данные о сотрудниках и их зарплатах. Такая таблица будет иметь три строки и три колонки, причем в каждой колонке содержатся данные одного типа.

В противоположность этому рассмотрим множество { (1), (1,2), (1, 2,3) }, состоящее из разнотипных числовых кортежей. Это множество не является отношением ни в

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

Основы дискретной математики.

Понятие множества. Отношение между множествами.

Множество – совокупность объектов, обладающих определенным свойством, объединенных в единое целое.

Объекты, составляющие множество называются элементами множества. Для того чтобы некоторую совокупность объектов можно было называть множеством должны выполняться следующие условия:

· Должно существовать правило, по которому моно определить принадлежит ли элемент к данной совокупности.

· Должно существовать правило, по которому элементы можно отличить друг от друга.

Множества обозначаются заглавными буквами, а его элементы маленькими. Способы задания множеств:

· Перечисление элементов множества. - для конечных множеств.

· Указание характеристического свойства .

Пустым множеством – называется множество, не содержащее ни одного элемента (Ø).

Два множества называются равными, если они состоят из одних и тех же элементов. , A=B

Множество B называется подмножеством множества А ( , тогда и только тогда когда все элементы множества B принадлежат множеству A .

Например: , B =>

Свойство:

Примечание: обычно рассматривают подмножество одного и того е множества, которое называется универсальным (u). Универсальное множество содержит все элементы.

Операции над множествами.

A

B

1. Объединением 2-х множеств А и В называется такое множество, которому принадлежат элементы множества А или множества В (элементы хотя бы одного из множеств).

2.Пересечением 2-х множеств называется новое множество, состоящее из элементов, одновременно принадлежат и первому и второму множеству.

Н-р: , ,

Свойство: операции объединения и пересечения.

· Коммутативность.

· Ассоциативность. ;

· Дистрибутивный. ;

U

4.Дополнение . Если А – подмножество универсального множества U , то дополнением множества А до множества U (обозначается ) называется множество состоящее из тех элементов множества U , которые не принадлежат множеству А .

Бинарные отношения и их свойства.

Пусть А и В это множества производной природы, рассмотрим упорядоченную пару элементов (а, в) а ϵ А, в ϵ В можно рассматривать упорядоченные «энки».

(а 1 , а 2 , а 3 ,…а n) , где а 1 ϵ А 1 ; а 2 ϵ А 2 ; …; а n ϵ А n ;

Декартовым (прямым) произведением множеств А 1 , А 2 , …, А n , называется мн-во, которое состоит из упорядоченных n k вида .

Н-р: М = {1,2,3}

М× М= М 2 = {(1,1);(1,2);(1,3); (2,1);(2,2);(2,3); (3,1);(3,2);(3,3)}.

Подмножества декартова произведения называется отношением степени n или энарным отношением. Если n =2, то рассматривают бинарные отношения. При чем говорят, что а 1 , а 2 находятся в бинарном отношении R , когда а 1 R а 2.

Бинарным отношением на множестве M называется подмножество прямого произведения множества n самого на себя.

М× М= М 2 = {(a, b )| a, b ϵ M } в предыдущем примере отношение меньше на множестве М порождает следующее множество: {(1,2);(1,3); (2,3)}

Бинарные отношения обладают различными свойствами в том числе:

· Рефлексивность: .

· Антирефлексивность (иррефлексивность): .

· Симметричность: .

· Антисимметричность: .

· Транзитивность: .

· Асимметричность: .

Виды отношений.

· Отношение эквивалентности;

· Отношение порядка.

v Рефлексивное транзитивное отношение называется отношением квазипорядка.

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

v Рефлексивное антисимметричное транзитивное отношение называется отношением (частичного) порядка.

v Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка.

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

Пусть A и B – произвольные множества. Возьмем по одному элементу из каждого множества, a из A, b из B и запишем их так: (сначала элемент первого множества, затем элемент второго множества – т.е. нам важен порядок, в котором берутся элементы). Такой объект будем называть упорядоченной парой . Равными будем считать только те пары, у которых элементы с одинаковыми номерами равны. = , если a = c и b = d. Очевидно, что если a ≠ b, то ≠ .

Декартовым произведением произвольных множеств A и B (обозначается: AB) называется множество, состоящее из всех возможных упорядоченных пар, первый элемент которых принадлежит A, а второй принадлежит B. По определению: AB = { | aA и bB}. Очевидно, что если A≠B, то AB ≠ BA. Декартово произведение множества A само на себя n раз называется декартовой степенью A (обозначается: A n).

Пример 5. Пусть A = {x, y} и B = {1, 2, 3}.

AB = {, , , , , }.

BA = {<1, x>, <2, x>, <3, x>, <1, y>, <2, y>, <3, y>}.

AA = A 2 = {, , , }.

BB = B 2 = {<1, 1>, <1, 2>, <1, 3>, <2, 1>, <2, 2>, <2, 3>, <3, 1>, <3, 2>, <3, 3>}.

Бинарным отношением на множестве M называется множество некоторых упорядоченных пар элементов множества M. Если r – бинарное отношение и пара принадлежит этому отношению, то пишут: r или x r y. Очевидно, r Í M 2 .

Пример 6. Множество {<1, 2>, <2, 2>, <3, 4>, <5, 2>, <2, 4>} является бинарным отношением на множестве {1, 2, 3, 4, 5}.

Пример 7. Отношение ³ на множестве целых чисел является бинарным отношением. Это бесконечное множество упорядоченных пар вида , где x ³ y, x и y – целые числа. Этому отношению принадлежат, например, пары <5, 3>, <2, 2>, <324, -23> и не принадлежат пары <5, 7>, <-3, 2>.

Пример 8. Отношение равенства на множестве A является бинарным отношением: I A = { | x Î A}. I A называется диагональю множества A.

Поскольку бинарные отношения являются множествами, то к ним применимы операции объединения, пересечения, дополнения и разности.

Областью определения бинарного отношения r называется множество D(r) = { x | существует такое y, что xry }. Областью значений бинарного отношения r называется множество R(r) = { y | существует такое x, что xry }.

Отношением, обратным к бинарному отношению r Í M 2 , называется бинарное отношение r -1 = { | Î r}. Очевидно, что D(r ‑1) = R(r), R(r ‑1) = D(r), r ‑ 1 Í M 2 .

Композицией бинарных отношений r 1 и r 2 , заданных на множестве M, называется бинарное отношение r 2 o r 1 = { | существует y такое, что Î r 1 и Í r 2 }. Очевидно, что r 2 o r 1 Í M 2 .

Пример 9. Пусть бинарное отношение r задано на множестве M = {a, b, c, d}, r = {, , , }. Тогда D(r) = {a, c}, R(r) = {b, c, d}, r ‑1 = {, , , }, r o r = {, , , }, r ‑1 o r = {, , , }, r o r ‑1 = {, , , , , , }.

Пусть r – бинарное отношение на множестве M. Отношение r называется рефлексивным , если x r x для любого x Î M. Отношение r называется симметричным , если вместе с каждой парой оно содержит и пару . Отношение r называется транзитивным , если из того, что x r y и y r z следует, что x r z. Отношение r называется антисимметричным , если оно не содержит одновременно пары и различных элементов x ¹ y множества M.

Укажем критерии выполнения этих свойств.

Бинарное отношение r на множестве M рефлексивно тогда и только тогда, когда I M Í r.

Бинарное отношение r симметрично тогда и только тогда, когда r = r ‑1 .

Бинарное отношение r на множестве M антисимметрично тогда и только тогда, когда r Ç r ‑1 = I M .

Бинарное отношение r транзитивно тогда и только тогда, когда r o r Í r.

Пример 10. Отношение из примера 6 является антисимметричным, но не является симметричным, рефлексивным и транзитивным. Отношение из примера 7 является рефлексивным, антисимметричным и транзитивным, но не является симметричным. Отношение I A обладает всеми четырьмя рассматриваемыми свойствами. Отношения r ‑1 o r и r o r ‑1 являются симметричными, транзитивными, но не являются антисимметричными и рефлексивными.

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

Отношением частичного порядка на множестве М называется транзитивное, антисимметричное и рефлексивное на М бинарное отношение r.

Пример 11. Отношение из примера 7 является отношением частичного порядка. Отношение I A является отношением эквивалентности и частичного порядка. Отношение параллельности на множестве прямых является отношением эквивалентности.

Само понятие «отношение», конечно, вам знакомо. Мы часто его употребляем в речи. Например, мы можем сказать, что я в хороших отношениях со всеми студентами моей группы.

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

В параграфе 2.2 мы говорили об отношениях, которые существуют между математическими объектами. Так, элемент по отношению к множеству находится в отношении принадлежности, два множества могут находиться в отношении включения или равенства.

Сейчас мы рассмотрим отношения, которые могут существовать между элементами множеств. Итак, мы сказали, что отношение, установленное между элементами множеств в рассмотренном примере, называется бинарными.

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

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

Бинарные отношения обычно обозначают буквами греческого алфавита: р («ро»), а («сигма»), |/ («пси») и др.

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

Если пара (а, b ) принадлежит бинарному отношению р, т.е. (а, b ) е р, то говорят, что элемент а находится в отношении р с элементом b , и пишут арб. Так, в приведенном выше примере рассмотрено отношение «учиться на факультете». Тогда можно сказать, что Петр находится в данном отношении с факультетом математики.

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

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

Пример 2.6

Пусть заданы два числовых множества: А = {1, 3,5} и В = {2, 8, 10}. Зададим бинарное отношение о между этими множествами перечислением: а = {(1, 2), (5, 10)}. Это же отношение мы может задать и характеристическим свойством: бинарное отношение образуют пары чисел, такие что число из первого множества в два раза меньше числа из второго множества.

Пример 2.7

Рассмотрим множество студентов вашей академической группы. Установим в этом множестве отношение «быть другом». Для любой пары студентов академической группы можно сказать, находятся они в данном отношении или нет. Может даже случиться так, что это бинарное отношение будет образовывать пустое множество. В каком случае это будет?

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

Бинарное отношение, заданное на множестве, может иметь разные свойства. Рассмотрим их.

1. Свойство рефлексивности.

Определение 2.9. рефлексивным , если для любого а е Л пара (а> а) е р.

Отношение «

2. Свойство симметричности.

Определение 2.10. Говорят, что бинарное отношение р, заданное на множестве Л, является симметричным , если для любых элементов а и b из Л из того, что пара (а , b ) находится в отношении р, следует, что пара (b , а) находится в отношении р.

Например, отношение равенства, заданное на множестве действительных чисел, симметрично, так как если число k равно числу п } то и число п равно числу k. Симметричным является и отношение «быть другом».

С другой стороны, отношение упорядоченности по величине (

3. Свойство антисимметричности.

Определение 2.11. Говорят, что бинарное отношение р, заданное на множестве Л, является антисимметричным у если для любых элементов а и b из Л из того, что пары (я, /;) и (/;, а) находятся в отношении р, следует, что а = Ь.

Например, отношение упорядоченности по величине на множестве действительных чисел антисимметрично. Ведь если известно, что для чисел х и у выполнено х и у то это означает, что х - у. А вот отношение параллельности прямых не является антисимметричным, так как если прямая / параллельна прямой t и прямая t параллельна прямой /, то это не означает, что прямые / и t совпадают. Они могут быть различны.

4. Свойство транзитивности.

Определение 2.12. Говорят, что бинарное отношение р, заданное на множестве Л, является транзитивным у если для любых элементов а , b и с из Л из того, что пары (я, b ) и (/?, с) находятся в отношении р, следует, что пара (а, с) также находится в отношении р.

Свойством транзитивности обладают отношения упорядоченности по величине, параллельности, отношение «быть родственником».

Отношение перпендикулярности прямых не является транзитивным (покажите это с помощью рисунка). Также по существу не является транзитивным и отношение «быть другом» (хотя и есть присказка, в которой выражено желание о транзитивности этого отношения: «Друг моего друга - мой друг»).

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

Отношением эквивалентности (или эквивалентностью) называется бинарное отношение, которое обладает свойствами рефлексивности, симметричности и транзитивности.

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

Например, отношение «быть одноклассником» является эквивалентностью, так как оно обладает свойством рефлексивности, симметричности и транзитивности. Отношение «быть не выше ростом» на множестве людей является отношением упорядоченности.

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

Определение 2.13. Разбиением множества/! называется представление этого множества в виде объединения непересекающихся подмножеств, которые называются классами разбиения.

Чтобы проверить, что мы имеем дело с разбиением множества, нужно проверить два условия:

• объединение полученных при разбиении подмножеств является исходным множеством;
• пересечение любых двух различных подмножеств является пустым множеством.

При выполнении классификации классами разбиения являются так называемые классы эквивалентности. Как же строятся эти классы?

Пусть на множестве А введено некоторое отношение эквивалентности р. Возьмем любой элемент а из А и все элементы из А, которые находятся с а в отношении р. Все эти элементы и будут образовывать класс эквивалентности элемента а. Понятно, что и сам элемент а попадет в этот класс. Действительно, если р - отношение эквивалентности, то оно обладает свойством рефлексивности, т.е. (а } а) е р, а это и означает, что сам элемент а входит в класс эквивалентности, который он образует.

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

Действительно, существует теорема, которая говорит о том, что если на множестве задано отношение эквивалентности, то множество всех классов эквивалентности, содержащих элементы этого множества, является разбиением этого множества.

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

Можно попробовать доказать каждое из этих утверждений самостоятельно или разобрать доказательство, которое приведено в работе .

При использовании классов эквивалентности мы разбиваем множество на подмножества, в каждое из которых входят своего рода «одинаковые» элементы. Например, множество всех положительных дробей можно разбить на классы эквивалентности таким образом: 1) взять каждую несокра-

тимую дробь (например, -); 2) в каждый класс эквивалентности соответ-

2 4 6 8 ч т

ствующеи дроби отнести все равные ей дроби - = - = - = 1аким

образом, мы разобьем все положительные дроби на соответствующие классы эквивалентности. Каждый такой класс является положительным рациональным числом.

• В Большой советской энциклопедии говорится, что «отношение - эмоционально-волевая установка личности на что-либо, т.е. выражение ее позиции; мысленное сопоставление различных объектов или сторон данного объекта». В толковом словаре Д. Н. Ушакова«отношение - взаимное общение, связь между людьми, обществами, странами и т.п., образующаяся из общения на какой-нибудь почве».