Бинарные отношения. Примеры бинарных отношений. Понятие отношения на множестве Отношения на множествах и их свойства
Пусть R - некоторое бинарное отношение на множестве X, а х, у, z любые его элементы. Если элемент х находится в отношении R с элементом у, то пишут xRy.
1. Отношение R на множестве X называется рефлексивным, если каждый элемент множества находится в этом отношении с самим собой.
R -рефлексивно на X <=> xRx для любого x€ X
Если отношение R рефлексивно, то в каждой вершине графа имеется петля. Например, отношения равенства и параллельности для отрезков являются рефлексивными, а отношение перпендикулярности и «длиннее» не являются рефлексивными. Это отражают графы на рисунке 42.
2. Отношение R на множестве X называется симметричным, если из того, что элемент х находится в данном отношении с элементом у, следует, что элемент у находится в этом же отношении с элементом х.
R - симметрично на (хЯу =>у Rx)
Граф симметричного отношения содержит парные стрелки, идущие в противоположных направлениях. Отношения параллельности, перпендикулярности и равенства для отрезков обладают симметричностью, а отношение «длиннее» - не является симметричным (рис. 42).
3. Отношение R на множестве X называется антисимметричным, если для различных элементов х и у из множества X из того, что элемент х находится в данном отношении с элементом у, следует, что элемент у в этом отношении с элементом х не находится.
R - антисимметрично на Х« (xRy и xy ≠ yRx)
Замечание: черта сверху обозначает отрицание высказывания.
На графе антисимметричного отношения две точки может соединять только одна стрелка. Примером такого отношения является отношение «длиннее» для отрезков (рис. 42). Отношения параллельности, перпендикулярности и равенства не являются антисимметричными. Существуют отношения, не являющиеся ни симметричными, ни антисимметричными, например отношение «быть братом» (рис. 40).
4. Отношение R на множестве X называется транзитивным, если из того, что элемент х находится в данном отношении с элементом у и элемент у находится в этом лее отношении с элементом z, следует, что элемент х находится в данном отношении с элементом Z
R - транзитивно на A≠ (xRy и yRz=> xRz)
На графах отношений «длиннее», параллельности и равенства на рисунке 42 можно заметить, что если стрелка идет от первого элемента ко второму и от второго к третьему, то обязательно есть стрелка, идущая от первого элемента к третьему. Эти отношения являются транзитивными. Перпендикулярность отрезков не обладает свойством транзитивности.
Существуют и другие свойства отношений между элементами одного множества, которые мы не рассматриваем.
Одно и то же отношение может обладать несколькими свойствами. Так, например, на множестве отрезков отношение «равно» - рефлексивно, симметрично, транзитивно; отношение «больше» - антисимметрично и транзитивно.
Если отношение на множестве X рефлексивно, симметрично и транзитивно, то оно является отношением эквивалентности на этом множестве. Такие отношения разбивают множество X на классы.
Данные отношения проявляются, например, при выполнении заданий: «Подбери полоски равные по длине и разложи по группам», «Разложи мячи так, чтобы в каждой коробке были мячи одного цвета». Отношения эквивалентности («быть равным по длине», «быть одного цвета») определяют в данном случае разбиение множеств полосок и мячей на классы.
Если отношение на множестве 1 транзитивно и антисимметрично, то оно называется отношением порядка на этом множестве.
Множество с заданным на нем отношением порядка называется упорядоченным множеством.
Например, выполняя задания: «Сравни полоски по ширине и разложи их от самой узкой до самой широкой», «Сравни числа и разложи числовые карточки по порядку», дети упорядочивают элементы множеств полосок и числовых карточек при помощи отношений порядка; «быть шире», «следовать за».
Вообще отношения эквивалентности и порядка играют большую роль в формировании у детей правильных представлений о классификации и упорядочении множеств. Кроме того, встречается много других отношений, которые не являются ни отношениями эквивалентности, ни отношениями порядка.
6. Что такое характеристическое свойство множества?
7. В каких отношениях могут находиться множества? Дайте пояснения каждому случаю и изобразите их при помощи кругов Эйлера.
8. Дайте определение подмножества. Приведите пример множеств, одно из которых является подмножеством другого. Запишите их отношение при помощи символов.
9. Дайте определение равных множеств. Приведите примеры двух равных множеств. Запишите их отношение при помощи символов.
10. Дайте определение пересечения двух множеств и изобразите его при помощи кругов Эйлера для каждого частного случая.
11. Дайте определение объединения двух множеств и изобразите его при помощи кругов Эйлера для каждого частного случая.
12. Дайте определение разности двух множеств и изобразите ее при помощи кругов Эйлера для каждого частного случая.
13. Дайте определение дополнения и изобразите его при помощи кругов Эйлера.
14. Что называется разбиением множества на классы? Назовите условия правильной классификации.
15. Что называется соответствием между двумя множествами? Назовите способы задания соответствий.
16. Какое соответствие называется взаимно однозначным?
17. Какие множества называют равномощными?
18. Какие множества называют равночисленными?
19. Назовите способы задания отношений на множестве.
20. Какое отношение на множестве называют рефлексивным?
21. Какое отношение на множестве называют симметричным?
22. Какое отношение на множестве называют антисимметричным?
23. Какое отношение на множестве называют транзитивным?
24. Дайте определение отношения эквивалентности.
25. Дайте определение отношения порядка.
26. Какое множество называют упорядоченным?
Определение . Бинарным отношением 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 матрицей, если:
- R 1 «иметь один и тот же остаток от деления на 5»; M 1 множество натуральных чисел.
- R 2 «быть равным»; M 2 множество натуральных чисел.
- R 3 «жить в одном городе»; M 3 множество людей.
- R 4 «быть знакомым»; M 4 множество людей.
- R 5 {(a,b):(a-b) - чётное; M 5 множество чисел {1,2,3,4,5,6,7,8,9}.
- R 6 {(a,b):(a+b) - чётное; M 6 множество чисел {1,2,3,4,5,6,7,8,9}.
- R 7 {(a,b):(a+1) - делитель (a+b)} ; M 7 - множество {1,2,3,4,5,6,7,8,9}.
- R 8 {(a,b):a - делитель (a+b),a≠1}; M 8 - множество натуральных чисел.
- R 9 «быть сестрой»; M 9 - множество людей.
- 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 .
- R рефлексивно тогда и только тогда, (далее используется знак ⇔) когда I ⊂ R.
- R симметрично ⇔ R = R -1 .
- R транзитивно ⇔ R º R ⊂ R
- R антисимметрично ⇔ R ⌒ R -1 ⊂ I .
- 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.
Отношение, заданное на множестве, может обладать рядом свойств, а именно:
2. Рефлексивность
Определение. Отношение R намножестве Х называется рефлексивным, если каждый элемент х множества Х находится в отношении R с самим собой.
Используя символы, это отношение можно записать в таком виде:
R рефлексивно на Х Û("х Î Х ) х R х
Пример. Отношение равенства на множестве отрезков рефлексивно, т.к. каждый отрезок равен себе самому.
Граф рефлексивного отношения во всех вершинах имеет петли.
2. Антирефлексивность
Определение. Отношение R намножестве Х называется антирефлексивным, если ни один элемент х множества Х не находится в отношении R с самим собой.
R антирефлексивно на Х Û("х Î Х )
Пример. Отношение «прямая х перпендикулярна прямой у » на множестве прямых плоскости антирефлексивно, т.к. ни одна прямая плоскости не перпендикулярна самой себе.
Граф антирефлексивного отношения не содержит ни одной петли.
Заметим, что существуют отношения, не являющиеся ни рефлексивными, ни антирефлексивными. Например, рассмотрим отношение «точка х симметрична точке у » на множестве точек плоскости.
Точка х симметрична точке х – истинно; точка у симметрична точке у – ложно, следовательно, мы не можем утверждать, что все точки плоскости симметричны сами себе, также мы не можем и утверждать, что ни одна точка плоскости не симметрична сама себе.
3. Симметричность
Определение . Отношение R намножестве Х называется симметричным, если из того, что элемент х находится в отношении R с элементом у , следует, что и элемент у находится в отношении R с элементом х .
R симметричнона Х Û("х , у Î Х ) х R у Þ у R х
Пример. Отношение «прямая х пересекает прямую у на множестве прямых плоскости» симметрично, т.к. если прямая х пересекает прямую у , то и прямая у обязательно будет пересекать прямую х .
Граф симметричного отношения вместе с каждой стрелкой из точки х в точку у должен содержать стрелку, соединяющую те же точки, но в обратном направлении.
4. Асимметричность
Определение . Отношение R намножестве Х называется асимметричным, если ни для каких элементов х , у из множества Х не может случиться, что элемент х находится в отношении R с элементом у и элемент у находится в отношении R с элементом х .
R асимметричнона Х Û("х , у Î Х ) х R у Þ
Пример. Отношение «х < у » асимметрично, т.к. ни для какой пары элементов х , у нельзя сказать, что одновременно х < у и у < х .
Граф асимметричного отношения не имеет петель и если две вершины графа соединены стрелкой, то эта стрелка только одна.
5. Антисимметричность
Определение . Отношение R намножестве Х называется антисимметричным, если из того что х находится в отношении с у , а у находится в отношении с х следует, что х = у.
R антисимметричнона Х Û("х , у Î Х ) х R у Ù у R х Þ х = у
Пример. Отношение «х £ у » антисимметрично, т.к. условия х £ у и у £ х одновременно выполняются только тогда, когда х = у.
Граф антисимметричного отношения имеет петли и если две вершины графа соединены стрелкой, то эта стрелка только одна.
6. Транзитивность
Определение . Отношение R намножестве Х называется транзитивным, если для любых элементов х , у , z из множества Х из того, что х находится в отношении с у , а у находится в отношении с z следует, что х находится в отношении с z.
R транзитивнона Х Û("х , у , z Î Х ) х R у Ù у R z Þ х R z
Пример. Отношение «х кратно у » транзитивно, т.к. если первое число кратно второму, а второе кратно третьему, то первое число будет кратно третьему.
Граф транзитивного отношения с каждой парой стрелок от х к у и от у к z содержит стрелку, идущую от х к z.
7. Связность
Определение . Отношение R намножестве Х называется связным, если для любых элементов х , у из множества Х х находится в отношении с у или у находится в отношении с х или х = у .
R связнона Х Û("х , у , z Î Х ) х R у Ú у R z Ú х = у
Другими словами: отношение R намножестве Х называется связным, если для любых различных элементов х , у из множества Х х находится в отношении с у или у находится в отношении с х или х = у .
Пример. Отношение «х < у » связно, т.к. какие бы мы действительные числа не взяли, обязательно одно из них будет больше другого или они равны.
На графе связного отношения все вершины соединены между собой стрелками.
Пример. Проверить, какими свойствами обладает
отношение «х – делитель у », заданное на множестве
Х = {2; 3; 4; 6; 8}.
1) данное отношение рефлексивно, т.к. каждое число из данного множества является делителем самого себя;
2) свойством антирефлексивности данное отношение не обладает;
3) свойство симметричности не выполняется, т.к. например, 2 является делителем числа 4, но 4 делителем числа 2 не является;
4) данное отношение антисимметрично: два числа могут быть одновременно делителями друг друга только в том случае, если эти числа равны;
5) отношение транзитивно, т.к. если одно число является делителем второго, а второе – делителем третьего, то первое число обязательно будет делителем третьего;
6) отношение свойством связности не обладает, т.к. например, числа 2 и 3 на графе стрелкой не соединены, т.к. два различных числа 2 и 3 делителями друг друга не являются.
Таким образом, данное отношение обладает свойствами рефлексивности, асимметричности и транзитивности.
§ 3. Отношение эквивалентности.
Связь отношения эквивалентности с разбиением множества на классы
Определение. Отношение R на множестве Х называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.
Пример. Рассмотрим отношение «х однокурсник у » на множестве студентов педфака. Оно обладает свойствами:
1) рефлексивности, т.к. каждый студент является однокурсником самому себе;
2) симметричности, т.к. если студент х у , то и студент у является однокурсником студента х ;
3) транзитивности, т.к. если студент х - однокурсник у , а студент у – однокурсник z , то студент х будет однокурсником студента z .
Таким образом, данное отношение обладает свойствами рефлексивности, симметричности и транзитивности, а значит, является отношением эквивалентности. При этом множество студентов педфака можно разбить на подмножества, состоящие из студентов, обучающихся на одном курсе. Получаем 5 подмножеств.
Отношением эквивалентности являются также, например, отношение параллельности прямых, отношение равенства фигур. Каждое такое отношение связано с разбиением множества на классы.
Теорема. Если на множестве Х задано отношение эквивалентности, то оно разбивает это множество на попарно непересекающиеся подмножества (классы эквивалентности).
Верно и обратное утверждение: если какое-либо отношение, заданное на множестве Х , порождает разбиение этого множества на классы, то оно является отношением эквивалентности.
Пример. На множестве Х = {1; 2; 3; 4; 5; 6; 7; 8} задано отношение «иметь один и тот же остаток при делении на 3». Является ли оно отношением эквивалентности?
Построим граф данного отношения:
Данное отношение обладает свойствами рефлексивности, симметричности и транзитивности, следовательно, является отношение эквивалентности и разбивает множество Х на классыэквивалентности. В каждом классе эквивалентности будут числа, которые при делении на 3 дают один и тот же остаток: Х 1 = {3; 6}, Х 2 = {1; 4; 7}, Х 3 = {2; 5; 8}.
Считают, что класс эквивалентности определяется любым своим представителем, т.е. произвольным элементом этого класса. Так, класс равных дробей можно задать, указав любую дробь, принадлежащую этому классу.
В начальном курсе математики также встречаются отношения эквивалентности, например, «выражения х и у имеют одинаковые числовые значения», «фигура х равна фигуре у ».
Определения
- 1. Бинарным отношением между элементами множеств А и В называется любое подмножество декартова произведения RAB, RAА.
- 2. Если А=В, то R - это бинарное отношение на A.
- 3. Обозначение: (x, y)R xRy.
- 4. Область определения бинарного отношения R - это множество R = {x: существует y такое, что (x, y)R}.
- 5. Область значений бинарного отношения R - это множество R = {y: существует x такое, что (x, y)R}.
- 6. Дополнение бинарного отношения R между элементами А и В - это множество R = (AB) R.
- 7. Обратное отношение для бинарного отношения R - это множество R1 = {(y, x) : (x, y)R}.
- 8. Произведение отношений R1AB и R2BC - это отношение R1 R2 = {(x, y) : существует zB такое, что (x, z)R1 и (z, y)R2}.
- 9. Отношение f называется функцией из А в В, если выполняется два условия:
- а) f = А, f В
- б) для всех x, y1, y2 из того, что (x, y1)f и (x, y2)f следует y1=y2.
- 10. Отношение f называется функцией из А на В, если в первом пункте будет выполняться f = А, f = В.
- 11. Обозначение: (x, y)f y = f(x).
- 12. Тождественная функция iA: AA определяется так: iA(x) = x.
- 13. Функция f называется 1-1-функцией, если для любых x1, x2, y из того, что y = f(x1) и y = f(x2) следует x1=x2.
- 14. Функция f: AB осуществляет взаимно однозначное соответствие между А и В, если f = А, f = В и f является 1-1-функцией.
- 15. Свойства бинарного отношения R на множестве А:
- - рефлексивность: (x, x)R для всех xA.
- - иррефлексивность: (x, x)R для всех xA.
- - симметричность: (x, y)R (y, x)R.
- - антисимметричность: (x, y)R и (y, x)R x=y.
- - транзитивность: (x, y)R и (y, z)R (x, z)R.
- - дихотомия: либо (x, y)R, либо (y, x)R для всех xA и yA.
- 16. Множества А1, A2, ..., Аr из Р(А) образуют разбиение множества А, если
- - Аi , i = 1, ..., r,
- - A = A1A2...Ar,
- - AiAj = , i j.
Подмножества Аi , i = 1, ..., r, называются блоками разбиения.
- 17. Эквивалентность на множестве А - это рефлексивное, транзитивное и симметричное отношение на А.
- 18. Класс эквивалентности элемента x по эквивалентности R - это множество [x]R={y: (x, y)R}.
- 19. Фактор множество A по R - это множество классов эквивалентности элементов множества А. Обозначение: A/R.
- 20. Классы эквивалентности (элементы фактор множества А/R) образуют разбиение множества А. Обратно. Любому разбиению множества А соответствует отношение эквивалентности R, классы эквивалентности которого совпадают с блоками указанного разбиения. По-другому. Каждый элемент множества А попадает в некоторый класс эквивалентности из A/R. Классы эквивалентности либо не пересекаются, либо совпадают.
- 21. Предпорядок на множестве A - это рефлексивное и транзитивное отношение на А.
- 22. Частичный порядок на множестве A - это рефлексивное, транзитивное и антисимметричное отношение на А.
- 23. Линейный порядок на множестве A - это рефлексивное, транзитивное и антисимметричное отношение на А, удовлетворяющее свойству дихотомии.
Пусть A={1, 2, 3}, B={a, b}. Выпишем декартово произведение: AB = { (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) }. Возьмём любое подмножество этого декартова произведения: R = { (1, a), (1, b), (2, b) }. Тогда R - это бинарное отношение на множествах A и B.
Будет ли это отношение являться функцией? Проверим выполнение двух условий 9a) и 9б). Область определения отношения R - это множество R = {1, 2} {1, 2, 3}, то есть первое условие не выполняется, поэтому в R нужно добавить одну из пар: (3, a) или (3, b). Если добавить обе пары, то не будет выполняться второе условие, так как ab. По этой же причине из R нужно выбросить одну из пар: (1, a) или (1, b). Таким образом, отношение R = { (1, a), (2, b), (3, b) } является функцией. Заметим, что R не является 1-1 функцией.
На заданных множествах A и В функциями также будут являться следующие отношения: { (1, a), (2, a), (3, a) }, { (1, a), (2, a), (3, b) }, { (1, b), (2, b), (3, b) } и т.д.
Пусть A={1, 2, 3}. Примером отношения на множестве A является R = { (1, 1), (2, 1), (2, 3) }. Примером функции на множестве A является f = { (1, 1), (2, 1), (3, 3) }.
Примеры решения задач
1. Найти R, R, R1, RR, RR1, R1R для R = {(x, y) | x, y D и x+y0}.
Если (x, y)R, то x и y пробегают все действительные числа. Поэтому R = R = D.
Если (x, y)R, то x+y0, значит y+x0 и (y, x)R. Поэтому R1=R.
Для любых xD, yD возьмём z=-|max(x, y)|-1, тогда x+z0 и z+y0, т.е. (x, z)R и (z, y)R. Поэтому RR = RR1 = R1R = D2.
2. Для каких бинарных отношений R справедливо R1= R?
Пусть RAB. Возможны два случая:
- (1) AB. Возьмём xAB. Тогда (x, x)R (x, x)R1 (x, x)R (x, x)(AB) R (x, x)R. Противоречие.
- (2) AB=. Так как R1BA, а RAB, то R1= R= . Из R1 = следует, что R = . Из R = следует, что R=AB. Противоречие.
Поэтому если A и B, то таких отношений R не существует.
3. На множестве D действительных чисел определим отношение R следующим образом: (x, y)R (x-y) - рациональное число. Доказать, что R есть эквивалентность.
Рефлексивность:
Для любого xD x-x=0 - рациональное число. Потому (x, x)R.
Симметричность:
Если (x, y)R, то x-y = . Тогда y-x=-(x-y)=- - рациональное число. Поэтому (y, x)R.
Транзитивность:
Если (x, y)R, (y, z)R, то x-y = и y-z =. Складывая эти два уравнения, получаем, что x-z = + - рациональное число. Поэтому (x, z)R.
Следовательно, R - это эквивалентность.
4. Разбиение плоскости D2 состоит из блоков, изображённых на рисунке а). Выписать отношение эквивалентности R, соответствующее этому разбиению, и классы эквивалентности.
Аналогичная задача для b) и c).
а) две точки эквивалентны, если лежат на прямой вида y=2x+b, где b - любое действительное число.
b) две точки (x1,y1) и (x2,y2) эквивалентны, если (целая часть x1 равна целой части x2) и (целая часть y1 равна целой части y2).
с) решить самостоятельно.
Задачи для самостоятельного решения
- 1. Доказать, что если f есть функция из A в B и g есть функция из B в C, то fg есть функция из A в C.
- 2. Пусть A и B - конечные множества, состоящие из m и n элементов соответственно.
Сколько существует бинарных отношений между элементами множеств A и B?
Сколько имеется функций из A в B?
Сколько имеется 1-1 функций из A в B?
При каких m и n существует взаимно-однозначное соответствие между A и B?
3. Доказать, что f удовлетворяет условию f(AB)=f(A)f(B) для любых A и B тогда и только тогда, когда f есть 1-1 функция.
Понятие отношения наряду с понятием множества «пронизывает» всю математику. Интуитивно отношение понимается как связь объектов. Наша задача заключается в том, чтобы, используя сформулированные выше конструкции теории множеств, определить на математическом языке, что же понимается в математике под термином «отношение».
Бинарные отношения на множестве
Пусть дано множество А. Связь элементов хну множества А моделируется парой (ду>). Если элемент х связан с у, значит, мы имеем пару (л:,у) в качестве элемента некоторого множества; если д; не связан с у , значит, пара (л:^) не является объектом множества. Итак, имеем следующее определение.
Бинарным отношением на множестве А называется произвольное множество пар элементов из А.
Другими словами, бинарное отношение на множестве А - ото подмножество прямого произведения АхА=А 2 . В частности, само множество А 2 всех пар является бинарным отношением.
По аналогии с бинарным (или двуместным) отношением можно рассматривать п-местное отношение на множестве как подмножество прямого произведения А". Мы в основном будем рассматривать бинарные отношения, но для краткости речи говорить просто: «отношение на множестве А».
Обозначим произвольное бинарное отношение греческой буквой р.
Если (л",у)е р, то говорят, что л" находится в отношении р с у, и пишут
Если (ду)?Р> то имеем отрицание соответствующего утверждения. В этом случае наряду с записью ~|(хру) (или хру) пишут д-ру, перечеркивая знак отношения.
Пример 8.1.1. Рассмотрим множество А = {1,2,3,4,5}. Множество пар
определяет на А отношение «меньше», обозначаемое знаком <.>
11а этом же множестве можно рассмотреть другое множество пар
оно определяет отношение равенства.
Пример 8.1.2. Рассмотрим множество {N, Z, Q, I, R} основных числовых множеств и множество пар
Имеем отношение, определенное нами в пункте 2.2 как отношение строгого включения множеств. Заметим, что, например, пара (Q. I) нс лежит в указанном множестве, так как Qczl, более того, эти множества не пересекаются.
Пример 8.1.3. Дано множество слов Л={ток, кот, шок, кол, лак}. Рассмотрим такое отношение:
р = {(ток, шок), (шок, ток), (шок, кол), (кол, шок),
(кол, лак), (лак, кол), (кот, кол), (кол, кот)}.
Это отношение можно выразить таким образом: слова множества А находятся в отношении р тогда и только тогда, когда они имеют ровно две одинаковые буквы.
Заметим, что любое множество пар является отношением, неважно, имеется ли для этого отношения хорошее словесное описание.
Так как отношение является множеством, то его можно задать характеристическим свойством, то сеть предикатом Р(ху): р = {(.*,>>) еЛ 2 Р(ху)}. Также используется запись:
Читают: «г находится в отношении с у тогда и только тогда, когда истинно Р(ху)».
Пример 8.1.4. Определим на множестве/! = {1,2,3,4,5} отношение:
Здесь Р(ху) = (л+2=у). Зададим это отношение перечислением пар:
Пример 8.1.5. Зададим на множестве Z (или на множестве N) отношение с помощью предложения: «Существует целое число /?, такое, что х=п у». Символически можно записать:
Имеем уже определенное ранее отношение делимости, обозначаемое знаком:. Этому отношению принадлежат такие пары, как (6,2), (6,3), (4,4), (111, -37) и другие. В отличие от предыдущих примеров это множество пар бесконечно, и перечислить все пары не удастся.
Рассмотрим важнейшие свойства, которыми могут обладать бинарные отношения на множестве.
Отношение р на множестве А называется рефлексивным , если любой элемент х из А находится в отношении р сам с собой, то есть для всех д; из А выполняется лрт:
Пример 8.1.6. Рассмотрим отношение делимости на множестве Z. Возьмем произвольное целое число х. Так как х=х 9 то х‘:х. Значит, любое целое число делится на само себя: V.veZ (л:л). Поэтому отношение делимости рефлексивно.
Так как любое множество является подмножеством самого себя, то отношение включения множеств рефлексивно (на любой совокупности множеств).
Отношение р на множестве А называется аитирефлексивным , если ни один элемент множества А не находится в отношении р с самим собой:
Пример 8.1.7. R антирефлексивно, так как никакое число не меньше самого себя.
Построим отрицание к предложению «Отношение р рефлексивно»:
Таким образом, отношение р не является рефлексивным тогда и только тогда, когда существует элемент хеА, который не находится в отношении р сам с собой. Отношение, не являющееся рефлексивным, не обязано быть аитирефлексивным.
Пример 8.1.8. Рассмотрим отношение на множестве R, заданное предложением «Число х противоположно числу у». Число х называется противоположным числу у, если сумма х+у равна 0.
Это отношение не рефлексивно. Контрпример: х=1. Так как 1 + 1*0, то число 1 не противоположно 1.
Это отношение нс антирефлексивно. Контрпример: ,v=0. Так как 0+0=0, то число 0 противоположно 0.
Отношение р на множестве А называется симметричным , если из того, что х находится в отношении р с у, следует, что у находится в отношении р с
Пример 8.1.9. Из тождества х+у=у+.х вытекает утверждение: для любых действительных чисел х и у если х противоположно v, то у противоположно х. Значит, данное отношение симметрично. Часто говорят просто: «Числа х и у противоположны».
Отношение «Число х меньше числа у» на множестве R не является симметричным: 3 меньше 4, но 4 не меньше 3.
Отношение р на множестве А называется антисимметричным , если ни для каких различных элементов х и у из А, таких, что хру, не выполняется
урх:
Пример 8.1.10. Отношение «меньше» на множестве R антисимметрично.
Определение антисимметричного отношения можно сформулировать другими способами. Введем обозначения:
Используя таблицу истинности, можно доказать, что формула 1Р л М -равносильна формуле М л К -> Р, которая, в свою очередь, по правилу контрапозиции равносильна 1Р ->~|(Л/ л К). На основании этого можно сказать, что отношение р является антисимметричным тогда и только тогда, когда выполняется одно из равносильных условий:
А) Из того, что хру и урх, следует х=у:
Б) Никакие различные элементы не могут одновременно находиться в отношении р друг с другом.
Пример 8.1.11. Рассмотрим отношение включения на произвольном семействе множеств. Так как ЛсУл Y^X=>X=Y, то включение е есть антисимметричное отношение.
Пример 8.1.12. Отношение делимости на множестве Z не является ни симметричным, ни антисимметричным. Так как 4:2, но 2?4, то отношение не симметрично. Так как 2:(-2) и (-2):2, но (-2)^2, то отношение не является антисимметричным.
Однако на множестве N натуральных чисел имеем антисимметричное отношение: Vjt^eN (х:у лу:х ->х=у). Проверьте это утверждение, пользуясь определением делимости.
Отношение р на множестве А называется транзитивным , если из того, что х находится в отношении р с у, а у находится в отношении р с z, следует, что.V находится в отношении р с z:
Пример 8.1.13. Отношение делимости транзитивно (и на множестве Z и на множестве N): х:у л у: z => x:z. Покажем это. Пусть х:у и y:z. Тогда х=пу и y=kz для некоторых целых чисел п и к. Тогда х = n(kz) = (nk)z = mz, где т есть целое число. Поэтому xz.
Отношение включения множеств также транзитивно: XcY л YcZ => XezZ. Докажите.
Отношение «Числа х и у противоположны» не является транзитивным. Контрпример: х=2,у=-2, 2=2. Тогда числа 2 и (-2) противоположны, а также (-2) и 2 противоположны. Но числа х=2 и z=2 нс являются противоположными.
Пример 8.1.14. Рассмотрим некоторые примеры отношений из предыдущего пункта.
Отношение из примера 8.1.3 антирефлексивно и симметрично. Отношение из примера 8.1.4 антирефлексивно и антисимметрично. Ни одно из этих отношений нс транзитивно. Докажите это, рассмотрев соответствующие контрпримеры.
Некоторым отношениям, обладающим одновременно рядом свойств, даны общие называния. Из рассмотренных выше примеров одновременно свойствами рефлексивности, антисиммегричности и транзитивности обладают отношение включения множеств с и отношение делимости на множестве N. Также этими тремя свойствами обладает отношение «х меньше либо равно у », определенное на множестве R (или на любом его подмножестве):
Рефлексивное, антисимметричное и транзитивное отношение называется отношением порядка.
Множество А , на котором задано отношение порядка р, называется упорядоченным множеством . Пишут (А, р).
В настоящее время теория упорядоченных множеств - это большой раздел математики, которому посвящены целые книги. Мы отметим лишь ряд особенностей понятия «упорядоченное множество».
Интуитивно слова «упорядоченное множество» часто понимаются в более узком смысле. Рассмотрим упорядоченную л-ку, составленную из попарно различных элементов. Например, пятерка букв (III,К,О,Л,А) определяет слово ШКОЛА. В этом случае слова «элементы записаны в определенном порядке» понимаются в том смысле, что мы занумеровали их натуральными числами 1, 2, 3, 4, 5 и расположили в порядке возрастания номеров. Обобщим этот пример.
Пусть дано «-элементное множество А. Занумеровав каким-то образом ею элементы а, а 2 >а„, мы действительно получим упорядоченное множество, определив отношение порядка следующим образом:
Соотношение понимается так: то, что элемент х связан с другим элементом у, означает, что х записан в кортеже левее у.
Пример 8.1.15. Дано множество /4={а,б.в,г}. Упорядоченная четверка его различных элементов (б,в,а,г) задаст такое отношение порядка:
{(б,б), (б,в), (б,а), (б,г), (в,в), (в,а), (в,г), (а,а), (а,г), (г,г)}.
Заметим, что порядок не обязан обладать так называемым свойством линейности.
Пример 8.1.16. Рассмотрим на множестве А = {2,4,6,8} отношение делимости:. Задайте это отношение множеством пар. Так как в А лежат только натуральные числа, то: отношение порядка. Имеем упорядоченное множество А, :).
Такой порядок нельзя представить в виде упорядоченной четверки следующих друг за другом элементов. Можно привести графическую иллюстрацию отношения с помощью точек и стрелок: из точки х в точку у ведет стрелка тогда и только тогда, когда х:у.
Рассмотрим числа 6 и 4. Ни одно из них нс делится на другое. Говорят, что это несравнимые элементы.
Пусть на множестве А задано отношение порядка р. Элементы * и у называются сравнимыми , если выполняется хотя бы одно из двух соотношений хру или урх.
Порядок р на множестве А называется линейным , если любые два элемента множества А сравнимы. Множество, на котором определен линейный порядок, называется линейно упорядоченным (или цепью).
Пример 8.1.17. Отношение R является линейным порядком, так как Vx^yeR (х Поэтому (R,
упорядоченное множество.
Отношение делимости натуральных чисел в общем случае не является линейным порядком. Контрпример дан в примере 8.1.16.»
Отмстим, что любой линейный порядок на конечном множестве задается нумерацией его элементов. Чтобы подчеркнуть, что порядок может быть нс линейным, упорядоченное множество в общем случае иногда называют частично упорядоченным.
- Секреты молодости и красоты екатерины андреевой Рецепт красоты от екатерины андреевой
- Как нарисовать барабаны Как нарисовать барабан карандашом поэтапно
- Щадящая диета для похудения живота: рацион, правила Правила составления рациона
- Что делать с коровой, которая не встает после отела Если подняться не получается